Input.cpp revision b0c71eb9f50ce06327fa6bb6219f0970e04fd856 
1//
2// Copyright 2010 The Android Open Source Project
3//
4// Provides a pipe-based transport for native events in the NDK.
5//
6#define LOG_TAG "Input"
7
8//#define LOG_NDEBUG 0
9
10// Log debug messages about keymap probing.
11#define DEBUG_PROBE 0
12
13// Log debug messages about velocity tracking.
14#define DEBUG_VELOCITY 0
15
16// Log debug messages about least squares fitting.
17#define DEBUG_LEAST_SQUARES 0
18
19// Log debug messages about acceleration.
20#define DEBUG_ACCELERATION 0
21
22
23#include <stdlib.h>
24#include <unistd.h>
25#include <ctype.h>
26
27#include <ui/Input.h>
28
29#include <math.h>
30#include <limits.h>
31
32#ifdef HAVE_ANDROID_OS
33#include <binder/Parcel.h>
34
35#include "SkPoint.h"
36#include "SkMatrix.h"
37#include "SkScalar.h"
38#endif
39
40namespace android {
41
42static const char* CONFIGURATION_FILE_DIR[] = {
43        "idc/",
44        "keylayout/",
45        "keychars/",
46};
47
48static const char* CONFIGURATION_FILE_EXTENSION[] = {
49        ".idc",
50        ".kl",
51        ".kcm",
52};
53
54static bool isValidNameChar(char ch) {
55    return isascii(ch) && (isdigit(ch) || isalpha(ch) || ch == '-' || ch == '_');
56}
57
58static void appendInputDeviceConfigurationFileRelativePath(String8& path,
59        const String8& name, InputDeviceConfigurationFileType type) {
60    path.append(CONFIGURATION_FILE_DIR[type]);
61    for (size_t i = 0; i < name.length(); i++) {
62        char ch = name[i];
63        if (!isValidNameChar(ch)) {
64            ch = '_';
65        }
66        path.append(&ch, 1);
67    }
68    path.append(CONFIGURATION_FILE_EXTENSION[type]);
69}
70
71String8 getInputDeviceConfigurationFilePathByDeviceIdentifier(
72        const InputDeviceIdentifier& deviceIdentifier,
73        InputDeviceConfigurationFileType type) {
74    if (deviceIdentifier.vendor !=0 && deviceIdentifier.product != 0) {
75        if (deviceIdentifier.version != 0) {
76            // Try vendor product version.
77            String8 versionPath(getInputDeviceConfigurationFilePathByName(
78                    String8::format("Vendor_%04x_Product_%04x_Version_%04x",
79                            deviceIdentifier.vendor, deviceIdentifier.product,
80                            deviceIdentifier.version),
81                    type));
82            if (!versionPath.isEmpty()) {
83                return versionPath;
84            }
85        }
86
87        // Try vendor product.
88        String8 productPath(getInputDeviceConfigurationFilePathByName(
89                String8::format("Vendor_%04x_Product_%04x",
90                        deviceIdentifier.vendor, deviceIdentifier.product),
91                type));
92        if (!productPath.isEmpty()) {
93            return productPath;
94        }
95    }
96
97    // Try device name.
98    return getInputDeviceConfigurationFilePathByName(deviceIdentifier.name, type);
99}
100
101String8 getInputDeviceConfigurationFilePathByName(
102        const String8& name, InputDeviceConfigurationFileType type) {
103    // Search system repository.
104    String8 path;
105    path.setTo(getenv("ANDROID_ROOT"));
106    path.append("/usr/");
107    appendInputDeviceConfigurationFileRelativePath(path, name, type);
108#if DEBUG_PROBE
109    LOGD("Probing for system provided input device configuration file: path='%s'", path.string());
110#endif
111    if (!access(path.string(), R_OK)) {
112#if DEBUG_PROBE
113        LOGD("Found");
114#endif
115        return path;
116    }
117
118    // Search user repository.
119    // TODO Should only look here if not in safe mode.
120    path.setTo(getenv("ANDROID_DATA"));
121    path.append("/system/devices/");
122    appendInputDeviceConfigurationFileRelativePath(path, name, type);
123#if DEBUG_PROBE
124    LOGD("Probing for system user input device configuration file: path='%s'", path.string());
125#endif
126    if (!access(path.string(), R_OK)) {
127#if DEBUG_PROBE
128        LOGD("Found");
129#endif
130        return path;
131    }
132
133    // Not found.
134#if DEBUG_PROBE
135    LOGD("Probe failed to find input device configuration file: name='%s', type=%d",
136            name.string(), type);
137#endif
138    return String8();
139}
140
141
142// --- InputEvent ---
143
144void InputEvent::initialize(int32_t deviceId, int32_t source) {
145    mDeviceId = deviceId;
146    mSource = source;
147}
148
149void InputEvent::initialize(const InputEvent& from) {
150    mDeviceId = from.mDeviceId;
151    mSource = from.mSource;
152}
153
154// --- KeyEvent ---
155
156bool KeyEvent::hasDefaultAction(int32_t keyCode) {
157    switch (keyCode) {
158        case AKEYCODE_HOME:
159        case AKEYCODE_BACK:
160        case AKEYCODE_CALL:
161        case AKEYCODE_ENDCALL:
162        case AKEYCODE_VOLUME_UP:
163        case AKEYCODE_VOLUME_DOWN:
164        case AKEYCODE_VOLUME_MUTE:
165        case AKEYCODE_POWER:
166        case AKEYCODE_CAMERA:
167        case AKEYCODE_HEADSETHOOK:
168        case AKEYCODE_MENU:
169        case AKEYCODE_NOTIFICATION:
170        case AKEYCODE_FOCUS:
171        case AKEYCODE_SEARCH:
172        case AKEYCODE_MEDIA_PLAY:
173        case AKEYCODE_MEDIA_PAUSE:
174        case AKEYCODE_MEDIA_PLAY_PAUSE:
175        case AKEYCODE_MEDIA_STOP:
176        case AKEYCODE_MEDIA_NEXT:
177        case AKEYCODE_MEDIA_PREVIOUS:
178        case AKEYCODE_MEDIA_REWIND:
179        case AKEYCODE_MEDIA_RECORD:
180        case AKEYCODE_MEDIA_FAST_FORWARD:
181        case AKEYCODE_MUTE:
182            return true;
183    }
184
185    return false;
186}
187
188bool KeyEvent::hasDefaultAction() const {
189    return hasDefaultAction(getKeyCode());
190}
191
192bool KeyEvent::isSystemKey(int32_t keyCode) {
193    switch (keyCode) {
194        case AKEYCODE_MENU:
195        case AKEYCODE_SOFT_RIGHT:
196        case AKEYCODE_HOME:
197        case AKEYCODE_BACK:
198        case AKEYCODE_CALL:
199        case AKEYCODE_ENDCALL:
200        case AKEYCODE_VOLUME_UP:
201        case AKEYCODE_VOLUME_DOWN:
202        case AKEYCODE_VOLUME_MUTE:
203        case AKEYCODE_MUTE:
204        case AKEYCODE_POWER:
205        case AKEYCODE_HEADSETHOOK:
206        case AKEYCODE_MEDIA_PLAY:
207        case AKEYCODE_MEDIA_PAUSE:
208        case AKEYCODE_MEDIA_PLAY_PAUSE:
209        case AKEYCODE_MEDIA_STOP:
210        case AKEYCODE_MEDIA_NEXT:
211        case AKEYCODE_MEDIA_PREVIOUS:
212        case AKEYCODE_MEDIA_REWIND:
213        case AKEYCODE_MEDIA_RECORD:
214        case AKEYCODE_MEDIA_FAST_FORWARD:
215        case AKEYCODE_CAMERA:
216        case AKEYCODE_FOCUS:
217        case AKEYCODE_SEARCH:
218            return true;
219    }
220
221    return false;
222}
223
224bool KeyEvent::isSystemKey() const {
225    return isSystemKey(getKeyCode());
226}
227
228void KeyEvent::initialize(
229        int32_t deviceId,
230        int32_t source,
231        int32_t action,
232        int32_t flags,
233        int32_t keyCode,
234        int32_t scanCode,
235        int32_t metaState,
236        int32_t repeatCount,
237        nsecs_t downTime,
238        nsecs_t eventTime) {
239    InputEvent::initialize(deviceId, source);
240    mAction = action;
241    mFlags = flags;
242    mKeyCode = keyCode;
243    mScanCode = scanCode;
244    mMetaState = metaState;
245    mRepeatCount = repeatCount;
246    mDownTime = downTime;
247    mEventTime = eventTime;
248}
249
250void KeyEvent::initialize(const KeyEvent& from) {
251    InputEvent::initialize(from);
252    mAction = from.mAction;
253    mFlags = from.mFlags;
254    mKeyCode = from.mKeyCode;
255    mScanCode = from.mScanCode;
256    mMetaState = from.mMetaState;
257    mRepeatCount = from.mRepeatCount;
258    mDownTime = from.mDownTime;
259    mEventTime = from.mEventTime;
260}
261
262
263// --- PointerCoords ---
264
265float PointerCoords::getAxisValue(int32_t axis) const {
266    if (axis < 0 || axis > 63) {
267        return 0;
268    }
269
270    uint64_t axisBit = 1LL << axis;
271    if (!(bits & axisBit)) {
272        return 0;
273    }
274    uint32_t index = __builtin_popcountll(bits & (axisBit - 1LL));
275    return values[index];
276}
277
278status_t PointerCoords::setAxisValue(int32_t axis, float value) {
279    if (axis < 0 || axis > 63) {
280        return NAME_NOT_FOUND;
281    }
282
283    uint64_t axisBit = 1LL << axis;
284    uint32_t index = __builtin_popcountll(bits & (axisBit - 1LL));
285    if (!(bits & axisBit)) {
286        if (value == 0) {
287            return OK; // axes with value 0 do not need to be stored
288        }
289        uint32_t count = __builtin_popcountll(bits);
290        if (count >= MAX_AXES) {
291            tooManyAxes(axis);
292            return NO_MEMORY;
293        }
294        bits |= axisBit;
295        for (uint32_t i = count; i > index; i--) {
296            values[i] = values[i - 1];
297        }
298    }
299    values[index] = value;
300    return OK;
301}
302
303static inline void scaleAxisValue(PointerCoords& c, int axis, float scaleFactor) {
304    float value = c.getAxisValue(axis);
305    if (value != 0) {
306        c.setAxisValue(axis, value * scaleFactor);
307    }
308}
309
310void PointerCoords::scale(float scaleFactor) {
311    // No need to scale pressure or size since they are normalized.
312    // No need to scale orientation since it is meaningless to do so.
313    scaleAxisValue(*this, AMOTION_EVENT_AXIS_X, scaleFactor);
314    scaleAxisValue(*this, AMOTION_EVENT_AXIS_Y, scaleFactor);
315    scaleAxisValue(*this, AMOTION_EVENT_AXIS_TOUCH_MAJOR, scaleFactor);
316    scaleAxisValue(*this, AMOTION_EVENT_AXIS_TOUCH_MINOR, scaleFactor);
317    scaleAxisValue(*this, AMOTION_EVENT_AXIS_TOOL_MAJOR, scaleFactor);
318    scaleAxisValue(*this, AMOTION_EVENT_AXIS_TOOL_MINOR, scaleFactor);
319}
320
321#ifdef HAVE_ANDROID_OS
322status_t PointerCoords::readFromParcel(Parcel* parcel) {
323    bits = parcel->readInt64();
324
325    uint32_t count = __builtin_popcountll(bits);
326    if (count > MAX_AXES) {
327        return BAD_VALUE;
328    }
329
330    for (uint32_t i = 0; i < count; i++) {
331        values[i] = parcel->readInt32();
332    }
333    return OK;
334}
335
336status_t PointerCoords::writeToParcel(Parcel* parcel) const {
337    parcel->writeInt64(bits);
338
339    uint32_t count = __builtin_popcountll(bits);
340    for (uint32_t i = 0; i < count; i++) {
341        parcel->writeInt32(values[i]);
342    }
343    return OK;
344}
345#endif
346
347void PointerCoords::tooManyAxes(int axis) {
348    LOGW("Could not set value for axis %d because the PointerCoords structure is full and "
349            "cannot contain more than %d axis values.", axis, int(MAX_AXES));
350}
351
352bool PointerCoords::operator==(const PointerCoords& other) const {
353    if (bits != other.bits) {
354        return false;
355    }
356    uint32_t count = __builtin_popcountll(bits);
357    for (uint32_t i = 0; i < count; i++) {
358        if (values[i] != other.values[i]) {
359            return false;
360        }
361    }
362    return true;
363}
364
365void PointerCoords::copyFrom(const PointerCoords& other) {
366    bits = other.bits;
367    uint32_t count = __builtin_popcountll(bits);
368    for (uint32_t i = 0; i < count; i++) {
369        values[i] = other.values[i];
370    }
371}
372
373
374// --- PointerProperties ---
375
376bool PointerProperties::operator==(const PointerProperties& other) const {
377    return id == other.id
378            && toolType == other.toolType;
379}
380
381void PointerProperties::copyFrom(const PointerProperties& other) {
382    id = other.id;
383    toolType = other.toolType;
384}
385
386
387// --- MotionEvent ---
388
389void MotionEvent::initialize(
390        int32_t deviceId,
391        int32_t source,
392        int32_t action,
393        int32_t flags,
394        int32_t edgeFlags,
395        int32_t metaState,
396        int32_t buttonState,
397        float xOffset,
398        float yOffset,
399        float xPrecision,
400        float yPrecision,
401        nsecs_t downTime,
402        nsecs_t eventTime,
403        size_t pointerCount,
404        const PointerProperties* pointerProperties,
405        const PointerCoords* pointerCoords) {
406    InputEvent::initialize(deviceId, source);
407    mAction = action;
408    mFlags = flags;
409    mEdgeFlags = edgeFlags;
410    mMetaState = metaState;
411    mButtonState = buttonState;
412    mXOffset = xOffset;
413    mYOffset = yOffset;
414    mXPrecision = xPrecision;
415    mYPrecision = yPrecision;
416    mDownTime = downTime;
417    mPointerProperties.clear();
418    mPointerProperties.appendArray(pointerProperties, pointerCount);
419    mSampleEventTimes.clear();
420    mSamplePointerCoords.clear();
421    addSample(eventTime, pointerCoords);
422}
423
424void MotionEvent::copyFrom(const MotionEvent* other, bool keepHistory) {
425    InputEvent::initialize(other->mDeviceId, other->mSource);
426    mAction = other->mAction;
427    mFlags = other->mFlags;
428    mEdgeFlags = other->mEdgeFlags;
429    mMetaState = other->mMetaState;
430    mButtonState = other->mButtonState;
431    mXOffset = other->mXOffset;
432    mYOffset = other->mYOffset;
433    mXPrecision = other->mXPrecision;
434    mYPrecision = other->mYPrecision;
435    mDownTime = other->mDownTime;
436    mPointerProperties = other->mPointerProperties;
437
438    if (keepHistory) {
439        mSampleEventTimes = other->mSampleEventTimes;
440        mSamplePointerCoords = other->mSamplePointerCoords;
441    } else {
442        mSampleEventTimes.clear();
443        mSampleEventTimes.push(other->getEventTime());
444        mSamplePointerCoords.clear();
445        size_t pointerCount = other->getPointerCount();
446        size_t historySize = other->getHistorySize();
447        mSamplePointerCoords.appendArray(other->mSamplePointerCoords.array()
448                + (historySize * pointerCount), pointerCount);
449    }
450}
451
452void MotionEvent::addSample(
453        int64_t eventTime,
454        const PointerCoords* pointerCoords) {
455    mSampleEventTimes.push(eventTime);
456    mSamplePointerCoords.appendArray(pointerCoords, getPointerCount());
457}
458
459const PointerCoords* MotionEvent::getRawPointerCoords(size_t pointerIndex) const {
460    return &mSamplePointerCoords[getHistorySize() * getPointerCount() + pointerIndex];
461}
462
463float MotionEvent::getRawAxisValue(int32_t axis, size_t pointerIndex) const {
464    return getRawPointerCoords(pointerIndex)->getAxisValue(axis);
465}
466
467float MotionEvent::getAxisValue(int32_t axis, size_t pointerIndex) const {
468    float value = getRawPointerCoords(pointerIndex)->getAxisValue(axis);
469    switch (axis) {
470    case AMOTION_EVENT_AXIS_X:
471        return value + mXOffset;
472    case AMOTION_EVENT_AXIS_Y:
473        return value + mYOffset;
474    }
475    return value;
476}
477
478const PointerCoords* MotionEvent::getHistoricalRawPointerCoords(
479        size_t pointerIndex, size_t historicalIndex) const {
480    return &mSamplePointerCoords[historicalIndex * getPointerCount() + pointerIndex];
481}
482
483float MotionEvent::getHistoricalRawAxisValue(int32_t axis, size_t pointerIndex,
484        size_t historicalIndex) const {
485    return getHistoricalRawPointerCoords(pointerIndex, historicalIndex)->getAxisValue(axis);
486}
487
488float MotionEvent::getHistoricalAxisValue(int32_t axis, size_t pointerIndex,
489        size_t historicalIndex) const {
490    float value = getHistoricalRawPointerCoords(pointerIndex, historicalIndex)->getAxisValue(axis);
491    switch (axis) {
492    case AMOTION_EVENT_AXIS_X:
493        return value + mXOffset;
494    case AMOTION_EVENT_AXIS_Y:
495        return value + mYOffset;
496    }
497    return value;
498}
499
500ssize_t MotionEvent::findPointerIndex(int32_t pointerId) const {
501    size_t pointerCount = mPointerProperties.size();
502    for (size_t i = 0; i < pointerCount; i++) {
503        if (mPointerProperties.itemAt(i).id == pointerId) {
504            return i;
505        }
506    }
507    return -1;
508}
509
510void MotionEvent::offsetLocation(float xOffset, float yOffset) {
511    mXOffset += xOffset;
512    mYOffset += yOffset;
513}
514
515void MotionEvent::scale(float scaleFactor) {
516    mXOffset *= scaleFactor;
517    mYOffset *= scaleFactor;
518    mXPrecision *= scaleFactor;
519    mYPrecision *= scaleFactor;
520
521    size_t numSamples = mSamplePointerCoords.size();
522    for (size_t i = 0; i < numSamples; i++) {
523        mSamplePointerCoords.editItemAt(i).scale(scaleFactor);
524    }
525}
526
527#ifdef HAVE_ANDROID_OS
528static inline float transformAngle(const SkMatrix* matrix, float angleRadians) {
529    // Construct and transform a vector oriented at the specified clockwise angle from vertical.
530    // Coordinate system: down is increasing Y, right is increasing X.
531    SkPoint vector;
532    vector.fX = SkFloatToScalar(sinf(angleRadians));
533    vector.fY = SkFloatToScalar(-cosf(angleRadians));
534    matrix->mapVectors(& vector, 1);
535
536    // Derive the transformed vector's clockwise angle from vertical.
537    float result = atan2f(SkScalarToFloat(vector.fX), SkScalarToFloat(-vector.fY));
538    if (result < - M_PI_2) {
539        result += M_PI;
540    } else if (result > M_PI_2) {
541        result -= M_PI;
542    }
543    return result;
544}
545
546void MotionEvent::transform(const SkMatrix* matrix) {
547    float oldXOffset = mXOffset;
548    float oldYOffset = mYOffset;
549
550    // The tricky part of this implementation is to preserve the value of
551    // rawX and rawY.  So we apply the transformation to the first point
552    // then derive an appropriate new X/Y offset that will preserve rawX and rawY.
553    SkPoint point;
554    float rawX = getRawX(0);
555    float rawY = getRawY(0);
556    matrix->mapXY(SkFloatToScalar(rawX + oldXOffset), SkFloatToScalar(rawY + oldYOffset),
557            & point);
558    float newX = SkScalarToFloat(point.fX);
559    float newY = SkScalarToFloat(point.fY);
560    float newXOffset = newX - rawX;
561    float newYOffset = newY - rawY;
562
563    mXOffset = newXOffset;
564    mYOffset = newYOffset;
565
566    // Apply the transformation to all samples.
567    size_t numSamples = mSamplePointerCoords.size();
568    for (size_t i = 0; i < numSamples; i++) {
569        PointerCoords& c = mSamplePointerCoords.editItemAt(i);
570        float x = c.getAxisValue(AMOTION_EVENT_AXIS_X) + oldXOffset;
571        float y = c.getAxisValue(AMOTION_EVENT_AXIS_Y) + oldYOffset;
572        matrix->mapXY(SkFloatToScalar(x), SkFloatToScalar(y), &point);
573        c.setAxisValue(AMOTION_EVENT_AXIS_X, SkScalarToFloat(point.fX) - newXOffset);
574        c.setAxisValue(AMOTION_EVENT_AXIS_Y, SkScalarToFloat(point.fY) - newYOffset);
575
576        float orientation = c.getAxisValue(AMOTION_EVENT_AXIS_ORIENTATION);
577        c.setAxisValue(AMOTION_EVENT_AXIS_ORIENTATION, transformAngle(matrix, orientation));
578    }
579}
580
581status_t MotionEvent::readFromParcel(Parcel* parcel) {
582    size_t pointerCount = parcel->readInt32();
583    size_t sampleCount = parcel->readInt32();
584    if (pointerCount == 0 || pointerCount > MAX_POINTERS || sampleCount == 0) {
585        return BAD_VALUE;
586    }
587
588    mDeviceId = parcel->readInt32();
589    mSource = parcel->readInt32();
590    mAction = parcel->readInt32();
591    mFlags = parcel->readInt32();
592    mEdgeFlags = parcel->readInt32();
593    mMetaState = parcel->readInt32();
594    mButtonState = parcel->readInt32();
595    mXOffset = parcel->readFloat();
596    mYOffset = parcel->readFloat();
597    mXPrecision = parcel->readFloat();
598    mYPrecision = parcel->readFloat();
599    mDownTime = parcel->readInt64();
600
601    mPointerProperties.clear();
602    mPointerProperties.setCapacity(pointerCount);
603    mSampleEventTimes.clear();
604    mSampleEventTimes.setCapacity(sampleCount);
605    mSamplePointerCoords.clear();
606    mSamplePointerCoords.setCapacity(sampleCount * pointerCount);
607
608    for (size_t i = 0; i < pointerCount; i++) {
609        mPointerProperties.push();
610        PointerProperties& properties = mPointerProperties.editTop();
611        properties.id = parcel->readInt32();
612        properties.toolType = parcel->readInt32();
613    }
614
615    while (sampleCount-- > 0) {
616        mSampleEventTimes.push(parcel->readInt64());
617        for (size_t i = 0; i < pointerCount; i++) {
618            mSamplePointerCoords.push();
619            status_t status = mSamplePointerCoords.editTop().readFromParcel(parcel);
620            if (status) {
621                return status;
622            }
623        }
624    }
625    return OK;
626}
627
628status_t MotionEvent::writeToParcel(Parcel* parcel) const {
629    size_t pointerCount = mPointerProperties.size();
630    size_t sampleCount = mSampleEventTimes.size();
631
632    parcel->writeInt32(pointerCount);
633    parcel->writeInt32(sampleCount);
634
635    parcel->writeInt32(mDeviceId);
636    parcel->writeInt32(mSource);
637    parcel->writeInt32(mAction);
638    parcel->writeInt32(mFlags);
639    parcel->writeInt32(mEdgeFlags);
640    parcel->writeInt32(mMetaState);
641    parcel->writeInt32(mButtonState);
642    parcel->writeFloat(mXOffset);
643    parcel->writeFloat(mYOffset);
644    parcel->writeFloat(mXPrecision);
645    parcel->writeFloat(mYPrecision);
646    parcel->writeInt64(mDownTime);
647
648    for (size_t i = 0; i < pointerCount; i++) {
649        const PointerProperties& properties = mPointerProperties.itemAt(i);
650        parcel->writeInt32(properties.id);
651        parcel->writeInt32(properties.toolType);
652    }
653
654    const PointerCoords* pc = mSamplePointerCoords.array();
655    for (size_t h = 0; h < sampleCount; h++) {
656        parcel->writeInt64(mSampleEventTimes.itemAt(h));
657        for (size_t i = 0; i < pointerCount; i++) {
658            status_t status = (pc++)->writeToParcel(parcel);
659            if (status) {
660                return status;
661            }
662        }
663    }
664    return OK;
665}
666#endif
667
668bool MotionEvent::isTouchEvent(int32_t source, int32_t action) {
669    if (source & AINPUT_SOURCE_CLASS_POINTER) {
670        // Specifically excludes HOVER_MOVE and SCROLL.
671        switch (action & AMOTION_EVENT_ACTION_MASK) {
672        case AMOTION_EVENT_ACTION_DOWN:
673        case AMOTION_EVENT_ACTION_MOVE:
674        case AMOTION_EVENT_ACTION_UP:
675        case AMOTION_EVENT_ACTION_POINTER_DOWN:
676        case AMOTION_EVENT_ACTION_POINTER_UP:
677        case AMOTION_EVENT_ACTION_CANCEL:
678        case AMOTION_EVENT_ACTION_OUTSIDE:
679            return true;
680        }
681    }
682    return false;
683}
684
685
686// --- VelocityTracker ---
687
688const uint32_t VelocityTracker::DEFAULT_DEGREE;
689const nsecs_t VelocityTracker::DEFAULT_HORIZON;
690const uint32_t VelocityTracker::HISTORY_SIZE;
691
692static inline float vectorDot(const float* a, const float* b, uint32_t m) {
693    float r = 0;
694    while (m--) {
695        r += *(a++) * *(b++);
696    }
697    return r;
698}
699
700static inline float vectorNorm(const float* a, uint32_t m) {
701    float r = 0;
702    while (m--) {
703        float t = *(a++);
704        r += t * t;
705    }
706    return sqrtf(r);
707}
708
709#if DEBUG_LEAST_SQUARES || DEBUG_VELOCITY
710static String8 vectorToString(const float* a, uint32_t m) {
711    String8 str;
712    str.append("[");
713    while (m--) {
714        str.appendFormat(" %f", *(a++));
715        if (m) {
716            str.append(",");
717        }
718    }
719    str.append(" ]");
720    return str;
721}
722
723static String8 matrixToString(const float* a, uint32_t m, uint32_t n, bool rowMajor) {
724    String8 str;
725    str.append("[");
726    for (size_t i = 0; i < m; i++) {
727        if (i) {
728            str.append(",");
729        }
730        str.append(" [");
731        for (size_t j = 0; j < n; j++) {
732            if (j) {
733                str.append(",");
734            }
735            str.appendFormat(" %f", a[rowMajor ? i * n + j : j * m + i]);
736        }
737        str.append(" ]");
738    }
739    str.append(" ]");
740    return str;
741}
742#endif
743
744VelocityTracker::VelocityTracker() {
745    clear();
746}
747
748void VelocityTracker::clear() {
749    mIndex = 0;
750    mMovements[0].idBits.clear();
751    mActivePointerId = -1;
752}
753
754void VelocityTracker::clearPointers(BitSet32 idBits) {
755    BitSet32 remainingIdBits(mMovements[mIndex].idBits.value & ~idBits.value);
756    mMovements[mIndex].idBits = remainingIdBits;
757
758    if (mActivePointerId >= 0 && idBits.hasBit(mActivePointerId)) {
759        mActivePointerId = !remainingIdBits.isEmpty() ? remainingIdBits.firstMarkedBit() : -1;
760    }
761}
762
763void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions) {
764    if (++mIndex == HISTORY_SIZE) {
765        mIndex = 0;
766    }
767
768    while (idBits.count() > MAX_POINTERS) {
769        idBits.clearLastMarkedBit();
770    }
771
772    Movement& movement = mMovements[mIndex];
773    movement.eventTime = eventTime;
774    movement.idBits = idBits;
775    uint32_t count = idBits.count();
776    for (uint32_t i = 0; i < count; i++) {
777        movement.positions[i] = positions[i];
778    }
779
780    if (mActivePointerId < 0 || !idBits.hasBit(mActivePointerId)) {
781        mActivePointerId = count != 0 ? idBits.firstMarkedBit() : -1;
782    }
783
784#if DEBUG_VELOCITY
785    LOGD("VelocityTracker: addMovement eventTime=%lld, idBits=0x%08x, activePointerId=%d",
786            eventTime, idBits.value, mActivePointerId);
787    for (BitSet32 iterBits(idBits); !iterBits.isEmpty(); ) {
788        uint32_t id = iterBits.firstMarkedBit();
789        uint32_t index = idBits.getIndexOfBit(id);
790        iterBits.clearBit(id);
791        Estimator estimator;
792        getEstimator(id, DEFAULT_DEGREE, DEFAULT_HORIZON, &estimator);
793        LOGD("  %d: position (%0.3f, %0.3f), "
794                "estimator (degree=%d, xCoeff=%s, yCoeff=%s, confidence=%f)",
795                id, positions[index].x, positions[index].y,
796                int(estimator.degree),
797                vectorToString(estimator.xCoeff, estimator.degree).string(),
798                vectorToString(estimator.yCoeff, estimator.degree).string(),
799                estimator.confidence);
800    }
801#endif
802}
803
804void VelocityTracker::addMovement(const MotionEvent* event) {
805    int32_t actionMasked = event->getActionMasked();
806
807    switch (actionMasked) {
808    case AMOTION_EVENT_ACTION_DOWN:
809    case AMOTION_EVENT_ACTION_HOVER_ENTER:
810        // Clear all pointers on down before adding the new movement.
811        clear();
812        break;
813    case AMOTION_EVENT_ACTION_POINTER_DOWN: {
814        // Start a new movement trace for a pointer that just went down.
815        // We do this on down instead of on up because the client may want to query the
816        // final velocity for a pointer that just went up.
817        BitSet32 downIdBits;
818        downIdBits.markBit(event->getPointerId(event->getActionIndex()));
819        clearPointers(downIdBits);
820        break;
821    }
822    case AMOTION_EVENT_ACTION_MOVE:
823    case AMOTION_EVENT_ACTION_HOVER_MOVE:
824        break;
825    default:
826        // Ignore all other actions because they do not convey any new information about
827        // pointer movement.  We also want to preserve the last known velocity of the pointers.
828        // Note that ACTION_UP and ACTION_POINTER_UP always report the last known position
829        // of the pointers that went up.  ACTION_POINTER_UP does include the new position of
830        // pointers that remained down but we will also receive an ACTION_MOVE with this
831        // information if any of them actually moved.  Since we don't know how many pointers
832        // will be going up at once it makes sense to just wait for the following ACTION_MOVE
833        // before adding the movement.
834        return;
835    }
836
837    size_t pointerCount = event->getPointerCount();
838    if (pointerCount > MAX_POINTERS) {
839        pointerCount = MAX_POINTERS;
840    }
841
842    BitSet32 idBits;
843    for (size_t i = 0; i < pointerCount; i++) {
844        idBits.markBit(event->getPointerId(i));
845    }
846
847    nsecs_t eventTime;
848    Position positions[pointerCount];
849
850    size_t historySize = event->getHistorySize();
851    for (size_t h = 0; h < historySize; h++) {
852        eventTime = event->getHistoricalEventTime(h);
853        for (size_t i = 0; i < pointerCount; i++) {
854            positions[i].x = event->getHistoricalX(i, h);
855            positions[i].y = event->getHistoricalY(i, h);
856        }
857        addMovement(eventTime, idBits, positions);
858    }
859
860    eventTime = event->getEventTime();
861    for (size_t i = 0; i < pointerCount; i++) {
862        positions[i].x = event->getX(i);
863        positions[i].y = event->getY(i);
864    }
865    addMovement(eventTime, idBits, positions);
866}
867
868/**
869 * Solves a linear least squares problem to obtain a N degree polynomial that fits
870 * the specified input data as nearly as possible.
871 *
872 * Returns true if a solution is found, false otherwise.
873 *
874 * The input consists of two vectors of data points X and Y with indices 0..m-1.
875 * The output is a vector B with indices 0..n-1 that describes a polynomial
876 * that fits the data, such the sum of abs(Y[i] - (B[0] + B[1] X[i] + B[2] X[i]^2 ... B[n] X[i]^n))
877 * for all i between 0 and m-1 is minimized.
878 *
879 * That is to say, the function that generated the input data can be approximated
880 * by y(x) ~= B[0] + B[1] x + B[2] x^2 + ... + B[n] x^n.
881 *
882 * The coefficient of determination (R^2) is also returned to describe the goodness
883 * of fit of the model for the given data.  It is a value between 0 and 1, where 1
884 * indicates perfect correspondence.
885 *
886 * This function first expands the X vector to a m by n matrix A such that
887 * A[i][0] = 1, A[i][1] = X[i], A[i][2] = X[i]^2, ..., A[i][n] = X[i]^n.
888 *
889 * Then it calculates the QR decomposition of A yielding an m by m orthonormal matrix Q
890 * and an m by n upper triangular matrix R.  Because R is upper triangular (lower
891 * part is all zeroes), we can simplify the decomposition into an m by n matrix
892 * Q1 and a n by n matrix R1 such that A = Q1 R1.
893 *
894 * Finally we solve the system of linear equations given by R1 B = (Qtranspose Y)
895 * to find B.
896 *
897 * For efficiency, we lay out A and Q column-wise in memory because we frequently
898 * operate on the column vectors.  Conversely, we lay out R row-wise.
899 *
900 * http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares
901 * http://en.wikipedia.org/wiki/Gram-Schmidt
902 */
903static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32_t n,
904        float* outB, float* outDet) {
905#if DEBUG_LEAST_SQUARES
906    LOGD("solveLeastSquares: m=%d, n=%d, x=%s, y=%s", int(m), int(n),
907            vectorToString(x, m).string(), vectorToString(y, m).string());
908#endif
909
910    // Expand the X vector to a matrix A.
911    float a[n][m]; // column-major order
912    for (uint32_t h = 0; h < m; h++) {
913        a[0][h] = 1;
914        for (uint32_t i = 1; i < n; i++) {
915            a[i][h] = a[i - 1][h] * x[h];
916        }
917    }
918#if DEBUG_LEAST_SQUARES
919    LOGD("  - a=%s", matrixToString(&a[0][0], m, n, false /*rowMajor*/).string());
920#endif
921
922    // Apply the Gram-Schmidt process to A to obtain its QR decomposition.
923    float q[n][m]; // orthonormal basis, column-major order
924    float r[n][n]; // upper triangular matrix, row-major order
925    for (uint32_t j = 0; j < n; j++) {
926        for (uint32_t h = 0; h < m; h++) {
927            q[j][h] = a[j][h];
928        }
929        for (uint32_t i = 0; i < j; i++) {
930            float dot = vectorDot(&q[j][0], &q[i][0], m);
931            for (uint32_t h = 0; h < m; h++) {
932                q[j][h] -= dot * q[i][h];
933            }
934        }
935
936        float norm = vectorNorm(&q[j][0], m);
937        if (norm < 0.000001f) {
938            // vectors are linearly dependent or zero so no solution
939#if DEBUG_LEAST_SQUARES
940            LOGD("  - no solution, norm=%f", norm);
941#endif
942            return false;
943        }
944
945        float invNorm = 1.0f / norm;
946        for (uint32_t h = 0; h < m; h++) {
947            q[j][h] *= invNorm;
948        }
949        for (uint32_t i = 0; i < n; i++) {
950            r[j][i] = i < j ? 0 : vectorDot(&q[j][0], &a[i][0], m);
951        }
952    }
953#if DEBUG_LEAST_SQUARES
954    LOGD("  - q=%s", matrixToString(&q[0][0], m, n, false /*rowMajor*/).string());
955    LOGD("  - r=%s", matrixToString(&r[0][0], n, n, true /*rowMajor*/).string());
956
957    // calculate QR, if we factored A correctly then QR should equal A
958    float qr[n][m];
959    for (uint32_t h = 0; h < m; h++) {
960        for (uint32_t i = 0; i < n; i++) {
961            qr[i][h] = 0;
962            for (uint32_t j = 0; j < n; j++) {
963                qr[i][h] += q[j][h] * r[j][i];
964            }
965        }
966    }
967    LOGD("  - qr=%s", matrixToString(&qr[0][0], m, n, false /*rowMajor*/).string());
968#endif
969
970    // Solve R B = Qt Y to find B.  This is easy because R is upper triangular.
971    // We just work from bottom-right to top-left calculating B's coefficients.
972    for (uint32_t i = n; i-- != 0; ) {
973        outB[i] = vectorDot(&q[i][0], y, m);
974        for (uint32_t j = n - 1; j > i; j--) {
975            outB[i] -= r[i][j] * outB[j];
976        }
977        outB[i] /= r[i][i];
978    }
979#if DEBUG_LEAST_SQUARES
980    LOGD("  - b=%s", vectorToString(outB, n).string());
981#endif
982
983    // Calculate the coefficient of determination as 1 - (SSerr / SStot) where
984    // SSerr is the residual sum of squares (squared variance of the error),
985    // and SStot is the total sum of squares (squared variance of the data).
986    float ymean = 0;
987    for (uint32_t h = 0; h < m; h++) {
988        ymean += y[h];
989    }
990    ymean /= m;
991
992    float sserr = 0;
993    float sstot = 0;
994    for (uint32_t h = 0; h < m; h++) {
995        float err = y[h] - outB[0];
996        float term = 1;
997        for (uint32_t i = 1; i < n; i++) {
998            term *= x[h];
999            err -= term * outB[i];
1000        }
1001        sserr += err * err;
1002        float var = y[h] - ymean;
1003        sstot += var * var;
1004    }
1005    *outDet = sstot > 0.000001f ? 1.0f - (sserr / sstot) : 1;
1006#if DEBUG_LEAST_SQUARES
1007    LOGD("  - sserr=%f", sserr);
1008    LOGD("  - sstot=%f", sstot);
1009    LOGD("  - det=%f", *outDet);
1010#endif
1011    return true;
1012}
1013
1014bool VelocityTracker::getVelocity(uint32_t id, float* outVx, float* outVy) const {
1015    Estimator estimator;
1016    if (getEstimator(id, DEFAULT_DEGREE, DEFAULT_HORIZON, &estimator)) {
1017        if (estimator.degree >= 1) {
1018            *outVx = estimator.xCoeff[1];
1019            *outVy = estimator.yCoeff[1];
1020            return true;
1021        }
1022    }
1023    *outVx = 0;
1024    *outVy = 0;
1025    return false;
1026}
1027
1028bool VelocityTracker::getEstimator(uint32_t id, uint32_t degree, nsecs_t horizon,
1029        Estimator* outEstimator) const {
1030    outEstimator->clear();
1031
1032    // Iterate over movement samples in reverse time order and collect samples.
1033    float x[HISTORY_SIZE];
1034    float y[HISTORY_SIZE];
1035    float time[HISTORY_SIZE];
1036    uint32_t m = 0;
1037    uint32_t index = mIndex;
1038    const Movement& newestMovement = mMovements[mIndex];
1039    do {
1040        const Movement& movement = mMovements[index];
1041        if (!movement.idBits.hasBit(id)) {
1042            break;
1043        }
1044
1045        nsecs_t age = newestMovement.eventTime - movement.eventTime;
1046        if (age > horizon) {
1047            break;
1048        }
1049
1050        const Position& position = movement.getPosition(id);
1051        x[m] = position.x;
1052        y[m] = position.y;
1053        time[m] = -age * 0.000000001f;
1054        index = (index == 0 ? HISTORY_SIZE : index) - 1;
1055    } while (++m < HISTORY_SIZE);
1056
1057    if (m == 0) {
1058        return false; // no data
1059    }
1060
1061    // Calculate a least squares polynomial fit.
1062    if (degree > Estimator::MAX_DEGREE) {
1063        degree = Estimator::MAX_DEGREE;
1064    }
1065    if (degree > m - 1) {
1066        degree = m - 1;
1067    }
1068    if (degree >= 1) {
1069        float xdet, ydet;
1070        uint32_t n = degree + 1;
1071        if (solveLeastSquares(time, x, m, n, outEstimator->xCoeff, &xdet)
1072                && solveLeastSquares(time, y, m, n, outEstimator->yCoeff, &ydet)) {
1073            outEstimator->degree = degree;
1074            outEstimator->confidence = xdet * ydet;
1075#if DEBUG_LEAST_SQUARES
1076            LOGD("estimate: degree=%d, xCoeff=%s, yCoeff=%s, confidence=%f",
1077                    int(outEstimator->degree),
1078                    vectorToString(outEstimator->xCoeff, n).string(),
1079                    vectorToString(outEstimator->yCoeff, n).string(),
1080                    outEstimator->confidence);
1081#endif
1082            return true;
1083        }
1084    }
1085
1086    // No velocity data available for this pointer, but we do have its current position.
1087    outEstimator->xCoeff[0] = x[0];
1088    outEstimator->yCoeff[0] = y[0];
1089    outEstimator->degree = 0;
1090    outEstimator->confidence = 1;
1091    return true;
1092}
1093
1094
1095// --- VelocityControl ---
1096
1097const nsecs_t VelocityControl::STOP_TIME;
1098
1099VelocityControl::VelocityControl() {
1100    reset();
1101}
1102
1103void VelocityControl::setParameters(const VelocityControlParameters& parameters) {
1104    mParameters = parameters;
1105    reset();
1106}
1107
1108void VelocityControl::reset() {
1109    mLastMovementTime = LLONG_MIN;
1110    mRawPosition.x = 0;
1111    mRawPosition.y = 0;
1112    mVelocityTracker.clear();
1113}
1114
1115void VelocityControl::move(nsecs_t eventTime, float* deltaX, float* deltaY) {
1116    if ((deltaX && *deltaX) || (deltaY && *deltaY)) {
1117        if (eventTime >= mLastMovementTime + STOP_TIME) {
1118#if DEBUG_ACCELERATION
1119            LOGD("VelocityControl: stopped, last movement was %0.3fms ago",
1120                    (eventTime - mLastMovementTime) * 0.000001f);
1121#endif
1122            reset();
1123        }
1124
1125        mLastMovementTime = eventTime;
1126        if (deltaX) {
1127            mRawPosition.x += *deltaX;
1128        }
1129        if (deltaY) {
1130            mRawPosition.y += *deltaY;
1131        }
1132        mVelocityTracker.addMovement(eventTime, BitSet32(BitSet32::valueForBit(0)), &mRawPosition);
1133
1134        float vx, vy;
1135        float scale = mParameters.scale;
1136        if (mVelocityTracker.getVelocity(0, &vx, &vy)) {
1137            float speed = hypotf(vx, vy) * scale;
1138            if (speed >= mParameters.highThreshold) {
1139                // Apply full acceleration above the high speed threshold.
1140                scale *= mParameters.acceleration;
1141            } else if (speed > mParameters.lowThreshold) {
1142                // Linearly interpolate the acceleration to apply between the low and high
1143                // speed thresholds.
1144                scale *= 1 + (speed - mParameters.lowThreshold)
1145                        / (mParameters.highThreshold - mParameters.lowThreshold)
1146                        * (mParameters.acceleration - 1);
1147            }
1148
1149#if DEBUG_ACCELERATION
1150            LOGD("VelocityControl(%0.3f, %0.3f, %0.3f, %0.3f): "
1151                    "vx=%0.3f, vy=%0.3f, speed=%0.3f, accel=%0.3f",
1152                    mParameters.scale, mParameters.lowThreshold, mParameters.highThreshold,
1153                    mParameters.acceleration,
1154                    vx, vy, speed, scale / mParameters.scale);
1155#endif
1156        } else {
1157#if DEBUG_ACCELERATION
1158            LOGD("VelocityControl(%0.3f, %0.3f, %0.3f, %0.3f): unknown velocity",
1159                    mParameters.scale, mParameters.lowThreshold, mParameters.highThreshold,
1160                    mParameters.acceleration);
1161#endif
1162        }
1163
1164        if (deltaX) {
1165            *deltaX *= scale;
1166        }
1167        if (deltaY) {
1168            *deltaY *= scale;
1169        }
1170    }
1171}
1172
1173
1174// --- InputDeviceInfo ---
1175
1176InputDeviceInfo::InputDeviceInfo() {
1177    initialize(-1, String8("uninitialized device info"));
1178}
1179
1180InputDeviceInfo::InputDeviceInfo(const InputDeviceInfo& other) :
1181        mId(other.mId), mName(other.mName), mSources(other.mSources),
1182        mKeyboardType(other.mKeyboardType),
1183        mMotionRanges(other.mMotionRanges) {
1184}
1185
1186InputDeviceInfo::~InputDeviceInfo() {
1187}
1188
1189void InputDeviceInfo::initialize(int32_t id, const String8& name) {
1190    mId = id;
1191    mName = name;
1192    mSources = 0;
1193    mKeyboardType = AINPUT_KEYBOARD_TYPE_NONE;
1194    mMotionRanges.clear();
1195}
1196
1197const InputDeviceInfo::MotionRange* InputDeviceInfo::getMotionRange(
1198        int32_t axis, uint32_t source) const {
1199    size_t numRanges = mMotionRanges.size();
1200    for (size_t i = 0; i < numRanges; i++) {
1201        const MotionRange& range = mMotionRanges.itemAt(i);
1202        if (range.axis == axis && range.source == source) {
1203            return &range;
1204        }
1205    }
1206    return NULL;
1207}
1208
1209void InputDeviceInfo::addSource(uint32_t source) {
1210    mSources |= source;
1211}
1212
1213void InputDeviceInfo::addMotionRange(int32_t axis, uint32_t source, float min, float max,
1214        float flat, float fuzz) {
1215    MotionRange range = { axis, source, min, max, flat, fuzz };
1216    mMotionRanges.add(range);
1217}
1218
1219void InputDeviceInfo::addMotionRange(const MotionRange& range) {
1220    mMotionRanges.add(range);
1221}
1222
1223} // namespace android
1224