brotli_no_stdlib/huffman/
mod.rs

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

brotli_no_stdlib/huffman/
mod.rs
