1 /*
2 ** FAAD2 - Freeware Advanced Audio (AAC) Decoder including SBR decoding
3 ** Copyright (C) 2003-2005 M. Bakker, Nero AG, http://www.nero.com
4 **
5 ** This program is free software; you can redistribute it and/or modify
6 ** it under the terms of the GNU General Public License as published by
7 ** the Free Software Foundation; either version 2 of the License, or
8 ** (at your option) any later version.
9 **
10 ** This program is distributed in the hope that it will be useful,
11 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 ** GNU General Public License for more details.
14 **
15 ** You should have received a copy of the GNU General Public License
16 ** along with this program; if not, write to the Free Software
17 ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 **
19 ** Any non-GPL usage of this software or parts of this software is strictly
20 ** forbidden.
21 **
22 ** The "appropriate copyright message" mentioned in section 2c of the GPLv2
23 ** must read: "Code from FAAD2 is copyright (c) Nero AG, www.nero.com"
24 **
25 ** Commercial non-GPL licensing of this software is possible.
26 ** For more info contact Nero AG through Mpeg4AAClicense@nero.com.
27 **
28 ** $Id: huffman.c,v 1.26 2007/11/01 12:33:30 menno Exp $
29 **/
30
31 #include "common.h"
32 #include "structs.h"
33
34 #include <stdlib.h>
35 #ifdef ANALYSIS
36 #include <stdio.h>
37 #endif
38
39 #include "bits.h"
40 #include "huffman.h"
41 #include "codebook/hcb.h"
42
43
44 /* static function declarations */
45 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len);
46 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp);
47 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp);
48 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp);
49 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp);
50 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp);
51 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp);
52 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp);
53 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp);
54 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp);
55 static int16_t huffman_codebook(uint8_t i);
56 static void vcb11_check_LAV(uint8_t cb, int16_t *sp);
57
huffman_scale_factor(bitfile * ld)58 int8_t huffman_scale_factor(bitfile *ld)
59 {
60 uint16_t offset = 0;
61
62 while (hcb_sf[offset][1])
63 {
64 uint8_t b = faad_get1bit(ld
65 DEBUGVAR(1,255,"huffman_scale_factor()"));
66 offset += hcb_sf[offset][b];
67
68 if (offset > 240)
69 {
70 /* printf("ERROR: offset into hcb_sf = %d >240!\n", offset); */
71 return -1;
72 }
73 }
74
75 return hcb_sf[offset][0];
76 }
77
78
79 hcb *hcb_table[] = {
80 0, hcb1_1, hcb2_1, 0, hcb4_1, 0, hcb6_1, 0, hcb8_1, 0, hcb10_1, hcb11_1
81 };
82
83 hcb_2_quad *hcb_2_quad_table[] = {
84 0, hcb1_2, hcb2_2, 0, hcb4_2, 0, 0, 0, 0, 0, 0, 0
85 };
86
87 hcb_2_pair *hcb_2_pair_table[] = {
88 0, 0, 0, 0, 0, 0, hcb6_2, 0, hcb8_2, 0, hcb10_2, hcb11_2
89 };
90
91 hcb_bin_pair *hcb_bin_table[] = {
92 0, 0, 0, 0, 0, hcb5, 0, hcb7, 0, hcb9, 0, 0
93 };
94
95 uint8_t hcbN[] = { 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 6, 5 };
96
97 /* defines whether a huffman codebook is unsigned or not */
98 /* Table 4.6.2 */
99 uint8_t unsigned_cb[] = { 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
100 /* codebook 16 to 31 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
101 };
102
103 int hcb_2_quad_table_size[] = { 0, 114, 86, 0, 185, 0, 0, 0, 0, 0, 0, 0 };
104 int hcb_2_pair_table_size[] = { 0, 0, 0, 0, 0, 0, 126, 0, 83, 0, 210, 373 };
105 int hcb_bin_table_size[] = { 0, 0, 0, 161, 0, 161, 0, 127, 0, 337, 0, 0 };
106
huffman_sign_bits(bitfile * ld,int16_t * sp,uint8_t len)107 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len)
108 {
109 uint8_t i;
110
111 for (i = 0; i < len; i++)
112 {
113 if(sp[i])
114 {
115 if(faad_get1bit(ld
116 DEBUGVAR(1,5,"huffman_sign_bits(): sign bit")) & 1)
117 {
118 sp[i] = -sp[i];
119 }
120 }
121 }
122 }
123
huffman_getescape(bitfile * ld,int16_t sp)124 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp)
125 {
126 uint8_t neg, i;
127 int16_t j;
128 int16_t off;
129
130 if (sp < 0)
131 {
132 if (sp != -16)
133 return sp;
134 neg = 1;
135 } else {
136 if (sp != 16)
137 return sp;
138 neg = 0;
139 }
140
141 for (i = 4; ; i++)
142 {
143 if (faad_get1bit(ld
144 DEBUGVAR(1,6,"huffman_getescape(): escape size")) == 0)
145 {
146 break;
147 }
148 }
149
150 off = (int16_t)faad_getbits(ld, i
151 DEBUGVAR(1,9,"huffman_getescape(): escape"));
152
153 j = off | (1<<i);
154 if (neg)
155 j = -j;
156
157 return j;
158 }
159
huffman_2step_quad(uint8_t cb,bitfile * ld,int16_t * sp)160 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp)
161 {
162 uint32_t cw;
163 uint16_t offset = 0;
164 uint8_t extra_bits;
165
166 cw = faad_showbits(ld, hcbN[cb]);
167 offset = hcb_table[cb][cw].offset;
168 extra_bits = hcb_table[cb][cw].extra_bits;
169
170 if (extra_bits)
171 {
172 /* we know for sure it's more than hcbN[cb] bits long */
173 faad_flushbits(ld, hcbN[cb]);
174 offset += (uint16_t)faad_showbits(ld, extra_bits);
175 faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]);
176 } else {
177 faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits);
178 }
179
180 if (offset > hcb_2_quad_table_size[cb])
181 {
182 /* printf("ERROR: offset into hcb_2_quad_table = %d >%d!\n", offset,
183 hcb_2_quad_table_size[cb]); */
184 return 10;
185 }
186
187 sp[0] = hcb_2_quad_table[cb][offset].x;
188 sp[1] = hcb_2_quad_table[cb][offset].y;
189 sp[2] = hcb_2_quad_table[cb][offset].v;
190 sp[3] = hcb_2_quad_table[cb][offset].w;
191
192 return 0;
193 }
194
huffman_2step_quad_sign(uint8_t cb,bitfile * ld,int16_t * sp)195 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
196 {
197 uint8_t err = huffman_2step_quad(cb, ld, sp);
198 huffman_sign_bits(ld, sp, QUAD_LEN);
199
200 return err;
201 }
202
huffman_2step_pair(uint8_t cb,bitfile * ld,int16_t * sp)203 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp)
204 {
205 uint32_t cw;
206 uint16_t offset = 0;
207 uint8_t extra_bits;
208
209 cw = faad_showbits(ld, hcbN[cb]);
210 offset = hcb_table[cb][cw].offset;
211 extra_bits = hcb_table[cb][cw].extra_bits;
212
213 if (extra_bits)
214 {
215 /* we know for sure it's more than hcbN[cb] bits long */
216 faad_flushbits(ld, hcbN[cb]);
217 offset += (uint16_t)faad_showbits(ld, extra_bits);
218 faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]);
219 } else {
220 faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits);
221 }
222
223 if (offset > hcb_2_pair_table_size[cb])
224 {
225 /* printf("ERROR: offset into hcb_2_pair_table = %d >%d!\n", offset,
226 hcb_2_pair_table_size[cb]); */
227 return 10;
228 }
229
230 sp[0] = hcb_2_pair_table[cb][offset].x;
231 sp[1] = hcb_2_pair_table[cb][offset].y;
232
233 return 0;
234 }
235
huffman_2step_pair_sign(uint8_t cb,bitfile * ld,int16_t * sp)236 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
237 {
238 uint8_t err = huffman_2step_pair(cb, ld, sp);
239 huffman_sign_bits(ld, sp, PAIR_LEN);
240
241 return err;
242 }
243
huffman_binary_quad(uint8_t cb,bitfile * ld,int16_t * sp)244 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp)
245 {
246 uint16_t offset = 0;
247
248 while (!hcb3[offset].is_leaf)
249 {
250 uint8_t b = faad_get1bit(ld
251 DEBUGVAR(1,255,"huffman_spectral_data():3"));
252 offset += hcb3[offset].data[b];
253 }
254
255 if (offset > hcb_bin_table_size[cb])
256 {
257 /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
258 hcb_bin_table_size[cb]); */
259 return 10;
260 }
261
262 sp[0] = hcb3[offset].data[0];
263 sp[1] = hcb3[offset].data[1];
264 sp[2] = hcb3[offset].data[2];
265 sp[3] = hcb3[offset].data[3];
266
267 return 0;
268 }
269
huffman_binary_quad_sign(uint8_t cb,bitfile * ld,int16_t * sp)270 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
271 {
272 uint8_t err = huffman_binary_quad(cb, ld, sp);
273 huffman_sign_bits(ld, sp, QUAD_LEN);
274
275 return err;
276 }
277
huffman_binary_pair(uint8_t cb,bitfile * ld,int16_t * sp)278 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp)
279 {
280 uint16_t offset = 0;
281
282 while (!hcb_bin_table[cb][offset].is_leaf)
283 {
284 uint8_t b = faad_get1bit(ld
285 DEBUGVAR(1,255,"huffman_spectral_data():9"));
286 offset += hcb_bin_table[cb][offset].data[b];
287 }
288
289 if (offset > hcb_bin_table_size[cb])
290 {
291 /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
292 hcb_bin_table_size[cb]); */
293 return 10;
294 }
295
296 sp[0] = hcb_bin_table[cb][offset].data[0];
297 sp[1] = hcb_bin_table[cb][offset].data[1];
298
299 return 0;
300 }
301
huffman_binary_pair_sign(uint8_t cb,bitfile * ld,int16_t * sp)302 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
303 {
304 uint8_t err = huffman_binary_pair(cb, ld, sp);
305 huffman_sign_bits(ld, sp, PAIR_LEN);
306
307 return err;
308 }
309
huffman_codebook(uint8_t i)310 static int16_t huffman_codebook(uint8_t i)
311 {
312 static const uint32_t data = 16428320;
313 if (i == 0) return (int16_t)(data >> 16) & 0xFFFF;
314 else return (int16_t)data & 0xFFFF;
315 }
316
vcb11_check_LAV(uint8_t cb,int16_t * sp)317 static void vcb11_check_LAV(uint8_t cb, int16_t *sp)
318 {
319 static const uint16_t vcb11_LAV_tab[] = {
320 16, 31, 47, 63, 95, 127, 159, 191, 223,
321 255, 319, 383, 511, 767, 1023, 2047
322 };
323 uint16_t max = 0;
324
325 if (cb < 16 || cb > 31)
326 return;
327
328 max = vcb11_LAV_tab[cb - 16];
329
330 if ((abs(sp[0]) > max) || (abs(sp[1]) > max))
331 {
332 sp[0] = 0;
333 sp[1] = 0;
334 }
335 }
336
huffman_spectral_data(uint8_t cb,bitfile * ld,int16_t * sp)337 uint8_t huffman_spectral_data(uint8_t cb, bitfile *ld, int16_t *sp)
338 {
339 switch (cb)
340 {
341 case 1: /* 2-step method for data quadruples */
342 case 2:
343 return huffman_2step_quad(cb, ld, sp);
344 case 3: /* binary search for data quadruples */
345 return huffman_binary_quad_sign(cb, ld, sp);
346 case 4: /* 2-step method for data quadruples */
347 return huffman_2step_quad_sign(cb, ld, sp);
348 case 5: /* binary search for data pairs */
349 return huffman_binary_pair(cb, ld, sp);
350 case 6: /* 2-step method for data pairs */
351 return huffman_2step_pair(cb, ld, sp);
352 case 7: /* binary search for data pairs */
353 case 9:
354 return huffman_binary_pair_sign(cb, ld, sp);
355 case 8: /* 2-step method for data pairs */
356 case 10:
357 return huffman_2step_pair_sign(cb, ld, sp);
358 case 12: {
359 uint8_t err = huffman_2step_pair(11, ld, sp);
360 sp[0] = huffman_codebook(0); sp[1] = huffman_codebook(1);
361 return err; }
362 case 11:
363 {
364 uint8_t err = huffman_2step_pair_sign(11, ld, sp);
365 sp[0] = huffman_getescape(ld, sp[0]);
366 sp[1] = huffman_getescape(ld, sp[1]);
367 return err;
368 }
369 #ifdef ERROR_RESILIENCE
370 /* VCB11 uses codebook 11 */
371 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
372 case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
373 {
374 uint8_t err = huffman_2step_pair_sign(11, ld, sp);
375 sp[0] = huffman_getescape(ld, sp[0]);
376 sp[1] = huffman_getescape(ld, sp[1]);
377
378 /* check LAV (Largest Absolute Value) */
379 /* this finds errors in the ESCAPE signal */
380 vcb11_check_LAV(cb, sp);
381
382 return err;
383 }
384 #endif
385 default:
386 /* Non existent codebook number, something went wrong */
387 return 11;
388 }
389
390 return 0;
391 }
392
393
394 #ifdef ERROR_RESILIENCE
395
396 /* Special version of huffman_spectral_data
397 Will not read from a bitfile but a bits_t structure.
398 Will keep track of the bits decoded and return the number of bits remaining.
399 Do not read more than ld->len, return -1 if codeword would be longer */
400
huffman_spectral_data_2(uint8_t cb,bits_t * ld,int16_t * sp)401 int8_t huffman_spectral_data_2(uint8_t cb, bits_t *ld, int16_t *sp)
402 {
403 uint32_t cw;
404 uint16_t offset = 0;
405 uint8_t extra_bits;
406 uint8_t i, vcb11 = 0;
407
408
409 switch (cb)
410 {
411 case 1: /* 2-step method for data quadruples */
412 case 2:
413 case 4:
414
415 cw = showbits_hcr(ld, hcbN[cb]);
416 offset = hcb_table[cb][cw].offset;
417 extra_bits = hcb_table[cb][cw].extra_bits;
418
419 if (extra_bits)
420 {
421 /* we know for sure it's more than hcbN[cb] bits long */
422 if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
423 offset += (uint16_t)showbits_hcr(ld, extra_bits);
424 if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]) ) return -1;
425 } else {
426 if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits) ) return -1;
427 }
428
429 sp[0] = hcb_2_quad_table[cb][offset].x;
430 sp[1] = hcb_2_quad_table[cb][offset].y;
431 sp[2] = hcb_2_quad_table[cb][offset].v;
432 sp[3] = hcb_2_quad_table[cb][offset].w;
433 break;
434
435 case 6: /* 2-step method for data pairs */
436 case 8:
437 case 10:
438 case 11:
439 /* VCB11 uses codebook 11 */
440 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
441 case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
442
443 if (cb >= 16)
444 {
445 /* store the virtual codebook */
446 vcb11 = cb;
447 cb = 11;
448 }
449
450 cw = showbits_hcr(ld, hcbN[cb]);
451 offset = hcb_table[cb][cw].offset;
452 extra_bits = hcb_table[cb][cw].extra_bits;
453
454 if (extra_bits)
455 {
456 /* we know for sure it's more than hcbN[cb] bits long */
457 if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
458 offset += (uint16_t)showbits_hcr(ld, extra_bits);
459 if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]) ) return -1;
460 } else {
461 if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits) ) return -1;
462 }
463 sp[0] = hcb_2_pair_table[cb][offset].x;
464 sp[1] = hcb_2_pair_table[cb][offset].y;
465 break;
466
467 case 3: /* binary search for data quadruples */
468
469 while (!hcb3[offset].is_leaf)
470 {
471 uint8_t b;
472
473 if ( get1bit_hcr(ld, &b) ) return -1;
474 offset += hcb3[offset].data[b];
475 }
476
477 sp[0] = hcb3[offset].data[0];
478 sp[1] = hcb3[offset].data[1];
479 sp[2] = hcb3[offset].data[2];
480 sp[3] = hcb3[offset].data[3];
481
482 break;
483
484 case 5: /* binary search for data pairs */
485 case 7:
486 case 9:
487
488 while (!hcb_bin_table[cb][offset].is_leaf)
489 {
490 uint8_t b;
491
492 if (get1bit_hcr(ld, &b) ) return -1;
493 offset += hcb_bin_table[cb][offset].data[b];
494 }
495
496 sp[0] = hcb_bin_table[cb][offset].data[0];
497 sp[1] = hcb_bin_table[cb][offset].data[1];
498
499 break;
500 }
501
502 /* decode sign bits */
503 if (unsigned_cb[cb])
504 {
505 for(i = 0; i < ((cb < FIRST_PAIR_HCB) ? QUAD_LEN : PAIR_LEN); i++)
506 {
507 if(sp[i])
508 {
509 uint8_t b;
510 if ( get1bit_hcr(ld, &b) ) return -1;
511 if (b != 0) {
512 sp[i] = -sp[i];
513 }
514 }
515 }
516 }
517
518 /* decode huffman escape bits */
519 if ((cb == ESC_HCB) || (cb >= 16))
520 {
521 uint8_t k;
522 for (k = 0; k < 2; k++)
523 {
524 if ((sp[k] == 16) || (sp[k] == -16))
525 {
526 uint8_t neg, i;
527 int32_t j;
528 uint32_t off;
529
530 neg = (sp[k] < 0) ? 1 : 0;
531
532 for (i = 4; ; i++)
533 {
534 uint8_t b;
535 if (get1bit_hcr(ld, &b))
536 return -1;
537 if (b == 0)
538 break;
539 }
540
541 if (getbits_hcr(ld, i, &off))
542 return -1;
543 j = off + (1<<i);
544 sp[k] = (int16_t)((neg) ? -j : j);
545 }
546 }
547
548 if (vcb11 != 0)
549 {
550 /* check LAV (Largest Absolute Value) */
551 /* this finds errors in the ESCAPE signal */
552 vcb11_check_LAV(vcb11, sp);
553 }
554 }
555 return ld->len;
556 }
557
558 #endif
559
560