brotli_decompressor/huffman/
mod.rs

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;
135
136const BROTLI_REVERSE_BITS_LOWEST: u32 =
137  (1u32 << (BROTLI_REVERSE_BITS_MAX as u32 - 1 + BROTLI_REVERSE_BITS_BASE as u32));
138
139// Callers narrow their key with `as u8`, which is sound only because this port
140// uses BROTLI_REVERSE_BITS_BASE == 0: keys accumulate from
141// BROTLI_REVERSE_BITS_LOWEST and so stay under
142// 1 << (BROTLI_REVERSE_BITS_MAX + BROTLI_REVERSE_BITS_BASE).
143//
144// That is not a spec guarantee. The reference implementation sets
145// BROTLI_REVERSE_BITS_BASE = (sizeof(brotli_reg_t) << 3) - BROTLI_REVERSE_BITS_MAX
146// (56 on 64-bit) wherever BROTLI_RBIT is available, which puts the key in the
147// high bits of a full register and makes it far larger than a u8. If that is
148// ever mirrored here the narrowing below would silently truncate, so fail the
149// build instead.
150const _REVERSE_BITS_KEYS_FIT_IN_U8: [(); 256] =
151  [(); 1usize << (BROTLI_REVERSE_BITS_MAX + BROTLI_REVERSE_BITS_BASE as usize)];
152
153// Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
154// where reverse(value, len) is the bit-wise reversal of the len least
155// significant bits of value.
156//
157// Callers narrow to u8, which is sound because BrotliBuildHuffmanTable rejects
158// root_bits outside [1, BROTLI_REVERSE_BITS_MAX] up front and
159// BrotliBuildCodeLengthsHuffmanTable requires
160// BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <= BROTLI_REVERSE_BITS_MAX, which
161// bounds every key by 1 << 8.
162fn BrotliReverseBits(num: u8) -> u32 {
163  num.reverse_bits() as u32
164}
165
166// Stores code in table[0], table[step], table[2*step], ..., table[end]
167// Assumes that end is an integer multiple of step.
168//
169// The written extent is table[offset .. offset + end], so bounds-checking the
170// last index covers the whole loop. That check is what makes the `fast_mut!`
171// write sound under --features=unsafe, where it is an unchecked store.
172fn ReplicateValue(table: &mut [HuffmanCode],
173                  offset: u32,
174                  step: i32,
175                  mut end: i32,
176                  code: HuffmanCode) -> bool {
177  if step <= 0 || end <= 0 || end % step != 0 {
178    return false;
179  }
180  if u64::from(offset) + (end - step) as u64 >= table.len() as u64 {
181    return false;
182  }
183  loop {
184    end -= step;
185    fast_mut!((table)[offset as usize + end as usize]) = code;
186    if end == 0 {
187      break;
188    }
189  }
190  true
191}
192
193// Returns the table width of the next 2nd level table. count is the histogram
194// of bit lengths for the remaining symbols, len is the code length of the next
195// processed symbol.
196//
197// The scan runs len up to BROTLI_HUFFMAN_MAX_CODE_LENGTH, which can be past the
198// caller's max_length, so `count` may run out underneath it.
199fn NextTableBitSize(count: &[u16], mut len: i32, root_bits: i32) -> Option<i32> {
200  debug_assert!(len > root_bits);
201  let mut left: i64 = 1i64 << (len - root_bits);
202  while len < BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 {
203    if len as usize >= count.len() {
204      return None;
205    }
206    left -= i64::from(fast!((count)[len as usize]));
207    if left <= 0 {
208      break;
209    }
210    len += 1;
211    left <<= 1;
212  }
213  Some(len - root_bits)
214}
215
216// symbol_lists is indexed relative to symbol_lists_offset, and the relative
217// index is deliberately negative for the per-length list heads (the reference
218// implementation indexes backwards off a raw pointer here). i64 covers both
219// directions in one expression, but we need to check if the resulting index
220// lands in the slice
221fn symbol_list_value(symbol_lists: &[u16],
222                     symbol_lists_offset: usize,
223                     relative_index: i32) -> Option<u16> {
224  let index = symbol_lists_offset as i64 + i64::from(relative_index);
225  if index < 0 || index as u64 >= symbol_lists.len() as u64 {
226    return None;
227  }
228  Some(fast!((symbol_lists)[index as usize]))
229}
230
231
232pub fn BrotliBuildCodeLengthsHuffmanTable(mut table: &mut [HuffmanCode],
233                                          code_lengths: &[u8],
234                                          count: &[u16]) -> bool {
235  let mut sorted: [i32; 18] = fast_uninitialized![18];     /* symbols sorted by code length */
236  // offsets in sorted table for each length
237  let mut offset: [i32; (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1) as usize] =
238    fast_uninitialized![(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1) as usize];
239  const table_size: i32 = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
240  if BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH as usize > BROTLI_REVERSE_BITS_MAX ||
241     table.len() < table_size as usize ||
242     code_lengths.len() < sorted.len() ||
243     count.len() <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH as usize {
244    return false;
245  }
246  let mut actual_count =
247    [0u16; (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1) as usize];
248  for code_length in code_lengths.iter().take(sorted.len()) {
249    let code_length_index = *code_length as usize;
250    if code_length_index >= actual_count.len() {
251      return false;
252    }
253    actual_count[code_length_index] += 1;
254  }
255  if actual_count[1..] != count[1..actual_count.len()] {
256    return false;
257  }
258
259  // generate offsets into sorted symbol table by code length
260  let mut symbol: i32 = -1;         /* symbol index in original or sorted table */
261  let mut bits: i32 = 1;
262  for _ in 0..BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH {
263    symbol += fast!((count)[bits as usize]) as i32;
264    fast_mut!((offset)[bits as usize]) = symbol;
265    bits += 1;
266  }
267  // Symbols with code length 0 are placed after all other symbols.
268  fast_mut!((offset)[0]) = 17;
269
270  // sort symbols by length, by symbol order within each length
271  symbol = 18;
272  loop {
273    for _ in 0..6 {
274      symbol -= 1;
275      let index = fast!((offset)[fast_inner!((code_lengths)[symbol as usize]) as usize]);
276      fast_mut!((offset)[fast_inner!((code_lengths)[symbol as usize]) as usize]) -= 1;
277      fast_mut!((sorted)[index as usize]) = symbol;
278    }
279    if symbol == 0 {
280      break;
281    }
282  }
283
284  // Special case: all symbols but one have 0 code length.
285  if fast!((offset)[0]) == 0 {
286    let code: HuffmanCode = HuffmanCode {
287      bits: 0,
288      value: fast!((sorted)[0]) as u16,
289    };
290    for val in fast_mut!((table)[0 ; table_size as usize]).iter_mut() {
291      *val = code;
292    }
293    return true;
294  }
295
296  // fill in table
297  //
298  // The caller only gets here with a complete prefix code (it rejects
299  // space != 0), so the keys below sum to exactly 1 << BROTLI_REVERSE_BITS_MAX
300  // and the last one used is 0xFF: `key as u8` cannot truncate.
301  let mut key: u32 = 0; /* prefix code */
302  let mut key_step: u32 = BROTLI_REVERSE_BITS_LOWEST; /* prefix code addend */
303  symbol = 0;
304  bits = 1;
305  let mut step: i32 = 2;
306  loop {
307    let mut code: HuffmanCode = HuffmanCode {
308      bits: (bits as u8),
309      value: 0,
310    };
311    let mut bits_count: i32 = fast!((count)[bits as usize]) as i32;
312
313    while bits_count != 0 {
314      code.value = fast!((sorted)[symbol as usize]) as u16;
315      symbol += 1;
316      let reversed_key = BrotliReverseBits(key as u8);
317      // Cannot fail while table_size is 32: step is 1 << bits and
318      // reversed_key < 1 << bits, so the last index written is below table_size.
319      if !ReplicateValue(&mut table, reversed_key, step, table_size, code) {
320        return false;
321      }
322      key += key_step;
323      bits_count -= 1;
324    }
325    step <<= 1;
326    key_step >>= 1;
327    bits += 1;
328    if !(bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH as i32) {
329      break;
330    }
331  }
332  true
333}
334
335pub fn BrotliBuildHuffmanTable(mut root_table: &mut [HuffmanCode],
336                               root_bits: i32,
337                               symbol_lists: &[u16],
338                               symbol_lists_offset: usize, /* need negative-index to symbol_lists */
339                               count: &mut [u16])
340                               -> u32 {
341  let mut code: HuffmanCode = HuffmanCode {
342    bits: 0,
343    value: 0,
344  };       /* current table entry */
345  let mut max_length: i32 = -1;
346
347  // Entry preconditions. The body's index bounds all derive from these plus the
348  // max_length check below: root_bits <= 8 keeps every prefix key under 1 << 8,
349  // and max_length < count.len() keeps every code-length index in range.
350  if root_bits <= 0 ||
351     root_bits as usize > BROTLI_REVERSE_BITS_MAX ||
352     BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 - root_bits >
353       BROTLI_REVERSE_BITS_MAX as i32 ||
354     symbol_lists_offset >= symbol_lists.len() {
355    return 0;
356  }
357
358  while match symbol_list_value(symbol_lists, symbol_lists_offset, max_length) {
359    Some(value) => value == 0xFFFF,
360    None => return 0,
361  } {
362    max_length -= 1;
363  }
364  max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 + 1;
365  // The scan above can walk off the front of symbol_lists' head region, which is
366  // the one way max_length ends up negative. Callers may pass a count histogram
367  // only as long as the code lengths they used, hence the second bound.
368  if max_length < 0 || max_length as usize >= count.len() {
369    return 0;
370  }
371  debug_assert!(max_length <= BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32);
372
373  let mut table_free_offset: u32 = 0;
374  let mut table_bits: i32 = root_bits;      /* key length of current table */
375  // root_bits <= 8, so every `1 << table_bits` below is at most 1 << 8.
376  let mut table_size: i32 = 1 << table_bits;/* size of current table */
377  let mut total_size: i32 = table_size;     /* sum of root table size and 2nd level table sizes */
378
379  // fill in root table
380  // let's reduce the table size to a smaller size if possible, and
381  // create the repetitions by memcpy if possible in the coming loop
382  if table_bits > max_length {
383    table_bits = max_length;
384    table_size = 1 << table_bits;
385  }
386  let mut key: u32 = 0; /* prefix code */
387  let mut key_step: u32 = BROTLI_REVERSE_BITS_LOWEST; /* prefix code addend */
388  let mut bits: i32 = 1;
389  let mut step: i32 = 2; /* step size to replicate values in current table */
390  loop {
391    code.bits = bits as u8;
392    let mut symbol: i32 = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 + 1);
393    let mut bits_count: i32 = fast!((count)[bits as usize]) as i32;
394    while bits_count != 0 {
395      symbol = match symbol_list_value(symbol_lists, symbol_lists_offset, symbol) {
396        Some(symbol) => symbol as i32,
397        None => return 0,
398      };
399      code.value = symbol as u16;
400      let reversed_key = BrotliReverseBits(key as u8);
401      if !ReplicateValue(&mut root_table, table_free_offset + reversed_key, step,
402                         table_size, code) {
403        return 0;
404      }
405      key += key_step;
406      bits_count -= 1;
407    }
408    step <<= 1;
409    key_step >>= 1;
410    bits += 1;
411    if !(bits <= table_bits) {
412      break;
413    }
414  }
415
416  // if root_bits != table_bits we only created one fraction of the
417  // table, and we need to replicate it now.
418  while total_size != table_size {
419    // Doubling the filled prefix in place; total_size bounds the loop.
420    let base = table_free_offset as usize;
421    let size = table_size as usize;
422    if base + 2 * size > root_table.len() {
423      return 0;
424    }
425    let (head, tail) = root_table.split_at_mut(base + size);
426    tail[..size].clone_from_slice(&head[base..]);
427    table_size <<= 1;
428  }
429
430  // fill in 2nd level tables and add pointers to root table
431  key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
432  let mut sub_key: u32 = BROTLI_REVERSE_BITS_LOWEST << 1;       /* 2nd level table prefix code */
433  let mut sub_key_step: u32 = BROTLI_REVERSE_BITS_LOWEST;   /* 2nd level table prefix code addend */
434
435  step = 2;
436
437  let mut len: i32 = root_bits + 1; /* current code length */
438  while len <= max_length {
439    let mut symbol: i32 = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH as i32 + 1);
440    while fast!((count)[len as usize]) != 0 {
441      if sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1u32) {
442        table_free_offset += table_size as u32;
443        table_bits = match NextTableBitSize(count, len, root_bits) {
444          Some(table_bits) => table_bits,
445          None => return 0,
446        };
447        table_size = 1 << table_bits;
448        total_size += table_size;
449        sub_key = BrotliReverseBits(key as u8);
450        key += key_step;
451        // Checked rather than assumed: this is narrowed into the u16
452        // HuffmanCode::value, and sub_key then indexes a write.
453        let table_value = match (table_free_offset as usize).checked_sub(sub_key as usize) {
454          Some(table_value) if table_value <= u16::MAX as usize => table_value as u16,
455          _ => return 0,
456        };
457        match root_table.get_mut(sub_key as usize) {
458          Some(entry) => {
459            entry.bits = (table_bits + root_bits) as u8;
460            entry.value = table_value;
461          },
462          None => return 0,
463        }
464        sub_key = 0;
465      }
466      code.bits = (len - root_bits) as u8;
467      symbol = match symbol_list_value(symbol_lists, symbol_lists_offset, symbol) {
468        Some(symbol) => symbol as i32,
469        None => return 0,
470      };
471      code.value = symbol as u16;
472      let reversed_sub_key = BrotliReverseBits(sub_key as u8);
473      if !ReplicateValue(&mut root_table, table_free_offset + reversed_sub_key, step,
474                         table_size, code) {
475        return 0;
476      }
477      sub_key += sub_key_step;
478      // len <= max_length < count.len(), and the loop condition just read a
479      // nonzero count[len].
480      fast_mut!((count)[len as usize]) -= 1;
481    }
482    step <<= 1;
483    sub_key_step >>= 1;
484    len += 1
485  }
486  total_size as u32
487}
488
489
490
491pub fn BrotliBuildSimpleHuffmanTable(table: &mut [HuffmanCode],
492                                     root_bits: i32,
493                                     val: &[u16],
494                                     num_symbols: u32)
495                                     -> u32 {
496  if root_bits <= 0 || root_bits >= 32 {
497    return 0;
498  }
499  // num_symbols is the raw 2-bit field (plus one extra bit when it reads 3), so
500  // 0..=4 are the only encodable values. This match rejects anything larger,
501  // which is why the branch chain below needs no final catch-all.
502  let required_symbols = match num_symbols {
503    0 => 1,
504    1 => 2,
505    2 | 3 => 3,
506    4 => 4,
507    _ => return 0,
508  };
509  if val.len() < required_symbols {
510    return 0;
511  }
512  let mut table_size: u32 = 1;
513  // root_bits is in 1..32 by the check above, so the shift is in range.
514  let goal_size: u32 = 1u32 << root_bits;
515  if table.len() < goal_size as usize {
516    return 0;
517  }
518  if num_symbols == 0 {
519    fast_mut!((table)[0]).bits = 0;
520    fast_mut!((table)[0]).value = fast!((val)[0]);
521  } else if num_symbols == 1 {
522    fast_mut!((table)[0]).bits = 1;
523    fast_mut!((table)[1]).bits = 1;
524    if fast!((val)[1]) > fast!((val)[0]) {
525      fast_mut!((table)[0]).value = fast!((val)[0]);
526      fast_mut!((table)[1]).value = fast!((val)[1]);
527    } else {
528      fast_mut!((table)[0]).value = fast!((val)[1]);
529      fast_mut!((table)[1]).value = fast!((val)[0]);
530    }
531    table_size = 2;
532  } else if num_symbols == 2 {
533    fast_mut!((table)[0]).bits = 1;
534    fast_mut!((table)[0]).value = fast!((val)[0]);
535    fast_mut!((table)[2]).bits = 1;
536    fast_mut!((table)[2]).value = fast!((val)[0]);
537    if fast!((val)[2]) > fast!((val)[1]) {
538      fast_mut!((table)[1]).value = fast!((val)[1]);
539      fast_mut!((table)[3]).value = fast!((val)[2]);
540    } else {
541      fast_mut!((table)[1]).value = fast!((val)[2]);
542      fast_mut!((table)[3]).value = fast!((val)[1]);
543    }
544    fast_mut!((table)[1]).bits = 2;
545    fast_mut!((table)[3]).bits = 2;
546    table_size = 4;
547  } else if num_symbols == 3 {
548    let last: u16 = if val.len() > 3 { fast!((val)[3]) } else { 65535 };
549    let mut mval: [u16; 4] = [fast!((val)[0]), fast!((val)[1]), fast!((val)[2]), last];
550    for i in 0..3 {
551      for k in i + 1..4 {
552        if mval[k] < mval[i] {
553          mval.swap(k, i);
554        }
555      }
556    }
557    for i in 0..4 {
558      fast_mut!((table)[i]).bits = 2;
559    }
560    fast_mut!((table)[0]).value = mval[0];
561    fast_mut!((table)[2]).value = mval[1];
562    fast_mut!((table)[1]).value = mval[2];
563    fast_mut!((table)[3]).value = mval[3];
564    table_size = 4;
565  } else {
566    debug_assert_eq!(num_symbols, 4);
567    let mut mval: [u16; 4] = [fast!((val)[0]), fast!((val)[1]), fast!((val)[2]), fast!((val)[3])];
568    if mval[3] < mval[2] {
569      mval.swap(3, 2)
570    }
571    for i in 0..7 {
572      fast_mut!((table)[i]).value = mval[0];
573      fast_mut!((table)[i]).bits = (1 + (i & 1)) as u8;
574    }
575    fast_mut!((table)[1]).value = mval[1];
576    fast_mut!((table)[3]).value = mval[2];
577    fast_mut!((table)[5]).value = mval[1];
578    fast_mut!((table)[7]).value = mval[3];
579    fast_mut!((table)[3]).bits = 3;
580    fast_mut!((table)[7]).bits = 3;
581    table_size = 8;
582  }
583  while table_size != goal_size {
584    for index in 0..table_size {
585      fast_mut!((table)[(table_size + index) as usize]) = fast!((table)[index as usize]);
586    }
587    table_size <<= 1;
588  }
589  goal_size
590}
brotli_decompressor/huffman/mod.rs

brotli_decompressor/huffman/
mod.rs
