vole_document/encode/
candidates.rs

1//! Candidate generators.
2//!
3//! Each generator proposes a bounded, deterministic reconstruction hypothesis.
4//! Generators are cheap to decline and never trusted because their logic
5//! "looks obvious": every candidate reaches the common court.
6
7use crate::SOURCE_FORMAT_OPAQUE;
8use crate::adapter::opaque;
9use crate::container::{Descriptor, UNIVERSE};
10use crate::dra::{Op, Program};
11#[cfg(feature = "rans")]
12use crate::entropy::{
13    CODER_ORDER0_BYTE_RANS, CODER_VERSION_1, EntropyChannelDescriptor, EntropyModel, encode_channel,
14};
15use crate::error::Result;
16use crate::integrity::sha256;
17use crate::limits::Limits;
18
19/// Stable candidate identity. The discriminant order is the final
20/// deterministic tie-breaker when prices and work are equal.
21#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
22#[repr(u8)]
23pub enum CandidateKind {
24    /// Single literal object, literal program (Phase 1 floor).
25    Raw = 0,
26    /// Run-length generated repeats (Phase 2).
27    Rle = 1,
28    /// Typed byte rANS entropy channel (Phase 2).
29    ByteRans = 2,
30    /// PDF physical span partition as literal-span DRA ops (Phase 3).
31    PdfPhysical = 3,
32}
33
34impl CandidateKind {
35    /// Stable short name for reports and receipts.
36    pub const fn name(self) -> &'static str {
37        match self {
38            CandidateKind::Raw => "RAW",
39            CandidateKind::Rle => "RLE",
40            CandidateKind::ByteRans => "BYTE_RANS",
41            CandidateKind::PdfPhysical => "PDF_PHYSICAL",
42        }
43    }
44}
45
46/// A proposed descriptor together with its originating family.
47#[derive(Debug, Clone)]
48pub struct Candidate {
49    /// Which family produced this proposal.
50    pub kind: CandidateKind,
51    /// The proposed descriptor.
52    pub descriptor: Descriptor,
53}
54
55/// Generate the bounded candidate set for `input`.
56///
57/// Order is deterministic: RAW first, then RLE when it is expressible.
58pub fn propose(input: &[u8], limits: Limits) -> Result<Vec<Candidate>> {
59    let mut out = vec![Candidate {
60        kind: CandidateKind::Raw,
61        descriptor: opaque::propose(input, limits)?,
62    }];
63    if let Some(rle) = propose_rle(input, limits)? {
64        out.push(rle);
65    }
66    #[cfg(feature = "rans")]
67    if let Some(byte_rans) = propose_byte_rans(input, limits)? {
68        out.push(byte_rans);
69    }
70    if let Some(pdf) = crate::adapter::pdf::propose_pdf(input, limits)? {
71        out.push(pdf);
72    }
73    Ok(out)
74}
75
76/// Propose an inline-run + `REPEAT_LAST` representation of `input`.
77///
78/// Each maximal run of equal bytes becomes one `INLINE` of that single byte,
79/// optionally followed by a `REPEAT_LAST` repeating it `length - 1` more times.
80/// The sequence is therefore always `INLINE, REPEAT_LAST, INLINE, ...`, so no
81/// two `REPEAT_LAST` instructions are ever adjacent. `objects` is empty because
82/// every byte is carried in the graph.
83///
84/// Returns `Ok(None)`, declining honestly, when the run list cannot be
85/// expressed within `limits`: the program would need more instructions than
86/// `max_graph_ops`, or a run is too long to reconstruct with a single
87/// `REPEAT_LAST` (`length - 1` exceeds `max_repeat_count` or `u32::MAX`).
88pub fn propose_rle(input: &[u8], limits: Limits) -> Result<Option<Candidate>> {
89    // Maximal runs of equal bytes: (byte value, run length).
90    let mut runs: Vec<(u8, u64)> = Vec::new();
91    for &b in input {
92        match runs.last_mut() {
93            Some((last, len)) if *last == b => *len += 1,
94            _ => runs.push((b, 1)),
95        }
96    }
97
98    // Worst case is one INLINE plus one REPEAT_LAST per run.
99    if runs.len().saturating_mul(2) > limits.max_graph_ops as usize {
100        return Ok(None);
101    }
102
103    // A run must be reconstructible by a single INLINE + REPEAT_LAST pair.
104    for &(_, length) in &runs {
105        let extra = length - 1;
106        if extra > limits.max_repeat_count || extra > u32::MAX as u64 {
107            return Ok(None);
108        }
109    }
110
111    let mut ops = Vec::with_capacity(runs.len() * 2);
112    for &(byte, length) in &runs {
113        ops.push(Op::Inline { bytes: vec![byte] });
114        if length > 1 {
115            ops.push(Op::RepeatLast {
116                count: (length - 1) as u32,
117            });
118        }
119    }
120
121    let descriptor = Descriptor {
122        universe: UNIVERSE.to_string(),
123        source_format: SOURCE_FORMAT_OPAQUE,
124        format_basis: "opaque;rle-runs".to_string(),
125        models: vec![],
126        channels: vec![],
127        objects: vec![],
128        program: Program::new(ops),
129        source_sha256: sha256(input),
130        source_len: input.len() as u64,
131    };
132    Ok(Some(Candidate {
133        kind: CandidateKind::Rle,
134        descriptor,
135    }))
136}
137
138/// Propose an order-0 byte-rANS representation of the whole `input` as one
139/// entropy channel.
140///
141/// The 256-entry normalized model and the channel header are fully serialized
142/// and charged by the court, so this candidate only wins when order-0 coding
143/// recovers more bytes than the model costs. Declines (`Ok(None)`) honestly:
144///
145/// - empty input: RAW is trivially smaller and there is nothing to code;
146/// - `input.len() > limits.max_channel_symbols`: a single channel cannot carry
147///   it, so the candidate is not expressible within the declared bounds.
148///
149/// Determinism follows from the pure `from_counts` normalizer and from
150/// `encode_channel`, which both depend only on their inputs.
151#[cfg(feature = "rans")]
152pub fn propose_byte_rans(input: &[u8], limits: Limits) -> Result<Option<Candidate>> {
153    if input.is_empty() || input.len() as u64 > limits.max_channel_symbols {
154        return Ok(None);
155    }
156
157    let mut counts = [0u64; 256];
158    for &b in input {
159        counts[b as usize] += 1;
160    }
161    let model = EntropyModel::from_counts(&counts, 12)?;
162    let capsule = encode_channel(&model, input)?;
163
164    let channel = EntropyChannelDescriptor {
165        coder: CODER_ORDER0_BYTE_RANS,
166        coder_version: CODER_VERSION_1,
167        scale_bits: model.scale_bits,
168        lane_count: 1,
169        model_id: 0,
170        symbol_count: capsule.symbol_count,
171        decoded_length: capsule.decoded_length,
172        initial_state: capsule.initial_state,
173        payload: capsule.payload,
174    };
175
176    let descriptor = Descriptor {
177        universe: UNIVERSE.to_string(),
178        source_format: SOURCE_FORMAT_OPAQUE,
179        format_basis: "opaque;byte-rans".to_string(),
180        models: vec![model],
181        channels: vec![channel],
182        objects: vec![],
183        program: Program::new(vec![Op::DecodeChannel { channel_id: 0 }]),
184        source_sha256: sha256(input),
185        source_len: input.len() as u64,
186    };
187
188    Ok(Some(Candidate {
189        kind: CandidateKind::ByteRans,
190        descriptor,
191    }))
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    /// Deterministic xorshift64 PRNG for incompressible test data.
199    fn xorshift64(state: &mut u64) -> u64 {
200        let mut x = *state;
201        x ^= x << 13;
202        x ^= x >> 7;
203        x ^= x << 17;
204        *state = x;
205        x
206    }
207
208    fn xorshift_bytes(n: usize, seed: u64) -> Vec<u8> {
209        let mut state = seed | 1; // avoid the zero fixed point
210        let mut out = Vec::with_capacity(n + 8);
211        while out.len() < n {
212            out.extend_from_slice(&xorshift64(&mut state).to_le_bytes());
213        }
214        out.truncate(n);
215        out
216    }
217
218    fn assert_exact(bytes: &[u8], input: &[u8], limits: Limits) {
219        let (out, parsed) = crate::materialize::decode_to_bytes(bytes, limits).unwrap();
220        assert_eq!(out, input, "materialized bytes must equal the source");
221        assert_eq!(out.len() as u64, parsed.descriptor.source_len);
222        assert_eq!(
223            crate::integrity::sha256(&out),
224            crate::integrity::sha256(input)
225        );
226    }
227
228    #[test]
229    fn rle_wins_on_zeros() {
230        let input = vec![0u8; 65536];
231        let (bytes, report) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
232        assert_eq!(report.kind, CandidateKind::Rle);
233        assert!(
234            report.encoded_len < 512,
235            "RLE encoding of zeros was {} bytes",
236            report.encoded_len
237        );
238        assert_exact(&bytes, &input, Limits::DEFAULT);
239    }
240
241    #[test]
242    fn rle_wins_on_long_runs() {
243        let mut input = Vec::new();
244        input.extend_from_slice(&[0xAAu8; 1000]);
245        input.extend_from_slice(&[0x00, 0x01]);
246        input.extend_from_slice(&[0x55u8; 5000]);
247        input.extend_from_slice(b"tail");
248
249        let (bytes, report) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
250        assert_eq!(report.kind, CandidateKind::Rle);
251        assert!(report.encoded_len < 512);
252        assert_exact(&bytes, &input, Limits::DEFAULT);
253    }
254
255    #[test]
256    fn raw_wins_on_incompressible() {
257        let input = xorshift_bytes(64 * 1024, 0x9E37_79B9_7F4A_7C15);
258        let (bytes, report) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
259        assert_eq!(
260            report.kind,
261            CandidateKind::Raw,
262            "incompressible data must be stored RAW"
263        );
264        assert_exact(&bytes, &input, Limits::DEFAULT);
265    }
266
267    #[test]
268    fn single_byte_is_rle() {
269        let input = [7u8];
270        let (bytes, report) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
271        assert_eq!(report.kind, CandidateKind::Rle);
272        assert!(report.encoded_len < 512);
273        assert_exact(&bytes, &input, Limits::DEFAULT);
274    }
275
276    #[test]
277    fn rle_declines_when_graph_too_big() {
278        let input = vec![0u8; 100];
279        let limits = Limits {
280            max_graph_ops: 1,
281            ..Limits::DEFAULT
282        };
283        assert!(
284            propose_rle(&input, limits).unwrap().is_none(),
285            "100 single-byte runs cannot fit in a one-op graph"
286        );
287        // The RAW candidate still reconstructs exactly under these limits.
288        let (bytes, report) = crate::encode::encode(&input, limits).unwrap();
289        assert_eq!(report.kind, CandidateKind::Raw);
290        assert_exact(&bytes, &input, limits);
291    }
292
293    #[cfg(feature = "rans")]
294    #[test]
295    fn byte_rans_wins_on_text() {
296        let input = b"The quick brown fox jumps over the lazy dog. ".repeat(1500);
297        let (bytes, report) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
298        assert_eq!(report.kind, CandidateKind::ByteRans);
299        assert!(
300            report.encoded_len < report.source_len,
301            "order-0 rANS must beat RAW on low-entropy text: {} vs {}",
302            report.encoded_len,
303            report.source_len
304        );
305        assert_exact(&bytes, &input, Limits::DEFAULT);
306    }
307
308    #[cfg(feature = "rans")]
309    #[test]
310    fn byte_rans_exact_on_all_byte_values() {
311        // Exercise every byte value through the channel. A uniform `0..=255`
312        // stream is incompressible at order 0 (and the 516-byte model makes rANS
313        // lose to RAW), so the body is a skewed, deterministic stream whose head
314        // guarantees all 256 symbols are present and nonzero-frequency.
315        let mut input: Vec<u8> = (0..=255u8).collect();
316        let mut state = 0x2545_F491_4F6C_DD1D;
317        while input.len() < 64 * 1024 {
318            let r = xorshift64(&mut state);
319            if !r.is_multiple_of(8) {
320                input.push(0x00);
321            } else {
322                input.push((r >> 32) as u8);
323            }
324        }
325        input.truncate(64 * 1024);
326
327        let (bytes, report) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
328        assert_eq!(report.kind, CandidateKind::ByteRans);
329        assert_exact(&bytes, &input, Limits::DEFAULT);
330    }
331
332    #[test]
333    fn byte_rans_is_deterministic() {
334        let input = b"deterministic byte rANS stream ".repeat(600);
335        let (a, _) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
336        let (b, _) = crate::encode::encode(&input, Limits::DEFAULT).unwrap();
337        assert_eq!(a, b, ".voldoc bytes must be identical across encodes");
338    }
339
340    #[cfg(feature = "rans")]
341    #[test]
342    fn byte_rans_declines_empty() {
343        assert!(
344            propose_byte_rans(&[], Limits::DEFAULT).unwrap().is_none(),
345            "empty input must decline: RAW is trivially smaller"
346        );
347    }
348
349    #[cfg(feature = "rans")]
350    #[test]
351    fn model_cost_is_charged() {
352        // On a two-byte input the 516-byte canonical model cannot pay for
353        // itself, so BYTE_RANS must lose the complete-cost court. This documents
354        // model-cost honesty.
355        let input = b"ab";
356        let (bytes, report) = crate::encode::encode(input, Limits::DEFAULT).unwrap();
357        assert_ne!(report.kind, CandidateKind::ByteRans);
358        assert_exact(&bytes, input, Limits::DEFAULT);
359    }
360}
vole_document/encode/candidates.rs

vole_document/encode/
candidates.rs
