ptrveloc.c revision 35c4bbdf 
1/*
2 *
3 * Copyright © 2006-2009 Simon Thum             simon dot thum at gmx dot de
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
23 */
24
25#ifdef HAVE_DIX_CONFIG_H
26#include <dix-config.h>
27#endif
28
29#include <math.h>
30#include <ptrveloc.h>
31#include <exevents.h>
32#include <X11/Xatom.h>
33#include <os.h>
34
35#include <xserver-properties.h>
36
37/*****************************************************************************
38 * Predictable pointer acceleration
39 *
40 * 2006-2009 by Simon Thum (simon [dot] thum [at] gmx de)
41 *
42 * Serves 3 complementary functions:
43 * 1) provide a sophisticated ballistic velocity estimate to improve
44 *    the relation between velocity (of the device) and acceleration
45 * 2) make arbitrary acceleration profiles possible
46 * 3) decelerate by two means (constant and adaptive) if enabled
47 *
48 * Important concepts are the
49 *
50 * - Scheme
51 *      which selects the basic algorithm
52 *      (see devices.c/InitPointerAccelerationScheme)
53 * - Profile
54 *      which returns an acceleration
55 *      for a given velocity
56 *
57 *  The profile can be selected by the user at runtime.
58 *  The classic profile is intended to cleanly perform old-style
59 *  function selection (threshold =/!= 0)
60 *
61 ****************************************************************************/
62
63/* fwds */
64static double
65SimpleSmoothProfile(DeviceIntPtr dev, DeviceVelocityPtr vel, double velocity,
66                    double threshold, double acc);
67static PointerAccelerationProfileFunc
68GetAccelerationProfile(DeviceVelocityPtr vel, int profile_num);
69static BOOL
70InitializePredictableAccelerationProperties(DeviceIntPtr,
71                                            DeviceVelocityPtr,
72                                            PredictableAccelSchemePtr);
73static BOOL
74DeletePredictableAccelerationProperties(DeviceIntPtr,
75                                        PredictableAccelSchemePtr);
76
77/*#define PTRACCEL_DEBUGGING*/
78
79#ifdef PTRACCEL_DEBUGGING
80#define DebugAccelF(...) ErrorFSigSafe("dix/ptraccel: " __VA_ARGS__)
81#else
82#define DebugAccelF(...)        /* */
83#endif
84
85/********************************
86 *  Init/Uninit
87 *******************************/
88
89/* some int which is not a profile number */
90#define PROFILE_UNINITIALIZE (-100)
91
92/**
93 * Init DeviceVelocity struct so it should match the average case
94 */
95void
96InitVelocityData(DeviceVelocityPtr vel)
97{
98    memset(vel, 0, sizeof(DeviceVelocityRec));
99
100    vel->corr_mul = 10.0;       /* dots per 10 milisecond should be usable */
101    vel->const_acceleration = 1.0;      /* no acceleration/deceleration  */
102    vel->reset_time = 300;
103    vel->use_softening = 1;
104    vel->min_acceleration = 1.0;        /* don't decelerate */
105    vel->max_rel_diff = 0.2;
106    vel->max_diff = 1.0;
107    vel->initial_range = 2;
108    vel->average_accel = TRUE;
109    SetAccelerationProfile(vel, AccelProfileClassic);
110    InitTrackers(vel, 16);
111}
112
113/**
114 * Clean up DeviceVelocityRec
115 */
116void
117FreeVelocityData(DeviceVelocityPtr vel)
118{
119    free(vel->tracker);
120    SetAccelerationProfile(vel, PROFILE_UNINITIALIZE);
121}
122
123/**
124 * Init predictable scheme
125 */
126Bool
127InitPredictableAccelerationScheme(DeviceIntPtr dev,
128                                  ValuatorAccelerationPtr protoScheme)
129{
130    DeviceVelocityPtr vel;
131    ValuatorAccelerationRec scheme;
132    PredictableAccelSchemePtr schemeData;
133
134    scheme = *protoScheme;
135    vel = calloc(1, sizeof(DeviceVelocityRec));
136    schemeData = calloc(1, sizeof(PredictableAccelSchemeRec));
137    if (!vel || !schemeData) {
138        free(vel);
139        free(schemeData);
140        return FALSE;
141    }
142    InitVelocityData(vel);
143    schemeData->vel = vel;
144    scheme.accelData = schemeData;
145    if (!InitializePredictableAccelerationProperties(dev, vel, schemeData)) {
146        free(vel);
147        free(schemeData);
148        return FALSE;
149    }
150    /* all fine, assign scheme to device */
151    dev->valuator->accelScheme = scheme;
152    return TRUE;
153}
154
155/**
156 *  Uninit scheme
157 */
158void
159AccelerationDefaultCleanup(DeviceIntPtr dev)
160{
161    DeviceVelocityPtr vel = GetDevicePredictableAccelData(dev);
162
163    if (vel) {
164        /* the proper guarantee would be that we're not inside of
165         * AccelSchemeProc(), but that seems impossible. Schemes don't get
166         * switched often anyway.
167         */
168        OsBlockSignals();
169        dev->valuator->accelScheme.AccelSchemeProc = NULL;
170        FreeVelocityData(vel);
171        free(vel);
172        DeletePredictableAccelerationProperties(dev,
173                                                (PredictableAccelSchemePtr)
174                                                dev->valuator->accelScheme.
175                                                accelData);
176        free(dev->valuator->accelScheme.accelData);
177        dev->valuator->accelScheme.accelData = NULL;
178        OsReleaseSignals();
179    }
180}
181
182/*************************
183 * Input property support
184 ************************/
185
186/**
187 * choose profile
188 */
189static int
190AccelSetProfileProperty(DeviceIntPtr dev, Atom atom,
191                        XIPropertyValuePtr val, BOOL checkOnly)
192{
193    DeviceVelocityPtr vel;
194    int profile, *ptr = &profile;
195    int rc;
196    int nelem = 1;
197
198    if (atom != XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER))
199        return Success;
200
201    vel = GetDevicePredictableAccelData(dev);
202    if (!vel)
203        return BadValue;
204    rc = XIPropToInt(val, &nelem, &ptr);
205
206    if (checkOnly) {
207        if (rc)
208            return rc;
209
210        if (GetAccelerationProfile(vel, profile) == NULL)
211            return BadValue;
212    }
213    else
214        SetAccelerationProfile(vel, profile);
215
216    return Success;
217}
218
219static long
220AccelInitProfileProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
221{
222    int profile = vel->statistics.profile_number;
223    Atom prop_profile_number = XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER);
224
225    XIChangeDeviceProperty(dev, prop_profile_number, XA_INTEGER, 32,
226                           PropModeReplace, 1, &profile, FALSE);
227    XISetDevicePropertyDeletable(dev, prop_profile_number, FALSE);
228    return XIRegisterPropertyHandler(dev, AccelSetProfileProperty, NULL, NULL);
229}
230
231/**
232 * constant deceleration
233 */
234static int
235AccelSetDecelProperty(DeviceIntPtr dev, Atom atom,
236                      XIPropertyValuePtr val, BOOL checkOnly)
237{
238    DeviceVelocityPtr vel;
239    float v, *ptr = &v;
240    int rc;
241    int nelem = 1;
242
243    if (atom != XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION))
244        return Success;
245
246    vel = GetDevicePredictableAccelData(dev);
247    if (!vel)
248        return BadValue;
249    rc = XIPropToFloat(val, &nelem, &ptr);
250
251    if (checkOnly) {
252        if (rc)
253            return rc;
254        return (v > 0) ? Success : BadValue;
255    }
256
257    vel->const_acceleration = 1 / v;
258
259    return Success;
260}
261
262static long
263AccelInitDecelProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
264{
265    float fval = 1.0 / vel->const_acceleration;
266    Atom prop_const_decel =
267        XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION);
268    XIChangeDeviceProperty(dev, prop_const_decel,
269                           XIGetKnownProperty(XATOM_FLOAT), 32, PropModeReplace,
270                           1, &fval, FALSE);
271    XISetDevicePropertyDeletable(dev, prop_const_decel, FALSE);
272    return XIRegisterPropertyHandler(dev, AccelSetDecelProperty, NULL, NULL);
273}
274
275/**
276 * adaptive deceleration
277 */
278static int
279AccelSetAdaptDecelProperty(DeviceIntPtr dev, Atom atom,
280                           XIPropertyValuePtr val, BOOL checkOnly)
281{
282    DeviceVelocityPtr veloc;
283    float v, *ptr = &v;
284    int rc;
285    int nelem = 1;
286
287    if (atom != XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION))
288        return Success;
289
290    veloc = GetDevicePredictableAccelData(dev);
291    if (!veloc)
292        return BadValue;
293    rc = XIPropToFloat(val, &nelem, &ptr);
294
295    if (checkOnly) {
296        if (rc)
297            return rc;
298        return (v >= 1.0f) ? Success : BadValue;
299    }
300
301    if (v >= 1.0f)
302        veloc->min_acceleration = 1 / v;
303
304    return Success;
305}
306
307static long
308AccelInitAdaptDecelProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
309{
310    float fval = 1.0 / vel->min_acceleration;
311    Atom prop_adapt_decel =
312        XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION);
313
314    XIChangeDeviceProperty(dev, prop_adapt_decel,
315                           XIGetKnownProperty(XATOM_FLOAT), 32, PropModeReplace,
316                           1, &fval, FALSE);
317    XISetDevicePropertyDeletable(dev, prop_adapt_decel, FALSE);
318    return XIRegisterPropertyHandler(dev, AccelSetAdaptDecelProperty, NULL,
319                                     NULL);
320}
321
322/**
323 * velocity scaling
324 */
325static int
326AccelSetScaleProperty(DeviceIntPtr dev, Atom atom,
327                      XIPropertyValuePtr val, BOOL checkOnly)
328{
329    DeviceVelocityPtr vel;
330    float v, *ptr = &v;
331    int rc;
332    int nelem = 1;
333
334    if (atom != XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING))
335        return Success;
336
337    vel = GetDevicePredictableAccelData(dev);
338    if (!vel)
339        return BadValue;
340    rc = XIPropToFloat(val, &nelem, &ptr);
341
342    if (checkOnly) {
343        if (rc)
344            return rc;
345
346        return (v > 0) ? Success : BadValue;
347    }
348
349    if (v > 0)
350        vel->corr_mul = v;
351
352    return Success;
353}
354
355static long
356AccelInitScaleProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
357{
358    float fval = vel->corr_mul;
359    Atom prop_velo_scale = XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING);
360
361    XIChangeDeviceProperty(dev, prop_velo_scale,
362                           XIGetKnownProperty(XATOM_FLOAT), 32, PropModeReplace,
363                           1, &fval, FALSE);
364    XISetDevicePropertyDeletable(dev, prop_velo_scale, FALSE);
365    return XIRegisterPropertyHandler(dev, AccelSetScaleProperty, NULL, NULL);
366}
367
368static BOOL
369InitializePredictableAccelerationProperties(DeviceIntPtr dev,
370                                            DeviceVelocityPtr vel,
371                                            PredictableAccelSchemePtr
372                                            schemeData)
373{
374    int num_handlers = 4;
375
376    if (!vel)
377        return FALSE;
378
379    schemeData->prop_handlers = calloc(num_handlers, sizeof(long));
380    if (!schemeData->prop_handlers)
381        return FALSE;
382    schemeData->num_prop_handlers = num_handlers;
383    schemeData->prop_handlers[0] = AccelInitProfileProperty(dev, vel);
384    schemeData->prop_handlers[1] = AccelInitDecelProperty(dev, vel);
385    schemeData->prop_handlers[2] = AccelInitAdaptDecelProperty(dev, vel);
386    schemeData->prop_handlers[3] = AccelInitScaleProperty(dev, vel);
387
388    return TRUE;
389}
390
391BOOL
392DeletePredictableAccelerationProperties(DeviceIntPtr dev,
393                                        PredictableAccelSchemePtr scheme)
394{
395    DeviceVelocityPtr vel;
396    Atom prop;
397    int i;
398
399    prop = XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING);
400    XIDeleteDeviceProperty(dev, prop, FALSE);
401    prop = XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION);
402    XIDeleteDeviceProperty(dev, prop, FALSE);
403    prop = XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION);
404    XIDeleteDeviceProperty(dev, prop, FALSE);
405    prop = XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER);
406    XIDeleteDeviceProperty(dev, prop, FALSE);
407
408    vel = GetDevicePredictableAccelData(dev);
409    if (vel) {
410        for (i = 0; i < scheme->num_prop_handlers; i++)
411            if (scheme->prop_handlers[i])
412                XIUnregisterPropertyHandler(dev, scheme->prop_handlers[i]);
413    }
414
415    free(scheme->prop_handlers);
416    scheme->prop_handlers = NULL;
417    scheme->num_prop_handlers = 0;
418    return TRUE;
419}
420
421/*********************
422 * Tracking logic
423 ********************/
424
425void
426InitTrackers(DeviceVelocityPtr vel, int ntracker)
427{
428    if (ntracker < 1) {
429        ErrorF("invalid number of trackers\n");
430        return;
431    }
432    free(vel->tracker);
433    vel->tracker = (MotionTrackerPtr) calloc(ntracker, sizeof(MotionTracker));
434    vel->num_tracker = ntracker;
435}
436
437enum directions {
438    N = (1 << 0),
439    NE = (1 << 1),
440    E = (1 << 2),
441    SE = (1 << 3),
442    S = (1 << 4),
443    SW = (1 << 5),
444    W = (1 << 6),
445    NW = (1 << 7),
446    UNDEFINED = 0xFF
447};
448
449/**
450 * return a bit field of possible directions.
451 * There's no reason against widening to more precise directions (<45 degrees),
452 * should it not perform well. All this is needed for is sort out non-linear
453 * motion, so precision isn't paramount. However, one should not flag direction
454 * too narrow, since it would then cut the linear segment to zero size way too
455 * often.
456 *
457 * @return A bitmask for N, NE, S, SE, etc. indicating the directions for
458 * this movement.
459 */
460static int
461DoGetDirection(int dx, int dy)
462{
463    int dir = 0;
464
465    /* on insignificant mickeys, flag 135 degrees */
466    if (abs(dx) < 2 && abs(dy) < 2) {
467        /* first check diagonal cases */
468        if (dx > 0 && dy > 0)
469            dir = E | SE | S;
470        else if (dx > 0 && dy < 0)
471            dir = N | NE | E;
472        else if (dx < 0 && dy < 0)
473            dir = W | NW | N;
474        else if (dx < 0 && dy > 0)
475            dir = W | SW | S;
476        /* check axis-aligned directions */
477        else if (dx > 0)
478            dir = NE | E | SE;
479        else if (dx < 0)
480            dir = NW | W | SW;
481        else if (dy > 0)
482            dir = SE | S | SW;
483        else if (dy < 0)
484            dir = NE | N | NW;
485        else
486            dir = UNDEFINED;    /* shouldn't happen */
487    }
488    else {                      /* compute angle and set appropriate flags */
489        double r;
490        int i1, i2;
491
492        r = atan2(dy, dx);
493        /* find direction.
494         *
495         * Add 360° to avoid r become negative since C has no well-defined
496         * modulo for such cases. Then divide by 45° to get the octant
497         * number,  e.g.
498         *          0 <= r <= 1 is [0-45]°
499         *          1 <= r <= 2 is [45-90]°
500         *          etc.
501         * But we add extra 90° to match up with our N, S, etc. defines up
502         * there, rest stays the same.
503         */
504        r = (r + (M_PI * 2.5)) / (M_PI / 4);
505        /* this intends to flag 2 directions (45 degrees),
506         * except on very well-aligned mickeys. */
507        i1 = (int) (r + 0.1) % 8;
508        i2 = (int) (r + 0.9) % 8;
509        if (i1 < 0 || i1 > 7 || i2 < 0 || i2 > 7)
510            dir = UNDEFINED;    /* shouldn't happen */
511        else
512            dir = (1 << i1 | 1 << i2);
513    }
514    return dir;
515}
516
517#define DIRECTION_CACHE_RANGE 5
518#define DIRECTION_CACHE_SIZE (DIRECTION_CACHE_RANGE*2+1)
519
520/* cache DoGetDirection().
521 * To avoid excessive use of direction calculation, cache the values for
522 * [-5..5] for both x/y. Anything outside of that is calcualted on the fly.
523 *
524 * @return A bitmask for N, NE, S, SE, etc. indicating the directions for
525 * this movement.
526 */
527static int
528GetDirection(int dx, int dy)
529{
530    static int cache[DIRECTION_CACHE_SIZE][DIRECTION_CACHE_SIZE];
531    int dir;
532
533    if (abs(dx) <= DIRECTION_CACHE_RANGE && abs(dy) <= DIRECTION_CACHE_RANGE) {
534        /* cacheable */
535        dir = cache[DIRECTION_CACHE_RANGE + dx][DIRECTION_CACHE_RANGE + dy];
536        if (dir == 0) {
537            dir = DoGetDirection(dx, dy);
538            cache[DIRECTION_CACHE_RANGE + dx][DIRECTION_CACHE_RANGE + dy] = dir;
539        }
540    }
541    else {
542        /* non-cacheable */
543        dir = DoGetDirection(dx, dy);
544    }
545
546    return dir;
547}
548
549#undef DIRECTION_CACHE_RANGE
550#undef DIRECTION_CACHE_SIZE
551
552/* convert offset (age) to array index */
553#define TRACKER_INDEX(s, d) (((s)->num_tracker + (s)->cur_tracker - (d)) % (s)->num_tracker)
554#define TRACKER(s, d) &(s)->tracker[TRACKER_INDEX(s,d)]
555
556/**
557 * Add the delta motion to each tracker, then reset the latest tracker to
558 * 0/0 and set it as the current one.
559 */
560static inline void
561FeedTrackers(DeviceVelocityPtr vel, double dx, double dy, int cur_t)
562{
563    int n;
564
565    for (n = 0; n < vel->num_tracker; n++) {
566        vel->tracker[n].dx += dx;
567        vel->tracker[n].dy += dy;
568    }
569    n = (vel->cur_tracker + 1) % vel->num_tracker;
570    vel->tracker[n].dx = 0.0;
571    vel->tracker[n].dy = 0.0;
572    vel->tracker[n].time = cur_t;
573    vel->tracker[n].dir = GetDirection(dx, dy);
574    DebugAccelF("motion [dx: %f dy: %f dir:%d diff: %d]\n",
575                dx, dy, vel->tracker[n].dir,
576                cur_t - vel->tracker[vel->cur_tracker].time);
577    vel->cur_tracker = n;
578}
579
580/**
581 * calc velocity for given tracker, with
582 * velocity scaling.
583 * This assumes linear motion.
584 */
585static double
586CalcTracker(const MotionTracker * tracker, int cur_t)
587{
588    double dist = sqrt(tracker->dx * tracker->dx + tracker->dy * tracker->dy);
589    int dtime = cur_t - tracker->time;
590
591    if (dtime > 0)
592        return dist / dtime;
593    else
594        return 0;               /* synonymous for NaN, since we're not C99 */
595}
596
597/* find the most plausible velocity. That is, the most distant
598 * (in time) tracker which isn't too old, the movement vector was
599 * in the same octant, and where the velocity is within an
600 * acceptable range to the inital velocity.
601 *
602 * @return The tracker's velocity or 0 if the above conditions are unmet
603 */
604static double
605QueryTrackers(DeviceVelocityPtr vel, int cur_t)
606{
607    int offset, dir = UNDEFINED, used_offset = -1, age_ms;
608
609    /* initial velocity: a low-offset, valid velocity */
610    double initial_velocity = 0, result = 0, velocity_diff;
611    double velocity_factor = vel->corr_mul * vel->const_acceleration;   /* premultiply */
612
613    /* loop from current to older data */
614    for (offset = 1; offset < vel->num_tracker; offset++) {
615        MotionTracker *tracker = TRACKER(vel, offset);
616        double tracker_velocity;
617
618        age_ms = cur_t - tracker->time;
619
620        /* bail out if data is too old and protect from overrun */
621        if (age_ms >= vel->reset_time || age_ms < 0) {
622            DebugAccelF("query: tracker too old (reset after %d, age is %d)\n",
623                        vel->reset_time, age_ms);
624            break;
625        }
626
627        /*
628         * this heuristic avoids using the linear-motion velocity formula
629         * in CalcTracker() on motion that isn't exactly linear. So to get
630         * even more precision we could subdivide as a final step, so possible
631         * non-linearities are accounted for.
632         */
633        dir &= tracker->dir;
634        if (dir == 0) {         /* we've changed octant of movement (e.g. NE → NW) */
635            DebugAccelF("query: no longer linear\n");
636            /* instead of breaking it we might also inspect the partition after,
637             * but actual improvement with this is probably rare. */
638            break;
639        }
640
641        tracker_velocity = CalcTracker(tracker, cur_t) * velocity_factor;
642
643        if ((initial_velocity == 0 || offset <= vel->initial_range) &&
644            tracker_velocity != 0) {
645            /* set initial velocity and result */
646            result = initial_velocity = tracker_velocity;
647            used_offset = offset;
648        }
649        else if (initial_velocity != 0 && tracker_velocity != 0) {
650            velocity_diff = fabs(initial_velocity - tracker_velocity);
651
652            if (velocity_diff > vel->max_diff &&
653                velocity_diff / (initial_velocity + tracker_velocity) >=
654                vel->max_rel_diff) {
655                /* we're not in range, quit - it won't get better. */
656                DebugAccelF("query: tracker too different:"
657                            " old %2.2f initial %2.2f diff: %2.2f\n",
658                            tracker_velocity, initial_velocity, velocity_diff);
659                break;
660            }
661            /* we're in range with the initial velocity,
662             * so this result is likely better
663             * (it contains more information). */
664            result = tracker_velocity;
665            used_offset = offset;
666        }
667    }
668    if (offset == vel->num_tracker) {
669        DebugAccelF("query: last tracker in effect\n");
670        used_offset = vel->num_tracker - 1;
671    }
672    if (used_offset >= 0) {
673#ifdef PTRACCEL_DEBUGGING
674        MotionTracker *tracker = TRACKER(vel, used_offset);
675
676        DebugAccelF("result: offset %i [dx: %f dy: %f diff: %i]\n",
677                    used_offset, tracker->dx, tracker->dy,
678                    cur_t - tracker->time);
679#endif
680    }
681    return result;
682}
683
684#undef TRACKER_INDEX
685#undef TRACKER
686
687/**
688 * Perform velocity approximation based on 2D 'mickeys' (mouse motion delta).
689 * return true if non-visible state reset is suggested
690 */
691BOOL
692ProcessVelocityData2D(DeviceVelocityPtr vel, double dx, double dy, int time)
693{
694    double velocity;
695
696    vel->last_velocity = vel->velocity;
697
698    FeedTrackers(vel, dx, dy, time);
699
700    velocity = QueryTrackers(vel, time);
701
702    DebugAccelF("velocity is %f\n", velocity);
703
704    vel->velocity = velocity;
705    return velocity == 0;
706}
707
708/**
709 * this flattens significant ( > 1) mickeys a little bit for more steady
710 * constant-velocity response
711 */
712static inline double
713ApplySimpleSoftening(double prev_delta, double delta)
714{
715    double result = delta;
716
717    if (delta < -1.0 || delta > 1.0) {
718        if (delta > prev_delta)
719            result -= 0.5;
720        else if (delta < prev_delta)
721            result += 0.5;
722    }
723    return result;
724}
725
726/**
727 * Soften the delta based on previous deltas stored in vel.
728 *
729 * @param[in,out] fdx Delta X, modified in-place.
730 * @param[in,out] fdx Delta Y, modified in-place.
731 */
732static void
733ApplySoftening(DeviceVelocityPtr vel, double *fdx, double *fdy)
734{
735    if (vel->use_softening) {
736        *fdx = ApplySimpleSoftening(vel->last_dx, *fdx);
737        *fdy = ApplySimpleSoftening(vel->last_dy, *fdy);
738    }
739}
740
741static void
742ApplyConstantDeceleration(DeviceVelocityPtr vel, double *fdx, double *fdy)
743{
744    *fdx *= vel->const_acceleration;
745    *fdy *= vel->const_acceleration;
746}
747
748/*
749 * compute the acceleration for given velocity and enforce min_acceleration
750 */
751double
752BasicComputeAcceleration(DeviceIntPtr dev,
753                         DeviceVelocityPtr vel,
754                         double velocity, double threshold, double acc)
755{
756
757    double result;
758
759    result = vel->Profile(dev, vel, velocity, threshold, acc);
760
761    /* enforce min_acceleration */
762    if (result < vel->min_acceleration)
763        result = vel->min_acceleration;
764    return result;
765}
766
767/**
768 * Compute acceleration. Takes into account averaging, nv-reset, etc.
769 * If the velocity has changed, an average is taken of 6 velocity factors:
770 * current velocity, last velocity and 4 times the average between the two.
771 */
772static double
773ComputeAcceleration(DeviceIntPtr dev,
774                    DeviceVelocityPtr vel, double threshold, double acc)
775{
776    double result;
777
778    if (vel->velocity <= 0) {
779        DebugAccelF("profile skipped\n");
780        /*
781         * If we have no idea about device velocity, don't pretend it.
782         */
783        return 1;
784    }
785
786    if (vel->average_accel && vel->velocity != vel->last_velocity) {
787        /* use simpson's rule to average acceleration between
788         * current and previous velocity.
789         * Though being the more natural choice, it causes a minor delay
790         * in comparison, so it can be disabled. */
791        result =
792            BasicComputeAcceleration(dev, vel, vel->velocity, threshold, acc);
793        result +=
794            BasicComputeAcceleration(dev, vel, vel->last_velocity, threshold,
795                                     acc);
796        result +=
797            4.0f * BasicComputeAcceleration(dev, vel,
798                                            (vel->last_velocity +
799                                             vel->velocity) / 2,
800                                            threshold,
801                                            acc);
802        result /= 6.0f;
803        DebugAccelF("profile average [%.2f ... %.2f] is %.3f\n",
804                    vel->velocity, vel->last_velocity, result);
805    }
806    else {
807        result = BasicComputeAcceleration(dev, vel,
808                                          vel->velocity, threshold, acc);
809        DebugAccelF("profile sample [%.2f] is %.3f\n",
810                    vel->velocity, result);
811    }
812
813    return result;
814}
815
816/*****************************************
817 *  Acceleration functions and profiles
818 ****************************************/
819
820/**
821 * Polynomial function similar previous one, but with f(1) = 1
822 */
823static double
824PolynomialAccelerationProfile(DeviceIntPtr dev,
825                              DeviceVelocityPtr vel,
826                              double velocity, double ignored, double acc)
827{
828    return pow(velocity, (acc - 1.0) * 0.5);
829}
830
831/**
832 * returns acceleration for velocity.
833 * This profile selects the two functions like the old scheme did
834 */
835static double
836ClassicProfile(DeviceIntPtr dev,
837               DeviceVelocityPtr vel,
838               double velocity, double threshold, double acc)
839{
840    if (threshold > 0) {
841        return SimpleSmoothProfile(dev, vel, velocity, threshold, acc);
842    }
843    else {
844        return PolynomialAccelerationProfile(dev, vel, velocity, 0, acc);
845    }
846}
847
848/**
849 * Power profile
850 * This has a completely smooth transition curve, i.e. no jumps in the
851 * derivatives.
852 *
853 * This has the expense of overall response dependency on min-acceleration.
854 * In effect, min_acceleration mimics const_acceleration in this profile.
855 */
856static double
857PowerProfile(DeviceIntPtr dev,
858             DeviceVelocityPtr vel,
859             double velocity, double threshold, double acc)
860{
861    double vel_dist;
862
863    acc = (acc - 1.0) * 0.1f + 1.0;     /* without this, acc of 2 is unuseable */
864
865    if (velocity <= threshold)
866        return vel->min_acceleration;
867    vel_dist = velocity - threshold;
868    return (pow(acc, vel_dist)) * vel->min_acceleration;
869}
870
871/**
872 * just a smooth function in [0..1] -> [0..1]
873 *  - point symmetry at 0.5
874 *  - f'(0) = f'(1) = 0
875 *  - starts faster than a sinoid
876 *  - smoothness C1 (Cinf if you dare to ignore endpoints)
877 */
878static inline double
879CalcPenumbralGradient(double x)
880{
881    x *= 2.0f;
882    x -= 1.0f;
883    return 0.5f + (x * sqrt(1.0 - x * x) + asin(x)) / M_PI;
884}
885
886/**
887 * acceleration function similar to classic accelerated/unaccelerated,
888 * but with smooth transition in between (and towards zero for adaptive dec.).
889 */
890static double
891SimpleSmoothProfile(DeviceIntPtr dev,
892                    DeviceVelocityPtr vel,
893                    double velocity, double threshold, double acc)
894{
895    if (velocity < 1.0f)
896        return CalcPenumbralGradient(0.5 + velocity * 0.5) * 2.0f - 1.0f;
897    if (threshold < 1.0f)
898        threshold = 1.0f;
899    if (velocity <= threshold)
900        return 1;
901    velocity /= threshold;
902    if (velocity >= acc)
903        return acc;
904    else
905        return 1.0f + (CalcPenumbralGradient(velocity / acc) * (acc - 1.0f));
906}
907
908/**
909 * This profile uses the first half of the penumbral gradient as a start
910 * and then scales linearly.
911 */
912static double
913SmoothLinearProfile(DeviceIntPtr dev,
914                    DeviceVelocityPtr vel,
915                    double velocity, double threshold, double acc)
916{
917    double res, nv;
918
919    if (acc > 1.0f)
920        acc -= 1.0f;            /*this is so acc = 1 is no acceleration */
921    else
922        return 1.0f;
923
924    nv = (velocity - threshold) * acc * 0.5f;
925
926    if (nv < 0) {
927        res = 0;
928    }
929    else if (nv < 2) {
930        res = CalcPenumbralGradient(nv * 0.25f) * 2.0f;
931    }
932    else {
933        nv -= 2.0f;
934        res = nv * 2.0f / M_PI  /* steepness of gradient at 0.5 */
935            + 1.0f;             /* gradient crosses 2|1 */
936    }
937    res += vel->min_acceleration;
938    return res;
939}
940
941/**
942 * From 0 to threshold, the response graduates smoothly from min_accel to
943 * acceleration. Beyond threshold it is exactly the specified acceleration.
944 */
945static double
946SmoothLimitedProfile(DeviceIntPtr dev,
947                     DeviceVelocityPtr vel,
948                     double velocity, double threshold, double acc)
949{
950    double res;
951
952    if (velocity >= threshold || threshold == 0.0f)
953        return acc;
954
955    velocity /= threshold;      /* should be [0..1[ now */
956
957    res = CalcPenumbralGradient(velocity) * (acc - vel->min_acceleration);
958
959    return vel->min_acceleration + res;
960}
961
962static double
963LinearProfile(DeviceIntPtr dev,
964              DeviceVelocityPtr vel,
965              double velocity, double threshold, double acc)
966{
967    return acc * velocity;
968}
969
970static double
971NoProfile(DeviceIntPtr dev,
972          DeviceVelocityPtr vel, double velocity, double threshold, double acc)
973{
974    return 1.0f;
975}
976
977static PointerAccelerationProfileFunc
978GetAccelerationProfile(DeviceVelocityPtr vel, int profile_num)
979{
980    switch (profile_num) {
981    case AccelProfileClassic:
982        return ClassicProfile;
983    case AccelProfileDeviceSpecific:
984        return vel->deviceSpecificProfile;
985    case AccelProfilePolynomial:
986        return PolynomialAccelerationProfile;
987    case AccelProfileSmoothLinear:
988        return SmoothLinearProfile;
989    case AccelProfileSimple:
990        return SimpleSmoothProfile;
991    case AccelProfilePower:
992        return PowerProfile;
993    case AccelProfileLinear:
994        return LinearProfile;
995    case AccelProfileSmoothLimited:
996        return SmoothLimitedProfile;
997    case AccelProfileNone:
998        return NoProfile;
999    default:
1000        return NULL;
1001    }
1002}
1003
1004/**
1005 * Set the profile by number.
1006 * Intended to make profiles exchangeable at runtime.
1007 * If you created a profile, give it a number here and in the header to
1008 * make it selectable. In case some profile-specific init is needed, here
1009 * would be a good place, since FreeVelocityData() also calls this with
1010 * PROFILE_UNINITIALIZE.
1011 *
1012 * returns FALSE if profile number is unavailable, TRUE otherwise.
1013 */
1014int
1015SetAccelerationProfile(DeviceVelocityPtr vel, int profile_num)
1016{
1017    PointerAccelerationProfileFunc profile;
1018
1019    profile = GetAccelerationProfile(vel, profile_num);
1020
1021    if (profile == NULL && profile_num != PROFILE_UNINITIALIZE)
1022        return FALSE;
1023
1024    /* Here one could free old profile-private data */
1025    free(vel->profile_private);
1026    vel->profile_private = NULL;
1027    /* Here one could init profile-private data */
1028    vel->Profile = profile;
1029    vel->statistics.profile_number = profile_num;
1030    return TRUE;
1031}
1032
1033/**********************************************
1034 * driver interaction
1035 **********************************************/
1036
1037/**
1038 * device-specific profile
1039 *
1040 * The device-specific profile is intended as a hook for a driver
1041 * which may want to provide an own acceleration profile.
1042 * It should not rely on profile-private data, instead
1043 * it should do init/uninit in the driver (ie. with DEVICE_INIT and friends).
1044 * Users may override or choose it.
1045 */
1046void
1047SetDeviceSpecificAccelerationProfile(DeviceVelocityPtr vel,
1048                                     PointerAccelerationProfileFunc profile)
1049{
1050    if (vel)
1051        vel->deviceSpecificProfile = profile;
1052}
1053
1054/**
1055 * Use this function to obtain a DeviceVelocityPtr for a device. Will return NULL if
1056 * the predictable acceleration scheme is not in effect.
1057 */
1058DeviceVelocityPtr
1059GetDevicePredictableAccelData(DeviceIntPtr dev)
1060{
1061    BUG_RETURN_VAL(!dev, NULL);
1062
1063    if (dev->valuator &&
1064        dev->valuator->accelScheme.AccelSchemeProc ==
1065        acceleratePointerPredictable &&
1066        dev->valuator->accelScheme.accelData != NULL) {
1067
1068        return ((PredictableAccelSchemePtr)
1069                dev->valuator->accelScheme.accelData)->vel;
1070    }
1071    return NULL;
1072}
1073
1074/********************************
1075 *  acceleration schemes
1076 *******************************/
1077
1078/**
1079 * Modifies valuators in-place.
1080 * This version employs a velocity approximation algorithm to
1081 * enable fine-grained predictable acceleration profiles.
1082 */
1083void
1084acceleratePointerPredictable(DeviceIntPtr dev, ValuatorMask *val, CARD32 evtime)
1085{
1086    double dx = 0, dy = 0;
1087    DeviceVelocityPtr velocitydata = GetDevicePredictableAccelData(dev);
1088    Bool soften = TRUE;
1089
1090    if (valuator_mask_num_valuators(val) == 0 || !velocitydata)
1091        return;
1092
1093    if (velocitydata->statistics.profile_number == AccelProfileNone &&
1094        velocitydata->const_acceleration == 1.0f) {
1095        return;                 /*we're inactive anyway, so skip the whole thing. */
1096    }
1097
1098    if (valuator_mask_isset(val, 0)) {
1099        dx = valuator_mask_get_double(val, 0);
1100    }
1101
1102    if (valuator_mask_isset(val, 1)) {
1103        dy = valuator_mask_get_double(val, 1);
1104    }
1105
1106    if (dx != 0.0 || dy != 0.0) {
1107        /* reset non-visible state? */
1108        if (ProcessVelocityData2D(velocitydata, dx, dy, evtime)) {
1109            soften = FALSE;
1110        }
1111
1112        if (dev->ptrfeed && dev->ptrfeed->ctrl.num) {
1113            double mult;
1114
1115            /* invoke acceleration profile to determine acceleration */
1116            mult = ComputeAcceleration(dev, velocitydata,
1117                                       dev->ptrfeed->ctrl.threshold,
1118                                       (double) dev->ptrfeed->ctrl.num /
1119                                       (double) dev->ptrfeed->ctrl.den);
1120
1121            DebugAccelF("mult is %f\n", mult);
1122            if (mult != 1.0f || velocitydata->const_acceleration != 1.0f) {
1123                if (mult > 1.0f && soften)
1124                    ApplySoftening(velocitydata, &dx, &dy);
1125                ApplyConstantDeceleration(velocitydata, &dx, &dy);
1126
1127                if (dx != 0.0)
1128                    valuator_mask_set_double(val, 0, mult * dx);
1129                if (dy != 0.0)
1130                    valuator_mask_set_double(val, 1, mult * dy);
1131                DebugAccelF("delta x:%.3f y:%.3f\n", mult * dx, mult * dy);
1132            }
1133        }
1134    }
1135    /* remember last motion delta (for softening/slow movement treatment) */
1136    velocitydata->last_dx = dx;
1137    velocitydata->last_dy = dy;
1138}
1139
1140/**
1141 * Originally a part of xf86PostMotionEvent; modifies valuators
1142 * in-place. Retained mostly for embedded scenarios.
1143 */
1144void
1145acceleratePointerLightweight(DeviceIntPtr dev,
1146                             ValuatorMask *val, CARD32 ignored)
1147{
1148    double mult = 0.0, tmpf;
1149    double dx = 0.0, dy = 0.0;
1150
1151    if (valuator_mask_isset(val, 0)) {
1152        dx = valuator_mask_get(val, 0);
1153    }
1154
1155    if (valuator_mask_isset(val, 1)) {
1156        dy = valuator_mask_get(val, 1);
1157    }
1158
1159    if (valuator_mask_num_valuators(val) == 0)
1160        return;
1161
1162    if (dev->ptrfeed && dev->ptrfeed->ctrl.num) {
1163        /* modeled from xf86Events.c */
1164        if (dev->ptrfeed->ctrl.threshold) {
1165            if ((fabs(dx) + fabs(dy)) >= dev->ptrfeed->ctrl.threshold) {
1166                if (dx != 0.0) {
1167                    tmpf = (dx * (double) (dev->ptrfeed->ctrl.num)) /
1168                        (double) (dev->ptrfeed->ctrl.den);
1169                    valuator_mask_set_double(val, 0, tmpf);
1170                }
1171
1172                if (dy != 0.0) {
1173                    tmpf = (dy * (double) (dev->ptrfeed->ctrl.num)) /
1174                        (double) (dev->ptrfeed->ctrl.den);
1175                    valuator_mask_set_double(val, 1, tmpf);
1176                }
1177            }
1178        }
1179        else {
1180            mult = pow(dx * dx + dy * dy,
1181                       ((double) (dev->ptrfeed->ctrl.num) /
1182                        (double) (dev->ptrfeed->ctrl.den) - 1.0) / 2.0) / 2.0;
1183            if (dx != 0.0)
1184                valuator_mask_set_double(val, 0, mult * dx);
1185            if (dy != 0.0)
1186                valuator_mask_set_double(val, 1, mult * dy);
1187        }
1188    }
1189}
1190