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 uint8_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 uint8_t huffman_getescape(bitfile *ld, int16_t *sp)
125 {
126 uint8_t neg, i;
127 int16_t j;
128 int16_t off;
129 int16_t x = *sp;
130
131 if (x < 0)
132 {
133 if (x != -16)
134 return 0;
135 neg = 1;
136 } else {
137 if (x != 16)
138 return 0;
139 neg = 0;
140 }
141
142 for (i = 4; i < 16; i++)
143 {
144 if (faad_get1bit(ld
145 DEBUGVAR(1,6,"huffman_getescape(): escape size")) == 0)
146 {
147 break;
148 }
149 }
150 if (i >= 16)
151 return 10;
152
153 off = (int16_t)faad_getbits(ld, i
154 DEBUGVAR(1,9,"huffman_getescape(): escape"));
155
156 j = off | (1<<i);
157 if (neg)
158 j = -j;
159
160 *sp = j;
161 return 0;
162 }
163
huffman_2step_quad(uint8_t cb,bitfile * ld,int16_t * sp)164 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp)
165 {
166 uint32_t cw;
167 uint16_t offset = 0;
168 uint8_t extra_bits;
169
170 cw = faad_showbits(ld, hcbN[cb]);
171 offset = hcb_table[cb][cw].offset;
172 extra_bits = hcb_table[cb][cw].extra_bits;
173
174 if (extra_bits)
175 {
176 /* we know for sure it's more than hcbN[cb] bits long */
177 faad_flushbits(ld, hcbN[cb]);
178 offset += (uint16_t)faad_showbits(ld, extra_bits);
179 faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]);
180 } else {
181 faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits);
182 }
183
184 if (offset > hcb_2_quad_table_size[cb])
185 {
186 /* printf("ERROR: offset into hcb_2_quad_table = %d >%d!\n", offset,
187 hcb_2_quad_table_size[cb]); */
188 return 10;
189 }
190
191 sp[0] = hcb_2_quad_table[cb][offset].x;
192 sp[1] = hcb_2_quad_table[cb][offset].y;
193 sp[2] = hcb_2_quad_table[cb][offset].v;
194 sp[3] = hcb_2_quad_table[cb][offset].w;
195
196 return 0;
197 }
198
huffman_2step_quad_sign(uint8_t cb,bitfile * ld,int16_t * sp)199 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
200 {
201 uint8_t err = huffman_2step_quad(cb, ld, sp);
202 huffman_sign_bits(ld, sp, QUAD_LEN);
203
204 return err;
205 }
206
huffman_2step_pair(uint8_t cb,bitfile * ld,int16_t * sp)207 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp)
208 {
209 uint32_t cw;
210 uint16_t offset = 0;
211 uint8_t extra_bits;
212
213 cw = faad_showbits(ld, hcbN[cb]);
214 offset = hcb_table[cb][cw].offset;
215 extra_bits = hcb_table[cb][cw].extra_bits;
216
217 if (extra_bits)
218 {
219 /* we know for sure it's more than hcbN[cb] bits long */
220 faad_flushbits(ld, hcbN[cb]);
221 offset += (uint16_t)faad_showbits(ld, extra_bits);
222 faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]);
223 } else {
224 faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits);
225 }
226
227 if (offset > hcb_2_pair_table_size[cb])
228 {
229 /* printf("ERROR: offset into hcb_2_pair_table = %d >%d!\n", offset,
230 hcb_2_pair_table_size[cb]); */
231 return 10;
232 }
233
234 sp[0] = hcb_2_pair_table[cb][offset].x;
235 sp[1] = hcb_2_pair_table[cb][offset].y;
236
237 return 0;
238 }
239
huffman_2step_pair_sign(uint8_t cb,bitfile * ld,int16_t * sp)240 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
241 {
242 uint8_t err = huffman_2step_pair(cb, ld, sp);
243 huffman_sign_bits(ld, sp, PAIR_LEN);
244
245 return err;
246 }
247
huffman_binary_quad(uint8_t cb,bitfile * ld,int16_t * sp)248 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp)
249 {
250 uint16_t offset = 0;
251
252 while (!hcb3[offset].is_leaf)
253 {
254 uint8_t b = faad_get1bit(ld
255 DEBUGVAR(1,255,"huffman_spectral_data():3"));
256 offset += hcb3[offset].data[b];
257 }
258
259 if (offset > hcb_bin_table_size[cb])
260 {
261 /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
262 hcb_bin_table_size[cb]); */
263 return 10;
264 }
265
266 sp[0] = hcb3[offset].data[0];
267 sp[1] = hcb3[offset].data[1];
268 sp[2] = hcb3[offset].data[2];
269 sp[3] = hcb3[offset].data[3];
270
271 return 0;
272 }
273
huffman_binary_quad_sign(uint8_t cb,bitfile * ld,int16_t * sp)274 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
275 {
276 uint8_t err = huffman_binary_quad(cb, ld, sp);
277 huffman_sign_bits(ld, sp, QUAD_LEN);
278
279 return err;
280 }
281
huffman_binary_pair(uint8_t cb,bitfile * ld,int16_t * sp)282 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp)
283 {
284 uint16_t offset = 0;
285
286 while (!hcb_bin_table[cb][offset].is_leaf)
287 {
288 uint8_t b = faad_get1bit(ld
289 DEBUGVAR(1,255,"huffman_spectral_data():9"));
290 offset += hcb_bin_table[cb][offset].data[b];
291 }
292
293 if (offset > hcb_bin_table_size[cb])
294 {
295 /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
296 hcb_bin_table_size[cb]); */
297 return 10;
298 }
299
300 sp[0] = hcb_bin_table[cb][offset].data[0];
301 sp[1] = hcb_bin_table[cb][offset].data[1];
302
303 return 0;
304 }
305
huffman_binary_pair_sign(uint8_t cb,bitfile * ld,int16_t * sp)306 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
307 {
308 uint8_t err = huffman_binary_pair(cb, ld, sp);
309 huffman_sign_bits(ld, sp, PAIR_LEN);
310
311 return err;
312 }
313
huffman_codebook(uint8_t i)314 static int16_t huffman_codebook(uint8_t i)
315 {
316 static const uint32_t data = 16428320;
317 if (i == 0) return (int16_t)(data >> 16) & 0xFFFF;
318 else return (int16_t)data & 0xFFFF;
319 }
320
vcb11_check_LAV(uint8_t cb,int16_t * sp)321 static void vcb11_check_LAV(uint8_t cb, int16_t *sp)
322 {
323 static const uint16_t vcb11_LAV_tab[] = {
324 16, 31, 47, 63, 95, 127, 159, 191, 223,
325 255, 319, 383, 511, 767, 1023, 2047
326 };
327 uint16_t max = 0;
328
329 if (cb < 16 || cb > 31)
330 return;
331
332 max = vcb11_LAV_tab[cb - 16];
333
334 if ((abs(sp[0]) > max) || (abs(sp[1]) > max))
335 {
336 sp[0] = 0;
337 sp[1] = 0;
338 }
339 }
340
huffman_spectral_data(uint8_t cb,bitfile * ld,int16_t * sp)341 uint8_t huffman_spectral_data(uint8_t cb, bitfile *ld, int16_t *sp)
342 {
343 switch (cb)
344 {
345 case 1: /* 2-step method for data quadruples */
346 case 2:
347 return huffman_2step_quad(cb, ld, sp);
348 case 3: /* binary search for data quadruples */
349 return huffman_binary_quad_sign(cb, ld, sp);
350 case 4: /* 2-step method for data quadruples */
351 return huffman_2step_quad_sign(cb, ld, sp);
352 case 5: /* binary search for data pairs */
353 return huffman_binary_pair(cb, ld, sp);
354 case 6: /* 2-step method for data pairs */
355 return huffman_2step_pair(cb, ld, sp);
356 case 7: /* binary search for data pairs */
357 case 9:
358 return huffman_binary_pair_sign(cb, ld, sp);
359 case 8: /* 2-step method for data pairs */
360 case 10:
361 return huffman_2step_pair_sign(cb, ld, sp);
362 case 12: {
363 uint8_t err = huffman_2step_pair(11, ld, sp);
364 sp[0] = huffman_codebook(0); sp[1] = huffman_codebook(1);
365 return err; }
366 case 11:
367 {
368 uint8_t err = huffman_2step_pair_sign(11, ld, sp);
369 if (!err)
370 err = huffman_getescape(ld, &sp[0]);
371 if (!err)
372 err = huffman_getescape(ld, &sp[1]);
373 return err;
374 }
375 #ifdef ERROR_RESILIENCE
376 /* VCB11 uses codebook 11 */
377 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
378 case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
379 {
380 uint8_t err = huffman_2step_pair_sign(11, ld, sp);
381 if (!err)
382 err = huffman_getescape(ld, &sp[0]);
383 if (!err)
384 err = huffman_getescape(ld, &sp[1]);
385
386 /* check LAV (Largest Absolute Value) */
387 /* this finds errors in the ESCAPE signal */
388 vcb11_check_LAV(cb, sp);
389
390 return err;
391 }
392 #endif
393 default:
394 /* Non existent codebook number, something went wrong */
395 return 11;
396 }
397
398 return 0;
399 }
400
401
402 #ifdef ERROR_RESILIENCE
403
404 /* Special version of huffman_spectral_data
405 Will not read from a bitfile but a bits_t structure.
406 Will keep track of the bits decoded and return the number of bits remaining.
407 Do not read more than ld->len, return -1 if codeword would be longer */
408
huffman_spectral_data_2(uint8_t cb,bits_t * ld,int16_t * sp)409 int8_t huffman_spectral_data_2(uint8_t cb, bits_t *ld, int16_t *sp)
410 {
411 uint32_t cw;
412 uint16_t offset = 0;
413 uint8_t extra_bits;
414 uint8_t i, vcb11 = 0;
415
416
417 switch (cb)
418 {
419 case 1: /* 2-step method for data quadruples */
420 case 2:
421 case 4:
422
423 cw = showbits_hcr(ld, hcbN[cb]);
424 offset = hcb_table[cb][cw].offset;
425 extra_bits = hcb_table[cb][cw].extra_bits;
426
427 if (extra_bits)
428 {
429 /* we know for sure it's more than hcbN[cb] bits long */
430 if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
431 offset += (uint16_t)showbits_hcr(ld, extra_bits);
432 if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]) ) return -1;
433 } else {
434 if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits) ) return -1;
435 }
436
437 sp[0] = hcb_2_quad_table[cb][offset].x;
438 sp[1] = hcb_2_quad_table[cb][offset].y;
439 sp[2] = hcb_2_quad_table[cb][offset].v;
440 sp[3] = hcb_2_quad_table[cb][offset].w;
441 break;
442
443 case 6: /* 2-step method for data pairs */
444 case 8:
445 case 10:
446 case 11:
447 /* VCB11 uses codebook 11 */
448 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
449 case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
450
451 if (cb >= 16)
452 {
453 /* store the virtual codebook */
454 vcb11 = cb;
455 cb = 11;
456 }
457
458 cw = showbits_hcr(ld, hcbN[cb]);
459 offset = hcb_table[cb][cw].offset;
460 extra_bits = hcb_table[cb][cw].extra_bits;
461
462 if (extra_bits)
463 {
464 /* we know for sure it's more than hcbN[cb] bits long */
465 if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
466 offset += (uint16_t)showbits_hcr(ld, extra_bits);
467 if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]) ) return -1;
468 } else {
469 if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits) ) return -1;
470 }
471 sp[0] = hcb_2_pair_table[cb][offset].x;
472 sp[1] = hcb_2_pair_table[cb][offset].y;
473 break;
474
475 case 3: /* binary search for data quadruples */
476
477 while (!hcb3[offset].is_leaf)
478 {
479 uint8_t b;
480
481 if ( get1bit_hcr(ld, &b) ) return -1;
482 offset += hcb3[offset].data[b];
483 }
484
485 sp[0] = hcb3[offset].data[0];
486 sp[1] = hcb3[offset].data[1];
487 sp[2] = hcb3[offset].data[2];
488 sp[3] = hcb3[offset].data[3];
489
490 break;
491
492 case 5: /* binary search for data pairs */
493 case 7:
494 case 9:
495
496 while (!hcb_bin_table[cb][offset].is_leaf)
497 {
498 uint8_t b;
499
500 if (get1bit_hcr(ld, &b) ) return -1;
501 offset += hcb_bin_table[cb][offset].data[b];
502 }
503
504 sp[0] = hcb_bin_table[cb][offset].data[0];
505 sp[1] = hcb_bin_table[cb][offset].data[1];
506
507 break;
508 }
509
510 /* decode sign bits */
511 if (unsigned_cb[cb])
512 {
513 for(i = 0; i < ((cb < FIRST_PAIR_HCB) ? QUAD_LEN : PAIR_LEN); i++)
514 {
515 if(sp[i])
516 {
517 uint8_t b;
518 if ( get1bit_hcr(ld, &b) ) return -1;
519 if (b != 0) {
520 sp[i] = -sp[i];
521 }
522 }
523 }
524 }
525
526 /* decode huffman escape bits */
527 if ((cb == ESC_HCB) || (cb >= 16))
528 {
529 uint8_t k;
530 for (k = 0; k < 2; k++)
531 {
532 if ((sp[k] == 16) || (sp[k] == -16))
533 {
534 uint8_t neg, i;
535 int32_t j;
536 uint32_t off;
537
538 neg = (sp[k] < 0) ? 1 : 0;
539
540 for (i = 4; ; i++)
541 {
542 uint8_t b;
543 if (get1bit_hcr(ld, &b))
544 return -1;
545 if (b == 0)
546 break;
547 }
548
549 if (getbits_hcr(ld, i, &off))
550 return -1;
551 j = off + (1<<i);
552 sp[k] = (int16_t)((neg) ? -j : j);
553 }
554 }
555
556 if (vcb11 != 0)
557 {
558 /* check LAV (Largest Absolute Value) */
559 /* this finds errors in the ESCAPE signal */
560 vcb11_check_LAV(vcb11, sp);
561 }
562 }
563 return ld->len;
564 }
565
566 #endif
567
568