]> git.nihav.org Git - nihav.git/blob - src/io/codebook.rs
complete codebook LUT generator
[nihav.git] / src / io / codebook.rs
1 use std::collections::HashMap;
2 use std::cmp::{max, min};
3 use io::bitreader::BitReader;
4
5 #[derive(Debug)]
6 pub enum CodebookError {
7 InvalidCodebook,
8 MemoryError,
9 InvalidCode,
10 }
11
12 #[derive(Debug, Copy, Clone)]
13 pub enum CodebookMode {
14 MSB,
15 LSB,
16 }
17
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
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
203 impl<S: Copy> Codebook<S> {
204
205 pub fn new(cb: &mut CodebookDescReader<S>, mode: CodebookMode) -> CodebookResult<Self> {
206 let mut maxbits = 0;
207 let mut nnz = 0;
208 let mut escape_list: EscapeCodes = HashMap::new();
209
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);
220 }
221 if bits > 0 { symidx = symidx + 1; }
222 }
223 if maxbits == 0 { return Err(CodebookError::InvalidCodebook); }
224
225 if maxbits > MAX_LUT_BITS { maxbits = MAX_LUT_BITS; }
226
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);
233
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);
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 }
252 }
253 symidx = symidx + 1;
254 }
255
256 for (_, bucket) in &escape_list {
257 build_esc_lut(&mut table, mode, &bucket)?;
258 }
259
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> {
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;
288 }
289 Ok(cb.syms[idx])
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);
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);
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 },
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 }
370 );
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);
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);
405 }
406 }