dix/ptrveloc.c

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