1 files changed, 377 insertions, 0 deletions
diff --git a/widget/TouchResampler.cpp b/widget/TouchResampler.cpp
new file mode 100644
index 0000000000..eeed30fe0e
--- /dev/null
+++ b/widget/TouchResampler.cpp
@@ -0,0 +1,377 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "TouchResampler.h"
+
+#include "nsAlgorithm.h"
+
+/**
+ * TouchResampler implementation
+ */
+
+namespace mozilla {
+namespace widget {
+
+// The values below have been tested and found to be acceptable on a device
+// with a display refresh rate of 60Hz and touch sampling rate of 100Hz.
+// While their "ideal" values are dependent on the exact rates of each device,
+// the values we've picked below should be somewhat robust across a variation of
+// different rates. They mostly aim to avoid making predictions that are too far
+// away (in terms of distance) from the finger, and to detect pauses in the
+// finger motion without too much delay.
+
+// Maximum time between two consecutive data points to consider resampling
+// between them.
+// Values between 1x and 5x of the touch sampling interval are reasonable.
+static const double kTouchResampleWindowSize = 40.0;
+
+// These next two values constrain the sampling timestamp.
+// Our caller will usually adjust frame timestamps to be slightly in the past,
+// for example by 5ms. This means that, during normal operation, we will
+// maximally need to predict by [touch sampling rate] minus 5ms.
+// So we would like kTouchResampleMaxPredictMs to satisfy the following:
+// kTouchResampleMaxPredictMs + [frame time adjust] > [touch sampling rate]
+static const double kTouchResampleMaxPredictMs = 8.0;
+// This one is a protection against very outdated frame timestamps.
+// Values larger than the touch sampling interval and less than 3x of the vsync
+// interval are reasonable.
+static const double kTouchResampleMaxBacksampleMs = 20.0;
+
+// The maximum age of the most recent data point to consider resampling.
+// Should be between 1x and 3x of the touch sampling interval.
+static const double kTouchResampleOldTouchThresholdMs = 17.0;
+
+uint64_t TouchResampler::ProcessEvent(MultiTouchInput&& aInput) {
+  mCurrentTouches.UpdateFromEvent(aInput);
+
+  uint64_t eventId = mNextEventId;
+  mNextEventId++;
+
+  if (aInput.mType == MultiTouchInput::MULTITOUCH_MOVE) {
+    // Touch move events are deferred until NotifyFrame.
+    mDeferredTouchMoveEvents.push({std::move(aInput), eventId});
+  } else {
+    // Non-move events are transferred to the outgoing queue unmodified.
+    // If there are pending touch move events, flush those out first, so that
+    // events are emitted in the right order.
+    FlushDeferredTouchMoveEventsUnresampled();
+    if (mInResampledState) {
+      // Return to a non-resampled state before emitting a non-move event.
+      ReturnToNonResampledState();
+    }
+    EmitEvent(std::move(aInput), eventId);
+  }
+
+  return eventId;
+}
+
+void TouchResampler::NotifyFrame(const TimeStamp& aTimeStamp) {
+  TimeStamp lastTouchTime = mCurrentTouches.LatestDataPointTime();
+  if (mDeferredTouchMoveEvents.empty() ||
+      (lastTouchTime &&
+       lastTouchTime < aTimeStamp - TimeDuration::FromMilliseconds(
+                                        kTouchResampleOldTouchThresholdMs))) {
+    // We haven't received a touch move event in a while, so the fingers must
+    // have stopped moving. Flush any old touch move events.
+    FlushDeferredTouchMoveEventsUnresampled();
+
+    if (mInResampledState) {
+      // Make sure we pause at the resting position that we actually observed,
+      // and not at a resampled position.
+      ReturnToNonResampledState();
+    }
+
+    // Clear touch location history so that we don't resample across a pause.
+    mCurrentTouches.ClearDataPoints();
+    return;
+  }
+
+  MOZ_RELEASE_ASSERT(lastTouchTime);
+  TimeStamp lowerBound = lastTouchTime - TimeDuration::FromMilliseconds(
+                                             kTouchResampleMaxBacksampleMs);
+  TimeStamp upperBound = lastTouchTime + TimeDuration::FromMilliseconds(
+                                             kTouchResampleMaxPredictMs);
+  TimeStamp sampleTime = clamped(aTimeStamp, lowerBound, upperBound);
+
+  if (mLastEmittedEventTime && sampleTime < mLastEmittedEventTime) {
+    // Keep emitted timestamps in order.
+    sampleTime = mLastEmittedEventTime;
+  }
+
+  // We have at least one pending touch move event. Pick one of the events from
+  // mDeferredTouchMoveEvents as the base event for the resampling adjustment.
+  // We want to produce an event stream whose timestamps are in the right order.
+  // As the base event, use the first event that's at or after sampleTime,
+  // unless there is no such event, in that case use the last one we have. We
+  // will set the timestamp on the resampled event to sampleTime later.
+  // Flush out any older events so that everything remains in the right order.
+  MultiTouchInput input;
+  uint64_t eventId;
+  while (true) {
+    MOZ_RELEASE_ASSERT(!mDeferredTouchMoveEvents.empty());
+    std::tie(input, eventId) = std::move(mDeferredTouchMoveEvents.front());
+    mDeferredTouchMoveEvents.pop();
+    if (mDeferredTouchMoveEvents.empty() || input.mTimeStamp >= sampleTime) {
+      break;
+    }
+    // Flush this event to the outgoing queue without resampling. What ends up
+    // on the screen will still be smooth because we will proceed to emit a
+    // resampled event before the paint for this frame starts.
+    PrependLeftoverHistoricalData(&input);
+    MOZ_RELEASE_ASSERT(input.mTimeStamp < sampleTime);
+    EmitEvent(std::move(input), eventId);
+  }
+
+  mOriginalOfResampledTouchMove = Nothing();
+
+  // Compute the resampled touch positions.
+  nsTArray<ScreenIntPoint> resampledPositions;
+  bool anyPositionDifferentFromOriginal = false;
+  for (const auto& touch : input.mTouches) {
+    ScreenIntPoint resampledPosition =
+        mCurrentTouches.ResampleTouchPositionAtTime(
+            touch.mIdentifier, touch.mScreenPoint, sampleTime);
+    if (resampledPosition != touch.mScreenPoint) {
+      anyPositionDifferentFromOriginal = true;
+    }
+    resampledPositions.AppendElement(resampledPosition);
+  }
+
+  if (anyPositionDifferentFromOriginal) {
+    // Store a copy of the original event, so that we can return to an
+    // non-resampled position later, if necessary.
+    mOriginalOfResampledTouchMove = Some(input);
+
+    // Add the original observed position to the historical data, as well as any
+    // leftover historical positions from the previous touch move event, and
+    // store the resampled values in the "final" position of the event.
+    PrependLeftoverHistoricalData(&input);
+    for (size_t i = 0; i < input.mTouches.Length(); i++) {
+      auto& touch = input.mTouches[i];
+      touch.mHistoricalData.AppendElement(SingleTouchData::HistoricalTouchData{
+          input.mTimeStamp,
+          touch.mScreenPoint,
+          touch.mLocalScreenPoint,
+          touch.mRadius,
+          touch.mRotationAngle,
+          touch.mForce,
+      });
+
+      // Remove any historical touch data that's in the future, compared to
+      // sampleTime. This data will be included by upcoming touch move
+      // events. This only happens if the frame timestamp can be older than the
+      // event timestamp, i.e. if interpolation occurs (rather than
+      // extrapolation).
+      auto futureDataStart = std::find_if(
+          touch.mHistoricalData.begin(), touch.mHistoricalData.end(),
+          [sampleTime](
+              const SingleTouchData::HistoricalTouchData& aHistoricalData) {
+            return aHistoricalData.mTimeStamp > sampleTime;
+          });
+      if (futureDataStart != touch.mHistoricalData.end()) {
+        nsTArray<SingleTouchData::HistoricalTouchData> futureData(
+            Span<SingleTouchData::HistoricalTouchData>(touch.mHistoricalData)
+                .From(futureDataStart.GetIndex()));
+        touch.mHistoricalData.TruncateLength(futureDataStart.GetIndex());
+        mRemainingTouchData.insert({touch.mIdentifier, std::move(futureData)});
+      }
+
+      touch.mScreenPoint = resampledPositions[i];
+    }
+    input.mTimeStamp = sampleTime;
+  }
+
+  EmitEvent(std::move(input), eventId);
+  mInResampledState = anyPositionDifferentFromOriginal;
+}
+
+void TouchResampler::PrependLeftoverHistoricalData(MultiTouchInput* aInput) {
+  for (auto& touch : aInput->mTouches) {
+    auto leftoverData = mRemainingTouchData.find(touch.mIdentifier);
+    if (leftoverData != mRemainingTouchData.end()) {
+      nsTArray<SingleTouchData::HistoricalTouchData> data =
+          std::move(leftoverData->second);
+      mRemainingTouchData.erase(leftoverData);
+      touch.mHistoricalData.InsertElementsAt(0, data);
+    }
+
+    if (TimeStamp cutoffTime = mLastEmittedEventTime) {
+      // If we received historical touch data that was further in the past than
+      // the last resampled event, discard that data so that the touch data
+      // points are emitted in order.
+      touch.mHistoricalData.RemoveElementsBy(
+          [cutoffTime](const SingleTouchData::HistoricalTouchData& aTouchData) {
+            return aTouchData.mTimeStamp < cutoffTime;
+          });
+    }
+  }
+  mRemainingTouchData.clear();
+}
+
+void TouchResampler::FlushDeferredTouchMoveEventsUnresampled() {
+  while (!mDeferredTouchMoveEvents.empty()) {
+    auto [input, eventId] = std::move(mDeferredTouchMoveEvents.front());
+    mDeferredTouchMoveEvents.pop();
+    PrependLeftoverHistoricalData(&input);
+    EmitEvent(std::move(input), eventId);
+    mInResampledState = false;
+    mOriginalOfResampledTouchMove = Nothing();
+  }
+}
+
+void TouchResampler::ReturnToNonResampledState() {
+  MOZ_RELEASE_ASSERT(mInResampledState);
+  MOZ_RELEASE_ASSERT(mDeferredTouchMoveEvents.empty(),
+                     "Don't call this if there is a deferred touch move event. "
+                     "We can return to the non-resampled state by sending that "
+                     "event, rather than a copy of a previous event.");
+
+  // The last outgoing event was a resampled touch move event.
+  // Return to the non-resampled state, by sending a touch move event to
+  // "overwrite" any resampled positions with the original observed positions.
+  MultiTouchInput input = std::move(*mOriginalOfResampledTouchMove);
+  mOriginalOfResampledTouchMove = Nothing();
+
+  // For the event's timestamp, we want to backdate the correction as far as we
+  // can, while still preserving timestamp ordering. But we also don't want to
+  // backdate it to be older than it was originally.
+  if (mLastEmittedEventTime > input.mTimeStamp) {
+    input.mTimeStamp = mLastEmittedEventTime;
+  }
+
+  // Assemble the correct historical touch data for this event.
+  // We don't want to include data points that we've already sent out with the
+  // resampled event. And from the leftover data points, we only want those that
+  // don't duplicate the final time + position of this event.
+  for (auto& touch : input.mTouches) {
+    touch.mHistoricalData.Clear();
+  }
+  PrependLeftoverHistoricalData(&input);
+  for (auto& touch : input.mTouches) {
+    touch.mHistoricalData.RemoveElementsBy([&](const auto& histData) {
+      return histData.mTimeStamp >= input.mTimeStamp;
+    });
+  }
+
+  EmitExtraEvent(std::move(input));
+  mInResampledState = false;
+}
+
+void TouchResampler::TouchInfo::Update(const SingleTouchData& aTouch,
+                                       const TimeStamp& aEventTime) {
+  for (const auto& historicalData : aTouch.mHistoricalData) {
+    mBaseDataPoint = mLatestDataPoint;
+    mLatestDataPoint =
+        Some(DataPoint{historicalData.mTimeStamp, historicalData.mScreenPoint});
+  }
+  mBaseDataPoint = mLatestDataPoint;
+  mLatestDataPoint = Some(DataPoint{aEventTime, aTouch.mScreenPoint});
+}
+
+ScreenIntPoint TouchResampler::TouchInfo::ResampleAtTime(
+    const ScreenIntPoint& aLastObservedPosition, const TimeStamp& aTimeStamp) {
+  TimeStamp cutoff =
+      aTimeStamp - TimeDuration::FromMilliseconds(kTouchResampleWindowSize);
+  if (!mBaseDataPoint || !mLatestDataPoint ||
+      !(mBaseDataPoint->mTimeStamp < mLatestDataPoint->mTimeStamp) ||
+      mBaseDataPoint->mTimeStamp < cutoff) {
+    return aLastObservedPosition;
+  }
+
+  // For the actual resampling, connect the last two data points with a line and
+  // sample along that line.
+  TimeStamp t1 = mBaseDataPoint->mTimeStamp;
+  TimeStamp t2 = mLatestDataPoint->mTimeStamp;
+  double t = (aTimeStamp - t1) / (t2 - t1);
+
+  double x1 = mBaseDataPoint->mPosition.x;
+  double x2 = mLatestDataPoint->mPosition.x;
+  double y1 = mBaseDataPoint->mPosition.y;
+  double y2 = mLatestDataPoint->mPosition.y;
+
+  int32_t resampledX = round(x1 + t * (x2 - x1));
+  int32_t resampledY = round(y1 + t * (y2 - y1));
+  return ScreenIntPoint(resampledX, resampledY);
+}
+
+void TouchResampler::CurrentTouches::UpdateFromEvent(
+    const MultiTouchInput& aInput) {
+  switch (aInput.mType) {
+    case MultiTouchInput::MULTITOUCH_START: {
+      // A new touch has been added; make sure mTouches reflects the current
+      // touches in the event.
+      nsTArray<TouchInfo> newTouches;
+      for (const auto& touch : aInput.mTouches) {
+        const auto touchInfo = TouchByIdentifier(touch.mIdentifier);
+        if (touchInfo != mTouches.end()) {
+          // This is one of the existing touches.
+          newTouches.AppendElement(std::move(*touchInfo));
+          mTouches.RemoveElementAt(touchInfo);
+        } else {
+          // This is the new touch.
+          newTouches.AppendElement(TouchInfo{
+              touch.mIdentifier, Nothing(),
+              Some(DataPoint{aInput.mTimeStamp, touch.mScreenPoint})});
+        }
+      }
+      MOZ_ASSERT(mTouches.IsEmpty(), "Missing touch end before touch start?");
+      mTouches = std::move(newTouches);
+      break;
+    }
+
+    case MultiTouchInput::MULTITOUCH_MOVE: {
+      // The touches have moved.
+      // Add position information to the history data points.
+      for (const auto& touch : aInput.mTouches) {
+        const auto touchInfo = TouchByIdentifier(touch.mIdentifier);
+        MOZ_ASSERT(touchInfo != mTouches.end());
+        if (touchInfo != mTouches.end()) {
+          touchInfo->Update(touch, aInput.mTimeStamp);
+        }
+      }
+      mLatestDataPointTime = aInput.mTimeStamp;
+      break;
+    }
+
+    case MultiTouchInput::MULTITOUCH_END: {
+      // A touch has been removed.
+      MOZ_RELEASE_ASSERT(aInput.mTouches.Length() == 1);
+      const auto touchInfo = TouchByIdentifier(aInput.mTouches[0].mIdentifier);
+      MOZ_ASSERT(touchInfo != mTouches.end());
+      if (touchInfo != mTouches.end()) {
+        mTouches.RemoveElementAt(touchInfo);
+      }
+      break;
+    }
+
+    case MultiTouchInput::MULTITOUCH_CANCEL:
+      // All touches are canceled.
+      mTouches.Clear();
+      break;
+  }
+}
+
+nsTArray<TouchResampler::TouchInfo>::iterator
+TouchResampler::CurrentTouches::TouchByIdentifier(int32_t aIdentifier) {
+  return std::find_if(mTouches.begin(), mTouches.end(),
+                      [aIdentifier](const TouchInfo& info) {
+                        return info.mIdentifier == aIdentifier;
+                      });
+}
+
+ScreenIntPoint TouchResampler::CurrentTouches::ResampleTouchPositionAtTime(
+    int32_t aIdentifier, const ScreenIntPoint& aLastObservedPosition,
+    const TimeStamp& aTimeStamp) {
+  const auto touchInfo = TouchByIdentifier(aIdentifier);
+  MOZ_ASSERT(touchInfo != mTouches.end());
+  if (touchInfo != mTouches.end()) {
+    return touchInfo->ResampleAtTime(aLastObservedPosition, aTimeStamp);
+  }
+  return aLastObservedPosition;
+}
+
+}  // namespace widget
+}  // namespace mozilla