diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 17:32:43 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 17:32:43 +0000 |
commit | 6bf0a5cb5034a7e684dcc3500e841785237ce2dd (patch) | |
tree | a68f146d7fa01f0134297619fbe7e33db084e0aa /mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java | |
parent | Initial commit. (diff) | |
download | thunderbird-6bf0a5cb5034a7e684dcc3500e841785237ce2dd.tar.xz thunderbird-6bf0a5cb5034a7e684dcc3500e841785237ce2dd.zip |
Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java')
-rw-r--r-- | mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java | 538 |
1 files changed, 538 insertions, 0 deletions
diff --git a/mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java b/mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java new file mode 100644 index 0000000000..b0b7c7da13 --- /dev/null +++ b/mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java @@ -0,0 +1,538 @@ +/* + * Copyright (C) 2018 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. + */ +package org.mozilla.thirdparty.com.google.android.exoplayer2.extractor; + +import androidx.annotation.IntDef; +import androidx.annotation.Nullable; +import org.mozilla.thirdparty.com.google.android.exoplayer2.C; +import org.mozilla.thirdparty.com.google.android.exoplayer2.util.Assertions; +import org.mozilla.thirdparty.com.google.android.exoplayer2.util.Util; +import java.io.IOException; +import java.lang.annotation.Documented; +import java.lang.annotation.Retention; +import java.lang.annotation.RetentionPolicy; + +/** + * A seeker that supports seeking within a stream by searching for the target frame using binary + * search. + * + * <p>This seeker operates on a stream that contains multiple frames (or samples). Each frame is + * associated with some kind of timestamps, such as stream time, or frame indices. Given a target + * seek time, the seeker will find the corresponding target timestamp, and perform a search + * operation within the stream to identify the target frame and return the byte position in the + * stream of the target frame. + */ +public abstract class BinarySearchSeeker { + + /** A seeker that looks for a given timestamp from an input. */ + protected interface TimestampSeeker { + + /** + * Searches a limited window of the provided input for a target timestamp. The size of the + * window is implementation specific, but should be small enough such that it's reasonable for + * multiple such reads to occur during a seek operation. + * + * @param input The {@link ExtractorInput} from which data should be peeked. + * @param targetTimestamp The target timestamp. + * @return A {@link TimestampSearchResult} that describes the result of the search. + * @throws IOException If an error occurred reading from the input. + * @throws InterruptedException If the thread was interrupted. + */ + TimestampSearchResult searchForTimestamp(ExtractorInput input, long targetTimestamp) + throws IOException, InterruptedException; + + /** Called when a seek operation finishes. */ + default void onSeekFinished() {} + } + + /** + * A {@link SeekTimestampConverter} implementation that returns the seek time itself as the + * timestamp for a seek time position. + */ + public static final class DefaultSeekTimestampConverter implements SeekTimestampConverter { + + @Override + public long timeUsToTargetTime(long timeUs) { + return timeUs; + } + } + + /** + * A converter that converts seek time in stream time into target timestamp for the {@link + * BinarySearchSeeker}. + */ + protected interface SeekTimestampConverter { + /** + * Converts a seek time in microseconds into target timestamp for the {@link + * BinarySearchSeeker}. + */ + long timeUsToTargetTime(long timeUs); + } + + /** + * When seeking within the source, if the offset is smaller than or equal to this value, the seek + * operation will be performed using a skip operation. Otherwise, the source will be reloaded at + * the new seek position. + */ + private static final long MAX_SKIP_BYTES = 256 * 1024; + + protected final BinarySearchSeekMap seekMap; + protected final TimestampSeeker timestampSeeker; + protected @Nullable SeekOperationParams seekOperationParams; + + private final int minimumSearchRange; + + /** + * Constructs an instance. + * + * @param seekTimestampConverter The {@link SeekTimestampConverter} that converts seek time in + * stream time into target timestamp. + * @param timestampSeeker A {@link TimestampSeeker} that will be used to search for timestamps + * within the stream. + * @param durationUs The duration of the stream in microseconds. + * @param floorTimePosition The minimum timestamp value (inclusive) in the stream. + * @param ceilingTimePosition The minimum timestamp value (exclusive) in the stream. + * @param floorBytePosition The starting position of the frame with minimum timestamp value + * (inclusive) in the stream. + * @param ceilingBytePosition The position after the frame with maximum timestamp value in the + * stream. + * @param approxBytesPerFrame Approximated bytes per frame. + * @param minimumSearchRange The minimum byte range that this binary seeker will operate on. If + * the remaining search range is smaller than this value, the search will stop, and the seeker + * will return the position at the floor of the range as the result. + */ + @SuppressWarnings("initialization") + protected BinarySearchSeeker( + SeekTimestampConverter seekTimestampConverter, + TimestampSeeker timestampSeeker, + long durationUs, + long floorTimePosition, + long ceilingTimePosition, + long floorBytePosition, + long ceilingBytePosition, + long approxBytesPerFrame, + int minimumSearchRange) { + this.timestampSeeker = timestampSeeker; + this.minimumSearchRange = minimumSearchRange; + this.seekMap = + new BinarySearchSeekMap( + seekTimestampConverter, + durationUs, + floorTimePosition, + ceilingTimePosition, + floorBytePosition, + ceilingBytePosition, + approxBytesPerFrame); + } + + /** Returns the seek map for the stream. */ + public final SeekMap getSeekMap() { + return seekMap; + } + + /** + * Sets the target time in microseconds within the stream to seek to. + * + * @param timeUs The target time in microseconds within the stream. + */ + public final void setSeekTargetUs(long timeUs) { + if (seekOperationParams != null && seekOperationParams.getSeekTimeUs() == timeUs) { + return; + } + seekOperationParams = createSeekParamsForTargetTimeUs(timeUs); + } + + /** Returns whether the last operation set by {@link #setSeekTargetUs(long)} is still pending. */ + public final boolean isSeeking() { + return seekOperationParams != null; + } + + /** + * Continues to handle the pending seek operation. Returns one of the {@code RESULT_} values from + * {@link Extractor}. + * + * @param input The {@link ExtractorInput} from which data should be read. + * @param seekPositionHolder If {@link Extractor#RESULT_SEEK} is returned, this holder is updated + * to hold the position of the required seek. + * @return One of the {@code RESULT_} values defined in {@link Extractor}. + * @throws IOException If an error occurred reading from the input. + * @throws InterruptedException If the thread was interrupted. + */ + public int handlePendingSeek(ExtractorInput input, PositionHolder seekPositionHolder) + throws InterruptedException, IOException { + TimestampSeeker timestampSeeker = Assertions.checkNotNull(this.timestampSeeker); + while (true) { + SeekOperationParams seekOperationParams = Assertions.checkNotNull(this.seekOperationParams); + long floorPosition = seekOperationParams.getFloorBytePosition(); + long ceilingPosition = seekOperationParams.getCeilingBytePosition(); + long searchPosition = seekOperationParams.getNextSearchBytePosition(); + + if (ceilingPosition - floorPosition <= minimumSearchRange) { + // The seeking range is too small, so we can just continue from the floor position. + markSeekOperationFinished(/* foundTargetFrame= */ false, floorPosition); + return seekToPosition(input, floorPosition, seekPositionHolder); + } + if (!skipInputUntilPosition(input, searchPosition)) { + return seekToPosition(input, searchPosition, seekPositionHolder); + } + + input.resetPeekPosition(); + TimestampSearchResult timestampSearchResult = + timestampSeeker.searchForTimestamp(input, seekOperationParams.getTargetTimePosition()); + + switch (timestampSearchResult.type) { + case TimestampSearchResult.TYPE_POSITION_OVERESTIMATED: + seekOperationParams.updateSeekCeiling( + timestampSearchResult.timestampToUpdate, timestampSearchResult.bytePositionToUpdate); + break; + case TimestampSearchResult.TYPE_POSITION_UNDERESTIMATED: + seekOperationParams.updateSeekFloor( + timestampSearchResult.timestampToUpdate, timestampSearchResult.bytePositionToUpdate); + break; + case TimestampSearchResult.TYPE_TARGET_TIMESTAMP_FOUND: + markSeekOperationFinished( + /* foundTargetFrame= */ true, timestampSearchResult.bytePositionToUpdate); + skipInputUntilPosition(input, timestampSearchResult.bytePositionToUpdate); + return seekToPosition( + input, timestampSearchResult.bytePositionToUpdate, seekPositionHolder); + case TimestampSearchResult.TYPE_NO_TIMESTAMP: + // We can't find any timestamp in the search range from the search position. + // Give up, and just continue reading from the last search position in this case. + markSeekOperationFinished(/* foundTargetFrame= */ false, searchPosition); + return seekToPosition(input, searchPosition, seekPositionHolder); + default: + throw new IllegalStateException("Invalid case"); + } + } + } + + protected SeekOperationParams createSeekParamsForTargetTimeUs(long timeUs) { + return new SeekOperationParams( + timeUs, + seekMap.timeUsToTargetTime(timeUs), + seekMap.floorTimePosition, + seekMap.ceilingTimePosition, + seekMap.floorBytePosition, + seekMap.ceilingBytePosition, + seekMap.approxBytesPerFrame); + } + + protected final void markSeekOperationFinished(boolean foundTargetFrame, long resultPosition) { + seekOperationParams = null; + timestampSeeker.onSeekFinished(); + onSeekOperationFinished(foundTargetFrame, resultPosition); + } + + protected void onSeekOperationFinished(boolean foundTargetFrame, long resultPosition) { + // Do nothing. + } + + protected final boolean skipInputUntilPosition(ExtractorInput input, long position) + throws IOException, InterruptedException { + long bytesToSkip = position - input.getPosition(); + if (bytesToSkip >= 0 && bytesToSkip <= MAX_SKIP_BYTES) { + input.skipFully((int) bytesToSkip); + return true; + } + return false; + } + + protected final int seekToPosition( + ExtractorInput input, long position, PositionHolder seekPositionHolder) { + if (position == input.getPosition()) { + return Extractor.RESULT_CONTINUE; + } else { + seekPositionHolder.position = position; + return Extractor.RESULT_SEEK; + } + } + + /** + * Contains parameters for a pending seek operation by {@link BinarySearchSeeker}. + * + * <p>This class holds parameters for a binary-search for the {@code targetTimePosition} in the + * range [floorPosition, ceilingPosition). + */ + protected static class SeekOperationParams { + private final long seekTimeUs; + private final long targetTimePosition; + private final long approxBytesPerFrame; + + private long floorTimePosition; + private long ceilingTimePosition; + private long floorBytePosition; + private long ceilingBytePosition; + private long nextSearchBytePosition; + + /** + * Returns the next position in the stream to search for target frame, given [floorBytePosition, + * ceilingBytePosition), with corresponding [floorTimePosition, ceilingTimePosition). + */ + protected static long calculateNextSearchBytePosition( + long targetTimePosition, + long floorTimePosition, + long ceilingTimePosition, + long floorBytePosition, + long ceilingBytePosition, + long approxBytesPerFrame) { + if (floorBytePosition + 1 >= ceilingBytePosition + || floorTimePosition + 1 >= ceilingTimePosition) { + return floorBytePosition; + } + long seekTimeDuration = targetTimePosition - floorTimePosition; + float estimatedBytesPerTimeUnit = + (float) (ceilingBytePosition - floorBytePosition) + / (ceilingTimePosition - floorTimePosition); + // It's better to under-estimate rather than over-estimate, because the extractor + // input can skip forward easily, but cannot rewind easily (it may require a new connection + // to be made). + // Therefore, we should reduce the estimated position by some amount, so it will converge to + // the correct frame earlier. + long bytesToSkip = (long) (seekTimeDuration * estimatedBytesPerTimeUnit); + long confidenceInterval = bytesToSkip / 20; + long estimatedFramePosition = floorBytePosition + bytesToSkip - approxBytesPerFrame; + long estimatedPosition = estimatedFramePosition - confidenceInterval; + return Util.constrainValue(estimatedPosition, floorBytePosition, ceilingBytePosition - 1); + } + + protected SeekOperationParams( + long seekTimeUs, + long targetTimePosition, + long floorTimePosition, + long ceilingTimePosition, + long floorBytePosition, + long ceilingBytePosition, + long approxBytesPerFrame) { + this.seekTimeUs = seekTimeUs; + this.targetTimePosition = targetTimePosition; + this.floorTimePosition = floorTimePosition; + this.ceilingTimePosition = ceilingTimePosition; + this.floorBytePosition = floorBytePosition; + this.ceilingBytePosition = ceilingBytePosition; + this.approxBytesPerFrame = approxBytesPerFrame; + this.nextSearchBytePosition = + calculateNextSearchBytePosition( + targetTimePosition, + floorTimePosition, + ceilingTimePosition, + floorBytePosition, + ceilingBytePosition, + approxBytesPerFrame); + } + + /** + * Returns the floor byte position of the range [floorPosition, ceilingPosition) for this seek + * operation. + */ + private long getFloorBytePosition() { + return floorBytePosition; + } + + /** + * Returns the ceiling byte position of the range [floorPosition, ceilingPosition) for this seek + * operation. + */ + private long getCeilingBytePosition() { + return ceilingBytePosition; + } + + /** Returns the target timestamp as translated from the seek time. */ + private long getTargetTimePosition() { + return targetTimePosition; + } + + /** Returns the target seek time in microseconds. */ + private long getSeekTimeUs() { + return seekTimeUs; + } + + /** Updates the floor constraints (inclusive) of the seek operation. */ + private void updateSeekFloor(long floorTimePosition, long floorBytePosition) { + this.floorTimePosition = floorTimePosition; + this.floorBytePosition = floorBytePosition; + updateNextSearchBytePosition(); + } + + /** Updates the ceiling constraints (exclusive) of the seek operation. */ + private void updateSeekCeiling(long ceilingTimePosition, long ceilingBytePosition) { + this.ceilingTimePosition = ceilingTimePosition; + this.ceilingBytePosition = ceilingBytePosition; + updateNextSearchBytePosition(); + } + + /** Returns the next position in the stream to search. */ + private long getNextSearchBytePosition() { + return nextSearchBytePosition; + } + + private void updateNextSearchBytePosition() { + this.nextSearchBytePosition = + calculateNextSearchBytePosition( + targetTimePosition, + floorTimePosition, + ceilingTimePosition, + floorBytePosition, + ceilingBytePosition, + approxBytesPerFrame); + } + } + + /** + * Represents possible search results for {@link + * TimestampSeeker#searchForTimestamp(ExtractorInput, long)}. + */ + public static final class TimestampSearchResult { + + /** The search found a timestamp that it deems close enough to the given target. */ + public static final int TYPE_TARGET_TIMESTAMP_FOUND = 0; + /** The search found only timestamps larger than the target timestamp. */ + public static final int TYPE_POSITION_OVERESTIMATED = -1; + /** The search found only timestamps smaller than the target timestamp. */ + public static final int TYPE_POSITION_UNDERESTIMATED = -2; + /** The search didn't find any timestamps. */ + public static final int TYPE_NO_TIMESTAMP = -3; + + @Documented + @Retention(RetentionPolicy.SOURCE) + @IntDef({ + TYPE_TARGET_TIMESTAMP_FOUND, + TYPE_POSITION_OVERESTIMATED, + TYPE_POSITION_UNDERESTIMATED, + TYPE_NO_TIMESTAMP + }) + @interface Type {} + + public static final TimestampSearchResult NO_TIMESTAMP_IN_RANGE_RESULT = + new TimestampSearchResult(TYPE_NO_TIMESTAMP, C.TIME_UNSET, C.POSITION_UNSET); + + /** The type of the result. */ + @Type private final int type; + + /** + * When {@link #type} is {@link #TYPE_POSITION_OVERESTIMATED}, the {@link + * SeekOperationParams#ceilingTimePosition} should be updated with this value. When {@link + * #type} is {@link #TYPE_POSITION_UNDERESTIMATED}, the {@link + * SeekOperationParams#floorTimePosition} should be updated with this value. + */ + private final long timestampToUpdate; + /** + * When {@link #type} is {@link #TYPE_POSITION_OVERESTIMATED}, the {@link + * SeekOperationParams#ceilingBytePosition} should be updated with this value. When {@link + * #type} is {@link #TYPE_POSITION_UNDERESTIMATED}, the {@link + * SeekOperationParams#floorBytePosition} should be updated with this value. + */ + private final long bytePositionToUpdate; + + private TimestampSearchResult( + @Type int type, long timestampToUpdate, long bytePositionToUpdate) { + this.type = type; + this.timestampToUpdate = timestampToUpdate; + this.bytePositionToUpdate = bytePositionToUpdate; + } + + /** + * Returns a result to signal that the current position in the input stream overestimates the + * true position of the target frame, and the {@link BinarySearchSeeker} should modify its + * {@link SeekOperationParams}'s ceiling timestamp and byte position using the given values. + */ + public static TimestampSearchResult overestimatedResult( + long newCeilingTimestamp, long newCeilingBytePosition) { + return new TimestampSearchResult( + TYPE_POSITION_OVERESTIMATED, newCeilingTimestamp, newCeilingBytePosition); + } + + /** + * Returns a result to signal that the current position in the input stream underestimates the + * true position of the target frame, and the {@link BinarySearchSeeker} should modify its + * {@link SeekOperationParams}'s floor timestamp and byte position using the given values. + */ + public static TimestampSearchResult underestimatedResult( + long newFloorTimestamp, long newCeilingBytePosition) { + return new TimestampSearchResult( + TYPE_POSITION_UNDERESTIMATED, newFloorTimestamp, newCeilingBytePosition); + } + + /** + * Returns a result to signal that the target timestamp has been found at {@code + * resultBytePosition}, and the seek operation can stop. + */ + public static TimestampSearchResult targetFoundResult(long resultBytePosition) { + return new TimestampSearchResult( + TYPE_TARGET_TIMESTAMP_FOUND, C.TIME_UNSET, resultBytePosition); + } + } + + /** + * A {@link SeekMap} implementation that returns the estimated byte location from {@link + * SeekOperationParams#calculateNextSearchBytePosition(long, long, long, long, long, long)} for + * each {@link #getSeekPoints(long)} query. + */ + public static class BinarySearchSeekMap implements SeekMap { + private final SeekTimestampConverter seekTimestampConverter; + private final long durationUs; + private final long floorTimePosition; + private final long ceilingTimePosition; + private final long floorBytePosition; + private final long ceilingBytePosition; + private final long approxBytesPerFrame; + + /** Constructs a new instance of this seek map. */ + public BinarySearchSeekMap( + SeekTimestampConverter seekTimestampConverter, + long durationUs, + long floorTimePosition, + long ceilingTimePosition, + long floorBytePosition, + long ceilingBytePosition, + long approxBytesPerFrame) { + this.seekTimestampConverter = seekTimestampConverter; + this.durationUs = durationUs; + this.floorTimePosition = floorTimePosition; + this.ceilingTimePosition = ceilingTimePosition; + this.floorBytePosition = floorBytePosition; + this.ceilingBytePosition = ceilingBytePosition; + this.approxBytesPerFrame = approxBytesPerFrame; + } + + @Override + public boolean isSeekable() { + return true; + } + + @Override + public SeekPoints getSeekPoints(long timeUs) { + long nextSearchPosition = + SeekOperationParams.calculateNextSearchBytePosition( + /* targetTimePosition= */ seekTimestampConverter.timeUsToTargetTime(timeUs), + /* floorTimePosition= */ floorTimePosition, + /* ceilingTimePosition= */ ceilingTimePosition, + /* floorBytePosition= */ floorBytePosition, + /* ceilingBytePosition= */ ceilingBytePosition, + /* approxBytesPerFrame= */ approxBytesPerFrame); + return new SeekPoints(new SeekPoint(timeUs, nextSearchPosition)); + } + + @Override + public long getDurationUs() { + return durationUs; + } + + /** @see SeekTimestampConverter#timeUsToTargetTime(long) */ + public long timeUsToTargetTime(long timeUs) { + return seekTimestampConverter.timeUsToTargetTime(timeUs); + } + } +} |