manifold/
tokens.rs

1// LZ77-2D token engine (MNF8 FLAG_TOKENS payload).
2//
3// The retained verdict of docs/mnf9-engine-ladder-probe.md (arm B, 2026-10-27;
4// Rust port measured in docs/mnf9-token-arm.md): the payload is a token
5// stream over the image-wide MED residual plane instead of per-tile mode
6// records. Tokens crush repeating residual planes (gradient −77%, solid
7// −81% vs the plane's zlib) and lose on noise-dominated ones, so the
8// encoder only emits the flag when it measures smaller (rate-aware pick,
9// docs/mnf8-adr-003-tokens.md).
10//
11// Wire grammar (v1.7.x; tags are self-describing per token):
12//   tag 0 literal: 1 + 3 B  (one residual pixel)
13//   tag 1 match:   1 + 2 + 2 + 1 B  (dx u16 le, dy u16 le, len px, len >= 7)
14//   tag 2 near:    1 + 1 + 1 + 1 B  (dx u8, dy u8, len px, len >= 7)
15// dist = dy*width + dx pixels; a match's source is strictly earlier in the
16// plane and copies are byte-forward (overlapping self-referential runs exact).
17// Tag 2 (ADR-005) encodes any match whose dx and dy both fit a byte — the
18// address histogram measured near-universal (docs/mnf9-erdos-probe.md:
19// dy fit u8 on every corpus match) — saving 2 B per near match with NO
20// per-file flag: the decoder dispatches by tag. Old decoders (1.6/1.7.0
21// token walk) reject tag 2 as unknown; new decoders read all three.
22// On equal match length the matcher prefers the NEARER candidate
23// (near-encodable) — a pure encoder-policy win at zero decode cost.
24// Byte cost model: every arm is re-costed through the SAME container coder
25// as the record path (backend_compress), per-file selection decides.
26
27use crate::error::Error;
28
29/// Match minimum length in pixels.
30pub const MIN_MATCH_PX: usize = 7;
31/// Match search window in pixels (the measured arm-B window).
32pub const WINDOW_PX: usize = 1 << 24;
33/// Wire tag: one residual pixel follows (3 bytes).
34pub const TAG_LITERAL: u8 = 0;
35/// Wire tag: dx(2) dy(2) len(1) follow; copies len pixels from dist back.
36pub const TAG_MATCH: u8 = 1;
37/// Wire tag (ADR-005): dx(1) dy(1) len(1) follow; the narrow-coordinate
38/// match — legal iff dx < 256 AND dy < 256.
39pub const TAG_NEAR: u8 = 2;
40/// Wire length field holds a byte count capped here (= 85 px; a longer run
41/// simply emits consecutive tokens).
42const MAX_MATCH_BYTES: usize = 255;
43/// Candidate scans per position before the matcher gives up (probe cap).
44/// Deep-chain candidate cap (ADR-005 era): the pick measures BOTH this
45/// arm and the shallow v1.7 arm (cap 16) and keeps the smaller wire.
46pub const MAX_CANDIDATES: usize = 1024;
47
48/// Token counts for one encoded plane.
49#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
50pub struct TokenStats {
51    /// Tag-0 literals emitted.
52    pub literals: u64,
53    /// Tag-1/2 matches emitted (all matches).
54    pub matches: u64,
55    /// Tag-2 near matches (narrow-coordinate, 4 B form).
56    pub near_matches: u64,
57}
58
59#[inline]
60fn key3(b: &[u8]) -> u32 {
61    u32::from(b[0]) | (u32::from(b[1]) << 8) | (u32::from(b[2]) << 16)
62}
63
64/// Parse the residual plane (row-major, 3 B/px) into the token wire.
65/// Matcher semantics are the measured arm-B ones: 3-byte pixel-key hash
66/// chains, newest-first scan, bounded candidates, min match 7 px,
67/// byte-forward (overlapping) copies. Candidates whose 2D (dx, dy) split
68/// does not fit the wire's u16 fields are skipped. Matches whose (dx, dy)
69/// both fit a byte emit TAG_NEAR (4 B vs 6 B, ADR-005); on equal length
70/// the matcher prefers the NEARER (near-encodable) candidate.
71///
72/// ponytail: O(n * cap) match scan with per-position table inserts; cap =
73/// MAX_CANDIDATES (ADR-006: the pick also measures the shallow cap-16
74/// arm). Revisit only if encode throughput on multi-megapixel images
75/// becomes a complaint.
76pub fn encode_plane(res: &[u8], w: usize, h: usize) -> Result<(Vec<u8>, TokenStats), Error> {
77    encode_plane_cap(res, w, h, MAX_CANDIDATES)
78}
79
80/// Same matcher with an explicit candidate cap (the pick loop measures the
81/// shallow and deep arms; cap 16 = the v1.7 measured ladder arm).
82pub fn encode_plane_cap(
83    res: &[u8],
84    w: usize,
85    h: usize,
86    cap: usize,
87) -> Result<(Vec<u8>, TokenStats), Error> {
88    let npx = w
89        .checked_mul(h)
90        .ok_or_else(|| Error::fmt_msg("dims overflow"))?;
91    if res.len() != npx * 3 {
92        return Err(Error::fmt_msg("token plane size mismatch"));
93    }
94    let mut wire = Vec::with_capacity(res.len() / 2);
95    let mut table: std::collections::HashMap<u32, Vec<u32>> = std::collections::HashMap::new();
96    let mut stats = TokenStats::default();
97    let mut pos: usize = 0;
98    while pos < npx {
99        let key = key3(&res[pos * 3..pos * 3 + 3]);
100        let mut best_len = 0usize;
101        let mut best_dist = 0usize;
102        let mut ncand = 0usize;
103        if let Some(chain) = table.get(&key) {
104            for &q in chain.iter().rev() {
105                let q = q as usize;
106                let dist = pos - q;
107                if dist > WINDOW_PX || ncand >= cap {
108                    break;
109                }
110                ncand += 1;
111                let mut l = 0usize;
112                while l < MAX_MATCH_BYTES
113                    && pos * 3 + l < res.len()
114                    && res[q * 3 + l] == res[pos * 3 + l]
115                {
116                    l += 1;
117                }
118                let lpx = l / 3;
119                if lpx >= MIN_MATCH_PX {
120                    let (dx, dy) = (dist % w, dist / w);
121                    if dx <= 0xFFFF && dy <= 0xFFFF {
122                        // ADR-005: prefer near-encodable candidates on equal
123                        // length (strictly better wire, no decode cost); a
124                        // longer match always wins regardless of distance.
125                        let near = dx < 256 && dy < 256;
126                        let cur_near = best_len > 0 && {
127                            let (cdx, cdy) = (best_dist % w, best_dist / w);
128                            cdx < 256 && cdy < 256
129                        };
130                        if lpx > best_len || (lpx == best_len && near && !cur_near) {
131                            best_len = lpx;
132                            best_dist = dist;
133                        }
134                    }
135                }
136            }
137        }
138        if best_len >= MIN_MATCH_PX {
139            let (dx, dy) = (best_dist % w, best_dist / w);
140            if dx < 256 && dy < 256 {
141                wire.push(TAG_NEAR);
142                wire.push(dx as u8);
143                wire.push(dy as u8);
144                wire.push(best_len as u8);
145                stats.near_matches += 1;
146            } else {
147                wire.push(TAG_MATCH);
148                wire.extend_from_slice(&(dx as u16).to_le_bytes());
149                wire.extend_from_slice(&(dy as u16).to_le_bytes());
150                wire.push(best_len as u8);
151            }
152            for p in pos..pos + best_len {
153                let k = key3(&res[p * 3..p * 3 + 3]);
154                table.entry(k).or_default().push(p as u32);
155            }
156            pos += best_len;
157            stats.matches += 1;
158        } else {
159            wire.push(TAG_LITERAL);
160            wire.extend_from_slice(&res[pos * 3..pos * 3 + 3]);
161            table.entry(key).or_default().push(pos as u32);
162            pos += 1;
163            stats.literals += 1;
164        }
165    }
166    Ok((wire, stats))
167}
168
169/// Exact inverse of [`encode_plane`]: rebuild the residual plane from the
170/// wire. Malformed wires are errors, never panics: unknown tags,
171/// truncation, below-minimum matches, out-of-range match sources, and any
172/// wire decoding to the wrong plane size.
173pub fn decode_plane(wire: &[u8], w: usize, h: usize) -> Result<Vec<u8>, Error> {
174    let npx = w
175        .checked_mul(h)
176        .ok_or_else(|| Error::fmt_msg("dims overflow"))?;
177    let mut out: Vec<u8> = Vec::with_capacity(npx * 3);
178    let mut c = 0usize;
179    while c < wire.len() {
180        match wire[c] {
181            TAG_LITERAL => {
182                if c + 4 > wire.len() {
183                    return Err(Error::fmt_msg("token wire: truncated literal"));
184                }
185                out.extend_from_slice(&wire[c + 1..c + 4]);
186                c += 4;
187            }
188            TAG_MATCH => {
189                if c + 6 > wire.len() {
190                    return Err(Error::fmt_msg("token wire: truncated match"));
191                }
192                let dx = u16::from_le_bytes([wire[c + 1], wire[c + 2]]) as usize;
193                let dy = u16::from_le_bytes([wire[c + 3], wire[c + 4]]) as usize;
194                let len = wire[c + 5] as usize;
195                c += 6;
196                if len < MIN_MATCH_PX {
197                    return Err(Error::fmt_msg("token wire: match below minimum"));
198                }
199                let p = out.len() / 3;
200                let dist = dy * w + dx;
201                if dist == 0 || dist > p {
202                    return Err(Error::fmt_msg("token wire: match source out of range"));
203                }
204                if out.len() + len * 3 > npx * 3 {
205                    return Err(Error::fmt_msg("token wire: match overruns plane"));
206                }
207                let q = (p - dist) * 3;
208                // byte-forward copy: overlapping matches (len > dist) are the
209                // LZ77 self-referential run and are exact here.
210                for k in 0..len * 3 {
211                    let b = out[q + k];
212                    out.push(b);
213                }
214            }
215            TAG_NEAR => {
216                if c + 4 > wire.len() {
217                    return Err(Error::fmt_msg("token wire: truncated near match"));
218                }
219                let dx = wire[c + 1] as usize;
220                let dy = wire[c + 2] as usize;
221                let len = wire[c + 3] as usize;
222                c += 4;
223                if len < MIN_MATCH_PX {
224                    return Err(Error::fmt_msg("token wire: near match below minimum"));
225                }
226                let p = out.len() / 3;
227                let dist = dy * w + dx;
228                if dist == 0 || dist > p {
229                    return Err(Error::fmt_msg("token wire: near match source out of range"));
230                }
231                if out.len() + len * 3 > npx * 3 {
232                    return Err(Error::fmt_msg("token wire: near match overruns plane"));
233                }
234                let q = (p - dist) * 3;
235                for k in 0..len * 3 {
236                    let b = out[q + k];
237                    out.push(b);
238                }
239            }
240            _ => return Err(Error::fmt_msg("token wire: unknown tag")),
241        }
242    }
243    if out.len() != npx * 3 {
244        return Err(Error::fmt_msg("token wire: plane size mismatch"));
245    }
246    Ok(out)
247}
248#[test]
249fn near_matches_fire_and_roundtrip_exactly() {
250    // ADR-005: planted repeats at near offsets (dx,dy both < 256) emit
251    // the 4-B tag-2 form; far offsets stay tag-1; both decode exact.
252    let (w, h) = (300usize, 200usize);
253    let mut plane = vec![0u8; w * h * 3];
254    for i in 0..w * h {
255        plane[i * 3] = (i % 251) as u8;
256        plane[i * 3 + 1] = ((i * 7) % 251) as u8;
257        plane[i * 3 + 2] = (i * 11 % 251) as u8;
258    }
259    // near repeat: dx = 10, dy = 5 (both < 256). Blocks LAST so no later
260    // filler pass destroys them. block = 256 FULL pixels (768 bytes).
261    let block: Vec<u8> = (0..16 * 16 * 3).map(|k| (k * 13 % 251) as u8).collect();
262    for (bx, by) in [(10usize, 5usize), (20usize, 10usize), (250usize, 30usize)] {
263        for y in 0..16 {
264            for x in 0..16 {
265                let dst = ((by + y) * w + bx + x) * 3;
266                plane[dst..dst + 3].copy_from_slice(&block[(y * 16 + x) * 3..(y * 16 + x) * 3 + 3]);
267            }
268        }
269    }
270    let (wire, st) = encode_plane(&plane, w, h).expect("encode");
271    assert!(st.near_matches >= 2, "near repeats must fire tag 2: {st:?}");
272    let back = decode_plane(&wire, w, h).expect("decode");
273    assert_eq!(back, plane, "near+far mixed wire exact");
274}
275
276#[test]
277fn near_preferred_on_equal_length() {
278    // ADR-005 matcher policy: with two equal-length candidates (one
279    // near-encodable, one far), the wire must take the 4-B form.
280    let (w, h) = (600usize, 60usize);
281    let mut plane = vec![0u8; w * h * 3];
282    for i in 0..w * h {
283        plane[i * 3] = (i % 251) as u8;
284        plane[i * 3 + 1] = ((i * 7) % 251) as u8;
285        plane[i * 3 + 2] = ((i * 3) % 251) as u8;
286    }
287    // candidate A (far): dy = 0, dx = 500 — 16-px identical block at
288    // column 500, row 0.
289    let block: Vec<u8> = (0..16 * 16 * 3).map(|k| (k * 13 % 251) as u8).collect();
290    for y in 0..16 {
291        for x in 0..16 {
292            let dst = (y * w + 500 + x) * 3;
293            plane[dst..dst + 3].copy_from_slice(&block[(y * 16 + x) * 3..(y * 16 + x) * 3 + 3]);
294        }
295    }
296    // candidate B (near): SAME block at dx = 30, dy = 20 (dist = 30 + 20*w
297    // — near-encodable), visited AFTER A's chain entry (chain is
298    // newest-first; B at a LATER position means its insert comes later).
299    for y in 0..16 {
300        for x in 0..16 {
301            let dst = ((20 + y) * w + 30 + x) * 3;
302            plane[dst..dst + 3].copy_from_slice(&block[(y * 16 + x) * 3..(y * 16 + x) * 3 + 3]);
303        }
304    }
305    // trigger pixel: first position after both blocks — place the SAME
306    // 16-block at (60, 40) — near from B's tail? simpler: assert the
307    // wire contains >= 1 tag-2 byte sequence for the B copy.
308    for y in 0..16 {
309        for x in 0..16 {
310            let dst = ((40 + y) * w + 60 + x) * 3;
311            plane[dst..dst + 3].copy_from_slice(&block[(y * 16 + x) * 3..(y * 16 + x) * 3 + 3]);
312        }
313    }
314    let (wire, st) = encode_plane(&plane, w, h).expect("encode");
315    assert!(
316        st.near_matches >= 1,
317        "near candidates must emit tag 2: {st:?}"
318    );
319    let back = decode_plane(&wire, w, h).expect("decode");
320    assert_eq!(back, plane);
321}
322
323#[test]
324fn near_malformed_rejected() {
325    let (w, h) = (64usize, 8usize);
326    let plane: Vec<u8> = (0..w * h * 3).map(|k| (k % 251) as u8).collect();
327    let (wire, _) = encode_plane(&plane, w, h).expect("encode");
328    // truncated near token
329    let mut bad = wire.clone();
330    bad.push(TAG_NEAR);
331    bad.push(5);
332    bad.push(1);
333    // missing len
334    assert!(decode_plane(&bad, w, h).is_err());
335    bad.push(7);
336    assert!(decode_plane(&bad, w, h).is_err()); // overruns plane
337                                                // below-minimum len in a near token
338    assert!(decode_plane(
339        &{
340            let mut v = wire.clone();
341            v.push(TAG_NEAR);
342            v.extend_from_slice(&[5, 1, 3]);
343            v
344        },
345        w,
346        h
347    )
348    .is_err());
349}
manifold/tokens.rs

manifold/
tokens.rs
