Improve VelocityTracker numerical stability.

Replaced VelocityTracker with a faster and more accurate
native implementation.  This avoids the duplicate maintenance
overhead of having two implementations.

The new algorithm requires that the sample duration be at least
10ms in order to contribute to the velocity calculation.  This
ensures that the velocity is not severely overestimated when
samples arrive in bursts.

The new algorithm computes the exponentially weighted moving
average using weights based on the relative duration of successive
sample periods.

The new algorithm is also more careful about how it handles
individual pointers going down or up and their effects on the
collected movement traces.  The intent is to preserve the last
known velocity of pointers as they go up while also ensuring
that other motion samples do not count twice in that case.

Bug: 4086785
Change-Id: I2632321232c64d6b8faacdb929e33f60e64dcdd3

2 files changed, 30 insertions, 3 deletions

diff --git a/include/ui/Input.h b/include/ui/Input.h
index e9cacf4..8e8b61b 100644
--- a/include/ui/Input.h
+++ b/include/ui/Input.h
@@ -311,6 +311,13 @@ public:
 
     inline int32_t getAction() const { return mAction; }
 
+    inline int32_t getActionMasked() const { return mAction & AMOTION_EVENT_ACTION_MASK; }
+
+    inline int32_t getActionIndex() const {
+        return (mAction & AMOTION_EVENT_ACTION_POINTER_INDEX_MASK)
+                >> AMOTION_EVENT_ACTION_POINTER_INDEX_SHIFT;
+    }
+
     inline void setAction(int32_t action) { mAction = action; }
 
     inline int32_t getFlags() const { return mFlags; }
@@ -458,6 +465,8 @@ public:
                 AMOTION_EVENT_AXIS_ORIENTATION, pointerIndex, historicalIndex);
     }
 
+    ssize_t findPointerIndex(int32_t pointerId) const;
+
     void initialize(
             int32_t deviceId,
             int32_t source,
@@ -551,8 +560,7 @@ private:
 };
 
 /*
- * Calculates the velocity of pointer motions over time.
- * Uses essentially the same algorithm as android.view.VelocityTracker.
+ * Calculates the velocity of pointer movements over time.
  */
 class VelocityTracker {
 public:
@@ -565,6 +573,11 @@ public:
     // Resets the velocity tracker state.
     void clear();
 
+    // Resets the velocity tracker state for specific pointers.
+    // Call this method when some pointers have changed and may be reusing
+    // an id that was assigned to a different pointer earlier.
+    void clearPointers(BitSet32 idBits);
+
     // Adds movement information for a set of pointers.
     // The idBits bitfield specifies the pointer ids of the pointers whose positions
     // are included in the movement.
@@ -572,11 +585,20 @@ public:
     // increasing id.  Its size should be equal to the number of one bits in idBits.
     void addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions);
 
+    // Adds movement information for all pointers in a MotionEvent, including historical samples.
+    void addMovement(const MotionEvent* event);
+
     // Gets the velocity of the specified pointer id in position units per second.
     // Returns false and sets the velocity components to zero if there is no movement
     // information for the pointer.
     bool getVelocity(uint32_t id, float* outVx, float* outVy) const;
 
+    // Gets the active pointer id, or -1 if none.
+    inline int32_t getActivePointerId() const { return mActivePointerId; }
+
+    // Gets a bitset containing all pointer ids from the most recent movement.
+    inline BitSet32 getCurrentPointerIdBits() const { return mMovements[mIndex].idBits; }
+
 private:
     // Number of samples to keep.
     static const uint32_t HISTORY_SIZE = 10;
@@ -585,7 +607,7 @@ private:
     static const nsecs_t MAX_AGE = 200 * 1000000; // 200 ms
 
     // The minimum duration between samples when estimating velocity.
-    static const nsecs_t MIN_DURATION = 5 * 1000000; // 5 ms
+    static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
 
     struct Movement {
         nsecs_t eventTime;
@@ -595,6 +617,7 @@ private:
 
     uint32_t mIndex;
     Movement mMovements[HISTORY_SIZE];
+    int32_t mActivePointerId;
 };
 
 /*
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h
index f03825a..de748b5 100644
--- a/include/utils/BitSet.h
+++ b/include/utils/BitSet.h
@@ -61,6 +61,10 @@ struct BitSet32 {
     // Result is undefined if all bits are marked.
     inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); }
 
+    // Finds the last marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); }
+
     // Gets the index of the specified bit in the set, which is the number of
     // marked bits that appear before the specified bit.
     inline uint32_t getIndexOfBit(uint32_t n) const {