VideoFrameScheduler.cpp revision c851b5de495169d7e9528644c2592746021bd968 
1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17//#define LOG_NDEBUG 0
18#define LOG_TAG "VideoFrameScheduler"
19#include <utils/Log.h>
20#define ATRACE_TAG ATRACE_TAG_VIDEO
21#include <utils/Trace.h>
22
23#include <sys/time.h>
24
25#include <binder/IServiceManager.h>
26#include <gui/ISurfaceComposer.h>
27#include <ui/DisplayStatInfo.h>
28
29#include <media/stagefright/foundation/ADebug.h>
30
31#include "VideoFrameScheduler.h"
32
33namespace android {
34
35static const nsecs_t kNanosIn1s = 1000000000;
36
37template<class T>
38inline static const T divRound(const T &nom, const T &den) {
39    if ((nom >= 0) ^ (den >= 0)) {
40        return (nom - den / 2) / den;
41    } else {
42        return (nom + den / 2) / den;
43    }
44}
45
46template<class T>
47inline static T abs(const T &a) {
48    return a < 0 ? -a : a;
49}
50
51template<class T>
52inline static const T &min(const T &a, const T &b) {
53    return a < b ? a : b;
54}
55
56template<class T>
57inline static const T &max(const T &a, const T &b) {
58    return a > b ? a : b;
59}
60
61template<class T>
62inline static T periodicError(const T &val, const T &period) {
63    T err = abs(val) % period;
64    return (err < (period / 2)) ? err : (period - err);
65}
66
67template<class T>
68static int compare(const T *lhs, const T *rhs) {
69    if (*lhs < *rhs) {
70        return -1;
71    } else if (*lhs > *rhs) {
72        return 1;
73    } else {
74        return 0;
75    }
76}
77
78/* ======================================================================= */
79/*                                   PLL                                   */
80/* ======================================================================= */
81
82static const size_t kMinSamplesToStartPrime = 3;
83static const size_t kMinSamplesToStopPrime = VideoFrameScheduler::kHistorySize;
84static const size_t kMinSamplesToEstimatePeriod = 3;
85static const size_t kMaxSamplesToEstimatePeriod = VideoFrameScheduler::kHistorySize;
86
87static const size_t kPrecision = 12;
88static const size_t kErrorThreshold = (1 << (kPrecision * 2)) / 10;
89static const int64_t kMultiplesThresholdDiv = 4;            // 25%
90static const int64_t kReFitThresholdDiv = 100;              // 1%
91static const nsecs_t kMaxAllowedFrameSkip = kNanosIn1s;     // 1 sec
92static const nsecs_t kMinPeriod = kNanosIn1s / 120;         // 120Hz
93static const nsecs_t kRefitRefreshPeriod = 10 * kNanosIn1s; // 10 sec
94
95VideoFrameScheduler::PLL::PLL()
96    : mPeriod(-1),
97      mPhase(0),
98      mPrimed(false),
99      mSamplesUsedForPriming(0),
100      mLastTime(-1),
101      mNumSamples(0) {
102}
103
104void VideoFrameScheduler::PLL::reset(float fps) {
105    //test();
106
107    mSamplesUsedForPriming = 0;
108    mLastTime = -1;
109
110    // set up or reset video PLL
111    if (fps <= 0.f) {
112        mPeriod = -1;
113        mPrimed = false;
114    } else {
115        ALOGV("reset at %.1f fps", fps);
116        mPeriod = (nsecs_t)(1e9 / fps + 0.5);
117        mPrimed = true;
118    }
119
120    restart();
121}
122
123// reset PLL but keep previous period estimate
124void VideoFrameScheduler::PLL::restart() {
125    mNumSamples = 0;
126    mPhase = -1;
127}
128
129#if 0
130
131void VideoFrameScheduler::PLL::test() {
132    nsecs_t period = kNanosIn1s / 60;
133    mTimes[0] = 0;
134    mTimes[1] = period;
135    mTimes[2] = period * 3;
136    mTimes[3] = period * 4;
137    mTimes[4] = period * 7;
138    mTimes[5] = period * 8;
139    mTimes[6] = period * 10;
140    mTimes[7] = period * 12;
141    mNumSamples = 8;
142    int64_t a, b, err;
143    fit(0, period * 12 / 7, 8, &a, &b, &err);
144    // a = 0.8(5)+
145    // b = -0.14097(2)+
146    // err = 0.2750578(703)+
147    ALOGD("a=%lld (%.6f), b=%lld (%.6f), err=%lld (%.6f)",
148            (long long)a, (a / (float)(1 << kPrecision)),
149            (long long)b, (b / (float)(1 << kPrecision)),
150            (long long)err, (err / (float)(1 << (kPrecision * 2))));
151}
152
153#endif
154
155void VideoFrameScheduler::PLL::fit(
156        nsecs_t phase, nsecs_t period, size_t numSamplesToUse,
157        int64_t *a, int64_t *b, int64_t *err) {
158    if (numSamplesToUse > mNumSamples) {
159        numSamplesToUse = mNumSamples;
160    }
161
162    int64_t sumX = 0;
163    int64_t sumXX = 0;
164    int64_t sumXY = 0;
165    int64_t sumYY = 0;
166    int64_t sumY = 0;
167
168    int64_t x = 0; // x usually is in [0..numSamplesToUse)
169    nsecs_t lastTime;
170    for (size_t i = 0; i < numSamplesToUse; i++) {
171        size_t ix = (mNumSamples - numSamplesToUse + i) % kHistorySize;
172        nsecs_t time = mTimes[ix];
173        if (i > 0) {
174            x += divRound(time - lastTime, period);
175        }
176        // y is usually in [-numSamplesToUse..numSamplesToUse+kRefitRefreshPeriod/kMinPeriod) << kPrecision
177        //   ideally in [0..numSamplesToUse), but shifted by -numSamplesToUse during
178        //   priming, and possibly shifted by up to kRefitRefreshPeriod/kMinPeriod
179        //   while we are not refitting.
180        int64_t y = divRound(time - phase, period >> kPrecision);
181        sumX += x;
182        sumY += y;
183        sumXX += x * x;
184        sumXY += x * y;
185        sumYY += y * y;
186        lastTime = time;
187    }
188
189    int64_t div   = numSamplesToUse * sumXX - sumX * sumX;
190    int64_t a_nom = numSamplesToUse * sumXY - sumX * sumY;
191    int64_t b_nom = sumXX * sumY            - sumX * sumXY;
192    *a = divRound(a_nom, div);
193    *b = divRound(b_nom, div);
194    // don't use a and b directly as the rounding error is significant
195    *err = sumYY - divRound(a_nom * sumXY + b_nom * sumY, div);
196    ALOGV("fitting[%zu] a=%lld (%.6f), b=%lld (%.6f), err=%lld (%.6f)",
197            numSamplesToUse,
198            (long long)*a,   (*a / (float)(1 << kPrecision)),
199            (long long)*b,   (*b / (float)(1 << kPrecision)),
200            (long long)*err, (*err / (float)(1 << (kPrecision * 2))));
201}
202
203void VideoFrameScheduler::PLL::prime(size_t numSamplesToUse) {
204    if (numSamplesToUse > mNumSamples) {
205        numSamplesToUse = mNumSamples;
206    }
207    CHECK(numSamplesToUse >= 3);  // must have at least 3 samples
208
209    // estimate video framerate from deltas between timestamps, and
210    // 2nd order deltas
211    Vector<nsecs_t> deltas;
212    nsecs_t lastTime, firstTime;
213    for (size_t i = 0; i < numSamplesToUse; ++i) {
214        size_t index = (mNumSamples - numSamplesToUse + i) % kHistorySize;
215        nsecs_t time = mTimes[index];
216        if (i > 0) {
217            if (time - lastTime > kMinPeriod) {
218                //ALOGV("delta: %lld", (long long)(time - lastTime));
219                deltas.push(time - lastTime);
220            }
221        } else {
222            firstTime = time;
223        }
224        lastTime = time;
225    }
226    deltas.sort(compare<nsecs_t>);
227    size_t numDeltas = deltas.size();
228    if (numDeltas > 1) {
229        nsecs_t deltaMinLimit = min(deltas[0] / kMultiplesThresholdDiv, kMinPeriod);
230        nsecs_t deltaMaxLimit = deltas[numDeltas / 2] * kMultiplesThresholdDiv;
231        for (size_t i = numDeltas / 2 + 1; i < numDeltas; ++i) {
232            if (deltas[i] > deltaMaxLimit) {
233                deltas.resize(i);
234                numDeltas = i;
235                break;
236            }
237        }
238        for (size_t i = 1; i < numDeltas; ++i) {
239            nsecs_t delta2nd = deltas[i] - deltas[i - 1];
240            if (delta2nd >= deltaMinLimit) {
241                //ALOGV("delta2: %lld", (long long)(delta2nd));
242                deltas.push(delta2nd);
243            }
244        }
245    }
246
247    // use the one that yields the best match
248    int64_t bestScore;
249    for (size_t i = 0; i < deltas.size(); ++i) {
250        nsecs_t delta = deltas[i];
251        int64_t score = 0;
252#if 1
253        // simplest score: number of deltas that are near multiples
254        size_t matches = 0;
255        for (size_t j = 0; j < deltas.size(); ++j) {
256            nsecs_t err = periodicError(deltas[j], delta);
257            if (err < delta / kMultiplesThresholdDiv) {
258                ++matches;
259            }
260        }
261        score = matches;
262#if 0
263        // could be weighed by the (1 - normalized error)
264        if (numSamplesToUse >= kMinSamplesToEstimatePeriod) {
265            int64_t a, b, err;
266            fit(firstTime, delta, numSamplesToUse, &a, &b, &err);
267            err = (1 << (2 * kPrecision)) - err;
268            score *= max(0, err);
269        }
270#endif
271#else
272        // or use the error as a negative score
273        if (numSamplesToUse >= kMinSamplesToEstimatePeriod) {
274            int64_t a, b, err;
275            fit(firstTime, delta, numSamplesToUse, &a, &b, &err);
276            score = -delta * err;
277        }
278#endif
279        if (i == 0 || score > bestScore) {
280            bestScore = score;
281            mPeriod = delta;
282            mPhase = firstTime;
283        }
284    }
285    ALOGV("priming[%zu] phase:%lld period:%lld", numSamplesToUse, mPhase, mPeriod);
286}
287
288nsecs_t VideoFrameScheduler::PLL::addSample(nsecs_t time) {
289    if (mLastTime >= 0
290            // if time goes backward, or we skipped rendering
291            && (time > mLastTime + kMaxAllowedFrameSkip || time < mLastTime)) {
292        restart();
293    }
294
295    mLastTime = time;
296    mTimes[mNumSamples % kHistorySize] = time;
297    ++mNumSamples;
298
299    bool doFit = time > mRefitAt;
300    if ((mPeriod <= 0 || !mPrimed) && mNumSamples >= kMinSamplesToStartPrime) {
301        prime(kMinSamplesToStopPrime);
302        ++mSamplesUsedForPriming;
303        doFit = true;
304    }
305    if (mPeriod > 0 && mNumSamples >= kMinSamplesToEstimatePeriod) {
306        if (mPhase < 0) {
307            // initialize phase to the current render time
308            mPhase = time;
309            doFit = true;
310        } else if (!doFit) {
311            int64_t err = periodicError(time - mPhase, mPeriod);
312            doFit = err > mPeriod / kReFitThresholdDiv;
313        }
314
315        if (doFit) {
316            int64_t a, b, err;
317            mRefitAt = time + kRefitRefreshPeriod;
318            fit(mPhase, mPeriod, kMaxSamplesToEstimatePeriod, &a, &b, &err);
319            mPhase += (mPeriod * b) >> kPrecision;
320            mPeriod = (mPeriod * a) >> kPrecision;
321            ALOGV("new phase:%lld period:%lld", (long long)mPhase, (long long)mPeriod);
322
323            if (err < kErrorThreshold) {
324                if (!mPrimed && mSamplesUsedForPriming >= kMinSamplesToStopPrime) {
325                    mPrimed = true;
326                }
327            } else {
328                mPrimed = false;
329                mSamplesUsedForPriming = 0;
330            }
331        }
332    }
333    return mPeriod;
334}
335
336/* ======================================================================= */
337/*                             Frame Scheduler                             */
338/* ======================================================================= */
339
340static const nsecs_t kDefaultVsyncPeriod = kNanosIn1s / 60;  // 60Hz
341static const nsecs_t kVsyncRefreshPeriod = kNanosIn1s;       // 1 sec
342
343VideoFrameScheduler::VideoFrameScheduler()
344    : mVsyncTime(0),
345      mVsyncPeriod(0),
346      mVsyncRefreshAt(0),
347      mLastVsyncTime(-1),
348      mTimeCorrection(0) {
349}
350
351void VideoFrameScheduler::updateVsync() {
352    mVsyncRefreshAt = systemTime(SYSTEM_TIME_MONOTONIC) + kVsyncRefreshPeriod;
353    mVsyncPeriod = 0;
354    mVsyncTime = 0;
355
356    // TODO: schedule frames for the destination surface
357    // For now, surface flinger only schedules frames on the primary display
358    if (mComposer == NULL) {
359        String16 name("SurfaceFlinger");
360        sp<IServiceManager> sm = defaultServiceManager();
361        mComposer = interface_cast<ISurfaceComposer>(sm->checkService(name));
362    }
363    if (mComposer != NULL) {
364        DisplayStatInfo stats;
365        status_t res = mComposer->getDisplayStats(NULL /* display */, &stats);
366        if (res == OK) {
367            ALOGV("vsync time:%lld period:%lld",
368                    (long long)stats.vsyncTime, (long long)stats.vsyncPeriod);
369            mVsyncTime = stats.vsyncTime;
370            mVsyncPeriod = stats.vsyncPeriod;
371        } else {
372            ALOGW("getDisplayStats returned %d", res);
373        }
374    } else {
375        ALOGW("could not get surface mComposer service");
376    }
377}
378
379void VideoFrameScheduler::init(float videoFps) {
380    updateVsync();
381
382    mLastVsyncTime = -1;
383    mTimeCorrection = 0;
384
385    mPll.reset(videoFps);
386}
387
388void VideoFrameScheduler::restart() {
389    mLastVsyncTime = -1;
390    mTimeCorrection = 0;
391
392    mPll.restart();
393}
394
395nsecs_t VideoFrameScheduler::getVsyncPeriod() {
396    if (mVsyncPeriod > 0) {
397        return mVsyncPeriod;
398    }
399    return kDefaultVsyncPeriod;
400}
401
402nsecs_t VideoFrameScheduler::schedule(nsecs_t renderTime) {
403    nsecs_t origRenderTime = renderTime;
404
405    nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
406    if (now >= mVsyncRefreshAt) {
407        updateVsync();
408    }
409
410    // without VSYNC info, there is nothing to do
411    if (mVsyncPeriod == 0) {
412        ALOGV("no vsync: render=%lld", (long long)renderTime);
413        return renderTime;
414    }
415
416    // ensure vsync time is well before (corrected) render time
417    if (mVsyncTime > renderTime - 4 * mVsyncPeriod) {
418        mVsyncTime -=
419            ((mVsyncTime - renderTime) / mVsyncPeriod + 5) * mVsyncPeriod;
420    }
421
422    // Video presentation takes place at the VSYNC _after_ renderTime.  Adjust renderTime
423    // so this effectively becomes a rounding operation (to the _closest_ VSYNC.)
424    renderTime -= mVsyncPeriod / 2;
425
426    const nsecs_t videoPeriod = mPll.addSample(origRenderTime);
427    if (videoPeriod > 0) {
428        // Smooth out rendering
429        size_t N = 12;
430        nsecs_t fiveSixthDev =
431            abs(((videoPeriod * 5 + mVsyncPeriod) % (mVsyncPeriod * 6)) - mVsyncPeriod)
432                    / (mVsyncPeriod / 100);
433        // use 20 samples if we are doing 5:6 ratio +- 1% (e.g. playing 50Hz on 60Hz)
434        if (fiveSixthDev < 12) {  /* 12% / 6 = 2% */
435            N = 20;
436        }
437
438        nsecs_t offset = 0;
439        nsecs_t edgeRemainder = 0;
440        for (size_t i = 1; i <= N; i++) {
441            offset +=
442                (renderTime + mTimeCorrection + videoPeriod * i - mVsyncTime) % mVsyncPeriod;
443            edgeRemainder += (videoPeriod * i) % mVsyncPeriod;
444        }
445        mTimeCorrection += mVsyncPeriod / 2 - offset / N;
446        renderTime += mTimeCorrection;
447        nsecs_t correctionLimit = mVsyncPeriod * 3 / 5;
448        edgeRemainder = abs(edgeRemainder / N - mVsyncPeriod / 2);
449        if (edgeRemainder <= mVsyncPeriod / 3) {
450            correctionLimit /= 2;
451        }
452
453        // estimate how many VSYNCs a frame will spend on the display
454        nsecs_t nextVsyncTime =
455            renderTime + mVsyncPeriod - ((renderTime - mVsyncTime) % mVsyncPeriod);
456        if (mLastVsyncTime >= 0) {
457            size_t minVsyncsPerFrame = videoPeriod / mVsyncPeriod;
458            size_t vsyncsForLastFrame = divRound(nextVsyncTime - mLastVsyncTime, mVsyncPeriod);
459            bool vsyncsPerFrameAreNearlyConstant =
460                periodicError(videoPeriod, mVsyncPeriod) / (mVsyncPeriod / 20) == 0;
461
462            if (mTimeCorrection > correctionLimit &&
463                    (vsyncsPerFrameAreNearlyConstant || vsyncsForLastFrame > minVsyncsPerFrame)) {
464                // remove a VSYNC
465                mTimeCorrection -= mVsyncPeriod / 2;
466                renderTime -= mVsyncPeriod / 2;
467                nextVsyncTime -= mVsyncPeriod;
468                --vsyncsForLastFrame;
469            } else if (mTimeCorrection < -correctionLimit &&
470                    (vsyncsPerFrameAreNearlyConstant || vsyncsForLastFrame == minVsyncsPerFrame)) {
471                // add a VSYNC
472                mTimeCorrection += mVsyncPeriod / 2;
473                renderTime += mVsyncPeriod / 2;
474                nextVsyncTime += mVsyncPeriod;
475                ++vsyncsForLastFrame;
476            }
477            ATRACE_INT("FRAME_VSYNCS", vsyncsForLastFrame);
478        }
479        mLastVsyncTime = nextVsyncTime;
480    }
481
482    // align rendertime to the center between VSYNC edges
483    renderTime -= (renderTime - mVsyncTime) % mVsyncPeriod;
484    renderTime += mVsyncPeriod / 2;
485    ALOGV("adjusting render: %lld => %lld", (long long)origRenderTime, (long long)renderTime);
486    ATRACE_INT("FRAME_FLIP_IN(ms)", (renderTime - now) / 1000000);
487    return renderTime;
488}
489
490void VideoFrameScheduler::release() {
491    mComposer.clear();
492}
493
494VideoFrameScheduler::~VideoFrameScheduler() {
495    release();
496}
497
498} // namespace android
499
500