tinybz2 0.1.0

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
//! Huffman coding for bz2.
//!
//! bz2 uses a multi-table Huffman scheme:
//! - Symbols are divided into groups of 50 ("selector groups").
//! - Up to 6 different Huffman tables are created.
//! - A selector array maps each group of 50 symbols to one of the tables.
//! - The selectors themselves are MTF-encoded and stored as unary codes.
//! - Code lengths are delta-encoded in the bitstream.
//!
//! Memory: ~10 KB for all tables + selectors.

use crate::constants::{MAX_SYMBOLS, MAX_GROUPS, MAX_CODE_LEN, MIN_CODE_LEN, GROUP_SIZE};
use crate::error::Error;
use crate::bitio::{BitReader, BitWriter};

// ── Huffman Table ──────────────────────────────────────────────────────────

/// A single Huffman table: code lengths and derived encoding/decoding info.
#[derive(Clone)]
pub struct HuffTable {
    /// Code length for each symbol (0 = symbol not present).
    pub lengths: [u8; MAX_SYMBOLS],
    /// Number of active symbols.
    pub n_symbols: usize,
    /// Lookup: symbol → (code, code_length) for encoding.
    pub codes: [u32; MAX_SYMBOLS],
}

impl HuffTable {
    pub const fn new() -> Self {
        Self {
            lengths: [0; MAX_SYMBOLS],
            n_symbols: 0,
            codes: [0; MAX_SYMBOLS],
        }
    }

    /// Build canonical Huffman codes from the code lengths.
    ///
    /// This assigns codes in canonical order: shorter codes first,
    /// and for equal lengths, symbols in ascending order.
    pub fn build_codes(&mut self) -> Result<(), Error> {
        // Find min and max code lengths
        let mut min_len = MAX_CODE_LEN;
        let mut max_len = 0u32;
        for i in 0..self.n_symbols {
            let l = self.lengths[i] as u32;
            if l > 0 {
                if l < min_len {
                    min_len = l;
                }
                if l > max_len {
                    max_len = l;
                }
            }
        }

        if max_len > MAX_CODE_LEN {
            return Err(Error::BadHuffmanTable);
        }

        // Count codes of each length
        let mut bl_count = [0u32; (MAX_CODE_LEN + 1) as usize];
        for i in 0..self.n_symbols {
            bl_count[self.lengths[i] as usize] += 1;
        }
        bl_count[0] = 0;

        // Compute first code for each length
        let mut next_code = [0u32; (MAX_CODE_LEN + 1) as usize];
        let mut code = 0u32;
        for bits in 1..=max_len {
            code = (code + bl_count[(bits - 1) as usize]) << 1;
            next_code[bits as usize] = code;
        }

        // Assign codes to symbols
        for i in 0..self.n_symbols {
            let l = self.lengths[i] as u32;
            if l > 0 {
                self.codes[i] = next_code[l as usize];
                next_code[l as usize] += 1;
            }
        }

        Ok(())
    }
}

/// Collection of Huffman tables for a bz2 block.
pub struct HuffTables {
    pub tables: [HuffTable; MAX_GROUPS],
    pub n_groups: usize,
    pub n_symbols: usize,
}

impl HuffTables {
    pub fn new() -> Self {
        Self {
            tables: [
                HuffTable::new(),
                HuffTable::new(),
                HuffTable::new(),
                HuffTable::new(),
                HuffTable::new(),
                HuffTable::new(),
            ],
            n_groups: 0,
            n_symbols: 0,
        }
    }
}

// ── Encoding ───────────────────────────────────────────────────────────────

