1 /* 2 * Copyright 2015 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_LINEAR_MAP_H 18 #define ANDROID_LINEAR_MAP_H 19 20 #include <stdint.h> 21 22 namespace android { 23 24 /* 25 A general purpose lookup utility that defines a mapping between X and Y as a 26 continuous set of line segments with shared (x, y) end-points. 27 The (x, y) points must be added in order, monotonically increasing in both x and y; 28 a log warning is emitted if this does not happen (See general usage notes below). 29 30 A limited history of (x, y) points is kept for space reasons (See general usage notes). 31 32 In AudioFlinger, we use the LinearMap to associate track frames to 33 sink frames. When we want to obtain a client track timestamp, we first 34 get a timestamp from the sink. The sink timestamp's position (mPosition) 35 corresponds to the sink frames written. We use LinearMap to figure out which track frame 36 the sink frame corresponds to. This allows us to substitute a track frame for the 37 the sink frame (keeping the mTime identical) and return that timestamp back to the client. 38 39 The method findX() can be used to retrieve an x value from a given y value and is 40 used for timestamps, similarly for findY() which is provided for completeness. 41 42 We update the (track frame, sink frame) points in the LinearMap each time we write data 43 to the sink by the AudioFlinger PlaybackThread (MixerThread). 44 45 46 AudioFlinger Timestamp Notes: 47 48 1) Example: Obtaining a track timestamp during playback. In this case, the LinearMap 49 looks something like this: 50 51 Track Frame Sink Frame 52 (track start) 53 0 50000 (track starts here, the sink may already be running) 54 1000 51000 55 2000 52000 56 57 When we request a track timestamp, we call the sink getTimestamp() and get for example 58 mPosition = 51020. Using the LinearMap, we find we have played to track frame 1020. 59 We substitute the sink mPosition of 51020 with the track position 1020, 60 and return that timestamp to the app. 61 62 2) Example: Obtaining a track timestamp duing pause. In this case, the LinearMap 63 looks something like this: 64 65 Track Frame Sink Frame 66 ... (some time has gone by) 67 15000 30000 68 16000 31000 69 17000 32000 70 (pause here) 71 (suppose we call sink getTimestamp() here and get sink mPosition = 31100; that means 72 we have played to track frame 16100. The track timestamp mPosition will 73 continue to advance until the sink timestamp returns a value of mPosition 74 greater than 32000, corresponding to track frame 17000 when the pause was called). 75 17000 33000 76 17000 34000 77 ... 78 79 3) If the track underruns, it appears as if a pause was called on that track. 80 81 4) If there is an underrun in the HAL layer, then it may be possible that 82 the sink getTimestamp() will return a value greater than the number of frames written 83 (it should always be less). This should be rare, if not impossible by some 84 HAL implementations of the sink getTimestamp. In that case, timing is lost 85 and we will return the most recent track frame written. 86 87 5) When called with no points in the map, findX() returns the start value (default 0). 88 This is consistent with starting after a stop() or flush(). 89 90 6) Resuming after Track standby will be similar to coming out of pause, as the HAL ensures 91 framesWritten() and getTimestamp() are contiguous for non-offloaded/direct tracks. 92 93 7) LinearMap works for different speeds and sample rates as it uses 94 linear interpolation. Since AudioFlinger only updates speed and sample rate 95 exactly at the sample points pushed into the LinearMap, the returned values 96 from findX() and findY() are accurate regardless of how many speed or sample 97 rate changes are made, so long as the coordinate looked up is within the 98 sample history. 99 100 General usage notes: 101 102 1) In order for the LinearMap to work reliably, you cannot look backwards more 103 than the size of its circular buffer history, set upon creation (typically 16). 104 If you look back further, the position is extrapolated either from a passed in 105 extrapolation parameter or from the oldest line segment. 106 107 2) Points must monotonically increase in x and y. The increment between adjacent 108 points cannot be greater than signed 32 bits. Wrap in the x, y coordinates are supported, 109 since we use differences in our computation. 110 111 3) If the frame data is discontinuous (due to stop or flush) call reset() to clear 112 the sample counter. 113 114 4) If (x, y) are not strictly monotonic increasing, i.e. (x2 > x1) and (y2 > y1), 115 then one or both of the inverses y = f(x) or x = g(y) may have multiple solutions. 116 In that case, the most recent solution is returned by findX() or findY(). We 117 do not warn if (x2 == x1) or (y2 == y1), but we do logcat warn if (x2 < x1) or 118 (y2 < y1). 119 120 5) Due to rounding it is possible x != findX(findY(x)) or y != findY(findX(y)) 121 even when the inverse exists. Nevertheless, the values should be close. 122 123 */ 124 125 template <typename T> 126 class LinearMap { 127 public: 128 // This enumeration describes the reliability of the findX() or findY() estimation 129 // in descending order. 130 enum FindMethod { 131 FIND_METHOD_INTERPOLATION, // High reliability (errors due to rounding) 132 FIND_METHOD_FORWARD_EXTRAPOLATION, // Reliability based on no future speed changes 133 FIND_METHOD_BACKWARD_EXTRAPOLATION, // Reliability based on prior estimated speed 134 FIND_METHOD_START_VALUE, // No samples in history, using start value 135 }; 136 137 LinearMap(size_t size) 138 : mSize(size), 139 mPos(0), // a circular buffer, so could start anywhere. the first sample is at 1. 140 mSamples(0), 141 // mStepValid(false), // only valid if mSamples > 1 142 // mExtrapolateTail(false), // only valid if mSamples > 0 143 mX(new T[size]), 144 mY(new T[size]) { } 145 146 ~LinearMap() { 147 delete[] mX; 148 delete[] mY; 149 } 150 151 // Add a new sample point to the linear map. 152 // 153 // The difference between the new sample and the previous sample 154 // in the x or y coordinate must be less than INT32_MAX for purposes 155 // of the linear interpolation or extrapolation. 156 // 157 // The value should be monotonic increasing (e.g. diff >= 0); 158 // logcat warnings are issued if they are not. 159 __attribute__((no_sanitize("integer"))) 160 void push(T x, T y) { 161 // Assumption: we assume x, y are monotonic increasing values, 162 // which (can) wrap in precision no less than 32 bits and have 163 // "step" or differences between adjacent points less than 32 bits. 164 165 if (mSamples > 0) { 166 const bool lastStepValid = mStepValid; 167 int32_t xdiff; 168 int32_t ydiff; 169 // check difference assumption here 170 mStepValid = checkedDiff(&xdiff, x, mX[mPos], "x") 171 & /* bitwise AND to always warn for ydiff, though logical AND is also OK */ 172 checkedDiff(&ydiff, y, mY[mPos], "y"); 173 174 // Optimization: do not add a new sample if the line segment would 175 // simply extend the previous line segment. This extends the useful 176 // history by removing redundant points. 177 if (mSamples > 1 && mStepValid && lastStepValid) { 178 const size_t prev = previousPosition(); 179 const int32_t xdiff2 = x - mX[prev]; 180 const int32_t ydiff2 = y - mY[prev]; 181 182 // if both current step and previous step are valid (non-negative and 183 // less than INT32_MAX for precision greater than 4 bytes) 184 // then the sum of the two steps is valid when the 185 // int32_t difference is non-negative. 186 if (xdiff2 >= 0 && ydiff2 >= 0 187 && (int64_t)xdiff2 * ydiff == (int64_t)ydiff2 * xdiff) { 188 // ALOGD("reusing sample! (%u, %u) sample depth %zd", x, y, mSamples); 189 mX[mPos] = x; 190 mY[mPos] = y; 191 return; 192 } 193 } 194 } 195 if (++mPos >= mSize) { 196 mPos = 0; 197 } 198 if (mSamples < mSize) { 199 mExtrapolateTail = false; 200 ++mSamples; 201 } else { 202 // we enable extrapolation beyond the oldest sample 203 // if the sample buffers are completely full and we 204 // no longer know the full history. 205 mExtrapolateTail = true; 206 } 207 mX[mPos] = x; 208 mY[mPos] = y; 209 } 210 211 // clear all samples from the circular array 212 void reset() { 213 // no need to reset mPos, we use a circular buffer. 214 // computed values such as mStepValid are set after a subsequent push(). 215 mSamples = 0; 216 } 217 218 // returns true if LinearMap contains at least one sample. 219 bool hasData() const { 220 return mSamples != 0; 221 } 222 223 // find the corresponding X point from a Y point. 224 // See findU for details. 225 __attribute__((no_sanitize("integer"))) 226 T findX(T y, FindMethod *method = NULL, double extrapolation = 0.0, T startValue = 0) const { 227 return findU(y, mX, mY, method, extrapolation, startValue); 228 } 229 230 // find the corresponding Y point from a X point. 231 // See findU for details. 232 __attribute__((no_sanitize("integer"))) 233 T findY(T x, FindMethod *method = NULL, double extrapolation = 0.0, T startValue = 0) const { 234 return findU(x, mY, mX, method, extrapolation, startValue); 235 } 236 237 protected: 238 239 // returns false if the diff is out of int32_t bounds or negative. 240 __attribute__((no_sanitize("integer"))) 241 static inline bool checkedDiff(int32_t *diff, T x2, T x1, const char *coord) { 242 if (sizeof(T) >= 8) { 243 const int64_t diff64 = x2 - x1; 244 *diff = (int32_t)diff64; // intentionally lose precision 245 if (diff64 > INT32_MAX) { 246 ALOGW("LinearMap: %s overflow diff(%lld) from %llu - %llu exceeds INT32_MAX", 247 coord, (long long)diff64, 248 (unsigned long long)x2, (unsigned long long)x1); 249 return false; 250 } else if (diff64 < 0) { 251 ALOGW("LinearMap: %s negative diff(%lld) from %llu - %llu", 252 coord, (long long)diff64, 253 (unsigned long long)x2, (unsigned long long)x1); 254 return false; 255 } 256 return true; 257 } 258 // for 32 bit integers we cannot detect overflow (it 259 // shows up as a negative difference). 260 *diff = x2 - x1; 261 if (*diff < 0) { 262 ALOGW("LinearMap: %s negative diff(%d) from %u - %u", 263 coord, *diff, (unsigned)x2, (unsigned)x1); 264 return false; 265 } 266 return true; 267 } 268 269 // Returns the previous position in the mSamples array 270 // going backwards back steps. 271 // 272 // Parameters: 273 // back: number of backward steps, cannot be less than zero or greater than mSamples. 274 // 275 __attribute__((no_sanitize("integer"))) 276 size_t previousPosition(ssize_t back = 1) const { 277 LOG_ALWAYS_FATAL_IF(back < 0 || (size_t)back > mSamples, "Invalid back(%zd)", back); 278 ssize_t position = mPos - back; 279 if (position < 0) position += mSize; 280 return (size_t)position; 281 } 282 283 // A generic implementation of finding the "other coordinate" with coordinates 284 // (u, v) = (x, y) or (u, v) = (y, x). 285 // 286 // Parameters: 287 // uArray: the u axis samples. 288 // vArray: the v axis samples. 289 // method: [out] how the returned value was computed. 290 // extrapolation: the slope used when extrapolating from the 291 // first sample value or the last sample value in the history. 292 // If mExtrapolateTail is set, the slope of the last line segment 293 // is used if the extrapolation parameter is zero to continue the tail of history. 294 // At this time, we do not use a different value for forward extrapolation from the 295 // head of history from backward extrapolation from the tail of history. 296 // TODO: back extrapolation value could be stored along with mX, mY in history. 297 // startValue: used only when there are no samples in history. One can detect 298 // whether there are samples in history by the method hasData(). 299 // 300 __attribute__((no_sanitize("integer"))) 301 T findU(T v, T *uArray, T *vArray, FindMethod *method, 302 double extrapolation, T startValue) const { 303 if (mSamples == 0) { 304 if (method != NULL) { 305 *method = FIND_METHOD_START_VALUE; 306 } 307 return startValue; // nothing yet 308 } 309 ssize_t previous = 0; 310 int32_t diff = 0; 311 for (ssize_t i = 0; i < (ssize_t)mSamples; ++i) { 312 size_t current = previousPosition(i); 313 314 // Assumption: even though the type "T" may have precision greater 315 // than 32 bits, the difference between adjacent points is limited to 32 bits. 316 diff = v - vArray[current]; 317 if (diff >= 0 || 318 (i == (ssize_t)mSamples - 1 && mExtrapolateTail && extrapolation == 0.0)) { 319 // ALOGD("depth = %zd out of %zd", i, limit); 320 if (i == 0) { 321 if (method != NULL) { 322 *method = FIND_METHOD_FORWARD_EXTRAPOLATION; 323 } 324 return uArray[current] + diff * extrapolation; 325 } 326 // interpolate / extrapolate: For this computation, we 327 // must use differentials here otherwise we have inconsistent 328 // values on modulo wrap. previous is always valid here since 329 // i > 0. we also perform rounding with the assumption 330 // that uStep, vStep, and diff are non-negative. 331 int32_t uStep = uArray[previous] - uArray[current]; // non-negative 332 int32_t vStep = vArray[previous] - vArray[current]; // positive 333 T u = uStep <= 0 || vStep <= 0 ? // we do not permit negative ustep or vstep 334 uArray[current] 335 : ((int64_t)diff * uStep + (vStep >> 1)) / vStep + uArray[current]; 336 // ALOGD("u:%u diff:%d uStep:%d vStep:%d u_current:%d", 337 // u, diff, uStep, vStep, uArray[current]); 338 if (method != NULL) { 339 *method = (diff >= 0) ? 340 FIND_METHOD_INTERPOLATION : FIND_METHOD_BACKWARD_EXTRAPOLATION; 341 } 342 return u; 343 } 344 previous = current; 345 } 346 // previous is always valid here. 347 if (method != NULL) { 348 *method = FIND_METHOD_BACKWARD_EXTRAPOLATION; 349 } 350 return uArray[previous] + diff * extrapolation; 351 } 352 353 private: 354 const size_t mSize; // Size of mX and mY arrays (history). 355 size_t mPos; // Index in mX and mY of last pushed data; 356 // (incremented after push) [0, mSize - 1]. 357 size_t mSamples; // Number of valid samples in the array [0, mSize]. 358 bool mStepValid; // Last sample step was valid (non-negative) 359 bool mExtrapolateTail; // extrapolate tail using oldest line segment 360 T * const mX; // History of X values as a circular array. 361 T * const mY; // History of Y values as a circular array. 362 }; 363 364 } // namespace android 365 366 #endif // ANDROID_LINEAR_MAP_H 367
