brotli_decompressor/huffman/
mod.rs

Help
1#![allow(non_snake_case)]
2#![allow(non_upper_case_globals)]
3mod tests;
4use ::core;
5use alloc;
6use alloc::Allocator;
7use alloc::SliceWrapper;
8use alloc::SliceWrapperMut;
9use core::default::Default;
10pub const BROTLI_HUFFMAN_MAX_CODE_LENGTH: usize = 15;
11
12// For current format this constant equals to kNumInsertAndCopyCodes
13pub const BROTLI_HUFFMAN_MAX_CODE_LENGTHS_SIZE: usize = 704;
14
15// Maximum possible Huffman table size for an alphabet size of (index * 32),
16// max code length 15 and root table bits 8.
17// pub const kMaxHuffmanTableSize : [u16;23] = [
18// 256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822,
19// 854, 886, 920, 952, 984, 1016, 1048, 1080, 1112, 1144,1176,1208,1240,272,
20// 1304, 1336, 1368, 1400, 1432, 1464, 1496, 1528];
21// pub const BROTLI_HUFFMAN_MAX_SIZE_26 : u32 = 396;
22// pub const BROTLI_HUFFMAN_MAX_SIZE_258 : u32 = 632;
23// pub const BROTLI_HUFFMAN_MAX_SIZE_272 : u32 = 646;
24//
25pub const BROTLI_HUFFMAN_MAX_TABLE_SIZE: u32 = 1080;
26pub const BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH: u32 = 5;
27
28#[repr(C)]
29#[derive(PartialEq, Copy, Clone, Debug)]
30pub struct HuffmanCode {
31  pub value: u16, // symbol value or table offset
32  pub bits: u8, // number of bits used for this symbol
33}
34
35impl HuffmanCode {
36  pub fn eq(&self, other: &Self) -> bool {
37    self.value == other.value && self.bits == other.bits
38  }
39}
40
41impl Default for HuffmanCode {
42  fn default() -> Self {
43    HuffmanCode {
44      value: 0,
45      bits: 0,
46    }
47  }
48}
49
50// Contains a collection of Huffman trees with the same alphabet size.
51pub struct HuffmanTreeGroup<Alloc32: Allocator<u32>, AllocHC: Allocator<HuffmanCode>> {
52  pub htrees: Alloc32::AllocatedMemory,
53  pub codes: AllocHC::AllocatedMemory,
54  pub alphabet_size: u16,
55  pub max_symbol: u16,
56  pub num_htrees: u16,
57}
58
59impl<AllocU32 : alloc::Allocator<u32>,
60     AllocHC : alloc::Allocator<HuffmanCode> > HuffmanTreeGroup<AllocU32, AllocHC> {
61    pub fn init(self : &mut Self, mut alloc_u32 : &mut AllocU32, mut alloc_hc : &mut AllocHC,
62                alphabet_size : u16, max_symbol: u16, ntrees : u16) {
63        self.reset(&mut alloc_u32, &mut alloc_hc);
64        self.alphabet_size = alphabet_size;
65        self.max_symbol = max_symbol;
66        self.num_htrees = ntrees;
67        let nt = ntrees as usize;
68        let _ = core::mem::replace(&mut self.htrees,
69                           alloc_u32.alloc_cell(nt));
70        let _ = core::mem::replace(&mut self.codes,
71                           alloc_hc.alloc_cell(nt * BROTLI_HUFFMAN_MAX_TABLE_SIZE as usize));
72    }
73
74//  pub fn get_tree_mut<'a>(self :&'a mut Self, index : u32, mut tree_out : &'a mut [HuffmanCode]) {
75//        let start : usize = fast!((self.htrees)[index as usize]) as usize;
76//        let _ = core::mem::replace(&mut tree_out, fast_mut!((self.codes.slice_mut())[start;]));
77//    }
78//    pub fn get_tree<'a>(self :&'a Self, index : u32, mut tree_out : &'a [HuffmanCode]) {
79//        let start : usize = fast!((self.htrees)[index as usize]) as usize;
80//        let _ = core::mem::replace(&mut tree_out, fast_slice!((self.codes)[start;]));
81//    }
82    #[allow(dead_code)]
83    pub fn get_tree_mut(&mut self, index : u32) -> &mut [HuffmanCode] {
84        let start : usize = fast_slice!((self.htrees)[index as usize]) as usize;
85        fast_mut!((self.codes.slice_mut())[start;])
86    }
87    #[allow(dead_code)]
88    pub fn get_tree(&self, index : u32) -> &[HuffmanCode] {
89        let start : usize = fast_slice!((self.htrees)[index as usize]) as usize;
90        fast_slice!((self.codes)[start;])
91    }
92    pub fn reset(self : &mut Self, alloc_u32 : &mut AllocU32, alloc_hc : &mut AllocHC) {
93        alloc_u32.free_cell(core::mem::replace(&mut self.htrees,
94                                               AllocU32::AllocatedMemory::default()));
95        alloc_hc.free_cell(core::mem::replace(&mut self.codes,
96                                              AllocHC::AllocatedMemory::default()));
97
98// for mut iter in self.htrees[0..self.num_htrees as usize].iter_mut() {
99//    if iter.slice().len() > 0 {
100//        alloc_hc.free_cell(core::mem::replace(&mut iter,
101//                                              AllocHC::AllocatedMemory::default()));
102//    }
103// }
104
105    }
106    pub fn build_hgroup_cache(&self) -> [&[HuffmanCode]; 256] {
107      let mut ret : [&[HuffmanCode]; 256] = [&[]; 256];
108      let mut index : usize = 0;
109      for htree in self.htrees.slice() {
110          ret[index] = fast_slice!((&self.codes)[*htree as usize ; ]);
111          index += 1;
112      }
113      ret
114    }
115}
116
117impl<AllocU32 : alloc::Allocator<u32>,
118     AllocHC : alloc::Allocator<HuffmanCode> > Default for HuffmanTreeGroup<AllocU32, AllocHC> {
119    fn default() -> Self {
120        HuffmanTreeGroup::<AllocU32, AllocHC> {
121          htrees : AllocU32::AllocatedMemory::default(),
122          codes : AllocHC::AllocatedMemory::default(),
123          max_symbol: 0,
124          alphabet_size : 0,
125          num_htrees : 0,
126        }
127    }
128}
129
130
131
132const BROTLI_REVERSE_BITS_MAX: usize = 8;
133
134const BROTLI_REVERSE_BITS_BASE: u8 = 0;
135const kReverseBits: [u8; (1 << BROTLI_REVERSE_BITS_MAX)] =
136  [0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
137   0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
138   0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
139   0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
140   0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
141   0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
142   0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
143   0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
144   0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
145   0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
146   0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
147   0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
148   0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
149   0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
150   0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
151   0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF];
152
153const BROTLI_REVERSE_BITS_LOWEST: u32 =
154  (1u32 << (BROTLI_REVERSE_BITS_MAX as u32 - 1 + BROTLI_REVERSE_BITS_BASE as u32));
155
156// Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
157// where reverse(value, len) is the bit-wise reversal of the len least
158// significant bits of value.
159fn BrotliReverseBits(num: u32) -> u32 {
160  fast!((kReverseBits)[num as usize]) as u32
161}
162
163// Stores code in table[0], table[step], table[2*step], ..., table[end]
164// Assumes that end is an integer multiple of step
165fn ReplicateValue(table: &mut [HuffmanCode],
166                  offset: u32,
167                  step: i32,
168                  mut end: i32,
169                  code: HuffmanCode) {
170  loop {
171    end -= step;
172    fast_mut!((table)[offset as usize + end as usize]) = code;
173    if end <= 0 {
174      break;
175    }
176  }
177}
178
179// Returns the table width of the next 2nd level table. count is the histogram
180// of bit lengths for the remaining symbols, len is the code length of the next
181// processed symbol
182fn NextTableBitSize(count: &[u16], mut len: i32, root_bits: i32) -> i32 {
183  let mut left: i32 = 1 << (len - root_bits);
184  while len < BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 {
185    left -= fast!((count)[len as usize]) as i32;
186    if left <= 0 {
187      break;
188    }
189    len += 1;
190    left <<= 1;
191  }
192  len - root_bits
193}
194
195
196pub fn BrotliBuildCodeLengthsHuffmanTable(mut table: &mut [HuffmanCode],
197                                          code_lengths: &[u8],
198                                          count: &[u16]) {
199  let mut sorted: [i32; 18] = fast_uninitialized![18];     /* symbols sorted by code length */
200  // offsets in sorted table for each length
201  let mut offset: [i32; (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1) as usize] =
202    fast_uninitialized![(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1) as usize];
203  assert!(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH as usize <= BROTLI_REVERSE_BITS_MAX as usize);
204
205  // generate offsets into sorted symbol table by code length
206  let mut symbol: i32 = -1;         /* symbol index in original or sorted table */
207  let mut bits: i32 = 1;
208  for _ in 0..BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH {
209    symbol += fast!((count)[bits as usize]) as i32;
210    fast_mut!((offset)[bits as usize]) = symbol;
211    bits += 1;
212  }
213  // Symbols with code length 0 are placed after all other symbols.
214  fast_mut!((offset)[0]) = 17;
215
216  // sort symbols by length, by symbol order within each length
217  symbol = 18;
218  loop {
219    for _ in 0..6 {
220      symbol -= 1;
221      let index = fast!((offset)[fast_inner!((code_lengths)[symbol as usize]) as usize]);
222      fast_mut!((offset)[fast_inner!((code_lengths)[symbol as usize]) as usize]) -= 1;
223      fast_mut!((sorted)[index as usize]) = symbol;
224    }
225    if symbol == 0 {
226      break;
227    }
228  }
229
230  const table_size: i32 = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
231
232  // Special case: all symbols but one have 0 code length.
233  if fast!((offset)[0]) == 0 {
234    let code: HuffmanCode = HuffmanCode {
235      bits: 0,
236      value: fast!((sorted)[0]) as u16,
237    };
238    for val in fast_mut!((table)[0 ; table_size as usize]).iter_mut() {
239      *val = code;
240    }
241    return;
242  }
243
244  // fill in table
245  let mut key: u32 = 0; /* prefix code */
246  let mut key_step: u32 = BROTLI_REVERSE_BITS_LOWEST; /* prefix code addend */
247  symbol = 0;
248  bits = 1;
249  let mut step: i32 = 2;
250  loop {
251    let mut code: HuffmanCode = HuffmanCode {
252      bits: (bits as u8),
253      value: 0,
254    };
255    let mut bits_count: i32 = fast!((count)[bits as usize]) as i32;
256
257    while bits_count != 0 {
258      code.value = fast!((sorted)[symbol as usize]) as u16;
259      symbol += 1;
260      ReplicateValue(&mut table, BrotliReverseBits(key), step, table_size, code);
261      key += key_step;
262      bits_count -= 1;
263    }
264    step <<= 1;
265    key_step >>= 1;
266    bits += 1;
267    if !(bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH as i32) {
268      break;
269    }
270  }
271}
272
273pub fn BrotliBuildHuffmanTable(mut root_table: &mut [HuffmanCode],
274                               root_bits: i32,
275                               symbol_lists: &[u16],
276                               symbol_lists_offset: usize, /* need negative-index to symbol_lists */
277                               count: &mut [u16])
278                               -> u32 {
279  let mut code: HuffmanCode = HuffmanCode {
280    bits: 0,
281    value: 0,
282  };       /* current table entry */
283  let mut max_length: i32 = -1;
284
285  assert!(root_bits as isize <= BROTLI_REVERSE_BITS_MAX as isize);
286  assert!(BROTLI_HUFFMAN_MAX_CODE_LENGTH as isize - root_bits as isize <=
287          BROTLI_REVERSE_BITS_MAX as isize);
288
289  while fast!((symbol_lists)[((symbol_lists_offset as isize) + max_length as isize) as usize]) ==
290        0xFFFF {
291    max_length -= 1;
292  }
293  max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 + 1;
294
295  let mut table_free_offset: u32 = 0;
296  let mut table_bits: i32 = root_bits;      /* key length of current table */
297  let mut table_size: i32 = 1 << table_bits;/* size of current table */
298  let mut total_size: i32 = table_size;     /* sum of root table size and 2nd level table sizes */
299
300  // fill in root table
301  // let's reduce the table size to a smaller size if possible, and
302  // create the repetitions by memcpy if possible in the coming loop
303  if table_bits > max_length {
304    table_bits = max_length;
305    table_size = 1 << table_bits;
306  }
307  let mut key: u32 = 0; /* prefix code */
308  let mut key_step: u32 = BROTLI_REVERSE_BITS_LOWEST; /* prefix code addend */
309  let mut bits: i32 = 1;
310  let mut step: i32 = 2; /* step size to replicate values in current table */
311  loop {
312    code.bits = bits as u8;
313    let mut symbol: i32 = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 + 1);
314    let mut bits_count: i32 = fast!((count)[bits as usize]) as i32;
315    while bits_count != 0 {
316      symbol =
317        fast!((symbol_lists)[(symbol_lists_offset as isize + symbol as isize) as usize]) as i32;
318      code.value = symbol as u16;
319      ReplicateValue(&mut root_table,
320                     table_free_offset + BrotliReverseBits(key),
321                     step,
322                     table_size,
323                     code);
324      key += key_step;
325      bits_count -= 1;
326    }
327    step <<= 1;
328    key_step >>= 1;
329    bits += 1;
330    if !(bits <= table_bits) {
331      break;
332    }
333  }
334
335  // if root_bits != table_bits we only created one fraction of the
336  // table, and we need to replicate it now.
337  while total_size != table_size {
338    for index in 0..table_size {
339      // FIXME: did I get this right?
340      fast_mut!((root_table)[table_free_offset as usize + table_size as usize + index as usize]) =
341        fast!((root_table)[table_free_offset as usize + index as usize]);
342    }
343    table_size <<= 1;
344  }
345
346  // fill in 2nd level tables and add pointers to root table
347  key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
348  let mut sub_key: u32 = BROTLI_REVERSE_BITS_LOWEST << 1;       /* 2nd level table prefix code */
349  let mut sub_key_step: u32 = BROTLI_REVERSE_BITS_LOWEST;   /* 2nd level table prefix code addend */
350
351  step = 2;
352
353  let mut len: i32 = root_bits + 1; /* current code length */
354  while len <= max_length {
355    let mut symbol: i32 = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 + 1);
356    while fast!((count)[len as usize]) != 0 {
357      if sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1u32) {
358        table_free_offset += table_size as u32;
359        table_bits = NextTableBitSize(count, len, root_bits);
360        table_size = 1 << table_bits;
361        total_size += table_size;
362        sub_key = BrotliReverseBits(key);
363        key += key_step;
364        fast_mut!((root_table)[sub_key as usize]).bits = (table_bits + root_bits) as u8;
365        fast_mut!((root_table)[sub_key as usize]).value =
366          ((table_free_offset as usize) - sub_key as usize) as u16;
367        sub_key = 0;
368      }
369      code.bits = (len - root_bits) as u8;
370      symbol =
371        fast!((symbol_lists)[(symbol_lists_offset as isize + symbol as isize) as usize]) as i32;
372      code.value = symbol as u16;
373      ReplicateValue(&mut root_table,
374                     table_free_offset + BrotliReverseBits(sub_key),
375                     step,
376                     table_size,
377                     code);
378      sub_key += sub_key_step;
379      fast_mut!((count)[len as usize]) -= 1;
380    }
381    step <<= 1;
382    sub_key_step >>= 1;
383    len += 1
384  }
385  total_size as u32
386}
387
388
389
390pub fn BrotliBuildSimpleHuffmanTable(table: &mut [HuffmanCode],
391                                     root_bits: i32,
392                                     val: &[u16],
393                                     num_symbols: u32)
394                                     -> u32 {
395  let mut table_size: u32 = 1;
396  let goal_size: u32 = 1u32 << root_bits;
397  assert!(num_symbols <= 4);
398  if num_symbols == 0 {
399    fast_mut!((table)[0]).bits = 0;
400    fast_mut!((table)[0]).value = fast!((val)[0]);
401  } else if num_symbols == 1 {
402    fast_mut!((table)[0]).bits = 1;
403    fast_mut!((table)[1]).bits = 1;
404    if fast!((val)[1]) > fast!((val)[0]) {
405      fast_mut!((table)[0]).value = fast!((val)[0]);
406      fast_mut!((table)[1]).value = fast!((val)[1]);
407    } else {
408      fast_mut!((table)[0]).value = fast!((val)[1]);
409      fast_mut!((table)[1]).value = fast!((val)[0]);
410    }
411    table_size = 2;
412  } else if num_symbols == 2 {
413    fast_mut!((table)[0]).bits = 1;
414    fast_mut!((table)[0]).value = fast!((val)[0]);
415    fast_mut!((table)[2]).bits = 1;
416    fast_mut!((table)[2]).value = fast!((val)[0]);
417    if fast!((val)[2]) > fast!((val)[1]) {
418      fast_mut!((table)[1]).value = fast!((val)[1]);
419      fast_mut!((table)[3]).value = fast!((val)[2]);
420    } else {
421      fast_mut!((table)[1]).value = fast!((val)[2]);
422      fast_mut!((table)[3]).value = fast!((val)[1]);
423    }
424    fast_mut!((table)[1]).bits = 2;
425    fast_mut!((table)[3]).bits = 2;
426    table_size = 4;
427  } else if num_symbols == 3 {
428    let last: u16 = if val.len() > 3 { fast!((val)[3]) } else { 65535 };
429    let mut mval: [u16; 4] = [fast!((val)[0]), fast!((val)[1]), fast!((val)[2]), last];
430    for i in 0..3 {
431      for k in i + 1..4 {
432        if mval[k] < mval[i] {
433          mval.swap(k, i);
434        }
435      }
436    }
437    for i in 0..4 {
438      fast_mut!((table)[i]).bits = 2;
439    }
440    fast_mut!((table)[0]).value = mval[0];
441    fast_mut!((table)[2]).value = mval[1];
442    fast_mut!((table)[1]).value = mval[2];
443    fast_mut!((table)[3]).value = mval[3];
444    table_size = 4;
445  } else if num_symbols == 4 {
446    let mut mval: [u16; 4] = [fast!((val)[0]), fast!((val)[1]), fast!((val)[2]), fast!((val)[3])];
447    if mval[3] < mval[2] {
448      mval.swap(3, 2)
449    }
450    for i in 0..7 {
451      fast_mut!((table)[i]).value = mval[0];
452      fast_mut!((table)[i]).bits = (1 + (i & 1)) as u8;
453    }
454    fast_mut!((table)[1]).value = mval[1];
455    fast_mut!((table)[3]).value = mval[2];
456    fast_mut!((table)[5]).value = mval[1];
457    fast_mut!((table)[7]).value = mval[3];
458    fast_mut!((table)[3]).bits = 3;
459    fast_mut!((table)[7]).bits = 3;
460    table_size = 8;
461  } else {
462    assert!(false);
463  }
464  while table_size != goal_size {
465    for index in 0..table_size {
466      fast_mut!((table)[(table_size + index) as usize]) = fast!((table)[index as usize]);
467    }
468    table_size <<= 1;
469  }
470  goal_size
471}
brotli_decompressor/huffman/mod.rs

brotli_decompressor/huffman/
mod.rs
