gwseq-io 0.2.1

//! The adaptive arithmetic coder — CRAM 3.1's alternative to rANS N×16.
//!
//! Reference: `docs/cram_codecs_v3.1.md` §4.
//!
//! Where rANS stores a frequency table and decodes against it, this stores
//! *nothing*: both sides start from a uniform model and update it identically
//! after every symbol, so the table is re-derived from the bytes already
//! decoded. That makes it smaller on data with local structure, and it makes it
//! unforgiving — a single symbol decoded wrongly corrupts the model, and every
//! symbol after it decodes against a table the encoder never had. There is no
//! resynchronisation. This is the codec where "returns plausible bytes instead
//! of failing" is least likely to hold: it usually turns into a length
//! mismatch a few hundred bytes later.
//!
//! The outer layer — the flag byte, `Stripe`, `Pack`, `Cat`, `NoSize` — is
//! rANS N×16's, near enough that [`super::rans4x16`] is worth reading first.
//! Three things differ:
//!
//! * `N32` does not exist. Bit 2 is reserved (§4 keeps it for a possible
//!   order-2), and bit 4 is `Ext`.
//! * `Ext` routes the whole stream to bzip2, so that `Pack` and `Stripe` can be
//!   applied before it. §4 admits this is a layering mistake kept for 3.0
//!   compatibility.
//! * `RLE` is not a transform undone after entropy decoding. It is *inside* the
//!   coder: literals and run lengths come from separate models, interleaved in
//!   one stream. There is no `RleMeta` because there is nothing to store.
//!
//! # A correction to the pseudocode
//!
//! §4.3's `DecodeRLE0` and `DecodeRLE1` end their loop body with `i <- run+1`,
//! which would restart the output at the same place for every run. It is
//! `i <- i + run + 1`; §4.3's own worked example — `ABBCCCCDDDDD` as
//! `A<0> B<1> C<3,0> D<3,1>` — only reaches twelve bytes that way. The same
//! inversion of `NoSize` that §3.7 has is here too, and corrected the same way;
//! see [`super::rans4x16`].

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

use super::{bzip2, ByteReader, PackMeta, MAX_CODEC_LEN};

/// The flag byte, §4.3.
mod flag {
    pub const ORDER: u8 = 1;
    pub const EXT: u8 = 4;
    pub const STRIPE: u8 = 8;
    pub const NO_SIZE: u8 = 16;
    pub const CAT: u8 = 32;
    pub const RLE: u8 = 64;
    pub const PACK: u8 = 128;
}

/// How deep a stripe may nest. As [`super::rans4x16`]: real data never nests.
const MAX_STRIPE_DEPTH: u32 = 4;

/// Decode a complete arithmetic-coded block.
pub fn decode(data: &[u8], path: &str, offset: u64) -> Result<Vec<u8>> {
    let mut reader = ByteReader::new(data, path, offset);
    decode_stream(&mut reader, None, 0)
}

fn decode_stream(
    reader: &mut ByteReader<'_>,
    known_len: Option<usize>,
    depth: u32,
) -> Result<Vec<u8>> {
    let flags = reader.u8()?;

    let mut len = if flags & flag::NO_SIZE == 0 {
        reader.length()?
    } else {
        known_len.ok_or_else(|| {
            Error::corrupt(
                reader.path(),
                reader.offset(),
                "an arith stream sets NoSize but nothing outside it knows the size",
            )
        })?
    };

    if flags & flag::STRIPE != 0 {
        return decode_stripe(reader, len, depth);
    }

    // Pack's meta-data is read before the entropy decode and applied after it,
    // and it rewrites `len` to the length of the *packed* data underneath.
    let mut pack = None;
    if flags & flag::PACK != 0 {
        let unpacked_len = len;
        let meta = PackMeta::read(reader)?;
        len = meta.packed_len;
        pack = Some((meta, unpacked_len));
    }

    if len > MAX_CODEC_LEN {
        return Err(Error::corrupt(
            reader.path(),
            reader.offset(),
            format!("an arith stream declares {len} bytes, past this reader's ceiling"),
        ));
    }

    let mut data = if flags & flag::CAT != 0 {
        reader.take(len)?.to_vec()
    } else if flags & flag::EXT != 0 {
        // §4.3: "the magic number *must* be validated" — bzip2 is the only
        // external codec defined, and `bzip2::decode` checks `BZh` itself.
        bzip2::decode(
            reader.take(reader.remaining())?,
            len,
            reader.path(),
            reader.offset(),
        )?
    } else {
        let rle = flags & flag::RLE != 0;
        let order_1 = flags & flag::ORDER != 0;
        match (rle, order_1) {
            (false, false) => decode_order_0(reader, len)?,
            (false, true) => decode_order_1(reader, len)?,
            (true, false) => decode_rle_0(reader, len)?,
            (true, true) => decode_rle_1(reader, len)?,
        }
    };

    if let Some((meta, unpacked_len)) = pack {
        data = meta.unpack(&data, unpacked_len, reader.path(), reader.offset())?;
    }
    Ok(data)
}

