gwseq-io 0.2.1

//! The internal encodings — how one data series is laid out inside a slice.
//!
//! Format reference: `docs/cram_format_v3.1.md` §13.
//!
//! Not to be confused with the *compression methods* in [`super::codecs`],
//! which squeeze a whole block once its layout is settled. A series says
//! `EXTERNAL(id=12)` — an encoding, meaning "my values are the next bytes of
//! block 12" — and block 12 separately says `rans4x16`, a method. The two are
//! read at different times by different code and it is worth keeping the words
//! apart.
//!
//! Four of these ([`Encoding::Beta`], [`Encoding::Subexp`],
//! [`Encoding::Gamma`], [`Encoding::Huffman`]) read *bits* from the slice's one
//! core block; the rest read bytes from external blocks. That is the whole
//! reason a slice has a core block at all, and why [`Streams`] carries a bit
//! reader alongside its byte cursors.

use crate::bytes::LeCursor;
use crate::error::{Error, Result};

use super::container::{read_itf8, read_itf8_array};

/// A most-significant-bit-first reader over the core data block.
///
/// §8.6: "a bit stream (most significant bit first)". One byte can hold several
/// records, so there is no aligning to anything — the reader carries a bit
/// position and nothing else.
#[derive(Debug)]
pub struct BitReader<'a> {
    data: &'a [u8],
    /// Bits consumed, so the byte is `bit >> 3` and the shift `7 - (bit & 7)`.
    bit: usize,
    path: &'a str,
}

impl<'a> BitReader<'a> {
    pub fn new(data: &'a [u8], path: &'a str) -> Self {
        Self { data, bit: 0, path }
    }

    fn exhausted(&self) -> Error {
        Error::corrupt(
            self.path,
            (self.bit / 8) as u64,
            "a core data block ran out of bits mid-record",
        )
    }

    #[inline]
    pub fn read_bit(&mut self) -> Result<u32> {
        let byte = *self
            .data
            .get(self.bit >> 3)
            .ok_or_else(|| self.exhausted())?;
        let value = u32::from(byte >> (7 - (self.bit & 7))) & 1;
        self.bit += 1;
        Ok(value)
    }

    /// `n` bits, most significant first. `n` of zero reads nothing and gives
    /// zero, which is what a zero-bit Huffman code and a zero-width beta both
    /// need.
    #[inline]
    pub fn read_bits(&mut self, n: u32) -> Result<u32> {
        if n > 32 {
            return Err(Error::corrupt(
                self.path,
                (self.bit / 8) as u64,
                format!("a {n}-bit field, which does not fit the 32 bits it is read into"),
            ));
        }
        let mut value = 0u32;
        for _ in 0..n {
            value = (value << 1) | self.read_bit()?;
        }
        Ok(value)
    }
}

/// A cursor into one external block.
#[derive(Debug)]
struct BlockCursor<'a> {
    data: &'a [u8],
    pos: usize,
}

/// Everything a data series can read from, for one slice.
///
/// External blocks are keyed by content id and **shared**: two series naming
/// the same block consume it in the order they are read, which is what the
/// format says and is the reason this is one table rather than a cursor per
/// series.
///
/// The table is two parallel arrays scanned linearly, not a `HashMap`. A slice
/// carries a few dozen blocks and this is looked up once per series per
/// record — tens of millions of times for a whole file — so the constant
/// matters more than the asymptotics: thirty `i32`s are two cache lines, and
/// hashing one key is not cheaper than reading them. Content ids are also
/// sparse (a tag block's id is its three letters packed into an integer), so
/// there is nothing to index directly by.
#[derive(Debug)]
pub struct Streams<'a> {
    pub core: BitReader<'a>,
    ids: Vec<i32>,
    cursors: Vec<BlockCursor<'a>>,
    path: &'a str,
}

impl<'a> Streams<'a> {
    pub fn new(
        core: &'a [u8],
        external: impl IntoIterator<Item = (i32, &'a [u8])>,
        path: &'a str,
    ) -> Self {
        let (ids, cursors) = external
            .into_iter()
            .map(|(id, data)| (id, BlockCursor { data, pos: 0 }))
            .unzip();
        Self {
            core: BitReader::new(core, path),
            ids,
            cursors,
            path,
        }
    }

    fn index(&self, id: i32) -> Result<usize> {
        self.ids
            .iter()
            .position(|candidate| *candidate == id)
            .ok_or_else(|| {
                Error::corrupt(
                    self.path,
                    0,
                    format!(
                        "a data series reads external block {id}, which its slice does not carry"
                    ),
                )
            })
    }

    fn block(&mut self, id: i32) -> Result<&mut BlockCursor<'a>> {
        let index = self.index(id)?;
        Ok(&mut self.cursors[index])
    }

