LibAudio: Improve FLAC seeking

"Improve" is an understatement, since this commit makes all FLAC files
seek without errors, mostly with high accuracy, and partially even fast:
- A new generic seek table type is introduced, which keeps an
  always-sorted list of seek points, which allows it to use binary
  search and fast insertion.
- Automatic seek points are inserted according to two heuristics
  (distance between seek points and minimum seek precision), which not
  only builds a seek table for already-played sections of the file, but
  improves seek precision even for files with an existing seek table.
- Manual seeking by skipping frames works properly now and is still used
  as a last resort.

7 files changed, 164 insertions, 25 deletions

diff --git a/Userland/Libraries/LibAudio/CMakeLists.txt b/Userland/Libraries/LibAudio/CMakeLists.txt
index 8f9f665acb..cf807e8ed1 100644
--- a/Userland/Libraries/LibAudio/CMakeLists.txt
+++ b/Userland/Libraries/LibAudio/CMakeLists.txt
@@ -1,4 +1,5 @@
 set(SOURCES
+    GenericTypes.cpp
     SampleFormats.cpp
     Loader.cpp
     WavLoader.cpp
diff --git a/Userland/Libraries/LibAudio/FlacLoader.cpp b/Userland/Libraries/LibAudio/FlacLoader.cpp
index 1f44634fdb..ff146cf52a 100644
--- a/Userland/Libraries/LibAudio/FlacLoader.cpp
+++ b/Userland/Libraries/LibAudio/FlacLoader.cpp
@@ -19,6 +19,7 @@
 #include <AK/UFixedBigInt.h>
 #include <LibAudio/FlacLoader.h>
 #include <LibAudio/FlacTypes.h>
+#include <LibAudio/GenericTypes.h>
 #include <LibAudio/LoaderError.h>
 #include <LibAudio/Resampler.h>
 #include <LibAudio/VorbisComment.h>
@@ -203,12 +204,19 @@ MaybeLoaderError FlacLoaderPlugin::load_seektable(FlacRawMetadataBlock& block)
     BigEndianInputBitStream seektable_bytes { MaybeOwned<Stream>(memory_stream) };
     for (size_t i = 0; i < block.length / 18; ++i) {
         // 11.14. SEEKPOINT
-        FlacSeekPoint seekpoint {
-            .sample_index = LOADER_TRY(seektable_bytes.read_bits<u64>(64)),
-            .byte_offset = LOADER_TRY(seektable_bytes.read_bits<u64>(64)),
-            .num_samples = LOADER_TRY(seektable_bytes.read_bits<u16>(16))
+        u64 sample_index = LOADER_TRY(seektable_bytes.read_bits<u64>(64));
+        u64 byte_offset = LOADER_TRY(seektable_bytes.read_bits<u64>(64));
+        // The sample count of a seek point is not relevant to us.
+        [[maybe_unused]] u16 sample_count = LOADER_TRY(seektable_bytes.read_bits<u16>(16));
+        // Placeholder, to be ignored.
+        if (sample_index == 0xFFFFFFFFFFFFFFFF)
+            continue;
+
+        SeekPoint seekpoint {
+            .sample_index = sample_index,
+            .byte_offset = byte_offset,
         };
-        m_seektable.append(seekpoint);
+        TRY(m_seektable.insert_seek_point(seekpoint));
     }
     dbgln_if(AFLACLOADER_DEBUG, "Loaded seektable of size {}", m_seektable.size());
     return {};
@@ -268,41 +276,57 @@ MaybeLoaderError FlacLoaderPlugin::seek(int int_sample_index)
     if (sample_index == m_loaded_samples)
         return {};
 
-    auto maybe_target_seekpoint = m_seektable.last_matching([sample_index](auto& seekpoint) { return seekpoint.sample_index <= sample_index; });
+    auto maybe_target_seekpoint = m_seektable.seek_point_before(sample_index);
+    auto const seek_tolerance = (seek_tolerance_ms * m_sample_rate) / 1000;
     // No seektable or no fitting entry: Perform normal forward read
     if (!maybe_target_seekpoint.has_value()) {
         if (sample_index < m_loaded_samples) {
             LOADER_TRY(m_stream->seek(m_data_start_location, SeekMode::SetPosition));
             m_loaded_samples = 0;
         }
-        auto to_read = sample_index - m_loaded_samples;
-        if (to_read == 0)
+        if (sample_index - m_loaded_samples == 0)
             return {};
-        dbgln_if(AFLACLOADER_DEBUG, "Seeking {} samples manually", to_read);
-        (void)TRY(load_chunks(to_read));
+        dbgln_if(AFLACLOADER_DEBUG, "Seeking {} samples manually", sample_index - m_loaded_samples);
     } else {
         auto target_seekpoint = maybe_target_seekpoint.release_value();
 
         // When a small seek happens, we may already be closer to the target than the seekpoint.
         if (sample_index - target_seekpoint.sample_index > sample_index - m_loaded_samples) {
-            dbgln_if(AFLACLOADER_DEBUG, "Close enough to target: seeking {} samples manually", sample_index - m_loaded_samples);
-            (void)TRY(load_chunks(sample_index - m_loaded_samples));
+            dbgln_if(AFLACLOADER_DEBUG, "Close enough to target ({} samples): not seeking", sample_index - m_loaded_samples);
             return {};
         }
 
-        dbgln_if(AFLACLOADER_DEBUG, "Seeking to seektable: sample index {}, byte offset {}, sample count {}", target_seekpoint.sample_index, target_seekpoint.byte_offset, target_seekpoint.num_samples);
+        dbgln_if(AFLACLOADER_DEBUG, "Seeking to seektable: sample index {}, byte offset {}", target_seekpoint.sample_index, target_seekpoint.byte_offset);
         auto position = target_seekpoint.byte_offset + m_data_start_location;
         if (m_stream->seek(static_cast<i64>(position), SeekMode::SetPosition).is_error())
             return LoaderError { LoaderError::Category::IO, m_loaded_samples, DeprecatedString::formatted("Invalid seek position {}", position) };
-
-        auto remaining_samples_after_seekpoint = sample_index - m_data_start_location;
-        if (remaining_samples_after_seekpoint > 0)
-            (void)TRY(load_chunks(remaining_samples_after_seekpoint));
         m_loaded_samples = target_seekpoint.sample_index;
     }
+
+    // Skip frames until we're within the seek tolerance.
+    while (sample_index - m_loaded_samples > seek_tolerance) {
+        (void)TRY(next_frame());
+        m_loaded_samples += m_current_frame->sample_count;
+    }
+
     return {};
 }
 
+bool FlacLoaderPlugin::should_insert_seekpoint_at(u64 sample_index) const
+{
+    auto const max_seekpoint_distance = (maximum_seekpoint_distance_ms * m_sample_rate) / 1000;
+    auto const seek_tolerance = (seek_tolerance_ms * m_sample_rate) / 1000;
+    auto const current_seekpoint_distance = m_seektable.seek_point_sample_distance_around(sample_index).value_or(NumericLimits<u64>::max());
+    auto const distance_to_previous_seekpoint = sample_index - m_seektable.seek_point_before(sample_index).value_or({ 0, 0 }).sample_index;
+
+    // We insert a seekpoint only under two conditions:
+    // - The seek points around us are spaced too far for what the loader recommends.
+    //   Prevents inserting too many seek points between pre-loaded seek points.
+    // - We are so far away from the previous seek point that seeking will become too imprecise if we don't insert a seek point at least here.
+    //   Prevents inserting too many seek points at the end of files without pre-loaded seek points.
+    return current_seekpoint_distance >= max_seekpoint_distance && distance_to_previous_seekpoint >= seek_tolerance;
+}
+
 ErrorOr<Vector<FixedArray<Sample>>, LoaderError> FlacLoaderPlugin::load_chunks(size_t samples_to_read_from_input)
 {
     ssize_t remaining_samples = static_cast<ssize_t>(m_total_samples - m_loaded_samples);
@@ -333,6 +357,16 @@ LoaderSamples FlacLoaderPlugin::next_frame()
         }                                                                                                                                         \
     } while (0)
 