/// §4.3's `DecodeStripe`: `N` sub-streams holding every `N`th byte.
fn decode_stripe(reader: &mut ByteReader<'_>, len: usize, depth: u32) -> Result<Vec<u8>> {
    if depth >= MAX_STRIPE_DEPTH {
        return Err(Error::corrupt(
            reader.path(),
            reader.offset(),
            "arith stripes nested past this reader's limit",
        ));
    }
    let n = reader.u8()? as usize;
    if n == 0 {
        return Err(Error::corrupt(
            reader.path(),
            reader.offset(),
            "an arith stripe of zero sub-streams",
        ));
    }
    let mut lengths = Vec::with_capacity(n);
    for _ in 0..n {
        lengths.push(reader.length()?);
    }

    let mut out = vec![0u8; len];
    for (j, compressed_len) in lengths.into_iter().enumerate() {
        let sub_len = len / n + usize::from(len % n > j);
        let bytes = reader.take(compressed_len)?;
        let mut sub = ByteReader::new(bytes, reader.path(), reader.offset());
        let decoded = decode_stream(&mut sub, Some(sub_len), depth + 1)?;
        if decoded.len() != sub_len {
            return Err(Error::corrupt(
                reader.path(),
                reader.offset(),
                format!(
                    "an arith stripe sub-stream gave {} bytes where {sub_len} were due",
                    decoded.len()
                ),
            ));
        }
        for (i, byte) in decoded.into_iter().enumerate() {
            out[i * n + j] = byte;
        }
    }
    Ok(out)
}

/// §4's range decoder: `code` is a window into the stream, `range` the width
/// still to be divided up.
///
/// Shared with [`super::fqzcomp`], which §6 builds directly on §4's coder and
/// models — "the entropy encoder used is shared between all models, so the bit
/// streams are multiplexed together".
pub(super) struct RangeCoder {
    range: u32,
    code: u32,
}

impl RangeCoder {
    /// §4's `RangeDecodeCreate`.
    ///
    /// **Five** bytes, not four. The specification's `for i <- 0 to 4` is
    /// inclusive — as its rANS loops are — and the following `code AND 2^32-1`
    /// only makes sense if a fifth byte has already shifted the first one out.
    /// Read as four, every symbol from the first is wrong.
    pub(super) fn new(reader: &mut ByteReader<'_>) -> Result<Self> {
        let mut code: u32 = 0;
        for _ in 0..5 {
            code = (code << 8) | u32::from(reader.u8()?);
        }
        Ok(Self {
            range: u32::MAX,
            code,
        })
    }

    /// §4's `RangeGetFreq`. Note that it *narrows* `range` as a side effect;
    /// [`RangeCoder::decode`] relies on the narrowed value.
    pub(super) fn frequency(&mut self, total: u32) -> u32 {
        self.range /= total;
        self.code / self.range
    }

    /// §4's `RangeDecode`, renormalisation included.
    pub(super) fn decode(
        &mut self,
        low: u32,
        freq: u32,
        reader: &mut ByteReader<'_>,
    ) -> Result<()> {
        // Both products are bounded by the invariant `range × total <= 2^32`
        // that `frequency` established, and `low + freq <= total`. Wrapping is
        // used rather than proved away because a corrupt stream reaches here
        // with a model that a valid one could not produce, and a debug-build
        // panic on hostile input is a bug in its own right.
        self.code = self.code.wrapping_sub(low.wrapping_mul(self.range));
        self.range = self.range.wrapping_mul(freq);
        while self.range < (1 << 24) {
            self.range <<= 8;
            self.code = (self.code << 8) | u32::from(reader.u8()?);
        }
        Ok(())
    }
}