    fn take(&mut self, id: i32, n: usize) -> Result<&'a [u8]> {
        let path = self.path;
        let cursor = self.block(id)?;
        let end = cursor
            .pos
            .checked_add(n)
            .filter(|end| *end <= cursor.data.len())
            .ok_or_else(|| {
                Error::corrupt(
                    path,
                    cursor.pos as u64,
                    format!(
                        "a data series wants {n} bytes of external block {id} with {} left",
                        cursor.data.len() - cursor.pos
                    ),
                )
            })?;
        let out = &cursor.data[cursor.pos..end];
        cursor.pos = end;
        Ok(out)
    }

    fn byte(&mut self, id: i32) -> Result<u8> {
        Ok(self.take(id, 1)?[0])
    }

    /// Bytes up to and including `stop`, returning what came before it.
    fn take_until(&mut self, id: i32, stop: u8) -> Result<&'a [u8]> {
        let path = self.path;
        let cursor = self.block(id)?;
        let rest = &cursor.data[cursor.pos..];
        let end = memchr::memchr(stop, rest).ok_or_else(|| {
            Error::corrupt(
                path,
                cursor.pos as u64,
                format!("a byte array in external block {id} with no {stop:#04x} to end it"),
            )
        })?;
        cursor.pos += end + 1;
        Ok(&rest[..end])
    }
}

/// One of §13's codecs, with its parameters.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub enum Encoding {
    /// The series is not stored. Reading one is an error rather than a default:
    /// a `NULL` series is one the file says nothing about, and inventing a
    /// value would be inventing data.
    ///
    /// The `Default`, because an absent series is exactly this.
    #[default]
    Null,
    External {
        block_id: i32,
    },
    Huffman {
        /// Symbols and codes, sorted into canonical order at parse time.
        symbols: Vec<i32>,
        /// `(first code, first index, count)` for each bit length in use,
        /// ascending — which is all canonical decoding needs.
        lengths: Vec<(u32, u32, usize, usize)>,
        /// The one-symbol case, whose codeword is zero bits long. §13.3 calls
        /// this out specifically: it is how the format spells a constant.
        constant: Option<i32>,
    },
    ByteArrayLen {
        len: Box<Encoding>,
        value: Box<Encoding>,
    },
    ByteArrayStop {
        stop: u8,
        block_id: i32,
    },
    Beta {
        offset: i32,
        bits: u32,
    },
    Subexp {
        offset: i32,
        k: u32,
    },
    Gamma {
        offset: i32,
    },
}

impl Encoding {
    /// Read an encoding: a codec id, a parameter byte count, then the
    /// parameters.
    ///
    /// The declared byte count is honoured rather than assumed — the cursor is
    /// moved to the end of the parameters whatever the codec consumed — so a
    /// codec that grows a parameter in a later minor version does not
    /// desynchronise the whole map.
    pub fn read(cursor: &mut LeCursor<'_>) -> Result<Self> {
        let codec = read_itf8(cursor)?;
        let n_bytes = read_itf8(cursor)?;
        if n_bytes < 0 {
            return Err(Error::corrupt(
                cursor.path(),
                cursor.file_offset(),
                format!("an encoding with {n_bytes} parameter bytes"),
            ));
        }
        let start = cursor.position();
        let end = start + n_bytes as usize;
        let encoding = Self::read_params(cursor, codec)?;
        cursor.seek(end)?;
        Ok(encoding)
    }

