Improve VelocityTracker numerical stability. (DO NOT MERGE)

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: I95054102397c4b6a9076dc6a0fc841b4beec7920

6 files changed, 223 insertions, 28 deletions

diff --git a/core/jni/Android.mk b/core/jni/Android.mk
index 1c4dc29..7c064df 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 97cba23..0840cf8 100644
--- a/core/jni/android_view_MotionEvent.cpp
+++ b/core/jni/android_view_MotionEvent.cpp
@@ -59,7 +59,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));
 }
@@ -70,10 +73,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();
@@ -90,18 +93,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()) {
@@ -502,13 +493,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