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