/// Generate Huffman tables from symbol frequencies.
///
/// For simplicity, we generate a single table (n_groups=1) with
/// length-limited Huffman codes. bz2 allows up to 6 tables, but for
/// small embedded payloads one table is sufficient and much simpler.
///
/// `freq[i]` is the frequency of symbol `i`.
/// `n_symbols` is the total number of symbols (including EOB).
pub fn generate_tables(
    freq: &[u32],
    n_symbols: usize,
    tables: &mut HuffTables,
) {
    tables.n_symbols = n_symbols;
    tables.n_groups = 1;

    // Simple length-limited Huffman via the "package-merge" approximation:
    // We assign code lengths based on symbol frequency ranking.
    // This is a simplification — for optimal compression we'd use full
    // package-merge, but for correctness we just need valid prefix codes
    // with lengths ≤ MAX_CODE_LEN.

    // Collect (freq, symbol_index) pairs and sort by frequency descending.
    let mut sorted: [(u32, u16); MAX_SYMBOLS] = [(0, 0); MAX_SYMBOLS];
    for i in 0..n_symbols {
        sorted[i] = (freq[i], i as u16);
    }
    // Simple insertion sort (n_symbols ≤ 258, so this is fine)
    for i in 1..n_symbols {
        let key = sorted[i];
        let mut j = i;
        while j > 0 && sorted[j - 1].0 < key.0 {
            sorted[j] = sorted[j - 1];
            j -= 1;
        }
        sorted[j] = key;
    }

    // Assign code lengths using a simple heuristic:
    // Split symbols into buckets of exponentially increasing length.
    // This produces valid codes that are reasonably close to optimal.
    let table = &mut tables.tables[0];
    table.n_symbols = n_symbols;

    if n_symbols <= 2 {
        for i in 0..n_symbols {
            table.lengths[sorted[i].1 as usize] = 1;
        }
    } else {
        // Use a simple approach: compute ideal lengths from frequencies,
        // then clamp to [MIN_CODE_LEN, MAX_CODE_LEN].
        let total_freq: u64 = freq[..n_symbols].iter().map(|&f| f as u64).sum();
        if total_freq == 0 {
            // All zero frequencies — assign uniform lengths
            let bits = log2_ceil(n_symbols as u32).max(1);
            for i in 0..n_symbols {
                table.lengths[i] = bits as u8;
            }
        } else {
            for i in 0..n_symbols {
                let f = freq[i] as u64;
                if f == 0 {
                    table.lengths[i] = MAX_CODE_LEN as u8;
                } else {
                    // Ideal length = -log2(f / total) = log2(total) - log2(f)
                    let ideal = if total_freq <= f {
                        1
                    } else {
                        // Ceiling division: ceil(total/f) so Shannon length rounds correctly
                        let ratio = ((total_freq + f - 1) / f) as u32;
                        log2_ceil(ratio).max(1)
                    };
                    let clamped = ideal.clamp(MIN_CODE_LEN, MAX_CODE_LEN);
                    table.lengths[i] = clamped as u8;
                }
            }
        }
    }

    // Kraft validity check: Σ 2^(MAX_LEN - l_i) must be ≤ 2^MAX_LEN.
    // If over-full (shouldn't happen after ceil fix, but safety net),
    // increment shortest codes until valid. Zero extra allocation.
    let kraft_limit = 1u32 << MAX_CODE_LEN;
    loop {
        let mut kraft_sum = 0u32;
        for i in 0..n_symbols {
            let l = table.lengths[i] as u32;
            if l > 0 && l <= MAX_CODE_LEN {
                kraft_sum = kraft_sum.saturating_add(1u32 << (MAX_CODE_LEN - l));
            }
        }
        if kraft_sum <= kraft_limit {
            break;
        }
        // Over-full: find the shortest code and increment it by 1
        let mut min_len = MAX_CODE_LEN as u8;
        let mut min_idx = 0;
        for i in 0..n_symbols {
            if table.lengths[i] > 0 && table.lengths[i] < min_len {
                min_len = table.lengths[i];
                min_idx = i;
            }
        }
        table.lengths[min_idx] += 1;
    }

    // Build canonical codes
    let _ = table.build_codes();
}

/// Ceil(log2(n)) for n > 0.
fn log2_ceil(n: u32) -> u32 {
    if n <= 1 {
        return 0;
    }
    32 - (n - 1).leading_zeros()
}

// ── Bitstream Writing ──────────────────────────────────────────────────────

