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