Debian Codegraph @

.cargo/vendor/fdeflate/src/lib.rs

raw
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 }