/// Write Huffman tables to the bitstream (delta-encoded code lengths).
pub fn write_tables(writer: &mut BitWriter, tables: &HuffTables) -> Result<(), Error> {
    let n_groups = tables.n_groups;
    let n_symbols = tables.n_symbols;

    for g in 0..n_groups {
        let table = &tables.tables[g];
        let mut current_len = table.lengths[0] as i32;
        writer.write_bits(5, current_len as u32)?;

        for i in 0..n_symbols {
            let target_len = table.lengths[i] as i32;
            while current_len < target_len {
                writer.write_bits(2, 0b10)?; // increment: 1,0
                current_len += 1;
            }
            while current_len > target_len {
                writer.write_bits(2, 0b11)?; // decrement: 1,1
                current_len -= 1;
            }
            writer.write_bit(0)?; // done adjusting this symbol
        }
    }

    Ok(())
}

/// Write selectors to the bitstream (MTF-encoded, unary).
pub fn write_selectors(
    writer: &mut BitWriter,
    selectors: &[u8],
    n_selectors: usize,
    n_groups: usize,
) -> Result<(), Error> {
    // MTF-encode the selectors
    let mut mtf_list = [0u8; MAX_GROUPS];
    for i in 0..n_groups {
        mtf_list[i] = i as u8;
    }

    for i in 0..n_selectors {
        let sel = selectors[i];
        // Find position in MTF list
        let mut pos = 0;
        while pos < n_groups && mtf_list[pos] != sel {
            pos += 1;
        }

        // Move to front
        if pos > 0 {
            let ch = mtf_list[pos];
            let mut j = pos;
            while j > 0 {
                mtf_list[j] = mtf_list[j - 1];
                j -= 1;
            }
            mtf_list[0] = ch;
        }

        // Write as unary: pos ones followed by a zero
        for _ in 0..pos {
            writer.write_bit(1)?;
        }
        writer.write_bit(0)?;
    }

    Ok(())
}

// ── Bitstream Reading (Decompression) ──────────────────────────────────────

/// Read Huffman tables from the bitstream (delta-encoded code lengths).
pub fn read_tables(
    reader: &mut BitReader,
    n_groups: usize,
    n_symbols: usize,
    tables: &mut HuffTables,
) -> Result<(), Error> {
    tables.n_groups = n_groups;
    tables.n_symbols = n_symbols;

    for g in 0..n_groups {
        let table = &mut tables.tables[g];
        table.n_symbols = n_symbols;

        let mut current_len = reader.read_bits(5)? as i32;

        for i in 0..n_symbols {
            loop {
                if current_len < MIN_CODE_LEN as i32 || current_len > MAX_CODE_LEN as i32 {
                    return Err(Error::BadHuffmanTable);
                }

                let bit = reader.read_bit()?;
                if bit == 0 {
                    break; // done adjusting
                }
                let bit2 = reader.read_bit()?;
                if bit2 == 0 {
                    current_len += 1; // 1,0 = increment
                } else {
                    current_len -= 1; // 1,1 = decrement
                }
            }

            table.lengths[i] = current_len as u8;
        }

        table.build_codes()?;
    }

    Ok(())
}

/// Read selectors from the bitstream.
pub fn read_selectors(
    reader: &mut BitReader,
    n_selectors: usize,
    n_groups: usize,
    selectors: &mut [u8],
) -> Result<(), Error> {
    // MTF state for selector decoding
    let mut mtf_list = [0u8; MAX_GROUPS];
    for i in 0..n_groups {
        mtf_list[i] = i as u8;
    }

    for i in 0..n_selectors {
        // Read unary: count ones until a zero
        let mut pos = 0usize;
        while reader.read_bool()? {
            pos += 1;
            if pos >= n_groups {
                return Err(Error::BadSelector);
            }
        }

        // MTF decode
        let sel = mtf_list[pos];
        if pos > 0 {
            let mut j = pos;
            while j > 0 {
                mtf_list[j] = mtf_list[j - 1];
                j -= 1;
            }
            mtf_list[0] = sel;
        }

        selectors[i] = sel;
    }

    Ok(())
}

