]>
Commit | Line | Data |
---|---|---|
0ca65ffd KS |
1 | use std::collections::HashMap; |
2 | use std::cmp::{max, min}; | |
4667915a KS |
3 | use io::bitreader::BitReader; |
4 | ||
5 | #[derive(Debug)] | |
6 | pub enum CodebookError { | |
7 | InvalidCodebook, | |
8 | MemoryError, | |
9 | InvalidCode, | |
10 | } | |
11 | ||
0ca65ffd KS |
12 | #[derive(Debug, Copy, Clone)] |
13 | pub enum CodebookMode { | |
14 | MSB, | |
15 | LSB, | |
16 | } | |
17 | ||
4667915a KS |
18 | type CodebookResult<T> = Result<T, CodebookError>; |
19 | ||
20 | pub struct FullCodebookDesc<S> { | |
21 | code: u32, | |
22 | bits: u8, | |
23 | sym: S, | |
24 | } | |
25 | ||
26 | pub struct ShortCodebookDesc { | |
27 | code: u32, | |
28 | bits: u8, | |
29 | } | |
30 | ||
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; | |
36 | } | |
37 | ||
38 | #[allow(dead_code)] | |
39 | pub struct Codebook<S> { | |
40 | table: Vec<u32>, | |
41 | syms: Vec<S>, | |
42 | lut_bits: u8, | |
43 | } | |
44 | ||
45 | pub trait CodebookReader<S> { | |
46 | fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S>; | |
47 | } | |
48 | ||
0ca65ffd KS |
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, | |
53 | ]; | |
54 | ||
55 | let mut ret = 0; | |
56 | let mut val = inval; | |
57 | for _ in 0..8 { | |
58 | ret = (ret << 4) | (REV_TAB[(val & 0xF) as usize] as u32); | |
59 | val = val >> 4; | |
60 | } | |
61 | ret | |
62 | } | |
63 | ||
64 | const TABLE_FILL_VALUE: u32 = 0x7F; | |
65 | const MAX_LUT_BITS: u8 = 10; | |
66 | ||
67 | fn fill_lut_msb(table: &mut Vec<u32>, off: usize, | |
68 | code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) { | |
69 | if !esc { | |
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; | |
77 | } | |
78 | } else { | |
79 | let idx = (code as usize) + off; | |
80 | table[idx] = (symidx << 8) | 0x80 | (bits as u32); | |
81 | } | |
82 | } | |
83 | ||
84 | fn fill_lut_lsb(table: &mut Vec<u32>, off: usize, | |
85 | code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) { | |
86 | if !esc { | |
87 | let fill_len = lut_bits - bits; | |
88 | let fill_size = 1 << fill_len; | |
89 | let fill_code = code; | |
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); | |
94 | } | |
95 | } else { | |
96 | let idx = (code as usize) + off; | |
97 | table[idx] = (symidx << 8) | 0x80 | (bits as u32); | |
98 | } | |
99 | } | |
100 | ||
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 { | |
103 | match mode { | |
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), | |
106 | }; | |
107 | bits > lut_bits | |
108 | } | |
109 | ||
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); | |
117 | Ok(cur_off) | |
118 | } | |
119 | ||
120 | ||
121 | fn extract_lut_part(code: u32, bits: u8, lut_bits: u8, mode: CodebookMode) -> u32 { | |
122 | match mode { | |
123 | CodebookMode::MSB => code >> (bits - lut_bits), | |
124 | CodebookMode::LSB => code & ((1 << lut_bits) - 1), | |
125 | } | |
126 | } | |
127 | ||
128 | fn extract_esc_part(code: u32, bits: u8, lut_bits: u8, mode: CodebookMode) -> u32 { | |
129 | match mode { | |
130 | CodebookMode::MSB => code & ((1 << (bits - lut_bits)) - 1), | |
131 | CodebookMode::LSB => code >> lut_bits, | |
132 | } | |
133 | } | |
134 | ||
135 | #[derive(Clone,Copy)] | |
136 | struct Code { | |
137 | code: u32, | |
138 | bits: u8, | |
139 | idx: usize, | |
140 | } | |
141 | ||
142 | struct CodeBucket { | |
143 | maxlen: u8, | |
144 | offset: usize, | |
145 | codes: Vec<Code>, | |
146 | } | |
147 | ||
148 | impl CodeBucket { | |
149 | fn new() -> Self { | |
150 | CodeBucket { maxlen: 0, offset: 0, codes: Vec::new() } | |
151 | } | |
152 | fn add_code(&mut self, c: Code) { | |
153 | if c.bits > self.maxlen { self.maxlen = c.bits; } | |
154 | self.codes.push(c); | |
155 | } | |
156 | } | |
157 | ||
158 | type EscapeCodes = HashMap<u32, CodeBucket>; | |
159 | ||
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!"); } | |
166 | } | |
167 | ||
168 | fn build_esc_lut(table: &mut Vec<u32>, | |
169 | mode: CodebookMode, | |
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 }; | |
173 | ||
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); | |
179 | } else { | |
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); | |
183 | } | |
184 | } | |
185 | ||
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; | |
194 | } | |
195 | ||
196 | for (_, sec_bucket) in &escape_list { | |
197 | build_esc_lut(table, mode, sec_bucket)?; | |
198 | } | |
199 | ||
200 | Ok(()) | |
201 | } | |
202 | ||
4667915a | 203 | impl<S: Copy> Codebook<S> { |
0ca65ffd KS |
204 | |
205 | pub fn new(cb: &mut CodebookDescReader<S>, mode: CodebookMode) -> CodebookResult<Self> { | |
4667915a KS |
206 | let mut maxbits = 0; |
207 | let mut nnz = 0; | |
0ca65ffd KS |
208 | let mut escape_list: EscapeCodes = HashMap::new(); |
209 | ||
210 | let mut symidx: usize = 0; | |
4667915a KS |
211 | for i in 0..cb.len() { |
212 | let bits = cb.bits(i); | |
213 | if bits > 0 { nnz = nnz + 1; } | |
0ca65ffd KS |
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); | |
4667915a | 220 | } |
0ca65ffd | 221 | if bits > 0 { symidx = symidx + 1; } |
4667915a KS |
222 | } |
223 | if maxbits == 0 { return Err(CodebookError::InvalidCodebook); } | |
224 | ||
0ca65ffd KS |
225 | if maxbits > MAX_LUT_BITS { maxbits = MAX_LUT_BITS; } |
226 | ||
4667915a | 227 | let tab_len = 1 << maxbits; |
0ca65ffd KS |
228 | let mut table: Vec<u32> = Vec::with_capacity(tab_len); |
229 | let mut syms: Vec<S> = Vec::with_capacity(nnz); | |
4667915a | 230 | if table.capacity() < tab_len { return Err(CodebookError::MemoryError); } |
0ca65ffd KS |
231 | if syms.capacity() < nnz { return Err(CodebookError::MemoryError); } |
232 | table.resize(tab_len, TABLE_FILL_VALUE); | |
4667915a KS |
233 | |
234 | let mut symidx: u32 = 0; | |
235 | for i in 0..cb.len() { | |
236 | let bits = cb.bits(i); | |
0ca65ffd | 237 | let code = cb.code(i); |
4667915a | 238 | if bits == 0 { continue; } |
0ca65ffd KS |
239 | if bits <= MAX_LUT_BITS { |
240 | fill_lut(&mut table, mode, 0, code, bits, maxbits, symidx, false); | |
241 | } else { | |
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; | |
250 | } | |
251 | } | |
4667915a KS |
252 | } |
253 | symidx = symidx + 1; | |
254 | } | |
255 | ||
0ca65ffd KS |
256 | for (_, bucket) in &escape_list { |
257 | build_esc_lut(&mut table, mode, &bucket)?; | |
258 | } | |
259 | ||
4667915a KS |
260 | for i in 0..cb.len() { |
261 | if cb.bits(i) > 0 { | |
262 | syms.push(cb.sym(i)); | |
263 | } | |
264 | } | |
265 | ||
266 | Ok(Codebook { table: table, syms: syms, lut_bits: maxbits }) | |
267 | } | |
268 | } | |
269 | ||
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> { | |
0ca65ffd KS |
273 | let mut esc = true; |
274 | let mut idx = 0; | |
275 | let mut lut_bits = cb.lut_bits; | |
276 | while esc { | |
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); | |
284 | } | |
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; | |
4667915a | 288 | } |
0ca65ffd | 289 | Ok(cb.syms[idx]) |
4667915a KS |
290 | } |
291 | } | |
292 | ||
293 | pub struct FullCodebookDescReader<S> { | |
294 | data: Vec<FullCodebookDesc<S>>, | |
295 | } | |
296 | ||
297 | impl<S> FullCodebookDescReader<S> { | |
298 | pub fn new(data: Vec<FullCodebookDesc<S>>) -> Self { | |
299 | FullCodebookDescReader { data: data } | |
300 | } | |
301 | } | |
302 | ||
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() } | |
308 | } | |
309 | ||
310 | pub struct ShortCodebookDescReader { | |
311 | data: Vec<ShortCodebookDesc>, | |
312 | } | |
313 | ||
314 | impl ShortCodebookDescReader { | |
315 | pub fn new(data: Vec<ShortCodebookDesc<>>) -> Self { | |
316 | ShortCodebookDescReader { data: data } | |
317 | } | |
318 | } | |
319 | ||
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() } | |
325 | } | |
326 | ||
327 | #[cfg(test)] | |
328 | mod test { | |
329 | use super::*; | |
330 | use io::bitreader::*; | |
331 | ||
332 | #[test] | |
333 | fn test_cb() { | |
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 } | |
340 | ); | |
341 | let buf = &BITS; | |
342 | let mut br = BitReader::new(buf, buf.len(), BitReaderMode::BE); | |
343 | let mut cfr = FullCodebookDescReader::new(cb_desc); | |
0ca65ffd | 344 | let cb = Codebook::new(&mut cfr, CodebookMode::MSB).unwrap(); |
4667915a KS |
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); | |
352 | } else { | |
353 | assert_eq!(0, 1); | |
354 | } | |
355 | ||
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 }, | |
0ca65ffd KS |
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 } | |
4667915a KS |
370 | ); |
371 | let mut br2 = BitReader::new(buf, buf.len(), BitReaderMode::BE); | |
372 | let mut cfr = ShortCodebookDescReader::new(scb_desc); | |
0ca65ffd | 373 | let cb = Codebook::new(&mut cfr, CodebookMode::MSB).unwrap(); |
4667915a KS |
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); | |
0ca65ffd KS |
377 | assert_eq!(br2.read_cb(&cb).unwrap(), 8); |
378 | ||
379 | assert_eq!(reverse_bits(0b0000_0101_1011_1011_1101_1111_0111_1111), | |
380 | 0b1111_1110_1111_1011_1101_1101_1010_0000); | |
381 | ||
382 | const BITS_LE: [u8; 3] = [0b11101111, 0b01110010, 0b01]; | |
383 | let buf = &BITS_LE; | |
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 } | |
397 | ); | |
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); | |
4667915a KS |
405 | } |
406 | } |