path: root/mobile/android/exoplayer2/src/main/java/org/mozilla/thirdparty/com/google/android/exoplayer2/extractor/BinarySearchSeeker.java

/*
 * 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);
    }
  }
}