/// §4.1's adaptive model: symbols and frequencies, kept roughly sorted by
/// frequency so the linear scan is short.
pub(super) struct Model {
    symbols: Vec<u8>,
    freq: Vec<u32>,
    total: u32,
}

/// §4.1: the frequency sum must stay under `2^16-16`, so that adding a step
/// never carries past sixteen bits.
const MAX_TOTAL: u32 = (1 << 16) - 17;

/// What a decoded symbol adds to its own frequency.
const STEP: u32 = 16;

impl Model {
    /// §4.1's `ModelCreate`: every symbol present, every frequency one.
    ///
    /// No symbol is ever allowed to reach zero — that is what keeps every
    /// symbol decodable no matter what the data did, and why
    /// [`Model::renormalise`] halves by subtracting rather than dividing.
    pub(super) fn new(n_symbols: usize) -> Self {
        Self {
            symbols: (0..n_symbols).map(|s| s as u8).collect(),
            freq: vec![1; n_symbols],
            total: n_symbols as u32,
        }
    }

    /// §4.1's `ModelRenormalise`: halve, rounding up.
    fn renormalise(&mut self) {
        self.total = 0;
        for f in self.freq.iter_mut() {
            *f -= *f / 2;
            self.total += *f;
        }
    }

    /// §4.1's `ModelDecode`: one symbol, and the model updated to match.
    pub(super) fn decode(
        &mut self,
        rc: &mut RangeCoder,
        reader: &mut ByteReader<'_>,
    ) -> Result<u8> {
        let target = rc.frequency(self.total);
        let mut acc = 0u32;
        let mut x = 0usize;
        // The specification's `while acc + F_x <= freq` has no bound, because
        // in a valid stream `freq < total` and the frequencies sum to `total`.
        // A corrupt stream breaks that and walks off the end of the array, so
        // the scan is bounded and the overrun reported.
        while x < self.freq.len() && acc + self.freq[x] <= target {
            acc += self.freq[x];
            x += 1;
        }
        if x >= self.freq.len() {
            return Err(Error::corrupt(
                reader.path(),
                reader.offset(),
                format!(
                    "an arith model selecting frequency {target} of {}, which no symbol covers",
                    self.total
                ),
            ));
        }

        rc.decode(acc, self.freq[x], reader)?;
        let symbol = self.symbols[x];

        self.freq[x] += STEP;
        self.total += STEP;
        if self.total > MAX_TOTAL {
            self.renormalise();
        }
        // Keep the commonest symbols at the front, one swap at a time. This is
        // not an optimisation that a decoder may skip: the encoder does it too,
        // and the cumulative frequencies depend on the order.
        if x > 0 && self.freq[x] > self.freq[x - 1] {
            self.freq.swap(x, x - 1);
            self.symbols.swap(x, x - 1);
        }
        Ok(symbol)
    }
}

/// The alphabet size a stream opens with: a byte, where zero means 256.
fn read_max_sym(reader: &mut ByteReader<'_>) -> Result<usize> {
    let max_sym = reader.u8()?;
    Ok(if max_sym == 0 { 256 } else { max_sym as usize })
}

/// §4.2's `DecodeOrder0`.
fn decode_order_0(reader: &mut ByteReader<'_>, len: usize) -> Result<Vec<u8>> {
    let n_symbols = read_max_sym(reader)?;
    let mut model = Model::new(n_symbols);
    let mut rc = RangeCoder::new(reader)?;
    let mut out = Vec::with_capacity(len.min(1 << 20));
    for _ in 0..len {
        out.push(model.decode(&mut rc, reader)?);
    }
    Ok(out)
}

