fdeflate/
tables.rs

Help
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) => 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 = [EXCEPTIONAL_ENTRY; 288];
100    let mut i = 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 = 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 = [0; 32];
121    let mut i = 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}
fdeflate/tables.rs

fdeflate/
tables.rs
