ClockEstimator.h revision aa8b569eb652c22821b93a6e543449a52ad21158 
1bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant/*
2bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant**
3bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** Copyright 2014, The Android Open Source Project
4bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant**
5bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** Licensed under the Apache License, Version 2.0 (the "License");
6bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** you may not use this file except in compliance with the License.
7bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** You may obtain a copy of the License at
8bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant**
9bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant**     http://www.apache.org/licenses/LICENSE-2.0
10bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant**
11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** Unless required by applicable law or agreed to in writing, software
12bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** distributed under the License is distributed on an "AS IS" BASIS,
13bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** See the License for the specific language governing permissions and
15bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant** limitations under the License.
16bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant*/
17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#ifndef CLOCK_ESTIMATOR_H_
19bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
20bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#define CLOCK_ESTIMATOR_H_
21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
22bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
23bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <utils/RefBase.h>
24bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <utils/Vector.h>
25bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
26bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantnamespace android {
27bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// ---------------------------------------------------------------------------
28bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
29bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantstruct ClockEstimator : RefBase {
30bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant    virtual double estimate(double x, double y) = 0;
31bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant    virtual void reset() = 0;
32bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant};
33bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant
34struct WindowedLinearFitEstimator : ClockEstimator {
35    struct LinearFit {
36        /**
37         * Fit y = a * x + b, where each input has a weight
38         */
39        double mX;  // sum(w_i * x_i)
40        double mXX; // sum(w_i * x_i^2)
41        double mY;  // sum(w_i * y_i)
42        double mYY; // sum(w_i * y_i^2)
43        double mXY; // sum(w_i * x_i * y_i)
44        double mW;  // sum(w_i)
45
46        LinearFit();
47        void reset();
48        void combine(const LinearFit &lf);
49        void add(double x, double y, double w);
50        void scale(double w);
51        double interpolate(double x);
52        double size() const;
53
54        DISALLOW_EVIL_CONSTRUCTORS(LinearFit);
55    };
56
57    /**
58     * Estimator for f(x) = y' where input y' is noisy, but
59     * theoretically linear:
60     *
61     *      y' =~ y = a * x + b
62     *
63     * It uses linear fit regression over a tapering rolling window
64     * to get an estimate for y (from the current and past inputs
65     * (x, y')).
66     *
67     *     ____________
68     *    /|          |\
69     *   / |          | \
70     *  /  |          |  \   <--- new data (x, y')
71     * /   |   main   |   \
72     * <--><----------><-->
73     * tail            head
74     *
75     * weight is 1 under the main window, tapers exponentially by
76     * the factors given in the head and the tail.
77     *
78     * Assuming that x and y' are monotonic, that x is somewhat
79     * evenly sampled, and that a =~ 1, the estimated y is also
80     * going to be monotonic.
81     */
82    WindowedLinearFitEstimator(
83            size_t headLength = 5, double headFactor = 0.5,
84            size_t mainLength = 0, double tailFactor = 0.99);
85
86    virtual void reset();
87
88    // add a new sample (x -> y') and return an estimated value for the true y
89    virtual double estimate(double x, double y);
90
91private:
92    Vector<double> mXHistory; // circular buffer
93    Vector<double> mYHistory; // circular buffer
94    LinearFit mHead;
95    LinearFit mMain;
96    LinearFit mTail;
97    double mHeadFactorInv;
98    double mTailFactor;
99    double mFirstWeight;
100    size_t mHistoryLength;
101    size_t mHeadLength;
102    size_t mNumSamples;
103    size_t mSampleIx;
104
105    DISALLOW_EVIL_CONSTRUCTORS(WindowedLinearFitEstimator);
106};
107
108}; // namespace android
109
110#endif
111