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