| 1 |
use crate::utils::const_min_usize; |
| 2 |
|
| 3 |
/// Number of symbols in each Huffman code. Note: for the literal/length |
| 4 |
/// and offset codes, these are actually the maximum values; a given block |
| 5 |
/// might use fewer symbols. |
| 6 |
pub const DEFLATE_NUM_PRECODE_SYMS: usize = 19; |
| 7 |
pub const DEFLATE_NUM_LITLEN_SYMS: usize = 288; |
| 8 |
pub const DEFLATE_NUM_OFFSET_SYMS: usize = 32; |
| 9 |
|
| 10 |
/// Maximum possible overrun when decoding codeword lengths |
| 11 |
pub const DELFATE_MAX_LENS_OVERRUN: usize = 137; |
| 12 |
|
| 13 |
/// Order which precode lengths are stored |
| 14 |
pub static DEFLATE_PRECODE_LENS_PERMUTATION: [u8; DEFLATE_NUM_PRECODE_SYMS] = [ |
| 15 |
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 |
| 16 |
]; |
| 17 |
|
| 18 |
pub const PRECODE_ENOUGH: usize = 128; |
| 19 |
|
| 20 |
/// Maximum codeword length across all codes. |
| 21 |
pub const DEFLATE_MAX_CODEWORD_LENGTH: usize = 15; |
| 22 |
|
| 23 |
pub const DEFLATE_MAX_OFFSET_CODEWORD_LENGTH: usize = 15; |
| 24 |
pub const DEFLATE_MAX_LITLEN_CODEWORD_LENGTH: usize = 15; |
| 25 |
|
| 26 |
pub const PRECODE_TABLE_BITS: usize = 7; |
| 27 |
|
| 28 |
pub const LITLEN_TABLE_BITS: usize = 11; |
| 29 |
pub const LITLEN_ENOUGH: usize = 2342; |
| 30 |
/// Maximum bits found in the lookup table for offsets |
| 31 |
/// offsets larger than this require a lookup into a sub-table |
| 32 |
pub const OFFSET_TABLEBITS: usize = 8; |
| 33 |
/// Note, default libdeflate value is 402, but with 512, |
| 34 |
/// we can remove a branch check by simply doing & 511, and I'll take that. |
| 35 |
pub const OFFSET_ENOUGH: usize = 512; |
| 36 |
/// Maximum number of symbols across all codes |
| 37 |
pub const DEFLATE_MAX_NUM_SYMS: usize = 288; |
| 38 |
|
| 39 |
///Maximum codeword length in bits for each precode |
| 40 |
pub const DEFLATE_MAX_PRE_CODEWORD_LEN: u8 = 7; |
| 41 |
|
| 42 |
/// Format for precode decode table entries, Bits not explicitly contain zeroes |
| 43 |
/// |
| 44 |
/// 20-16: presym |
| 45 |
/// 10-8 Codeword length(not used) |
| 46 |
/// Bit 2-0 Codeword length |
| 47 |
/// |
| 48 |
/// It never has sub-tables since we use PRECODE_TABLEBITS == MAX_PRECODEWORD_LENGTH |
| 49 |
/// |
| 50 |
/// PRECODE_DECODE_RESULTS contains static parts of the entry for each symbol, |
| 51 |
/// make_decode_table_entry produces the final results |
| 52 |
pub static PRECODE_DECODE_RESULTS: [u32; 19] = make_precode_static_table(); |
| 53 |
|
| 54 |
const fn make_precode_static_table() -> [u32; 19] |
| 55 |
{ |
| 56 |
let mut table: [u32; 19] = [0; 19]; |
| 57 |
let mut i = 0; |
| 58 |
|
| 59 |
while i < 19 |
| 60 |
{ |
| 61 |
table[i] = (i as u32) << 16; |
| 62 |
i += 1; |
| 63 |
} |
| 64 |
|
| 65 |
table |
| 66 |
} |
| 67 |
|
| 68 |
/// Presence of a literal entry |
| 69 |
pub const HUFFDEC_LITERAL: u32 = 0x80000000; |
| 70 |
/// Presence of HUFFDEC_SUITABLE_POINTER or HUFFDEC_END_OF_BLOCK |
| 71 |
pub const HUFFDEC_EXCEPTIONAL: u32 = 0x00008000; |
| 72 |
/// Pointer entry in the litlen or offset decode table |
| 73 |
pub const HUFFDEC_SUITABLE_POINTER: u32 = 0x00004000; |
| 74 |
/// End of block entry in litlen decode table |
| 75 |
pub const HUFFDEC_END_OF_BLOCK: u32 = 0x00002000; |
| 76 |
|
| 77 |
#[rustfmt::skip] |
| 78 |
#[allow(clippy::zero_prefixed_literal)] |
| 79 |
const fn construct_litlen_decode_table() -> [u32; 288] |
| 80 |
{ |
| 81 |
let mut results: [u32; 288] = [0; 288]; |
| 82 |
let mut i = 0; |
| 83 |
|
| 84 |
while i < 256 |
| 85 |
{ |
| 86 |
results[i] = ((i as u32) << 16) | HUFFDEC_LITERAL; |
| 87 |
i += 1; |
| 88 |
} |
| 89 |
|
| 90 |
results[i] = HUFFDEC_EXCEPTIONAL | HUFFDEC_END_OF_BLOCK; |
| 91 |
i += 1; |
| 92 |
|
| 93 |
|
| 94 |
let base_and_bits_tables = [ |
| 95 |
(003, 0), (004, 0), (005, 0), (006, 0), |
| 96 |
(007, 0), (008, 0), (009, 0), (010, 0), |
| 97 |
(011, 1), (013, 1), (015, 1), (017, 1), |
| 98 |
(019, 2), (023, 2), (027, 2), (031, 2), |
| 99 |
(035, 3), (043, 3), (051, 3), (059, 3), |
| 100 |
(067, 4), (083, 4), (099, 4), (115, 4), |
| 101 |
(131, 5), (163, 5), (195, 5), (227, 5), |
| 102 |
(258, 0), (258, 0), (258, 0), |
| 103 |
]; |
| 104 |
let mut j = 0; |
| 105 |
|
| 106 |
while i < 288 |
| 107 |
{ |
| 108 |
let (length_base, extra_bits) = base_and_bits_tables[j]; |
| 109 |
results[i] = (length_base << 16) | extra_bits; |
| 110 |
|
| 111 |
i += 1; |
| 112 |
j += 1; |
| 113 |
} |
| 114 |
|
| 115 |
results |
| 116 |
} |
| 117 |
|
| 118 |
const fn entry(base: u32, extra: u32) -> u32 |
| 119 |
{ |
| 120 |
base << 16 | extra |
| 121 |
} |
| 122 |
|
| 123 |
#[rustfmt::skip] |
| 124 |
#[allow(clippy::zero_prefixed_literal)] // the things we do for alignment |
| 125 |
pub static OFFSET_DECODE_RESULTS: [u32; 32] = [ |
| 126 |
entry(00001, 00), entry(00002, 00), entry(00003, 00), entry(00004, 00), |
| 127 |
entry(00005, 01), entry(00007, 01), entry(00009, 02), entry(00013, 02), |
| 128 |
entry(00017, 03), entry(00025, 03), entry(00033, 04), entry(00049, 04), |
| 129 |
entry(00065, 05), entry(00097, 05), entry(00129, 06), entry(00193, 06), |
| 130 |
entry(00257, 07), entry(00385, 07), entry(00513, 08), entry(00769, 08), |
| 131 |
entry(01025, 09), entry(01537, 09), entry(02049, 10), entry(03073, 10), |
| 132 |
entry(04097, 11), entry(06145, 11), entry(08193, 12), entry(12289, 12), |
| 133 |
entry(16385, 13), entry(24577, 13), entry(24577, 13), entry(24577, 13), |
| 134 |
]; |
| 135 |
|
| 136 |
pub static LITLEN_DECODE_RESULTS: [u32; 288] = construct_litlen_decode_table(); |
| 137 |
|
| 138 |
pub const DEFLATE_BLOCKTYPE_DYNAMIC_HUFFMAN: u64 = 2; |
| 139 |
|
| 140 |
pub const DEFLATE_BLOCKTYPE_UNCOMPRESSED: u64 = 0; |
| 141 |
pub const DEFLATE_BLOCKTYPE_RESERVED: u64 = 3; |
| 142 |
|
| 143 |
pub const DEFLATE_BLOCKTYPE_STATIC: u64 = 1; |
| 144 |
|
| 145 |
pub const LITLEN_DECODE_BITS: usize = |
| 146 |
const_min_usize(DEFLATE_MAX_LITLEN_CODEWORD_LENGTH, LITLEN_TABLE_BITS); |
| 147 |
|
| 148 |
/// Maximum length of a deflate match |
| 149 |
pub const DEFLATE_MAX_MATCH_LEN: usize = 258; |
| 150 |
|
| 151 |
/// Number of bytes copied per every loop |
| 152 |
pub const FASTCOPY_BYTES: usize = 16; |
| 153 |
|
| 154 |
/// Worst case maximum number of output bytes writtern during each iteration of the |
| 155 |
/// fastloop. |
| 156 |
pub const FASTLOOP_MAX_BYTES_WRITTEN: usize = 6 + DEFLATE_MAX_MATCH_LEN + (2 * FASTCOPY_BYTES); |