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#![forbid(unsafe_code)]
22#![warn(missing_docs)]
23
24mod compress;
25mod decompress;
26mod huffman;
27mod tables;
28
29pub use compress::{compress_to_vec, Compressor, StoredOnlyCompressor};
30pub use decompress::{
31 decompress_to_vec, decompress_to_vec_bounded, BoundedDecompressionError, DecompressionError,
32 Decompressor,
33};
34
35/// Build a length limited huffman tree.
36///
37/// Dynamic programming algorithm from fpnge.
38#[doc(hidden)]
39pub fn compute_code_lengths(
40 freqs: &[u64],
41 min_limit: &[u8],
42 max_limit: &[u8],
43 calculated_nbits: &mut [u8],
44) {
45 debug_assert_eq!(freqs.len(), min_limit.len());
46 debug_assert_eq!(freqs.len(), max_limit.len());
47 debug_assert_eq!(freqs.len(), calculated_nbits.len());
48 let len = freqs.len();
49
50 for i in 0..len {
51 debug_assert!(min_limit[i] >= 1);
52 debug_assert!(min_limit[i] <= max_limit[i]);
53 }
54
55 let precision = *max_limit.iter().max().unwrap();
56 let num_patterns = 1 << precision;
57
58 let mut dynp = vec![u64::MAX; (num_patterns + 1) * (len + 1)];
59 let index = |sym: usize, off: usize| sym * (num_patterns + 1) + off;
60
61 dynp[index(0, 0)] = 0;
62 for sym in 0..len {
63 for bits in min_limit[sym]..=max_limit[sym] {
64 let off_delta = 1 << (precision - bits);
65 for off in 0..=num_patterns.saturating_sub(off_delta) {
66 dynp[index(sym + 1, off + off_delta)] = dynp[index(sym, off)]
67 .saturating_add(freqs[sym] * u64::from(bits))
68 .min(dynp[index(sym + 1, off + off_delta)]);
69 }
70 }
71 }
72
73 let mut sym = len;
74 let mut off = num_patterns;
75
76 while sym > 0 {
77 sym -= 1;
78 assert!(off > 0);
79
80 for bits in min_limit[sym]..=max_limit[sym] {
81 let off_delta = 1 << (precision - bits);
82 if off_delta <= off
83 && dynp[index(sym + 1, off)]
84 == dynp[index(sym, off - off_delta)]
85 .saturating_add(freqs[sym] * u64::from(bits))
86 {
87 off -= off_delta;
88 calculated_nbits[sym] = bits;
89 break;
90 }
91 }
92 }
93
94 for i in 0..len {
95 debug_assert!(calculated_nbits[i] >= min_limit[i]);
96 debug_assert!(calculated_nbits[i] <= max_limit[i]);
97 }
98}
99
100const fn compute_codes<const NSYMS: usize>(lengths: &[u8; NSYMS]) -> Option<[u16; NSYMS]> {
101 let mut codes = [0u16; NSYMS];
102
103 let mut code = 0u32;
104
105 let mut len = 1;
106 while len <= 16 {
107 let mut i = 0;
108 while i < lengths.len() {
109 if lengths[i] == len {
110 codes[i] = (code as u16).reverse_bits() >> (16 - len);
111 code += 1;
112 }
113 i += 1;
114 }
115 code <<= 1;
116 len += 1;
117 }
118
119 if code == 2 << 16 {
120 Some(codes)
121 } else {
122 None
123 }
124}
125