    fn read_params(cursor: &mut LeCursor<'_>, codec: i32) -> Result<Self> {
        Ok(match codec {
            0 => Self::Null,
            1 => Self::External {
                block_id: read_itf8(cursor)?,
            },
            3 => {
                let symbols = read_itf8_array(cursor)?;
                let lengths = read_itf8_array(cursor)?;
                Self::huffman(symbols, lengths, cursor)?
            }
            4 => Self::ByteArrayLen {
                len: Box::new(Self::read(cursor)?),
                value: Box::new(Self::read(cursor)?),
            },
            5 => Self::ByteArrayStop {
                stop: cursor.take(1)?[0],
                block_id: read_itf8(cursor)?,
            },
            6 => Self::Beta {
                offset: read_itf8(cursor)?,
                bits: Self::bit_width(read_itf8(cursor)?, cursor)?,
            },
            7 => Self::Subexp {
                offset: read_itf8(cursor)?,
                k: Self::bit_width(read_itf8(cursor)?, cursor)?,
            },
            9 => Self::Gamma {
                offset: read_itf8(cursor)?,
            },
            // §13.8 and §13.9. Both were dropped after CRAM 1.0 and this
            // reader does not open a 1.0 file at all, so meeting one means the
            // encoding map is not what it claims to be.
            2 | 8 => {
                return Err(Error::Unsupported(format!(
                    "{}: a data series uses golomb coding, which cram 3 does not define",
                    cursor.path()
                )))
            }
            other => {
                return Err(Error::corrupt(
                    cursor.path(),
                    cursor.file_offset(),
                    format!("encoding codec {other} is not one the format defines"),
                ))
            }
        })
    }

    fn bit_width(value: i32, cursor: &LeCursor<'_>) -> Result<u32> {
        if !(0..=32).contains(&value) {
            return Err(Error::corrupt(
                cursor.path(),
                cursor.file_offset(),
                format!("an encoding of {value} bits"),
            ));
        }
        Ok(value as u32)
    }

    /// Build the canonical code table from the symbols and their bit lengths.
    ///
    /// §13.3: sort by bit length then by symbol value, give the first symbol a
    /// codeword of all zeros, and increment from there — shifting left when the
    /// length grows. Only the per-length starting points are kept, which is
    /// what a bit-by-bit decode needs.
    fn huffman(symbols: Vec<i32>, bit_lengths: Vec<i32>, cursor: &LeCursor<'_>) -> Result<Self> {
        if symbols.len() != bit_lengths.len() {
            return Err(Error::corrupt(
                cursor.path(),
                cursor.file_offset(),
                format!(
                    "a huffman table of {} symbols and {} code lengths",
                    symbols.len(),
                    bit_lengths.len()
                ),
            ));
        }
        if symbols.is_empty() {
            return Err(Error::corrupt(
                cursor.path(),
                cursor.file_offset(),
                "an empty huffman table",
            ));
        }
        // The constant case: one symbol, zero bits.
        if symbols.len() == 1 {
            return Ok(Self::Huffman {
                symbols,
                lengths: Vec::new(),
                constant: None,
            }
            .with_constant());
        }
        let mut pairs: Vec<(u32, i32)> = bit_lengths
            .iter()
            .zip(&symbols)
            .map(|(len, symbol)| {
                if !(1..=32).contains(len) {
                    return Err(Error::corrupt(
                        cursor.path(),
                        cursor.file_offset(),
                        format!("a huffman codeword of {len} bits"),
                    ));
                }
                Ok((*len as u32, *symbol))
            })
            .collect::<Result<_>>()?;
        pairs.sort_unstable();

        let mut sorted = Vec::with_capacity(pairs.len());
        let mut lengths: Vec<(u32, u32, usize, usize)> = Vec::new();
        let mut code = 0u32;
        let mut previous_len = 0u32;
        // The Kraft sum, in units of 2^-32. A canonical code is only decodable
        // if it sums to at most 1; an over-subscribed table is accepted by the
        // arithmetic below and then decodes ambiguously, which is a wrong
        // answer rather than an error.
        let mut kraft = 0u64;
        for (index, (len, symbol)) in pairs.into_iter().enumerate() {
            kraft += 1u64 << (32 - len.min(32));
            if kraft > 1u64 << 32 {
                return Err(Error::corrupt(
                    cursor.path(),
                    cursor.file_offset(),
                    "a huffman table whose code lengths over-subscribe the code",
                ));
            }
            if index > 0 {
                // Both of these overflow on lengths a file may name —
                // `[1, 2, …, 32, 32]` reaches 2^32 — which is a debug panic
                // and a silent wrap in release. The Kraft check above makes
                // that unreachable for a table that decodes at all; these are
                // belt and braces, and cheap.
                code = code.wrapping_add(1);
                code = code.wrapping_shl(len - previous_len);
            }
            if lengths.last().map(|(l, ..)| *l) != Some(len) {
                lengths.push((len, code, index, 0));
            }
            let last = lengths.last_mut().expect("just pushed");
            last.3 += 1;
            previous_len = len;
            sorted.push(symbol);
        }
        Ok(Self::Huffman {
            symbols: sorted,
            lengths,
            constant: None,
        })
    }

