Move LinearMap from libmedia to audio_utils.
LinearMap It is only used in AudioFlinger to associate track frames
to sink frames. It is not related to media stuff. In that case, move
it to audio_utils.
Test: make
Change-Id: I947e1cb61bd6e66d5fd53b4f7d0a8e1c5876cbf4
diff --git a/media/libmedia/include/media/LinearMap.h b/media/libmedia/include/media/LinearMap.h
deleted file mode 100644
index 2220a0c..0000000
--- a/media/libmedia/include/media/LinearMap.h
+++ /dev/null
@@ -1,366 +0,0 @@
-/*
- * Copyright 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef ANDROID_LINEAR_MAP_H
-#define ANDROID_LINEAR_MAP_H
-
-#include <stdint.h>
-
-namespace android {
-
-/*
-A general purpose lookup utility that defines a mapping between X and Y as a
-continuous set of line segments with shared (x, y) end-points.
-The (x, y) points must be added in order, monotonically increasing in both x and y;
-a log warning is emitted if this does not happen (See general usage notes below).
-
-A limited history of (x, y) points is kept for space reasons (See general usage notes).
-
-In AudioFlinger, we use the LinearMap to associate track frames to
-sink frames. When we want to obtain a client track timestamp, we first
-get a timestamp from the sink. The sink timestamp's position (mPosition)
-corresponds to the sink frames written. We use LinearMap to figure out which track frame
-the sink frame corresponds to. This allows us to substitute a track frame for the
-the sink frame (keeping the mTime identical) and return that timestamp back to the client.
-
-The method findX() can be used to retrieve an x value from a given y value and is
-used for timestamps, similarly for findY() which is provided for completeness.
-
-We update the (track frame, sink frame) points in the LinearMap each time we write data
-to the sink by the AudioFlinger PlaybackThread (MixerThread).
-
-
-AudioFlinger Timestamp Notes:
-
-1) Example: Obtaining a track timestamp during playback. In this case, the LinearMap
-looks something like this:
-
-Track Frame Sink Frame
-(track start)
-0 50000 (track starts here, the sink may already be running)
-1000 51000
-2000 52000
-
-When we request a track timestamp, we call the sink getTimestamp() and get for example
-mPosition = 51020. Using the LinearMap, we find we have played to track frame 1020.
-We substitute the sink mPosition of 51020 with the track position 1020,
-and return that timestamp to the app.
-
-2) Example: Obtaining a track timestamp duing pause. In this case, the LinearMap
-looks something like this:
-
-Track Frame Sink Frame
-... (some time has gone by)
-15000 30000
-16000 31000
-17000 32000
-(pause here)
-(suppose we call sink getTimestamp() here and get sink mPosition = 31100; that means
- we have played to track frame 16100. The track timestamp mPosition will
- continue to advance until the sink timestamp returns a value of mPosition
- greater than 32000, corresponding to track frame 17000 when the pause was called).
-17000 33000
-17000 34000
-...
-
-3) If the track underruns, it appears as if a pause was called on that track.
-
-4) If there is an underrun in the HAL layer, then it may be possible that
-the sink getTimestamp() will return a value greater than the number of frames written
-(it should always be less). This should be rare, if not impossible by some
-HAL implementations of the sink getTimestamp. In that case, timing is lost
-and we will return the most recent track frame written.
-
-5) When called with no points in the map, findX() returns the start value (default 0).
-This is consistent with starting after a stop() or flush().
-
-6) Resuming after Track standby will be similar to coming out of pause, as the HAL ensures
-framesWritten() and getTimestamp() are contiguous for non-offloaded/direct tracks.
-
-7) LinearMap works for different speeds and sample rates as it uses
-linear interpolation. Since AudioFlinger only updates speed and sample rate
-exactly at the sample points pushed into the LinearMap, the returned values
-from findX() and findY() are accurate regardless of how many speed or sample
-rate changes are made, so long as the coordinate looked up is within the
-sample history.
-
-General usage notes:
-
-1) In order for the LinearMap to work reliably, you cannot look backwards more
-than the size of its circular buffer history, set upon creation (typically 16).
-If you look back further, the position is extrapolated either from a passed in
-extrapolation parameter or from the oldest line segment.
-
-2) Points must monotonically increase in x and y. The increment between adjacent
-points cannot be greater than signed 32 bits. Wrap in the x, y coordinates are supported,
-since we use differences in our computation.
-
-3) If the frame data is discontinuous (due to stop or flush) call reset() to clear
-the sample counter.
-
-4) If (x, y) are not strictly monotonic increasing, i.e. (x2 > x1) and (y2 > y1),
-then one or both of the inverses y = f(x) or x = g(y) may have multiple solutions.
-In that case, the most recent solution is returned by findX() or findY(). We
-do not warn if (x2 == x1) or (y2 == y1), but we do logcat warn if (x2 < x1) or
-(y2 < y1).
-
-5) Due to rounding it is possible x != findX(findY(x)) or y != findY(findX(y))
-even when the inverse exists. Nevertheless, the values should be close.
-
-*/
-
-template <typename T>
-class LinearMap {
-public:
- // This enumeration describes the reliability of the findX() or findY() estimation
- // in descending order.
- enum FindMethod {
- FIND_METHOD_INTERPOLATION, // High reliability (errors due to rounding)
- FIND_METHOD_FORWARD_EXTRAPOLATION, // Reliability based on no future speed changes
- FIND_METHOD_BACKWARD_EXTRAPOLATION, // Reliability based on prior estimated speed
- FIND_METHOD_START_VALUE, // No samples in history, using start value
- };
-
- explicit LinearMap(size_t size)
- : mSize(size),
- mPos(0), // a circular buffer, so could start anywhere. the first sample is at 1.
- mSamples(0),
- // mStepValid(false), // only valid if mSamples > 1
- // mExtrapolateTail(false), // only valid if mSamples > 0
- mX(new T[size]),
- mY(new T[size]) { }
-
- ~LinearMap() {
- delete[] mX;
- delete[] mY;
- }
-
- // Add a new sample point to the linear map.
- //
- // The difference between the new sample and the previous sample
- // in the x or y coordinate must be less than INT32_MAX for purposes
- // of the linear interpolation or extrapolation.
- //
- // The value should be monotonic increasing (e.g. diff >= 0);
- // logcat warnings are issued if they are not.
- __attribute__((no_sanitize("integer")))
- void push(T x, T y) {
- // Assumption: we assume x, y are monotonic increasing values,
- // which (can) wrap in precision no less than 32 bits and have
- // "step" or differences between adjacent points less than 32 bits.
-
- if (mSamples > 0) {
- const bool lastStepValid = mStepValid;
- int32_t xdiff;
- int32_t ydiff;
- // check difference assumption here
- mStepValid = checkedDiff(&xdiff, x, mX[mPos], "x")
- & /* bitwise AND to always warn for ydiff, though logical AND is also OK */
- checkedDiff(&ydiff, y, mY[mPos], "y");
-
- // Optimization: do not add a new sample if the line segment would
- // simply extend the previous line segment. This extends the useful
- // history by removing redundant points.
- if (mSamples > 1 && mStepValid && lastStepValid) {
- const size_t prev = previousPosition();
- const int32_t xdiff2 = x - mX[prev];
- const int32_t ydiff2 = y - mY[prev];
-
- // if both current step and previous step are valid (non-negative and
- // less than INT32_MAX for precision greater than 4 bytes)
- // then the sum of the two steps is valid when the
- // int32_t difference is non-negative.
- if (xdiff2 >= 0 && ydiff2 >= 0
- && (int64_t)xdiff2 * ydiff == (int64_t)ydiff2 * xdiff) {
- // ALOGD("reusing sample! (%u, %u) sample depth %zd", x, y, mSamples);
- mX[mPos] = x;
- mY[mPos] = y;
- return;
- }
- }
- }
- if (++mPos >= mSize) {
- mPos = 0;
- }
- if (mSamples < mSize) {
- mExtrapolateTail = false;
- ++mSamples;
- } else {
- // we enable extrapolation beyond the oldest sample
- // if the sample buffers are completely full and we
- // no longer know the full history.
- mExtrapolateTail = true;
- }
- mX[mPos] = x;
- mY[mPos] = y;
- }
-
- // clear all samples from the circular array
- void reset() {
- // no need to reset mPos, we use a circular buffer.
- // computed values such as mStepValid are set after a subsequent push().
- mSamples = 0;
- }
-
- // returns true if LinearMap contains at least one sample.
- bool hasData() const {
- return mSamples != 0;
- }
-
- // find the corresponding X point from a Y point.
- // See findU for details.
- __attribute__((no_sanitize("integer")))
- T findX(T y, FindMethod *method = NULL, double extrapolation = 0.0, T startValue = 0) const {
- return findU(y, mX, mY, method, extrapolation, startValue);
- }
-
- // find the corresponding Y point from a X point.
- // See findU for details.
- __attribute__((no_sanitize("integer")))
- T findY(T x, FindMethod *method = NULL, double extrapolation = 0.0, T startValue = 0) const {
- return findU(x, mY, mX, method, extrapolation, startValue);
- }
-
-protected:
-
- // returns false if the diff is out of int32_t bounds or negative.
- __attribute__((no_sanitize("integer")))
- static inline bool checkedDiff(int32_t *diff, T x2, T x1, const char *coord) {
- if (sizeof(T) >= 8) {
- const int64_t diff64 = x2 - x1;
- *diff = (int32_t)diff64; // intentionally lose precision
- if (diff64 > INT32_MAX) {
- ALOGW("LinearMap: %s overflow diff(%lld) from %llu - %llu exceeds INT32_MAX",
- coord, (long long)diff64,
- (unsigned long long)x2, (unsigned long long)x1);
- return false;
- } else if (diff64 < 0) {
- ALOGW("LinearMap: %s negative diff(%lld) from %llu - %llu",
- coord, (long long)diff64,
- (unsigned long long)x2, (unsigned long long)x1);
- return false;
- }
- return true;
- }
- // for 32 bit integers we cannot detect overflow (it
- // shows up as a negative difference).
- *diff = x2 - x1;
- if (*diff < 0) {
- ALOGW("LinearMap: %s negative diff(%d) from %u - %u",
- coord, *diff, (unsigned)x2, (unsigned)x1);
- return false;
- }
- return true;
- }
-
- // Returns the previous position in the mSamples array
- // going backwards back steps.
- //
- // Parameters:
- // back: number of backward steps, cannot be less than zero or greater than mSamples.
- //
- __attribute__((no_sanitize("integer")))
- size_t previousPosition(ssize_t back = 1) const {
- LOG_ALWAYS_FATAL_IF(back < 0 || (size_t)back > mSamples, "Invalid back(%zd)", back);
- ssize_t position = mPos - back;
- if (position < 0) position += mSize;
- return (size_t)position;
- }
-
- // A generic implementation of finding the "other coordinate" with coordinates
- // (u, v) = (x, y) or (u, v) = (y, x).
- //
- // Parameters:
- // uArray: the u axis samples.
- // vArray: the v axis samples.
- // method: [out] how the returned value was computed.
- // extrapolation: the slope used when extrapolating from the
- // first sample value or the last sample value in the history.
- // If mExtrapolateTail is set, the slope of the last line segment
- // is used if the extrapolation parameter is zero to continue the tail of history.
- // At this time, we do not use a different value for forward extrapolation from the
- // head of history from backward extrapolation from the tail of history.
- // TODO: back extrapolation value could be stored along with mX, mY in history.
- // startValue: used only when there are no samples in history. One can detect
- // whether there are samples in history by the method hasData().
- //
- __attribute__((no_sanitize("integer")))
- T findU(T v, T *uArray, T *vArray, FindMethod *method,
- double extrapolation, T startValue) const {
- if (mSamples == 0) {
- if (method != NULL) {
- *method = FIND_METHOD_START_VALUE;
- }
- return startValue; // nothing yet
- }
- ssize_t previous = 0;
- int32_t diff = 0;
- for (ssize_t i = 0; i < (ssize_t)mSamples; ++i) {
- size_t current = previousPosition(i);
-
- // Assumption: even though the type "T" may have precision greater
- // than 32 bits, the difference between adjacent points is limited to 32 bits.
- diff = v - vArray[current];
- if (diff >= 0 ||
- (i == (ssize_t)mSamples - 1 && mExtrapolateTail && extrapolation == 0.0)) {
- // ALOGD("depth = %zd out of %zd", i, limit);
- if (i == 0) {
- if (method != NULL) {
- *method = FIND_METHOD_FORWARD_EXTRAPOLATION;
- }
- return uArray[current] + diff * extrapolation;
- }
- // interpolate / extrapolate: For this computation, we
- // must use differentials here otherwise we have inconsistent
- // values on modulo wrap. previous is always valid here since
- // i > 0. we also perform rounding with the assumption
- // that uStep, vStep, and diff are non-negative.
- int32_t uStep = uArray[previous] - uArray[current]; // non-negative
- int32_t vStep = vArray[previous] - vArray[current]; // positive
- T u = uStep <= 0 || vStep <= 0 ? // we do not permit negative ustep or vstep
- uArray[current]
- : ((int64_t)diff * uStep + (vStep >> 1)) / vStep + uArray[current];
- // ALOGD("u:%u diff:%d uStep:%d vStep:%d u_current:%d",
- // u, diff, uStep, vStep, uArray[current]);
- if (method != NULL) {
- *method = (diff >= 0) ?
- FIND_METHOD_INTERPOLATION : FIND_METHOD_BACKWARD_EXTRAPOLATION;
- }
- return u;
- }
- previous = current;
- }
- // previous is always valid here.
- if (method != NULL) {
- *method = FIND_METHOD_BACKWARD_EXTRAPOLATION;
- }
- return uArray[previous] + diff * extrapolation;
- }
-
-private:
- const size_t mSize; // Size of mX and mY arrays (history).
- size_t mPos; // Index in mX and mY of last pushed data;
- // (incremented after push) [0, mSize - 1].
- size_t mSamples; // Number of valid samples in the array [0, mSize].
- bool mStepValid; // Last sample step was valid (non-negative)
- bool mExtrapolateTail; // extrapolate tail using oldest line segment
- T * const mX; // History of X values as a circular array.
- T * const mY; // History of Y values as a circular array.
-};
-
-} // namespace android
-
-#endif // ANDROID_LINEAR_MAP_H
diff --git a/services/audioflinger/AudioFlinger.h b/services/audioflinger/AudioFlinger.h
index bbf8a29..d2de5fe 100644
--- a/services/audioflinger/AudioFlinger.h
+++ b/services/audioflinger/AudioFlinger.h
@@ -67,11 +67,11 @@
#include <media/AudioBufferProvider.h>
#include <media/AudioMixer.h>
#include <media/ExtendedAudioBufferProvider.h>
-#include <media/LinearMap.h>
#include <media/VolumeShaper.h>
#include <audio_utils/clock.h>
#include <audio_utils/FdToString.h>
+#include <audio_utils/LinearMap.h>
#include <audio_utils/SimpleLog.h>
#include <audio_utils/TimestampVerifier.h>