1use crate::decompress::{EXCEPTIONAL_ENTRY, LITERAL_ENTRY};
2
3/// Hard-coded Huffman codes used regardless of the input.
4///
5/// These values work well for PNGs with some form of filtering enabled, but will likely make most
6/// other inputs worse.
7pub(crate) const HUFFMAN_LENGTHS: [u8; 286] = [
8 2, 3, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10,
9 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
10 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
11 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
12 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
13 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
14 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
15 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
16 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11,
17 11, 11, 11, 10, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 8, 9, 8, 8, 8, 8, 8, 7,
18 7, 7, 6, 6, 6, 5, 4, 3, 12, 12, 12, 9, 9, 11, 10, 11, 11, 10, 11, 11, 11, 11, 11, 11, 12, 11,
19 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 9,
20];
21
22pub(crate) const HUFFMAN_CODES: [u16; 286] = match crate::compute_codes(&HUFFMAN_LENGTHS) {
23 Some(codes: [u16; 286]) => codes,
24 None => panic!("HUFFMAN_LENGTHS is invalid"),
25};
26
27/// Length code for length values (derived from deflate spec).
28pub(crate) const LENGTH_TO_SYMBOL: [u16; 256] = [
29 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268, 269, 269, 269,
30 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272, 273, 273, 273, 273, 273, 273,
31 273, 273, 274, 274, 274, 274, 274, 274, 274, 274, 275, 275, 275, 275, 275, 275, 275, 275, 276,
32 276, 276, 276, 276, 276, 276, 276, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277,
33 277, 277, 277, 277, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278,
34 278, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 280, 280,
35 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 281, 281, 281, 281, 281,
36 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,
37 281, 281, 281, 281, 281, 281, 281, 281, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
38 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
39 282, 282, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,
40 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 284, 284, 284, 284,
41 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284,
42 284, 284, 284, 284, 284, 284, 284, 284, 285,
43];
44
45/// Number of extra bits for length values (derived from deflate spec).
46pub(crate) const LENGTH_TO_LEN_EXTRA: [u8; 256] = [
47 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
48 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
49 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
50 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
51 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
52 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
53 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
54 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0,
55];
56
57pub(crate) const BITMASKS: [u32; 17] = [
58 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF,
59 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF,
60];
61
62/// Order of the length code length alphabet (derived from deflate spec).
63pub(crate) const CLCL_ORDER: [usize; 19] = [
64 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
65];
66
67/// Number of extra bits for each length code (derived from deflate spec).
68pub(crate) const LEN_SYM_TO_LEN_EXTRA: [u8; 29] = [
69 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
70];
71
72/// The base length for each length code (derived from deflate spec).
73pub(crate) const LEN_SYM_TO_LEN_BASE: [usize; 29] = [
74 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131,
75 163, 195, 227, 258,
76];
77
78/// Number of extra bits for each distance code (derived from deflate spec.)
79pub(crate) const DIST_SYM_TO_DIST_EXTRA: [u8; 30] = [
80 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13,
81 13,
82];
83
84/// The base distance for each distance code (derived from deflate spec).
85pub(crate) const DIST_SYM_TO_DIST_BASE: [u16; 30] = [
86 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537,
87 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
88];
89
90/// The main litlen_table uses a 12-bit input to lookup the meaning of the symbol. The table is
91/// split into 4 sections:
92///
93/// aaaaaaaa_bbbbbbbb_1000yyyy_0000xxxx x = input_advance_bits, y = output_advance_bytes (literal)
94/// 0000000z_zzzzzzzz_00000yyy_0000xxxx x = input_advance_bits, y = extra_bits, z = distance_base (length)
95/// 00000000_00000000_01000000_0000xxxx x = input_advance_bits (EOF)
96/// 0000xxxx_xxxxxxxx_01100000_00000000 x = secondary_table_index
97/// 00000000_00000000_01000000_00000000 invalid code
98pub(crate) const LITLEN_TABLE_ENTRIES: [u32; 288] = {
99 let mut entries: [u32; 288] = [EXCEPTIONAL_ENTRY; 288];
100 let mut i: usize = 0;
101 while i < 256 {
102 entries[i] = (i as u32) << 16 | LITERAL_ENTRY | (1 << 8);
103 i += 1;
104 }
105
106 let mut i: usize = 257;
107 while i < 286 {
108 entries[i] = (LEN_SYM_TO_LEN_BASE[i - 257] as u32) << 16
109 | (LEN_SYM_TO_LEN_EXTRA[i - 257] as u32) << 8;
110 i += 1;
111 }
112 entries
113};
114
115/// The distance table is a 512-entry table that maps 9 bits of distance symbols to their meaning.
116///
117/// 00000000_00000000_00000000_00000000 symbol is more than 9 bits
118/// zzzzzzzz_zzzzzzzz_0000yyyy_0000xxxx x = input_advance_bits, y = extra_bits, z = distance_base
119pub(crate) const DISTANCE_TABLE_ENTRIES: [u32; 32] = {
120 let mut entries: [u32; 32] = [0; 32];
121 let mut i: usize = 0;
122 while i < 30 {
123 entries[i] = (DIST_SYM_TO_DIST_BASE[i] as u32) << 16
124 | (DIST_SYM_TO_DIST_EXTRA[i] as u32) << 8
125 | LITERAL_ENTRY;
126 i += 1;
127 }
128 entries
129};
130
131pub(crate) const FIXED_LITLEN_TABLE: [u32; 512] = [
132 16391, 5275912, 1081608, 7537672, 2032135, 7373064, 3178760, 12615945, 655367, 6324488,
133 2130184, 10518793, 33032, 8421640, 4227336, 14713097, 393223, 5800200, 1605896, 9470217,
134 3867399, 7897352, 3703048, 13664521, 1114375, 6848776, 2654472, 11567369, 557320, 8945928,
135 4751624, 15761673, 262151, 5538056, 1343752, 14877960, 2818823, 7635208, 3440904, 13140233,
136 852231, 6586632, 2392328, 11043081, 295176, 8683784, 4489480, 15237385, 524295, 6062344,
137 1868040, 9994505, 5440519, 8159496, 3965192, 14188809, 1507847, 7110920, 2916616, 12091657,
138 819464, 9208072, 5013768, 16285961, 196615, 5406984, 1212680, 10683656, 2294535, 7504136,
139 3309832, 12878089, 721159, 6455560, 2261256, 10780937, 164104, 8552712, 4358408, 14975241,
140 458759, 5931272, 1736968, 9732361, 4391943, 8028424, 3834120, 13926665, 1245703, 6979848,
141 2785544, 11829513, 688392, 9077000, 4882696, 16023817, 327687, 5669128, 1474824, 16392,
142 3343111, 7766280, 3571976, 13402377, 983303, 6717704, 2523400, 11305225, 426248, 8814856,
143 4620552, 15499529, 589831, 6193416, 1999112, 10256649, 6489095, 8290568, 4096264, 14450953,
144 1769991, 7241992, 3047688, 12353801, 950536, 9339144, 5144840, 16548105, 16391, 5341448,
145 1147144, 8586504, 2032135, 7438600, 3244296, 12747017, 655367, 6390024, 2195720, 10649865,
146 98568, 8487176, 4292872, 14844169, 393223, 5865736, 1671432, 9601289, 3867399, 7962888,
147 3768584, 13795593, 1114375, 6914312, 2720008, 11698441, 622856, 9011464, 4817160, 15892745,
148 262151, 5603592, 1409288, 16908296, 2818823, 7700744, 3506440, 13271305, 852231, 6652168,
149 2457864, 11174153, 360712, 8749320, 4555016, 15368457, 524295, 6127880, 1933576, 10125577,
150 5440519, 8225032, 4030728, 14319881, 1507847, 7176456, 2982152, 12222729, 885000, 9273608,
151 5079304, 16417033, 196615, 5472520, 1278216, 12780808, 2294535, 7569672, 3375368, 13009161,
152 721159, 6521096, 2326792, 10912009, 229640, 8618248, 4423944, 15106313, 458759, 5996808,
153 1802504, 9863433, 4391943, 8093960, 3899656, 14057737, 1245703, 7045384, 2851080, 11960585,
154 753928, 9142536, 4948232, 16154889, 327687, 5734664, 1540360, 16392, 3343111, 7831816, 3637512,
155 13533449, 983303, 6783240, 2588936, 11436297, 491784, 8880392, 4686088, 15630601, 589831,
156 6258952, 2064648, 10387721, 6489095, 8356104, 4161800, 14582025, 1769991, 7307528, 3113224,
157 12484873, 1016072, 9404680, 5210376, 16679177, 16391, 5275912, 1081608, 7537672, 2032135,
158 7373064, 3178760, 12681481, 655367, 6324488, 2130184, 10584329, 33032, 8421640, 4227336,
159 14778633, 393223, 5800200, 1605896, 9535753, 3867399, 7897352, 3703048, 13730057, 1114375,
160 6848776, 2654472, 11632905, 557320, 8945928, 4751624, 15827209, 262151, 5538056, 1343752,
161 14877960, 2818823, 7635208, 3440904, 13205769, 852231, 6586632, 2392328, 11108617, 295176,
162 8683784, 4489480, 15302921, 524295, 6062344, 1868040, 10060041, 5440519, 8159496, 3965192,
163 14254345, 1507847, 7110920, 2916616, 12157193, 819464, 9208072, 5013768, 16351497, 196615,
164 5406984, 1212680, 10683656, 2294535, 7504136, 3309832, 12943625, 721159, 6455560, 2261256,
165 10846473, 164104, 8552712, 4358408, 15040777, 458759, 5931272, 1736968, 9797897, 4391943,
166 8028424, 3834120, 13992201, 1245703, 6979848, 2785544, 11895049, 688392, 9077000, 4882696,
167 16089353, 327687, 5669128, 1474824, 16392, 3343111, 7766280, 3571976, 13467913, 983303,
168 6717704, 2523400, 11370761, 426248, 8814856, 4620552, 15565065, 589831, 6193416, 1999112,
169 10322185, 6489095, 8290568, 4096264, 14516489, 1769991, 7241992, 3047688, 12419337, 950536,
170 9339144, 5144840, 16613641, 16391, 5341448, 1147144, 8586504, 2032135, 7438600, 3244296,
171 12812553, 655367, 6390024, 2195720, 10715401, 98568, 8487176, 4292872, 14909705, 393223,
172 5865736, 1671432, 9666825, 3867399, 7962888, 3768584, 13861129, 1114375, 6914312, 2720008,
173 11763977, 622856, 9011464, 4817160, 15958281, 262151, 5603592, 1409288, 16908296, 2818823,
174 7700744, 3506440, 13336841, 852231, 6652168, 2457864, 11239689, 360712, 8749320, 4555016,
175 15433993, 524295, 6127880, 1933576, 10191113, 5440519, 8225032, 4030728, 14385417, 1507847,
176 7176456, 2982152, 12288265, 885000, 9273608, 5079304, 16482569, 196615, 5472520, 1278216,
177 12780808, 2294535, 7569672, 3375368, 13074697, 721159, 6521096, 2326792, 10977545, 229640,
178 8618248, 4423944, 15171849, 458759, 5996808, 1802504, 9928969, 4391943, 8093960, 3899656,
179 14123273, 1245703, 7045384, 2851080, 12026121, 753928, 9142536, 4948232, 16220425, 327687,
180 5734664, 1540360, 16392, 3343111, 7831816, 3637512, 13598985, 983303, 6783240, 2588936,
181 11501833, 491784, 8880392, 4686088, 15696137, 589831, 6258952, 2064648, 10453257, 6489095,
182 8356104, 4161800, 14647561, 1769991, 7307528, 3113224, 12550409, 1016072, 9404680, 5210376,
183 16744713,
184];
185
186pub(crate) const FIXED_DIST_TABLE: [u32; 32] = [
187 98309, 16877317, 1147653, 268536581, 360709, 67209477, 4293893, 1073843461, 229381, 33654789,
188 2196485, 536972293, 623109, 134318597, 8488453, 5, 163845, 25265925, 1671941, 402754309,
189 491781, 100763909, 6391045, 1610714373, 294917, 50432005, 3245061, 805407749, 885253,
190 201427461, 12682757, 5,
191];
192
193#[cfg(test)]
194pub(crate) const FIXED_CODE_LENGTHS: [u8; 320] = make_fixed_code_lengths();
195
196#[cfg(test)]
197const fn make_fixed_code_lengths() -> [u8; 320] {
198 let mut i = 0;
199 let mut lengths = [0; 320];
200 while i < 144 {
201 lengths[i] = 8;
202 i += 1;
203 }
204 while i < 256 {
205 lengths[i] = 9;
206 i += 1;
207 }
208 while i < 280 {
209 lengths[i] = 7;
210 i += 1;
211 }
212 while i < 288 {
213 lengths[i] = 8;
214 i += 1;
215 }
216 while i < 320 {
217 lengths[i] = 5;
218 i += 1;
219 }
220 lengths
221}
222