ai_fdeflate/
lib.rs

1//! A fast deflate implementation.
2//!
3//! This crate contains an optimized implementation of the deflate algorithm tuned to compress PNG
4//! images. It is compatible with standard zlib, but make a bunch of simplifying assumptions that
5//! drastically improve encoding performance:
6//!
7//! - Exactly one block per deflate stream.
8//! - No distance codes except for run length encoding of zeros.
9//! - A single fixed huffman tree trained on a large corpus of PNG images.
10//! - All huffman codes are 12 bits or less.
11//!
12//! It also contains a fast decompressor that supports arbitrary zlib streams but does especially
13//! well on streams that meet the above assumptions.
14//!
15//! # Inspiration
16//!
17//! The algorithms in this crate take inspiration from multiple sources:
18//! * [fpnge](https://github.com/veluca93/fpnge)
19//! * [zune-inflate](https://github.com/etemesi254/zune-image/tree/main/zune-inflate)
20//! * [RealTime Data Compression blog](https://fastcompression.blogspot.com/2015/10/huffman-revisited-part-4-multi-bytes.html)
21#![cfg_attr(not(feature = "std"), no_std)]
22#![forbid(unsafe_code)]
23#![warn(missing_docs)]
24
25extern crate alloc;
26
27use alloc::vec;
28
29pub(crate) use no_std_io::io;
30
31mod compress;
32mod decompress;
33mod huffman;
34mod tables;
35
36pub use compress::{
37    compress_to_vec, compress_to_vec_rle, compress_to_vec_ultra_fast, compress_to_vec_with_level,
38    Compressor, StoredOnlyCompressor, UltraFastCompressor,
39};
40pub use decompress::{
41    decompress_to_vec, decompress_to_vec_bounded, BoundedDecompressionError, DecompressionError,
42    Decompressor,
43};
44
45/// Build a length limited huffman tree.
46///
47/// Dynamic programming algorithm from fpnge.
48#[doc(hidden)]
49pub fn compute_code_lengths(
50    freqs: &[u64],
51    min_limit: &[u8],
52    max_limit: &[u8],
53    calculated_nbits: &mut [u8],
54) {
55    debug_assert_eq!(freqs.len(), min_limit.len());
56    debug_assert_eq!(freqs.len(), max_limit.len());
57    debug_assert_eq!(freqs.len(), calculated_nbits.len());
58    let len = freqs.len();
59
60    for i in 0..len {
61        debug_assert!(min_limit[i] >= 1);
62        debug_assert!(min_limit[i] <= max_limit[i]);
63    }
64
65    let precision = *max_limit.iter().max().unwrap();
66    let num_patterns = 1 << precision;
67
68    let mut dynp = vec![u64::MAX; (num_patterns + 1) * (len + 1)];
69    let index = |sym: usize, off: usize| sym * (num_patterns + 1) + off;
70
71    dynp[index(0, 0)] = 0;
72    for sym in 0..len {
73        for bits in min_limit[sym]..=max_limit[sym] {
74            let off_delta = 1 << (precision - bits);
75            for off in 0..=num_patterns.saturating_sub(off_delta) {
76                dynp[index(sym + 1, off + off_delta)] = dynp[index(sym, off)]
77                    .saturating_add(freqs[sym] * u64::from(bits))
78                    .min(dynp[index(sym + 1, off + off_delta)]);
79            }
80        }
81    }
82
83    let mut sym = len;
84    let mut off = num_patterns;
85
86    while sym > 0 {
87        sym -= 1;
88        assert!(off > 0);
89
90        for bits in min_limit[sym]..=max_limit[sym] {
91            let off_delta = 1 << (precision - bits);
92            if off_delta <= off
93                && dynp[index(sym + 1, off)]
94                    == dynp[index(sym, off - off_delta)]
95                        .saturating_add(freqs[sym] * u64::from(bits))
96            {
97                off -= off_delta;
98                calculated_nbits[sym] = bits;
99                break;
100            }
101        }
102    }
103
104    for i in 0..len {
105        debug_assert!(calculated_nbits[i] >= min_limit[i]);
106        debug_assert!(calculated_nbits[i] <= max_limit[i]);
107    }
108}
109
110const fn compute_codes<const NSYMS: usize>(lengths: &[u8; NSYMS]) -> Option<[u16; NSYMS]> {
111    let mut codes = [0u16; NSYMS];
112
113    let mut code = 0u32;
114
115    let mut len = 1;
116    while len <= 16 {
117        let mut i = 0;
118        while i < lengths.len() {
119            if lengths[i] == len {
120                codes[i] = (code as u16).reverse_bits() >> (16 - len);
121                code += 1;
122            }
123            i += 1;
124        }
125        code <<= 1;
126        len += 1;
127    }
128
129    if code == 2 << 16 {
130        Some(codes)
131    } else {
132        None
133    }
134}
ai_fdeflate/lib.rs

ai_fdeflate/
lib.rs
