Skip to main content

tufazip_preprocess/
codec.rs

1use std::cmp::Ordering;
2use std::collections::HashSet;
3use std::fs::File;
4use std::io::{BufReader, BufWriter, Read, Write};
5use std::path::{Path, PathBuf};
6
7use crate::case_space::{
8    case_space_encode, CaseSpaceDecoder, CH_FIRST_UPPER, CH_NO_SPACE, CH_TO_UPPER,
9};
10use crate::dictionary::Dictionary;
11use crate::error::PreprocessError;
12
13const NS: usize = 256;
14const MAX_WORDS_PER_ITER: usize = 100;
15const SUBST_COST: f64 = 7.0;
16const TOT_FREQ_RED_BITS: f64 = 1.3;
17
18/// Ordering applied to the final dictionary entries.
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
20pub enum SortOrder {
21    /// Keep base bytes `0..256` followed by learned merges in discovery order.
22    #[default]
23    Discovery,
24    /// Sort all symbols by decreasing corpus frequency (`-s` flag in `preprocess.c`).
25    ByFrequency,
26}
27
28/// Parameters controlling dictionary induction during preprocessing.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct EncodeConfig {
31    /// Approximate maximum vocabulary size, including the 256 base byte symbols.
32    pub max_words: usize,
33    /// Minimum frequency required for a merged word to be added and retained.
34    pub min_freq: u32,
35    /// Output vocabulary ordering.
36    pub sort_order: SortOrder,
37    /// Optional path where frequency/coverage debug info is written (`-D` in `preprocess.c`).
38    pub debug_dict_path: Option<PathBuf>,
39}
40
41impl Default for EncodeConfig {
42    fn default() -> Self {
43        Self {
44            max_words: 4097,
45            min_freq: 5,
46            sort_order: SortOrder::Discovery,
47            debug_dict_path: None,
48        }
49    }
50}
51
52/// Summary statistics from a preprocessing run.
53#[derive(Debug, Clone, Copy, PartialEq)]
54pub struct EncodeReport {
55    /// Input byte count before preprocessing.
56    pub input_bytes: usize,
57    /// Symbol count immediately after case/space encoding.
58    pub case_space_symbols: usize,
59    /// Final vocabulary size (`256 + learned_words`).
60    pub vocab_size: usize,
61    /// Final emitted token count.
62    pub token_count: usize,
63    /// Zero-order symbol entropy in bits.
64    pub entropy_bits: f64,
65}
66
67#[derive(Debug, Clone)]
68struct WordEntry {
69    pair: [u16; 2],
70    freq: u32,
71    score: f32,
72}
73
74const EMPTY_SLOT: u32 = u32::MAX;
75
76#[inline]
77const fn pack_pair(pair: [u16; 2]) -> u32 {
78    ((pair[0] as u32) << 16) | (pair[1] as u32)
79}
80
81#[inline]
82fn hash_pair_key(key: u32, mask: usize) -> usize {
83    let h = key.wrapping_mul(0x9E37_79B1);
84    ((h ^ (h >> 16)) as usize) & mask
85}
86
87#[derive(Debug)]
88struct WordList {
89    words: Vec<WordEntry>,
90    keys: Vec<u32>,
91    vals: Vec<u32>,
92    mask: usize,
93}
94
95impl WordList {
96    fn with_table_cap(cap: usize) -> Self {
97        let cap = cap.next_power_of_two().max(64);
98        Self {
99            words: Vec::new(),
100            keys: vec![0; cap],
101            vals: vec![EMPTY_SLOT; cap],
102            mask: cap - 1,
103        }
104    }
105
106    fn clear(&mut self) {
107        self.words.clear();
108        self.vals.fill(EMPTY_SLOT);
109    }
110
111    fn grow(&mut self) {
112        let new_cap = (self.vals.len() * 2).max(64);
113        let new_mask = new_cap - 1;
114        let mut new_keys = vec![0u32; new_cap];
115        let mut new_vals = vec![EMPTY_SLOT; new_cap];
116        for (idx, entry) in self.words.iter().enumerate() {
117            let k = pack_pair(entry.pair);
118            let mut slot = hash_pair_key(k, new_mask);
119            while new_vals[slot] != EMPTY_SLOT {
120                slot = (slot + 1) & new_mask;
121            }
122            new_keys[slot] = k;
123            new_vals[slot] = idx as u32;
124        }
125        self.keys = new_keys;
126        self.vals = new_vals;
127        self.mask = new_mask;
128    }
129
130    #[inline]
131    fn find(&self, pair: [u16; 2]) -> Option<usize> {
132        let k = pack_pair(pair);
133        let mut slot = hash_pair_key(k, self.mask);
134        loop {
135            let val = self.vals[slot];
136            if val == EMPTY_SLOT {
137                return None;
138            }
139            if self.keys[slot] == k {
140                return Some(val as usize);
141            }
142            slot = (slot + 1) & self.mask;
143        }
144    }
145
146    #[inline]
147    fn find_or_insert(&mut self, pair: [u16; 2]) -> usize {
148        if self.words.len() * 2 >= self.vals.len() {
149            self.grow();
150        }
151        let k = pack_pair(pair);
152        let mut slot = hash_pair_key(k, self.mask);
153        loop {
154            let val = self.vals[slot];
155            if val == EMPTY_SLOT {
156                let idx = self.words.len();
157                self.words.push(WordEntry {
158                    pair,
159                    freq: 0,
160                    score: 0.0,
161                });
162                self.keys[slot] = k;
163                self.vals[slot] = idx as u32;
164                return idx;
165            }
166            if self.keys[slot] == k {
167                return val as usize;
168            }
169            slot = (slot + 1) & self.mask;
170        }
171    }
172}
173
174impl Default for WordList {
175    fn default() -> Self {
176        Self::with_table_cap(4096)
177    }
178}
179
180fn expand_symbol(words: &[WordEntry], code: usize, out: &mut Vec<u8>) {
181    if code < NS {
182        out.push(code as u8);
183    } else {
184        let entry = &words[code - NS];
185        expand_symbol(words, usize::from(entry.pair[0]), out);
186        expand_symbol(words, usize::from(entry.pair[1]), out);
187    }
188}
189
190fn build_symbol_n_bits(cw: &WordList, char_freq: &[u32; NS], tot_freq: usize) -> Vec<f32> {
191    let total = tot_freq as f64;
192    let total_syms = NS + cw.words.len();
193    let mut n_bits = vec![0.0f32; total_syms];
194    for (c, &freq) in char_freq.iter().enumerate() {
195        n_bits[c] = -(((f64::from(freq) / total).log2()) as f32);
196    }
197    for (i, p) in cw.words.iter().enumerate() {
198        let code = NS + i;
199        n_bits[code] = if p.freq == 0 {
200            let a = usize::from(p.pair[0]);
201            let b = usize::from(p.pair[1]);
202            n_bits[a] + n_bits[b]
203        } else {
204            -(((f64::from(p.freq) / total).log2()) as f32)
205        };
206    }
207    n_bits
208}
209
210fn select_best_words(
211    ws: &mut WordList,
212    max_to_add: usize,
213    cw: &mut WordList,
214    char_freq: &[u32; NS],
215    tot_freq: usize,
216    min_freq: u32,
217) -> usize {
218    let sym_bits = build_symbol_n_bits(cw, char_freq, tot_freq);
219    let total = tot_freq as f64;
220    for entry in &mut ws.words {
221        if entry.freq <= 1 {
222            entry.score = -1.0;
223            continue;
224        }
225        let freq_f = entry.freq as f32;
226        let old_bits =
227            (sym_bits[usize::from(entry.pair[0])] + sym_bits[usize::from(entry.pair[1])]) * freq_f;
228        let new_bits = ((-(f64::from(entry.freq) / total).log2() + TOT_FREQ_RED_BITS)
229            * f64::from(entry.freq)
230            + SUBST_COST) as f32;
231        entry.score = old_bits - new_bits;
232    }
233
234    ws.words.sort_by(|a, b| {
235        if a.score > b.score {
236            Ordering::Less
237        } else if a.score < b.score {
238            Ordering::Greater
239        } else {
240            Ordering::Equal
241        }
242    });
243
244    let bitmap_len = NS + cw.words.len();
245    let mut bitmap_start = vec![false; bitmap_len];
246    let mut bitmap_end = vec![false; bitmap_len];
247
248    let mut added = 0usize;
249    for entry in &ws.words {
250        if entry.score <= 0.0 || entry.freq < min_freq {
251            break;
252        }
253        let a = usize::from(entry.pair[0]);
254        let b = usize::from(entry.pair[1]);
255        if bitmap_end[a] || bitmap_start[b] {
256            continue;
257        }
258        bitmap_start[a] = true;
259        bitmap_end[b] = true;
260        cw.find_or_insert(entry.pair);
261        added += 1;
262        if added >= max_to_add {
263            break;
264        }
265    }
266    added
267}
268
269fn compute_word_freq(s: &mut WordList, char_freq: &mut [u32; NS], buf: &[u16]) {
270    for entry in &mut s.words {
271        entry.freq = 0;
272    }
273    char_freq.fill(0);
274    for &c in buf {
275        let c_usize = usize::from(c);
276        if c_usize >= NS {
277            s.words[c_usize - NS].freq += 1;
278        } else {
279            char_freq[c_usize] += 1;
280        }
281    }
282}
283
284fn out_word(obuf: &mut Vec<u16>, s: &WordList, c: u16) {
285    let c_usize = usize::from(c);
286    if c_usize < NS {
287        obuf.push(c);
288    } else {
289        let p = &s.words[c_usize - NS];
290        if p.freq == 0 {
291            out_word(obuf, s, p.pair[0]);
292            out_word(obuf, s, p.pair[1]);
293        } else {
294            obuf.push(c);
295        }
296    }
297}
298
299fn update_word_freq(
300    s: &mut WordList,
301    char_freq: &mut [u32; NS],
302    buf: &mut Vec<u16>,
303    scratch: &mut Vec<u16>,
304    min_freq: u32,
305) -> usize {
306    compute_word_freq(s, char_freq, buf);
307
308    let mut word_count = 0usize;
309    for entry in &mut s.words {
310        if entry.freq >= min_freq {
311            word_count += 1;
312        } else {
313            entry.freq = 0;
314        }
315    }
316    if word_count == s.words.len() {
317        return word_count;
318    }
319
320    scratch.clear();
321    for &sym in buf.iter() {
322        out_word(scratch, s, sym);
323    }
324    std::mem::swap(buf, scratch);
325    compute_word_freq(s, char_freq, buf);
326    word_count
327}
328
329fn compute_entropy(s: &WordList, char_freq: &[u32; NS], buf_len: usize) -> f64 {
330    if buf_len == 0 {
331        return 0.0;
332    }
333    let total = buf_len as f64;
334    let mut n_bits = 0.0f64;
335    for &freq in char_freq {
336        if freq != 0 {
337            let f = f64::from(freq);
338            n_bits += -(f / total).log2() * f;
339        }
340    }
341    for entry in &s.words {
342        if entry.freq > 0 {
343            let f = f64::from(entry.freq);
344            n_bits += -(f / total).log2() * f;
345        }
346    }
347    n_bits
348}
349
350fn sort_words(s: &WordList, char_freq: &[u32; NS], order: SortOrder) -> Vec<usize> {
351    let total_slots = NS + s.words.len();
352    let mut tab = Vec::with_capacity(total_slots);
353    for i in 0..total_slots {
354        if i >= NS && s.words[i - NS].freq == 0 {
355            continue;
356        }
357        tab.push(i);
358    }
359    if order == SortOrder::ByFrequency {
360        tab.sort_by(|&c1, &c2| {
361            let freq1 = if c1 < NS {
362                char_freq[c1]
363            } else {
364                s.words[c1 - NS].freq
365            };
366            let freq2 = if c2 < NS {
367                char_freq[c2]
368            } else {
369                s.words[c2 - NS].freq
370            };
371            freq2.cmp(&freq1)
372        });
373    }
374    tab
375}
376
377fn write_debug_word(out: &mut impl Write, words: &[WordEntry], code: usize) -> std::io::Result<()> {
378    if code < NS {
379        let byte = code as u8;
380        match byte {
381            b'\n' => out.write_all(b"\\n"),
382            b'\\' => out.write_all(b"\\\\"),
383            CH_TO_UPPER => out.write_all(b"\\u"),
384            CH_FIRST_UPPER => out.write_all(b"\\c"),
385            CH_NO_SPACE => out.write_all(b"\\s"),
386            other => out.write_all(&[other]),
387        }
388    } else {
389        let entry = &words[code - NS];
390        write_debug_word(out, words, usize::from(entry.pair[0]))?;
391        write_debug_word(out, words, usize::from(entry.pair[1]))
392    }
393}
394
395fn save_words_debug(
396    path: &Path,
397    s: &WordList,
398    char_freq: &[u32; NS],
399    tot_freq: usize,
400    tab: &[usize],
401) -> Result<(), PreprocessError> {
402    let file = File::create(path)?;
403    let mut out = BufWriter::new(file);
404    writeln!(out, "{:>7} {:>5} WORD", "FREQ", "CUM%")?;
405    let mut sum = 0u64;
406    let denom = tot_freq.max(1) as f64;
407    for &c in tab {
408        let freq = if c < NS {
409            char_freq[c]
410        } else {
411            s.words[c - NS].freq
412        };
413        sum += u64::from(freq);
414        write!(out, "{freq:>7} {:>5.1} '", (sum as f64) / denom * 100.0)?;
415        write_debug_word(&mut out, &s.words, c)?;
416        writeln!(out, "'")?;
417    }
418    out.flush()?;
419    Ok(())
420}
421
422fn emit_token_ids(
423    code: usize,
424    words: &[WordEntry],
425    convert_table: &[u16],
426    out_tokens: &mut Vec<u16>,
427) {
428    if code < NS {
429        out_tokens.push(convert_table[code]);
430    } else {
431        let idx = code - NS;
432        let entry = &words[idx];
433        if entry.freq == 0 {
434            emit_token_ids(usize::from(entry.pair[0]), words, convert_table, out_tokens);
435            emit_token_ids(usize::from(entry.pair[1]), words, convert_table, out_tokens);
436        } else {
437            out_tokens.push(convert_table[code]);
438        }
439    }
440}
441
442fn fnv1a_u16(slice: &[u16]) -> u64 {
443    let mut hash = 0xcbf2_9ce4_8422_2325u64;
444    for &v in slice {
445        hash ^= u64::from(v);
446        hash = hash.wrapping_mul(0x0100_0000_01b3);
447    }
448    hash
449}
450
451/// Runs Fabrice Bellard's bigram dictionary induction and encodes `input` into token IDs.
452///
453/// # Errors
454///
455/// Returns [`PreprocessError::InvalidMaxWords`] if `config.max_words < 256` or `> 65536`,
456/// or [`PreprocessError::Io`] if `config.debug_dict_path` cannot be written.
457pub fn encode_bytes(
458    input: &[u8],
459    config: &EncodeConfig,
460) -> Result<(Dictionary, Vec<u16>, EncodeReport), PreprocessError> {
461    if config.max_words < NS || config.max_words > usize::from(u16::MAX) + 1 {
462        return Err(PreprocessError::InvalidMaxWords(config.max_words));
463    }
464
465    let mut buf = case_space_encode(input);
466    let case_space_symbols = buf.len();
467    let mut s = WordList::default();
468    let mut char_freq = [0u32; NS];
469    compute_word_freq(&mut s, &mut char_freq, &buf);
470
471    let max_learned = config.max_words - NS;
472    let mut word_count = 0usize;
473    let mut entropy_bits = compute_entropy(&s, &char_freq, buf.len());
474    let mut seen_states = HashSet::new();
475    seen_states.insert((s.words.len(), word_count, buf.len(), fnv1a_u16(&buf)));
476    let mut ws = WordList::with_table_cap(16384);
477    let mut scratch_buf = Vec::with_capacity(buf.len());
478
479    while word_count < max_learned {
480        if buf.len() < 2 {
481            break;
482        }
483        ws.clear();
484        for pair in buf.windows(2) {
485            let idx = ws.find_or_insert([pair[0], pair[1]]);
486            ws.words[idx].freq += 1;
487        }
488        let added = select_best_words(
489            &mut ws,
490            MAX_WORDS_PER_ITER.min(max_learned - word_count),
491            &mut s,
492            &char_freq,
493            buf.len(),
494            config.min_freq,
495        );
496        if added == 0 {
497            break;
498        }
499
500        scratch_buf.clear();
501        let mut i = 0usize;
502        while i < buf.len() {
503            if i + 1 < buf.len() {
504                if let Some(word_idx) = s.find([buf[i], buf[i + 1]]) {
505                    scratch_buf.push((NS + word_idx) as u16);
506                    i += 2;
507                    continue;
508                }
509            }
510            scratch_buf.push(buf[i]);
511            i += 1;
512        }
513        std::mem::swap(&mut buf, &mut scratch_buf);
514
515        let word_count_prev = word_count;
516        word_count = update_word_freq(
517            &mut s,
518            &mut char_freq,
519            &mut buf,
520            &mut scratch_buf,
521            config.min_freq,
522        );
523        entropy_bits = compute_entropy(&s, &char_freq, buf.len());
524        let state = (s.words.len(), word_count, buf.len(), fnv1a_u16(&buf));
525        if word_count >= max_learned || word_count == word_count_prev || !seen_states.insert(state)
526        {
527            break;
528        }
529    }
530
531    let tab_sort = sort_words(&s, &char_freq, config.sort_order);
532    if let Some(debug_path) = &config.debug_dict_path {
533        save_words_debug(debug_path, &s, &char_freq, buf.len(), &tab_sort)?;
534    }
535
536    let mut dict_words = Vec::with_capacity(tab_sort.len());
537    let mut convert_table = vec![u16::MAX; NS + s.words.len()];
538    for (new_id, &orig_code) in tab_sort.iter().enumerate() {
539        convert_table[orig_code] = new_id as u16;
540        let mut word_bytes = Vec::new();
541        expand_symbol(&s.words, orig_code, &mut word_bytes);
542        dict_words.push(word_bytes);
543    }
544
545    let mut out_tokens = Vec::with_capacity(buf.len());
546    for &code in &buf {
547        emit_token_ids(usize::from(code), &s.words, &convert_table, &mut out_tokens);
548    }
549
550    let dict = Dictionary::from_words(dict_words);
551    let report = EncodeReport {
552        input_bytes: input.len(),
553        case_space_symbols,
554        vocab_size: dict.len(),
555        token_count: out_tokens.len(),
556        entropy_bits,
557    };
558    Ok((dict, out_tokens, report))
559}
560
561/// Preprocesses `in_path`, writing the learned dictionary to `dict_path` and big-endian tokens to `out_path`.
562///
563/// # Errors
564///
565/// Returns [`PreprocessError`] on invalid parameters or I/O failures.
566pub fn encode_file(
567    in_path: impl AsRef<Path>,
568    out_path: impl AsRef<Path>,
569    dict_path: impl AsRef<Path>,
570    config: &EncodeConfig,
571) -> Result<EncodeReport, PreprocessError> {
572    let input = std::fs::read(in_path)?;
573    let (dict, tokens, report) = encode_bytes(&input, config)?;
574    dict.save(dict_path)?;
575    write_tokens_be16(out_path, &tokens)?;
576    Ok(report)
577}
578
579#[derive(Debug, Default)]
580struct TrieNode {
581    token: Option<u16>,
582    children: Vec<(u8, usize)>,
583}
584
585/// Encodes `input` greedily (longest match first) using an existing [`Dictionary`].
586///
587/// Useful when compressing new text with a fixed vocabulary such as `assets/enwik9.voc`.
588///
589/// # Errors
590///
591/// Returns [`PreprocessError::MissingByteSymbol`] if `dict` does not contain all 256
592/// single-byte base entries required as fallback.
593pub fn encode_with_dictionary(
594    input: &[u8],
595    dict: &Dictionary,
596) -> Result<Vec<u16>, PreprocessError> {
597    let mut byte_tokens = [None::<u16>; 256];
598    let mut nodes = vec![TrieNode::default()];
599
600    for (idx, word) in dict.words().iter().enumerate() {
601        let token = idx as u16;
602        if word.len() == 1 && byte_tokens[usize::from(word[0])].is_none() {
603            byte_tokens[usize::from(word[0])] = Some(token);
604        }
605        let mut node_idx = 0usize;
606        for &b in word {
607            let next_idx = nodes[node_idx]
608                .children
609                .iter()
610                .find(|&&(ch, _)| ch == b)
611                .map(|&(_, child)| child);
612            node_idx = match next_idx {
613                Some(child) => child,
614                None => {
615                    let child = nodes.len();
616                    nodes.push(TrieNode::default());
617                    nodes[node_idx].children.push((b, child));
618                    child
619                }
620            };
621        }
622        if nodes[node_idx].token.is_none() {
623            nodes[node_idx].token = Some(token);
624        }
625    }
626
627    for (b, slot) in byte_tokens.iter().enumerate() {
628        if slot.is_none() {
629            return Err(PreprocessError::MissingByteSymbol(b as u8));
630        }
631    }
632
633    let cs_u16 = case_space_encode(input);
634    let cs: Vec<u8> = cs_u16.into_iter().map(|v| v as u8).collect();
635    let mut tokens = Vec::with_capacity(cs.len() / 2 + 1);
636    let mut pos = 0usize;
637
638    while pos < cs.len() {
639        let mut node_idx = 0usize;
640        let mut best_token = byte_tokens[usize::from(cs[pos])]
641            .ok_or_else(|| PreprocessError::MissingByteSymbol(cs[pos]))?;
642        let mut best_len = 1usize;
643
644        let mut cur = pos;
645        while cur < cs.len() {
646            let ch = cs[cur];
647            let Some(&(_, next_idx)) = nodes[node_idx].children.iter().find(|&&(c, _)| c == ch)
648            else {
649                break;
650            };
651            node_idx = next_idx;
652            cur += 1;
653            if let Some(tok) = nodes[node_idx].token {
654                best_token = tok;
655                best_len = cur - pos;
656            }
657        }
658
659        tokens.push(best_token);
660        pos += best_len;
661    }
662
663    Ok(tokens)
664}
665
666/// Decodes a sequence of token IDs back into the exact original source bytes.
667///
668/// # Errors
669///
670/// Returns [`PreprocessError::InvalidSymbol`] if any token ID is `>= dict.len()`.
671pub fn decode_tokens(tokens: &[u16], dict: &Dictionary) -> Result<Vec<u8>, PreprocessError> {
672    let mut out = Vec::with_capacity(tokens.len() * 2);
673    let mut decoder = CaseSpaceDecoder::new();
674    for &tok in tokens {
675        let Some(bytes) = dict.get(tok) else {
676            return Err(PreprocessError::InvalidSymbol {
677                symbol: tok,
678                vocab_size: dict.len(),
679            });
680        };
681        // Writing to Vec<u8> is infallible.
682        let _ = decoder.push_bytes(bytes, &mut out);
683    }
684    Ok(out)
685}
686
687/// Streams a big-endian `u16` token file back to its original raw file using `dict_path`.
688///
689/// # Errors
690///
691/// Returns [`PreprocessError`] on I/O error, odd file length, or out-of-range symbol ID.
692pub fn decode_file(
693    in_path: impl AsRef<Path>,
694    out_path: impl AsRef<Path>,
695    dict_path: impl AsRef<Path>,
696) -> Result<usize, PreprocessError> {
697    let dict = Dictionary::load(dict_path)?;
698    let in_file = File::open(in_path)?;
699    let in_len = in_file.metadata()?.len();
700    if in_len % 2 != 0 {
701        return Err(PreprocessError::OddTokenStreamLength(in_len));
702    }
703
704    let mut reader = BufReader::with_capacity(256 * 1024, in_file);
705    let out_file = File::create(out_path)?;
706    let mut writer = BufWriter::with_capacity(256 * 1024, out_file);
707    let mut decoder = CaseSpaceDecoder::new();
708    let mut pair = [0u8; 2];
709    let mut count = 0usize;
710
711    loop {
712        match reader.read_exact(&mut pair) {
713            Ok(()) => {
714                let tok = u16::from_be_bytes(pair);
715                let Some(word) = dict.get(tok) else {
716                    return Err(PreprocessError::InvalidSymbol {
717                        symbol: tok,
718                        vocab_size: dict.len(),
719                    });
720                };
721                decoder.push_bytes(word, &mut writer)?;
722                count += 1;
723            }
724            Err(e) if e.kind() == std::io::ErrorKind::UnexpectedEof => break,
725            Err(e) => return Err(e.into()),
726        }
727    }
728
729    writer.flush()?;
730    Ok(count)
731}
732
733/// Writes `tokens` as big-endian `u16` pairs to `path`.
734///
735/// # Errors
736///
737/// Returns [`PreprocessError::Io`] on write failure.
738pub fn write_tokens_be16(path: impl AsRef<Path>, tokens: &[u16]) -> Result<(), PreprocessError> {
739    let file = File::create(path)?;
740    let mut writer = BufWriter::with_capacity(256 * 1024, file);
741    for &tok in tokens {
742        writer.write_all(&tok.to_be_bytes())?;
743    }
744    writer.flush()?;
745    Ok(())
746}
747
748/// Reads big-endian `u16` token IDs from `path`.
749///
750/// # Errors
751///
752/// Returns [`PreprocessError::OddTokenStreamLength`] or [`PreprocessError::Io`].
753pub fn read_tokens_be16(path: impl AsRef<Path>) -> Result<Vec<u16>, PreprocessError> {
754    let bytes = std::fs::read(path)?;
755    if bytes.len() % 2 != 0 {
756        return Err(PreprocessError::OddTokenStreamLength(bytes.len() as u64));
757    }
758    let mut tokens = Vec::with_capacity(bytes.len() / 2);
759    for chunk in bytes.chunks_exact(2) {
760        tokens.push(u16::from_be_bytes([chunk[0], chunk[1]]));
761    }
762    Ok(tokens)
763}
764
765#[cfg(test)]
766mod tests {
767    use std::path::PathBuf;
768
769    use super::*;
770
771    fn sample_corpus() -> Vec<u8> {
772        let block = concat!(
773            "<page>\n",
774            "  <title>Wikipedia: Neural Data Compression &amp; Rust</title>\n",
775            "  <text xml:space=\"preserve\">\n",
776            "    The QUICK brown fox jumps over the lazy dog.\n",
777            "    Backslashes \\ and newlines\nappear alongside UTF-8: café, naïve, 日本語, —!\n",
778            "    Numbers 1234567890, URLs https://example.org/wiki/Compression, and repetition.\n",
779            "  </text>\n",
780            "</page>\n",
781        );
782        block.repeat(12).into_bytes()
783    }
784
785    #[test]
786    fn encode_decode_roundtrip_discovery_and_frequency() {
787        let corpus = sample_corpus();
788        for order in [SortOrder::Discovery, SortOrder::ByFrequency] {
789            let debug_tmp = tempfile::NamedTempFile::new().unwrap();
790            let cfg = EncodeConfig {
791                max_words: 400,
792                min_freq: 3,
793                sort_order: order,
794                debug_dict_path: Some(debug_tmp.path().to_path_buf()),
795            };
796            let (dict, tokens, report) = encode_bytes(&corpus, &cfg).unwrap();
797            assert!(dict.len() >= 256);
798            assert!(dict.len() <= 400);
799            assert_eq!(report.token_count, tokens.len());
800            assert!(tokens.len() < corpus.len());
801
802            let decoded = decode_tokens(&tokens, &dict).unwrap();
803            assert_eq!(decoded, corpus, "roundtrip failed for {order:?}");
804
805            let debug_bytes = std::fs::read(debug_tmp.path()).unwrap();
806            assert!(debug_bytes.windows(4).any(|w| w == b"CUM%"));
807        }
808    }
809
810    #[test]
811    fn empty_input_roundtrip() {
812        let (dict, tokens, report) = encode_bytes(b"", &EncodeConfig::default()).unwrap();
813        assert_eq!(dict.len(), 256);
814        assert!(tokens.is_empty());
815        assert_eq!(report.token_count, 0);
816        assert_eq!(decode_tokens(&tokens, &dict).unwrap(), b"");
817    }
818
819    #[test]
820    fn encode_and_decode_file_with_enwik9_voc() {
821        let voc_path = PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("../../assets/enwik9.voc");
822        let dict = Dictionary::load(&voc_path).unwrap();
823        let corpus = sample_corpus();
824        let tokens = encode_with_dictionary(&corpus, &dict).unwrap();
825        assert!(tokens.len() < corpus.len());
826
827        let dir = tempfile::tempdir().unwrap();
828        let pp_path = dir.path().join("sample.pp");
829        let out_path = dir.path().join("sample.out");
830        write_tokens_be16(&pp_path, &tokens).unwrap();
831        let read_back = read_tokens_be16(&pp_path).unwrap();
832        assert_eq!(read_back, tokens);
833
834        let decoded_count = decode_file(&pp_path, &out_path, &voc_path).unwrap();
835        assert_eq!(decoded_count, tokens.len());
836        assert_eq!(std::fs::read(&out_path).unwrap(), corpus);
837    }
838
839    #[test]
840    fn decode_rejects_invalid_symbol_and_odd_length() {
841        let dict = Dictionary::from_words((0u8..=255).map(|b| vec![b]).collect());
842        assert!(matches!(
843            decode_tokens(&[300], &dict),
844            Err(PreprocessError::InvalidSymbol {
845                symbol: 300,
846                vocab_size: 256
847            })
848        ));
849
850        let dir = tempfile::tempdir().unwrap();
851        let voc_path = dir.path().join("tiny.voc");
852        let pp_path = dir.path().join("odd.pp");
853        let out_path = dir.path().join("out.bin");
854        dict.save(&voc_path).unwrap();
855        std::fs::write(&pp_path, [0, 1, 2]).unwrap();
856        assert!(matches!(
857            decode_file(&pp_path, &out_path, &voc_path),
858            Err(PreprocessError::OddTokenStreamLength(3))
859        ));
860    }
861
862    #[test]
863    fn encode_terminates_on_oscillating_merge_cycle() {
864        let crates_dir = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
865            .parent()
866            .unwrap()
867            .to_path_buf();
868        let mut rs_paths = Vec::new();
869        for entry in std::fs::read_dir(&crates_dir).unwrap() {
870            let src_dir = entry.unwrap().path().join("src");
871            if src_dir.is_dir() {
872                for src_entry in std::fs::read_dir(src_dir).unwrap() {
873                    let p = src_entry.unwrap().path();
874                    if p.extension().and_then(|s| s.to_str()) == Some("rs") {
875                        rs_paths.push(p);
876                    }
877                }
878            }
879        }
880        rs_paths.sort();
881        let mut corpus = Vec::new();
882        for (idx, p) in rs_paths.iter().enumerate() {
883            if idx > 0 {
884                corpus.push(b'\n');
885            }
886            corpus.extend_from_slice(&std::fs::read(p).unwrap());
887            if corpus.len() >= 32_768 {
888                break;
889            }
890        }
891        corpus.truncate(32_768);
892
893        let cfg = EncodeConfig {
894            max_words: 1024,
895            min_freq: 3,
896            sort_order: SortOrder::Discovery,
897            debug_dict_path: None,
898        };
899        let (dict, tokens, _report) = encode_bytes(&corpus, &cfg).unwrap();
900        let decoded = decode_tokens(&tokens, &dict).unwrap();
901        assert_eq!(decoded, corpus);
902    }
903}