LibVideo: Implement Matroska Cues for faster keyframe lookup

This implements the fastest seeking mode available for tracks with cues
using an array of cue points for each track. It approximates the index
based on the seeking timestamp and then finds the earliest cue point
before the timestamp. The approximation assumes that cues will be on
a regular interval, which I don't believe is always the case, but it
should at least be faster than iterating the whole set of cue points
each time.

Cues are stored per track, but most videos will only have cue points
for the video track(s) that are present. For now, this assumes that it
should only seek based on the cue points for the selected track. To
seek audio in a video file, we should copy the seeked iterator over to
the audio track's iterator after seeking is complete. The iterator will
then skip to the next audio block.

1 files changed, 11 insertions, 0 deletions

diff --git a/Userland/Libraries/LibVideo/Containers/Matroska/Reader.h b/Userland/Libraries/LibVideo/Containers/Matroska/Reader.h
index 69907846ca..b1c6b955bd 100644
--- a/Userland/Libraries/LibVideo/Containers/Matroska/Reader.h
+++ b/Userland/Libraries/LibVideo/Containers/Matroska/Reader.h
@@ -41,6 +41,8 @@ public:
 
     DecoderErrorOr<SampleIterator> create_sample_iterator(u64 track_number);
     DecoderErrorOr<void> seek_to_random_access_point(SampleIterator&, Time);
+    DecoderErrorOr<Optional<Vector<CuePoint> const&>> cue_points_for_track(u64 track_number);
+    DecoderErrorOr<bool> has_cues_for_track(u64 track_number);
 
 private:
     Reader(ReadonlyBytes data)
@@ -55,6 +57,10 @@ private:
     DecoderErrorOr<void> ensure_tracks_are_parsed();
     DecoderErrorOr<void> parse_tracks(Streamer&);
 
+    DecoderErrorOr<void> parse_cues(Streamer&);
+    DecoderErrorOr<void> ensure_cues_are_parsed();
+    DecoderErrorOr<void> seek_to_cue_for_timestamp(SampleIterator&, Time const&);
+
     RefPtr<Core::MappedFile> m_mapped_file;
     ReadonlyBytes m_data;
 
@@ -69,6 +75,10 @@ private:
     Optional<SegmentInformation> m_segment_information;
 
     OrderedHashMap<u64, TrackEntry> m_tracks;
+
+    // The vectors must be sorted by timestamp at all times.
+    HashMap<u64, Vector<CuePoint>> m_cues;
+    bool m_cues_have_been_parsed { false };
 };
 
 class SampleIterator {
@@ -90,6 +100,7 @@ private:
     }
 
     DecoderErrorOr<void> set_position(size_t position);
+    DecoderErrorOr<void> seek_to_cue_point(CuePoint const& cue_point);
 
     RefPtr<Core::MappedFile> m_file;
     ReadonlyBytes m_data;