1 /*
2  * Copyright 2018 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 #ifndef ANDROID_AUDIO_UTILS_TIMESTAMP_VERIFIER_H
18 #define ANDROID_AUDIO_UTILS_TIMESTAMP_VERIFIER_H
19 
20 #include <audio_utils/clock.h>
21 #include <audio_utils/Statistics.h>
22 
23 namespace android {
24 
25 /** Verifies that a sequence of timestamps (a frame count, time pair)
26  * is consistent based on sample rate.
27  *
28  * F is the type of frame counts (for example int64_t)
29  * T is the type of time in Ns (for example int64_t ns)
30  *
31  * All methods except for toString() are safe to call from a SCHED_FIFO thread.
32  */
33 template <typename F /* frame count */, typename T /* time units */>
34 class TimestampVerifier {
35 public:
36     explicit constexpr TimestampVerifier(
37             double alphaJitter = kDefaultAlphaJitter,
38             double alphaEstimator = kDefaultAlphaEstimator)
39         : mJitterMs{alphaJitter}
40         , mTimestampEstimator{alphaEstimator}
41         , mCorrectedJitterMs{alphaJitter}
42     { }
43 
44     // construct from static arrays.
45     template <size_t N>
TimestampVerifier(const F (& frames)[N],const T (& timeNs)[N],uint32_t sampleRate)46     constexpr TimestampVerifier(const F (&frames)[N], const T (&timeNs)[N], uint32_t sampleRate) {
47          for (size_t i = 0; i < N; ++i) {
48              add(frames[i], timeNs[i], sampleRate);
49          }
50     }
51 
52     /** adds a timestamp, represented by a (frames, timeNs) pair and the
53      * sample rate to the TimestampVerifier.
54      *
55      * The frames and timeNs should be monotonic increasing
56      * (from the previous discontinuity, or the start of adding).
57      *
58      * A sample rate change triggers a discontinuity automatically.
59      */
add(F frames,T timeNs,uint32_t sampleRate)60     constexpr void add(F frames, T timeNs, uint32_t sampleRate) {
61         // We consider negative time as "not ready".
62         // TODO: do we need to consider an explicit epoch start time?
63         if (timeNs < 0) {
64            ++mNotReady;
65            return;
66         }
67 
68         // Reject timestamp if identical to last
69         if (mLastTimestamp.mFrames == frames && mLastTimestamp.mTimeNs == timeNs
70                 && mSampleRate == sampleRate) {
71             return;
72         }
73 
74         if (mDiscontinuity || mSampleRate != sampleRate) {
75             // ALOGD("disc:%d frames:%lld timeNs:%lld",
76             //         mDiscontinuity, (long long)frames, (long long)timeNs);
77             switch (mDiscontinuityMode) {
78             case DISCONTINUITY_MODE_CONTINUOUS:
79                 break;
80             case DISCONTINUITY_MODE_ZERO:
81                 // frame position reset to 0 on discontinuity - detect this.
82                 if (mLastTimestamp.mFrames
83                         > kDiscontinuityZeroStartThresholdMs * sampleRate / MILLIS_PER_SECOND
84                         && frames >= mLastTimestamp.mFrames) {
85                     return;
86                 }
87                 break;
88             default:
89                 assert(false); // never here.
90                 break;
91             }
92             mDiscontinuity = false;
93             mFirstTimestamp = {frames, timeNs};
94             mLastTimestamp = mFirstTimestamp;
95             mLastCorrectedTimestamp = mFirstTimestamp;
96             mSampleRate = sampleRate;
97         } else {
98             assert(sampleRate != 0);
99             const FrameTime timestamp{frames, timeNs};
100             if (mCold && (timestamp.mTimeNs == mLastTimestamp.mTimeNs
101                     || computeRatio(timestamp, mLastTimestamp, sampleRate)
102                             < kMinimumSpeedToStartVerification)) {
103                 // cold is when the timestamp may take some time to start advancing at normal rate.
104                 ++mColds;
105                 mFirstTimestamp = timestamp;
106                 mLastCorrectedTimestamp = mFirstTimestamp;
107                 // ALOGD("colds:%lld frames:%lld timeNs:%lld",
108                 //         (long long)mColds, (long long)frames, (long long)timeNs);
109             } else {
110                 const double jitterMs = computeJitterMs(timestamp, mLastTimestamp, sampleRate);
111                 mJitterMs.add(jitterMs);
112                 // ALOGD("frames:%lld  timeNs:%lld jitterMs:%lf",
113                 //         (long long)frames, (long long)timeNs, jitterMs);
114 
115                 // Handle timestamp estimation
116                 if (mCold) {
117                     mCold = false;
118                     mTimestampEstimator.reset();
119                     mTimestampEstimator.add(
120                         {(double)mFirstTimestamp.mTimeNs * 1e-9, (double)mFirstTimestamp.mFrames});
121                     mFirstCorrectedTimestamp = mFirstTimestamp;
122                     mLastCorrectedTimestamp = mFirstCorrectedTimestamp;
123                 }
124                 mTimestampEstimator.add({(double)timeNs * 1e-9, (double)frames});
125 
126                 // Find the corrected timestamp, a posteriori estimate.
127                 FrameTime correctedTimestamp = timestamp;
128 
129                 // The estimator is valid after 2 timestamps; we choose correlation
130                 // of kEstimatorR2Lock to signal locked.
131                 if (mTimestampEstimator.getN() > 2
132                         && mTimestampEstimator.getR2() >= kEstimatorR2Lock) {
133 #if 1
134                     // We choose frame correction over time correction.
135                     // TODO: analyze preference.
136 
137                     // figure out frames based on time.
138                     const F newFrames = mTimestampEstimator.getYFromX((double)timeNs * 1e-9);
139                     // prevent retrograde correction.
140                     correctedTimestamp.mFrames = std::max(
141                             newFrames, mLastCorrectedTimestamp.mFrames);
142 #else
143                     // figure out time based on frames
144                     const T newTimeNs = mTimestampEstimator.getXFromY((double)frames) * 1e9;
145                     // prevent retrograde correction.
146                     correctedTimestamp.mTimeNs = std::max(
147                             newTimeNs, mLastCorrectedTimestamp.mTimeNs);
148 #endif
149                 }
150 
151                 // Compute the jitter if the corrected timestamp is used.
152                 const double correctedJitterMs = computeJitterMs(
153                         correctedTimestamp, mLastCorrectedTimestamp, sampleRate);
154                 mCorrectedJitterMs.add(correctedJitterMs);
155                 mLastCorrectedTimestamp = correctedTimestamp;
156             }
157             mLastTimestamp = timestamp;
158         }
159         ++mTimestamps;
160     }
161 
162     // How a discontinuity affects frame position.
163     enum DiscontinuityMode : int32_t {
164         DISCONTINUITY_MODE_CONTINUOUS, // frame position is unaffected.
165         DISCONTINUITY_MODE_ZERO,       // frame position resets to zero.
166     };
167 
168     /** registers a discontinuity.
169      *
170      * The next timestamp added does not participate in any statistics with the last
171      * timestamp, but rather anchors following timestamp sequence verification.
172      *
173      * Consecutive discontinuities are treated as one for the purposes of counting.
174      */
discontinuity(DiscontinuityMode mode)175     constexpr void discontinuity(DiscontinuityMode mode) {
176         assert(mode == DISCONTINUITY_MODE_CONTINUOUS || mode == DISCONTINUITY_MODE_ZERO);
177 
178         // If there is a pending ZERO discontinuity, do not override with CONTINUOUS
179         if (mode == DISCONTINUITY_MODE_CONTINUOUS && mDiscontinuityMode == DISCONTINUITY_MODE_ZERO
180                 && mDiscontinuity) {
181             return;
182         }
183 
184         if (mode != mDiscontinuityMode || !mDiscontinuity) {
185             // ALOGD("discontinuity");
186             mDiscontinuity = true;
187             mDiscontinuityMode = mode;
188             mCold = true;
189             ++mDiscontinuities;
190         }
191     }
192 
193     /** registers an error.
194      *
195      * The timestamp sequence is still assumed continuous after error. Use discontinuity()
196      * if it is not.
197      */
error()198     constexpr void error() {
199         ++mErrors;
200     }
201 
getDiscontinuityMode()202     constexpr DiscontinuityMode getDiscontinuityMode() const {
203         return mDiscontinuityMode;
204     }
205 
206     /** returns a string with relevant statistics.
207      *
208      * Should not be called from a SCHED_FIFO thread since it uses std::string.
209      */
toString()210     std::string toString() const {
211         std::stringstream ss;
212 
213         ss << "n=" << mTimestamps;          // number of timestamps added with valid times.
214         ss << " disc=" << mDiscontinuities; // discontinuities encountered (dups ignored).
215         ss << " cold=" << mColds;           // timestamps not progressing after discontinuity.
216         ss << " nRdy=" << mNotReady;        // timestamps not ready (time negative).
217         ss << " err=" << mErrors;           // errors encountered.
218         if (mSampleRate != 0) {             // ratio of time-by-frames / time
219             ss << " rate=" << computeRatio( // (since last discontinuity).
220                     mLastTimestamp, mFirstTimestamp, mSampleRate);
221         }
222         ss << " jitterMs(" << mJitterMs.toString() << ")";  // timestamp jitter statistics.
223 
224         double a, b, r2; // sample rate is the slope b.
225         estimateSampleRate(a, b, r2);
226 
227         // r2 is correlation coefficient (where 1 is best and 0 is worst),
228         // so for better printed resolution, we print from 1 - r2.
229         ss << " localSR(" << b << ", " << (1. - r2) << ")";
230         ss << " correctedJitterMs(" << mCorrectedJitterMs.toString() << ")";
231         return ss.str();
232     }
233 
234     // general counters
getN()235     constexpr int64_t getN() const { return mTimestamps; }
getDiscontinuities()236     constexpr int64_t getDiscontinuities() const { return mDiscontinuities; }
getNotReady()237     constexpr int64_t getNotReady() const { return mNotReady; }
getColds()238     constexpr int64_t getColds() const { return mColds; }
getErrors()239     constexpr int64_t getErrors() const { return mErrors; }
getJitterMs()240     constexpr const audio_utils::Statistics<double> & getJitterMs() const {
241         return mJitterMs;
242     }
243     // estimate local sample rate (dframes / dtime) which is the slope b from:
244     // y = a + bx
estimateSampleRate(double & a,double & b,double & r2)245     constexpr void estimateSampleRate(double &a, double &b, double &r2) const {
246         mTimestampEstimator.computeYLine(a, b, r2);
247     }
248 
249     // timestamp anchor info
250     using FrameTime = struct { F mFrames; T mTimeNs; }; // a "constexpr" pair
getFirstTimestamp()251     constexpr FrameTime getFirstTimestamp() const { return mFirstTimestamp; }
getLastTimestamp()252     constexpr FrameTime getLastTimestamp() const { return mLastTimestamp; }
getSampleRate()253     constexpr uint32_t getSampleRate() const { return mSampleRate; }
254 
getLastCorrectedTimestamp()255     constexpr FrameTime getLastCorrectedTimestamp() const { return mLastCorrectedTimestamp; }
256 
257     // Inf+-, NaN is possible only if sampleRate is 0 (should not happen)
computeJitterMs(const FrameTime & current,const FrameTime & last,uint32_t sampleRate)258     static constexpr double computeJitterMs(
259             const FrameTime &current, const FrameTime &last, uint32_t sampleRate) {
260         const auto diff = sub(current, last);
261         const double frameDifferenceNs = diff.first * 1e9 / sampleRate;
262         const double jitterNs = diff.second - frameDifferenceNs;  // actual - expected
263         return jitterNs * 1e-6;
264     }
265 
266 private:
267     // our statistics have exponentially weighted history.
268     // the defaults are here.
269     static constexpr double kDefaultAlphaJitter = 0.999;
270     static constexpr double kDefaultAlphaEstimator = 0.99;
271     static constexpr double kEstimatorR2Lock = 0.95;
272 
273     // general counters
274     int64_t mTimestamps = 0;
275     int64_t mDiscontinuities = 0;
276     int64_t mNotReady = 0;
277     int64_t mColds = 0;
278     int64_t mErrors = 0;
279     audio_utils::Statistics<double> mJitterMs{kDefaultAlphaJitter};
280 
281     // timestamp anchor info
282     bool mDiscontinuity = true;
283     bool mCold = true;
284     FrameTime mFirstTimestamp{};
285     FrameTime mLastTimestamp{};
286     uint32_t mSampleRate = 0;
287 
288     // timestamp estimation and correction
289     audio_utils::LinearLeastSquaresFit<double> mTimestampEstimator{kDefaultAlphaEstimator};
290     FrameTime mFirstCorrectedTimestamp{};
291     FrameTime mLastCorrectedTimestamp{};
292     audio_utils::Statistics<double> mCorrectedJitterMs{kDefaultAlphaJitter};
293 
294     // configuration
295     DiscontinuityMode mDiscontinuityMode = DISCONTINUITY_MODE_CONTINUOUS;
296 
297     static constexpr double kMinimumSpeedToStartVerification = 0.1;
298      // Number of ms so small that initial jitter is OK for DISCONTINUITY_MODE_ZERO.
299     static constexpr int64_t kDiscontinuityZeroStartThresholdMs = 5;
300 
301     // sub returns the signed type of the difference between left and right.
302     // This is only important if F or T are unsigned int types.
303     __attribute__((no_sanitize("integer")))
sub(const FrameTime & left,const FrameTime & right)304     static constexpr auto sub(const FrameTime &left, const FrameTime &right) {
305         return std::make_pair<
306                 typename std::make_signed<F>::type, typename std::make_signed<T>::type>(
307                         left.mFrames - right.mFrames, left.mTimeNs - right.mTimeNs);
308     }
309 
310     // Inf+-, Nan possible depending on differences between current and last.
computeRatio(const FrameTime & current,const FrameTime & last,uint32_t sampleRate)311     static constexpr double computeRatio(
312             const FrameTime &current, const FrameTime &last, uint32_t sampleRate) {
313         const auto diff = sub(current, last);
314         const double frameDifferenceNs = diff.first * 1e9 / sampleRate;
315         return frameDifferenceNs / diff.second;
316     }
317 };
318 
319 } // namespace android
320 
321 #endif // !ANDROID_AUDIO_UTILS_TIMESTAMP_VERIFIER_H
322