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