/// §4.2's `DecodeOrder1`: one model per preceding byte.
fn decode_order_1(reader: &mut ByteReader<'_>, len: usize) -> Result<Vec<u8>> {
    let n_symbols = read_max_sym(reader)?;
    let mut models: Vec<Model> = (0..n_symbols).map(|_| Model::new(n_symbols)).collect();
    let mut rc = RangeCoder::new(reader)?;
    let mut out = Vec::with_capacity(len.min(1 << 20));
    let mut last = 0usize;
    for _ in 0..len {
        let model = models.get_mut(last).ok_or_else(|| context(reader, last))?;
        let symbol = model.decode(&mut rc, reader)?;
        out.push(symbol);
        last = symbol as usize;
    }
    Ok(out)
}

/// A symbol used as a context when the alphabet is too small to hold it.
///
/// `max_sym` sizes both the alphabet and the model array, so this cannot happen
/// in a stream whose own header is consistent — but the header is a byte a file
/// chose, and the symbol is decoded from data.
fn context(reader: &ByteReader<'_>, symbol: usize) -> Error {
    Error::corrupt(
        reader.path(),
        reader.offset(),
        format!("an arith order-1 stream reaching context {symbol}, past the alphabet it declared"),
    )
}

/// The run-length models: one per symbol for the first run, plus 256 and 257
/// for continuations.
///
/// §4.3 splits runs into parts of at most three, and a part of exactly three
/// means "another part follows". The context for that next part is 256 the
/// first time and 257 after — so a long run costs one model lookup per three
/// bytes without ever touching the literal models.
fn run_models() -> Vec<Model> {
    (0..258).map(|_| Model::new(4)).collect()
}

/// Decode one run length: §4.3's inner `while part = 3` loop.
fn decode_run(
    runs: &mut [Model],
    first_context: usize,
    rc: &mut RangeCoder,
    reader: &mut ByteReader<'_>,
) -> Result<usize> {
    let mut part = runs[first_context].decode(rc, reader)? as usize;
    let mut run = part;
    let mut context = 256;
    while part == 3 {
        part = runs[context].decode(rc, reader)? as usize;
        context = 257;
        run += part;
        if run > MAX_CODEC_LEN {
            return Err(Error::corrupt(
                reader.path(),
                reader.offset(),
                "an arith run longer than this reader's ceiling",
            ));
        }
    }
    Ok(run)
}

/// §4.3's `DecodeRLE0`.
fn decode_rle_0(reader: &mut ByteReader<'_>, len: usize) -> Result<Vec<u8>> {
    let n_symbols = read_max_sym(reader)?;
    let mut literals = Model::new(n_symbols);
    let mut runs = run_models();
    let mut rc = RangeCoder::new(reader)?;

    let mut out = Vec::with_capacity(len.min(1 << 20));
    while out.len() < len {
        let symbol = literals.decode(&mut rc, reader)?;
        let run = decode_run(&mut runs, symbol as usize, &mut rc, reader)?;
        // A run may name more bytes than are left; the extra are dropped
        // rather than treated as corruption, because the length that governs
        // is the one the stream declared.
        let wanted = (run + 1).min(len - out.len());
        out.resize(out.len() + wanted, symbol);
    }
    Ok(out)
}

/// §4.3's `DecodeRLE1`: as `DecodeRLE0`, with the previous literal choosing the
/// literal model. The run models are not contextualised by it.
fn decode_rle_1(reader: &mut ByteReader<'_>, len: usize) -> Result<Vec<u8>> {
    let n_symbols = read_max_sym(reader)?;
    let mut literals: Vec<Model> = (0..n_symbols).map(|_| Model::new(n_symbols)).collect();
    let mut runs = run_models();
    let mut rc = RangeCoder::new(reader)?;

    let mut out = Vec::with_capacity(len.min(1 << 20));
    let mut last = 0usize;
    while out.len() < len {
        let model = literals
            .get_mut(last)
            .ok_or_else(|| context(reader, last))?;
        let symbol = model.decode(&mut rc, reader)?;
        last = symbol as usize;
        let run = decode_run(&mut runs, symbol as usize, &mut rc, reader)?;
        let wanted = (run + 1).min(len - out.len());
        out.resize(out.len() + wanted, symbol);
    }
    Ok(out)
}