    fn with_constant(self) -> Self {
        match self {
            Self::Huffman { symbols, .. } => {
                let constant = symbols.first().copied();
                Self::Huffman {
                    symbols,
                    lengths: Vec::new(),
                    constant,
                }
            }
            other => other,
        }
    }

    /// Whether this encoding stores anything at all.
    pub fn is_null(&self) -> bool {
        matches!(self, Self::Null)
    }

    /// Every external block this encoding reads, so a slice knows which of its
    /// blocks are wanted before it decodes any.
    pub fn block_ids(&self, out: &mut Vec<i32>) {
        match self {
            Self::External { block_id } | Self::ByteArrayStop { block_id, .. } => {
                out.push(*block_id)
            }
            Self::ByteArrayLen { len, value } => {
                len.block_ids(out);
                value.block_ids(out);
            }
            _ => {}
        }
    }

    /// Decode one integer.
    pub fn decode_int(&self, streams: &mut Streams<'_>) -> Result<i32> {
        Ok(match self {
            Self::External { block_id } => {
                // One lookup, not two: the cursor's data and position are both
                // `Copy`, so the reader below borrows neither the cursor nor
                // the stream table, and the position can be advanced after it.
                let path = streams.path;
                let cursor = streams.block(*block_id)?;
                let (data, pos) = (cursor.data, cursor.pos);
                let mut le = LeCursor::new(&data[pos..], pos as u64, path);
                let value = read_itf8(&mut le)?;
                cursor.pos += le.position();
                value
            }
            Self::Huffman {
                symbols,
                lengths,
                constant,
            } => {
                if let Some(value) = constant {
                    return Ok(*value);
                }
                Self::huffman_decode(symbols, lengths, streams)?
            }
            // Wrapping, not because the result means anything when it wraps,
            // but because `BETA(-1, 31)` over all-ones is an ordinary hostile
            // input and a debug-build panic on hostile input is a bug in its
            // own right — the standard this crate states in `codecs/arith.rs`.
            // A wrapped value goes on to fail some later bound instead.
            Self::Beta { offset, bits } => {
                (streams.core.read_bits(*bits)? as i32).wrapping_sub(*offset)
            }
            Self::Subexp { offset, k } => {
                let mut u = 0u32;
                while streams.core.read_bit()? == 1 {
                    u += 1;
                    if u > 32 {
                        return Err(Error::corrupt(
                            streams.path,
                            0,
                            "a subexponential codeword with more than 32 leading ones",
                        ));
                    }
                }
                let n = if u == 0 {
                    streams.core.read_bits(*k)?
                } else {
                    // `u` may reach 32 and `k` 32, so the width can exceed the
                    // 32 bits it shifts into: `1u32 << 32` is a panic in debug
                    // and a no-op in release. `read_bits` refuses anything
                    // past 32 itself, so this only has to refuse the shift.
                    let width = u + k - 1;
                    if width >= 32 {
                        return Err(Error::corrupt(
                            streams.path,
                            0,
                            format!("a subexponential codeword {width} bits wide"),
                        ));
                    }
                    (1u32 << width) + streams.core.read_bits(width)?
                };
                (n as i32).wrapping_sub(*offset)
            }
            Self::Gamma { offset } => {
                let mut zeros = 0u32;
                while streams.core.read_bit()? == 0 {
                    zeros += 1;
                    if zeros > 32 {
                        return Err(Error::corrupt(
                            streams.path,
                            0,
                            "an elias gamma codeword with more than 32 leading zeros",
                        ));
                    }
                }
                // The 1 just read is the value's top bit.
                let mut value = 1u32;
                for _ in 0..zeros {
                    value = (value << 1) | streams.core.read_bit()?;
                }
                (value as i32).wrapping_sub(*offset)
            }
            Self::Null => return Err(self.null_error(streams.path)),
            Self::ByteArrayLen { .. } | Self::ByteArrayStop { .. } => {
                return Err(Error::corrupt(
                    streams.path,
                    0,
                    "a byte-array encoding used for an integer data series",
                ))
            }
        })
    }