+    auto frame_byte_index = TRY(m_stream->tell());
+    auto sample_index = m_loaded_samples;
+    // Insert a new seek point if we don't have enough here.
+    if (should_insert_seekpoint_at(sample_index)) {
+        dbgln_if(AFLACLOADER_DEBUG, "Inserting ad-hoc seek point for sample {} at byte {:x} (seekpoint spacing {} samples)", sample_index, frame_byte_index, m_seektable.seek_point_sample_distance_around(sample_index).value_or(NumericLimits<u64>::max()));
+        auto maybe_error = m_seektable.insert_seek_point({ .sample_index = sample_index, .byte_offset = frame_byte_index - m_data_start_location });
+        if (maybe_error.is_error())
+            dbgln("FLAC Warning: Inserting seek point for sample {} failed: {}", sample_index, maybe_error.release_error());
+    }
+
     BigEndianInputBitStream bit_stream { MaybeOwned<Stream>(*m_stream) };
 
     // TODO: Check the CRC-16 checksum (and others) by keeping track of read data
diff --git a/Userland/Libraries/LibAudio/FlacLoader.h b/Userland/Libraries/LibAudio/FlacLoader.h
index 3bac59af78..7efcada099 100644
--- a/Userland/Libraries/LibAudio/FlacLoader.h
+++ b/Userland/Libraries/LibAudio/FlacLoader.h
@@ -87,6 +87,8 @@ private:
     ALWAYS_INLINE ErrorOr<u32, LoaderError> convert_sample_rate_code(u8 sample_rate_code);
     ALWAYS_INLINE ErrorOr<PcmSampleFormat, LoaderError> convert_bit_depth_code(u8 bit_depth_code);
 