/// The encoding halves of [`RangeCoder`] and [`Model`], which exist only so
/// that the decoders above round-trip against something rather than against
/// themselves. Shared with [`super::fqzcomp`], whose stream is §4's coder
/// driving §6's models.
#[cfg(test)]
pub(crate) mod testing {
    use super::{MAX_TOTAL, STEP};

    /// §4's `RangeEncode`, `RangeShiftLow`, `RangeEncodeStart` and
    /// `RangeEncodeEnd`, which exist only to make the round trips below real.
    ///
    /// The carry handling is the whole reason the encoder is longer than the
    /// decoder: `low` and `low + range` can straddle a byte boundary
    /// (0x37ffba20 to 0x38000034 is §4's example), and which of 0x37 or 0x38
    /// gets written is not known until the range has narrowed further. The
    /// pending bytes are counted rather than buffered.
    pub(crate) struct RangeEncoder {
        low: u64,
        range: u32,
        cache: u8,
        ff_num: u64,
        out: Vec<u8>,
    }

    impl RangeEncoder {
        pub(crate) fn new() -> Self {
            Self {
                low: 0,
                range: u32::MAX,
                cache: 0,
                ff_num: 0,
                out: Vec::new(),
            }
        }

        /// §4's `RangeShiftLow`.
        ///
        /// `low` is held in a `u64` so the carry out of bit 32 is a value to
        /// test rather than a flag to track separately, which is the same
        /// thing the specification's `if low < old_low` is detecting.
        pub(crate) fn shift_low(&mut self) {
            if self.low < 0xff00_0000 || self.low > 0xffff_ffff {
                let carry = (self.low >> 32) as u8;
                // The very first call writes `cache`, which is still zero —
                // and that leading zero is not spurious. It is the byte the
                // decoder's five-byte prime shifts straight back out again
                // with its `code AND 2^32-1`. Suppress it and every symbol
                // decodes one byte out of step.
                self.out.push(self.cache.wrapping_add(carry));
                while self.ff_num > 0 {
                    self.out.push(0xffu8.wrapping_add(carry));
                    self.ff_num -= 1;
                }
                self.cache = (self.low >> 24) as u8;
            } else {
                self.ff_num += 1;
            }
            self.low = (self.low << 8) & 0xffff_ffff;
        }

        pub(crate) fn encode(&mut self, low: u32, freq: u32, total: u32) {
            self.range /= total;
            self.low += u64::from(low) * u64::from(self.range);
            self.range *= freq;
            while self.range < (1 << 24) {
                self.range <<= 8;
                self.shift_low();
            }
        }

        /// §4's `RangeEncodeEnd`, plus the leading byte the decoder's
        /// five-byte prime expects.
        pub(crate) fn finish(mut self) -> Vec<u8> {
            for _ in 0..5 {
                self.shift_low();
            }
            self.out
        }
    }

    /// The encoding half of [`Model`], kept beside it for the same reason.
    pub(crate) struct ModelEncoder {
        symbols: Vec<u8>,
        freq: Vec<u32>,
        total: u32,
    }

    impl ModelEncoder {
        pub(crate) fn new(n_symbols: usize) -> Self {
            Self {
                symbols: (0..n_symbols).map(|s| s as u8).collect(),
                freq: vec![1; n_symbols],
                total: n_symbols as u32,
            }
        }

