From 0cd0565abc5a0abf8df41268b890d59dc5a92f06 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?kleines=20Filmr=C3=B6llchen?= Date: Sat, 18 Mar 2023 14:12:25 +0100 Subject: 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. --- Userland/Libraries/LibAudio/CMakeLists.txt | 1 + Userland/Libraries/LibAudio/FlacLoader.cpp | 68 ++++++++++++++++++------ Userland/Libraries/LibAudio/FlacLoader.h | 4 +- Userland/Libraries/LibAudio/FlacTypes.h | 7 --- Userland/Libraries/LibAudio/GenericTypes.cpp | 78 ++++++++++++++++++++++++++++ Userland/Libraries/LibAudio/GenericTypes.h | 24 +++++++++ Userland/Libraries/LibAudio/Loader.h | 7 +++ 7 files changed, 164 insertions(+), 25 deletions(-) create mode 100644 Userland/Libraries/LibAudio/GenericTypes.cpp (limited to 'Userland') 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 #include #include +#include #include #include #include @@ -203,12 +204,19 @@ MaybeLoaderError FlacLoaderPlugin::load_seektable(FlacRawMetadataBlock& block) BigEndianInputBitStream seektable_bytes { MaybeOwned(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(64)), - .byte_offset = LOADER_TRY(seektable_bytes.read_bits(64)), - .num_samples = LOADER_TRY(seektable_bytes.read_bits(16)) + u64 sample_index = LOADER_TRY(seektable_bytes.read_bits(64)); + u64 byte_offset = LOADER_TRY(seektable_bytes.read_bits(64)); + // The sample count of a seek point is not relevant to us. + [[maybe_unused]] u16 sample_count = LOADER_TRY(seektable_bytes.read_bits(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(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::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>, LoaderError> FlacLoaderPlugin::load_chunks(size_t samples_to_read_from_input) { ssize_t remaining_samples = static_cast(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::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(*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 convert_sample_rate_code(u8 sample_rate_code); ALWAYS_INLINE ErrorOr 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 m_current_frame; u64 m_current_sample_or_frame { 0 }; - Vector 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 + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#include "GenericTypes.h" +#include +#include +#include + +namespace Audio { + +size_t SeekTable::size() const +{ + return m_seek_points.size(); +} + +ReadonlySpan SeekTable::seek_points() const +{ + return m_seek_points.span(); +} + +Optional 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(sample_index) - static_cast(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 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(sample_index) - static_cast(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 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 data; }; +// A generic sample seek point within a file. +struct SeekPoint { + u64 sample_index; + u64 byte_offset; +}; + +class SeekTable { +public: + Optional 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 seek_point_sample_distance_around(u64 sample_index) const; + + size_t size() const; + ReadonlySpan seek_points() const; + + ErrorOr 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 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, LoaderError>; using MaybeLoaderError = ErrorOr; -- cgit v1.2.3