manifold/
mix_coder.rs

1//! MNF13-R5 — the dual-timescale adaptive mix coder (backend id 4).
2//!
3//! Per-context FAST (halving cap 4,096) and SLOW (cap 65,536)
4//! adaptive estimators over the full 256-symbol alphabet, mixed by a
5//! log-space EWA weight updated per symbol from the coded symbol —
6//! identical evolution on both sides (zero model transport; the
7//! wire = payload bytes only). ConstricTON 0.5's stream range coder
8//! carries the fixed-point probabilities (2^24 scale, no fp in the
9//! wire data path). The exact-inverse contract is asserted by the
10//! conformance suite (`tests/mnf8_conformance.rs`) and the corpus
11//! gate.
12//!
13//! Wire (v1.13.0): MNF8 backend id 4. The payload the backend field
14//! addresses = the mix-coded residual byte stream in the file's own
15//! coded order; every context key recomputes from already-coded
16//! bytes (the previous coded residual byte, bucketed to 8 keys), so
17//! the decoder needs no side tables and rejects malformed inputs
18//! with errors (never panics).
19//!
20//! Measured (docs/mnf13-r5.md): −1.80% complete corpus at the v1.12
21//! pick level, wins 19/19 photographic record files, zero
22//! regressions elsewhere (the pick keeps every prior arm).
23
24use constriction::stream::{
25    model::ContiguousCategoricalEntropyModel, queue::DefaultRangeDecoder,
26    queue::DefaultRangeEncoder, Decode, Encode,
27};
28
29/// Fixed-point probability scale (2^24).
30const SCALE: u64 = 1 << 24;
31/// Fast estimator's halving cap.
32pub const MIX_FAST_CAP: u64 = 4096;
33/// Slow estimator's halving cap.
34pub const MIX_SLOW_CAP: u64 = 65536;
35/// EWA learning rate (log space).
36const EWA_LR: f64 = 0.15;
37/// Per-symbol count increment.
38const COUNT_INC: u64 = 32;
39
40/// The previous-coded-byte context: 8 magnitude buckets of the
41/// previous coded byte (0; 1-2; 3-5; 6-11; 12-24; 25-48; 49-96; 97+).
42#[inline]
43pub fn mix_ctx_bucket(prev: u8) -> u8 {
44    match prev {
45        0 => 0,
46        1..=2 => 1,
47        3..=5 => 2,
48        6..=11 => 3,
49        12..=24 => 4,
50        25..=48 => 5,
51        49..=96 => 6,
52        _ => 7,
53    }
54}
55
56/// One context's dual estimator.
57#[derive(Clone)]
58struct MixCtx {
59    fast: Vec<u64>,
60    slow: Vec<u64>,
61    log_w: f64,
62}
63
64impl MixCtx {
65    fn new() -> Self {
66        Self {
67            fast: vec![1; 256],
68            slow: vec![1; 256],
69            log_w: 0.0,
70        }
71    }
72
73    /// Fixed-point probability vector over the FULL alphabet; every
74    /// symbol >= 1 (all must stay decodable); total exactly SCALE.
75    fn probs(&self) -> Vec<u32> {
76        let tf = self.fast.iter().sum::<u64>() as f64;
77        let ts = self.slow.iter().sum::<u64>() as f64;
78        let wf = 1.0 / (1.0 + (-self.log_w).exp());
79        let mut p: Vec<u64> = self
80            .fast
81            .iter()
82            .zip(&self.slow)
83            .map(|(&cf, &cs)| {
84                ((wf * (cf as f64 / tf) + (1.0 - wf) * (cs as f64 / ts)) * SCALE as f64) as u64
85            })
86            .collect();
87        // rebalance: remainder to slot 0; every zero slot <= 1 stolen
88        // from the densest entry (two passes, no double borrow)
89        let sum: u64 = p.iter().sum();
90        p[0] += SCALE - sum;
91        let mut dense = 0usize;
92        for (i, &v) in p.iter().enumerate() {
93            if v > p[dense] {
94                dense = i;
95            }
96        }
97        let zeros = p.iter().filter(|&&v| v == 0).count();
98        p[dense] = p[dense].max(1 + zeros as u64);
99        for v in p.iter_mut() {
100            if *v == 0 {
101                *v = 1;
102            }
103        }
104        p.into_iter().map(|v| v as u32).collect()
105    }
106
107    fn model(&self) -> Option<ContiguousCategoricalEntropyModel<u32, Vec<u32>, 24>> {
108        ContiguousCategoricalEntropyModel::<u32, Vec<u32>, 24>::from_nonzero_fixed_point_probabilities(
109            self.probs(),
110            false,
111        )
112        .ok()
113    }
114
115    fn step(&mut self, s: u8) {
116        let si = usize::from(s);
117        let tf = self.fast.iter().sum::<u64>() as f64;
118        let ts = self.slow.iter().sum::<u64>() as f64;
119        let pf = (self.fast[si] as f64 / tf).max(1e-9);
120        let ps = (self.slow[si] as f64 / ts).max(1e-9);
121        self.log_w = (self.log_w + EWA_LR * (pf.ln() - ps.ln())).clamp(-20.0, 20.0);
122        self.fast[si] += COUNT_INC;
123        self.slow[si] += COUNT_INC;
124        if self.fast.iter().sum::<u64>() > MIX_FAST_CAP {
125            for c in &mut self.fast {
126                *c = (*c + 1) >> 1;
127            }
128        }
129        if self.slow.iter().sum::<u64>() > MIX_SLOW_CAP {
130            for c in &mut self.slow {
131                *c = (*c + 1) >> 1;
132            }
133        }
134    }
135}
136
137/// The mix coder: encode `data` (the residual bytes in coded order).
138/// Zero transport; the model evolves from the bytes themselves.
139pub fn mix_encode(data: &[u8]) -> Vec<u8> {
140    let mut ctxs: Vec<MixCtx> = (0..8).map(|_| MixCtx::new()).collect();
141    let mut enc = DefaultRangeEncoder::new();
142    let mut prev = 0u8;
143    for &b in data {
144        let c = mix_ctx_bucket(prev);
145        let m = ctxs[usize::from(c)]
146            .model()
147            .expect("mix model with all-nonzero probabilities is always buildable");
148        enc.encode_symbols(std::iter::once((usize::from(b), &m)))
149            .expect("mix encode symbol");
150        ctxs[usize::from(c)].step(b);
151        prev = b;
152    }
153    let compressed = enc.into_compressed().expect("mix seal");
154    // The wire = [u32 stream_len][LE words]; the stream length is
155    // charged transport (honest) — the range coder cannot recover it
156    // from the frame alone.
157    let mut out = Vec::with_capacity(compressed.len() * 4 + 4);
158    out.extend_from_slice(
159        &u32::try_from(data.len())
160            .expect("stream len fits u32")
161            .to_le_bytes(),
162    );
163    for w in compressed {
164        out.extend_from_slice(&w.to_le_bytes());
165    }
166    out
167}
168
169/// The inverse: decode the wire back to its stream bytes. Errors,
170/// never panics, on malformed input.
171pub fn mix_decode(data: &[u8], limit: usize) -> Result<Vec<u8>, crate::error::Error> {
172    // payload = [u32 stream_len][LE words...]
173    if data.len() < 4 || !(data.len() - 4).is_multiple_of(4) {
174        return Err(crate::error::Error::fmt_msg("mix payload not word-aligned"));
175    }
176    let stream_len = usize::try_from(u32::from_le_bytes(data[..4].try_into().expect("4 bytes")))
177        .map_err(|_| crate::error::Error::fmt_msg("mix stream length"))?;
178    if stream_len > limit {
179        return Err(crate::error::Error::fmt_msg("bomb"));
180    }
181    let mut words = Vec::with_capacity((data.len() - 4) / 4);
182    for chunk in data[4..].chunks_exact(4) {
183        words.push(u32::from_le_bytes(chunk.try_into().expect("4 bytes")));
184    }
185    let mut dec = DefaultRangeDecoder::from_compressed(words)
186        .map_err(|e| crate::error::Error::fmt_msg(format!("mix decoder open: {e:?}")))?;
187    let mut ctxs: Vec<MixCtx> = (0..8).map(|_| MixCtx::new()).collect();
188    let mut out = Vec::with_capacity(stream_len);
189    let mut prev = 0u8;
190    for _i in 0..stream_len {
191        let c = usize::from(mix_ctx_bucket(prev));
192        let m = ctxs[c]
193            .model()
194            .ok_or_else(|| crate::error::Error::fmt_msg("mix model build failed"))?;
195        let s = dec
196            .decode_symbols(std::iter::once(&m))
197            .next()
198            .ok_or_else(|| crate::error::Error::fmt_msg("mix stream exhausted"))?
199            .map_err(|e| crate::error::Error::fmt_msg(format!("mix decode symbol: {e:?}")))?;
200        let s = u8::try_from(s)
201            .map_err(|_| crate::error::Error::fmt_msg("mix symbol out of byte range"))?;
202        ctxs[c].step(s);
203        out.push(s);
204        prev = s;
205    }
206    Ok(out)
207}
manifold/mix_coder.rs

manifold/
mix_coder.rs