/// Decode symbols from the bitstream using the Huffman tables.
///
/// Reads symbols one at a time until EOB is encountered.
/// `selectors[i]` specifies which table to use for symbol group `i`.
///
/// Returns the decoded symbol stream (excluding EOB) in `symbols`,
/// and the count of symbols decoded.
pub fn decode_symbols(
    reader: &mut BitReader,
    tables: &HuffTables,
    selectors: &[u8],
    n_selectors: usize,
    symbols: &mut [u16],
    max_symbols: usize,
) -> Result<usize, Error> {
    let eob = tables.n_symbols as u16 - 1;
    let mut out_pos = 0;
    let mut group_idx = 0;
    let mut sym_in_group = 0;

    loop {
        if group_idx >= n_selectors {
            return Err(Error::BadSelector);
        }

        let table_idx = selectors[group_idx] as usize;
        if table_idx >= tables.n_groups {
            return Err(Error::BadSelector);
        }

        let table = &tables.tables[table_idx];

        // Decode one symbol using this table's Huffman tree.
        // We do bit-by-bit canonical Huffman decoding.
        let sym = decode_one_symbol(reader, table)?;

        if sym == eob {
            break;
        }

        if out_pos >= max_symbols {
            return Err(Error::RleOverflow);
        }

        symbols[out_pos] = sym;
        out_pos += 1;

        sym_in_group += 1;
        if sym_in_group >= GROUP_SIZE {
            sym_in_group = 0;
            group_idx += 1;
        }
    }

    Ok(out_pos)
}

/// Decode a single Huffman symbol from the bitstream.
///
/// Uses canonical Huffman decoding: read bits one at a time, accumulate
/// a code value, and check against the canonical code ranges.
fn decode_one_symbol(reader: &mut BitReader, table: &HuffTable) -> Result<u16, Error> {
    // Build decoding limits for canonical codes.
    // For each length L, we know the first code of that length and
    // the number of symbols with that length.
    //
    // This is done on-the-fly to avoid precomputing and storing limits.

    let mut code = 0u32;
    let mut first_code = [0u32; (MAX_CODE_LEN + 1) as usize];
    let mut first_symbol = [0u16; (MAX_CODE_LEN + 1) as usize];
    let mut counts = [0u32; (MAX_CODE_LEN + 1) as usize];

    // Count symbols per length
    for i in 0..table.n_symbols {
        let l = table.lengths[i] as usize;
        counts[l] += 1;
    }

    // Build sorted symbol list by (length, symbol_index)
    // We need to map back from canonical position to symbol index.
    let mut sorted_symbols = [0u16; MAX_SYMBOLS];
    let mut pos = 0;
    for l in (MIN_CODE_LEN as usize)..=(MAX_CODE_LEN as usize) {
        first_code[l] = code;
        first_symbol[l] = pos as u16;
        for sym in 0..table.n_symbols {
            if table.lengths[sym] as usize == l {
                sorted_symbols[pos] = sym as u16;
                pos += 1;
            }
        }
        code = (code + counts[l]) << 1;
    }

    // Now decode: read bits and find which length/symbol matches
    let mut value = 0u32;
    for l in (MIN_CODE_LEN as usize)..=(MAX_CODE_LEN as usize) {
        value = (value << 1) | reader.read_bit()? as u32;
        if counts[l] > 0 && value >= first_code[l] && value < first_code[l] + counts[l] {
            let offset = (value - first_code[l]) as usize;
            return Ok(sorted_symbols[first_symbol[l] as usize + offset]);
        }
    }

    Err(Error::BadHuffmanTable)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn log2_ceil_values() {
        assert_eq!(log2_ceil(1), 0);
        assert_eq!(log2_ceil(2), 1);
        assert_eq!(log2_ceil(3), 2);
        assert_eq!(log2_ceil(4), 2);
        assert_eq!(log2_ceil(5), 3);
        assert_eq!(log2_ceil(256), 8);
    }

    #[test]
    fn build_simple_codes() {
        let mut table = HuffTable::new();
        table.n_symbols = 4;
        table.lengths[0] = 1;
        table.lengths[1] = 2;
        table.lengths[2] = 3;
        table.lengths[3] = 3;

        table.build_codes().unwrap();

        // Canonical codes for lengths [1,2,3,3]:
        // Symbol 0: length 1, code 0
        // Symbol 1: length 2, code 10
        // Symbol 2: length 3, code 110
        // Symbol 3: length 3, code 111
        assert_eq!(table.codes[0], 0b0);
        assert_eq!(table.codes[1], 0b10);
        assert_eq!(table.codes[2], 0b110);
        assert_eq!(table.codes[3], 0b111);
    }
}