Skip to main content

decibri_decode/
flac.rs

1//! FLAC: the third container this crate reads, and the first that is a codec
2//! as well as a container.
3//!
4//! Written from [RFC 9639](https://www.rfc-editor.org/rfc/rfc9639), which
5//! specifies the format in full, including the numerical considerations that
6//! decide the integer widths below and worked decoding examples that this
7//! crate carries as literal test vectors. No other implementation's source
8//! was consulted, deliberately: the point of a specification complete enough
9//! to implement from is that the resulting code has no provenance question
10//! attached to it.
11//!
12//! # The oracle is inside the data
13//!
14//! Every FLAC file carries an MD5 of its own unencoded audio in the
15//! streaminfo metadata block. That makes FLAC the one format in this crate
16//! whose correctness can be checked on **every file the decoder ever sees**,
17//! not only on the ones in a test suite, and this crate checks it: a
18//! whole-file decode hashes as it goes and a streaming decode hashes
19//! incrementally, and both compare at the end. A mismatch is
20//! [`DecodeError::Malformed`] naming the checksum field. The specification
21//! permits an all-zero checksum, which means "not known"; that is not a
22//! failure and is not treated as one.
23//!
24//! The hash is MD5 because the format says MD5. See [`md5`](crate::md5) for
25//! why substituting something stronger would remove the check rather than
26//! improve it.
27//!
28//! # The five ways a FLAC decoder is silently wrong
29//!
30//! Roughly in order of how likely each is to produce wrong audio rather than
31//! an error, which is the failure class this crate exists to avoid:
32//!
33//! - **Wasted bits.** A subframe may declare that every sample has some
34//!   number of low-order zero bits removed. Parsing the field and forgetting
35//!   to shift them back produces audio quieter by a power of two, with no
36//!   error anywhere. It is applied in [`decode_subframe`], **before** stereo
37//!   decorrelation is undone, which is the order RFC 9639 section 9.2.2
38//!   requires.
39//! - **Stereo decorrelation.** Left/side, right/side and mid/side each
40//!   reconstruct differently, and mid/side carries an odd-sample correction
41//!   that is easy to drop: an odd side sample means the mid sample lost a
42//!   least-significant bit to the right shift, and it is restored from the
43//!   side channel's low bit. See [`undo_decorrelation`].
44//! - **Integer width.** The format permits 32-bit audio, a side channel
45//!   needs 33 bits before reconstruction, and a linear prediction sums up to
46//!   32 products of a 33-bit sample and a 15-bit coefficient, 53 bits by
47//!   RFC 9639 appendix A.3's arithmetic. Every sample value and every
48//!   intermediate here is `i64`. A 32-bit intermediate would overflow only
49//!   on loud passages of deep material, which no small test file contains.
50//! - **The Rice escape code.** An all-ones Rice parameter means the
51//!   partition holds unencoded residuals at a stated width rather than
52//!   Rice-coded ones. Treating it as an ordinary parameter produces garbage
53//!   for that partition alone. See [`decode_residual`].
54//! - **The coded number.** A variable-length code that looks like UTF-8 and
55//!   is extended to 36 bits, so a UTF-8 routine cannot read it. It is
56//!   decoded by hand in [`read_coded_number`].
57//!
58//! # Both CRCs are verified
59//!
60//! The frame header carries a CRC-8 and the whole frame a CRC-16. Both are
61//! checked before any sample from that frame is delivered, and a mismatch is
62//! [`DecodeError::Malformed`] rather than audio. A decoder that decodes
63//! through a bad CRC is guessing.
64//!
65//! # A size in a file is a claim, not a fact
66//!
67//! The same discipline as [`wav`](crate::wav) and [`aiff`](crate::aiff), with
68//! one honest difference recorded rather than glossed. A FLAC frame declares
69//! its own sample count and a decoder must hold that many samples to
70//! reconstruct them, so unlike the two PCM containers there is an allocation
71//! that follows a number from the file. It is bounded twice: by the format,
72//! whose largest legal frame is 65535 samples in 8 channels, and by the
73//! streaminfo maximum block size, which RFC 9639 section 8.2 requires every
74//! frame to respect and which this reader enforces. Nothing is ever
75//! allocated from the declared *frame* size, the metadata block sizes or the
76//! total sample count.
77//!
78//! # No rate policy, and no property changes mid-stream
79//!
80//! Each frame header restates the sample rate, channel count and bit depth,
81//! and the format allows them to differ from frame to frame. This crate
82//! rejects that with a typed error rather than decoding it, because
83//! [`AudioBuffer`] carries exactly one [`AudioSpec`] for the samples it
84//! holds and there is no honest way to describe a buffer whose rate changed
85//! half way through. RFC 9639 section 9 explicitly permits a decoder to stop
86//! on such a change and recommends a real container for such streams.
87//!
88//! # Two readers, and the one difference between them
89//!
90//! [`FlacReader`] holds the whole file. [`FlacStreamDecoder`] reads one that
91//! arrives in pieces. Both drive the same frame decoder over the same bytes,
92//! so their output is identical by construction rather than by agreement.
93//! The difference is where the work happens: [`FlacReader::new`] validates
94//! the metadata only, and the audio frames are decoded by
95//! [`decode_to_end`](FlacReader::decode_to_end), which therefore returns a
96//! `Result` where [`WavReader`](crate::WavReader) and
97//! [`AiffReader`](crate::AiffReader) return the buffer directly. Those two
98//! carry linear PCM, which cannot fail once its header has parsed; a FLAC
99//! frame can.
100//!
101//! # And one writer
102//!
103//! [`FlacWriter`] writes native FLAC streams at compression levels 0
104//! through 8. It lives in this module because it must: residuals are
105//! computed by subtracting the very prediction functions the decoder adds,
106//! [`fixed_prediction`] and [`lpc_prediction`], so that the two directions
107//! cannot disagree about the arithmetic. What the writer searches and what
108//! it guarantees are recorded on the type itself.
109
110use std::ops::Range;
111
112use crate::audio::{AudioBuffer, AudioSpec};
113use crate::codec::{CodecId, FourCc};
114use crate::error::DecodeError;
115use crate::md5::Md5;
116use crate::sample::quantize;
117use crate::source::StreamSource;
118
119/// The four bytes every FLAC stream starts with.
120///
121/// Taken from [`probe`](crate::probe) rather than written again here, because
122/// the probe has to recognise a FLAC stream in a build that does not compile
123/// this module and the signature is one fact.
124const MAGIC: FourCc = crate::probe::FLAC_MAGIC;
125
126/// How many bytes a metadata block header occupies: one flag-and-type byte
127/// and a 24-bit big-endian length.
128const METADATA_HEADER_BYTES: usize = 4;
129
130/// The streaminfo metadata block type.
131const BLOCK_STREAMINFO: u8 = 0;
132
133/// The metadata block type RFC 9639 section 8.1 forbids, so that a block
134/// header can never be mistaken for a frame sync code.
135const BLOCK_FORBIDDEN: u8 = 127;
136
137/// How many bytes a streaminfo block body occupies. Fixed by the format, so
138/// a block declaring any other length is malformed rather than merely
139/// unexpected.
140const STREAMINFO_BYTES: usize = 34;
141
142/// The smallest block size the format allows, except in a stream's last
143/// frame.
144const MIN_BLOCK_SIZE: u32 = 16;
145
146/// The largest block size the format allows.
147const MAX_BLOCK_SIZE: u32 = 65_535;
148
149/// The most channels a FLAC frame can carry.
150const MAX_CHANNELS: u8 = 8;
151
152/// The highest linear predictor order the format defines.
153const MAX_LPC_ORDER: usize = 32;
154
155/// The smallest frame header, in bytes: four fixed bytes, a one-byte coded
156/// number and the CRC-8.
157const MIN_FRAME_HEADER_BYTES: usize = 6;
158
159/// The unencoded size of the largest frame the format permits, in bytes.
160///
161/// 65535 samples in 8 channels at 32 bits each, stored verbatim. A stereo
162/// frame's side subframe carries one extra bit, but two channels at 33 bits
163/// is far short of eight at 32, so this is the maximum across every legal
164/// shape.
165const MAX_VERBATIM_FRAME_BYTES: usize = MAX_BLOCK_SIZE as usize * MAX_CHANNELS as usize * (32 / 8);
166
167/// The largest frame this crate will read, in bytes.
168///
169/// [`MAX_VERBATIM_FRAME_BYTES`] plus four kilobytes, which is forty times
170/// what a frame header, eight subframe headers and the two-byte footer can
171/// occupy together. A frame larger than this cannot be one an encoder should
172/// have written: RFC 9639 section 9.2.7.3 requires an encoder that cannot
173/// code a subframe within the residual range to fall back to a verbatim
174/// subframe, so a conforming frame never exceeds its own unencoded size by
175/// more than its headers.
176///
177/// This is what bounds the streaming reader's buffer. It is a number stated
178/// here, derived from the format's own limits, and never read from a file.
179const MAX_FRAME_BYTES: usize = MAX_VERBATIM_FRAME_BYTES + 4_096;
180
181/// How many decoded samples the streaming reader holds before it stops
182/// taking bytes. The same figure, for the same reason, as every other
183/// bounded reader in the crate.
184const READY_LIMIT: usize = 65_536;
185
186/// How many bytes of interleaved samples are staged before being handed to
187/// the MD5 computation.
188///
189/// A fixed buffer rather than one frame's worth, so that hashing costs the
190/// same on a file with 65535-sample frames as on one with 16-sample frames
191/// and adds nothing to the reader's allocation ceiling.
192const MD5_STAGE_BYTES: usize = 4_096;
193
194// -- CRC ----------------------------------------------------------------------
195
196/// The CRC-8 lookup table for the polynomial `x^8 + x^2 + x^1 + x^0`, which
197/// RFC 9639 section 9.1.8 specifies for the frame header.
198const CRC8: [u8; 256] = crc8_table();
199
200/// The CRC-16 lookup table for the polynomial `x^16 + x^15 + x^2 + x^0`,
201/// which RFC 9639 section 9.3 specifies for the whole frame.
202const CRC16: [u16; 256] = crc16_table();
203
204/// Builds [`CRC8`] at compile time from the polynomial itself.
205///
206/// The table is derived rather than transcribed so there is one place the
207/// polynomial appears and no 256 constants for a typo to hide in.
208const fn crc8_table() -> [u8; 256] {
209    let mut table = [0u8; 256];
210    let mut index = 0;
211    while index < 256 {
212        let mut crc = index as u8;
213        let mut bit = 0;
214        while bit < 8 {
215            crc = if crc & 0x80 != 0 {
216                (crc << 1) ^ 0x07
217            } else {
218                crc << 1
219            };
220            bit += 1;
221        }
222        table[index] = crc;
223        index += 1;
224    }
225    table
226}
227
228/// Builds [`CRC16`] at compile time from the polynomial itself.
229const fn crc16_table() -> [u16; 256] {
230    let mut table = [0u16; 256];
231    let mut index = 0;
232    while index < 256 {
233        let mut crc = (index as u16) << 8;
234        let mut bit = 0;
235        while bit < 8 {
236            crc = if crc & 0x8000 != 0 {
237                (crc << 1) ^ 0x8005
238            } else {
239                crc << 1
240            };
241            bit += 1;
242        }
243        table[index] = crc;
244        index += 1;
245    }
246    table
247}
248
249/// The CRC-8 of `bytes`, initialised with zero.
250fn crc8(bytes: &[u8]) -> u8 {
251    bytes
252        .iter()
253        .fold(0u8, |crc, byte| CRC8[usize::from(crc ^ byte)])
254}
255
256/// The CRC-16 of `bytes`, initialised with zero.
257fn crc16(bytes: &[u8]) -> u16 {
258    bytes.iter().fold(0u16, |crc, byte| {
259        (crc << 8) ^ CRC16[usize::from((crc >> 8) as u8 ^ byte)]
260    })
261}
262
263// -- The bit reader -----------------------------------------------------------
264
265/// How many bits of the next 64 a window is guaranteed to expose.
266///
267/// A window is eight bytes read big-endian and shifted left by the bit
268/// offset within the first of them, so up to seven bits fall off the top.
269/// Every read below is of at most 33 bits, comfortably inside this.
270const WINDOW_BITS: u32 = 57;
271
272/// A most-significant-bit-first reader over a frame's bytes.
273///
274/// FLAC subframes are not byte aligned, and only the first subframe in a
275/// frame starts on a byte boundary, so everything past the frame header is read
276/// bit by bit. Every read is bounds-checked against the bytes that actually
277/// arrived, never against a length the file declared.
278struct BitReader<'a> {
279    /// The frame's bytes, starting at its first byte.
280    bytes: &'a [u8],
281    /// How many bits have been consumed from the start of `bytes`.
282    bit: usize,
283    /// Where `bytes[0]` sits in the whole input, so a rejection can name an
284    /// absolute offset.
285    base: u64,
286}
287
288impl<'a> BitReader<'a> {
289    /// A reader positioned at the first bit of `bytes`.
290    fn new(bytes: &'a [u8], base: u64) -> Self {
291        Self {
292            bytes,
293            bit: 0,
294            base,
295        }
296    }
297
298    /// How many bits have not been consumed.
299    fn bits_left(&self) -> usize {
300        (self.bytes.len() * 8).saturating_sub(self.bit)
301    }
302
303    /// The next 64 bits, left-aligned and zero-padded past the end of the
304    /// input.
305    ///
306    /// Only the top [`WINDOW_BITS`] are meaningful; the rest may have been
307    /// shifted out. Padding past the end is safe because every caller checks
308    /// [`bits_left`](Self::bits_left) first.
309    fn window(&self) -> u64 {
310        let byte = self.bit >> 3;
311        let shift = (self.bit & 7) as u32;
312        let mut buffer = [0u8; 8];
313        let take = self.bytes.len().saturating_sub(byte).min(8);
314        buffer[..take].copy_from_slice(&self.bytes[byte..byte + take]);
315        u64::from_be_bytes(buffer) << shift
316    }
317
318    /// The next `count` bits as an unsigned number. `count` is at most
319    /// [`WINDOW_BITS`].
320    fn read_bits(&mut self, count: u32) -> Result<u64, DecodeError> {
321        debug_assert!((1..=WINDOW_BITS).contains(&count));
322        if self.bits_left() < count as usize {
323            return Err(self.truncated(count as usize));
324        }
325        let value = self.window() >> (64 - count);
326        self.bit += count as usize;
327        Ok(value)
328    }
329
330    /// The next `count` bits as a two's-complement signed number.
331    fn read_signed(&mut self, count: u32) -> Result<i64, DecodeError> {
332        let raw = self.read_bits(count)?;
333        // Landing the value in the top of an i64 and shifting back
334        // arithmetically sign-extends it without a branch or a mask.
335        Ok(((raw << (64 - count)) as i64) >> (64 - count))
336    }
337
338    /// How many zero bits precede the next one bit, consuming both.
339    fn read_unary(&mut self) -> Result<u32, DecodeError> {
340        let mut zeros = 0u32;
341        loop {
342            let window = self.window();
343            if window == 0 {
344                // No one bit within reach. Step over the zeros that are
345                // really there and look again.
346                let step = self.bits_left().min(WINDOW_BITS as usize);
347                if step == 0 {
348                    return Err(self.truncated(1));
349                }
350                zeros = zeros.saturating_add(step as u32);
351                self.bit += step;
352                continue;
353            }
354            let run = window.leading_zeros() as usize;
355            if run >= self.bits_left() {
356                // The one bit is in the zero padding past the end, which
357                // means it has not arrived.
358                return Err(self.truncated(run + 1));
359            }
360            self.bit += run + 1;
361            return Ok(zeros.saturating_add(run as u32));
362        }
363    }
364
365    /// Steps forward to the next byte boundary, which RFC 9639 section 9.3
366    /// requires before the frame footer.
367    fn align_to_byte(&mut self) {
368        self.bit = (self.bit + 7) & !7;
369    }
370
371    /// How many whole bytes have been consumed. Only meaningful when the
372    /// reader is byte aligned.
373    fn byte_position(&self) -> usize {
374        self.bit >> 3
375    }
376
377    /// A rejection saying the frame needed more bytes than arrived.
378    ///
379    /// `expected` counts from the **start of the frame** rather than the
380    /// start of the input, because the incomplete item is the frame. The
381    /// streaming reader uses the number directly as "do not try again until
382    /// this many bytes of this frame are held".
383    fn truncated(&self, more_bits: usize) -> DecodeError {
384        DecodeError::Truncated {
385            expected: self.bit.saturating_add(more_bits).div_ceil(8) as u64,
386            available: self.bytes.len() as u64,
387        }
388    }
389
390    /// A rejection naming what the format required at the current position.
391    fn malformed(&self, expected: &'static str) -> DecodeError {
392        DecodeError::Malformed {
393            expected,
394            offset: self.base + (self.bit >> 3) as u64,
395        }
396    }
397}
398
399// -- Streaminfo ---------------------------------------------------------------
400
401/// What a FLAC stream's streaminfo metadata block declares.
402///
403/// RFC 9639 section 8.2's fields, read as they were written. Two of them are
404/// `Option` rather than the zero the format stores, because zero means "not
405/// known" for both, and a caller that could not tell an unknown length from
406/// an empty stream would be facing exactly the ambiguity the `Option` exists
407/// to avoid: `Some(0)` is an empty stream, `None` is a length the stream did
408/// not state.
409///
410/// `#[non_exhaustive]`: a consumer matching on it keeps a `..` rest pattern,
411/// and building one from a block a container carried goes through
412/// [`from_block`](Self::from_block).
413#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
414#[non_exhaustive]
415pub struct FlacStreamInfo {
416    /// The smallest block size in the stream, in interchannel samples,
417    /// excluding the last block.
418    pub min_block_size: u16,
419    /// The largest block size in the stream, in interchannel samples.
420    ///
421    /// Not advisory: RFC 9639 section 8.2 requires every frame to respect
422    /// it, and this crate rejects a frame that does not, which is also what
423    /// keeps the decode buffer bounded by something the format guarantees.
424    pub max_block_size: u16,
425    /// The smallest frame size in the stream, in bytes, or `None` when the
426    /// field is the zero that means unknown.
427    pub min_frame_size: Option<u32>,
428    /// The largest frame size in the stream, in bytes, or `None` when the
429    /// field is the zero that means unknown.
430    ///
431    /// Read and reported, and deliberately never allocated against.
432    pub max_frame_size: Option<u32>,
433    /// The rate and layout the stream decodes to.
434    pub spec: AudioSpec,
435    /// Bits per sample, between 4 and 32.
436    pub bits_per_sample: u8,
437    /// Total interchannel samples in the stream, or `None` when the field is
438    /// the zero that means unknown.
439    pub total_samples: Option<u64>,
440    /// The MD5 of the stream's unencoded audio, or `None` when the field is
441    /// the all-zero value that means unset.
442    ///
443    /// `None` is not a failure and does not weaken anything else: a file may
444    /// legitimately omit it, in which case there is simply no oracle for that
445    /// file and the CRCs remain.
446    pub md5: Option<[u8; 16]>,
447}
448
449impl FlacStreamInfo {
450    /// Parses the 34-byte **body** of a streaminfo metadata block, which is
451    /// how a container supplies one out of band.
452    ///
453    /// This is the constructor for the Ogg and Matroska shape: the container
454    /// carries the streaminfo block in its own codec-private header and hands
455    /// over bare frames, so the block has to become a [`FlacStreamInfo`] for
456    /// [`FlacFrameReader::with_stream_info`],
457    /// [`FlacStreamDecoder::frames_with_stream_info`] or
458    /// [`FlacRecovery::with_stream_info`] to take. The struct is
459    /// `#[non_exhaustive]`, so this is the one way to build one without a
460    /// whole stream in hand.
461    ///
462    /// The 34 bytes are RFC 9639 section 8.2's block body alone, **without**
463    /// the four-byte metadata block header (`0x00` or `0x80`, then a 24-bit
464    /// length of 34) in front of it. Where a caller finds them:
465    ///
466    /// - **Matroska** (the WebM and MKV FLAC mapping): `CodecPrivate` holds
467    ///   what a FLAC file starts with, the `fLaC` signature and then the
468    ///   metadata blocks, streaminfo required first. The body is bytes
469    ///   `8..42` of `CodecPrivate`.
470    /// - **Ogg** (the Ogg FLAC mapping): the first packet is a nine-byte
471    ///   prologue (`0x7F`, `FLAC`, two version bytes, a two-byte header
472    ///   packet count), the `fLaC` signature, then the streaminfo block. The
473    ///   body is bytes `17..51`, the last 34 of the 51-byte packet.
474    ///
475    /// # Errors
476    ///
477    /// [`DecodeError::Malformed`] when the slice is not exactly 34 bytes,
478    /// when either block size is below the format's minimum of 16 or the
479    /// minimum exceeds the maximum, when the sample rate is zero, or when
480    /// the bit depth is outside 4 through 32. Offsets in the error count
481    /// from the start of the body.
482    ///
483    /// # Example
484    ///
485    /// RFC 9639 appendix D.3's worked example taken apart the way Matroska
486    /// carries it: the streaminfo body from what would be `CodecPrivate`,
487    /// the bare frame from the packets.
488    ///
489    /// ```
490    /// use decibri_decode::{FlacFrameReader, FlacStreamInfo, Md5Check};
491    ///
492    /// # let file: [u8; 73] = [
493    /// #     0x66, 0x4c, 0x61, 0x43, 0x80, 0x00, 0x00, 0x22, 0x10, 0x00, 0x10, 0x00,
494    /// #     0x00, 0x00, 0x1f, 0x00, 0x00, 0x1f, 0x07, 0xd0, 0x00, 0x70, 0x00, 0x00,
495    /// #     0x00, 0x18, 0xf8, 0xf9, 0xe3, 0x96, 0xf5, 0xcb, 0xcf, 0xc6, 0xdc, 0x80,
496    /// #     0x7f, 0x99, 0x77, 0x90, 0x6b, 0x32, 0xff, 0xf8, 0x68, 0x02, 0x00, 0x17,
497    /// #     0xe9, 0x44, 0x00, 0x4f, 0x6f, 0x31, 0x3d, 0x10, 0x47, 0xd2, 0x27, 0xcb,
498    /// #     0x6d, 0x09, 0x08, 0x31, 0x45, 0x2b, 0xdc, 0x28, 0x22, 0x22, 0x80, 0x57,
499    /// #     0xa3,
500    /// # ];
501    /// let info = FlacStreamInfo::from_block(&file[8..42])?;
502    /// assert_eq!(info.spec.sample_rate, 32_000);
503    /// assert_eq!(info.total_samples, Some(24));
504    ///
505    /// let mut samples = Vec::new();
506    /// let report = FlacFrameReader::with_stream_info(&file[42..], info).decode(&mut samples)?;
507    /// assert_eq!(report.samples, 24);
508    /// // The block carries the MD5, so the bare frames were verified.
509    /// assert_eq!(report.md5, Md5Check::Verified);
510    /// # Ok::<(), decibri_decode::DecodeError>(())
511    /// ```
512    pub fn from_block(body: &[u8]) -> Result<Self, DecodeError> {
513        parse_streaminfo(body, 0)
514    }
515
516    /// How many bytes one sample occupies once sign-extended to a whole
517    /// number of bytes, which is the form RFC 9639 section 8.2 hashes.
518    fn md5_bytes_per_sample(&self) -> usize {
519        usize::from(self.bits_per_sample).div_ceil(8)
520    }
521}
522
523/// Reads a streaminfo block body, which is always exactly
524/// [`STREAMINFO_BYTES`] long.
525///
526/// `offset` is where the body sits in the input, so rejections name an
527/// absolute position.
528fn parse_streaminfo(body: &[u8], offset: u64) -> Result<FlacStreamInfo, DecodeError> {
529    let malformed = |expected| DecodeError::Malformed { expected, offset };
530    if body.len() != STREAMINFO_BYTES {
531        return Err(malformed("a streaminfo block of exactly 34 bytes"));
532    }
533    let mut reader = BitReader::new(body, offset);
534
535    let min_block_size = reader.read_bits(16)? as u16;
536    let max_block_size = reader.read_bits(16)? as u16;
537    let min_frame_size = reader.read_bits(24)? as u32;
538    let max_frame_size = reader.read_bits(24)? as u32;
539    let sample_rate = reader.read_bits(20)? as u32;
540    let channels = reader.read_bits(3)? as u16 + 1;
541    let bits_per_sample = reader.read_bits(5)? as u8 + 1;
542    let total_samples = reader.read_bits(36)?;
543    let mut md5 = [0u8; 16];
544    md5.copy_from_slice(&body[18..34]);
545
546    // RFC 9639 section 8.2: both block sizes are in 16..=65535 and the
547    // minimum does not exceed the maximum.
548    if u32::from(min_block_size) < MIN_BLOCK_SIZE || u32::from(max_block_size) < MIN_BLOCK_SIZE {
549        return Err(malformed("a streaminfo block size of at least 16 samples"));
550    }
551    if min_block_size > max_block_size {
552        return Err(malformed(
553            "a streaminfo minimum block size no larger than the maximum",
554        ));
555    }
556    // A rate of zero is legal in the format and means the content is not
557    // audio along a time axis. This crate decodes audio, and an AudioSpec
558    // carrying a rate of zero would be a wrong rate travelling with real
559    // samples, the failure AudioSpec exists to prevent. Rejected, named.
560    if sample_rate == 0 {
561        return Err(malformed("a streaminfo sample rate above zero"));
562    }
563    if !(4..=32).contains(&bits_per_sample) {
564        return Err(malformed("a streaminfo bit depth between 4 and 32"));
565    }
566
567    Ok(FlacStreamInfo {
568        min_block_size,
569        max_block_size,
570        min_frame_size: (min_frame_size != 0).then_some(min_frame_size),
571        max_frame_size: (max_frame_size != 0).then_some(max_frame_size),
572        spec: AudioSpec::new(sample_rate, channels),
573        bits_per_sample,
574        total_samples: (total_samples != 0).then_some(total_samples),
575        md5: (md5 != [0u8; 16]).then_some(md5),
576    })
577}
578
579// -- The frame header ---------------------------------------------------------
580
581/// How a stream divides its samples into frames.
582///
583/// RFC 9639 section 9.1: the bit that says which MUST NOT change during a
584/// stream, and this crate enforces that.
585#[derive(Debug, Clone, Copy, PartialEq, Eq)]
586enum Blocking {
587    /// Every frame but the last holds the same number of samples, and the
588    /// coded number is a frame number.
589    Fixed,
590    /// Frames may hold different numbers of samples, and the coded number is
591    /// a sample number.
592    Variable,
593}
594
595/// How a frame's subframes map onto its channels.
596#[derive(Debug, Clone, Copy, PartialEq, Eq)]
597enum ChannelAssignment {
598    /// Every channel is coded on its own. The only legal form above two
599    /// channels.
600    Independent(u8),
601    /// Two channels stored as left and (left - right).
602    LeftSide,
603    /// Two channels stored as (left - right) and right.
604    SideRight,
605    /// Two channels stored as ((left + right) >> 1) and (left - right).
606    MidSide,
607}
608
609impl ChannelAssignment {
610    /// How many channels the frame carries.
611    const fn count(self) -> u8 {
612        match self {
613            Self::Independent(channels) => channels,
614            Self::LeftSide | Self::SideRight | Self::MidSide => 2,
615        }
616    }
617
618    /// Which subframe, if any, carries the side channel and therefore one
619    /// extra bit of depth.
620    const fn side_channel(self) -> Option<usize> {
621        match self {
622            Self::Independent(_) => None,
623            Self::LeftSide | Self::MidSide => Some(1),
624            Self::SideRight => Some(0),
625        }
626    }
627}
628
629/// A parsed frame header.
630#[derive(Debug, Clone, Copy)]
631struct FrameHeader {
632    blocking: Blocking,
633    /// Samples per channel in this frame.
634    block_size: u32,
635    /// The rate this frame declares, or `None` when it defers to streaminfo.
636    sample_rate: Option<u32>,
637    channels: ChannelAssignment,
638    /// The bit depth this frame declares, or `None` when it defers to
639    /// streaminfo.
640    bits_per_sample: Option<u8>,
641    /// The frame or sample number this frame carries, which
642    /// [`Blocking`] says which of the two it is.
643    ///
644    /// Nothing in an ordinary decode reads it, since the samples arrive in order
645    /// and a decoder that trusted it would be trusting a number in a file.
646    /// [`FlacRecovery`] reads it, because after a gap it is the only thing in
647    /// the stream that says *where* decoding resumed.
648    coded_number: u64,
649    /// How many bytes the header occupies, including the CRC-8.
650    header_bytes: usize,
651}
652
653/// Reads the frame or sample number, which RFC 9639 section 9.1.5 codes in a
654/// UTF-8-like variable-length form extended to 36 bits.
655///
656/// **Not UTF-8**, and not decodable by a UTF-8 routine: the encoding runs to
657/// seven octets and codes numbers rather than characters. Written out by
658/// hand for exactly that reason.
659///
660/// Overlong encodings, a value spelled in more octets than it needs, are
661/// accepted. The specification's table gives a range per length but does not
662/// say a decoder must reject a value outside its range, the number is not
663/// used for anything here, and rejecting real files over a bookkeeping field
664/// costs compatibility for nothing.
665fn read_coded_number(reader: &mut BitReader<'_>) -> Result<u64, DecodeError> {
666    let first = reader.read_bits(8)? as u8;
667    let (continuations, mut value) = match first.leading_ones() {
668        0 => (0, u64::from(first)),
669        // 0b10xxxxxx is a continuation octet and cannot start a code.
670        1 => return Err(reader.malformed("a coded number not starting with a continuation octet")),
671        leading @ 2..=7 => {
672            let payload = 7 - leading;
673            (
674                leading - 1,
675                u64::from(first & ((1u8 << payload).wrapping_sub(1))),
676            )
677        }
678        // 0b11111111 is not a length this encoding defines.
679        _ => return Err(reader.malformed("a coded number of at most seven octets")),
680    };
681    for _ in 0..continuations {
682        let octet = reader.read_bits(8)? as u8;
683        if octet & 0xC0 != 0x80 {
684            return Err(reader.malformed("a coded number continuation octet"));
685        }
686        value = (value << 6) | u64::from(octet & 0x3F);
687    }
688    Ok(value)
689}
690
691/// Reads a frame header from the start of `bytes` and verifies its CRC-8.
692///
693/// Every rejection here is structural: the sync code, a reserved value, the
694/// reserved bit, or the CRC. Nothing is checked against streaminfo yet, so
695/// this function is usable on a frame in isolation.
696fn parse_frame_header(bytes: &[u8], base: u64) -> Result<FrameHeader, DecodeError> {
697    if bytes.len() < MIN_FRAME_HEADER_BYTES {
698        return Err(DecodeError::Truncated {
699            expected: MIN_FRAME_HEADER_BYTES as u64,
700            available: bytes.len() as u64,
701        });
702    }
703    let mut reader = BitReader::new(bytes, base);
704
705    // The 15-bit sync code, then the blocking strategy bit.
706    if reader.read_bits(15)? != 0b111_1111_1111_1100 {
707        return Err(reader.malformed("a frame sync code"));
708    }
709    let blocking = if reader.read_bits(1)? == 0 {
710        Blocking::Fixed
711    } else {
712        Blocking::Variable
713    };
714
715    let block_size_bits = reader.read_bits(4)? as u8;
716    let sample_rate_bits = reader.read_bits(4)? as u8;
717    let channel_bits = reader.read_bits(4)? as u8;
718    let bit_depth_bits = reader.read_bits(3)? as u8;
719    if reader.read_bits(1)? != 0 {
720        return Err(reader.malformed("a cleared reserved bit in the frame header"));
721    }
722
723    let channels = match channel_bits {
724        0..=7 => ChannelAssignment::Independent(channel_bits + 1),
725        8 => ChannelAssignment::LeftSide,
726        9 => ChannelAssignment::SideRight,
727        10 => ChannelAssignment::MidSide,
728        _ => return Err(reader.malformed("a defined channel assignment")),
729    };
730    let bits_per_sample = match bit_depth_bits {
731        0 => None,
732        1 => Some(8),
733        2 => Some(12),
734        4 => Some(16),
735        5 => Some(20),
736        6 => Some(24),
737        7 => Some(32),
738        // 0b011 is reserved.
739        _ => return Err(reader.malformed("a defined bit depth")),
740    };
741    let block_size = match block_size_bits {
742        0 => return Err(reader.malformed("a block size other than the reserved 0b0000")),
743        1 => Some(192),
744        2..=5 => Some(144u32 << block_size_bits),
745        // 0b0110 and 0b0111 store the real value after the coded number.
746        6 | 7 => None,
747        _ => Some(1u32 << block_size_bits),
748    };
749
750    // The coded number comes before the uncommon block size and sample rate,
751    // which is the one ordering trap in the header layout.
752    let coded_number = read_coded_number(&mut reader)?;
753
754    let block_size = match block_size {
755        Some(size) => size,
756        None => {
757            let width = if block_size_bits == 6 { 8 } else { 16 };
758            let stored = reader.read_bits(width)? as u32;
759            // 65535 codes for a block size of 65536, which streaminfo cannot
760            // represent, so RFC 9639 section 9.1.6 forbids it.
761            if stored == 65_535 {
762                return Err(reader.malformed("a block size representable in streaminfo"));
763            }
764            stored + 1
765        }
766    };
767
768    let sample_rate = match sample_rate_bits {
769        0 => None,
770        1 => Some(88_200),
771        2 => Some(176_400),
772        3 => Some(192_000),
773        4 => Some(8_000),
774        5 => Some(16_000),
775        6 => Some(22_050),
776        7 => Some(24_000),
777        8 => Some(32_000),
778        9 => Some(44_100),
779        10 => Some(48_000),
780        11 => Some(96_000),
781        12 => Some(reader.read_bits(8)? as u32 * 1_000),
782        13 => Some(reader.read_bits(16)? as u32),
783        14 => Some(reader.read_bits(16)? as u32 * 10),
784        _ => return Err(reader.malformed("a sample rate other than the forbidden 0b1111")),
785    };
786
787    let header_bytes = reader.byte_position();
788    let stored_crc = reader.read_bits(8)? as u8;
789    if crc8(&bytes[..header_bytes]) != stored_crc {
790        return Err(DecodeError::Malformed {
791            expected: "a frame header whose CRC-8 matches its contents",
792            offset: base + header_bytes as u64,
793        });
794    }
795
796    Ok(FrameHeader {
797        blocking,
798        block_size,
799        sample_rate,
800        channels,
801        bits_per_sample,
802        coded_number,
803        header_bytes: header_bytes + 1,
804    })
805}
806
807/// What a frame header codes when it says a field comes from streaminfo, and
808/// there is no streaminfo.
809///
810/// RFC 9639 section 9.1.4's sample rate code `0b0000` and section 9.1.3's bit
811/// depth code `0b000` both mean "take this from the streaminfo block". A bare
812/// frame stream has no streaminfo block, so neither is resolvable and neither
813/// is guessed: the strings below are what the rejection names.
814const UNRESOLVED_RATE: &str =
815    "a frame sample rate, or a streaminfo block to resolve the sample rate code 0b0000";
816/// The bit depth half of [`UNRESOLVED_RATE`].
817const UNRESOLVED_DEPTH: &str =
818    "a frame bit depth, or a streaminfo block to resolve the bit depth code 0b000";
819
820/// Builds the stream description a bare frame stream never carried, out of
821/// the first frame's own header.
822///
823/// FLAC frames are self-describing: each header restates the sample rate,
824/// channel assignment and bit depth, so for a stream whose first frame states
825/// all three this is a read rather than a guess. The two escape codes above
826/// are the exception and are rejected by name.
827///
828/// Two fields cannot be derived and are not invented. `max_block_size` is the
829/// format's own 65,535 rather than anything this stream promises, because a
830/// bare stream makes no promise and a later frame may be larger than the
831/// first; that is what bounds the decode buffer here, and it is the one place
832/// in this crate where a ceiling follows a specification limit rather than
833/// the bytes that arrived. `total_samples` and `md5` are `None`, which is
834/// what makes [`Md5Check::NoStreamInfo`] the honest answer for this path.
835fn derive_stream_info(header: &FrameHeader, base: u64) -> Result<FlacStreamInfo, DecodeError> {
836    let Some(sample_rate) = header.sample_rate else {
837        return Err(DecodeError::Malformed {
838            expected: UNRESOLVED_RATE,
839            offset: base,
840        });
841    };
842    let Some(bits_per_sample) = header.bits_per_sample else {
843        return Err(DecodeError::Malformed {
844            expected: UNRESOLVED_DEPTH,
845            offset: base,
846        });
847    };
848    Ok(FlacStreamInfo {
849        min_block_size: MIN_BLOCK_SIZE as u16,
850        max_block_size: MAX_BLOCK_SIZE as u16,
851        min_frame_size: None,
852        max_frame_size: None,
853        spec: AudioSpec::new(sample_rate, u16::from(header.channels.count())),
854        bits_per_sample,
855        total_samples: None,
856        md5: None,
857    })
858}
859
860// -- Prediction arithmetic, shared by the decoder and the encoder -------------
861
862/// The fixed predictor of `order` applied to the samples before `prior`'s
863/// end: what RFC 9639 section 9.2.5 says the next sample is expected to be.
864///
865/// **This is the one statement of the fixed prediction arithmetic in the
866/// crate, and both directions go through it.** The decoder adds a residual to
867/// this value; the encoder subtracts this value from a sample. If the two
868/// used separate arithmetic, an encoder bug could produce streams this
869/// crate's own decoder reconstructs incorrectly yet round-trips perfectly,
870/// which is coverage lesson 3 exactly: one rule, two implementations, and a
871/// control on either says nothing about the other.
872///
873/// The predictors are written out per order rather than folded into a
874/// coefficient loop: they are five fixed polynomials, and a table of them
875/// would be a table nobody could check against the specification at a
876/// glance.
877///
878/// Wrapping for the reason recorded on [`decode_fixed`]: a corrupted stream
879/// can drive the recursion without limit, and the CRC-16 that rejects the
880/// frame is checked after the subframes are decoded.
881fn fixed_prediction(prior: &[i64], order: usize) -> i64 {
882    let at = prior.len();
883    let previous = |back: usize| prior[at - back];
884    match order {
885        0 => 0,
886        1 => previous(1),
887        2 => previous(1).wrapping_mul(2).wrapping_sub(previous(2)),
888        3 => previous(1)
889            .wrapping_mul(3)
890            .wrapping_sub(previous(2).wrapping_mul(3))
891            .wrapping_add(previous(3)),
892        _ => previous(1)
893            .wrapping_mul(4)
894            .wrapping_sub(previous(2).wrapping_mul(6))
895            .wrapping_add(previous(3).wrapping_mul(4))
896            .wrapping_sub(previous(4)),
897    }
898}
899
900/// The linear prediction of the sample after `prior`'s end, from quantised
901/// `coefficients` and their right `shift`: RFC 9639 section 9.2.6's sum,
902/// shifted.
903///
904/// **The one statement of the LPC arithmetic in the crate**, for the same
905/// reason as [`fixed_prediction`], and the more important of the two: an
906/// encoder that predicted in floating point and quantised afterwards would
907/// produce streams that decode to something slightly different, passing on
908/// quiet material and failing on loud material at high bit depths, which no
909/// small test file catches.
910///
911/// The coefficients are ordered as the bitstream orders them: the first
912/// belongs to the sample immediately before the one being predicted.
913/// i64 throughout: a 33-bit side sample times a 15-bit coefficient, summed
914/// 32 times, needs 53 bits by RFC 9639 appendix A.3. Wrapping for the reason
915/// recorded on [`decode_fixed`].
916fn lpc_prediction(coefficients: &[i64], prior: &[i64], shift: u32) -> i64 {
917    let at = prior.len();
918    let mut prediction = 0i64;
919    for (step, coefficient) in coefficients.iter().enumerate() {
920        prediction = prediction.wrapping_add(coefficient.wrapping_mul(prior[at - 1 - step]));
921    }
922    prediction >> shift
923}
924
925// -- Subframes ----------------------------------------------------------------
926
927/// Decodes one subframe's `dst.len()` samples at `bits` bits of depth.
928///
929/// `bits` is the frame's bit depth, already increased by one where this
930/// subframe carries the side channel. Wasted bits are subtracted from it for
931/// the coded values and shifted back on before returning, which is the order
932/// RFC 9639 section 9.2.2 requires and the one that keeps stereo
933/// reconstruction lossless.
934fn decode_subframe(
935    reader: &mut BitReader<'_>,
936    bits: u32,
937    dst: &mut [i64],
938) -> Result<(), DecodeError> {
939    if reader.read_bits(1)? != 0 {
940        return Err(reader.malformed("a cleared leading bit in the subframe header"));
941    }
942    let subframe_type = reader.read_bits(6)? as u8;
943    let wasted = if reader.read_bits(1)? == 0 {
944        0
945    } else {
946        // The count minus one, in unary.
947        reader.read_unary()?.saturating_add(1)
948    };
949    if wasted >= bits {
950        return Err(reader.malformed("fewer wasted bits than the subframe's bit depth"));
951    }
952    let coded_bits = bits - wasted;
953
954    match subframe_type {
955        0 => {
956            let value = reader.read_signed(coded_bits)?;
957            dst.fill(value);
958        }
959        1 => {
960            for sample in dst.iter_mut() {
961                *sample = reader.read_signed(coded_bits)?;
962            }
963        }
964        8..=12 => decode_fixed(reader, coded_bits, usize::from(subframe_type - 8), dst)?,
965        32..=63 => decode_lpc(reader, coded_bits, usize::from(subframe_type - 31), dst)?,
966        _ => return Err(reader.malformed("a defined subframe type")),
967    }
968
969    if wasted > 0 {
970        for sample in dst.iter_mut() {
971            *sample <<= wasted;
972        }
973    }
974    Ok(())
975}
976
977/// Decodes a fixed-predictor subframe of `order`, which is 0 through 4.
978///
979/// The prediction itself is [`fixed_prediction`], the one statement of that
980/// arithmetic in the crate, which the encoder also subtracts through.
981///
982/// # Why the arithmetic wraps
983///
984/// For a conforming stream it cannot: RFC 9639 appendix A.3 bounds a
985/// fourth-order prediction over 32-bit audio at 36 bits, and every value
986/// here is `i64`. For a *corrupted* one it can, because a frame whose
987/// residuals were scrambled in transit drives the recursion without limit, and
988/// CRC-16 that rejects the frame is checked after the subframes are decoded,
989/// not before. Wrapping is defined behaviour that the CRC then catches;
990/// a checked `+` would be a panic on untrusted input, which is the one
991/// failure this crate refuses outright. The same reasoning applies to
992/// [`decode_lpc`] and [`undo_decorrelation`].
993fn decode_fixed(
994    reader: &mut BitReader<'_>,
995    bits: u32,
996    order: usize,
997    dst: &mut [i64],
998) -> Result<(), DecodeError> {
999    if order > dst.len() {
1000        return Err(reader.malformed("a predictor order no larger than the block size"));
1001    }
1002    for sample in dst.iter_mut().take(order) {
1003        *sample = reader.read_signed(bits)?;
1004    }
1005    decode_residual(reader, order, dst)?;
1006
1007    for index in order..dst.len() {
1008        let prediction = fixed_prediction(&dst[..index], order);
1009        dst[index] = dst[index].wrapping_add(prediction);
1010    }
1011    Ok(())
1012}
1013
1014/// Decodes a linear-predictor subframe of `order`, which is 1 through 32.
1015///
1016/// The coefficients appear in the bitstream in the order of the *past
1017/// samples* they multiply, which is the reverse of chronological order: the
1018/// first coefficient belongs to the sample immediately before the one being
1019/// predicted. Getting that backwards produces plausible-looking audio that
1020/// is wrong everywhere, so it is worth stating twice.
1021fn decode_lpc(
1022    reader: &mut BitReader<'_>,
1023    bits: u32,
1024    order: usize,
1025    dst: &mut [i64],
1026) -> Result<(), DecodeError> {
1027    if order > dst.len() {
1028        return Err(reader.malformed("a predictor order no larger than the block size"));
1029    }
1030    for sample in dst.iter_mut().take(order) {
1031        *sample = reader.read_signed(bits)?;
1032    }
1033
1034    let precision = reader.read_bits(4)? as u32 + 1;
1035    if precision > 15 {
1036        return Err(reader.malformed("a coefficient precision other than the forbidden 0b1111"));
1037    }
1038    // The shift is stored two's complement and RFC 9639 appendix B.4 says it
1039    // must not be negative. A negative shift would be a left shift, which no
1040    // encoder since the field was defined has written.
1041    let shift = reader.read_signed(5)?;
1042    if shift < 0 {
1043        return Err(reader.malformed("a non-negative predictor right shift"));
1044    }
1045    let shift = shift as u32;
1046
1047    let mut coefficients = [0i64; MAX_LPC_ORDER];
1048    for coefficient in coefficients.iter_mut().take(order) {
1049        *coefficient = reader.read_signed(precision)?;
1050    }
1051
1052    decode_residual(reader, order, dst)?;
1053
1054    for index in order..dst.len() {
1055        let prediction = lpc_prediction(&coefficients[..order], &dst[..index], shift);
1056        dst[index] = dst[index].wrapping_add(prediction);
1057    }
1058    Ok(())
1059}
1060
1061/// Decodes the coded residual into `dst[order..]`.
1062///
1063/// RFC 9639 section 9.2.7. The partitioning arithmetic is the part that has
1064/// to be exact: the first partition is short by the predictor order, because
1065/// those samples were stored unencoded as warm-up.
1066fn decode_residual(
1067    reader: &mut BitReader<'_>,
1068    order: usize,
1069    dst: &mut [i64],
1070) -> Result<(), DecodeError> {
1071    let parameter_bits = match reader.read_bits(2)? {
1072        0 => 4u32,
1073        1 => 5,
1074        _ => return Err(reader.malformed("a defined residual coding method")),
1075    };
1076    let escape = (1u64 << parameter_bits) - 1;
1077    let partition_order = reader.read_bits(4)? as u32;
1078    let partitions = 1usize << partition_order;
1079
1080    let block_size = dst.len();
1081    if !block_size.is_multiple_of(partitions) {
1082        return Err(reader.malformed("a block size divisible by the partition count"));
1083    }
1084    let per_partition = block_size >> partition_order;
1085    if per_partition <= order {
1086        return Err(reader.malformed("a partition longer than the predictor order"));
1087    }
1088
1089    let mut at = order;
1090    for partition in 0..partitions {
1091        let count = if partition == 0 {
1092            per_partition - order
1093        } else {
1094            per_partition
1095        };
1096        let parameter = reader.read_bits(parameter_bits)?;
1097
1098        if parameter == escape {
1099            // An escaped partition holds unencoded residuals at a stated
1100            // width. A width of zero means every residual in it is zero and
1101            // no bits at all are stored.
1102            let width = reader.read_bits(5)? as u32;
1103            if width == 0 {
1104                dst[at..at + count].fill(0);
1105            } else {
1106                for sample in &mut dst[at..at + count] {
1107                    *sample = reader.read_signed(width)?;
1108                }
1109            }
1110        } else {
1111            let parameter = parameter as u32;
1112            for sample in &mut dst[at..at + count] {
1113                let high = u64::from(reader.read_unary()?);
1114                let folded = if parameter == 0 {
1115                    high
1116                } else {
1117                    (high << parameter) | reader.read_bits(parameter)?
1118                };
1119                // RFC 9639 section 9.2.7.3 bounds every residual to a 32-bit
1120                // one's-complement range, so the folded value fits 32 bits
1121                // and cannot be the one that folds to -2^31.
1122                if folded > u64::from(u32::MAX) - 1 {
1123                    return Err(reader.malformed("a residual within the format's 32-bit range"));
1124                }
1125                // Zigzag: even folds to itself halved, odd folds to the
1126                // negative of half the next value up.
1127                *sample = ((folded >> 1) as i64) ^ -((folded & 1) as i64);
1128            }
1129        }
1130        at += count;
1131    }
1132    Ok(())
1133}
1134
1135// -- Stereo decorrelation -----------------------------------------------------
1136
1137/// Restores left and right from whichever pair of channels the frame stored.
1138///
1139/// `left` and `right` are the two subframes as decoded, in bitstream order,
1140/// and are replaced in place. RFC 9639 section 4.2.
1141///
1142/// The mid/side case is the one that is commonly got wrong. A mid sample is
1143/// `(left + right) >> 1`, so it has lost a least-significant bit, but only
1144/// when `left + right` was odd, which is exactly when `left - right` is odd
1145/// too. So the bit is recoverable from the side channel, and the correction
1146/// below is what makes mid/side lossless rather than nearly so.
1147fn undo_decorrelation(assignment: ChannelAssignment, left: &mut [i64], right: &mut [i64]) {
1148    match assignment {
1149        ChannelAssignment::Independent(_) => {}
1150        ChannelAssignment::LeftSide => {
1151            // left is left, right is the side channel.
1152            for (channel, side) in left.iter().zip(right.iter_mut()) {
1153                *side = channel.wrapping_sub(*side);
1154            }
1155        }
1156        ChannelAssignment::SideRight => {
1157            // left is the side channel, right is right.
1158            for (side, channel) in left.iter_mut().zip(right.iter()) {
1159                *side = side.wrapping_add(*channel);
1160            }
1161        }
1162        ChannelAssignment::MidSide => {
1163            for (mid, side) in left.iter_mut().zip(right.iter_mut()) {
1164                let restored = (mid.wrapping_shl(1)) | (*side & 1);
1165                let difference = *side;
1166                *mid = restored.wrapping_add(difference) >> 1;
1167                *side = restored.wrapping_sub(difference) >> 1;
1168            }
1169        }
1170    }
1171}
1172
1173// -- The frame decoder --------------------------------------------------------
1174
1175/// Decodes frames of one stream, holding the scratch both readers reuse.
1176///
1177/// It owns the MD5 computation, so the two readers cannot disagree about
1178/// what was hashed: they feed the same function the same frames.
1179#[derive(Debug)]
1180struct FrameDecoder {
1181    info: FlacStreamInfo,
1182    /// Decoded integer samples, one channel after another, `block_size` of
1183    /// each. Grown to the largest frame actually met, never to a declared
1184    /// size.
1185    channels: Vec<i64>,
1186    /// The MD5 of the unencoded audio, computed as decoding proceeds.
1187    hasher: Md5,
1188    /// Interleaved bytes staged for the MD5, and how many are filled.
1189    stage: [u8; MD5_STAGE_BYTES],
1190    staged: usize,
1191    /// Interchannel samples produced so far.
1192    samples_done: u64,
1193    /// Whether the previous frame was short enough that the format only
1194    /// allows it as the stream's last.
1195    last_frame_seen: bool,
1196    /// The blocking strategy the first frame declared, which the rest must
1197    /// match.
1198    blocking: Option<Blocking>,
1199    /// Whether `info` came from a streaminfo block, one read out of the
1200    /// stream or one the caller supplied out of band, rather than being
1201    /// derived from the first frame's own header.
1202    ///
1203    /// It decides one thing: whether a frame that defers its sample rate or
1204    /// bit depth to streaminfo can be resolved. Derived properties are not a
1205    /// streaminfo block and are not allowed to stand in for one, because a
1206    /// later frame's escape code refers to a block that does not exist and
1207    /// answering it from the first frame would be a guess.
1208    streaminfo: bool,
1209    /// `sample as f32` divides by this, per the crate's scaling rule.
1210    divisor: f32,
1211}
1212
1213impl FrameDecoder {
1214    /// A decoder for a stream whose streaminfo block says `info`.
1215    fn new(info: FlacStreamInfo) -> Self {
1216        Self::build(info, true)
1217    }
1218
1219    /// A decoder for a bare frame stream, whose `info` was derived from its
1220    /// first frame by [`derive_stream_info`].
1221    fn from_first_frame(info: FlacStreamInfo) -> Self {
1222        Self::build(info, false)
1223    }
1224
1225    /// The two constructors' shared body.
1226    ///
1227    /// Construction, then [`reset_to`](Self::reset_to), so the starting state
1228    /// is stated once rather than once per way of reaching it.
1229    fn build(info: FlacStreamInfo, streaminfo: bool) -> Self {
1230        let mut decoder = Self {
1231            info,
1232            channels: Vec::new(),
1233            hasher: Md5::new(),
1234            stage: [0; MD5_STAGE_BYTES],
1235            staged: 0,
1236            samples_done: 0,
1237            last_frame_seen: false,
1238            blocking: None,
1239            streaminfo,
1240            divisor: 0.0,
1241        };
1242        decoder.reset_to(info, streaminfo);
1243        decoder
1244    }
1245
1246    /// Returns this decoder to its just-constructed state for `info`, keeping
1247    /// the sample buffer's allocation.
1248    ///
1249    /// **This is the one statement of what a fresh decoder's state is**, and
1250    /// [`build`](Self::build) goes through it, so the two cannot drift into
1251    /// disagreeing about what "fresh" means.
1252    ///
1253    /// It exists because [`FlacRecovery`] trial-decodes a candidate frame at
1254    /// every plausible sync point, and a frame header may legitimately
1255    /// declare the format's largest block: 65,535 samples in 8 channels is a
1256    /// four-megabyte buffer. Building a decoder per candidate meant a byte
1257    /// run of such headers cost one four-megabyte allocation, and one
1258    /// four-megabyte zeroing, per candidate position, which is time
1259    /// proportional to input length times the format's maximum frame rather
1260    /// than to the input. Reusing the buffer is a change to what the scan
1261    /// *costs* and to nothing it *decides*: every field a decision reads is
1262    /// reset here to exactly what construction sets.
1263    fn reset_to(&mut self, info: FlacStreamInfo, streaminfo: bool) {
1264        self.info = info;
1265        self.channels.clear();
1266        self.hasher = Md5::new();
1267        self.staged = 0;
1268        self.samples_done = 0;
1269        self.last_frame_seen = false;
1270        self.blocking = None;
1271        self.streaminfo = streaminfo;
1272        // The crate's scaling rule, generalised to FLAC's 4-to-32-bit range:
1273        // an integer sample of n bits divides by 2^(n-1). At 8, 16, 24 and 32
1274        // bits this is exactly the divisor `sample.rs` uses, which
1275        // `flac_scaling_agrees_with_sample_rs` pins.
1276        self.divisor = (1u64 << (info.bits_per_sample - 1)) as f32;
1277    }
1278
1279    /// Decodes one frame from the start of `bytes`, appends its interleaved
1280    /// samples to `output` and returns how many bytes the frame occupied.
1281    ///
1282    /// `base` is where `bytes[0]` sits in the whole input.
1283    fn decode_frame(
1284        &mut self,
1285        bytes: &[u8],
1286        base: u64,
1287        output: &mut Vec<f32>,
1288    ) -> Result<usize, DecodeError> {
1289        let header = parse_frame_header(bytes, base)?;
1290        self.check_against_stream(&header, base)?;
1291        // Recorded after the check, so the first frame sets the strategy and
1292        // every frame after it has to match.
1293        self.blocking = Some(header.blocking);
1294
1295        let block_size = header.block_size as usize;
1296        let channel_count = usize::from(header.channels.count());
1297        let bits = u32::from(self.info.bits_per_sample);
1298
1299        // The one allocation that follows a number from the file, bounded by
1300        // the streaminfo maximum block size checked above and by the
1301        // format's own 65535-by-8 ceiling.
1302        self.channels.clear();
1303        self.channels.resize(block_size * channel_count, 0);
1304
1305        let mut reader = BitReader::new(bytes, base);
1306        reader.bit = header.header_bytes * 8;
1307        for channel in 0..channel_count {
1308            let side = header.channels.side_channel() == Some(channel);
1309            let start = channel * block_size;
1310            decode_subframe(
1311                &mut reader,
1312                bits + u32::from(side),
1313                &mut self.channels[start..start + block_size],
1314            )?;
1315        }
1316
1317        reader.align_to_byte();
1318        let frame_bytes = reader.byte_position();
1319        let stored_crc = reader.read_bits(16)? as u16;
1320        if crc16(&bytes[..frame_bytes]) != stored_crc {
1321            return Err(DecodeError::Malformed {
1322                expected: "a frame whose CRC-16 matches its contents",
1323                offset: base + frame_bytes as u64,
1324            });
1325        }
1326
1327        if channel_count == 2 {
1328            let (left, right) = self.channels.split_at_mut(block_size);
1329            undo_decorrelation(header.channels, left, right);
1330        }
1331
1332        self.emit(block_size, channel_count, output);
1333        self.samples_done += header.block_size as u64;
1334        self.last_frame_seen = header.block_size < MIN_BLOCK_SIZE;
1335        Ok(frame_bytes + 2)
1336    }
1337
1338    /// Rejects a frame whose properties do not match the stream's.
1339    ///
1340    /// Every check here is a place where decoding on would produce audio
1341    /// that is wrong rather than an error: a channel count or bit depth that
1342    /// changed cannot be described by one [`AudioSpec`], and a block size
1343    /// past the streaminfo maximum is both a format violation and the only
1344    /// bound on this decoder's buffer.
1345    fn check_against_stream(&self, header: &FrameHeader, base: u64) -> Result<(), DecodeError> {
1346        let malformed = |expected| DecodeError::Malformed {
1347            expected,
1348            offset: base,
1349        };
1350        if let Some(blocking) = self.blocking {
1351            if blocking != header.blocking {
1352                return Err(malformed("an unchanging blocking strategy"));
1353            }
1354        }
1355        if self.last_frame_seen {
1356            return Err(malformed(
1357                "no frame after one shorter than the minimum block size",
1358            ));
1359        }
1360        if u32::from(header.channels.count()) != u32::from(self.info.spec.channels) {
1361            return Err(malformed("a channel count matching streaminfo"));
1362        }
1363        match header.bits_per_sample {
1364            Some(bits) if bits != self.info.bits_per_sample => {
1365                return Err(malformed("a bit depth matching streaminfo"))
1366            }
1367            // The escape code, in a stream that has no streaminfo to escape
1368            // to. Rejected by name rather than answered from the first frame.
1369            None if !self.streaminfo => return Err(malformed(UNRESOLVED_DEPTH)),
1370            _ => {}
1371        }
1372        match header.sample_rate {
1373            Some(rate) if rate != self.info.spec.sample_rate => {
1374                return Err(malformed("a sample rate matching streaminfo"))
1375            }
1376            None if !self.streaminfo => return Err(malformed(UNRESOLVED_RATE)),
1377            _ => {}
1378        }
1379        if header.block_size > u32::from(self.info.max_block_size) {
1380            return Err(malformed(
1381                "a block size no larger than the streaminfo maximum",
1382            ));
1383        }
1384        Ok(())
1385    }
1386
1387    /// Interleaves the decoded channels into `output` as `f32`, and feeds the
1388    /// same samples to the MD5 in the byte-aligned little-endian form
1389    /// RFC 9639 section 8.2 specifies.
1390    fn emit(&mut self, block_size: usize, channel_count: usize, output: &mut Vec<f32>) {
1391        let width = self.info.md5_bytes_per_sample();
1392        output.reserve(block_size * channel_count);
1393        for index in 0..block_size {
1394            for channel in 0..channel_count {
1395                let sample = self.channels[channel * block_size + index];
1396                output.push(sample as f32 / self.divisor);
1397                if self.staged + width > MD5_STAGE_BYTES {
1398                    self.hasher.update(&self.stage[..self.staged]);
1399                    self.staged = 0;
1400                }
1401                // Little-endian, sign-extended to a whole number of bytes:
1402                // the low `width` bytes of the two's-complement value are
1403                // exactly that, because the value already fits the depth.
1404                self.stage[self.staged..self.staged + width]
1405                    .copy_from_slice(&sample.to_le_bytes()[..width]);
1406                self.staged += width;
1407            }
1408        }
1409    }
1410
1411    /// Closes the stream: checks the sample count against streaminfo and the
1412    /// MD5 against the decoded audio.
1413    ///
1414    /// `md5_offset` is where the checksum field sits in the input, so the
1415    /// rejection names it rather than the file.
1416    fn finish(mut self, md5_offset: u64) -> Result<(), DecodeError> {
1417        if let Some(total) = self.info.total_samples {
1418            if self.samples_done != total {
1419                return Err(if self.samples_done < total {
1420                    DecodeError::Truncated {
1421                        expected: total,
1422                        available: self.samples_done,
1423                    }
1424                } else {
1425                    DecodeError::Malformed {
1426                        expected: "a stream holding exactly the declared total number of samples",
1427                        offset: md5_offset,
1428                    }
1429                });
1430            }
1431        }
1432        let Some(declared) = self.info.md5 else {
1433            // An all-zero checksum means "not known", which the format
1434            // permits. There is simply no oracle for this file.
1435            return Ok(());
1436        };
1437        self.hasher.update(&self.stage[..self.staged]);
1438        self.staged = 0;
1439        if self.hasher.finish() != declared {
1440            return Err(DecodeError::Malformed {
1441                expected: "decoded audio matching the streaminfo MD5 checksum",
1442                offset: md5_offset,
1443            });
1444        }
1445        Ok(())
1446    }
1447}
1448
1449// -- Metadata -----------------------------------------------------------------
1450
1451/// What a metadata walk established about a stream's header.
1452struct Metadata {
1453    info: FlacStreamInfo,
1454    /// Where the MD5 field sits in the input.
1455    md5_offset: u64,
1456    /// Where the first audio frame starts.
1457    audio_offset: usize,
1458}
1459
1460/// Reads the `fLaC` signature and every metadata block, and answers where the
1461/// audio starts.
1462///
1463/// RFC 9639 section 8 requires the first metadata block to be streaminfo, so
1464/// a file that puts anything else there is rejected rather than searched.
1465/// Every other block type is stepped over without being parsed: this crate
1466/// decodes audio, and a vorbis comment it never reads cannot mislead it.
1467fn read_metadata(bytes: &[u8]) -> Result<Metadata, DecodeError> {
1468    let magic = bytes
1469        .get(..4)
1470        .map(|head| FourCc([head[0], head[1], head[2], head[3]]));
1471    match magic {
1472        Some(tag) if tag == MAGIC => {}
1473        Some(tag) => return Err(DecodeError::UnsupportedContainer { tag }),
1474        None => {
1475            return Err(DecodeError::Truncated {
1476                expected: 4,
1477                available: bytes.len() as u64,
1478            })
1479        }
1480    }
1481
1482    let mut at = 4usize;
1483    let mut info: Option<(FlacStreamInfo, u64)> = None;
1484    loop {
1485        let Some(header) = bytes.get(at..at + METADATA_HEADER_BYTES) else {
1486            return Err(DecodeError::Truncated {
1487                expected: (at + METADATA_HEADER_BYTES) as u64,
1488                available: bytes.len() as u64,
1489            });
1490        };
1491        let last = header[0] & 0x80 != 0;
1492        let kind = header[0] & 0x7F;
1493        // u64 throughout: `at + length` in usize wraps on a 32-bit target for
1494        // a crafted length, which turns a range check into a pass.
1495        let length =
1496            (u64::from(header[1]) << 16) | (u64::from(header[2]) << 8) | u64::from(header[3]);
1497        let body_at = at as u64 + METADATA_HEADER_BYTES as u64;
1498        if kind == BLOCK_FORBIDDEN {
1499            return Err(DecodeError::Malformed {
1500                expected: "a metadata block type other than the forbidden 127",
1501                offset: at as u64,
1502            });
1503        }
1504        if body_at + length > bytes.len() as u64 {
1505            return Err(DecodeError::Truncated {
1506                expected: body_at + length,
1507                available: bytes.len() as u64,
1508            });
1509        }
1510        let body_at = body_at as usize;
1511        let body_end = body_at + length as usize;
1512
1513        if kind == BLOCK_STREAMINFO {
1514            if info.is_some() {
1515                return Err(DecodeError::Malformed {
1516                    expected: "exactly one streaminfo metadata block",
1517                    offset: at as u64,
1518                });
1519            }
1520            info = Some((
1521                parse_streaminfo(&bytes[body_at..body_end], body_at as u64)?,
1522                body_at as u64 + 18,
1523            ));
1524        } else if info.is_none() {
1525            return Err(DecodeError::Malformed {
1526                expected: "a streaminfo block first among the metadata blocks",
1527                offset: at as u64,
1528            });
1529        }
1530
1531        at = body_end;
1532        if last {
1533            break;
1534        }
1535    }
1536
1537    let Some((info, md5_offset)) = info else {
1538        return Err(DecodeError::Malformed {
1539            expected: "a streaminfo metadata block",
1540            offset: 4,
1541        });
1542    };
1543    Ok(Metadata {
1544        info,
1545        md5_offset,
1546        audio_offset: at,
1547    })
1548}
1549
1550/// `true` when `bytes` opens with something that could be a frame header.
1551///
1552/// Used only to tell a stream that carries more audio than it declared from
1553/// one that carries a trailing tag, which is common in the wild and harmless.
1554fn looks_like_a_frame(bytes: &[u8]) -> bool {
1555    matches!(bytes, [0xFF, second, ..] if second & 0xFE == 0xF8)
1556}
1557
1558/// Decodes every frame in `audio` into `output` and answers how many bytes
1559/// were consumed.
1560///
1561/// `base` is where `audio[0]` sits in the whole input, so rejections name
1562/// absolute offsets. The MD5 is *not* closed here: the caller decides whether
1563/// [`FrameDecoder::finish`] is the right thing to do with what it produced.
1564///
1565/// One function rather than one per reader, for the reason recorded in
1566/// `CLAUDE.md`'s third coverage lesson: a rule with two implementations means
1567/// a negative control on the first says nothing about the second. The
1568/// whole-file reader, the bare frame reader and the recovering reader all
1569/// walk frames through this.
1570fn decode_frames(
1571    decoder: &mut FrameDecoder,
1572    audio: &[u8],
1573    base: u64,
1574    output: &mut Vec<f32>,
1575) -> Result<usize, DecodeError> {
1576    let total = decoder.info.total_samples;
1577    let mut at = 0usize;
1578    while at < audio.len() {
1579        if total.is_some_and(|total| decoder.samples_done >= total) {
1580            break;
1581        }
1582        at += decoder.decode_frame(&audio[at..], base + at as u64, output)?;
1583    }
1584
1585    // A stream that declared its length and then carried more audio is
1586    // internally inconsistent, and preferring either source silently is the
1587    // failure this crate refuses. A trailing tag is not audio and is left
1588    // alone.
1589    if total.is_some() && looks_like_a_frame(&audio[at..]) {
1590        return Err(DecodeError::Malformed {
1591            expected: "a stream holding exactly the declared total number of samples",
1592            offset: base + at as u64,
1593        });
1594    }
1595    Ok(at)
1596}
1597
1598// -- What a decode did about the checksum -------------------------------------
1599
1600/// Whether a decode checked its output against a streaminfo MD5, and why not
1601/// when it did not.
1602///
1603/// The whole-file reader has no need of this: a caller holding a
1604/// [`FlacReader`] can read [`FlacStreamInfo::md5`] and knows that a decode
1605/// which returned `Ok` matched it. The three paths that take their streaminfo
1606/// from somewhere other than the stream can each end up with no checksum to
1607/// check, for three different reasons, and none of them is visible in the
1608/// samples. Silently not verifying is how a decoder ends up credited with a
1609/// guarantee it did not provide, so it is reported instead.
1610///
1611/// There is no "failed" state. A mismatch is [`DecodeError::Malformed`] and
1612/// no samples travel with it.
1613///
1614/// `#[non_exhaustive]`: a consumer matching on it keeps a `_ =>` arm.
1615#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1616#[non_exhaustive]
1617pub enum Md5Check {
1618    /// The decoded audio was hashed and matched the streaminfo checksum.
1619    Verified,
1620    /// No streaminfo was available, so the stream's properties were derived
1621    /// from its first frame and there was no checksum to compare against.
1622    NoStreamInfo,
1623    /// Streaminfo was available and its checksum field is the all-zero value
1624    /// that RFC 9639 section 8.2 defines as "not known". Permitted by the
1625    /// format and not a failure.
1626    ChecksumUnset,
1627    /// Audio was skipped, so a hash over what was decoded is a hash over a
1628    /// different set of samples than the checksum describes. Only
1629    /// [`FlacRecovery`] can reach this.
1630    AudioIncomplete,
1631}
1632
1633impl Md5Check {
1634    /// Whether the audio was actually checked against a checksum.
1635    ///
1636    /// The one-line form of the enum above, for a caller that wants to refuse
1637    /// audio nothing verified.
1638    pub const fn is_verified(self) -> bool {
1639        matches!(self, Self::Verified)
1640    }
1641}
1642
1643// -- The whole-file reader ----------------------------------------------------
1644
1645/// A FLAC file held whole in memory.
1646///
1647/// [`new`](Self::new) validates the signature and every metadata block;
1648/// [`decode_to_end`](Self::decode_to_end) decodes the audio frames and
1649/// verifies the streaminfo MD5 over what it produced. The split is why this
1650/// reader's decode returns a `Result` where the two PCM containers' do not:
1651/// their payload cannot fail once the header has parsed, and a FLAC frame
1652/// can.
1653///
1654/// # Example
1655///
1656/// ```
1657/// use decibri_decode::FlacReader;
1658///
1659/// // RFC 9639 appendix D.3's worked example: 8-bit mono, 24 samples.
1660/// let file: [u8; 73] = [
1661///     0x66, 0x4c, 0x61, 0x43, 0x80, 0x00, 0x00, 0x22, 0x10, 0x00, 0x10, 0x00,
1662///     0x00, 0x00, 0x1f, 0x00, 0x00, 0x1f, 0x07, 0xd0, 0x00, 0x70, 0x00, 0x00,
1663///     0x00, 0x18, 0xf8, 0xf9, 0xe3, 0x96, 0xf5, 0xcb, 0xcf, 0xc6, 0xdc, 0x80,
1664///     0x7f, 0x99, 0x77, 0x90, 0x6b, 0x32, 0xff, 0xf8, 0x68, 0x02, 0x00, 0x17,
1665///     0xe9, 0x44, 0x00, 0x4f, 0x6f, 0x31, 0x3d, 0x10, 0x47, 0xd2, 0x27, 0xcb,
1666///     0x6d, 0x09, 0x08, 0x31, 0x45, 0x2b, 0xdc, 0x28, 0x22, 0x22, 0x80, 0x57,
1667///     0xa3,
1668/// ];
1669///
1670/// let reader = FlacReader::new(&file)?;
1671/// assert_eq!(reader.spec().sample_rate, 32_000);
1672/// assert_eq!(reader.stream_info().bits_per_sample, 8);
1673/// assert_eq!(reader.frames(), Some(24));
1674///
1675/// let decoded = reader.decode_to_end()?;
1676/// assert_eq!(decoded.frames(), 24);
1677/// // The first four samples are 0, 79, 111 and 78, scaled by 2^7.
1678/// assert_eq!(&decoded.samples()[..4], &[0.0, 79.0 / 128.0, 111.0 / 128.0, 78.0 / 128.0]);
1679/// # Ok::<(), decibri_decode::DecodeError>(())
1680/// ```
1681#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1682pub struct FlacReader<'a> {
1683    info: FlacStreamInfo,
1684    md5_offset: u64,
1685    /// The audio frames, from the first frame byte to the end of the input.
1686    audio: &'a [u8],
1687    /// Where `audio[0]` sits in the input, so rejections name absolute
1688    /// offsets.
1689    audio_offset: u64,
1690}
1691
1692impl<'a> FlacReader<'a> {
1693    /// Parses `bytes` as a FLAC stream, reading the signature and metadata.
1694    ///
1695    /// The audio frames are not touched here, so this is cheap on a large
1696    /// file and a reader that exists is a file whose *header* is valid.
1697    ///
1698    /// # Errors
1699    ///
1700    /// - [`DecodeError::UnsupportedContainer`] when the input does not start
1701    ///   with `fLaC`, naming the four bytes it did start with.
1702    /// - [`DecodeError::Truncated`] when the input ends inside the signature,
1703    ///   a metadata block header or a metadata block body.
1704    /// - [`DecodeError::Malformed`] when the first metadata block is not
1705    ///   streaminfo, a second streaminfo appears, a block declares the
1706    ///   forbidden type 127, or streaminfo carries a block size, sample rate
1707    ///   or bit depth the format does not allow.
1708    pub fn new(bytes: &'a [u8]) -> Result<Self, DecodeError> {
1709        let metadata = read_metadata(bytes)?;
1710        Ok(Self {
1711            info: metadata.info,
1712            md5_offset: metadata.md5_offset,
1713            audio: &bytes[metadata.audio_offset..],
1714            audio_offset: metadata.audio_offset as u64,
1715        })
1716    }
1717
1718    /// What the streaminfo metadata block declared.
1719    pub const fn stream_info(&self) -> &FlacStreamInfo {
1720        &self.info
1721    }
1722
1723    /// The rate and layout the stream decodes to.
1724    pub const fn spec(&self) -> AudioSpec {
1725        self.info.spec
1726    }
1727
1728    /// How many interchannel samples the stream declares, or `None` when the
1729    /// streaminfo field holds the zero that means unknown.
1730    ///
1731    /// `None` rather than `0` because a stream of unknown length and an
1732    /// empty one are different things, and `0` would conflate them.
1733    pub const fn frames(&self) -> Option<u64> {
1734        self.info.total_samples
1735    }
1736
1737    /// The audio frames, undecoded.
1738    pub const fn frame_data(&self) -> &'a [u8] {
1739        self.audio
1740    }
1741
1742    /// Decodes every frame, appends the interleaved samples to `output` and
1743    /// verifies the streaminfo MD5 over them.
1744    ///
1745    /// Returns how many interleaved samples were appended, frames times
1746    /// channels, which is the length `output` grew by.
1747    ///
1748    /// # Errors
1749    ///
1750    /// - [`DecodeError::Malformed`] for a frame whose CRC-8 or CRC-16 does
1751    ///   not match, a reserved or forbidden field value, a frame whose
1752    ///   properties disagree with streaminfo, and, as the check that covers
1753    ///   everything else, decoded audio whose MD5 is not the one streaminfo
1754    ///   carries.
1755    /// - [`DecodeError::Truncated`] when the input ends inside a frame or
1756    ///   holds fewer samples than streaminfo declares.
1757    pub fn decode(&self, output: &mut Vec<f32>) -> Result<usize, DecodeError> {
1758        let before = output.len();
1759        let mut decoder = FrameDecoder::new(self.info);
1760        decode_frames(&mut decoder, self.audio, self.audio_offset, output)?;
1761        decoder.finish(self.md5_offset)?;
1762        Ok(output.len() - before)
1763    }
1764
1765    /// Decodes the whole stream, bound to the spec that describes it.
1766    ///
1767    /// The channel count of the returned buffer is never zero: the format
1768    /// codes it as one more than a three-bit field, so no stream can declare
1769    /// none.
1770    ///
1771    /// # Errors
1772    ///
1773    /// As [`decode`](Self::decode).
1774    pub fn decode_to_end(&self) -> Result<AudioBuffer, DecodeError> {
1775        let mut samples = Vec::new();
1776        self.decode(&mut samples)?;
1777        Ok(AudioBuffer::from_samples(self.info.spec, samples))
1778    }
1779}
1780
1781// -- The bare frame reader ----------------------------------------------------
1782
1783/// What a bare frame stream decode did.
1784///
1785/// `#[non_exhaustive]`: a consumer constructing or matching it exhaustively
1786/// would break on a field added later.
1787#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1788#[non_exhaustive]
1789pub struct FlacFrameReport {
1790    /// How many interleaved samples were appended to the output.
1791    pub samples: usize,
1792    /// Whether the audio was checked against a streaminfo MD5.
1793    pub md5: Md5Check,
1794}
1795
1796/// A bare FLAC frame stream held whole in memory: no `fLaC` signature, no
1797/// metadata, the first byte is the first byte of a frame header.
1798///
1799/// # Why this is decodable at all
1800///
1801/// A FLAC frame is self-describing. Its header restates the block size,
1802/// sample rate, channel assignment and bit depth, carries a CRC-8 over
1803/// itself and is followed by a CRC-16 over the whole frame. So a run of
1804/// frames with nothing in front of it is a complete stream description, and
1805/// the corpus carries two files that are exactly that.
1806///
1807/// # Where it sits
1808///
1809/// This is the third headerless decoder in the crate, beside
1810/// [`PcmDecoder`](crate::PcmDecoder) and [`G711Decoder`](crate::G711Decoder),
1811/// and it takes the same position they do: what the container would have said
1812/// arrives out of band, or not at all. The difference is that PCM and G.711
1813/// bytes carry no claim, so their `new` takes an
1814/// [`AudioSpec`](crate::AudioSpec) the caller asserts, whereas FLAC frames do
1815/// carry one, so [`new`](Self::new) reads the properties rather than being
1816/// told them, and [`with_stream_info`](Self::with_stream_info) is for the
1817/// caller who has a real streaminfo block from somewhere else.
1818///
1819/// # The two escape codes
1820///
1821/// Sample rate code `0b0000` and bit depth code `0b000` mean "take this field
1822/// from the streaminfo block". [`new`](Self::new) has no streaminfo block, so
1823/// a frame using either is [`DecodeError::Malformed`] naming which of the two
1824/// could not be resolved. Nothing is defaulted and nothing is carried over
1825/// from a neighbouring frame. [`with_stream_info`](Self::with_stream_info)
1826/// resolves both.
1827///
1828/// # Example
1829///
1830/// ```
1831/// use decibri_decode::{FlacFrameReader, Md5Check};
1832///
1833/// # let file: [u8; 73] = [
1834/// #     0x66, 0x4c, 0x61, 0x43, 0x80, 0x00, 0x00, 0x22, 0x10, 0x00, 0x10, 0x00,
1835/// #     0x00, 0x00, 0x1f, 0x00, 0x00, 0x1f, 0x07, 0xd0, 0x00, 0x70, 0x00, 0x00,
1836/// #     0x00, 0x18, 0xf8, 0xf9, 0xe3, 0x96, 0xf5, 0xcb, 0xcf, 0xc6, 0xdc, 0x80,
1837/// #     0x7f, 0x99, 0x77, 0x90, 0x6b, 0x32, 0xff, 0xf8, 0x68, 0x02, 0x00, 0x17,
1838/// #     0xe9, 0x44, 0x00, 0x4f, 0x6f, 0x31, 0x3d, 0x10, 0x47, 0xd2, 0x27, 0xcb,
1839/// #     0x6d, 0x09, 0x08, 0x31, 0x45, 0x2b, 0xdc, 0x28, 0x22, 0x22, 0x80, 0x57,
1840/// #     0xa3,
1841/// # ];
1842/// // RFC 9639 appendix D.3's worked example with its 42-byte header removed,
1843/// // which is what a container handing over bare frames would deliver.
1844/// let frames = &file[42..];
1845///
1846/// let reader = FlacFrameReader::new(frames)?;
1847/// assert_eq!(reader.spec().sample_rate, 32_000);
1848/// assert_eq!(reader.stream_info().bits_per_sample, 8);
1849/// // Nothing declares a length, so there is none to report.
1850/// assert_eq!(reader.frames(), None);
1851///
1852/// let mut samples = Vec::new();
1853/// let report = reader.decode(&mut samples)?;
1854/// assert_eq!(report.samples, 24);
1855/// // No streaminfo block came with the frames, so nothing verified them.
1856/// assert_eq!(report.md5, Md5Check::NoStreamInfo);
1857/// assert!(!report.md5.is_verified());
1858/// # Ok::<(), decibri_decode::DecodeError>(())
1859/// ```
1860#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1861pub struct FlacFrameReader<'a> {
1862    /// The frames, from the first frame byte to the end of the input.
1863    audio: &'a [u8],
1864    info: FlacStreamInfo,
1865    /// Whether `info` came from a streaminfo block rather than from the first
1866    /// frame's header.
1867    streaminfo: bool,
1868}
1869
1870impl<'a> FlacFrameReader<'a> {
1871    /// Reads a bare frame stream, taking the stream's properties from its
1872    /// first frame header.
1873    ///
1874    /// Only the first header is parsed here, so this is cheap on a large
1875    /// input and a reader that exists is a stream whose *first frame header*
1876    /// is valid.
1877    ///
1878    /// # Errors
1879    ///
1880    /// - [`DecodeError::Truncated`] when the input is shorter than the
1881    ///   smallest possible frame header.
1882    /// - [`DecodeError::Malformed`] when the input does not begin with a
1883    ///   frame sync code, when the header's CRC-8 does not match, when a
1884    ///   reserved value is used, and, as the case this path adds, when the
1885    ///   header defers its sample rate or bit depth to a streaminfo block
1886    ///   that does not exist, which the error names.
1887    pub fn new(bytes: &'a [u8]) -> Result<Self, DecodeError> {
1888        let header = parse_frame_header(bytes, 0)?;
1889        Ok(Self {
1890            audio: bytes,
1891            info: derive_stream_info(&header, 0)?,
1892            streaminfo: false,
1893        })
1894    }
1895
1896    /// Reads a bare frame stream described by a streaminfo block the caller
1897    /// obtained elsewhere.
1898    ///
1899    /// This is the shape Ogg and Matroska use: the streaminfo block travels
1900    /// in the container's own codec-private header and the packets that
1901    /// follow are bare frames. The block's bytes become an `info` through
1902    /// [`FlacStreamInfo::from_block`]. Supplying it resolves the two escape
1903    /// codes, restores the declared sample count as a check, and, when the
1904    /// block carries one, restores the MD5 that a bare stream otherwise has
1905    /// no way to be checked against.
1906    ///
1907    /// Nothing is parsed here, so nothing can fail; a stream whose frames
1908    /// disagree with `info` is rejected by [`decode`](Self::decode), naming
1909    /// the field that disagreed.
1910    pub const fn with_stream_info(bytes: &'a [u8], info: FlacStreamInfo) -> Self {
1911        Self {
1912            audio: bytes,
1913            info,
1914            streaminfo: true,
1915        }
1916    }
1917
1918    /// The stream's properties: supplied by the caller, or read out of the
1919    /// first frame header.
1920    ///
1921    /// A derived description is not a streaminfo block and does not pretend
1922    /// to be one. Its `max_block_size` is the format's own 65,535 rather than
1923    /// a promise this stream made, and `total_samples`, `md5`,
1924    /// `min_frame_size` and `max_frame_size` are all `None`.
1925    pub const fn stream_info(&self) -> &FlacStreamInfo {
1926        &self.info
1927    }
1928
1929    /// The rate and layout the stream decodes to.
1930    pub const fn spec(&self) -> AudioSpec {
1931        self.info.spec
1932    }
1933
1934    /// How many interchannel samples the stream declares, which for a derived
1935    /// description is always `None` because nothing declared anything.
1936    pub const fn frames(&self) -> Option<u64> {
1937        self.info.total_samples
1938    }
1939
1940    /// Decodes every frame and appends the interleaved samples to `output`.
1941    ///
1942    /// # Errors
1943    ///
1944    /// - [`DecodeError::Malformed`] for a frame whose CRC-8 or CRC-16 does
1945    ///   not match, a reserved or forbidden field value, a frame whose
1946    ///   properties disagree with the stream's, a frame deferring a field to
1947    ///   a streaminfo block that is not there, and, when a checksum was
1948    ///   supplied, decoded audio that does not match it.
1949    /// - [`DecodeError::Truncated`] when the input ends inside a frame. A
1950    ///   partial trailing frame is an error here, exactly as it is
1951    ///   everywhere else in this crate; recovering what can be read from a
1952    ///   damaged run is [`FlacRecovery`], and is asked for explicitly.
1953    pub fn decode(&self, output: &mut Vec<f32>) -> Result<FlacFrameReport, DecodeError> {
1954        let before = output.len();
1955        let mut decoder = if self.streaminfo {
1956            FrameDecoder::new(self.info)
1957        } else {
1958            FrameDecoder::from_first_frame(self.info)
1959        };
1960        decode_frames(&mut decoder, self.audio, 0, output)?;
1961        // No streaminfo block sits in this input, so a checksum rejection
1962        // cannot name where the checksum came from. It names where the decode
1963        // concluded, which is the last byte it read.
1964        decoder.finish(self.audio.len() as u64)?;
1965        Ok(FlacFrameReport {
1966            samples: output.len() - before,
1967            md5: self.md5_outcome(),
1968        })
1969    }
1970
1971    /// Decodes the whole stream, bound to the spec that describes it.
1972    ///
1973    /// # Errors
1974    ///
1975    /// As [`decode`](Self::decode).
1976    pub fn decode_to_end(&self) -> Result<(AudioBuffer, FlacFrameReport), DecodeError> {
1977        let mut samples = Vec::new();
1978        let report = self.decode(&mut samples)?;
1979        Ok((AudioBuffer::from_samples(self.info.spec, samples), report))
1980    }
1981
1982    /// What a decode that returned `Ok` did about the checksum.
1983    fn md5_outcome(&self) -> Md5Check {
1984        if !self.streaminfo {
1985            Md5Check::NoStreamInfo
1986        } else if self.info.md5.is_none() {
1987            Md5Check::ChecksumUnset
1988        } else {
1989            Md5Check::Verified
1990        }
1991    }
1992}
1993
1994// -- Recovery -----------------------------------------------------------------
1995
1996/// Why a range of input produced no audio.
1997///
1998/// `#[non_exhaustive]`: a consumer matching on it keeps a `_ =>` arm.
1999#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
2000#[non_exhaustive]
2001pub enum FlacSkipReason {
2002    /// No sync point could be established anywhere in the range. Leading
2003    /// garbage, a run that begins part-way through a frame, and anything
2004    /// after the last frame all arrive here.
2005    NoSyncPoint,
2006    /// A frame at a known boundary was rejected, by a CRC that did not match
2007    /// or a header that disagreed with the stream, and the search for the
2008    /// next sync point began after it.
2009    FrameRejected,
2010}
2011
2012/// One range of input that produced no audio.
2013#[derive(Debug, Clone, PartialEq, Eq)]
2014#[non_exhaustive]
2015pub struct FlacSkip {
2016    /// The half-open byte range of the input, `[start, end)`, that was
2017    /// skipped.
2018    pub bytes: Range<u64>,
2019    /// The frames this gap cost, as a half-open range of the stream's own
2020    /// interchannel sample positions, or `None` when the stream does not say
2021    /// what they were.
2022    ///
2023    /// A frame is one interchannel sample, one value per channel, the unit
2024    /// AIFF calls a sample frame and FLAC's own frame counts use. A stereo
2025    /// gap of `0..10` is ten frames and twenty interleaved samples, so this
2026    /// range and [`FlacRecoveryReport::samples`] count in different units,
2027    /// and the names say which is which.
2028    ///
2029    /// The positions are **the stream's own**, taken from the coded numbers
2030    /// that surviving frame headers carry, not offsets into the output. A
2031    /// variable-blocksize stream codes the sample number directly; a
2032    /// fixed-blocksize stream codes a frame number, which is multiplied by
2033    /// the largest block size any recovered frame carried, the stream's
2034    /// constant block size, unless the only frames recovered were the
2035    /// stream's short last one.
2036    ///
2037    /// A gap between two recovered frames always resolves, and its width is
2038    /// exactly what was lost however the stream numbers itself. The two ends
2039    /// of the input are the cases that may not:
2040    ///
2041    /// - A gap **before the first recovered frame** resolves only when that
2042    ///   frame is the stream's first, or when a streaminfo block was supplied
2043    ///   and the input is therefore known to start where the stream does. A
2044    ///   bare frame stream may begin anywhere, and the conformance corpus has
2045    ///   one whose first surviving frame is number 12,927, so answering
2046    ///   "12,927 frames were lost" for a run that never held them would be an
2047    ///   invention. [`FlacRecoveryReport::first_frame`] is the thing that is
2048    ///   always known there.
2049    /// - A gap **after the last recovered frame** resolves only when a
2050    ///   declared total sample count says how far the stream ran.
2051    ///
2052    /// `None` is not zero and must not be read as it. An empty range is the
2053    /// meaningful zero: it says this gap cost no audio, which is what garbage
2054    /// in front of a stream's first frame amounts to.
2055    pub frames: Option<Range<u64>>,
2056    /// Why this range produced nothing.
2057    pub reason: FlacSkipReason,
2058}
2059
2060/// What a recovering decode found and what it did not.
2061#[derive(Debug, Clone, PartialEq, Eq)]
2062#[non_exhaustive]
2063pub struct FlacRecoveryReport {
2064    /// How many interleaved samples were appended to the output: frames
2065    /// times channels, which is the length the output vector grew by.
2066    ///
2067    /// The gaps in [`skipped`](Self::skipped) count frames, not interleaved
2068    /// samples; the two units are named apart because confusing them is a
2069    /// silent factor of the channel count.
2070    pub samples: usize,
2071    /// Whether the audio was checked against a streaminfo MD5. Any lost or
2072    /// unaccounted audio makes this [`Md5Check::AudioIncomplete`], because a
2073    /// hash over a stream with a hole in it is not the hash the checksum
2074    /// describes.
2075    pub md5: Md5Check,
2076    /// Every range of input that produced no audio, in input order.
2077    ///
2078    /// Empty means the whole input decoded, which is a thing recovery is
2079    /// allowed to report and is the case for a clean bare frame stream.
2080    pub skipped: Vec<FlacSkip>,
2081    /// Where the first frame of the output sits in the stream's own
2082    /// numbering, or `None` when the stream's blocking strategy leaves it
2083    /// underdetermined.
2084    ///
2085    /// A position in the unit [`FlacSkip::frames`] counts: one interchannel
2086    /// sample, one value per channel, and not the interleaved samples
2087    /// [`samples`](Self::samples) counts. On a stereo stream `Some(10)` is
2088    /// the eleventh frame and the twenty-first interleaved sample. RFC 9639
2089    /// calls this position the sample number, its name for an interchannel
2090    /// position, so its sample number and this frame position are the same
2091    /// field under the two vocabularies.
2092    ///
2093    /// This is the datum a leading gap cannot always give: it is read
2094    /// straight off the coded number of the first frame recovered, so it is
2095    /// right whether or not the input begins where the stream does. `Some(0)`
2096    /// says the output starts at the stream's first frame and nothing at the
2097    /// front is missing.
2098    pub first_frame: Option<u64>,
2099    /// What the stream turned out to be: the streaminfo the caller supplied,
2100    /// or the properties derived from the first frame that was recovered.
2101    pub stream_info: FlacStreamInfo,
2102}
2103
2104impl FlacRecoveryReport {
2105    /// How many frames were lost, in [`FlacSkip::frames`]'s unit of one
2106    /// interchannel sample per frame, or `None` when any skipped range's
2107    /// extent is unknown.
2108    ///
2109    /// Frames, not the interleaved samples [`samples`](Self::samples)
2110    /// counts. The two differ by the channel count, and the names are what
2111    /// say which is which: subtracting this from `samples` is subtracting
2112    /// two different units, and the names are there so that a reader of the
2113    /// call site can see it.
2114    ///
2115    /// `Some(0)` is the meaningful success case: bytes were skipped and none
2116    /// of them carried audio. `None` is not zero and must not be read as it:
2117    /// it says the decoder cannot account for what it did not get.
2118    pub fn frames_lost(&self) -> Option<u64> {
2119        let mut total = 0u64;
2120        for skip in &self.skipped {
2121            let range = skip.frames.as_ref()?;
2122            total += range.end.saturating_sub(range.start);
2123        }
2124        Some(total)
2125    }
2126}
2127
2128/// Recovers whatever audio a run of bytes holds, which may begin part-way
2129/// through a frame, hold garbage, or be damaged in the middle.
2130///
2131/// # This is opt-in, and it is a separate type on purpose
2132///
2133/// Everywhere else in this crate a partial or damaged frame is an error
2134/// rather than quietly shortened audio, and recovery is where that promise
2135/// would be easiest to lose. So it is not a flag on the other readers and
2136/// there is no way to reach it by accident: a caller who wants recovery names
2137/// this type, and every decode through it returns a [`FlacRecoveryReport`]
2138/// that says exactly which bytes produced nothing and which sample positions
2139/// were lost. A recovering decoder that returned what it found and said
2140/// nothing about the rest would contradict the rest of the crate.
2141///
2142/// # Chained validation, and why one header is not evidence
2143///
2144/// The frame sync code is 14 bits and the header CRC-8 is 8, so about one
2145/// position in 256 of random data carries something that parses as a frame
2146/// header. A single validating header is therefore no evidence at all. A sync
2147/// point is accepted only when the frame at it decodes with a matching
2148/// CRC-16 **and** a further frame header parses at the offset that frame
2149/// predicts. The one case with no successor, a frame that ends exactly at
2150/// the end of the input, is accepted on its own CRC-16, because requiring a
2151/// successor there would discard the last frame of every stream.
2152///
2153/// # What it cannot recover
2154///
2155/// Nothing before the first sync point it can establish, nothing in a frame
2156/// whose CRC-16 fails, and, without a streaminfo block, nothing in a frame
2157/// that defers its sample rate or bit depth to one. Those frames are skipped
2158/// and reported, not guessed at.
2159///
2160/// # Recovery is whole-buffer only
2161///
2162/// This type takes a byte slice and works over all of it. **There is no
2163/// streaming form of it**, so a live stream that meets corruption part-way
2164/// through cannot be resynchronised in place: [`FlacStreamDecoder`] reports
2165/// the damage as a typed error and stops, and recovering what the rest of the
2166/// stream held means collecting the bytes and handing them here.
2167///
2168/// That is a limitation rather than a defect, and it is a consequence of how
2169/// a sync point is established above. Accepting one requires decoding the
2170/// frame at it *and* parsing a header where that frame ends, so the decision
2171/// is only makeable with the bytes after the candidate already in hand. A
2172/// streaming resync would have to buffer forward by an unbounded amount to
2173/// reach the same standard of evidence, or lower the standard, and a 14-bit
2174/// sync code with an 8-bit header CRC is not evidence on its own.
2175///
2176/// # Example
2177///
2178/// ```
2179/// use decibri_decode::{FlacRecovery, FlacSkipReason};
2180///
2181/// # let file: [u8; 73] = [
2182/// #     0x66, 0x4c, 0x61, 0x43, 0x80, 0x00, 0x00, 0x22, 0x10, 0x00, 0x10, 0x00,
2183/// #     0x00, 0x00, 0x1f, 0x00, 0x00, 0x1f, 0x07, 0xd0, 0x00, 0x70, 0x00, 0x00,
2184/// #     0x00, 0x18, 0xf8, 0xf9, 0xe3, 0x96, 0xf5, 0xcb, 0xcf, 0xc6, 0xdc, 0x80,
2185/// #     0x7f, 0x99, 0x77, 0x90, 0x6b, 0x32, 0xff, 0xf8, 0x68, 0x02, 0x00, 0x17,
2186/// #     0xe9, 0x44, 0x00, 0x4f, 0x6f, 0x31, 0x3d, 0x10, 0x47, 0xd2, 0x27, 0xcb,
2187/// #     0x6d, 0x09, 0x08, 0x31, 0x45, 0x2b, 0xdc, 0x28, 0x22, 0x22, 0x80, 0x57,
2188/// #     0xa3,
2189/// # ];
2190/// // Five bytes of junk, then RFC 9639 appendix D.3's frames.
2191/// let mut damaged = vec![0xFF, 0xF8, 0x00, 0x11, 0x22];
2192/// damaged.extend_from_slice(&file[42..]);
2193///
2194/// let mut samples = Vec::new();
2195/// let report = FlacRecovery::new(&damaged).decode(&mut samples)?;
2196///
2197/// assert_eq!(report.samples, 24);
2198/// assert_eq!(report.skipped.len(), 1);
2199/// assert_eq!(report.skipped[0].bytes, 0..5);
2200/// assert_eq!(report.skipped[0].reason, FlacSkipReason::NoSyncPoint);
2201/// // Junk in front of the first frame costs no audio, and says so.
2202/// assert_eq!(report.frames_lost(), Some(0));
2203/// # Ok::<(), decibri_decode::DecodeError>(())
2204/// ```
2205#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2206pub struct FlacRecovery<'a> {
2207    bytes: &'a [u8],
2208    info: Option<FlacStreamInfo>,
2209}
2210
2211/// A skipped range, before its sample positions can be worked out.
2212///
2213/// The conversion from a coded number to a sample position needs the stream's
2214/// block size, and for a fixed-blocksize stream that is only known once every
2215/// frame has been seen. So the scan records the coded numbers on each side of
2216/// a gap and the arithmetic happens at the end.
2217struct PendingSkip {
2218    bytes: Range<u64>,
2219    /// The coded number and block size of the last frame decoded before the
2220    /// gap, or `None` when nothing had been decoded yet.
2221    before: Option<(u64, u32)>,
2222    /// The coded number of the frame decoding resumed at, or `None` when the
2223    /// input ran out first.
2224    after: Option<u64>,
2225    reason: FlacSkipReason,
2226}
2227
2228impl<'a> FlacRecovery<'a> {
2229    /// Recovers from `bytes`, taking the stream's properties from the first
2230    /// frame it manages to establish sync on.
2231    pub const fn new(bytes: &'a [u8]) -> Self {
2232        Self { bytes, info: None }
2233    }
2234
2235    /// Recovers from `bytes` using a streaminfo block obtained elsewhere,
2236    /// parsed through [`FlacStreamInfo::from_block`].
2237    ///
2238    /// Supplying it resolves the two escape codes, and, when nothing turns
2239    /// out to have been lost, lets the checksum be verified even though the
2240    /// input needed recovering.
2241    pub const fn with_stream_info(bytes: &'a [u8], info: FlacStreamInfo) -> Self {
2242        Self {
2243            bytes,
2244            info: Some(info),
2245        }
2246    }
2247
2248    /// Recovers every frame it can and appends the interleaved samples to
2249    /// `output`.
2250    ///
2251    /// The samples are contiguous; the holes are in the report, not in the
2252    /// buffer.
2253    ///
2254    /// # Errors
2255    ///
2256    /// [`DecodeError::Malformed`] when no sync point can be established
2257    /// anywhere in the input, which is the honest answer for a byte run that
2258    /// holds no FLAC frame. Damage *after* the first frame is reported rather
2259    /// than raised: that is what recovery is.
2260    pub fn decode(&self, output: &mut Vec<f32>) -> Result<FlacRecoveryReport, DecodeError> {
2261        let before = output.len();
2262        let end = self.bytes.len() as u64;
2263        let mut pending: Vec<PendingSkip> = Vec::new();
2264
2265        // The scan's scratch, held across every candidate sync point rather
2266        // than built per candidate: see [`FrameDecoder::reset_to`] for what
2267        // that costs when it is not.
2268        let mut trial: Option<FrameDecoder> = None;
2269        let mut scratch: Vec<f32> = Vec::new();
2270
2271        // The first sync point is established before the loop, so the loop
2272        // always holds a decoder and never has to ask whether it does. It is
2273        // also the one failure this path raises rather than reports: a byte
2274        // run with no frame in it anywhere is not damaged audio, it is not
2275        // audio.
2276        let Some((first, header)) = self.find_sync(0, &mut trial, &mut scratch) else {
2277            return Err(DecodeError::Malformed {
2278                expected: "at least one frame whose CRC-16 matches and which another frame follows",
2279                offset: 0,
2280            });
2281        };
2282        let info = match self.info {
2283            Some(info) => info,
2284            None => derive_stream_info(&header, first as u64)?,
2285        };
2286        let mut decoder = if self.info.is_some() {
2287            FrameDecoder::new(info)
2288        } else {
2289            FrameDecoder::from_first_frame(info)
2290        };
2291        // Pushed even when the input opens on a frame, because "no bytes were
2292        // skipped" is not the same as "no audio is missing": a run cut
2293        // exactly at a frame boundary loses everything before it and says so
2294        // through this gap's sample range. A gap that turns out to be empty
2295        // in both bytes and samples is dropped by `resolve_skips`.
2296        pending.push(PendingSkip {
2297            bytes: 0..first as u64,
2298            before: None,
2299            after: Some(header.coded_number),
2300            reason: FlacSkipReason::NoSyncPoint,
2301        });
2302
2303        let mut blocking = None;
2304        let mut widest_block = 0u32;
2305        let mut last: Option<(u64, u32)> = None;
2306        let mut first_coded: Option<u64> = None;
2307        // The frame decoded immediately before the current one with no gap
2308        // between them, which is the pair `Numbering` reads the coding of the
2309        // number off, and what it concluded.
2310        let mut adjacent: Option<(u64, u32)> = None;
2311        let mut frame_numbered: Option<bool> = None;
2312        let mut at = first;
2313        let mut skip_from = first;
2314        let mut reason = FlacSkipReason::NoSyncPoint;
2315        let mut locked = true;
2316
2317        while at < self.bytes.len() {
2318            if locked {
2319                let step = parse_frame_header(&self.bytes[at..], at as u64).and_then(|header| {
2320                    decoder
2321                        .decode_frame(&self.bytes[at..], at as u64, output)
2322                        .map(|consumed| (header, consumed))
2323                });
2324                match step {
2325                    Ok((header, consumed)) => {
2326                        blocking = Some(header.blocking);
2327                        widest_block = widest_block.max(header.block_size);
2328                        first_coded.get_or_insert(header.coded_number);
2329                        // Two frames back to back settle whether the coded
2330                        // number counts frames or samples, whatever the
2331                        // header's blocking bit claims.
2332                        if frame_numbered.is_none() {
2333                            if let Some((before, block)) = adjacent {
2334                                if header.coded_number == before + 1 {
2335                                    frame_numbered = Some(true);
2336                                } else if header.coded_number == before + u64::from(block) {
2337                                    frame_numbered = Some(false);
2338                                }
2339                            }
2340                        }
2341                        adjacent = Some((header.coded_number, header.block_size));
2342                        last = adjacent;
2343                        at += consumed;
2344                        skip_from = at;
2345                    }
2346                    Err(_) => {
2347                        // Sync is lost as of this frame. Everything from here
2348                        // to the next established sync point is a gap.
2349                        locked = false;
2350                        adjacent = None;
2351                        reason = FlacSkipReason::FrameRejected;
2352                        at += 1;
2353                    }
2354                }
2355                continue;
2356            }
2357
2358            let Some((start, header)) = self.find_sync(at, &mut trial, &mut scratch) else {
2359                break;
2360            };
2361            pending.push(PendingSkip {
2362                bytes: skip_from as u64..start as u64,
2363                before: last,
2364                after: Some(header.coded_number),
2365                reason,
2366            });
2367            reason = FlacSkipReason::NoSyncPoint;
2368            at = start;
2369            skip_from = start;
2370            locked = true;
2371            adjacent = None;
2372        }
2373
2374        if skip_from < self.bytes.len() {
2375            pending.push(PendingSkip {
2376                bytes: skip_from as u64..end,
2377                before: last,
2378                after: None,
2379                reason,
2380            });
2381        }
2382        let numbering = Numbering {
2383            // The measured answer where there was a pair to measure, and the
2384            // header's own claim where there was only one frame.
2385            frame_numbered: frame_numbered.unwrap_or(blocking == Some(Blocking::Fixed)),
2386            known: blocking.is_some(),
2387            widest: widest_block,
2388            total: info.total_samples,
2389            from_zero: self.info.is_some(),
2390        };
2391        let mut report = FlacRecoveryReport {
2392            samples: output.len() - before,
2393            // Replaced below. Starting from the pessimistic value means a
2394            // path added here that forgets to set it under-claims rather than
2395            // over-claims.
2396            md5: Md5Check::AudioIncomplete,
2397            skipped: resolve_skips(&pending, &numbering),
2398            first_frame: first_coded.and_then(|coded| numbering.position(coded)),
2399            stream_info: info,
2400        };
2401
2402        // The checksum describes the whole stream, so it is only worth
2403        // checking when the whole stream is what was decoded, and `finish`
2404        // would otherwise reject a recovery for doing exactly what it was
2405        // asked to do.
2406        report.md5 = if report.frames_lost() != Some(0) {
2407            Md5Check::AudioIncomplete
2408        } else if self.info.is_none() {
2409            Md5Check::NoStreamInfo
2410        } else if info.md5.is_none() {
2411            decoder.finish(end)?;
2412            Md5Check::ChecksumUnset
2413        } else {
2414            decoder.finish(end)?;
2415            Md5Check::Verified
2416        };
2417        Ok(report)
2418    }
2419
2420    /// Recovers the whole input, bound to the spec that describes it.
2421    ///
2422    /// # Errors
2423    ///
2424    /// As [`decode`](Self::decode).
2425    pub fn decode_to_end(&self) -> Result<(AudioBuffer, FlacRecoveryReport), DecodeError> {
2426        let mut samples = Vec::new();
2427        let report = self.decode(&mut samples)?;
2428        let spec = report.stream_info.spec;
2429        Ok((AudioBuffer::from_samples(spec, samples), report))
2430    }
2431
2432    /// Finds the next position at or after `from` that survives chained
2433    /// validation, with the header it parsed there.
2434    ///
2435    /// The cheap test comes first and rejects all but about one position in
2436    /// 32,768: a frame begins `0xFF` followed by a byte whose top seven bits
2437    /// complete the sync code. Only then is a header parsed, and only then is
2438    /// the frame trial-decoded.
2439    ///
2440    /// `trial` and `scratch` are the caller's, reused across every candidate
2441    /// and across every call, for the reason recorded on
2442    /// [`FrameDecoder::reset_to`]. Each candidate is still judged in
2443    /// isolation: the decoder is reset to its just-constructed state before
2444    /// every trial, so what is shared is the allocation and nothing else.
2445    fn find_sync(
2446        &self,
2447        from: usize,
2448        trial: &mut Option<FrameDecoder>,
2449        scratch: &mut Vec<f32>,
2450    ) -> Option<(usize, FrameHeader)> {
2451        let last_start = self.bytes.len().checked_sub(MIN_FRAME_HEADER_BYTES)?;
2452        for start in from..=last_start {
2453            if self.bytes[start] != 0xFF || self.bytes[start + 1] & 0xFE != 0xF8 {
2454                continue;
2455            }
2456            let Ok(header) = parse_frame_header(&self.bytes[start..], start as u64) else {
2457                continue;
2458            };
2459            let info = match self.info {
2460                Some(info) => info,
2461                None => match derive_stream_info(&header, start as u64) {
2462                    Ok(info) => info,
2463                    // A frame deferring a field to a streaminfo block that is
2464                    // not there is not decodable, so it is not a sync point.
2465                    Err(_) => continue,
2466                },
2467            };
2468            let streaminfo = self.info.is_some();
2469            let trial = trial.get_or_insert_with(|| FrameDecoder::build(info, streaminfo));
2470            trial.reset_to(info, streaminfo);
2471            scratch.clear();
2472            let Ok(consumed) = trial.decode_frame(&self.bytes[start..], start as u64, scratch)
2473            else {
2474                continue;
2475            };
2476            let next = start + consumed;
2477            if next == self.bytes.len()
2478                || parse_frame_header(&self.bytes[next..], next as u64).is_ok()
2479            {
2480                return Some((start, header));
2481            }
2482        }
2483        None
2484    }
2485}
2486
2487/// What the scan of the input established about the stream's numbering.
2488///
2489/// # Why the header bit is not taken at its word
2490///
2491/// RFC 9639 section 9.1.5 says a fixed-blocksize stream codes a frame number
2492/// and a variable-blocksize one codes a sample number. The bit that says
2493/// which was reserved in earlier versions of the format, and encoders of that
2494/// era wrote variable-blocksize streams with the bit clear and sample numbers
2495/// in the field. The conformance corpus carries one, written by Flake 0.11,
2496/// where reading the field as a frame number overstates a gap by a factor of
2497/// its block size.
2498///
2499/// So the two readings are told apart by measurement rather than by the bit:
2500/// two frames decoded back to back differ by one under frame numbering and by
2501/// a whole block under sample numbering, and a block is never one sample, so
2502/// the first consecutive pair settles it. The bit is only the starting guess,
2503/// used when the input held a single frame and there is no pair to look at.
2504struct Numbering {
2505    /// Whether the coded number is a frame number, as measured above.
2506    frame_numbered: bool,
2507    /// Whether either reading is available at all: without a decoded frame
2508    /// there is no blocking strategy to read.
2509    known: bool,
2510    /// The largest block size any recovered frame carried, which for a
2511    /// genuinely fixed-blocksize stream is its constant block size.
2512    widest: u32,
2513    /// The declared sample count, when there is one. The only thing that can
2514    /// close a gap running to the end of the input.
2515    total: Option<u64>,
2516    /// Whether the stream is known to be numbered from zero, which is true
2517    /// exactly when a streaminfo block described it: a stream with a
2518    /// streaminfo block starts where the stream starts.
2519    from_zero: bool,
2520}
2521
2522impl Numbering {
2523    /// The interchannel sample position a coded number names.
2524    fn position(&self, coded: u64) -> Option<u64> {
2525        match (self.known, self.frame_numbered) {
2526            (false, _) => None,
2527            (true, false) => Some(coded),
2528            (true, true) if self.widest > 0 => Some(coded * u64::from(self.widest)),
2529            (true, true) => None,
2530        }
2531    }
2532}
2533
2534/// Turns the coded numbers recorded either side of each gap into sample
2535/// positions.
2536fn resolve_skips(pending: &[PendingSkip], numbering: &Numbering) -> Vec<FlacSkip> {
2537    pending
2538        .iter()
2539        .map(|skip| {
2540            let start = match skip.before {
2541                Some((coded, block)) => numbering.position(coded).map(|at| at + u64::from(block)),
2542                // Nothing was decoded before this gap. Where the stream's
2543                // numbering begins is only knowable if something said so.
2544                None if numbering.from_zero => Some(0),
2545                None => match skip.after.and_then(|coded| numbering.position(coded)) {
2546                    // Unless the frame it resumed at is the stream's own
2547                    // first, in which case the gap plainly cost nothing.
2548                    Some(0) => Some(0),
2549                    _ => None,
2550                },
2551            };
2552            let end = match skip.after {
2553                Some(coded) => numbering.position(coded),
2554                None => numbering.total,
2555            };
2556            FlacSkip {
2557                bytes: skip.bytes.clone(),
2558                frames: match (start, end) {
2559                    (Some(start), Some(end)) => Some(start..end.max(start)),
2560                    _ => None,
2561                },
2562                reason: skip.reason,
2563            }
2564        })
2565        // A gap that cost no bytes and no frames is not a gap. This drops
2566        // the placeholder the scan always records at the front, for the
2567        // ordinary case where the input opens on the stream's first frame.
2568        .filter(|skip| {
2569            !(skip.bytes.is_empty() && skip.frames.as_ref().is_some_and(Range::is_empty))
2570        })
2571        .collect()
2572}
2573
2574// -- The streaming reader -----------------------------------------------------
2575
2576/// Where the streaming reader is in the stream.
2577#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2578enum State {
2579    /// Waiting for the four-byte `fLaC` signature.
2580    Signature,
2581    /// Waiting for a four-byte metadata block header.
2582    BlockHeader,
2583    /// Buffering the streaminfo body, the one metadata body that is read.
2584    StreaminfoBody { last: bool, offset: u64 },
2585    /// Discarding a metadata body that does not have to be read.
2586    SkipBlock { last: bool, left: u64 },
2587    /// Buffering and decoding audio frames.
2588    Audio,
2589    /// Past the end of the declared audio. Everything after it is discarded.
2590    Done,
2591}
2592
2593/// Reads a FLAC stream that arrives in pieces.
2594///
2595/// The [`StreamSource`] half of this module, with the same shape and the same
2596/// bounds as [`WavStreamDecoder`](crate::WavStreamDecoder) and
2597/// [`AiffStreamDecoder`](crate::AiffStreamDecoder). Nothing is buffered in
2598/// proportion to a size the file declared: the signature and block headers
2599/// are buffered, the streaminfo body is buffered at its fixed 34 bytes, every
2600/// other metadata body is discarded as it flows past, and one frame at a time
2601/// is held while it is assembled, capped at 2,101,216 bytes, which is the
2602/// largest frame the format can express plus room for its headers, and is a
2603/// figure stated in this crate rather than read from a file.
2604///
2605/// The MD5 is computed as frames are decoded and verified by
2606/// [`finish`](StreamSource::finish), so a streaming decode has the same
2607/// end-to-end check a whole-file decode has.
2608///
2609/// # Example
2610///
2611/// ```
2612/// use decibri_decode::{FlacStreamDecoder, StreamSource};
2613///
2614/// # let file: [u8; 73] = [
2615/// #     0x66, 0x4c, 0x61, 0x43, 0x80, 0x00, 0x00, 0x22, 0x10, 0x00, 0x10, 0x00,
2616/// #     0x00, 0x00, 0x1f, 0x00, 0x00, 0x1f, 0x07, 0xd0, 0x00, 0x70, 0x00, 0x00,
2617/// #     0x00, 0x18, 0xf8, 0xf9, 0xe3, 0x96, 0xf5, 0xcb, 0xcf, 0xc6, 0xdc, 0x80,
2618/// #     0x7f, 0x99, 0x77, 0x90, 0x6b, 0x32, 0xff, 0xf8, 0x68, 0x02, 0x00, 0x17,
2619/// #     0xe9, 0x44, 0x00, 0x4f, 0x6f, 0x31, 0x3d, 0x10, 0x47, 0xd2, 0x27, 0xcb,
2620/// #     0x6d, 0x09, 0x08, 0x31, 0x45, 0x2b, 0xdc, 0x28, 0x22, 0x22, 0x80, 0x57,
2621/// #     0xa3,
2622/// # ];
2623/// // `file` is RFC 9639 appendix D.3's worked example.
2624/// let mut stream = FlacStreamDecoder::new();
2625/// let mut samples = Vec::new();
2626/// for piece in file.chunks(5) {
2627///     let mut offset = 0;
2628///     while offset < piece.len() {
2629///         offset += stream.push(&piece[offset..])?;
2630///         while stream.pull(&mut samples, usize::MAX)? > 0 {}
2631///     }
2632/// }
2633/// stream.finish(&mut samples)?;
2634///
2635/// assert_eq!(stream.spec().map(|spec| spec.sample_rate), Some(32_000));
2636/// assert_eq!(samples.len(), 24);
2637/// # Ok::<(), decibri_decode::DecodeError>(())
2638/// ```
2639#[derive(Debug)]
2640pub struct FlacStreamDecoder {
2641    state: State,
2642    /// Bytes of a header, the streaminfo body or a frame that have not fully
2643    /// arrived. Bounded by [`MAX_FRAME_BYTES`].
2644    pending: Vec<u8>,
2645    /// Byte offset of the next byte to arrive, for error reporting.
2646    offset: u64,
2647    /// Where the frame currently being assembled starts in the input.
2648    frame_offset: u64,
2649    /// How many bytes of a frame must be held before decoding is worth
2650    /// retrying, from the last truncation.
2651    frame_needs: usize,
2652    info: Option<FlacStreamInfo>,
2653    md5_offset: u64,
2654    decoder: Option<FrameDecoder>,
2655    /// Whether `info`, once it arrives, is a streaminfo block rather than
2656    /// properties derived from the first frame. Set by the bare frame
2657    /// constructors; see [`FrameDecoder::streaminfo`].
2658    streaminfo: bool,
2659    /// What [`finish`](StreamSource::finish) did about the checksum, once it
2660    /// has run.
2661    md5: Option<Md5Check>,
2662    /// Decoded samples not yet pulled, and how far into them the caller is.
2663    ready: Vec<f32>,
2664    ready_read: usize,
2665    finished: bool,
2666    /// Which constructor built this reader, so `reset` returns it to that
2667    /// starting state rather than to one waiting for a signature it will
2668    /// never be sent.
2669    origin: Origin,
2670}
2671
2672/// Which of [`FlacStreamDecoder`]'s three constructors built a reader.
2673#[derive(Debug, Clone, Copy)]
2674enum Origin {
2675    /// A whole FLAC stream, signature first.
2676    Stream,
2677    /// Bare frames, with the properties to come from the first of them.
2678    BareFrames,
2679    /// Bare frames described by a streaminfo block from out of band.
2680    BareFramesWith(FlacStreamInfo),
2681}
2682
2683impl Default for FlacStreamDecoder {
2684    fn default() -> Self {
2685        Self::new()
2686    }
2687}
2688
2689impl FlacStreamDecoder {
2690    /// A reader waiting for the first byte of a stream.
2691    pub fn new() -> Self {
2692        Self::from_origin(Origin::Stream)
2693    }
2694
2695    /// A reader for a **bare frame stream**: no `fLaC` signature and no
2696    /// metadata, the first byte pushed is the first byte of a frame header.
2697    ///
2698    /// The streaming half of [`FlacFrameReader`], with the same properties
2699    /// and the same two escape-code rejections. [`spec`](StreamSource::spec)
2700    /// and [`stream_info`](Self::stream_info) answer `None` until the first
2701    /// frame header has arrived, which is what they already mean on this type
2702    /// and why a bare stream needs no separate way of saying it.
2703    pub fn frames() -> Self {
2704        Self::from_origin(Origin::BareFrames)
2705    }
2706
2707    /// A reader for a bare frame stream described by a streaminfo block the
2708    /// caller obtained elsewhere.
2709    ///
2710    /// This is the Ogg and Matroska shape: streaminfo in the container's
2711    /// codec-private header, bare frames in the packets. The block's bytes
2712    /// become an `info` through [`FlacStreamInfo::from_block`]. It resolves
2713    /// the two escape codes and restores the MD5 check to a path that
2714    /// otherwise has none. See [`md5_check`](Self::md5_check), which is how
2715    /// a caller finds out whether that check actually ran.
2716    pub fn frames_with_stream_info(info: FlacStreamInfo) -> Self {
2717        Self::from_origin(Origin::BareFramesWith(info))
2718    }
2719
2720    /// The three constructors' shared body, and what
2721    /// [`reset`](StreamSource::reset) rebuilds from.
2722    fn from_origin(origin: Origin) -> Self {
2723        let mut reader = Self {
2724            state: State::Signature,
2725            pending: Vec::new(),
2726            offset: 0,
2727            frame_offset: 0,
2728            frame_needs: MIN_FRAME_HEADER_BYTES,
2729            info: None,
2730            md5_offset: 0,
2731            decoder: None,
2732            streaminfo: true,
2733            md5: None,
2734            ready: Vec::new(),
2735            ready_read: 0,
2736            finished: false,
2737            origin,
2738        };
2739        match origin {
2740            Origin::Stream => {}
2741            Origin::BareFrames => {
2742                reader.state = State::Audio;
2743                reader.streaminfo = false;
2744            }
2745            Origin::BareFramesWith(info) => {
2746                reader.state = State::Audio;
2747                reader.info = Some(info);
2748                reader.decoder = Some(FrameDecoder::new(info));
2749            }
2750        }
2751        reader
2752    }
2753
2754    /// What the streaminfo metadata block declared, once it has arrived.
2755    ///
2756    /// For a bare frame stream this is the description derived from the first
2757    /// frame, or the one the caller supplied.
2758    pub const fn stream_info(&self) -> Option<FlacStreamInfo> {
2759        self.info
2760    }
2761
2762    /// What [`finish`](StreamSource::finish) did about the streaminfo MD5, or
2763    /// `None` before it has run.
2764    ///
2765    /// `None` is not a verdict. The check happens at the end of the stream
2766    /// and this reports what happened, never what is expected to happen, so a
2767    /// caller cannot read a guarantee off a decode that has not finished.
2768    pub const fn md5_check(&self) -> Option<Md5Check> {
2769        self.md5
2770    }
2771
2772    /// How many interleaved samples are decoded and waiting to be pulled:
2773    /// frames times channels, which is the length a caller's output vector
2774    /// grows by when they are.
2775    ///
2776    /// Interleaved samples, not the frames [`pull`](StreamSource::pull)
2777    /// counts; the two figures differ by the channel count.
2778    pub fn ready_samples(&self) -> usize {
2779        self.ready.len() - self.ready_read
2780    }
2781
2782    /// Buffers `bytes` into `pending` until it holds `need` of them, and says
2783    /// whether it now does.
2784    fn accumulate(&mut self, bytes: &[u8], need: usize, taken: &mut usize) -> bool {
2785        let want = need.saturating_sub(self.pending.len()).min(bytes.len());
2786        self.pending.extend_from_slice(&bytes[..want]);
2787        *taken += want;
2788        self.offset += want as u64;
2789        self.pending.len() >= need
2790    }
2791
2792    /// Reads a buffered metadata block header and decides what to do with the
2793    /// body.
2794    fn start_block(&mut self) -> Result<(), DecodeError> {
2795        let at = self.offset - METADATA_HEADER_BYTES as u64;
2796        let mut header = [0u8; METADATA_HEADER_BYTES];
2797        header.copy_from_slice(&self.pending);
2798        self.pending.clear();
2799        let last = header[0] & 0x80 != 0;
2800        let kind = header[0] & 0x7F;
2801        let length =
2802            (u64::from(header[1]) << 16) | (u64::from(header[2]) << 8) | u64::from(header[3]);
2803
2804        if kind == BLOCK_FORBIDDEN {
2805            return Err(DecodeError::Malformed {
2806                expected: "a metadata block type other than the forbidden 127",
2807                offset: at,
2808            });
2809        }
2810        if kind == BLOCK_STREAMINFO {
2811            if self.info.is_some() {
2812                return Err(DecodeError::Malformed {
2813                    expected: "exactly one streaminfo metadata block",
2814                    offset: at,
2815                });
2816            }
2817            if length != STREAMINFO_BYTES as u64 {
2818                return Err(DecodeError::Malformed {
2819                    expected: "a streaminfo block of exactly 34 bytes",
2820                    offset: at,
2821                });
2822            }
2823            self.state = State::StreaminfoBody {
2824                last,
2825                offset: self.offset,
2826            };
2827            return Ok(());
2828        }
2829        if self.info.is_none() {
2830            return Err(DecodeError::Malformed {
2831                expected: "a streaminfo block first among the metadata blocks",
2832                offset: at,
2833            });
2834        }
2835        self.state = if length == 0 {
2836            self.enter_audio(last)
2837        } else {
2838            State::SkipBlock { last, left: length }
2839        };
2840        Ok(())
2841    }
2842
2843    /// The state to move to once a metadata block has been stepped over.
2844    fn enter_audio(&mut self, last: bool) -> State {
2845        if last {
2846            self.frame_offset = self.offset;
2847            self.frame_needs = MIN_FRAME_HEADER_BYTES;
2848            State::Audio
2849        } else {
2850            State::BlockHeader
2851        }
2852    }
2853
2854    /// Reads the buffered streaminfo body.
2855    fn finish_streaminfo(&mut self, last: bool, offset: u64) -> Result<(), DecodeError> {
2856        let info = parse_streaminfo(&self.pending, offset)?;
2857        self.pending.clear();
2858        self.info = Some(info);
2859        self.md5_offset = offset + 18;
2860        self.decoder = Some(FrameDecoder::new(info));
2861        self.state = self.enter_audio(last);
2862        Ok(())
2863    }
2864
2865    /// Decodes as many whole frames out of `pending` as it holds.
2866    ///
2867    /// A frame has no length field, so the only way to find its end is to
2868    /// decode it. A truncation is not a failure here: it says the rest has
2869    /// not arrived, and the byte count it carries is remembered so the next
2870    /// attempt waits until it could possibly succeed rather than re-parsing
2871    /// the same partial frame on every push.
2872    fn drain_frames(&mut self) -> Result<(), DecodeError> {
2873        while self.pending.len() >= self.frame_needs {
2874            // A bare frame stream has no streaminfo block, so the first frame
2875            // header is where the stream's properties come from. Every other
2876            // path has a decoder before it ever reaches this state.
2877            if self.decoder.is_none() {
2878                match parse_frame_header(&self.pending, self.frame_offset) {
2879                    Ok(header) => {
2880                        let info = derive_stream_info(&header, self.frame_offset)?;
2881                        self.info = Some(info);
2882                        self.decoder = Some(FrameDecoder::from_first_frame(info));
2883                    }
2884                    Err(DecodeError::Truncated { expected, .. }) => {
2885                        self.frame_needs = (expected as usize).max(self.pending.len() + 1);
2886                        return Ok(());
2887                    }
2888                    Err(other) => return Err(other),
2889                }
2890            }
2891            let Some(decoder) = self.decoder.as_mut() else {
2892                return Ok(());
2893            };
2894            if let Some(info) = self.info {
2895                if info
2896                    .total_samples
2897                    .is_some_and(|total| decoder.samples_done >= total)
2898                {
2899                    self.state = State::Done;
2900                    self.pending.clear();
2901                    return Ok(());
2902                }
2903            }
2904            match decoder.decode_frame(&self.pending, self.frame_offset, &mut self.ready) {
2905                Ok(consumed) => {
2906                    self.pending.drain(..consumed);
2907                    self.frame_offset += consumed as u64;
2908                    self.frame_needs = MIN_FRAME_HEADER_BYTES;
2909                }
2910                Err(DecodeError::Truncated { expected, .. }) => {
2911                    // Wait for at least one more byte than is held, and for
2912                    // at least as many as the parse said it wanted.
2913                    self.frame_needs = (expected as usize).max(self.pending.len() + 1);
2914                    if self.frame_needs > MAX_FRAME_BYTES {
2915                        return Err(DecodeError::Malformed {
2916                            expected: "a frame no larger than the format's own maximum",
2917                            offset: self.frame_offset,
2918                        });
2919                    }
2920                    return Ok(());
2921                }
2922                Err(other) => return Err(other),
2923            }
2924        }
2925        Ok(())
2926    }
2927
2928    /// The body of [`push`](StreamSource::push), split out so a failure can
2929    /// set the finished flag in one place.
2930    fn push_inner(&mut self, bytes: &[u8], taken: &mut usize) -> Result<(), DecodeError> {
2931        while *taken < bytes.len() {
2932            let rest = &bytes[*taken..];
2933            match self.state {
2934                State::Signature => {
2935                    if !self.accumulate(rest, 4, taken) {
2936                        break;
2937                    }
2938                    let tag = FourCc([
2939                        self.pending[0],
2940                        self.pending[1],
2941                        self.pending[2],
2942                        self.pending[3],
2943                    ]);
2944                    self.pending.clear();
2945                    if tag != MAGIC {
2946                        return Err(DecodeError::UnsupportedContainer { tag });
2947                    }
2948                    self.state = State::BlockHeader;
2949                }
2950                State::BlockHeader => {
2951                    if !self.accumulate(rest, METADATA_HEADER_BYTES, taken) {
2952                        break;
2953                    }
2954                    self.start_block()?;
2955                }
2956                State::StreaminfoBody { last, offset } => {
2957                    if !self.accumulate(rest, STREAMINFO_BYTES, taken) {
2958                        break;
2959                    }
2960                    self.finish_streaminfo(last, offset)?;
2961                }
2962                State::SkipBlock { last, left } => {
2963                    let step = left.min(rest.len() as u64);
2964                    *taken += step as usize;
2965                    self.offset += step;
2966                    let left = left - step;
2967                    self.state = if left == 0 {
2968                        self.enter_audio(last)
2969                    } else {
2970                        State::SkipBlock { last, left }
2971                    };
2972                }
2973                State::Audio => {
2974                    if self.ready.len() - self.ready_read >= READY_LIMIT {
2975                        // Back-pressure: the caller has to pull before the
2976                        // reader will take more.
2977                        break;
2978                    }
2979                    let room = MAX_FRAME_BYTES - self.pending.len();
2980                    if room == 0 {
2981                        return Err(DecodeError::Malformed {
2982                            expected: "a frame no larger than the format's own maximum",
2983                            offset: self.frame_offset,
2984                        });
2985                    }
2986                    let step = room.min(rest.len());
2987                    self.pending.extend_from_slice(&rest[..step]);
2988                    *taken += step;
2989                    self.offset += step as u64;
2990                    self.drain_frames()?;
2991                }
2992                State::Done => {
2993                    // A trailing tag is not this reader's business; the audio
2994                    // it was promised is complete.
2995                    self.offset += (bytes.len() - *taken) as u64;
2996                    *taken = bytes.len();
2997                }
2998            }
2999        }
3000        Ok(())
3001    }
3002}
3003
3004impl StreamSource for FlacStreamDecoder {
3005    fn push(&mut self, bytes: &[u8]) -> Result<usize, DecodeError> {
3006        if self.finished {
3007            return Ok(0);
3008        }
3009        let mut taken = 0;
3010        let result = self.push_inner(bytes, &mut taken);
3011        if result.is_err() {
3012            // A stream that has failed structurally is over, for the reason
3013            // recorded on the WAV reader: a caller who keeps pushing must not
3014            // get a second, different answer from the same stream.
3015            self.finished = true;
3016        }
3017        result.map(|()| taken)
3018    }
3019
3020    fn pull(&mut self, output: &mut Vec<f32>, max_frames: usize) -> Result<usize, DecodeError> {
3021        let Some(info) = self.info else {
3022            return Ok(0);
3023        };
3024        let channels = usize::from(info.spec.channels);
3025        let available = self.ready.len() - self.ready_read;
3026        let frames = (available / channels).min(max_frames);
3027        let count = frames * channels;
3028        output.extend_from_slice(&self.ready[self.ready_read..self.ready_read + count]);
3029        self.ready_read += count;
3030        // Amortised compaction, exactly as the other two readers do it.
3031        if self.ready_read == self.ready.len() {
3032            self.ready.clear();
3033            self.ready_read = 0;
3034        } else if self.ready_read >= self.ready.len() / 2 {
3035            self.ready.drain(..self.ready_read);
3036            self.ready_read = 0;
3037        }
3038        Ok(frames)
3039    }
3040
3041    fn spec(&self) -> Option<AudioSpec> {
3042        self.info.map(|info| info.spec)
3043    }
3044
3045    fn buffered_bytes(&self) -> usize {
3046        self.pending.len()
3047    }
3048
3049    fn finish(&mut self, output: &mut Vec<f32>) -> Result<usize, DecodeError> {
3050        if self.finished {
3051            return Ok(0);
3052        }
3053        self.finished = true;
3054
3055        match self.state {
3056            State::Done => {}
3057            State::Signature => {
3058                return Err(DecodeError::Truncated {
3059                    expected: 4,
3060                    available: self.pending.len() as u64,
3061                })
3062            }
3063            State::BlockHeader => {
3064                return Err(DecodeError::Truncated {
3065                    expected: METADATA_HEADER_BYTES as u64,
3066                    available: self.pending.len() as u64,
3067                })
3068            }
3069            State::StreaminfoBody { .. } => {
3070                return Err(DecodeError::Truncated {
3071                    expected: STREAMINFO_BYTES as u64,
3072                    available: self.pending.len() as u64,
3073                })
3074            }
3075            State::SkipBlock { left, .. } => {
3076                return Err(DecodeError::Truncated {
3077                    expected: left,
3078                    available: 0,
3079                })
3080            }
3081            State::Audio => {
3082                // A stream can end on a frame boundary; anything left over is
3083                // a frame that never completed.
3084                if !self.pending.is_empty() {
3085                    return Err(DecodeError::Truncated {
3086                        expected: self.frame_needs as u64,
3087                        available: self.pending.len() as u64,
3088                    });
3089                }
3090            }
3091        }
3092
3093        if let Some(decoder) = self.decoder.take() {
3094            // A supplied streaminfo block is not in this input, so a checksum
3095            // rejection names where the decode concluded rather than a byte
3096            // that does not exist. The metadata walk sets `md5_offset` to a
3097            // real position, never zero, since a streaminfo body cannot
3098            // start before byte 26, and the bare frame constructors leave it
3099            // at zero.
3100            let at = if self.md5_offset == 0 {
3101                self.offset
3102            } else {
3103                self.md5_offset
3104            };
3105            decoder.finish(at)?;
3106        }
3107        let Some(info) = self.info else {
3108            return Ok(0);
3109        };
3110        // Set only once `finish` has actually run the check, so `md5_check`
3111        // reports what happened rather than what was expected to.
3112        self.md5 = Some(if !self.streaminfo {
3113            Md5Check::NoStreamInfo
3114        } else if info.md5.is_none() {
3115            Md5Check::ChecksumUnset
3116        } else {
3117            Md5Check::Verified
3118        });
3119        let channels = usize::from(info.spec.channels);
3120        let frames = (self.ready.len() - self.ready_read) / channels;
3121        output.extend_from_slice(&self.ready[self.ready_read..self.ready_read + frames * channels]);
3122        self.ready.clear();
3123        self.ready_read = 0;
3124        Ok(frames)
3125    }
3126
3127    fn reset(&mut self) {
3128        *self = Self::from_origin(self.origin);
3129    }
3130}
3131
3132// -- Deterministic mathematics for the writer ---------------------------------
3133//
3134// The writer's searches need a cosine (for the analysis window) and a base-2
3135// logarithm (for size estimation). `f64::cos` and `f64::ln` are libm calls
3136// whose last bits vary between platforms, which would put the crate's
3137// byte-identical claim at the mercy of whichever libm linked, so both are
3138// computed here from arithmetic IEEE 754 fully specifies: add, subtract,
3139// multiply and divide. Accuracy in the last few bits does not matter for a
3140// window shape or a search heuristic; producing the same bits everywhere
3141// does.
3142
3143/// `cos(pi * x)` for `x` in `[0, 1]`, by Taylor series after folding onto
3144/// `[0, 0.5]`.
3145///
3146/// Ten terms leave the truncation error near 1e-12 at the fold point, far
3147/// below anything a window shape can express in encoded bytes, and every
3148/// operation is exactly rounded per IEEE 754, so the result is bit-identical
3149/// on every target.
3150fn det_cos_pi(x: f64) -> f64 {
3151    let (x, sign) = if x > 0.5 { (1.0 - x, -1.0) } else { (x, 1.0) };
3152    let theta = x * std::f64::consts::PI;
3153    let z = theta * theta;
3154    let mut sum = 1.0f64;
3155    let mut term = 1.0f64;
3156    for k in 1i32..=10 {
3157        term *= -z / f64::from((2 * k - 1) * (2 * k));
3158        sum += term;
3159    }
3160    sign * sum
3161}
3162
3163/// `log2(x)` for positive finite `x`, from the exponent field and an atanh
3164/// series over the mantissa.
3165///
3166/// The mantissa lands in `[1, 2)`, so the series variable is at most `1/3`
3167/// and twelve terms leave the error near 1e-12. Used only to rank predictor
3168/// orders, where being deterministic matters and the last bits do not.
3169fn det_log2(x: f64) -> f64 {
3170    debug_assert!(x > 0.0 && x.is_finite());
3171    let bits = x.to_bits();
3172    let raw_exponent = (bits >> 52) & 0x7FF;
3173    if raw_exponent == 0 {
3174        // Subnormal: scale into the normal range and correct afterwards.
3175        return det_log2(x * (1u64 << 60) as f64) - 60.0;
3176    }
3177    let exponent = raw_exponent as i64 - 1023;
3178    let mantissa = f64::from_bits((bits & ((1u64 << 52) - 1)) | (1023u64 << 52));
3179    let z = (mantissa - 1.0) / (mantissa + 1.0);
3180    let z_squared = z * z;
3181    let mut term = z;
3182    let mut sum = 0.0f64;
3183    for k in 0i32..12 {
3184        sum += term / f64::from(2 * k + 1);
3185        term *= z_squared;
3186    }
3187    exponent as f64 + 2.0 * sum * std::f64::consts::LOG2_E
3188}
3189
3190// -- The bit writer -----------------------------------------------------------
3191
3192/// A most-significant-bit-first writer, the mirror of [`BitReader`].
3193///
3194/// Bits accumulate right-aligned in a 64-bit word and flush to bytes as they
3195/// fill. Every write is at most [`WINDOW_BITS`] bits, so with at most seven
3196/// held bits the accumulator cannot overflow.
3197struct BitWriter {
3198    out: Vec<u8>,
3199    /// Bits not yet flushed, right-aligned. At most seven after any write.
3200    accumulator: u64,
3201    /// How many bits `accumulator` holds.
3202    filled: u32,
3203}
3204
3205impl BitWriter {
3206    fn new() -> Self {
3207        Self {
3208            out: Vec::new(),
3209            accumulator: 0,
3210            filled: 0,
3211        }
3212    }
3213
3214    /// Appends the low `count` bits of `value`, most significant first.
3215    fn write(&mut self, value: u64, count: u32) {
3216        debug_assert!((1..=WINDOW_BITS).contains(&count));
3217        debug_assert!(count == 64 || value >> count == 0);
3218        self.accumulator = (self.accumulator << count) | value;
3219        self.filled += count;
3220        while self.filled >= 8 {
3221            self.filled -= 8;
3222            self.out.push((self.accumulator >> self.filled) as u8);
3223        }
3224    }
3225
3226    /// Appends `value` as `count` bits of two's complement.
3227    fn write_signed(&mut self, value: i64, count: u32) {
3228        let mask = if count >= 64 {
3229            u64::MAX
3230        } else {
3231            (1u64 << count) - 1
3232        };
3233        self.write(value as u64 & mask, count);
3234    }
3235
3236    /// Appends `quotient` zero bits and a terminating one bit, the unary
3237    /// form [`BitReader::read_unary`] reads.
3238    fn write_unary(&mut self, quotient: u64) {
3239        let mut left = quotient;
3240        while left >= 32 {
3241            self.write(0, 32);
3242            left -= 32;
3243        }
3244        // A one in `left + 1` bits is exactly `left` zeros then the one.
3245        self.write(1, left as u32 + 1);
3246    }
3247
3248    /// Pads with zero bits to the next byte boundary.
3249    fn align(&mut self) {
3250        if self.filled > 0 {
3251            self.write(0, 8 - self.filled);
3252        }
3253    }
3254
3255    /// The bytes written so far. Only meaningful at a byte boundary, which
3256    /// is where both CRC computations happen.
3257    fn bytes(&self) -> &[u8] {
3258        debug_assert_eq!(self.filled, 0);
3259        &self.out
3260    }
3261
3262    /// The finished bytes, aligned.
3263    fn into_bytes(mut self) -> Vec<u8> {
3264        self.align();
3265        self.out
3266    }
3267}
3268
3269/// Writes RFC 9639 section 9.1.5's UTF-8-like coded number, the shortest
3270/// form that holds `value`.
3271///
3272/// The mirror of [`read_coded_number`], for values up to 36 bits.
3273fn write_coded_number(writer: &mut BitWriter, value: u64) {
3274    debug_assert!(value < 1u64 << 36);
3275    if value < 0x80 {
3276        writer.write(value, 8);
3277        return;
3278    }
3279    // Two through seven octets carry 11, 16, 21, 26, 31 and 36 payload bits.
3280    let mut octets = 2u32;
3281    while octets < 7 && value >= 1u64 << (6 * (octets - 1) + (7 - octets)) {
3282        octets += 1;
3283    }
3284    let lead = (0xFFu64 << (8 - octets)) & 0xFF;
3285    writer.write(lead | (value >> (6 * (octets - 1))), 8);
3286    for step in (0..octets - 1).rev() {
3287        writer.write(0x80 | ((value >> (6 * step)) & 0x3F), 8);
3288    }
3289}
3290
3291// -- What a compression level means -------------------------------------------
3292
3293/// How the writer chooses between the stereo decorrelations.
3294#[derive(Debug, Clone, Copy, PartialEq, Eq)]
3295enum Stereo {
3296    /// Two independent subframes, no search.
3297    Independent,
3298    /// The four modes ranked by a cheap estimate over each candidate
3299    /// channel's second difference, and only the winner's two subframes
3300    /// actually searched.
3301    Estimated,
3302    /// All four candidate channels searched in full and the cheapest pair
3303    /// taken, at twice the subframe work of [`Stereo::Estimated`].
3304    Exhaustive,
3305}
3306
3307/// The analysis windows a level applies before autocorrelation.
3308///
3309/// A rectangular window leaks the block's edges into every lag, so some
3310/// taper is always worth its cost; which taper wins depends on the material,
3311/// which is why the upper levels try more than one and keep the cheapest
3312/// result.
3313#[derive(Debug, Clone, Copy, PartialEq, Eq)]
3314enum WindowShape {
3315    /// Tukey with a quarter of the block tapered: flat over the middle half.
3316    Tukey50,
3317    /// Hann, a Tukey window whose taper is the whole block.
3318    Hann,
3319    /// Tukey with an eighth of the block tapered at each end.
3320    Tukey25,
3321}
3322
3323impl WindowShape {
3324    /// The window as coefficients for a block of `len` samples.
3325    fn build(self, len: usize) -> Vec<f64> {
3326        let alpha = match self {
3327            Self::Tukey50 => 0.5,
3328            Self::Hann => 1.0,
3329            Self::Tukey25 => 0.25,
3330        };
3331        if len <= 1 {
3332            return vec![1.0; len];
3333        }
3334        let taper = alpha * (len - 1) as f64 / 2.0;
3335        (0..len)
3336            .map(|index| {
3337                let edge = (index.min(len - 1 - index)) as f64;
3338                if taper <= 0.0 || edge >= taper {
3339                    1.0
3340                } else {
3341                    0.5 * (1.0 + det_cos_pi(1.0 - edge / taper))
3342                }
3343            })
3344            .collect()
3345    }
3346}
3347
3348/// What one compression level searches.
3349///
3350/// The levels bound the same search rather than switching algorithms, which
3351/// is what keeps their outputs mutually decodable and their meaning "spend
3352/// more time, get smaller files" and nothing else.
3353struct Level {
3354    /// Samples per frame, except the last.
3355    block_size: u32,
3356    /// How stereo decorrelation is chosen.
3357    stereo: Stereo,
3358    /// The highest linear predictor order tried, zero meaning fixed
3359    /// predictors only.
3360    max_lpc_order: usize,
3361    /// The deepest residual partitioning tried.
3362    max_partition_order: u32,
3363    /// The analysis windows tried.
3364    windows: &'static [WindowShape],
3365    /// How many predictor orders per window are exactly costed rather than
3366    /// only estimated.
3367    lpc_candidates: usize,
3368}
3369
3370/// The nine levels. Block sizes, predictor bounds and partition depths
3371/// broadly follow the reference encoder's documented presets: 1152-sample
3372/// blocks with fixed predictors below level 3, 4096-sample blocks with LPC
3373/// at 3 and above, order 8 at the middle levels and 12 at the top, and a
3374/// widening stereo and window search.
3375const LEVELS: [Level; 9] = [
3376    Level {
3377        block_size: 1152,
3378        stereo: Stereo::Independent,
3379        max_lpc_order: 0,
3380        max_partition_order: 3,
3381        windows: &[],
3382        lpc_candidates: 0,
3383    },
3384    Level {
3385        block_size: 1152,
3386        stereo: Stereo::Estimated,
3387        max_lpc_order: 0,
3388        max_partition_order: 3,
3389        windows: &[],
3390        lpc_candidates: 0,
3391    },
3392    Level {
3393        block_size: 1152,
3394        stereo: Stereo::Exhaustive,
3395        max_lpc_order: 0,
3396        max_partition_order: 3,
3397        windows: &[],
3398        lpc_candidates: 0,
3399    },
3400    Level {
3401        block_size: 4096,
3402        stereo: Stereo::Independent,
3403        max_lpc_order: 6,
3404        max_partition_order: 4,
3405        windows: &[WindowShape::Tukey50],
3406        lpc_candidates: 1,
3407    },
3408    Level {
3409        block_size: 4096,
3410        stereo: Stereo::Estimated,
3411        max_lpc_order: 8,
3412        max_partition_order: 4,
3413        windows: &[WindowShape::Tukey50],
3414        lpc_candidates: 1,
3415    },
3416    Level {
3417        block_size: 4096,
3418        stereo: Stereo::Exhaustive,
3419        max_lpc_order: 8,
3420        max_partition_order: 5,
3421        windows: &[WindowShape::Tukey50],
3422        lpc_candidates: 1,
3423    },
3424    Level {
3425        block_size: 4096,
3426        stereo: Stereo::Exhaustive,
3427        max_lpc_order: 8,
3428        max_partition_order: 6,
3429        windows: &[WindowShape::Tukey50],
3430        lpc_candidates: 2,
3431    },
3432    Level {
3433        block_size: 4096,
3434        stereo: Stereo::Exhaustive,
3435        max_lpc_order: 12,
3436        max_partition_order: 6,
3437        windows: &[WindowShape::Tukey50, WindowShape::Hann],
3438        lpc_candidates: 2,
3439    },
3440    Level {
3441        block_size: 4096,
3442        stereo: Stereo::Exhaustive,
3443        max_lpc_order: 12,
3444        max_partition_order: 6,
3445        windows: &[
3446            WindowShape::Tukey50,
3447            WindowShape::Hann,
3448            WindowShape::Tukey25,
3449        ],
3450        lpc_candidates: 3,
3451    },
3452];
3453
3454/// The quantised coefficient precision written for every LPC subframe.
3455///
3456/// Fifteen bits is the most the format's streamable subset permits and what
3457/// the reference encoder writes at 4096-sample blocks. The header cost is
3458/// `order * 15` bits per subframe, under half a percent of a typical frame,
3459/// and precision below this measurably loses prediction accuracy.
3460const COEFFICIENT_PRECISION: u32 = 15;
3461
3462/// The largest Rice parameter the 4-bit form can code. 15 is the escape.
3463const RICE4_MAX: u32 = 14;
3464
3465/// The largest Rice parameter the 5-bit form can code. 31 is the escape.
3466const RICE5_MAX: u32 = 30;
3467
3468// -- The residual search ------------------------------------------------------
3469
3470/// The best Rice partitioning found for one subframe's residual.
3471#[derive(Debug, Clone)]
3472struct ResidualPlan {
3473    /// The residual section's total cost in bits: method, partition order,
3474    /// every parameter field and every coded residual.
3475    bits: u64,
3476    /// The partition order to write.
3477    partition_order: u32,
3478    /// Whether the parameters use the 5-bit form.
3479    five_bit: bool,
3480    /// The Rice parameter for each partition, in order.
3481    parameters: Vec<u32>,
3482}
3483
3484/// The zigzag fold RFC 9639 section 9.2.7.4 stores residuals in:
3485/// non-negative values to even numbers, negative to odd.
3486fn zigzag(residual: i64) -> u64 {
3487    (residual.wrapping_shl(1) ^ (residual >> 63)) as u64
3488}
3489
3490/// Whether every residual fits the format's 32-bit folded range, which
3491/// RFC 9639 section 9.2.7.3 requires. A subframe that does not is not
3492/// Rice-codable and falls back to verbatim.
3493fn residual_in_range(residual: &[i64]) -> bool {
3494    residual
3495        .iter()
3496        .all(|&value| value.unsigned_abs() <= i32::MAX as u64)
3497}
3498
3499/// Finds the cheapest partition order and Rice parameters for `folded`,
3500/// which is the zigzag residual of a predictor of `order` over a block of
3501/// `block_size` samples.
3502///
3503/// Exact rather than estimated: per-partition sums of `value >> p` are
3504/// accumulated once at the deepest feasible order and merged pairwise
3505/// upward, so every (partition order, parameter) cell's true bit cost is
3506/// known and the minimum is the minimum, not a guess. The per-value work is
3507/// proportional to the bits the value will actually occupy, so this costs
3508/// about what writing the residual costs.
3509fn plan_residual(folded: &[u64], block_size: usize, order: usize, max_po: u32) -> ResidualPlan {
3510    // The deepest order that divides the block and leaves the first
3511    // partition at least one residual.
3512    let mut po = max_po.min(block_size.trailing_zeros());
3513    while po > 0 && (block_size >> po) <= order {
3514        po -= 1;
3515    }
3516
3517    let mut partitions = 1usize << po;
3518    let part_len = block_size >> po;
3519    let mut counts = vec![0u64; partitions];
3520    // sums[j][p] is the sum of `value >> p` over partition j. Entries past
3521    // RICE5_MAX are never read: a value needing a larger parameter simply
3522    // contributes its full shifted magnitude at RICE5_MAX.
3523    let mut sums = vec![[0u64; (RICE5_MAX + 1) as usize]; partitions];
3524    for (index, &value) in folded.iter().enumerate() {
3525        let j = (order + index) / part_len;
3526        counts[j] += 1;
3527        let mut shifted = value;
3528        let mut p = 0usize;
3529        while shifted > 0 && p <= RICE5_MAX as usize {
3530            sums[j][p] += shifted;
3531            shifted >>= 1;
3532            p += 1;
3533        }
3534    }
3535
3536    let mut best: Option<ResidualPlan> = None;
3537    loop {
3538        let mut total4 = 2u64 + 4;
3539        let mut total5 = 2u64 + 4;
3540        let mut params4 = Vec::with_capacity(partitions);
3541        let mut params5 = Vec::with_capacity(partitions);
3542        for j in 0..partitions {
3543            let mut best4 = u64::MAX;
3544            let mut best4_p = 0u32;
3545            let mut best5 = u64::MAX;
3546            let mut best5_p = 0u32;
3547            for p in 0..=RICE5_MAX {
3548                let cost = counts[j] * u64::from(p + 1) + sums[j][p as usize];
3549                if p <= RICE4_MAX && cost < best4 {
3550                    best4 = cost;
3551                    best4_p = p;
3552                }
3553                if cost < best5 {
3554                    best5 = cost;
3555                    best5_p = p;
3556                }
3557            }
3558            total4 = total4.saturating_add(4 + best4);
3559            total5 = total5.saturating_add(5 + best5);
3560            params4.push(best4_p);
3561            params5.push(best5_p);
3562        }
3563        let (total, five_bit, params) = if total4 <= total5 {
3564            (total4, false, params4)
3565        } else {
3566            (total5, true, params5)
3567        };
3568        if best.as_ref().is_none_or(|held| total < held.bits) {
3569            best = Some(ResidualPlan {
3570                bits: total,
3571                partition_order: po,
3572                five_bit,
3573                parameters: params,
3574            });
3575        }
3576
3577        if po == 0 {
3578            break;
3579        }
3580        // A partition at the next order up is the union of an adjacent pair
3581        // at this one, so counts and sums merge pairwise; nothing is
3582        // rescanned.
3583        po -= 1;
3584        partitions /= 2;
3585        for j in 0..partitions {
3586            counts[j] = counts[2 * j] + counts[2 * j + 1];
3587            let left = sums[2 * j];
3588            let right = sums[2 * j + 1];
3589            for (slot, (a, b)) in sums[j].iter_mut().zip(left.iter().zip(right.iter())) {
3590                *slot = a + b;
3591            }
3592        }
3593        counts.truncate(partitions);
3594        sums.truncate(partitions);
3595    }
3596    best.expect("the partition order zero pass always produces a plan")
3597}
3598
3599/// Writes a planned residual: the coding method, the partition order, and
3600/// each partition's parameter and Rice-coded values.
3601fn write_residual(
3602    writer: &mut BitWriter,
3603    residual: &[i64],
3604    block_size: usize,
3605    order: usize,
3606    plan: &ResidualPlan,
3607) {
3608    writer.write(u64::from(plan.five_bit), 2);
3609    writer.write(u64::from(plan.partition_order), 4);
3610    let parameter_bits = if plan.five_bit { 5 } else { 4 };
3611    let part_len = block_size >> plan.partition_order;
3612    let mut at = 0usize;
3613    for (index, &parameter) in plan.parameters.iter().enumerate() {
3614        writer.write(u64::from(parameter), parameter_bits);
3615        let count = if index == 0 {
3616            part_len - order
3617        } else {
3618            part_len
3619        };
3620        for &value in &residual[at..at + count] {
3621            let folded = zigzag(value);
3622            writer.write_unary(folded >> parameter);
3623            if parameter > 0 {
3624                writer.write(folded & ((1u64 << parameter) - 1), parameter);
3625            }
3626        }
3627        at += count;
3628    }
3629}
3630
3631// -- The predictor search -----------------------------------------------------
3632
3633/// The subframe form the search settled on, with everything needed to write
3634/// it.
3635enum SubframeKind {
3636    /// Every sample is this value.
3637    Constant(i64),
3638    /// The samples stored raw.
3639    Verbatim,
3640    /// A fixed predictor and its residual.
3641    Fixed {
3642        order: usize,
3643        residual: Vec<i64>,
3644        partitions: ResidualPlan,
3645    },
3646    /// A quantised linear predictor and its residual.
3647    Lpc {
3648        order: usize,
3649        shift: u32,
3650        /// Exactly `order` coefficients, in bitstream order.
3651        coefficients: Vec<i64>,
3652        residual: Vec<i64>,
3653        partitions: ResidualPlan,
3654    },
3655}
3656
3657/// One subframe as the search decided to write it.
3658struct SubframePlan {
3659    kind: SubframeKind,
3660    /// Wasted bits declared and shifted out of every sample.
3661    wasted: u32,
3662    /// The subframe's bit depth before wasted removal, including the side
3663    /// channel's extra bit where this subframe carries the side.
3664    depth: u32,
3665    /// The samples shifted right by `wasted`, which is what warm-up and
3666    /// verbatim samples are written from.
3667    shifted: Vec<i64>,
3668    /// The exact size of the written subframe in bits, which is what the
3669    /// stereo search compares.
3670    cost: u64,
3671}
3672
3673/// The subframe header's cost: the pad bit, the type, and the wasted-bits
3674/// field.
3675fn subframe_header_bits(wasted: u32) -> u64 {
3676    8 + if wasted > 0 { u64::from(wasted) } else { 0 }
3677}
3678
3679/// Levinson-Durbin over the autocorrelation, producing the predictor at
3680/// every order up to `max_order` and the modelling error at each.
3681///
3682/// Returns how many orders were produced; numerical degeneracy (an error
3683/// that reaches zero, which perfectly predictable input causes) stops the
3684/// recursion early and the orders before it remain usable.
3685fn levinson(
3686    autocorrelation: &[f64],
3687    max_order: usize,
3688    coefficients: &mut [[f64; MAX_LPC_ORDER]; MAX_LPC_ORDER],
3689    errors: &mut [f64; MAX_LPC_ORDER],
3690) -> usize {
3691    let mut error = autocorrelation[0];
3692    let mut lpc = [0f64; MAX_LPC_ORDER];
3693    for m in 0..max_order {
3694        if error <= 0.0 || !error.is_finite() {
3695            return m;
3696        }
3697        let mut acc = autocorrelation[m + 1];
3698        for j in 0..m {
3699            acc -= lpc[j] * autocorrelation[m - j];
3700        }
3701        let reflection = acc / error;
3702        lpc[m] = reflection;
3703        for j in 0..m / 2 {
3704            let held = lpc[j];
3705            lpc[j] = held - reflection * lpc[m - 1 - j];
3706            lpc[m - 1 - j] -= reflection * held;
3707        }
3708        if m % 2 == 1 {
3709            let mid = m / 2;
3710            lpc[mid] -= reflection * lpc[mid];
3711        }
3712        error *= 1.0 - reflection * reflection;
3713        coefficients[m][..=m].copy_from_slice(&lpc[..=m]);
3714        errors[m] = error;
3715    }
3716    max_order
3717}
3718
3719/// Quantises floating-point predictor coefficients to integers and a right
3720/// shift, with error feedback so rounding error accumulates into later
3721/// coefficients instead of into the prediction.
3722///
3723/// The shift puts the largest coefficient against the precision's ceiling,
3724/// clamped to the 0 through 15 range the format's shift field carries.
3725/// `None` when the coefficients are degenerate: all zero, or not finite,
3726/// neither of which can predict anything.
3727fn quantise_lpc(coefficients: &[f64], precision: u32) -> Option<(Vec<i64>, u32)> {
3728    let mut largest = 0f64;
3729    for &coefficient in coefficients {
3730        let magnitude = coefficient.abs();
3731        if !magnitude.is_finite() {
3732            return None;
3733        }
3734        if magnitude > largest {
3735            largest = magnitude;
3736        }
3737    }
3738    if largest <= 0.0 {
3739        return None;
3740    }
3741    // floor(log2(largest)) from the exponent field. A subnormal reads as
3742    // -1023, which only drives the shift into its upper clamp.
3743    let exponent = ((largest.to_bits() >> 52) & 0x7FF) as i64 - 1023;
3744    let shift = (i64::from(precision) - 2 - exponent).clamp(0, 15) as u32;
3745    let scale = (1u64 << shift) as f64;
3746    let ceiling = (1i64 << (precision - 1)) - 1;
3747    let floor = -(1i64 << (precision - 1));
3748
3749    let mut quantised = Vec::with_capacity(coefficients.len());
3750    let mut error = 0f64;
3751    let mut any_nonzero = false;
3752    for &coefficient in coefficients {
3753        let target = coefficient * scale + error;
3754        let rounded = ((target + 0.5).floor() as i64).clamp(floor, ceiling);
3755        error = target - rounded as f64;
3756        quantised.push(rounded);
3757        if rounded != 0 {
3758            any_nonzero = true;
3759        }
3760    }
3761    if !any_nonzero {
3762        return None;
3763    }
3764    Some((quantised, shift))
3765}
3766
3767/// The autocorrelation of the windowed samples at lags 0 through `max_lag`.
3768fn autocorrelation(windowed: &[f64], max_lag: usize, out: &mut [f64]) {
3769    for (lag, slot) in out.iter_mut().enumerate().take(max_lag + 1) {
3770        *slot = windowed[lag..]
3771            .iter()
3772            .zip(windowed.iter())
3773            .map(|(&late, &early)| late * early)
3774            .sum();
3775    }
3776}
3777
3778/// Searches every subframe form the level allows for `samples` at `depth`
3779/// bits and returns the cheapest, exactly costed.
3780fn plan_subframe(samples: &[i64], depth: u32, level: &Level, windows: &[Vec<f64>]) -> SubframePlan {
3781    let n = samples.len();
3782    debug_assert!(n > 0);
3783
3784    // Constant wins outright on constant input: no other form can beat
3785    // header plus one sample.
3786    if samples.iter().all(|&sample| sample == samples[0]) {
3787        return SubframePlan {
3788            kind: SubframeKind::Constant(samples[0]),
3789            wasted: 0,
3790            depth,
3791            shifted: Vec::new(),
3792            cost: 8 + u64::from(depth),
3793        };
3794    }
3795
3796    // Wasted bits: low zero bits shared by every sample come off before any
3797    // prediction, shrinking warm-up samples, verbatim samples and residuals
3798    // alike. All-zero input cannot reach here, so some sample bounds the
3799    // count below `depth`.
3800    let mut wasted = depth - 1;
3801    for &sample in samples {
3802        if sample != 0 {
3803            wasted = wasted.min(sample.trailing_zeros());
3804            if wasted == 0 {
3805                break;
3806            }
3807        }
3808    }
3809    let coded_bits = depth - wasted;
3810    let shifted: Vec<i64> = if wasted == 0 {
3811        samples.to_vec()
3812    } else {
3813        samples.iter().map(|&sample| sample >> wasted).collect()
3814    };
3815    let header = subframe_header_bits(wasted);
3816
3817    // Verbatim is the floor every other candidate must beat, and the
3818    // fallback that keeps a conforming frame writable whatever the input.
3819    let mut best_kind = SubframeKind::Verbatim;
3820    let mut best_cost = header + n as u64 * u64::from(coded_bits);
3821
3822    // Fixed predictors: rank the five orders by the standard sum-of-absolute
3823    // residuals estimate over successive differences, then exactly cost the
3824    // best two. The differencing identity makes each order's residual one
3825    // subtraction pass over the previous order's.
3826    let max_fixed = 4.min(n - 1);
3827    let mut difference = shifted.clone();
3828    let mut order_sums = [u64::MAX; 5];
3829    order_sums[0] = shifted
3830        .iter()
3831        .fold(0u64, |acc, &v| acc.saturating_add(v.unsigned_abs()));
3832    for order in 1..=max_fixed {
3833        for index in (order..n).rev() {
3834            difference[index] = difference[index].wrapping_sub(difference[index - 1]);
3835        }
3836        order_sums[order] = difference[order..]
3837            .iter()
3838            .fold(0u64, |acc, &v| acc.saturating_add(v.unsigned_abs()));
3839    }
3840    let mut ranked: Vec<usize> = (0..=max_fixed).collect();
3841    ranked.sort_by_key(|&order| (order_sums[order], order));
3842    for &order in ranked.iter().take(2) {
3843        let residual: Vec<i64> = (order..n)
3844            .map(|index| shifted[index].wrapping_sub(fixed_prediction(&shifted[..index], order)))
3845            .collect();
3846        if !residual_in_range(&residual) {
3847            continue;
3848        }
3849        let folded: Vec<u64> = residual.iter().map(|&value| zigzag(value)).collect();
3850        let partitions = plan_residual(&folded, n, order, level.max_partition_order);
3851        let cost = header + order as u64 * u64::from(coded_bits) + partitions.bits;
3852        if cost < best_cost {
3853            best_cost = cost;
3854            best_kind = SubframeKind::Fixed {
3855                order,
3856                residual,
3857                partitions,
3858            };
3859        }
3860    }
3861
3862    // Linear prediction: autocorrelate under each window, run
3863    // Levinson-Durbin to every order, estimate each order's size from its
3864    // modelling error, and exactly cost only the most promising few.
3865    let max_lpc = level.max_lpc_order.min(n - 1);
3866    if max_lpc >= 1 {
3867        for window in windows {
3868            let windowed: Vec<f64> = shifted
3869                .iter()
3870                .zip(window.iter())
3871                .map(|(&sample, &weight)| sample as f64 * weight)
3872                .collect();
3873            let mut autoc = [0f64; MAX_LPC_ORDER + 1];
3874            autocorrelation(&windowed, max_lpc, &mut autoc);
3875            if autoc[0] <= 0.0 {
3876                continue;
3877            }
3878            let mut coefficients = [[0f64; MAX_LPC_ORDER]; MAX_LPC_ORDER];
3879            let mut errors = [0f64; MAX_LPC_ORDER];
3880            let available = levinson(&autoc, max_lpc, &mut coefficients, &mut errors);
3881
3882            let mut estimates: Vec<(f64, usize)> = (1..=available)
3883                .map(|order| {
3884                    let variance = (errors[order - 1] / n as f64).max(1e-12);
3885                    let per_residual = (0.5 * det_log2(variance) + 1.6).max(0.0);
3886                    let estimate = (n - order) as f64 * per_residual
3887                        + (order as u64 * u64::from(coded_bits + COEFFICIENT_PRECISION)) as f64;
3888                    (estimate, order)
3889                })
3890                .collect();
3891            estimates.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.cmp(&b.1)));
3892
3893            for &(_, order) in estimates.iter().take(level.lpc_candidates) {
3894                let Some((quantised, shift)) =
3895                    quantise_lpc(&coefficients[order - 1][..order], COEFFICIENT_PRECISION)
3896                else {
3897                    continue;
3898                };
3899                let residual: Vec<i64> = (order..n)
3900                    .map(|index| {
3901                        shifted[index].wrapping_sub(lpc_prediction(
3902                            &quantised,
3903                            &shifted[..index],
3904                            shift,
3905                        ))
3906                    })
3907                    .collect();
3908                if !residual_in_range(&residual) {
3909                    continue;
3910                }
3911                let folded: Vec<u64> = residual.iter().map(|&value| zigzag(value)).collect();
3912                let partitions = plan_residual(&folded, n, order, level.max_partition_order);
3913                let cost = header
3914                    + order as u64 * u64::from(coded_bits)
3915                    + 4
3916                    + 5
3917                    + order as u64 * u64::from(COEFFICIENT_PRECISION)
3918                    + partitions.bits;
3919                if cost < best_cost {
3920                    best_cost = cost;
3921                    best_kind = SubframeKind::Lpc {
3922                        order,
3923                        shift,
3924                        coefficients: quantised,
3925                        residual,
3926                        partitions,
3927                    };
3928                }
3929            }
3930        }
3931    }
3932
3933    SubframePlan {
3934        kind: best_kind,
3935        wasted,
3936        depth,
3937        shifted,
3938        cost: best_cost,
3939    }
3940}
3941
3942// -- The stereo search --------------------------------------------------------
3943
3944/// A cheap size estimate for one candidate channel: the mean absolute
3945/// second difference converted through the Rice relation that the optimal
3946/// parameter is about the log of the mean.
3947///
3948/// Only the ranking matters, and every mode's estimate shares the same
3949/// biases, so the shared constants cancel.
3950fn stereo_estimate(samples: &[i64]) -> f64 {
3951    let n = samples.len();
3952    if n < 3 {
3953        return n as f64 * 8.0;
3954    }
3955    let mut sum = 0u64;
3956    for window in samples.windows(3) {
3957        let second = window[2]
3958            .wrapping_sub(window[1].wrapping_mul(2))
3959            .wrapping_add(window[0]);
3960        sum = sum.saturating_add(second.unsigned_abs());
3961    }
3962    let mean = sum as f64 / (n - 2) as f64;
3963    n as f64 * (det_log2(mean + 1.0) + 2.0)
3964}
3965
3966/// Chooses the frame's channel assignment and plans its two subframes.
3967///
3968/// The side channel is one bit deeper than the frame, which is why `side`
3969/// plans at `bits + 1`; a mid sample halves back into range and stays at
3970/// `bits`.
3971fn plan_stereo(
3972    left: &[i64],
3973    right: &[i64],
3974    bits: u32,
3975    level: &Level,
3976    windows: &[Vec<f64>],
3977) -> (u8, Vec<SubframePlan>) {
3978    let mid: Vec<i64> = left
3979        .iter()
3980        .zip(right.iter())
3981        .map(|(&l, &r)| (l + r) >> 1)
3982        .collect();
3983    let side: Vec<i64> = left
3984        .iter()
3985        .zip(right.iter())
3986        .map(|(&l, &r)| l - r)
3987        .collect();
3988
3989    match level.stereo {
3990        Stereo::Independent => (
3991            1,
3992            vec![
3993                plan_subframe(left, bits, level, windows),
3994                plan_subframe(right, bits, level, windows),
3995            ],
3996        ),
3997        Stereo::Estimated => {
3998            let estimate_left = stereo_estimate(left);
3999            let estimate_right = stereo_estimate(right);
4000            let estimate_mid = stereo_estimate(&mid);
4001            let estimate_side = stereo_estimate(&side);
4002            let modes = [
4003                (estimate_left + estimate_right, 1u8),
4004                (estimate_left + estimate_side, 8),
4005                (estimate_side + estimate_right, 9),
4006                (estimate_mid + estimate_side, 10),
4007            ];
4008            let mut chosen = modes[0];
4009            for &mode in &modes[1..] {
4010                if mode.0.total_cmp(&chosen.0).is_lt() {
4011                    chosen = mode;
4012                }
4013            }
4014            let plans = match chosen.1 {
4015                1 => vec![
4016                    plan_subframe(left, bits, level, windows),
4017                    plan_subframe(right, bits, level, windows),
4018                ],
4019                8 => vec![
4020                    plan_subframe(left, bits, level, windows),
4021                    plan_subframe(&side, bits + 1, level, windows),
4022                ],
4023                9 => vec![
4024                    plan_subframe(&side, bits + 1, level, windows),
4025                    plan_subframe(right, bits, level, windows),
4026                ],
4027                _ => vec![
4028                    plan_subframe(&mid, bits, level, windows),
4029                    plan_subframe(&side, bits + 1, level, windows),
4030                ],
4031            };
4032            (chosen.1, plans)
4033        }
4034        Stereo::Exhaustive => {
4035            let plan_left = plan_subframe(left, bits, level, windows);
4036            let plan_right = plan_subframe(right, bits, level, windows);
4037            let plan_mid = plan_subframe(&mid, bits, level, windows);
4038            let plan_side = plan_subframe(&side, bits + 1, level, windows);
4039            let costs = [
4040                (plan_left.cost + plan_right.cost, 1u8),
4041                (plan_left.cost + plan_side.cost, 8),
4042                (plan_side.cost + plan_right.cost, 9),
4043                (plan_mid.cost + plan_side.cost, 10),
4044            ];
4045            let mut chosen = costs[0];
4046            for &mode in &costs[1..] {
4047                if mode.0 < chosen.0 {
4048                    chosen = mode;
4049                }
4050            }
4051            match chosen.1 {
4052                1 => (1, vec![plan_left, plan_right]),
4053                8 => (8, vec![plan_left, plan_side]),
4054                9 => (9, vec![plan_side, plan_right]),
4055                _ => (10, vec![plan_mid, plan_side]),
4056            }
4057        }
4058    }
4059}
4060
4061// -- Frame assembly -----------------------------------------------------------
4062
4063/// The frame header's block size field: a common table code, or the
4064/// explicit 8- or 16-bit form with its stored value.
4065fn block_size_code(count: usize) -> (u64, Option<(u64, u32)>) {
4066    match count {
4067        192 => (1, None),
4068        576 => (2, None),
4069        1152 => (3, None),
4070        2304 => (4, None),
4071        4608 => (5, None),
4072        256 => (8, None),
4073        512 => (9, None),
4074        1024 => (10, None),
4075        2048 => (11, None),
4076        4096 => (12, None),
4077        8192 => (13, None),
4078        16384 => (14, None),
4079        32768 => (15, None),
4080        _ if count <= 256 => (6, Some((count as u64 - 1, 8))),
4081        _ => (7, Some((count as u64 - 1, 16))),
4082    }
4083}
4084
4085/// The frame header's sample rate field, from the common table.
4086///
4087/// A rate outside the table defers to streaminfo with code zero rather than
4088/// using the uncommon stored forms: every stream this writer produces has a
4089/// streaminfo block, deferring is always representable, and it is never
4090/// larger than the stored forms it replaces.
4091fn sample_rate_code(rate: u32) -> u64 {
4092    match rate {
4093        88_200 => 1,
4094        176_400 => 2,
4095        192_000 => 3,
4096        8_000 => 4,
4097        16_000 => 5,
4098        22_050 => 6,
4099        24_000 => 7,
4100        32_000 => 8,
4101        44_100 => 9,
4102        48_000 => 10,
4103        96_000 => 11,
4104        _ => 0,
4105    }
4106}
4107
4108/// The frame header's bit depth field, from the common table, deferring to
4109/// streaminfo for the depths the table cannot express.
4110fn bit_depth_code(bits: u32) -> u64 {
4111    match bits {
4112        8 => 1,
4113        12 => 2,
4114        16 => 4,
4115        20 => 5,
4116        24 => 6,
4117        32 => 7,
4118        _ => 0,
4119    }
4120}
4121
4122/// Writes one subframe as its plan decided.
4123fn write_subframe(writer: &mut BitWriter, plan: &SubframePlan, block_size: usize) {
4124    writer.write(0, 1);
4125    let type_code = match &plan.kind {
4126        SubframeKind::Constant(_) => 0u64,
4127        SubframeKind::Verbatim => 1,
4128        SubframeKind::Fixed { order, .. } => 8 + *order as u64,
4129        SubframeKind::Lpc { order, .. } => 31 + *order as u64,
4130    };
4131    writer.write(type_code, 6);
4132    if plan.wasted == 0 {
4133        writer.write(0, 1);
4134    } else {
4135        writer.write(1, 1);
4136        // The count minus one in unary: wasted - 1 zeros, then the one.
4137        writer.write(1, plan.wasted);
4138    }
4139    let coded_bits = plan.depth - plan.wasted;
4140    match &plan.kind {
4141        SubframeKind::Constant(value) => writer.write_signed(*value, coded_bits),
4142        SubframeKind::Verbatim => {
4143            for &value in &plan.shifted {
4144                writer.write_signed(value, coded_bits);
4145            }
4146        }
4147        SubframeKind::Fixed {
4148            order,
4149            residual,
4150            partitions,
4151        } => {
4152            for &value in &plan.shifted[..*order] {
4153                writer.write_signed(value, coded_bits);
4154            }
4155            write_residual(writer, residual, block_size, *order, partitions);
4156        }
4157        SubframeKind::Lpc {
4158            order,
4159            shift,
4160            coefficients,
4161            residual,
4162            partitions,
4163        } => {
4164            for &value in &plan.shifted[..*order] {
4165                writer.write_signed(value, coded_bits);
4166            }
4167            writer.write(u64::from(COEFFICIENT_PRECISION - 1), 4);
4168            writer.write(u64::from(*shift), 5);
4169            for &coefficient in coefficients {
4170                writer.write_signed(coefficient, COEFFICIENT_PRECISION);
4171            }
4172            write_residual(writer, residual, block_size, *order, partitions);
4173        }
4174    }
4175}
4176
4177/// Writes one complete frame and returns how many bytes it occupied.
4178fn write_frame(
4179    out: &mut Vec<u8>,
4180    frame_index: u64,
4181    block_size: usize,
4182    sample_rate: u32,
4183    bits: u32,
4184    assignment: u8,
4185    plans: &[SubframePlan],
4186) -> usize {
4187    let mut writer = BitWriter::new();
4188    // The sync code and the fixed blocking strategy bit: every stream this
4189    // writer produces is fixed-blocksize, so the coded number is a frame
4190    // number.
4191    writer.write(0b111_1111_1111_1100, 15);
4192    writer.write(0, 1);
4193    let (size_code, size_tail) = block_size_code(block_size);
4194    writer.write(size_code, 4);
4195    writer.write(sample_rate_code(sample_rate), 4);
4196    writer.write(u64::from(assignment), 4);
4197    writer.write(bit_depth_code(bits), 3);
4198    writer.write(0, 1);
4199    write_coded_number(&mut writer, frame_index);
4200    if let Some((value, width)) = size_tail {
4201        writer.write(value, width);
4202    }
4203    let header_crc = crc8(writer.bytes());
4204    writer.write(u64::from(header_crc), 8);
4205
4206    for plan in plans {
4207        write_subframe(&mut writer, plan, block_size);
4208    }
4209    writer.align();
4210    let frame_crc = crc16(writer.bytes());
4211    writer.write(u64::from(frame_crc), 16);
4212
4213    let bytes = writer.into_bytes();
4214    out.extend_from_slice(&bytes);
4215    bytes.len()
4216}
4217
4218// -- The writer ---------------------------------------------------------------
4219
4220/// Writes native FLAC streams: a `fLaC` signature, one streaminfo block,
4221/// and Rice-coded audio frames.
4222///
4223/// The third writer in the crate, beside [`WavWriter`](crate::WavWriter) and
4224/// [`AiffWriter`](crate::AiffWriter) and shaped like both: construct with
4225/// the audio's description, then [`write`](Self::write) or
4226/// [`to_bytes`](Self::to_bytes). The difference FLAC brings is that writing
4227/// is a search rather than a transcription, so a [`level`](Self::with_level)
4228/// chooses how hard to look for a small file, 0 through 8 with 5 the
4229/// default, in broadly the reference encoder's sense of those numbers.
4230///
4231/// # What is written
4232///
4233/// Fixed-blocksize frames of every subframe type the decoder reads:
4234/// constant on runs the search finds constant, verbatim where prediction
4235/// cannot pay for itself, fixed predictors, and quantised linear predictors
4236/// found by windowed autocorrelation and Levinson-Durbin recursion. Stereo
4237/// frames choose per frame between independent, left/side, right/side and
4238/// mid/side coding. Wasted bits are detected and declared. The streaminfo
4239/// block states the true minimum and maximum block and frame sizes, the
4240/// total sample count, and the MD5 of the audio, which this crate's own
4241/// decoder and any other conforming decoder then verify. No other metadata
4242/// block is written: no padding, no seek table, no tags.
4243///
4244/// # The samples, and what lossless means here
4245///
4246/// Input is interleaved `f32`, quantised to `bits_per_sample`-bit integers
4247/// by the same rule every other writer in the crate uses, stated on
4248/// [`sample`](crate::sample): clamp to `-1.0..=1.0`, scale by
4249/// `2^(bits - 1)`, truncate toward zero, clamp in integer space. Encoding
4250/// is lossless over those integers, exactly; the quantisation is where
4251/// `f32` input meets an integer format, and it is the identical boundary
4252/// the decoder's scaling comes back across. At or below 24 bits the round
4253/// trip through [`FlacReader`] returns the input samples bit for bit.
4254///
4255/// # The arithmetic is the decoder's
4256///
4257/// Residuals are computed by subtracting the very prediction functions the
4258/// decoder adds, `fixed_prediction` and `lpc_prediction` in this module, at
4259/// the same widths in the same order. An encoder with its own arithmetic
4260/// could disagree with its decoder only on loud material at high depths,
4261/// which no small test catches; sharing the functions makes the
4262/// disagreement inexpressible.
4263///
4264/// # Determinism
4265///
4266/// The same samples at the same level produce the same bytes on every
4267/// platform. The search uses `f64` only through operations IEEE 754 defines
4268/// exactly, and the window cosine and estimation logarithm are computed
4269/// in-crate from arithmetic rather than taken from a libm that varies by
4270/// the last bit between targets.
4271///
4272/// # Example
4273///
4274/// ```
4275/// use decibri_decode::{AudioSpec, FlacReader, FlacWriter};
4276///
4277/// // A quiet ramp: every value scales to a whole 16-bit integer, so the
4278/// // round trip is exact.
4279/// let samples: Vec<f32> = (0..2000).map(|i| ((i % 128) as f32 - 64.0) / 128.0).collect();
4280/// let file = FlacWriter::new(AudioSpec::mono(44_100), 16).to_bytes(&samples)?;
4281///
4282/// let reader = FlacReader::new(&file)?;
4283/// assert_eq!(reader.frames(), Some(2000));
4284/// // decode_to_end verifies the streaminfo MD5 over what it decodes.
4285/// let decoded = reader.decode_to_end()?;
4286/// assert_eq!(decoded.samples(), &samples[..]);
4287/// # Ok::<(), decibri_decode::DecodeError>(())
4288/// ```
4289#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
4290pub struct FlacWriter {
4291    spec: AudioSpec,
4292    bits_per_sample: u8,
4293    level: u8,
4294}
4295
4296impl FlacWriter {
4297    /// A writer for audio at `spec`, quantised to `bits_per_sample` bits,
4298    /// at the default compression level 5.
4299    ///
4300    /// Any depth the format carries, 4 through 32, is accepted; depths the
4301    /// frame header cannot express directly are deferred to streaminfo,
4302    /// exactly as the decoder resolves them. Validation happens in
4303    /// [`write`](Self::write), where there is a `Result` to report it.
4304    pub const fn new(spec: AudioSpec, bits_per_sample: u8) -> Self {
4305        Self {
4306            spec,
4307            bits_per_sample,
4308            level: 5,
4309        }
4310    }
4311
4312    /// Sets the compression level, 0 through 8.
4313    ///
4314    /// Higher levels search more: larger predictor orders, deeper residual
4315    /// partitioning, more analysis windows and a fuller stereo search. The
4316    /// output of every level decodes identically; only the byte count and
4317    /// the encoding time differ. A level above 8 is rejected by
4318    /// [`write`](Self::write).
4319    pub const fn with_level(mut self, level: u8) -> Self {
4320        self.level = level;
4321        self
4322    }
4323
4324    /// The rate and layout written into streaminfo.
4325    pub const fn spec(&self) -> AudioSpec {
4326        self.spec
4327    }
4328
4329    /// The bit depth samples are quantised to.
4330    pub const fn bits_per_sample(&self) -> u8 {
4331        self.bits_per_sample
4332    }
4333
4334    /// The compression level [`write`](Self::write) will search at.
4335    pub const fn level(&self) -> u8 {
4336        self.level
4337    }
4338
4339    /// Appends a complete FLAC stream to `output`, and returns how many
4340    /// bytes it appended.
4341    ///
4342    /// `output` is appended to, never cleared, the same convention as every
4343    /// other writer in this crate.
4344    ///
4345    /// # Errors
4346    ///
4347    /// - [`DecodeError::UnsupportedChannelLayout`] for no channels or more
4348    ///   than the eight a FLAC frame can carry.
4349    /// - [`DecodeError::UnsupportedSampleFormat`] for a bit depth outside
4350    ///   the 4 through 32 the format defines.
4351    /// - [`DecodeError::Malformed`] for a sample rate of zero or beyond
4352    ///   streaminfo's 20-bit field, and for a compression level above 8.
4353    /// - [`DecodeError::Truncated`] when `samples` does not divide into
4354    ///   whole frames, for the reason recorded on
4355    ///   [`WavWriter::write`](crate::WavWriter::write): a partial frame
4356    ///   written would be rejected by every reader, and one dropped would be
4357    ///   silent truncation.
4358    pub fn write(&self, samples: &[f32], output: &mut Vec<u8>) -> Result<usize, DecodeError> {
4359        let channels = usize::from(self.spec.channels);
4360        if channels == 0 || channels > usize::from(MAX_CHANNELS) {
4361            return Err(DecodeError::UnsupportedChannelLayout {
4362                channels: self.spec.channels,
4363            });
4364        }
4365        // Streaminfo's rate field is 20 bits, and zero is not a rate. The
4366        // offset is where the field sits in the file this writer refused to
4367        // produce.
4368        if self.spec.sample_rate == 0 || self.spec.sample_rate > 0xF_FFFF {
4369            return Err(DecodeError::Malformed {
4370                expected: "a sample rate between 1 and 1048575, the range streaminfo carries",
4371                offset: 18,
4372            });
4373        }
4374        if !(4..=32).contains(&self.bits_per_sample) {
4375            return Err(DecodeError::UnsupportedSampleFormat {
4376                format: CodecId::Name("FLAC".to_string()),
4377                bits_per_sample: u16::from(self.bits_per_sample),
4378            });
4379        }
4380        if usize::from(self.level) >= LEVELS.len() {
4381            return Err(DecodeError::Malformed {
4382                expected: "a compression level between 0 and 8",
4383                offset: 0,
4384            });
4385        }
4386        let leftover = samples.len() % channels;
4387        if leftover != 0 {
4388            return Err(DecodeError::Truncated {
4389                expected: channels as u64,
4390                available: leftover as u64,
4391            });
4392        }
4393        let total_frames = (samples.len() / channels) as u64;
4394        if total_frames >= 1u64 << 36 {
4395            return Err(DecodeError::Malformed {
4396                expected: "no more sample frames than streaminfo's 36-bit total can declare",
4397                offset: 21,
4398            });
4399        }
4400
4401        let level = &LEVELS[usize::from(self.level)];
4402        let bits = u32::from(self.bits_per_sample);
4403        let block = level.block_size as usize;
4404        let scale = (1u64 << (bits - 1)) as f32;
4405        let floor = -(1i64 << (bits - 1));
4406        let ceiling = (1i64 << (bits - 1)) - 1;
4407        let width = usize::from(self.bits_per_sample).div_ceil(8);
4408
4409        let mut hasher = Md5::new();
4410        let mut body: Vec<u8> = Vec::new();
4411        let mut smallest_frame = u64::MAX;
4412        let mut largest_frame = 0u64;
4413        let mut channel_data: Vec<Vec<i64>> = vec![Vec::new(); channels];
4414        let mut hash_stage: Vec<u8> = Vec::new();
4415        let mut windows: Vec<Vec<f64>> = Vec::new();
4416        let mut window_len = 0usize;
4417
4418        let mut frame_index = 0u64;
4419        let mut done = 0usize;
4420        let total = total_frames as usize;
4421        while done < total {
4422            let count = block.min(total - done);
4423            for channel in &mut channel_data {
4424                channel.clear();
4425            }
4426            hash_stage.clear();
4427            let base = done * channels;
4428            for frame in 0..count {
4429                for (channel, data) in channel_data.iter_mut().enumerate() {
4430                    let value = quantize(
4431                        samples[base + frame * channels + channel],
4432                        scale,
4433                        floor,
4434                        ceiling,
4435                    );
4436                    data.push(value);
4437                    hash_stage.extend_from_slice(&value.to_le_bytes()[..width]);
4438                }
4439            }
4440            hasher.update(&hash_stage);
4441
4442            if level.max_lpc_order > 0 && (windows.is_empty() || window_len != count) {
4443                windows = level
4444                    .windows
4445                    .iter()
4446                    .map(|shape| shape.build(count))
4447                    .collect();
4448                window_len = count;
4449            }
4450
4451            let (assignment, plans) = if channels == 2 && level.stereo != Stereo::Independent {
4452                plan_stereo(&channel_data[0], &channel_data[1], bits, level, &windows)
4453            } else {
4454                (
4455                    (channels - 1) as u8,
4456                    channel_data
4457                        .iter()
4458                        .map(|channel| plan_subframe(channel, bits, level, &windows))
4459                        .collect(),
4460                )
4461            };
4462
4463            let frame_bytes = write_frame(
4464                &mut body,
4465                frame_index,
4466                count,
4467                self.spec.sample_rate,
4468                bits,
4469                assignment,
4470                &plans,
4471            ) as u64;
4472            smallest_frame = smallest_frame.min(frame_bytes);
4473            largest_frame = largest_frame.max(frame_bytes);
4474            frame_index += 1;
4475            done += count;
4476        }
4477
4478        let digest = hasher.finish();
4479        let start = output.len();
4480        output.extend_from_slice(MAGIC.as_bytes());
4481        // Streaminfo, the only metadata block, so its header carries the
4482        // last-block flag.
4483        output.push(0x80);
4484        output.extend_from_slice(&[0, 0, STREAMINFO_BYTES as u8]);
4485        let mut info = BitWriter::new();
4486        // Every frame but the last holds exactly the nominal block size, so
4487        // the nominal size is both the minimum and the maximum in RFC 9639
4488        // section 8.2's sense, which excludes the last block.
4489        info.write(u64::from(level.block_size), 16);
4490        info.write(u64::from(level.block_size), 16);
4491        let (min_frame, max_frame) = if frame_index == 0 {
4492            // No frames were written, so there are no frame sizes; zero is
4493            // the field's own spelling of unknown.
4494            (0, 0)
4495        } else {
4496            (smallest_frame, largest_frame)
4497        };
4498        info.write(min_frame, 24);
4499        info.write(max_frame, 24);
4500        info.write(u64::from(self.spec.sample_rate), 20);
4501        info.write(channels as u64 - 1, 3);
4502        info.write(u64::from(bits) - 1, 5);
4503        // An empty stream writes zero here, which the format reads as
4504        // unknown: the field has no way to distinguish the two, and this
4505        // writer does not pretend otherwise.
4506        info.write(total_frames, 36);
4507        output.extend_from_slice(&info.into_bytes());
4508        output.extend_from_slice(&digest);
4509        output.extend_from_slice(&body);
4510        Ok(output.len() - start)
4511    }
4512
4513    /// A complete FLAC stream as a new `Vec<u8>`.
4514    ///
4515    /// # Errors
4516    ///
4517    /// As [`write`](Self::write).
4518    pub fn to_bytes(&self, samples: &[f32]) -> Result<Vec<u8>, DecodeError> {
4519        let mut output = Vec::new();
4520        self.write(samples, &mut output)?;
4521        Ok(output)
4522    }
4523}
4524
4525#[cfg(test)]
4526mod tests {
4527    use super::*;
4528    use crate::sample::{i16_to_f32, i24_to_f32, i32_to_f32, i8_to_f32};
4529
4530    /// RFC 9639 appendix D.1's worked example: 16-bit stereo, one frame, one
4531    /// sample per channel, both subframes verbatim with wasted bits.
4532    const EXAMPLE_1: [u8; 45] = [
4533        0x66, 0x4c, 0x61, 0x43, 0x80, 0x00, 0x00, 0x22, 0x10, 0x00, 0x10, 0x00, 0x00, 0x00, 0x0f,
4534        0x00, 0x00, 0x0f, 0x0a, 0xc4, 0x42, 0xf0, 0x00, 0x00, 0x00, 0x01, 0x3e, 0x84, 0xb4, 0x18,
4535        0x07, 0xdc, 0x69, 0x03, 0x07, 0x58, 0x6a, 0x3d, 0xad, 0x1a, 0x2e, 0x0f, 0xff, 0xf8, 0x69,
4536    ];
4537
4538    /// The tail of example 1, which the array above cannot hold in one
4539    /// literal without becoming unreadable.
4540    const EXAMPLE_1_TAIL: [u8; 8] = [0x18, 0x00, 0x00, 0xbf, 0x03, 0x58, 0xfd, 0x03];
4541
4542    /// The frame footer of example 1.
4543    const EXAMPLE_1_CRC: [u8; 4] = [0x12, 0x8b, 0xaa, 0x9a];
4544
4545    /// Example 1 assembled.
4546    fn example_1() -> Vec<u8> {
4547        let mut file = EXAMPLE_1.to_vec();
4548        file.extend_from_slice(&EXAMPLE_1_TAIL);
4549        file.extend_from_slice(&EXAMPLE_1_CRC);
4550        file
4551    }
4552
4553    /// The CRC-8 the format specifies, against values that can be worked out
4554    /// by hand and against the one example 1 carries.
4555    ///
4556    /// `0x01` through the polynomial `x^8 + x^2 + x^1 + x^0` is seven left
4557    /// shifts to `0x80` and one more that reduces to the polynomial's low
4558    /// byte, `0x07`.
4559    #[test]
4560    fn crc8_matches_the_specification() {
4561        assert_eq!(crc8(&[0x00]), 0x00);
4562        assert_eq!(crc8(&[0x01]), 0x07);
4563        // Example 1's six-byte frame header at 0x2a, whose stored CRC-8 sits
4564        // at 0x30. The header ends where the CRC begins, sync code included.
4565        let file = example_1();
4566        assert_eq!(crc8(&file[0x2a..0x30]), file[0x30]);
4567    }
4568
4569    /// The CRC-16 the format specifies, likewise.
4570    ///
4571    /// `0x01` through `x^16 + x^15 + x^2 + x^0` reduces to `0x8005`, and
4572    /// example 1's whole frame, sync code included and the CRC itself
4573    /// excluded, hashes to the two bytes the file ends with.
4574    #[test]
4575    fn crc16_matches_the_specification() {
4576        assert_eq!(crc16(&[0x00]), 0x0000);
4577        assert_eq!(crc16(&[0x01]), 0x8005);
4578        let file = example_1();
4579        assert_eq!(
4580            crc16(&file[0x2a..0x37]),
4581            u16::from_be_bytes([file[0x37], file[0x38]])
4582        );
4583    }
4584
4585    #[test]
4586    fn the_coded_number_is_not_utf8() {
4587        // RFC 9639 section 9.1.5's own worked example: 51 billion, in seven
4588        // octets, which no UTF-8 decoder will read.
4589        let bytes = [0xFE, 0xAF, 0x9F, 0xB5, 0xA3, 0xB8, 0x80];
4590        let mut reader = BitReader::new(&bytes, 0);
4591        assert_eq!(
4592            read_coded_number(&mut reader).expect("read"),
4593            51_000_000_000
4594        );
4595
4596        // A single octet is itself.
4597        let mut reader = BitReader::new(&[0x7F], 0);
4598        assert_eq!(read_coded_number(&mut reader).expect("read"), 127);
4599
4600        // A continuation octet cannot start a code, and neither can 0xFF.
4601        for first in [0x80u8, 0xFF] {
4602            let bytes = [first, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80];
4603            let mut reader = BitReader::new(&bytes, 0);
4604            assert!(read_coded_number(&mut reader).is_err());
4605        }
4606    }
4607
4608    #[test]
4609    fn the_bit_reader_reads_across_byte_boundaries() {
4610        let bytes = [0b1010_1100, 0b1111_0000, 0b0000_1111];
4611        let mut reader = BitReader::new(&bytes, 0);
4612        assert_eq!(reader.read_bits(3).expect("read"), 0b101);
4613        assert_eq!(reader.read_bits(7).expect("read"), 0b011_0011);
4614        assert_eq!(reader.read_bits(14).expect("read"), 0b11_0000_0000_1111);
4615        assert!(reader.read_bits(1).is_err());
4616    }
4617
4618    #[test]
4619    fn the_bit_reader_sign_extends() {
4620        // 0b111 in three bits is -1, 0b011 is 3, and 0b100 in the last three
4621        // is -4: the same bits mean different values at different widths.
4622        let bytes = [0b1110_1110, 0b0000_0000];
4623        let mut reader = BitReader::new(&bytes, 0);
4624        assert_eq!(reader.read_signed(3).expect("read"), -1);
4625        assert_eq!(reader.read_signed(3).expect("read"), 3);
4626        assert_eq!(reader.read_signed(3).expect("read"), -4);
4627        // Unsigned, the same three bits are 4 rather than -4.
4628        let mut reader = BitReader::new(&bytes, 0);
4629        reader.bit = 6;
4630        assert_eq!(reader.read_bits(3).expect("read"), 4);
4631    }
4632
4633    #[test]
4634    fn unary_counts_zeros_and_eats_the_one() {
4635        let bytes = [0b0000_0100, 0b1000_0000];
4636        let mut reader = BitReader::new(&bytes, 0);
4637        assert_eq!(reader.read_unary().expect("read"), 5);
4638        assert_eq!(reader.read_unary().expect("read"), 2);
4639        // A run that never terminates inside the input is truncation, not a
4640        // hang.
4641        let mut reader = BitReader::new(&[0u8; 32], 0);
4642        assert!(reader.read_unary().is_err());
4643    }
4644
4645    #[test]
4646    fn a_long_unary_run_terminates() {
4647        // Sixteen zero bytes then a set bit: past the 57-bit window, so this
4648        // exercises the loop rather than the single-window fast path.
4649        let mut bytes = vec![0u8; 16];
4650        bytes.push(0x80);
4651        let mut reader = BitReader::new(&bytes, 0);
4652        assert_eq!(reader.read_unary().expect("read"), 128);
4653    }
4654
4655    /// The FLAC scaling rule and `sample.rs`'s must agree at every width the
4656    /// two share, because the same audio decoded through this container and
4657    /// through WAV has to give the same `f32`.
4658    ///
4659    /// This is the tie required by the crate's third coverage lesson: one
4660    /// rule with two implementations means a control on either one says
4661    /// nothing about the other. Breaking either divisor turns this red.
4662    #[test]
4663    fn flac_scaling_agrees_with_sample_rs() {
4664        fn flac_scale(sample: i64, bits: u8) -> f32 {
4665            sample as f32 / (1u64 << (bits - 1)) as f32
4666        }
4667
4668        for value in i16::MIN..=i16::MAX {
4669            assert_eq!(flac_scale(i64::from(value), 16), i16_to_f32(value));
4670        }
4671        for value in i8::MIN..=i8::MAX {
4672            assert_eq!(flac_scale(i64::from(value), 8), i8_to_f32(value));
4673        }
4674        for value in [
4675            crate::sample::I24_MIN,
4676            -1,
4677            0,
4678            1,
4679            crate::sample::I24_MAX,
4680            123_456,
4681        ] {
4682            assert_eq!(flac_scale(i64::from(value), 24), i24_to_f32(value));
4683        }
4684        for value in [i32::MIN, -1, 0, 1, i32::MAX, 1_234_567_890] {
4685            assert_eq!(flac_scale(i64::from(value), 32), i32_to_f32(value));
4686        }
4687    }
4688
4689    #[test]
4690    fn mid_side_reconstruction_is_lossless_over_a_swept_domain() {
4691        // The odd-sample correction is what makes this true. Sweeping both
4692        // channels over a range that straddles zero catches a sign error in
4693        // the arithmetic shift as well as a dropped correction.
4694        for left in -300i64..=300 {
4695            for right in -300i64..=300 {
4696                let mid = (left + right) >> 1;
4697                let side = left - right;
4698                let mut a = [mid];
4699                let mut b = [side];
4700                undo_decorrelation(ChannelAssignment::MidSide, &mut a, &mut b);
4701                assert_eq!((a[0], b[0]), (left, right), "mid/side lost {left},{right}");
4702            }
4703        }
4704    }
4705
4706    #[test]
4707    fn left_side_and_side_right_reconstruction_round_trip() {
4708        for left in [-32_768i64, -1, 0, 1, 32_767] {
4709            for right in [-32_768i64, -1, 0, 1, 32_767] {
4710                let side = left - right;
4711
4712                let mut a = [left];
4713                let mut b = [side];
4714                undo_decorrelation(ChannelAssignment::LeftSide, &mut a, &mut b);
4715                assert_eq!((a[0], b[0]), (left, right));
4716
4717                let mut a = [side];
4718                let mut b = [right];
4719                undo_decorrelation(ChannelAssignment::SideRight, &mut a, &mut b);
4720                assert_eq!((a[0], b[0]), (left, right));
4721            }
4722        }
4723    }
4724
4725    #[test]
4726    fn the_worked_example_decodes_exactly() {
4727        let file = example_1();
4728        let reader = FlacReader::new(&file).expect("open");
4729        assert_eq!(reader.spec(), AudioSpec::new(44_100, 2));
4730        assert_eq!(reader.stream_info().bits_per_sample, 16);
4731        assert_eq!(reader.frames(), Some(1));
4732
4733        let decoded = reader.decode_to_end().expect("decode");
4734        // RFC 9639 appendix D.1.4's own numbers, both of which come out of
4735        // wasted-bits subframes: 25588 and 10416.
4736        assert_eq!(
4737            decoded.samples(),
4738            [25_588.0 / 32_768.0, 10_416.0 / 32_768.0]
4739        );
4740    }
4741
4742    #[test]
4743    fn a_wrong_magic_is_named_rather_than_categorised() {
4744        let error = FlacReader::new(b"RIFFxxxxWAVE").expect_err("must reject");
4745        assert!(
4746            matches!(error, DecodeError::UnsupportedContainer { tag } if tag.as_bytes() == b"RIFF"),
4747            "unexpected error: {error}"
4748        );
4749    }
4750
4751    #[test]
4752    fn the_streaming_path_matches_the_whole_file_path() {
4753        let file = example_1();
4754        let whole = FlacReader::new(&file)
4755            .expect("open")
4756            .decode_to_end()
4757            .expect("decode");
4758
4759        for chunk in [1, 2, 3, 7, 16, 64, 4096] {
4760            let mut stream = FlacStreamDecoder::new();
4761            let mut samples = Vec::new();
4762            for piece in file.chunks(chunk) {
4763                let mut offset = 0;
4764                while offset < piece.len() {
4765                    offset += stream.push(&piece[offset..]).expect("push");
4766                    while stream.pull(&mut samples, usize::MAX).expect("pull") > 0 {}
4767                }
4768            }
4769            stream.finish(&mut samples).expect("finish");
4770            assert_eq!(
4771                samples,
4772                whole.samples(),
4773                "output changed with a {chunk}-byte feed size"
4774            );
4775        }
4776    }
4777
4778    #[test]
4779    fn an_all_zero_md5_is_unset_rather_than_a_failure() {
4780        let mut file = example_1();
4781        // The checksum field sits at 0x1a, eighteen bytes into the 34-byte
4782        // streaminfo body which starts at 8.
4783        file[26..42].fill(0);
4784        let reader = FlacReader::new(&file).expect("open");
4785        assert_eq!(reader.stream_info().md5, None);
4786        assert!(reader.decode_to_end().is_ok());
4787    }
4788
4789    #[test]
4790    fn a_wrong_md5_is_a_typed_error_rather_than_audio() {
4791        let mut file = example_1();
4792        file[26] ^= 0xFF;
4793        let error = FlacReader::new(&file)
4794            .expect("open")
4795            .decode_to_end()
4796            .expect_err("must reject");
4797        assert!(
4798            matches!(
4799                error,
4800                DecodeError::Malformed {
4801                    expected: "decoded audio matching the streaminfo MD5 checksum",
4802                    ..
4803                }
4804            ),
4805            "unexpected error: {error}"
4806        );
4807    }
4808
4809    // -- The writer's search machinery ----------------------------------------
4810
4811    /// A deterministic value stream for the searches' unit tests.
4812    fn splitmix(state: &mut u64) -> u64 {
4813        *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
4814        let mut z = *state;
4815        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
4816        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
4817        z ^ (z >> 31)
4818    }
4819
4820    /// The exact bit cost of one partition at one parameter, counted the
4821    /// slow way: value by value, quotient plus terminator plus parameter
4822    /// bits.
4823    fn brute_partition_cost(folded: &[u64], parameter: u32) -> u64 {
4824        folded
4825            .iter()
4826            .map(|&value| (value >> parameter) + 1 + u64::from(parameter))
4827            .sum()
4828    }
4829
4830    /// The partition search against exhaustive enumeration.
4831    ///
4832    /// The plan is built by accumulating shifted sums at the deepest order
4833    /// and merging pairwise; the oracle here recounts every (order, method,
4834    /// parameter) cell directly from the residuals, so a break in the
4835    /// accumulation, the merge or the minimum-taking cannot agree with it by
4836    /// construction. This is the in-tree gate for the Rice search, the one a
4837    /// negative control on the search must turn red.
4838    #[test]
4839    fn the_partition_search_matches_exhaustive_enumeration() {
4840        let mut state = 0x5EED_CAFE_u64;
4841        for (block_size, order, max_po) in
4842            [(64usize, 2usize, 3u32), (96, 0, 4), (256, 4, 8), (33, 1, 6)]
4843        {
4844            // A mix of small and occasionally large residuals, so both Rice
4845            // methods and several parameters are in play.
4846            let folded: Vec<u64> = (0..block_size - order)
4847                .map(|_| {
4848                    let raw = splitmix(&mut state);
4849                    if raw.is_multiple_of(13) {
4850                        raw >> 34
4851                    } else {
4852                        raw >> 56
4853                    }
4854                })
4855                .collect();
4856            let plan = plan_residual(&folded, block_size, order, max_po);
4857
4858            let mut expected = u64::MAX;
4859            let mut po = max_po.min(block_size.trailing_zeros());
4860            while block_size >> po <= order {
4861                po -= 1;
4862            }
4863            for po in (0..=po).rev() {
4864                if !block_size.is_multiple_of(1 << po) {
4865                    continue;
4866                }
4867                let part_len = block_size >> po;
4868                for (parameter_bits, max_parameter) in [(4u64, RICE4_MAX), (5, RICE5_MAX)] {
4869                    let mut total = 2 + 4;
4870                    let mut at = 0usize;
4871                    for partition in 0..1usize << po {
4872                        let count = if partition == 0 {
4873                            part_len - order
4874                        } else {
4875                            part_len
4876                        };
4877                        let best = (0..=max_parameter)
4878                            .map(|p| brute_partition_cost(&folded[at..at + count], p))
4879                            .min()
4880                            .expect("at least one parameter");
4881                        total += parameter_bits + best;
4882                        at += count;
4883                    }
4884                    expected = expected.min(total);
4885                }
4886            }
4887            assert_eq!(
4888                plan.bits, expected,
4889                "block {block_size} order {order} max_po {max_po}"
4890            );
4891
4892            // The written form must occupy exactly the bits the plan
4893            // claims, or the whole subframe search compared the wrong
4894            // things. Reconstruct the residuals from the folded values to
4895            // write them.
4896            let residual: Vec<i64> = folded
4897                .iter()
4898                .map(|&value| ((value >> 1) as i64) ^ -((value & 1) as i64))
4899                .collect();
4900            let mut writer = BitWriter::new();
4901            write_residual(&mut writer, &residual, block_size, order, &plan);
4902            let written_bits = writer.out.len() as u64 * 8 + u64::from(writer.filled);
4903            assert_eq!(written_bits, plan.bits, "written size vs planned size");
4904        }
4905    }
4906
4907    /// The bit writer against the bit reader, which is the pairing every
4908    /// encoded stream lives or dies by.
4909    #[test]
4910    fn the_bit_writer_mirrors_the_bit_reader() {
4911        let mut writer = BitWriter::new();
4912        writer.write(0b101, 3);
4913        writer.write_signed(-1, 7);
4914        writer.write(0x5A5A, 16);
4915        writer.write_signed(-12345, 33);
4916        writer.write_unary(0);
4917        writer.write_unary(5);
4918        writer.write_unary(100);
4919        writer.write(1, 1);
4920        let bytes = writer.into_bytes();
4921
4922        let mut reader = BitReader::new(&bytes, 0);
4923        assert_eq!(reader.read_bits(3).expect("read"), 0b101);
4924        assert_eq!(reader.read_signed(7).expect("read"), -1);
4925        assert_eq!(reader.read_bits(16).expect("read"), 0x5A5A);
4926        assert_eq!(reader.read_signed(33).expect("read"), -12345);
4927        assert_eq!(reader.read_unary().expect("read"), 0);
4928        assert_eq!(reader.read_unary().expect("read"), 5);
4929        assert_eq!(reader.read_unary().expect("read"), 100);
4930        assert_eq!(reader.read_bits(1).expect("read"), 1);
4931    }
4932
4933    /// The coded number writer against the coded number reader, at the
4934    /// length boundaries of the encoding.
4935    #[test]
4936    fn the_coded_number_round_trips_at_every_length_boundary() {
4937        for value in [
4938            0u64,
4939            0x7F,
4940            0x80,
4941            0x7FF,
4942            0x800,
4943            0xFFFF,
4944            0x1_0000,
4945            0x1F_FFFF,
4946            0x20_0000,
4947            0x3FF_FFFF,
4948            0x400_0000,
4949            0x7FFF_FFFF,
4950            0x8000_0000,
4951            (1 << 36) - 1,
4952        ] {
4953            let mut writer = BitWriter::new();
4954            write_coded_number(&mut writer, value);
4955            let bytes = writer.into_bytes();
4956            let mut reader = BitReader::new(&bytes, 0);
4957            assert_eq!(
4958                read_coded_number(&mut reader).expect("read"),
4959                value,
4960                "coded number {value:#x}"
4961            );
4962        }
4963    }
4964
4965    /// The deterministic cosine and logarithm against values checkable by
4966    /// hand. Accuracy here is loose on purpose: these feed a window shape
4967    /// and a ranking, and what the crate needs from them is identical bits
4968    /// everywhere, not the last ulp.
4969    #[test]
4970    fn the_deterministic_math_lands_near_the_true_values() {
4971        assert!((det_cos_pi(0.0) - 1.0).abs() < 1e-12);
4972        assert!(det_cos_pi(0.5).abs() < 1e-12);
4973        assert!((det_cos_pi(1.0) + 1.0).abs() < 1e-12);
4974        assert!((det_cos_pi(1.0 / 3.0) - 0.5).abs() < 1e-9);
4975        assert!((det_log2(8.0) - 3.0).abs() < 1e-9);
4976        assert!((det_log2(1.0)).abs() < 1e-9);
4977        assert!((det_log2(0.125) + 3.0).abs() < 1e-9);
4978        assert!((det_log2(3.0) - 1.584_962_500_721_156).abs() < 1e-9);
4979        // Subnormal inputs stay finite and ordered.
4980        assert!(det_log2(f64::from_bits(1)) < -1000.0);
4981    }
4982
4983    /// Quantised coefficients stay inside the fields that carry them.
4984    #[test]
4985    fn quantised_coefficients_fit_their_fields() {
4986        let mut state = 0xC0FF_EE00_u64;
4987        for _ in 0..200 {
4988            let order = (splitmix(&mut state) % 32 + 1) as usize;
4989            let coefficients: Vec<f64> = (0..order)
4990                .map(|_| {
4991                    let raw = splitmix(&mut state);
4992                    // Magnitudes from around 1e-4 to around 16.
4993                    let magnitude = ((raw >> 40) as f64 + 1.0) / 1_048_576.0;
4994                    let scaled = magnitude * ((1 << (raw % 18)) as f64 / 8.0);
4995                    if raw & 1 == 0 {
4996                        scaled
4997                    } else {
4998                        -scaled
4999                    }
5000                })
5001                .collect();
5002            let Some((quantised, shift)) = quantise_lpc(&coefficients, COEFFICIENT_PRECISION)
5003            else {
5004                continue;
5005            };
5006            assert!(shift <= 15, "shift {shift} does not fit the 5-bit field");
5007            assert_eq!(quantised.len(), order);
5008            let ceiling = (1i64 << (COEFFICIENT_PRECISION - 1)) - 1;
5009            let floor = -(1i64 << (COEFFICIENT_PRECISION - 1));
5010            for &q in &quantised {
5011                assert!(
5012                    (floor..=ceiling).contains(&q),
5013                    "coefficient {q} does not fit {COEFFICIENT_PRECISION} bits"
5014                );
5015            }
5016        }
5017    }
5018
5019    /// The shared prediction functions on values small enough to check by
5020    /// hand, so a rewrite of either cannot silently change what "order 2"
5021    /// means.
5022    #[test]
5023    fn the_shared_predictions_match_hand_arithmetic() {
5024        let history = [3i64, 5, 9, 15, 23];
5025        assert_eq!(fixed_prediction(&history, 0), 0);
5026        assert_eq!(fixed_prediction(&history, 1), 23);
5027        assert_eq!(fixed_prediction(&history, 2), 2 * 23 - 15);
5028        assert_eq!(fixed_prediction(&history, 3), 3 * 23 - 3 * 15 + 9);
5029        assert_eq!(fixed_prediction(&history, 4), 4 * 23 - 6 * 15 + 4 * 9 - 5);
5030        // Coefficients in bitstream order: the first multiplies the newest
5031        // sample. (2*23 + 1*15) >> 2 = 15 with truncation toward negative
5032        // infinity, which for a positive sum is plain division.
5033        assert_eq!(lpc_prediction(&[2, 1], &history, 2), (2 * 23 + 15) >> 2);
5034    }
5035}