+    bool should_insert_seekpoint_at(u64 sample_index) const;
+
     // Data obtained directly from the FLAC metadata: many values have specific bit counts
     u32 m_sample_rate { 0 };         // 20 bit
     u8 m_num_channels { 0 };         // 3 bit
@@ -105,7 +107,7 @@ private:
     u64 m_data_start_location { 0 };
     Optional<FlacFrameHeader> m_current_frame;
     u64 m_current_sample_or_frame { 0 };
-    Vector<FlacSeekPoint> m_seektable;
+    SeekTable m_seektable;
 };
 
 }
diff --git a/Userland/Libraries/LibAudio/FlacTypes.h b/Userland/Libraries/LibAudio/FlacTypes.h
index bedfa32f71..ca5ffdadfa 100644
--- a/Userland/Libraries/LibAudio/FlacTypes.h
+++ b/Userland/Libraries/LibAudio/FlacTypes.h
@@ -91,11 +91,4 @@ struct FlacSubframeHeader {
     u8 bits_per_sample;
 };
 
-// 11.14. SEEKPOINT
-struct FlacSeekPoint {
-    u64 sample_index;
-    u64 byte_offset;
-    u16 num_samples;
-};
-
 }
diff --git a/Userland/Libraries/LibAudio/GenericTypes.cpp b/Userland/Libraries/LibAudio/GenericTypes.cpp
new file mode 100644
index 0000000000..4c6225b1ef
--- /dev/null
+++ b/Userland/Libraries/LibAudio/GenericTypes.cpp
@@ -0,0 +1,78 @@
+/*
+ * Copyright (c) 2023, kleines Filmröllchen <filmroellchen@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "GenericTypes.h"
+#include <AK/BinarySearch.h>
+#include <AK/Error.h>
+#include <AK/Optional.h>
+
+namespace Audio {
+
+size_t SeekTable::size() const
+{
+    return m_seek_points.size();
+}
+
+ReadonlySpan<SeekPoint> SeekTable::seek_points() const
+{
+    return m_seek_points.span();
+}
+
+Optional<SeekPoint const&> SeekTable::seek_point_before(u64 sample_index) const
+{
+    if (m_seek_points.is_empty())
+        return {};
+    size_t nearby_seek_point_index = 0;
+    AK::binary_search(m_seek_points, sample_index, &nearby_seek_point_index, [](auto const& sample_index, auto const& seekpoint_candidate) {
+        return static_cast<i64>(sample_index) - static_cast<i64>(seekpoint_candidate.sample_index);
+    });
+    // Binary search will always give us a close index, but it may be too large or too small.
+    // By doing the index adjustment in this order, we will always find a seek point before the given sample.
+    while (nearby_seek_point_index < m_seek_points.size() - 1 && m_seek_points[nearby_seek_point_index].sample_index < sample_index)
+        ++nearby_seek_point_index;
+    while (nearby_seek_point_index > 0 && m_seek_points[nearby_seek_point_index].sample_index > sample_index)
+        --nearby_seek_point_index;
+    return m_seek_points[nearby_seek_point_index];
+}
+
+Optional<u64> SeekTable::seek_point_sample_distance_around(u64 sample_index) const
+{
+    if (m_seek_points.is_empty())
+        return {};
+    size_t nearby_seek_point_index = 0;
+    AK::binary_search(m_seek_points, sample_index, &nearby_seek_point_index, [](auto const& sample_index, auto const& seekpoint_candidate) {
+        return static_cast<i64>(sample_index) - static_cast<i64>(seekpoint_candidate.sample_index);
+    });
+
+    while (nearby_seek_point_index < m_seek_points.size() && m_seek_points[nearby_seek_point_index].sample_index <= sample_index)
+        ++nearby_seek_point_index;
+    // There is no seek point beyond the sample index.
+    if (nearby_seek_point_index >= m_seek_points.size())
+        return {};
+    auto upper_seek_point_index = nearby_seek_point_index;
+
+    while (nearby_seek_point_index > 0 && m_seek_points[nearby_seek_point_index].sample_index > sample_index)
+        --nearby_seek_point_index;
+    auto lower_seek_point_index = nearby_seek_point_index;
+
+    VERIFY(upper_seek_point_index >= lower_seek_point_index);
+    return m_seek_points[upper_seek_point_index].sample_index - m_seek_points[lower_seek_point_index].sample_index;
+}
+
+ErrorOr<void> SeekTable::insert_seek_point(SeekPoint seek_point)
+{
+    if (auto previous_seek_point = seek_point_before(seek_point.sample_index); previous_seek_point.has_value() && previous_seek_point->sample_index == seek_point.sample_index) {
+        // Do not insert a duplicate seek point.
+        return {};
+    }
+
+    // FIXME: This could be even faster if we used binary search while finding the insertion point.
+    return m_seek_points.try_insert_before_matching(seek_point, [&](auto const& other_seek_point) {
+        return seek_point.sample_index < other_seek_point.sample_index;
+    });
+}
+
+}
diff --git a/Userland/Libraries/LibAudio/GenericTypes.h b/Userland/Libraries/LibAudio/GenericTypes.h
index 4d485473cd..f60bc9af4b 100644
--- a/Userland/Libraries/LibAudio/GenericTypes.h
+++ b/Userland/Libraries/LibAudio/GenericTypes.h
@@ -51,4 +51,28 @@ struct PictureData {
     Vector<u8> data;
 };
 
+// A generic sample seek point within a file.
+struct SeekPoint {
+    u64 sample_index;
+    u64 byte_offset;
+};
+
+class SeekTable {
+public:
+    Optional<SeekPoint const&> seek_point_before(u64 sample_index) const;
+    // Returns the distance between the closest two seek points around the sample index.
+    // The lower seek point may be exactly at the sample index, but the upper seek point must be after the sample index.
+    Optional<u64> seek_point_sample_distance_around(u64 sample_index) const;
+
+    size_t size() const;
+    ReadonlySpan<SeekPoint> seek_points() const;
+
+    ErrorOr<void> insert_seek_point(SeekPoint);
+
+private:
+    // Invariant: The list of seek points is always sorted.
+    // This makes all operations, such as inserting and searching, faster.
+    Vector<SeekPoint> m_seek_points;
+};
+
 }
diff --git a/Userland/Libraries/LibAudio/Loader.h b/Userland/Libraries/LibAudio/Loader.h
index 37bb668a5f..699f28d345 100644
--- a/Userland/Libraries/LibAudio/Loader.h
+++ b/Userland/Libraries/LibAudio/Loader.h
@@ -32,6 +32,13 @@ static constexpr StringView no_plugin_error = "No loader plugin available"sv;
 // There was no intensive fine-tuning done to determine this value, so improvements may definitely be possible.
 constexpr size_t const loader_buffer_size = 8 * KiB;
 
+// Two seek points should ideally not be farther apart than this.
+// This variable is a heuristic for seek table-constructing loaders.
+constexpr u64 const maximum_seekpoint_distance_ms = 1000;
+// Seeking should be at least as precise as this.
+// That means: The actual achieved seek position must not be more than this amount of time before the requested seek position.
+constexpr u64 const seek_tolerance_ms = 5000;
+
 using LoaderSamples = ErrorOr<FixedArray<Sample>, LoaderError>;
 using MaybeLoaderError = ErrorOr<void, LoaderError>;