    /// Decode one byte.
    ///
    /// Separate from [`Self::decode_int`] because `EXTERNAL` means different
    /// things for the two: a byte series is one raw byte of the block, an
    /// integer series is an ITF8. Reading a `BA` base through the integer path
    /// gives the right answer for bases under 128 and the wrong one for the
    /// rest, which is the sort of bug that survives a smoke test.
    pub fn decode_byte(&self, streams: &mut Streams<'_>) -> Result<u8> {
        Ok(match self {
            Self::External { block_id } => streams.byte(*block_id)?,
            Self::Huffman { .. } | Self::Beta { .. } | Self::Subexp { .. } | Self::Gamma { .. } => {
                self.decode_int(streams)? as u8
            }
            Self::Null => return Err(self.null_error(streams.path)),
            Self::ByteArrayLen { .. } | Self::ByteArrayStop { .. } => {
                return Err(Error::corrupt(
                    streams.path,
                    0,
                    "a byte-array encoding used for a single-byte data series",
                ))
            }
        })
    }

    /// Decode a byte array onto the end of `out`.
    ///
    /// `len` is supplied by the caller for the series whose length comes from
    /// somewhere else — `BA` over a read length, `QS` over the same — and is
    /// `None` for the ones that carry their own.
    pub fn decode_array(
        &self,
        streams: &mut Streams<'_>,
        len: Option<usize>,
        out: &mut Vec<u8>,
    ) -> Result<()> {
        match self {
            Self::ByteArrayStop { stop, block_id } => {
                out.extend_from_slice(streams.take_until(*block_id, *stop)?);
            }
            Self::ByteArrayLen {
                len: len_enc,
                value,
            } => {
                let n = len_enc.decode_int(streams)?;
                if n < 0 {
                    return Err(Error::corrupt(
                        streams.path,
                        0,
                        format!("a byte array of {n} bytes"),
                    ));
                }
                value.decode_n(streams, n as usize, out)?;
            }
            Self::External { .. } | Self::Huffman { .. } => {
                let n = len.ok_or_else(|| {
                    Error::corrupt(
                        streams.path,
                        0,
                        "a byte-array data series with neither a stored length nor one to hand",
                    )
                })?;
                self.decode_n(streams, n, out)?;
            }
            Self::Null => return Err(self.null_error(streams.path)),
            other => {
                return Err(Error::corrupt(
                    streams.path,
                    0,
                    format!("{other:?} cannot encode a byte array"),
                ))
            }
        }
        Ok(())
    }

    /// `n` bytes through this encoding, appended to `out`.
    fn decode_n(&self, streams: &mut Streams<'_>, n: usize, out: &mut Vec<u8>) -> Result<()> {
        // The common case by far, and worth not doing a byte at a time: a run
        // of an external block is a slice of it.
        if let Self::External { block_id } = self {
            out.extend_from_slice(streams.take(*block_id, n)?);
            return Ok(());
        }
        out.reserve(n.min(1 << 20));
        for _ in 0..n {
            out.push(self.decode_byte(streams)?);
        }
        Ok(())
    }

    fn huffman_decode(
        symbols: &[i32],
        lengths: &[(u32, u32, usize, usize)],
        streams: &mut Streams<'_>,
    ) -> Result<i32> {
        let mut code = 0u32;
        let mut bits = 0u32;
        for &(len, first_code, first_index, count) in lengths {
            while bits < len {
                code = (code << 1) | streams.core.read_bit()?;
                bits += 1;
            }
            let offset = code.wrapping_sub(first_code) as usize;
            if offset < count {
                return Ok(symbols[first_index + offset]);
            }
        }
        Err(Error::corrupt(
            streams.path,
            0,
            "a bit pattern no huffman codeword in this slice's table matches",
        ))
    }

