Improve touch event resampling.

Fixed a few bugs related to the id-to-index mapping for
pointer coordinates.

Tightened the bounds on the resampling time interval to
avoid predicting too far into the future.

Only lerp X and Y components of motion events.

Alter the future to satisfy past predictions.  (Rewrite touch
events to conceal obvious discontinuities.)

Added a system property to control whether resampling is enabled
for debugging purposes.

Bug: 6375101
Change-Id: I35972d63278bc4e78148053a4125ad9abeebfedb

4 files changed, 176 insertions, 70 deletions

diff --git a/include/androidfw/Input.h b/include/androidfw/Input.h
index aa8b824..2c91fab 100644
--- a/include/androidfw/Input.h
+++ b/include/androidfw/Input.h
@@ -176,7 +176,6 @@ struct PointerCoords {
     status_t setAxisValue(int32_t axis, float value);
 
     void scale(float scale);
-    void lerp(const PointerCoords& a, const PointerCoords& b, float alpha);
 
     inline float getX() const {
         return getAxisValue(AMOTION_EVENT_AXIS_X);
diff --git a/include/androidfw/InputTransport.h b/include/androidfw/InputTransport.h
index 2924505..5706bce 100644
--- a/include/androidfw/InputTransport.h
+++ b/include/androidfw/InputTransport.h
@@ -92,6 +92,12 @@ struct InputMessage {
                 PointerCoords coords;
             } pointers[MAX_POINTERS];
 
+            int32_t getActionId() const {
+                uint32_t index = (action & AMOTION_EVENT_ACTION_POINTER_INDEX_MASK)
+                        >> AMOTION_EVENT_ACTION_POINTER_INDEX_SHIFT;
+                return pointers[index].properties.id;
+            }
+
             inline size_t size() const {
                 return sizeof(Motion) - sizeof(Pointer) * MAX_POINTERS
                         + sizeof(Pointer) * pointerCount;
@@ -322,6 +328,10 @@ public:
     bool hasPendingBatch() const;
 
 private:
+    // True if touch resampling is enabled.
+    const bool mResampleTouch;
+
+    // The input channel.
     sp<InputChannel> mChannel;
 
     // The current input message.
@@ -341,6 +351,7 @@ private:
     struct History {
         nsecs_t eventTime;
         BitSet32 idBits;
+        int32_t idToIndex[MAX_POINTER_ID + 1];
         PointerCoords pointers[MAX_POINTERS];
 
         void initializeFrom(const InputMessage* msg) {
@@ -349,10 +360,14 @@ private:
             for (size_t i = 0; i < msg->body.motion.pointerCount; i++) {
                 uint32_t id = msg->body.motion.pointers[i].properties.id;
                 idBits.markBit(id);
-                size_t index = idBits.getIndexOfBit(id);
-                pointers[index].copyFrom(msg->body.motion.pointers[i].coords);
+                idToIndex[id] = i;
+                pointers[i].copyFrom(msg->body.motion.pointers[i].coords);
             }
         }
+
+        const PointerCoords& getPointerById(uint32_t id) const {
+            return pointers[idToIndex[id]];
+        }
     };
     struct TouchState {
         int32_t deviceId;
@@ -360,12 +375,15 @@ private:
         size_t historyCurrent;
         size_t historySize;
         History history[2];
+        History lastResample;
 
         void initialize(int32_t deviceId, int32_t source) {
             this->deviceId = deviceId;
             this->source = source;
             historyCurrent = 0;
             historySize = 0;
+            lastResample.eventTime = 0;
+            lastResample.idBits.clear();
         }
 
         void addHistory(const InputMessage* msg) {
@@ -398,6 +416,7 @@ private:
             Batch& batch, size_t count, uint32_t* outSeq, InputEvent** outEvent);
 
     void updateTouchState(InputMessage* msg);
+    void rewriteMessage(const TouchState& state, InputMessage* msg);
     void resampleTouchState(nsecs_t frameTime, MotionEvent* event,
             const InputMessage *next);
 
@@ -412,6 +431,8 @@ private:
     static bool canAddSample(const Batch& batch, const InputMessage* msg);
     static ssize_t findSampleNoLaterThan(const Batch& batch, nsecs_t time);
     static bool shouldResampleTool(int32_t toolType);
+
+    static bool isTouchResamplingEnabled();
 };
 
 } // namespace android
diff --git a/libs/androidfw/Input.cpp b/libs/androidfw/Input.cpp
index 40a6c47..97b0ec1 100644
--- a/libs/androidfw/Input.cpp
+++ b/libs/androidfw/Input.cpp
@@ -211,26 +211,6 @@ void PointerCoords::scale(float scaleFactor) {
     scaleAxisValue(*this, AMOTION_EVENT_AXIS_TOOL_MINOR, scaleFactor);
 }
 
-void PointerCoords::lerp(const PointerCoords& a, const PointerCoords& b, float alpha) {
-    bits = 0;
-    for (uint64_t bitsRemaining = a.bits | b.bits; bitsRemaining; ) {
-        int32_t axis = __builtin_ctz(bitsRemaining);
-        uint64_t axisBit = 1LL << axis;
-        bitsRemaining &= ~axisBit;
-        if (a.bits & axisBit) {
-            if (b.bits & axisBit) {
-                float aval = a.getAxisValue(axis);
-                float bval = b.getAxisValue(axis);
-                setAxisValue(axis, aval + alpha * (bval - aval));
-            } else {
-                setAxisValue(axis, a.getAxisValue(axis));
-            }
-        } else {
-            setAxisValue(axis, b.getAxisValue(axis));
-        }
-    }
-}
-
 #ifdef HAVE_ANDROID_OS
 status_t PointerCoords::readFromParcel(Parcel* parcel) {
     bits = parcel->readInt64();
diff --git a/libs/androidfw/InputTransport.cpp b/libs/androidfw/InputTransport.cpp
index 9a4182c..351c666 100644
--- a/libs/androidfw/InputTransport.cpp
+++ b/libs/androidfw/InputTransport.cpp
@@ -21,6 +21,7 @@
 
 
 #include <cutils/log.h>
+#include <cutils/properties.h>
 #include <errno.h>
 #include <fcntl.h>
 #include <androidfw/InputTransport.h>
@@ -43,15 +44,23 @@ static const nsecs_t NANOS_PER_MS = 1000000;
 
 // Latency added during resampling.  A few milliseconds doesn't hurt much but
 // reduces the impact of mispredicted touch positions.
-static const nsecs_t RESAMPLE_LATENCY = 4 * NANOS_PER_MS;
+static const nsecs_t RESAMPLE_LATENCY = 5 * NANOS_PER_MS;
 
 // Minimum time difference between consecutive samples before attempting to resample.
-static const nsecs_t RESAMPLE_MIN_DELTA = 1 * NANOS_PER_MS;
+static const nsecs_t RESAMPLE_MIN_DELTA = 2 * NANOS_PER_MS;
 
-// Maximum linear interpolation scale value.  The larger this is, the more error may
-// potentially be introduced.
-static const float RESAMPLE_MAX_ALPHA = 2.0f;
+// Maximum time to predict forward from the last known state, to avoid predicting too
+// far into the future.  This time is further bounded by 50% of the last time delta.
+static const nsecs_t RESAMPLE_MAX_PREDICTION = 8 * NANOS_PER_MS;
 
+template<typename T>
+inline static T min(const T& a, const T& b) {
+    return a < b ? a : b;
+}
+
+inline static float lerp(float a, float b, float alpha) {
+    return a + alpha * (b - a);
+}
 
 // --- InputMessage ---
 
@@ -352,12 +361,28 @@ status_t InputPublisher::receiveFinishedSignal(uint32_t* outSeq, bool* outHandle
 // --- InputConsumer ---
 
 InputConsumer::InputConsumer(const sp<InputChannel>& channel) :
+        mResampleTouch(isTouchResamplingEnabled()),
         mChannel(channel), mMsgDeferred(false) {
 }
 
 InputConsumer::~InputConsumer() {
 }
 
+bool InputConsumer::isTouchResamplingEnabled() {
+    char value[PROPERTY_VALUE_MAX];
+    int length = property_get("debug.inputconsumer.resample", value, NULL);
+    if (length > 0) {
+        if (!strcmp("0", value)) {
+            return false;
+        }
+        if (strcmp("1", value)) {
+            ALOGD("Unrecognized property value for 'debug.inputconsumer.resample'.  "
+                    "Use '1' or '0'.");
+        }
+    }
+    return true;
+}
+
 status_t InputConsumer::consume(InputEventFactoryInterface* factory,
         bool consumeBatches, nsecs_t frameTime, uint32_t* outSeq, InputEvent** outEvent) {
 #if DEBUG_TRANSPORT_ACTIONS
@@ -538,18 +563,19 @@ status_t InputConsumer::consumeSamples(InputEventFactoryInterface* factory,
 }
 
 void InputConsumer::updateTouchState(InputMessage* msg) {
-    if (!(msg->body.motion.source & AINPUT_SOURCE_CLASS_POINTER)) {
+    if (!mResampleTouch ||
+            !(msg->body.motion.source & AINPUT_SOURCE_CLASS_POINTER)) {
         return;
     }
 
     int32_t deviceId = msg->body.motion.deviceId;
     int32_t source = msg->body.motion.source;
+    nsecs_t eventTime = msg->body.motion.eventTime;
 
-    // TODO: Filter the incoming touch event so that it aligns better
-    // with prior predictions.  Turning RESAMPLE_LATENCY offsets the need
-    // for filtering but it would be nice to reduce the latency further.
-
-    switch (msg->body.motion.action) {
+    // Update the touch state history to incorporate the new input message.
+    // If the message is in the past relative to the most recently produced resampled
+    // touch, then use the resampled time and coordinates instead.
+    switch (msg->body.motion.action & AMOTION_EVENT_ACTION_MASK) {
     case AMOTION_EVENT_ACTION_DOWN: {
         ssize_t index = findTouchState(deviceId, source);
         if (index < 0) {
@@ -567,6 +593,40 @@ void InputConsumer::updateTouchState(InputMessage* msg) {
         if (index >= 0) {
             TouchState& touchState = mTouchStates.editItemAt(index);
             touchState.addHistory(msg);
+            if (eventTime < touchState.lastResample.eventTime) {
+                rewriteMessage(touchState, msg);
+            } else {
+                touchState.lastResample.idBits.clear();
+            }
+        }
+        break;
+    }
+
+    case AMOTION_EVENT_ACTION_POINTER_DOWN: {
+        ssize_t index = findTouchState(deviceId, source);
+        if (index >= 0) {
+            TouchState& touchState = mTouchStates.editItemAt(index);
+            touchState.lastResample.idBits.clearBit(msg->body.motion.getActionId());
+            rewriteMessage(touchState, msg);
+        }
+        break;
+    }
+
+    case AMOTION_EVENT_ACTION_POINTER_UP: {
+        ssize_t index = findTouchState(deviceId, source);
+        if (index >= 0) {
+            TouchState& touchState = mTouchStates.editItemAt(index);
+            rewriteMessage(touchState, msg);
+            touchState.lastResample.idBits.clearBit(msg->body.motion.getActionId());
+        }
+        break;
+    }
+
+    case AMOTION_EVENT_ACTION_SCROLL: {
+        ssize_t index = findTouchState(deviceId, source);
+        if (index >= 0) {
+            const TouchState& touchState = mTouchStates.itemAt(index);
+            rewriteMessage(touchState, msg);
         }
         break;
     }
@@ -575,6 +635,8 @@ void InputConsumer::updateTouchState(InputMessage* msg) {
     case AMOTION_EVENT_ACTION_CANCEL: {
         ssize_t index = findTouchState(deviceId, source);
         if (index >= 0) {
+            const TouchState& touchState = mTouchStates.itemAt(index);
+            rewriteMessage(touchState, msg);
             mTouchStates.removeAt(index);
         }
         break;
@@ -582,13 +644,30 @@ void InputConsumer::updateTouchState(InputMessage* msg) {
     }
 }
 
-void InputConsumer::resampleTouchState(nsecs_t sampleTime, MotionEvent* event,
-    const InputMessage* next) {
-    if (event->getAction() != AMOTION_EVENT_ACTION_MOVE
-            || !(event->getSource() & AINPUT_SOURCE_CLASS_POINTER)) {
+void InputConsumer::rewriteMessage(const TouchState& state, InputMessage* msg) {
+    for (size_t i = 0; i < msg->body.motion.pointerCount; i++) {
+        uint32_t id = msg->body.motion.pointers[i].properties.id;
+        if (state.lastResample.idBits.hasBit(id)) {
+            PointerCoords& msgCoords = msg->body.motion.pointers[i].coords;
+            const PointerCoords& resampleCoords = state.lastResample.getPointerById(id);
 #if DEBUG_RESAMPLING
-        ALOGD("Not resampled, not a move.");
+            ALOGD("[%d] - rewrite (%0.3f, %0.3f), old (%0.3f, %0.3f)", id,
+                    resampleCoords.getAxisValue(AMOTION_EVENT_AXIS_X),
+                    resampleCoords.getAxisValue(AMOTION_EVENT_AXIS_Y),
+                    msgCoords.getAxisValue(AMOTION_EVENT_AXIS_X),
+                    msgCoords.getAxisValue(AMOTION_EVENT_AXIS_Y));
 #endif
+            msgCoords.setAxisValue(AMOTION_EVENT_AXIS_X, resampleCoords.getX());
+            msgCoords.setAxisValue(AMOTION_EVENT_AXIS_Y, resampleCoords.getY());
+        }
+    }
+}
+
+void InputConsumer::resampleTouchState(nsecs_t sampleTime, MotionEvent* event,
+    const InputMessage* next) {
+    if (!mResampleTouch
+            || !(event->getSource() & AINPUT_SOURCE_CLASS_POINTER)
+            || event->getAction() != AMOTION_EVENT_ACTION_MOVE) {
         return;
     }
 
@@ -608,73 +687,100 @@ void InputConsumer::resampleTouchState(nsecs_t sampleTime, MotionEvent* event,
         return;
     }
 
+    // Ensure that the current sample has all of the pointers that need to be reported.
     const History* current = touchState.getHistory(0);
+    size_t pointerCount = event->getPointerCount();
+    for (size_t i = 0; i < pointerCount; i++) {
+        uint32_t id = event->getPointerId(i);
+        if (!current->idBits.hasBit(id)) {
+#if DEBUG_RESAMPLING
+            ALOGD("Not resampled, missing id %d", id);
+#endif
+            return;
+        }
+    }
+
+    // Find the data to use for resampling.
     const History* other;
     History future;
+    float alpha;
     if (next) {
+        // Interpolate between current sample and future sample.
+        // So current->eventTime <= sampleTime <= future.eventTime.
         future.initializeFrom(next);
         other = &future;
+        nsecs_t delta = future.eventTime - current->eventTime;
+        if (delta < RESAMPLE_MIN_DELTA) {
+#if DEBUG_RESAMPLING
+            ALOGD("Not resampled, delta time is %lld ns.", delta);
+#endif
+            return;
+        }
+        alpha = float(sampleTime - current->eventTime) / delta;
     } else if (touchState.historySize >= 2) {
+        // Extrapolate future sample using current sample and past sample.
+        // So other->eventTime <= current->eventTime <= sampleTime.
         other = touchState.getHistory(1);
-    } else {
+        nsecs_t delta = current->eventTime - other->eventTime;
+        if (delta < RESAMPLE_MIN_DELTA) {
 #if DEBUG_RESAMPLING
-        ALOGD("Not resampled, insufficient data.");
+            ALOGD("Not resampled, delta time is %lld ns.", delta);
 #endif
-        return;
-    }
-
-    nsecs_t delta = current->eventTime - other->eventTime;
-    if (delta > -RESAMPLE_MIN_DELTA && delta < RESAMPLE_MIN_DELTA) {
+            return;
+        }
+        nsecs_t maxPredict = current->eventTime + min(delta / 2, RESAMPLE_MAX_PREDICTION);
+        if (sampleTime > maxPredict) {
 #if DEBUG_RESAMPLING
-        ALOGD("Not resampled, delta time is %lld", delta);
+            ALOGD("Sample time is too far in the future, adjusting prediction "
+                    "from %lld to %lld ns.",
+                    sampleTime - current->eventTime, maxPredict - current->eventTime);
 #endif
-        return;
-    }
-
-    float alpha = float(current->eventTime - sampleTime) / delta;
-    if (fabs(alpha) > RESAMPLE_MAX_ALPHA) {
+            sampleTime = maxPredict;
+        }
+        alpha = float(current->eventTime - sampleTime) / delta;
+    } else {
 #if DEBUG_RESAMPLING
-        ALOGD("Not resampled, alpha is %f", alpha);
+        ALOGD("Not resampled, insufficient data.");
 #endif
         return;
     }
 
-    size_t pointerCount = event->getPointerCount();
-    PointerCoords resampledCoords[MAX_POINTERS];
+    // Resample touch coordinates.
+    touchState.lastResample.eventTime = sampleTime;
+    touchState.lastResample.idBits.clear();
     for (size_t i = 0; i < pointerCount; i++) {
         uint32_t id = event->getPointerId(i);
-        if (!current->idBits.hasBit(id)) {
-#if DEBUG_RESAMPLING
-            ALOGD("Not resampled, missing id %d", id);
-#endif
-            return;
-        }
-        const PointerCoords& currentCoords =
-                current->pointers[current->idBits.getIndexOfBit(id)];
+        touchState.lastResample.idToIndex[id] = i;
+        touchState.lastResample.idBits.markBit(id);
+        PointerCoords& resampledCoords = touchState.lastResample.pointers[i];
+        const PointerCoords& currentCoords = current->getPointerById(id);
         if (other->idBits.hasBit(id)
                 && shouldResampleTool(event->getToolType(i))) {
-            const PointerCoords& otherCoords =
-                    other->pointers[other->idBits.getIndexOfBit(id)];
-            resampledCoords[i].lerp(currentCoords, otherCoords, alpha);
+            const PointerCoords& otherCoords = other->getPointerById(id);
+            resampledCoords.copyFrom(currentCoords);
+            resampledCoords.setAxisValue(AMOTION_EVENT_AXIS_X,
+                    lerp(currentCoords.getX(), otherCoords.getX(), alpha));
+            resampledCoords.setAxisValue(AMOTION_EVENT_AXIS_Y,
+                    lerp(currentCoords.getY(), otherCoords.getY(), alpha));
 #if DEBUG_RESAMPLING
             ALOGD("[%d] - out (%0.3f, %0.3f), cur (%0.3f, %0.3f), "
                     "other (%0.3f, %0.3f), alpha %0.3f",
-                    i, resampledCoords[i].getX(), resampledCoords[i].getY(),
+                    id, resampledCoords.getX(), resampledCoords.getY(),
                     currentCoords.getX(), currentCoords.getY(),
                     otherCoords.getX(), otherCoords.getY(),
                     alpha);
 #endif
         } else {
-            resampledCoords[i].copyFrom(currentCoords);
+            resampledCoords.copyFrom(currentCoords);
 #if DEBUG_RESAMPLING
             ALOGD("[%d] - out (%0.3f, %0.3f), cur (%0.3f, %0.3f)",
-                    i, resampledCoords[i].getX(), resampledCoords[i].getY(),
+                    id, resampledCoords.getX(), resampledCoords.getY(),
                     currentCoords.getX(), currentCoords.getY());
 #endif
         }
     }
 
-    event->addSample(sampleTime, resampledCoords);
+    event->addSample(sampleTime, touchState.lastResample.pointers);
 }
 
 bool InputConsumer::shouldResampleTool(int32_t toolType) {