1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "ui/events/gesture_detection/motion_event_buffer.h"
6
7#include "base/debug/trace_event.h"
8#include "ui/events/gesture_detection/motion_event.h"
9#include "ui/events/gesture_detection/motion_event_generic.h"
10
11namespace ui {
12namespace {
13
14// Latency added during resampling. A few milliseconds doesn't hurt much but
15// reduces the impact of mispredicted touch positions.
16const int kResampleLatencyMs = 5;
17
18// Minimum time difference between consecutive samples before attempting to
19// resample.
20const int kResampleMinDeltaMs = 2;
21
22// Maximum time to predict forward from the last known state, to avoid
23// predicting too far into the future.  This time is further bounded by 50% of
24// the last time delta.
25const int kResampleMaxPredictionMs = 8;
26
27typedef ScopedVector<MotionEvent> MotionEventVector;
28
29float Lerp(float a, float b, float alpha) {
30  return a + alpha * (b - a);
31}
32
33bool CanAddSample(const MotionEvent& event0, const MotionEvent& event1) {
34  DCHECK_EQ(event0.GetAction(), MotionEvent::ACTION_MOVE);
35  if (event1.GetAction() != MotionEvent::ACTION_MOVE)
36    return false;
37
38  const size_t pointer_count = event0.GetPointerCount();
39  if (pointer_count != event1.GetPointerCount())
40    return false;
41
42  for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
43    const int id = event0.GetPointerId(event0_i);
44    const int event1_i = event1.FindPointerIndexOfId(id);
45    if (event1_i == -1)
46      return false;
47    if (event0.GetToolType(event0_i) != event1.GetToolType(event1_i))
48      return false;
49  }
50
51  return true;
52}
53
54bool ShouldResampleTool(MotionEvent::ToolType tool) {
55  return tool == MotionEvent::TOOL_TYPE_UNKNOWN ||
56         tool == MotionEvent::TOOL_TYPE_FINGER;
57}
58
59size_t CountSamplesNoLaterThan(const MotionEventVector& batch,
60                               base::TimeTicks time) {
61  size_t count = 0;
62  while (count < batch.size() && batch[count]->GetEventTime() <= time)
63    ++count;
64  return count;
65}
66
67MotionEventVector ConsumeSamplesNoLaterThan(MotionEventVector* batch,
68                                            base::TimeTicks time) {
69  DCHECK(batch);
70  size_t count = CountSamplesNoLaterThan(*batch, time);
71  DCHECK_GE(batch->size(), count);
72  if (count == 0)
73    return MotionEventVector();
74
75  if (count == batch->size())
76    return batch->Pass();
77
78  // TODO(jdduke): Use a ScopedDeque to work around this mess.
79  MotionEventVector unconsumed_batch;
80  unconsumed_batch.insert(
81      unconsumed_batch.begin(), batch->begin() + count, batch->end());
82  batch->weak_erase(batch->begin() + count, batch->end());
83
84  unconsumed_batch.swap(*batch);
85  DCHECK_GE(unconsumed_batch.size(), 1U);
86  return unconsumed_batch.Pass();
87}
88
89PointerProperties PointerFromMotionEvent(const MotionEvent& event,
90                                         size_t pointer_index) {
91  PointerProperties result;
92  result.id = event.GetPointerId(pointer_index);
93  result.tool_type = event.GetToolType(pointer_index);
94  result.x = event.GetX(pointer_index);
95  result.y = event.GetY(pointer_index);
96  result.raw_x = event.GetRawX(pointer_index);
97  result.raw_y = event.GetRawY(pointer_index);
98  result.pressure = event.GetPressure(pointer_index);
99  result.touch_major = event.GetTouchMajor(pointer_index);
100  result.touch_minor = event.GetTouchMinor(pointer_index);
101  result.orientation = event.GetOrientation(pointer_index);
102  return result;
103}
104
105PointerProperties ResamplePointer(const MotionEvent& event0,
106                                  const MotionEvent& event1,
107                                  size_t event0_pointer_index,
108                                  size_t event1_pointer_index,
109                                  float alpha) {
110  DCHECK_EQ(event0.GetPointerId(event0_pointer_index),
111            event1.GetPointerId(event1_pointer_index));
112  // If the tool should not be resampled, use the latest event in the valid
113  // horizon (i.e., the event no later than the time interpolated by alpha).
114  if (!ShouldResampleTool(event0.GetToolType(event0_pointer_index))) {
115    if (alpha > 1)
116      return PointerFromMotionEvent(event1, event1_pointer_index);
117    else
118      return PointerFromMotionEvent(event0, event0_pointer_index);
119  }
120
121  PointerProperties p(PointerFromMotionEvent(event0, event0_pointer_index));
122  p.x = Lerp(p.x, event1.GetX(event1_pointer_index), alpha);
123  p.y = Lerp(p.y, event1.GetY(event1_pointer_index), alpha);
124  p.raw_x = Lerp(p.raw_x, event1.GetRawX(event1_pointer_index), alpha);
125  p.raw_y = Lerp(p.raw_y, event1.GetRawY(event1_pointer_index), alpha);
126  return p;
127}
128
129scoped_ptr<MotionEvent> ResampleMotionEvent(const MotionEvent& event0,
130                                            const MotionEvent& event1,
131                                            base::TimeTicks resample_time) {
132  DCHECK_EQ(MotionEvent::ACTION_MOVE, event0.GetAction());
133  DCHECK_EQ(event0.GetPointerCount(), event1.GetPointerCount());
134
135  const base::TimeTicks time0 = event0.GetEventTime();
136  const base::TimeTicks time1 = event1.GetEventTime();
137  DCHECK(time0 < time1);
138  DCHECK(time0 <= resample_time);
139
140  const float alpha = (resample_time - time0).InMillisecondsF() /
141                      (time1 - time0).InMillisecondsF();
142
143  scoped_ptr<MotionEventGeneric> event;
144  const size_t pointer_count = event0.GetPointerCount();
145  DCHECK_EQ(pointer_count, event1.GetPointerCount());
146  for (size_t event0_i = 0; event0_i < pointer_count; ++event0_i) {
147    int event1_i = event1.FindPointerIndexOfId(event0.GetPointerId(event0_i));
148    DCHECK_NE(event1_i, -1);
149    PointerProperties pointer = ResamplePointer(
150        event0, event1, event0_i, static_cast<size_t>(event1_i), alpha);
151
152    if (event0_i == 0) {
153      event.reset(new MotionEventGeneric(
154          MotionEvent::ACTION_MOVE, resample_time, pointer));
155    } else {
156      event->PushPointer(pointer);
157    }
158  }
159
160  DCHECK(event);
161  event->set_id(event0.GetId());
162  event->set_action_index(event0.GetActionIndex());
163  event->set_button_state(event0.GetButtonState());
164
165  return event.PassAs<MotionEvent>();
166}
167
168// MotionEvent implementation for storing multiple events, with the most
169// recent event used as the base event, and prior events used as the history.
170class CompoundMotionEvent : public ui::MotionEvent {
171 public:
172  explicit CompoundMotionEvent(MotionEventVector events)
173      : events_(events.Pass()) {
174    DCHECK_GE(events_.size(), 1U);
175  }
176  virtual ~CompoundMotionEvent() {}
177
178  virtual int GetId() const OVERRIDE { return latest().GetId(); }
179
180  virtual Action GetAction() const OVERRIDE { return latest().GetAction(); }
181
182  virtual int GetActionIndex() const OVERRIDE {
183    return latest().GetActionIndex();
184  }
185
186  virtual size_t GetPointerCount() const OVERRIDE {
187    return latest().GetPointerCount();
188  }
189
190  virtual int GetPointerId(size_t pointer_index) const OVERRIDE {
191    return latest().GetPointerId(pointer_index);
192  }
193
194  virtual float GetX(size_t pointer_index) const OVERRIDE {
195    return latest().GetX(pointer_index);
196  }
197
198  virtual float GetY(size_t pointer_index) const OVERRIDE {
199    return latest().GetY(pointer_index);
200  }
201
202  virtual float GetRawX(size_t pointer_index) const OVERRIDE {
203    return latest().GetRawX(pointer_index);
204  }
205
206  virtual float GetRawY(size_t pointer_index) const OVERRIDE {
207    return latest().GetRawY(pointer_index);
208  }
209
210  virtual float GetTouchMajor(size_t pointer_index) const OVERRIDE {
211    return latest().GetTouchMajor(pointer_index);
212  }
213
214  virtual float GetTouchMinor(size_t pointer_index) const OVERRIDE {
215    return latest().GetTouchMinor(pointer_index);
216  }
217
218  virtual float GetOrientation(size_t pointer_index) const OVERRIDE {
219    return latest().GetOrientation(pointer_index);
220  }
221
222  virtual float GetPressure(size_t pointer_index) const OVERRIDE {
223    return latest().GetPressure(pointer_index);
224  }
225
226  virtual ToolType GetToolType(size_t pointer_index) const OVERRIDE {
227    return latest().GetToolType(pointer_index);
228  }
229
230  virtual int GetButtonState() const OVERRIDE {
231    return latest().GetButtonState();
232  }
233
234  virtual int GetFlags() const OVERRIDE { return latest().GetFlags(); }
235
236  virtual base::TimeTicks GetEventTime() const OVERRIDE {
237    return latest().GetEventTime();
238  }
239
240  virtual size_t GetHistorySize() const OVERRIDE { return events_.size() - 1; }
241
242  virtual base::TimeTicks GetHistoricalEventTime(
243      size_t historical_index) const OVERRIDE {
244    DCHECK_LT(historical_index, GetHistorySize());
245    return events_[historical_index]->GetEventTime();
246  }
247
248  virtual float GetHistoricalTouchMajor(
249      size_t pointer_index,
250      size_t historical_index) const OVERRIDE {
251    DCHECK_LT(historical_index, GetHistorySize());
252    return events_[historical_index]->GetTouchMajor();
253  }
254
255  virtual float GetHistoricalX(size_t pointer_index,
256                               size_t historical_index) const OVERRIDE {
257    DCHECK_LT(historical_index, GetHistorySize());
258    return events_[historical_index]->GetX(pointer_index);
259  }
260
261  virtual float GetHistoricalY(size_t pointer_index,
262                               size_t historical_index) const OVERRIDE {
263    DCHECK_LT(historical_index, GetHistorySize());
264    return events_[historical_index]->GetY(pointer_index);
265  }
266
267  virtual scoped_ptr<MotionEvent> Clone() const OVERRIDE {
268    MotionEventVector cloned_events;
269    cloned_events.reserve(events_.size());
270    for (size_t i = 0; i < events_.size(); ++i)
271      cloned_events.push_back(events_[i]->Clone().release());
272    return scoped_ptr<MotionEvent>(
273        new CompoundMotionEvent(cloned_events.Pass()));
274  }
275
276  virtual scoped_ptr<MotionEvent> Cancel() const OVERRIDE {
277    return latest().Cancel();
278  }
279
280  // Returns the new, resampled event, or NULL if none was created.
281  // TODO(jdduke): Revisit resampling to handle cases where alternating frames
282  // are resampled or resampling is otherwise inconsistent, e.g., a 90hz input
283  // and 60hz frame signal could phase-align such that even frames yield an
284  // extrapolated event and odd frames are not resampled, crbug.com/399381.
285  const MotionEvent* TryResample(base::TimeTicks resample_time,
286                                 const ui::MotionEvent* next) {
287    DCHECK_EQ(GetAction(), ACTION_MOVE);
288    const ui::MotionEvent* event0 = NULL;
289    const ui::MotionEvent* event1 = NULL;
290    if (next) {
291      DCHECK(resample_time < next->GetEventTime());
292      // Interpolate between current sample and future sample.
293      event0 = events_.back();
294      event1 = next;
295    } else if (events_.size() >= 2) {
296      // Extrapolate future sample using current sample and past sample.
297      event0 = events_[events_.size() - 2];
298      event1 = events_[events_.size() - 1];
299
300      const base::TimeTicks time1 = event1->GetEventTime();
301      base::TimeTicks max_predict =
302          time1 +
303          std::min((event1->GetEventTime() - event0->GetEventTime()) / 2,
304                   base::TimeDelta::FromMilliseconds(kResampleMaxPredictionMs));
305      if (resample_time > max_predict) {
306        TRACE_EVENT_INSTANT2("input",
307                             "MotionEventBuffer::TryResample prediction adjust",
308                             TRACE_EVENT_SCOPE_THREAD,
309                             "original(ms)",
310                             (resample_time - time1).InMilliseconds(),
311                             "adjusted(ms)",
312                             (max_predict - time1).InMilliseconds());
313        resample_time = max_predict;
314      }
315    } else {
316      TRACE_EVENT_INSTANT0("input",
317                           "MotionEventBuffer::TryResample insufficient data",
318                           TRACE_EVENT_SCOPE_THREAD);
319      return NULL;
320    }
321
322    DCHECK(event0);
323    DCHECK(event1);
324    const base::TimeTicks time0 = event0->GetEventTime();
325    const base::TimeTicks time1 = event1->GetEventTime();
326    base::TimeDelta delta = time1 - time0;
327    if (delta < base::TimeDelta::FromMilliseconds(kResampleMinDeltaMs)) {
328      TRACE_EVENT_INSTANT1("input",
329                           "MotionEventBuffer::TryResample failure",
330                           TRACE_EVENT_SCOPE_THREAD,
331                           "event_delta_too_small(ms)",
332                           delta.InMilliseconds());
333      return NULL;
334    }
335
336    events_.push_back(
337        ResampleMotionEvent(*event0, *event1, resample_time).release());
338    return events_.back();
339  }
340
341  size_t samples() const { return events_.size(); }
342
343 private:
344  const MotionEvent& latest() const { return *events_.back(); }
345
346  // Events are in order from oldest to newest.
347  MotionEventVector events_;
348
349  DISALLOW_COPY_AND_ASSIGN(CompoundMotionEvent);
350};
351
352}  // namespace
353
354MotionEventBuffer::MotionEventBuffer(MotionEventBufferClient* client,
355                                     bool enable_resampling)
356    : client_(client), resample_(enable_resampling) {
357}
358
359MotionEventBuffer::~MotionEventBuffer() {
360}
361
362void MotionEventBuffer::OnMotionEvent(const MotionEvent& event) {
363  if (event.GetAction() != MotionEvent::ACTION_MOVE) {
364    last_extrapolated_event_time_ = base::TimeTicks();
365    if (!buffered_events_.empty())
366      FlushWithoutResampling(buffered_events_.Pass());
367    client_->ForwardMotionEvent(event);
368    return;
369  }
370
371  // Guard against events that are *older* than the last one that may have been
372  // artificially synthesized.
373  if (!last_extrapolated_event_time_.is_null()) {
374    DCHECK(buffered_events_.empty());
375    if (event.GetEventTime() < last_extrapolated_event_time_)
376      return;
377    last_extrapolated_event_time_ = base::TimeTicks();
378  }
379
380  scoped_ptr<MotionEvent> clone = event.Clone();
381  if (buffered_events_.empty()) {
382    buffered_events_.push_back(clone.release());
383    client_->SetNeedsFlush();
384    return;
385  }
386
387  if (CanAddSample(*buffered_events_.front(), *clone)) {
388    DCHECK(buffered_events_.back()->GetEventTime() <= clone->GetEventTime());
389  } else {
390    FlushWithoutResampling(buffered_events_.Pass());
391  }
392
393  buffered_events_.push_back(clone.release());
394  // No need to request another flush as the first event will have requested it.
395}
396
397void MotionEventBuffer::Flush(base::TimeTicks frame_time) {
398  if (buffered_events_.empty())
399    return;
400
401  // Shifting the sample time back slightly minimizes the potential for
402  // misprediction when extrapolating events.
403  if (resample_)
404    frame_time -= base::TimeDelta::FromMilliseconds(kResampleLatencyMs);
405
406  // TODO(jdduke): Use a persistent MotionEventVector vector for temporary
407  // storage.
408  MotionEventVector events(
409      ConsumeSamplesNoLaterThan(&buffered_events_, frame_time));
410  if (events.empty()) {
411    DCHECK(!buffered_events_.empty());
412    client_->SetNeedsFlush();
413    return;
414  }
415
416  if (!resample_ || (events.size() == 1 && buffered_events_.empty())) {
417    FlushWithoutResampling(events.Pass());
418    if (!buffered_events_.empty())
419      client_->SetNeedsFlush();
420    return;
421  }
422
423  CompoundMotionEvent resampled_event(events.Pass());
424  base::TimeTicks original_event_time = resampled_event.GetEventTime();
425  const MotionEvent* next_event =
426      !buffered_events_.empty() ? buffered_events_.front() : NULL;
427
428  // Try to interpolate/extrapolate a new event at |frame_time|. Note that
429  // |new_event|, if non-NULL, is owned by |resampled_event_|.
430  const MotionEvent* new_event =
431      resampled_event.TryResample(frame_time, next_event);
432
433  // Log the extrapolated event time, guarding against subsequently queued
434  // events that might have an earlier timestamp.
435  if (!next_event && new_event &&
436      new_event->GetEventTime() > original_event_time) {
437    last_extrapolated_event_time_ = new_event->GetEventTime();
438  } else {
439    last_extrapolated_event_time_ = base::TimeTicks();
440  }
441
442  client_->ForwardMotionEvent(resampled_event);
443  if (!buffered_events_.empty())
444    client_->SetNeedsFlush();
445}
446
447void MotionEventBuffer::FlushWithoutResampling(MotionEventVector events) {
448  last_extrapolated_event_time_ = base::TimeTicks();
449  if (events.empty())
450    return;
451
452  if (events.size() == 1) {
453    // Avoid CompoundEvent creation to prevent unnecessary allocations.
454    scoped_ptr<MotionEvent> event(events.front());
455    events.weak_clear();
456    client_->ForwardMotionEvent(*event);
457    return;
458  }
459
460  CompoundMotionEvent compound_event(events.Pass());
461  client_->ForwardMotionEvent(compound_event);
462}
463
464}  // namespace ui
465