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

7 files changed, 267 insertions, 319 deletions

diff --git a/core/java/android/view/VelocityTracker.java b/core/java/android/view/VelocityTracker.java
index 4ab2881..fccef2b 100644
--- a/core/java/android/view/VelocityTracker.java
+++ b/core/java/android/view/VelocityTracker.java
@@ -16,8 +16,6 @@
 
 package android.view;
 
-import android.util.Config;
-import android.util.Log;
 import android.util.Poolable;
 import android.util.Pool;
 import android.util.Pools;
@@ -25,24 +23,15 @@ import android.util.PoolableManager;
 
 /**
  * Helper for tracking the velocity of touch events, for implementing
- * flinging and other such gestures.  Use {@link #obtain} to retrieve a
- * new instance of the class when you are going to begin tracking, put
- * the motion events you receive into it with {@link #addMovement(MotionEvent)},
- * and when you want to determine the velocity call
- * {@link #computeCurrentVelocity(int)} and then {@link #getXVelocity()}
- * and {@link #getXVelocity()}.
+ * flinging and other such gestures.
+ *
+ * Use {@link #obtain} to retrieve a new instance of the class when you are going
+ * to begin tracking.  Put the motion events you receive into it with
+ * {@link #addMovement(MotionEvent)}.  When you want to determine the velocity call
+ * {@link #computeCurrentVelocity(int)} and then call {@link #getXVelocity(int)}
+ * and {@link #getXVelocity(int)} to retrieve the velocity for each pointer id.
  */
 public final class VelocityTracker implements Poolable<VelocityTracker> {
-    private static final String TAG = "VelocityTracker";
-    private static final boolean DEBUG = false;
-    private static final boolean localLOGV = DEBUG || Config.LOGV;
-
-    private static final int NUM_PAST = 10;
-    private static final int MAX_AGE_MILLISECONDS = 200;
-    
-    private static final int POINTER_POOL_CAPACITY = 20;
-    private static final int INVALID_POINTER = -1;
-
     private static final Pool<VelocityTracker> sPool = Pools.synchronizedPool(
             Pools.finitePool(new PoolableManager<VelocityTracker>() {
                 public VelocityTracker newInstance() {
@@ -56,31 +45,20 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
                     element.clear();
                 }
             }, 2));
-    
-    private static Pointer sRecycledPointerListHead;
-    private static int sRecycledPointerCount;
-    
-    private static final class Pointer {
-        public Pointer next;
-        
-        public int id;
-        public float xVelocity;
-        public float yVelocity;
-        
-        public final float[] pastX = new float[NUM_PAST];
-        public final float[] pastY = new float[NUM_PAST];
-        public final long[] pastTime = new long[NUM_PAST]; // uses Long.MIN_VALUE as a sentinel
-        
-        public int generation;
-    }
-    
-    private Pointer mPointerListHead; // sorted by id in increasing order
-    private int mLastTouchIndex;
-    private int mGeneration;
-    private int mActivePointerId;
 
+    private static final int ACTIVE_POINTER_ID = -1;
+
+    private int mPtr;
     private VelocityTracker mNext;
 
+    private static native int nativeInitialize();
+    private static native void nativeDispose(int ptr);
+    private static native void nativeClear(int ptr);
+    private static native void nativeAddMovement(int ptr, MotionEvent event);
+    private static native void nativeComputeCurrentVelocity(int ptr, int units, float maxVelocity);
+    private static native float nativeGetXVelocity(int ptr, int id);
+    private static native float nativeGetYVelocity(int ptr, int id);
+
     /**
      * Retrieve a new VelocityTracker object to watch the velocity of a
      * motion.  Be sure to call {@link #recycle} when done.  You should
@@ -116,18 +94,26 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     }
 
     private VelocityTracker() {
-        clear();
+        mPtr = nativeInitialize();
     }
-    
+
+    @Override
+    protected void finalize() throws Throwable {
+        try {
+            if (mPtr != 0) {
+                nativeDispose(mPtr);
+                mPtr = 0;
+            }
+        } finally {
+            super.finalize();
+        }
+    }
+
     /**
      * Reset the velocity tracker back to its initial state.
      */
     public void clear() {
-        releasePointerList(mPointerListHead);
-        
-        mPointerListHead = null;
-        mLastTouchIndex = 0;
-        mActivePointerId = INVALID_POINTER;
+        nativeClear(mPtr);
     }
     
     /**
@@ -137,110 +123,13 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * final {@link MotionEvent#ACTION_UP}.  You can, however, call this
      * for whichever events you desire.
      * 
-     * @param ev The MotionEvent you received and would like to track.
+     * @param event The MotionEvent you received and would like to track.
      */
-    public void addMovement(MotionEvent ev) {
-        final int historySize = ev.getHistorySize();
-        final int pointerCount = ev.getPointerCount();
-        final int lastTouchIndex = mLastTouchIndex;
-        final int nextTouchIndex = (lastTouchIndex + 1) % NUM_PAST;
-        final int finalTouchIndex = (nextTouchIndex + historySize) % NUM_PAST;
-        final int generation = mGeneration++;
-        
-        mLastTouchIndex = finalTouchIndex;
-
-        // Update pointer data.
-        Pointer previousPointer = null;
-        for (int i = 0; i < pointerCount; i++){
-            final int pointerId = ev.getPointerId(i);
-            
-            // Find the pointer data for this pointer id.
-            // This loop is optimized for the common case where pointer ids in the event
-            // are in sorted order.  However, we check for this case explicitly and
-            // perform a full linear scan from the start if needed.
-            Pointer nextPointer;
-            if (previousPointer == null || pointerId < previousPointer.id) {
-                previousPointer = null;
-                nextPointer = mPointerListHead;
-            } else {
-                nextPointer = previousPointer.next;
-            }
-            
-            final Pointer pointer;
-            for (;;) {
-                if (nextPointer != null) {
-                    final int nextPointerId = nextPointer.id;
-                    if (nextPointerId == pointerId) {
-                        pointer = nextPointer;
-                        break;
-                    }
-                    if (nextPointerId < pointerId) {
-                        nextPointer = nextPointer.next;
-                        continue;
-                    }
-                }
-                
-                // Pointer went down.  Add it to the list.
-                // Write a sentinel at the end of the pastTime trace so we will be able to
-                // tell when the trace started.
-                if (mActivePointerId == INVALID_POINTER) {
-                    // Congratulations! You're the new active pointer!
-                    mActivePointerId = pointerId;
-                }
-                pointer = obtainPointer();
-                pointer.id = pointerId;
-                pointer.pastTime[lastTouchIndex] = Long.MIN_VALUE;
-                pointer.next = nextPointer;
-                if (previousPointer == null) {
-                    mPointerListHead = pointer;
-                } else {
-                    previousPointer.next = pointer;
-                }
-                break;
-            }
-            
-            pointer.generation = generation;
-            previousPointer = pointer;
-            
-            final float[] pastX = pointer.pastX;
-            final float[] pastY = pointer.pastY;
-            final long[] pastTime = pointer.pastTime;
-            
-            for (int j = 0; j < historySize; j++) {
-                final int touchIndex = (nextTouchIndex + j) % NUM_PAST;
-                pastX[touchIndex] = ev.getHistoricalX(i, j);
-                pastY[touchIndex] = ev.getHistoricalY(i, j);
-                pastTime[touchIndex] = ev.getHistoricalEventTime(j);
-            }
-            pastX[finalTouchIndex] = ev.getX(i);
-            pastY[finalTouchIndex] = ev.getY(i);
-            pastTime[finalTouchIndex] = ev.getEventTime();
-        }
-        
-        // Find removed pointers.
-        previousPointer = null;
-        for (Pointer pointer = mPointerListHead; pointer != null; ) {
-            final Pointer nextPointer = pointer.next;
-            final int pointerId = pointer.id;
-            if (pointer.generation != generation) {
-                // Pointer went up.  Remove it from the list.
-                if (previousPointer == null) {
-                    mPointerListHead = nextPointer;
-                } else {
-                    previousPointer.next = nextPointer;
-                }
-                releasePointer(pointer);
-
-                if (pointerId == mActivePointerId) {
-                    // Pick a new active pointer. How is arbitrary.
-                    mActivePointerId = mPointerListHead != null ?
-                            mPointerListHead.id : INVALID_POINTER;
-                }
-            } else {
-                previousPointer = pointer;
-            }
-            pointer = nextPointer;
+    public void addMovement(MotionEvent event) {
+        if (event == null) {
+            throw new IllegalArgumentException("event must not be null");
         }
+        nativeAddMovement(mPtr, event);
     }
 
     /**
@@ -250,7 +139,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @see #computeCurrentVelocity(int, float) 
      */
     public void computeCurrentVelocity(int units) {
-        computeCurrentVelocity(units, Float.MAX_VALUE);
+        nativeComputeCurrentVelocity(mPtr, units, Float.MAX_VALUE);
     }
 
     /**
@@ -267,78 +156,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * must be positive.
      */
     public void computeCurrentVelocity(int units, float maxVelocity) {
-        final int lastTouchIndex = mLastTouchIndex;
-        
-        for (Pointer pointer = mPointerListHead; pointer != null; pointer = pointer.next) {
-            final long[] pastTime = pointer.pastTime;
-            
-            // Search backwards in time for oldest acceptable time.
-            // Stop at the beginning of the trace as indicated by the sentinel time Long.MIN_VALUE.
-            int oldestTouchIndex = lastTouchIndex;
-            int numTouches = 1;
-            final long minTime = pastTime[lastTouchIndex] - MAX_AGE_MILLISECONDS;
-            while (numTouches < NUM_PAST) {
-                final int nextOldestTouchIndex = (oldestTouchIndex + NUM_PAST - 1) % NUM_PAST;
-                final long nextOldestTime = pastTime[nextOldestTouchIndex];
-                if (nextOldestTime < minTime) { // also handles end of trace sentinel
-                    break;
-                }
-                oldestTouchIndex = nextOldestTouchIndex;
-                numTouches += 1;
-            }
-            
-            // If we have a lot of samples, skip the last received sample since it is
-            // probably pretty noisy compared to the sum of all of the traces already acquired.
-            if (numTouches > 3) {
-                numTouches -= 1;
-            }
-            
-            // Kind-of stupid.
-            final float[] pastX = pointer.pastX;
-            final float[] pastY = pointer.pastY;
-            
-            final float oldestX = pastX[oldestTouchIndex];
-            final float oldestY = pastY[oldestTouchIndex];
-            final long oldestTime = pastTime[oldestTouchIndex];
-            
-            float accumX = 0;
-            float accumY = 0;
-            
-            for (int i = 1; i < numTouches; i++) {
-                final int touchIndex = (oldestTouchIndex + i) % NUM_PAST;
-                final int duration = (int)(pastTime[touchIndex] - oldestTime);
-                
-                if (duration == 0) continue;
-                
-                float delta = pastX[touchIndex] - oldestX;
-                float velocity = (delta / duration) * units; // pixels/frame.
-                accumX = (accumX == 0) ? velocity : (accumX + velocity) * .5f;
-            
-                delta = pastY[touchIndex] - oldestY;
-                velocity = (delta / duration) * units; // pixels/frame.
-                accumY = (accumY == 0) ? velocity : (accumY + velocity) * .5f;
-            }
-            
-            if (accumX < -maxVelocity) {
-                accumX = - maxVelocity;
-            } else if (accumX > maxVelocity) {
-                accumX = maxVelocity;
-            }
-            
-            if (accumY < -maxVelocity) {
-                accumY = - maxVelocity;
-            } else if (accumY > maxVelocity) {
-                accumY = maxVelocity;
-            }
-            
-            pointer.xVelocity = accumX;
-            pointer.yVelocity = accumY;
-            
-            if (localLOGV) {
-                Log.v(TAG, "Pointer " + pointer.id
-                    + ": Y velocity=" + accumX +" X velocity=" + accumY + " N=" + numTouches);
-            }
-        }
+        nativeComputeCurrentVelocity(mPtr, units, maxVelocity);
     }
     
     /**
@@ -348,8 +166,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed X velocity.
      */
     public float getXVelocity() {
-        Pointer pointer = getPointer(mActivePointerId);
-        return pointer != null ? pointer.xVelocity : 0;
+        return nativeGetXVelocity(mPtr, ACTIVE_POINTER_ID);
     }
     
     /**
@@ -359,8 +176,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed Y velocity.
      */
     public float getYVelocity() {
-        Pointer pointer = getPointer(mActivePointerId);
-        return pointer != null ? pointer.yVelocity : 0;
+        return nativeGetYVelocity(mPtr, ACTIVE_POINTER_ID);
     }
     
     /**
@@ -371,8 +187,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed X velocity.
      */
     public float getXVelocity(int id) {
-        Pointer pointer = getPointer(id);
-        return pointer != null ? pointer.xVelocity : 0;
+        return nativeGetXVelocity(mPtr, id);
     }
     
     /**
@@ -383,68 +198,6 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed Y velocity.
      */
     public float getYVelocity(int id) {
-        Pointer pointer = getPointer(id);
-        return pointer != null ? pointer.yVelocity : 0;
-    }
-    
-    private Pointer getPointer(int id) {
-        for (Pointer pointer = mPointerListHead; pointer != null; pointer = pointer.next) {
-            if (pointer.id == id) {
-                return pointer;
-            }
-        }
-        return null;
-    }
-    
-    private static Pointer obtainPointer() {
-        synchronized (sPool) {
-            if (sRecycledPointerCount != 0) {
-                Pointer element = sRecycledPointerListHead;
-                sRecycledPointerCount -= 1;
-                sRecycledPointerListHead = element.next;
-                element.next = null;
-                return element;
-            }
-        }
-        return new Pointer();
-    }
-    
-    private static void releasePointer(Pointer pointer) {
-        synchronized (sPool) {
-            if (sRecycledPointerCount < POINTER_POOL_CAPACITY) {
-                pointer.next = sRecycledPointerListHead;
-                sRecycledPointerCount += 1;
-                sRecycledPointerListHead = pointer;
-            }
-        }
-    }
-    
-    private static void releasePointerList(Pointer pointer) {
-        if (pointer != null) {
-            synchronized (sPool) {
-                int count = sRecycledPointerCount;
-                if (count >= POINTER_POOL_CAPACITY) {
-                    return;
-                }
-                
-                Pointer tail = pointer;
-                for (;;) {
-                    count += 1;
-                    if (count >= POINTER_POOL_CAPACITY) {
-                        break;
-                    }
-                    
-                    Pointer next = tail.next;
-                    if (next == null) {
-                        break;
-                    }
-                    tail = next;
-                }
-
-                tail.next = sRecycledPointerListHead;
-                sRecycledPointerCount = count;
-                sRecycledPointerListHead = pointer;
-            }
-        }
+        return nativeGetYVelocity(mPtr, id);
     }
 }
diff --git a/core/jni/Android.mk b/core/jni/Android.mk
index 52fc930..b4a0e4f 100644
--- a/core/jni/Android.mk
+++ b/core/jni/Android.mk
@@ -54,6 +54,7 @@ LOCAL_SRC_FILES:= \
 	android_view_KeyCharacterMap.cpp \
 	android_view_GLES20Canvas.cpp \
 	android_view_MotionEvent.cpp \
+	android_view_VelocityTracker.cpp \
 	android_text_AndroidCharacter.cpp \
 	android_text_AndroidBidi.cpp \
 	android_os_Debug.cpp \
diff --git a/core/jni/AndroidRuntime.cpp b/core/jni/AndroidRuntime.cpp
index 0e071a4..e4eb692 100644
--- a/core/jni/AndroidRuntime.cpp
+++ b/core/jni/AndroidRuntime.cpp
@@ -170,6 +170,7 @@ extern int register_android_view_InputChannel(JNIEnv* env);
 extern int register_android_view_InputQueue(JNIEnv* env);
 extern int register_android_view_KeyEvent(JNIEnv* env);
 extern int register_android_view_MotionEvent(JNIEnv* env);
+extern int register_android_view_VelocityTracker(JNIEnv* env);
 extern int register_android_content_res_ObbScanner(JNIEnv* env);
 extern int register_android_content_res_Configuration(JNIEnv* env);
 extern int register_android_animation_PropertyValuesHolder(JNIEnv *env);
@@ -1302,6 +1303,7 @@ static const RegJNIRec gRegJNI[] = {
     REG_JNI(register_android_view_InputQueue),
     REG_JNI(register_android_view_KeyEvent),
     REG_JNI(register_android_view_MotionEvent),
+    REG_JNI(register_android_view_VelocityTracker),
 
     REG_JNI(register_android_content_res_ObbScanner),
     REG_JNI(register_android_content_res_Configuration),
diff --git a/core/jni/android_view_InputQueue.cpp b/core/jni/android_view_InputQueue.cpp
index b5a5d2e..80c4871 100644
--- a/core/jni/android_view_InputQueue.cpp
+++ b/core/jni/android_view_InputQueue.cpp
@@ -380,7 +380,7 @@ int NativeInputQueue::handleReceiveCallback(int receiveFd, int events, void* dat
 #if DEBUG_DISPATCH_CYCLE
         LOGD("channel '%s' ~ Received motion event.", connection->getInputChannelName());
 #endif
-        inputEventObj = android_view_MotionEvent_fromNative(env,
+        inputEventObj = android_view_MotionEvent_obtainAsCopy(env,
                 static_cast<MotionEvent*>(inputEvent));
         dispatchMethodId = gInputQueueClassInfo.dispatchMotionEvent;
         break;
diff --git a/core/jni/android_view_MotionEvent.cpp b/core/jni/android_view_MotionEvent.cpp
index 68ebfe7..4ce471e 100644
--- a/core/jni/android_view_MotionEvent.cpp
+++ b/core/jni/android_view_MotionEvent.cpp
@@ -57,7 +57,10 @@ static struct {
 
 // ----------------------------------------------------------------------------
 
-static MotionEvent* android_view_MotionEvent_getNativePtr(JNIEnv* env, jobject eventObj) {
+MotionEvent* android_view_MotionEvent_getNativePtr(JNIEnv* env, jobject eventObj) {
+    if (!eventObj) {
+        return NULL;
+    }
     return reinterpret_cast<MotionEvent*>(
             env->GetIntField(eventObj, gMotionEventClassInfo.mNativePtr));
 }
@@ -68,10 +71,10 @@ static void android_view_MotionEvent_setNativePtr(JNIEnv* env, jobject eventObj,
             reinterpret_cast<int>(event));
 }
 
-jobject android_view_MotionEvent_fromNative(JNIEnv* env, const MotionEvent* event) {
+jobject android_view_MotionEvent_obtainAsCopy(JNIEnv* env, const MotionEvent* event) {
     jobject eventObj = env->CallStaticObjectMethod(gMotionEventClassInfo.clazz,
             gMotionEventClassInfo.obtain);
-    if (env->ExceptionCheck()) {
+    if (env->ExceptionCheck() || !eventObj) {
         LOGE("An exception occurred while obtaining a motion event.");
         LOGE_EX(env);
         env->ExceptionClear();
@@ -88,18 +91,6 @@ jobject android_view_MotionEvent_fromNative(JNIEnv* env, const MotionEvent* even
     return eventObj;
 }
 
-status_t android_view_MotionEvent_toNative(JNIEnv* env, jobject eventObj,
-        MotionEvent* event) {
-    MotionEvent* srcEvent = android_view_MotionEvent_getNativePtr(env, eventObj);
-    if (!srcEvent) {
-        LOGE("MotionEvent was finalized");
-        return BAD_VALUE;
-    }
-
-    event->copyFrom(srcEvent, true);
-    return OK;
-}
-
 status_t android_view_MotionEvent_recycle(JNIEnv* env, jobject eventObj) {
     env->CallVoidMethod(eventObj, gMotionEventClassInfo.recycle);
     if (env->ExceptionCheck()) {
@@ -500,13 +491,7 @@ static jint android_view_MotionEvent_nativeGetPointerId(JNIEnv* env, jclass claz
 static jint android_view_MotionEvent_nativeFindPointerIndex(JNIEnv* env, jclass clazz,
         jint nativePtr, jint pointerId) {
     MotionEvent* event = reinterpret_cast<MotionEvent*>(nativePtr);
-    size_t pointerCount = event->getPointerCount();
-    for (size_t i = 0; i < pointerCount; i++) {
-        if (event->getPointerId(i) == pointerId) {
-            return i;
-        }
-    }
-    return -1;
+    return jint(event->findPointerIndex(pointerId));
 }
 
 static jint android_view_MotionEvent_nativeGetHistorySize(JNIEnv* env, jclass clazz,
diff --git a/core/jni/android_view_MotionEvent.h b/core/jni/android_view_MotionEvent.h
index 80dc861..0cf1fb2 100644
--- a/core/jni/android_view_MotionEvent.h
+++ b/core/jni/android_view_MotionEvent.h
@@ -26,12 +26,11 @@ class MotionEvent;
 
 /* Obtains an instance of a DVM MotionEvent object as a copy of a native MotionEvent instance.
  * Returns NULL on error. */
-extern jobject android_view_MotionEvent_fromNative(JNIEnv* env, const MotionEvent* event);
+extern jobject android_view_MotionEvent_obtainAsCopy(JNIEnv* env, const MotionEvent* event);
 
-/* Copies the contents of a DVM MotionEvent object to a native MotionEvent instance.
- * Returns non-zero on error. */
-extern status_t android_view_MotionEvent_toNative(JNIEnv* env, jobject eventObj,
-        MotionEvent* event);
+/* Gets the underlying native MotionEvent instance within a DVM MotionEvent object.
+ * Returns NULL if the event is NULL or if it is uninitialized. */
+extern MotionEvent* android_view_MotionEvent_getNativePtr(JNIEnv* env, jobject eventObj);
 
 /* Recycles a DVM MotionEvent object.
  * Returns non-zero on error. */
diff --git a/core/jni/android_view_VelocityTracker.cpp b/core/jni/android_view_VelocityTracker.cpp
new file mode 100644
index 0000000..daa0adc
--- /dev/null
+++ b/core/jni/android_view_VelocityTracker.cpp
@@ -0,0 +1,208 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "VelocityTracker-JNI"
+
+#include "JNIHelp.h"
+
+#include <android_runtime/AndroidRuntime.h>
+#include <utils/Log.h>
+#include <ui/Input.h>
+#include "android_view_MotionEvent.h"
+
+
+namespace android {
+
+// Special constant to request the velocity of the active pointer.
+static const int ACTIVE_POINTER_ID = -1;
+
+// --- VelocityTrackerState ---
+
+class VelocityTrackerState {
+public:
+    VelocityTrackerState();
+
+    void clear();
+    void addMovement(const MotionEvent* event);
+    void computeCurrentVelocity(int32_t units, float maxVelocity);
+    void getVelocity(int32_t id, float* outVx, float* outVy);
+
+private:
+    struct Velocity {
+        float vx, vy;
+    };
+
+    VelocityTracker mVelocityTracker;
+    int32_t mActivePointerId;
+    BitSet32 mCalculatedIdBits;
+    Velocity mCalculatedVelocity[MAX_POINTERS];
+};
+
+VelocityTrackerState::VelocityTrackerState() : mActivePointerId(-1) {
+}
+
+void VelocityTrackerState::clear() {
+    mVelocityTracker.clear();
+    mActivePointerId = -1;
+    mCalculatedIdBits.clear();
+}
+
+void VelocityTrackerState::addMovement(const MotionEvent* event) {
+    mVelocityTracker.addMovement(event);
+}
+
+void VelocityTrackerState::computeCurrentVelocity(int32_t units, float maxVelocity) {
+    BitSet32 idBits(mVelocityTracker.getCurrentPointerIdBits());
+    mCalculatedIdBits = idBits;
+
+    for (uint32_t index = 0; !idBits.isEmpty(); index++) {
+        uint32_t id = idBits.firstMarkedBit();
+        idBits.clearBit(id);
+
+        float vx, vy;
+        mVelocityTracker.getVelocity(id, &vx, &vy);
+
+        vx = vx * units / 1000;
+        vy = vy * units / 1000;
+
+        if (vx > maxVelocity) {
+            vx = maxVelocity;
+        } else if (vx < -maxVelocity) {
+            vx = -maxVelocity;
+        }
+        if (vy > maxVelocity) {
+            vy = maxVelocity;
+        } else if (vy < -maxVelocity) {
+            vy = -maxVelocity;
+        }
+
+        Velocity& velocity = mCalculatedVelocity[index];
+        velocity.vx = vx;
+        velocity.vy = vy;
+    }
+}
+
+void VelocityTrackerState::getVelocity(int32_t id, float* outVx, float* outVy) {
+    if (id == ACTIVE_POINTER_ID) {
+        id = mVelocityTracker.getActivePointerId();
+    }
+
+    float vx, vy;
+    if (id >= 0 && id <= MAX_POINTER_ID && mCalculatedIdBits.hasBit(id)) {
+        uint32_t index = mCalculatedIdBits.getIndexOfBit(id);
+        const Velocity& velocity = mCalculatedVelocity[index];
+        vx = velocity.vx;
+        vy = velocity.vy;
+    } else {
+        vx = 0;
+        vy = 0;
+    }
+
+    if (outVx) {
+        *outVx = vx;
+    }
+    if (outVy) {
+        *outVy = vy;
+    }
+}
+
+
+// --- JNI Methods ---
+
+static jint android_view_VelocityTracker_nativeInitialize(JNIEnv* env, jclass clazz) {
+    return reinterpret_cast<jint>(new VelocityTrackerState());
+}
+
+static void android_view_VelocityTracker_nativeDispose(JNIEnv* env, jclass clazz, jint ptr) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    delete state;
+}
+
+static void android_view_VelocityTracker_nativeClear(JNIEnv* env, jclass clazz, jint ptr) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    state->clear();
+}
+
+static void android_view_VelocityTracker_nativeAddMovement(JNIEnv* env, jclass clazz, jint ptr,
+        jobject eventObj) {
+    const MotionEvent* event = android_view_MotionEvent_getNativePtr(env, eventObj);
+    if (!event) {
+        LOGW("nativeAddMovement failed because MotionEvent was finalized.");
+        return;
+    }
+
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    state->addMovement(event);
+}
+
+static void android_view_VelocityTracker_nativeComputeCurrentVelocity(JNIEnv* env, jclass clazz,
+        jint ptr, jint units, jfloat maxVelocity) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    state->computeCurrentVelocity(units, maxVelocity);
+}
+
+static jfloat android_view_VelocityTracker_nativeGetXVelocity(JNIEnv* env, jclass clazz,
+        jint ptr, jint id) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    float vx;
+    state->getVelocity(id, &vx, NULL);
+    return vx;
+}
+
+static jfloat android_view_VelocityTracker_nativeGetYVelocity(JNIEnv* env, jclass clazz,
+        jint ptr, jint id) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    float vy;
+    state->getVelocity(id, NULL, &vy);
+    return vy;
+}
+
+
+// --- JNI Registration ---
+
+static JNINativeMethod gVelocityTrackerMethods[] = {
+    /* name, signature, funcPtr */
+    { "nativeInitialize",
+            "()I",
+            (void*)android_view_VelocityTracker_nativeInitialize },
+    { "nativeDispose",
+            "(I)V",
+            (void*)android_view_VelocityTracker_nativeDispose },
+    { "nativeClear",
+            "(I)V",
+            (void*)android_view_VelocityTracker_nativeClear },
+    { "nativeAddMovement",
+            "(ILandroid/view/MotionEvent;)V",
+            (void*)android_view_VelocityTracker_nativeAddMovement },
+    { "nativeComputeCurrentVelocity",
+            "(IIF)V",
+            (void*)android_view_VelocityTracker_nativeComputeCurrentVelocity },
+    { "nativeGetXVelocity",
+            "(II)F",
+            (void*)android_view_VelocityTracker_nativeGetXVelocity },
+    { "nativeGetYVelocity",
+            "(II)F",
+            (void*)android_view_VelocityTracker_nativeGetYVelocity },
+};
+
+int register_android_view_VelocityTracker(JNIEnv* env) {
+    int res = jniRegisterNativeMethods(env, "android/view/VelocityTracker",
+            gVelocityTrackerMethods, NELEM(gVelocityTrackerMethods));
+    LOG_FATAL_IF(res < 0, "Unable to register native methods.");
+    return 0;
+}
+
+} // namespace android