    fn null_error(&self, path: &str) -> Error {
        Error::corrupt(
            path,
            0,
            "a record reads a data series this file's encoding map stores as NULL",
        )
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn streams<'a>(core: &'a [u8], external: &'a [(i32, &'a [u8])]) -> Streams<'a> {
        Streams::new(core, external.iter().map(|(id, d)| (*id, *d)), "test")
    }

    fn parse(bytes: &[u8]) -> Encoding {
        let mut cursor = LeCursor::new(bytes, 0, "test");
        Encoding::read(&mut cursor).expect("an encoding")
    }

    /// Hostile codeword widths, which a debug build used to abort on.
    ///
    /// The crate's rule, stated in `codecs/arith.rs`, is that a debug-build
    /// panic on hostile input is a bug in its own right: the Python extension
    /// ships release and would wrap instead, but anyone running the suite over
    /// a fuzzed slice gets an abort rather than a named failure.
    #[test]
    fn hostile_bit_codec_parameters_give_errors_rather_than_overflow() {
        // SUBEXP(0, 1) over thirty-two leading ones: `u + k - 1` reaches 32,
        // and `1u32 << 32` is the panic.
        let subexp = Encoding::Subexp { offset: 0, k: 1 };
        let ones = [0xffu8; 8];
        let mut s = streams(&ones, &[]);
        assert!(subexp.decode_int(&mut s).is_err());

        // BETA(-1, 31) over all-ones: `read_bits` gives 2^31 - 1 and the
        // offset subtraction overflows an i32.
        let beta = Encoding::Beta {
            offset: -1,
            bits: 31,
        };
        let mut s = streams(&ones, &[]);
        assert_eq!(
            beta.decode_int(&mut s).expect("wraps, does not abort"),
            i32::MIN
        );

        // GAMMA(-1) likewise.
        let gamma = Encoding::Gamma { offset: -1 };
        let zeros_then_ones = [0x00u8, 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
        let mut s = streams(&zeros_then_ones, &[]);
        let _ = gamma.decode_int(&mut s);
    }

    /// A canonical Huffman code whose lengths claim more of the code space
    /// than there is.
    ///
    /// Accepted, it decodes ambiguously — two symbols sharing a codeword —
    /// which is a wrong answer rather than an error. The code assignment also
    /// used to overflow on the way: `[1, 2, …, 32, 32]` reaches 2^32.
    #[test]
    fn an_over_subscribed_huffman_table_is_refused() {
        // Four symbols, each claimed to be one bit long: a one-bit code has
        // room for two.
        let mut bytes = vec![3u8, 12u8]; // codec 3, twelve parameter bytes
        bytes.push(4); // four symbols
        bytes.extend_from_slice(&[0, 1, 2, 3]);
        bytes.push(4); // four lengths
        bytes.extend_from_slice(&[1, 1, 1, 1]);
        let mut cursor = LeCursor::new(&bytes, 0, "test");
        let error = Encoding::read(&mut cursor).expect_err("over-subscribed");
        assert!(error.to_string().contains("over-subscribe"), "{error}");

        // One more symbol than the code has room for, at the widest length.
        let mut bytes = vec![3u8, 0u8];
        let mut params = vec![34u8];
        params.extend(0..34u8);
        params.push(34);
        params.extend((1..=32u8).chain([32, 32]));
        bytes[1] = params.len() as u8;
        bytes.extend_from_slice(&params);
        let mut cursor = LeCursor::new(&bytes, 0, "test");
        assert!(Encoding::read(&mut cursor).is_err(), "one code too many");
    }

    /// The widest legal canonical code, which fills the space exactly.
    ///
    /// Lengths `1, 2, …, 32, 32` sum to exactly one under Kraft, so this is a
    /// table an encoder may legitimately write — and it is also the shape that
    /// walks the code assignment to the top of a `u32`. It must be accepted,
    /// and it must not overflow on the way.
    #[test]
    fn the_widest_complete_huffman_table_is_accepted_without_overflow() {
        let mut bytes = vec![3u8, 0u8];
        let mut params = vec![33u8];
        params.extend(0..33u8);
        params.push(33);
        params.extend((1..=32u8).chain(std::iter::once(32)));
        bytes[1] = params.len() as u8;
        bytes.extend_from_slice(&params);
        let mut cursor = LeCursor::new(&bytes, 0, "test");
        Encoding::read(&mut cursor).expect("a complete code, however wide");
    }

    /// A code that exactly fills the space is still accepted.
    #[test]
    fn a_complete_huffman_table_is_accepted() {
        let mut bytes = vec![3u8, 0u8];
        let params = vec![2u8, 0, 1, 2, 1, 1];
        bytes[1] = params.len() as u8;
        bytes.extend_from_slice(&params);
        let mut cursor = LeCursor::new(&bytes, 0, "test");
        let encoding = Encoding::read(&mut cursor).expect("two one-bit codes fill the code");
        let mut s = streams(&[0b0100_0000], &[]);
        assert_eq!(encoding.decode_int(&mut s).expect("first"), 0);
        assert_eq!(encoding.decode_int(&mut s).expect("second"), 1);
    }

    /// §13.4's worked example, byte for byte: a `BYTE_ARRAY_LEN` whose length
    /// is a one-symbol Huffman (always 2) and whose values come from external
    /// block 200.
    #[test]
    fn the_spec_byte_array_len_example_parses_to_what_it_describes() {
        let bytes = [
            0x04, 0x0a, // BYTE_ARRAY_LEN, 10 parameter bytes
            0x03, 0x04, 0x01, 0x02, 0x01, 0x00, // HUFFMAN: one symbol (2), one length (0)
            0x01, 0x02, 0x80, 0xc8, // EXTERNAL, 2 bytes, block 200
        ];
        let mut cursor = LeCursor::new(&bytes, 0, "test");
        let encoding = Encoding::read(&mut cursor).expect("an encoding");
        let Encoding::ByteArrayLen { len, value } = &encoding else {
            panic!("not a byte array len: {encoding:?}")
        };
        assert_eq!(**value, Encoding::External { block_id: 200 });
        // A one-symbol Huffman is a constant and reads no bits at all.
        let mut s = streams(&[], &[(200, b"ab")]);
        assert_eq!(len.decode_int(&mut s).expect("constant"), 2);

        let mut out = Vec::new();
        encoding
            .decode_array(&mut s, None, &mut out)
            .expect("array");
        assert_eq!(out, b"ab");
    }

    /// §13.3's example table, which is the whole of canonical Huffman in six
    /// rows. Symbols are the values 0..5 standing in for A..F.
    #[test]
    fn canonical_huffman_assigns_the_codewords_the_spec_prints() {
        let mut bytes = vec![0x03, 0x00];
        let mut params = vec![6u8, 0, 1, 2, 3, 4, 5]; // alphabet: A..F as 0..5
        params.extend_from_slice(&[6, 1, 3, 3, 3, 4, 4]); // bit lengths
        bytes[1] = params.len() as u8;
        bytes.extend_from_slice(&params);
        let encoding = parse(&bytes);

        // A=0, B=100, C=101, D=110, E=1110, F=1111 packed msb-first:
        // 0 100 101 110 1110 1111 -> 0100 1011 1011 1011 11 (padded)
        let core = [0b0100_1011, 0b1011_1011, 0b1100_0000];
        let mut s = streams(&core, &[]);
        for expected in [0, 1, 2, 3, 4, 5] {
            assert_eq!(encoding.decode_int(&mut s).expect("a symbol"), expected);
        }
    }

    #[test]
    fn a_one_symbol_huffman_is_a_constant_and_reads_no_bits() {
        let bytes = [0x03, 0x04, 0x01, 0x2a, 0x01, 0x00];
        let encoding = parse(&bytes);
        let mut s = streams(&[], &[]);
        for _ in 0..100 {
            assert_eq!(encoding.decode_int(&mut s).expect("constant"), 42);
        }
    }

    /// §13.5's table: three bits and an offset of -10 spelling 10 to 15.
    #[test]
    fn beta_coding_reads_the_spec_example() {
        // offset -10 as itf8 is the five-byte form.
        let mut params = vec![0xff, 0xff, 0xff, 0xff, 0x06]; // -10
        params.push(3);
        let mut bytes = vec![0x06, params.len() as u8];
        bytes.extend_from_slice(&params);
        let encoding = parse(&bytes);
        assert_eq!(
            encoding,
            Encoding::Beta {
                offset: -10,
                bits: 3
            }
        );
        // 000 001 010 011 100 101
        let core = [0b0000_0101, 0b0011_1001, 0b0100_0000];
        let mut s = streams(&core, &[]);
        for expected in 10..=15 {
            assert_eq!(encoding.decode_int(&mut s).expect("a value"), expected);
        }
    }

    /// §13.6's table, for each of the three `k` it prints.
    #[test]
    fn subexponential_coding_reads_the_spec_examples() {
        let cases: [(u32, &[&str]); 3] = [
            (
                0,
                &[
                    "0", "10", "1100", "1101", "111000", "111001", "111010", "111011", "11110000",
                    "11110001", "11110010",
                ],
            ),
            (
                1,
                &[
                    "00", "01", "100", "101", "11000", "11001", "11010", "11011", "1110000",
                    "1110001", "1110010",
                ],
            ),
            (
                2,
                &[
                    "000", "001", "010", "011", "1000", "1001", "1010", "1011", "110000", "110001",
                    "110010",
                ],
            ),
        ];
        for (k, codewords) in cases {
            let encoding = Encoding::Subexp { offset: 0, k };
            let bits: String = codewords.concat();
            let core = pack_bits(&bits);
            let mut s = streams(&core, &[]);
            for (expected, codeword) in codewords.iter().enumerate() {
                assert_eq!(
                    encoding.decode_int(&mut s).expect("a value"),
                    expected as i32,
                    "k={k}, codeword {codeword}"
                );
            }
        }
    }

    /// §13.7's table.
    #[test]
    fn gamma_coding_reads_the_spec_example() {
        let encoding = Encoding::Gamma { offset: 0 };
        let core = pack_bits("1010011 00100");
        let mut s = streams(&core, &[]);
        for expected in [1, 2, 3, 4] {
            assert_eq!(encoding.decode_int(&mut s).expect("a value"), expected);
        }
    }

    #[test]
    fn byte_array_stop_returns_what_precedes_its_terminator() {
        let bytes = [0x05, 0x02, 0x00, 0x0b]; // stop 0, block 11
        let encoding = parse(&bytes);
        let mut s = streams(&[], &[(11, b"first\0second\0")]);
        let mut out = Vec::new();
        encoding
            .decode_array(&mut s, None, &mut out)
            .expect("array");
        assert_eq!(out, b"first");
        out.clear();
        encoding
            .decode_array(&mut s, None, &mut out)
            .expect("array");
        assert_eq!(out, b"second");
        // And the third read has nothing to end it.
        assert!(encoding.decode_array(&mut s, None, &mut out).is_err());
    }

    /// An external integer series is ITF8; an external byte series is one raw
    /// byte. Reading a base of 0xC1 through the integer path would consume two
    /// bytes and give 0x0100-something.
    #[test]
    fn external_reads_itf8_for_integers_and_raw_bytes_for_bytes() {
        let encoding = Encoding::External { block_id: 1 };
        let mut s = streams(&[], &[(1, &[0xc1, 0x00, 0x00])]);
        assert_eq!(encoding.decode_int(&mut s).expect("an int"), 0x1_0000);
        let mut s = streams(&[], &[(1, &[0xc1, 0x00, 0x00])]);
        assert_eq!(encoding.decode_byte(&mut s).expect("a byte"), 0xc1);
    }

    /// Two series naming one block share its cursor, and consume it in the
    /// order they are read.
    #[test]
    fn two_series_on_one_block_consume_it_in_read_order() {
        let a = Encoding::External { block_id: 7 };
        let b = Encoding::External { block_id: 7 };
        let mut s = streams(&[], &[(7, b"xy")]);
        assert_eq!(a.decode_byte(&mut s).expect("a"), b'x');
        assert_eq!(b.decode_byte(&mut s).expect("b"), b'y');
    }

    #[test]
    fn a_null_series_is_an_error_rather_than_a_default() {
        let mut s = streams(&[], &[]);
        assert!(Encoding::Null.decode_int(&mut s).is_err());
        assert!(Encoding::Null.decode_byte(&mut s).is_err());
    }

    #[test]
    fn golomb_is_refused_by_name() {
        for codec in [2u8, 8] {
            let bytes = [codec, 0x02, 0x00, 0x01];
            let mut cursor = LeCursor::new(&bytes, 0, "test");
            match Encoding::read(&mut cursor) {
                Err(Error::Unsupported(message)) => {
                    assert!(message.contains("golomb"), "{message}")
                }
                other => panic!("codec {codec} gave {other:?}"),
            }
        }
    }

    /// The declared parameter length is what the cursor moves by, so an
    /// encoding carrying more than this reader understands does not
    /// desynchronise the map behind it.
    #[test]
    fn a_longer_parameter_block_than_the_codec_reads_is_skipped_whole() {
        let bytes = [
            0x01, 0x04, 0x0b, 0xff, 0xff, 0xff, // EXTERNAL(11) with three spare bytes
            0x01, 0x01, 0x0c, // EXTERNAL(12)
        ];
        let mut cursor = LeCursor::new(&bytes, 0, "test");
        assert_eq!(
            Encoding::read(&mut cursor).expect("first"),
            Encoding::External { block_id: 11 }
        );
        assert_eq!(
            Encoding::read(&mut cursor).expect("second"),
            Encoding::External { block_id: 12 }
        );
    }

    /// Turn a string of `0`/`1` (spaces ignored) into msb-first bytes.
    fn pack_bits(bits: &str) -> Vec<u8> {
        let mut out = Vec::new();
        let mut byte = 0u8;
        let mut n = 0;
        for c in bits.chars().filter(|c| *c == '0' || *c == '1') {
            byte = (byte << 1) | u8::from(c == '1');
            n += 1;
            if n == 8 {
                out.push(byte);
                byte = 0;
                n = 0;
            }
        }
        if n > 0 {
            out.push(byte << (8 - n));
        }
        out
    }
}