1 use std::collections::HashMap;
2 use std::cmp::{max, min};
3 use io::bitreader::BitReader;
6 pub enum CodebookError {
12 #[derive(Debug, Copy, Clone)]
13 pub enum CodebookMode {
18 type CodebookResult<T> = Result<T, CodebookError>;
20 pub struct FullCodebookDesc<S> {
26 pub struct ShortCodebookDesc {
31 pub trait CodebookDescReader<S> {
32 fn bits(&mut self, idx: usize) -> u8;
33 fn code(&mut self, idx: usize) -> u32;
34 fn sym (&mut self, idx: usize) -> S;
35 fn len (&mut self) -> usize;
39 pub struct Codebook<S> {
45 pub trait CodebookReader<S> {
46 fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S>;
49 pub fn reverse_bits(inval: u32) -> u32 {
50 const REV_TAB: [u8; 16] = [
51 0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110,
52 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111,
58 ret = (ret << 4) | (REV_TAB[(val & 0xF) as usize] as u32);
64 const TABLE_FILL_VALUE: u32 = 0x7F;
65 const MAX_LUT_BITS: u8 = 10;
67 fn fill_lut_msb(table: &mut Vec<u32>, off: usize,
68 code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) {
70 let fill_len = lut_bits - bits;
71 let fill_size = 1 << fill_len;
72 let fill_code = code << (lut_bits - bits);
73 let lut_value = (symidx << 8) | (bits as u32);
74 for j in 0..fill_size {
75 let idx = (fill_code + j) as usize;
76 table[idx + off] = lut_value;
79 let idx = (code as usize) + off;
80 table[idx] = (symidx << 8) | 0x80 | (bits as u32);
84 fn fill_lut_lsb(table: &mut Vec<u32>, off: usize,
85 code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) {
87 let fill_len = lut_bits - bits;
88 let fill_size = 1 << fill_len;
90 let step = lut_bits - fill_len;
91 for j in 0..fill_size {
92 let idx = (fill_code + (j << step)) as usize;
93 table[idx + off] = (symidx << 8) | (bits as u32);
96 let idx = (code as usize) + off;
97 table[idx] = (symidx << 8) | 0x80 | (bits as u32);
101 fn fill_lut(table: &mut Vec<u32>, mode: CodebookMode,
102 off: usize, code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) -> bool {
104 CodebookMode::MSB => fill_lut_msb(table, off, code, bits, lut_bits, symidx, esc),
105 CodebookMode::LSB => fill_lut_lsb(table, off, code, bits, lut_bits, symidx, esc),
110 fn resize_table(table: &mut Vec<u32>, bits: u8) -> CodebookResult<u32> {
111 let add_size = (1 << bits) as usize;
112 table.reserve(add_size);
113 let cur_off = table.len() as u32;
114 let new_size = table.len() + add_size;
115 if table.capacity() < new_size { return Err(CodebookError::MemoryError); }
116 table.resize(new_size, TABLE_FILL_VALUE);
121 fn extract_lut_part(code: u32, bits: u8, lut_bits: u8, mode: CodebookMode) -> u32 {
123 CodebookMode::MSB => code >> (bits - lut_bits),
124 CodebookMode::LSB => code & ((1 << lut_bits) - 1),
128 fn extract_esc_part(code: u32, bits: u8, lut_bits: u8, mode: CodebookMode) -> u32 {
130 CodebookMode::MSB => code & ((1 << (bits - lut_bits)) - 1),
131 CodebookMode::LSB => code >> lut_bits,
135 #[derive(Clone,Copy)]
150 CodeBucket { maxlen: 0, offset: 0, codes: Vec::new() }
152 fn add_code(&mut self, c: Code) {
153 if c.bits > self.maxlen { self.maxlen = c.bits; }
158 type EscapeCodes = HashMap<u32, CodeBucket>;
160 fn add_esc_code(cc: &mut EscapeCodes, key: u32, code: u32, bits: u8, idx: usize) {
161 if !cc.contains_key(&key) { cc.insert(key, CodeBucket::new()); }
162 let b = cc.get_mut(&key);
163 if let Some(bucket) = b {
164 bucket.add_code(Code {code: code, bits: bits, idx: idx });
165 } else { panic!("no bucket when expected!"); }
168 fn build_esc_lut(table: &mut Vec<u32>,
170 bucket: &CodeBucket) -> CodebookResult<()> {
171 let mut escape_list: EscapeCodes = HashMap::new();
172 let maxlen = if bucket.maxlen > MAX_LUT_BITS { MAX_LUT_BITS } else { bucket.maxlen };
174 for code in &bucket.codes {
175 let bits = code.bits;
176 if code.bits < MAX_LUT_BITS {
177 fill_lut(table, mode, bucket.offset, code.code, bits,
178 maxlen, code.idx as u32, false);
180 let ckey = extract_lut_part(code.code, bits, MAX_LUT_BITS, mode);
181 let cval = extract_esc_part(code.code, bits, MAX_LUT_BITS, mode);
182 add_esc_code(&mut escape_list, ckey, cval, bits - MAX_LUT_BITS, code.idx);
186 let cur_offset = bucket.offset;
187 for (ckey, sec_bucket) in &mut escape_list {
188 let key = *ckey as u32;
189 let maxlen = min(sec_bucket.maxlen, MAX_LUT_BITS);
190 let new_off = resize_table(table, maxlen)?;
191 fill_lut(table, mode, cur_offset, key, maxlen,
192 MAX_LUT_BITS, new_off, true);
193 sec_bucket.offset = new_off as usize;
196 for (_, sec_bucket) in &escape_list {
197 build_esc_lut(table, mode, sec_bucket)?;
203 impl<S: Copy> Codebook<S> {
205 pub fn new(cb: &mut CodebookDescReader<S>, mode: CodebookMode) -> CodebookResult<Self> {
208 let mut escape_list: EscapeCodes = HashMap::new();
210 let mut symidx: usize = 0;
211 for i in 0..cb.len() {
212 let bits = cb.bits(i);
213 if bits > 0 { nnz = nnz + 1; }
214 maxbits = max(bits, maxbits);
215 if bits > MAX_LUT_BITS {
216 let code = cb.code(i);
217 let ckey = extract_lut_part(code, bits, MAX_LUT_BITS, mode);
218 let cval = extract_esc_part(code, bits, MAX_LUT_BITS, mode);
219 add_esc_code(&mut escape_list, ckey, cval, bits - MAX_LUT_BITS, symidx);
221 if bits > 0 { symidx = symidx + 1; }
223 if maxbits == 0 { return Err(CodebookError::InvalidCodebook); }
225 if maxbits > MAX_LUT_BITS { maxbits = MAX_LUT_BITS; }
227 let tab_len = 1 << maxbits;
228 let mut table: Vec<u32> = Vec::with_capacity(tab_len);
229 let mut syms: Vec<S> = Vec::with_capacity(nnz);
230 if table.capacity() < tab_len { return Err(CodebookError::MemoryError); }
231 if syms.capacity() < nnz { return Err(CodebookError::MemoryError); }
232 table.resize(tab_len, TABLE_FILL_VALUE);
234 let mut symidx: u32 = 0;
235 for i in 0..cb.len() {
236 let bits = cb.bits(i);
237 let code = cb.code(i);
238 if bits == 0 { continue; }
239 if bits <= MAX_LUT_BITS {
240 fill_lut(&mut table, mode, 0, code, bits, maxbits, symidx, false);
242 let ckey = extract_lut_part(code, bits, MAX_LUT_BITS, mode) as usize;
243 if table[ckey] == TABLE_FILL_VALUE {
244 let key = ckey as u32;
245 if let Some(bucket) = escape_list.get_mut(&key) {
246 let maxlen = min(bucket.maxlen, MAX_LUT_BITS);
247 let new_off = resize_table(&mut table, maxlen)?;
248 fill_lut(&mut table, mode, 0, key, maxlen, MAX_LUT_BITS, new_off, true);
249 bucket.offset = new_off as usize;
256 for (_, bucket) in &escape_list {
257 build_esc_lut(&mut table, mode, &bucket)?;
260 for i in 0..cb.len() {
262 syms.push(cb.sym(i));
266 Ok(Codebook { table: table, syms: syms, lut_bits: maxbits })
270 impl<'a, S: Copy> CodebookReader<S> for BitReader<'a> {
271 #[allow(unused_variables)]
272 fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S> {
275 let mut lut_bits = cb.lut_bits;
277 let lut_idx = (self.peek(lut_bits) as usize) + (idx as usize);
278 if cb.table[lut_idx] == TABLE_FILL_VALUE { return Err(CodebookError::InvalidCode); }
279 let bits = cb.table[lut_idx] & 0x7F;
280 esc = (cb.table[lut_idx] & 0x80) != 0;
281 idx = (cb.table[lut_idx] >> 8) as usize;
282 if (bits as isize) > self.left() {
283 return Err(CodebookError::InvalidCode);
285 let skip_bits = if esc { lut_bits as u32 } else { bits };
286 if let Err(_) = self.skip(skip_bits as u32) {}
287 lut_bits = bits as u8;
293 pub struct FullCodebookDescReader<S> {
294 data: Vec<FullCodebookDesc<S>>,
297 impl<S> FullCodebookDescReader<S> {
298 pub fn new(data: Vec<FullCodebookDesc<S>>) -> Self {
299 FullCodebookDescReader { data: data }
303 impl<S: Copy> CodebookDescReader<S> for FullCodebookDescReader<S> {
304 fn bits(&mut self, idx: usize) -> u8 { self.data[idx].bits }
305 fn code(&mut self, idx: usize) -> u32 { self.data[idx].code }
306 fn sym (&mut self, idx: usize) -> S { self.data[idx].sym }
307 fn len(&mut self) -> usize { self.data.len() }
310 pub struct ShortCodebookDescReader {
311 data: Vec<ShortCodebookDesc>,
314 impl ShortCodebookDescReader {
315 pub fn new(data: Vec<ShortCodebookDesc<>>) -> Self {
316 ShortCodebookDescReader { data: data }
320 impl CodebookDescReader<u32> for ShortCodebookDescReader {
321 fn bits(&mut self, idx: usize) -> u8 { self.data[idx].bits }
322 fn code(&mut self, idx: usize) -> u32 { self.data[idx].code }
323 fn sym (&mut self, idx: usize) -> u32 { idx as u32 }
324 fn len(&mut self) -> usize { self.data.len() }
330 use io::bitreader::*;
334 const BITS: [u8; 2] = [0b01011011, 0b10111100];
335 let cb_desc: Vec<FullCodebookDesc<i8>> = vec!(
336 FullCodebookDesc { code: 0b0, bits: 1, sym: 16 },
337 FullCodebookDesc { code: 0b10, bits: 2, sym: -3 },
338 FullCodebookDesc { code: 0b110, bits: 3, sym: 42 },
339 FullCodebookDesc { code: 0b1110, bits: 4, sym: -42 }
342 let mut br = BitReader::new(buf, buf.len(), BitReaderMode::BE);
343 let mut cfr = FullCodebookDescReader::new(cb_desc);
344 let cb = Codebook::new(&mut cfr, CodebookMode::MSB).unwrap();
345 assert_eq!(br.read_cb(&cb).unwrap(), 16);
346 assert_eq!(br.read_cb(&cb).unwrap(), -3);
347 assert_eq!(br.read_cb(&cb).unwrap(), 42);
348 assert_eq!(br.read_cb(&cb).unwrap(), -42);
349 let ret = br.read_cb(&cb);
350 if let Err(e) = ret {
351 assert_eq!(e as i32, CodebookError::InvalidCode as i32);
356 let scb_desc: Vec<ShortCodebookDesc> = vec!(
357 ShortCodebookDesc { code: 0b0, bits: 1 },
358 ShortCodebookDesc { code: 0, bits: 0 },
359 ShortCodebookDesc { code: 0b10, bits: 2 },
360 ShortCodebookDesc { code: 0, bits: 0 },
361 ShortCodebookDesc { code: 0, bits: 0 },
362 ShortCodebookDesc { code: 0b110, bits: 3 },
363 ShortCodebookDesc { code: 0, bits: 0 },
364 ShortCodebookDesc { code: 0b11100, bits: 5 },
365 ShortCodebookDesc { code: 0b11101, bits: 5 },
366 ShortCodebookDesc { code: 0b1111010, bits: 7 },
367 ShortCodebookDesc { code: 0b1111011, bits: 7 },
368 ShortCodebookDesc { code: 0b1111110, bits: 7 },
369 ShortCodebookDesc { code: 0b11111111, bits: 8 }
371 let mut br2 = BitReader::new(buf, buf.len(), BitReaderMode::BE);
372 let mut cfr = ShortCodebookDescReader::new(scb_desc);
373 let cb = Codebook::new(&mut cfr, CodebookMode::MSB).unwrap();
374 assert_eq!(br2.read_cb(&cb).unwrap(), 0);
375 assert_eq!(br2.read_cb(&cb).unwrap(), 2);
376 assert_eq!(br2.read_cb(&cb).unwrap(), 5);
377 assert_eq!(br2.read_cb(&cb).unwrap(), 8);
379 assert_eq!(reverse_bits(0b0000_0101_1011_1011_1101_1111_0111_1111),
380 0b1111_1110_1111_1011_1101_1101_1010_0000);
382 const BITS_LE: [u8; 3] = [0b11101111, 0b01110010, 0b01];
384 let scble_desc: Vec<ShortCodebookDesc> = vec!(
385 ShortCodebookDesc { code: 0b00, bits: 2 },
386 ShortCodebookDesc { code: 0, bits: 0 },
387 ShortCodebookDesc { code: 0b01, bits: 2 },
388 ShortCodebookDesc { code: 0, bits: 0 },
389 ShortCodebookDesc { code: 0, bits: 0 },
390 ShortCodebookDesc { code: 0b011, bits: 3 },
391 ShortCodebookDesc { code: 0, bits: 0 },
392 ShortCodebookDesc { code: 0b10111, bits: 5 },
393 ShortCodebookDesc { code: 0b00111, bits: 5 },
394 ShortCodebookDesc { code: 0b0101111, bits: 7 },
395 ShortCodebookDesc { code: 0b0111111, bits: 7 },
396 ShortCodebookDesc { code: 0b1011101111, bits: 10 }
398 let mut brl = BitReader::new(buf, buf.len(), BitReaderMode::LE);
399 let mut cfr = ShortCodebookDescReader::new(scble_desc);
400 let cb = Codebook::new(&mut cfr, CodebookMode::LSB).unwrap();
401 assert_eq!(brl.read_cb(&cb).unwrap(), 11);
402 assert_eq!(brl.read_cb(&cb).unwrap(), 0);
403 assert_eq!(brl.read_cb(&cb).unwrap(), 7);
404 assert_eq!(brl.read_cb(&cb).unwrap(), 0);