        pub(crate) fn encode(&mut self, rc: &mut RangeEncoder, symbol: u8) {
            let mut acc = 0u32;
            let mut x = 0usize;
            while self.symbols[x] != symbol {
                acc += self.freq[x];
                x += 1;
            }
            rc.encode(acc, self.freq[x], self.total);

            self.freq[x] += STEP;
            self.total += STEP;
            if self.total > MAX_TOTAL {
                self.total = 0;
                for f in self.freq.iter_mut() {
                    *f -= *f / 2;
                    self.total += *f;
                }
            }
            if x > 0 && self.freq[x] > self.freq[x - 1] {
                self.freq.swap(x, x - 1);
                self.symbols.swap(x, x - 1);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::testing::{ModelEncoder, RangeEncoder};
    use super::*;

    fn alphabet(data: &[u8]) -> usize {
        data.iter().map(|b| *b as usize + 1).max().unwrap_or(1)
    }

    fn encode_order_0(data: &[u8]) -> Vec<u8> {
        let n = alphabet(data);
        let mut model = ModelEncoder::new(n);
        let mut rc = RangeEncoder::new();
        for byte in data {
            model.encode(&mut rc, *byte);
        }
        let mut out = vec![(n & 0xff) as u8];
        out.extend_from_slice(&rc.finish());
        out
    }

    fn encode_order_1(data: &[u8]) -> Vec<u8> {
        let n = alphabet(data);
        let mut models: Vec<ModelEncoder> = (0..n).map(|_| ModelEncoder::new(n)).collect();
        let mut rc = RangeEncoder::new();
        let mut last = 0usize;
        for byte in data {
            models[last].encode(&mut rc, *byte);
            last = *byte as usize;
        }
        let mut out = vec![(n & 0xff) as u8];
        out.extend_from_slice(&rc.finish());
        out
    }

    /// Split `data` into the literal-and-run pairs §4.3 encodes.
    fn runs_of(data: &[u8]) -> Vec<(u8, usize)> {
        let mut out = Vec::new();
        let mut i = 0;
        while i < data.len() {
            let symbol = data[i];
            let mut run = 0;
            while i + run + 1 < data.len() && data[i + run + 1] == symbol {
                run += 1;
            }
            out.push((symbol, run));
            i += run + 1;
        }
        out
    }

    fn encode_run(rc: &mut RangeEncoder, runs: &mut [ModelEncoder], first: usize, mut run: usize) {
        let mut context = first;
        loop {
            let part = run.min(3);
            runs[context].encode(rc, part as u8);
            run -= part;
            if part < 3 {
                return;
            }
            context = if context == first { 256 } else { 257 };
        }
    }

    fn encode_rle(data: &[u8], order_1: bool) -> Vec<u8> {
        let n = alphabet(data);
        let mut literals: Vec<ModelEncoder> = if order_1 {
            (0..n).map(|_| ModelEncoder::new(n)).collect()
        } else {
            vec![ModelEncoder::new(n)]
        };
        let mut runs: Vec<ModelEncoder> = (0..258).map(|_| ModelEncoder::new(4)).collect();
        let mut rc = RangeEncoder::new();
        let mut last = 0usize;
        for (symbol, run) in runs_of(data) {
            let index = if order_1 { last } else { 0 };
            literals[index].encode(&mut rc, symbol);
            last = symbol as usize;
            encode_run(&mut rc, &mut runs, symbol as usize, run);
        }
        let mut out = vec![(n & 0xff) as u8];
        out.extend_from_slice(&rc.finish());
        out
    }

    /// Wrap an entropy-coded body in the flag byte and length §4.3 expects.
    fn wrap(flags: u8, len: usize, body: &[u8]) -> Vec<u8> {
        let mut out = vec![flags];
        let mut value = len as u32;
        let mut seven = Vec::new();
        loop {
            seven.push((value & 0x7f) as u8);
            value >>= 7;
            if value == 0 {
                break;
            }
        }
        for (i, byte) in seven.iter().enumerate().rev() {
            out.push(if i == 0 { *byte } else { byte | 0x80 });
        }
        out.extend_from_slice(body);
        out
    }

    fn roundtrip(data: &[u8], flags: u8) {
        let body = match (flags & flag::RLE != 0, flags & flag::ORDER != 0) {
            (false, false) => encode_order_0(data),
            (false, true) => encode_order_1(data),
            (true, order_1) => encode_rle(data, order_1),
        };
        let stream = wrap(flags, data.len(), &body);
        let decoded = decode(&stream, "test", 0)
            .unwrap_or_else(|e| panic!("flags {flags}, {} bytes: {e}", data.len()));
        assert_eq!(decoded, data, "flags {flags}, {} bytes", data.len());
    }

    #[test]
    fn order_0_round_trips_text() {
        roundtrip(&b"abracadabra".repeat(30), 0);
    }

    #[test]
    fn order_1_round_trips_text() {
        roundtrip(&b"abracadabra".repeat(30), flag::ORDER);
    }

    #[test]
    fn run_length_round_trips_at_both_orders() {
        let data = b"ABBCCCCDDDDD".repeat(10);
        roundtrip(&data, flag::RLE);
        roundtrip(&data, flag::RLE | flag::ORDER);
    }

    /// §4.3's own worked example, which is also the one that catches the
    /// `i <- run+1` misreading: decoded that way it never gets past the
    /// second run.
    #[test]
    fn the_specifications_run_length_example_decodes_to_twelve_bytes() {
        let data = b"ABBCCCCDDDDD";
        assert_eq!(
            runs_of(data),
            vec![(b'A', 0), (b'B', 1), (b'C', 3), (b'D', 4)]
        );
        roundtrip(data, flag::RLE);
    }

    #[test]
    fn a_run_longer_than_three_is_split_into_continuations() {
        // 3 is the largest part, so a run of 300 is one first part and a
        // hundred continuations — the path through contexts 256 and 257.
        let data = vec![b'Z'; 300];
        roundtrip(&data, flag::RLE);
        roundtrip(&data, flag::RLE | flag::ORDER);
    }

    #[test]
    fn the_whole_byte_alphabet_round_trips() {
        // 256 symbols, so `max_sym` is written as zero and read back as 256.
        let data: Vec<u8> = (0..=255u8).chain((0..=255u8).rev()).collect();
        roundtrip(&data, 0);
        roundtrip(&data, flag::ORDER);
    }

    #[test]
    fn a_stream_long_enough_to_renormalise_its_model_round_trips() {
        // Each symbol adds 16 to the total, so about four thousand symbols
        // cross `MAX_TOTAL` and halve every frequency. Both sides must do it
        // at exactly the same symbol.
        let data: Vec<u8> = (0..20_000).map(|i| b"acgt"[i % 4]).collect();
        roundtrip(&data, 0);
        roundtrip(&data, flag::ORDER);
    }

    #[test]
    fn a_single_byte_and_an_empty_stream_round_trip() {
        roundtrip(b"", 0);
        roundtrip(b"Q", 0);
        roundtrip(b"Q", flag::ORDER);
        roundtrip(b"Q", flag::RLE);
    }

    #[test]
    fn the_cat_flag_gives_the_bytes_back_verbatim() {
        let stream = wrap(flag::CAT, 5, b"hello");
        assert_eq!(decode(&stream, "test", 0).expect("cat"), b"hello");
    }

    #[test]
    fn a_stripe_interleaves_its_sub_streams() {
        // Four sub-streams of two bytes each, interleaved back to eight.
        let subs: Vec<Vec<u8>> = (0..4)
            .map(|j| {
                let body = encode_order_0(&[j * 10, j * 10 + 1]);
                let mut sub = vec![flag::NO_SIZE];
                sub.extend_from_slice(&body);
                sub
            })
            .collect();
        let mut stream = wrap(flag::STRIPE, 8, &[]);
        stream.push(4);
        for sub in &subs {
            stream.push(sub.len() as u8);
        }
        for sub in &subs {
            stream.extend_from_slice(sub);
        }
        assert_eq!(
            decode(&stream, "test", 0).expect("stripe"),
            vec![0, 10, 20, 30, 1, 11, 21, 31]
        );
    }

    #[test]
    fn a_model_selecting_a_frequency_no_symbol_covers_is_refused() {
        // The bound the specification's unbounded `while` leaves off. Reached
        // by feeding a stream that primes the coder with all-ones, which puts
        // `code` far past what the four-symbol model covers.
        let mut stream = wrap(flag::RLE, 64, &[4u8]);
        stream.extend_from_slice(&[0xff; 32]);
        let error = decode(&stream, "test", 0).expect_err("no symbol covers it");
        assert!(
            error.to_string().contains("which no symbol covers"),
            "{error}"
        );
    }

    #[test]
    fn every_prefix_of_a_real_stream_fails_without_panicking() {
        let stream = wrap(
            flag::ORDER,
            330,
            &encode_order_1(&b"abracadabra".repeat(30)),
        );
        for cut in 0..stream.len() {
            let _ = decode(&stream[..cut], "test", 0);
        }
        for byte in 0..=255u8 {
            let mut damaged = stream.clone();
            damaged[0] = byte;
            let _ = decode(&damaged, "test", 0);
        }
    }
}