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

vole_document/encode/
candidates.rs
