Ignore svn changes up to r30324
[mplayer/glamo.git] / libfaad2 / huffman.c
blob435e3e6b8029dcf13dfbbd8bb30788667b0adb66
1 /*
2 ** FAAD2 - Freeware Advanced Audio (AAC) Decoder including SBR decoding
3 ** Copyright (C) 2003-2004 M. Bakker, Ahead Software 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.
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.
19 ** Any non-GPL usage of this software or parts of this software is strictly
20 ** forbidden.
22 ** Commercial non-GPL licensing of this software is possible.
23 ** For more info contact Ahead Software through Mpeg4AAClicense@nero.com.
25 ** $Id: huffman.c,v 1.22 2004/09/04 14:56:28 menno Exp $
26 **/
28 #include "common.h"
29 #include "structs.h"
31 #include <stdlib.h>
32 #ifdef ANALYSIS
33 #include <stdio.h>
34 #endif
36 #include "bits.h"
37 #include "huffman.h"
38 #include "codebook/hcb.h"
41 /* static function declarations */
42 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len);
43 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp);
44 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp);
45 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp);
46 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp);
47 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp);
48 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp);
49 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp);
50 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp);
51 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp);
52 static int16_t huffman_codebook(uint8_t i);
53 static void vcb11_check_LAV(uint8_t cb, int16_t *sp);
55 int8_t huffman_scale_factor(bitfile *ld)
57 uint16_t offset = 0;
59 while (hcb_sf[offset][1])
61 uint8_t b = faad_get1bit(ld
62 DEBUGVAR(1,255,"huffman_scale_factor()"));
63 offset += hcb_sf[offset][b];
65 if (offset > 240)
67 /* printf("ERROR: offset into hcb_sf = %d >240!\n", offset); */
68 return -1;
72 return hcb_sf[offset][0];
76 hcb *hcb_table[] = {
77 0, hcb1_1, hcb2_1, 0, hcb4_1, 0, hcb6_1, 0, hcb8_1, 0, hcb10_1, hcb11_1
80 hcb_2_quad *hcb_2_quad_table[] = {
81 0, hcb1_2, hcb2_2, 0, hcb4_2, 0, 0, 0, 0, 0, 0, 0
84 hcb_2_pair *hcb_2_pair_table[] = {
85 0, 0, 0, 0, 0, 0, hcb6_2, 0, hcb8_2, 0, hcb10_2, hcb11_2
88 hcb_bin_pair *hcb_bin_table[] = {
89 0, 0, 0, 0, 0, hcb5, 0, hcb7, 0, hcb9, 0, 0
92 uint8_t hcbN[] = { 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 6, 5 };
94 /* defines whether a huffman codebook is unsigned or not */
95 /* Table 4.6.2 */
96 uint8_t unsigned_cb[] = { 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
97 /* codebook 16 to 31 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
100 int hcb_2_quad_table_size[] = { 0, 114, 86, 0, 185, 0, 0, 0, 0, 0, 0, 0 };
101 int hcb_2_pair_table_size[] = { 0, 0, 0, 0, 0, 0, 126, 0, 83, 0, 210, 373 };
102 int hcb_bin_table_size[] = { 0, 0, 0, 161, 0, 161, 0, 127, 0, 337, 0, 0 };
104 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len)
106 uint8_t i;
108 for (i = 0; i < len; i++)
110 if(sp[i])
112 if(faad_get1bit(ld
113 DEBUGVAR(1,5,"huffman_sign_bits(): sign bit")) & 1)
115 sp[i] = -sp[i];
121 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp)
123 uint8_t neg, i;
124 int16_t j;
125 int16_t off;
127 if (sp < 0)
129 if (sp != -16)
130 return sp;
131 neg = 1;
132 } else {
133 if (sp != 16)
134 return sp;
135 neg = 0;
138 for (i = 4; ; i++)
140 if (faad_get1bit(ld
141 DEBUGVAR(1,6,"huffman_getescape(): escape size")) == 0)
143 break;
147 off = (int16_t)faad_getbits(ld, i
148 DEBUGVAR(1,9,"huffman_getescape(): escape"));
150 j = off | (1<<i);
151 if (neg)
152 j = -j;
154 return j;
157 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp)
159 uint32_t cw;
160 uint16_t offset = 0;
161 uint8_t extra_bits;
163 cw = faad_showbits(ld, hcbN[cb]);
164 offset = hcb_table[cb][cw].offset;
165 extra_bits = hcb_table[cb][cw].extra_bits;
167 if (extra_bits)
169 /* we know for sure it's more than hcbN[cb] bits long */
170 faad_flushbits(ld, hcbN[cb]);
171 offset += (uint16_t)faad_showbits(ld, extra_bits);
172 faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]);
173 } else {
174 faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits);
177 if (offset > hcb_2_quad_table_size[cb])
179 /* printf("ERROR: offset into hcb_2_quad_table = %d >%d!\n", offset,
180 hcb_2_quad_table_size[cb]); */
181 return 10;
184 sp[0] = hcb_2_quad_table[cb][offset].x;
185 sp[1] = hcb_2_quad_table[cb][offset].y;
186 sp[2] = hcb_2_quad_table[cb][offset].v;
187 sp[3] = hcb_2_quad_table[cb][offset].w;
189 return 0;
192 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
194 uint8_t err = huffman_2step_quad(cb, ld, sp);
195 huffman_sign_bits(ld, sp, QUAD_LEN);
197 return err;
200 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp)
202 uint32_t cw;
203 uint16_t offset = 0;
204 uint8_t extra_bits;
206 cw = faad_showbits(ld, hcbN[cb]);
207 offset = hcb_table[cb][cw].offset;
208 extra_bits = hcb_table[cb][cw].extra_bits;
210 if (extra_bits)
212 /* we know for sure it's more than hcbN[cb] bits long */
213 faad_flushbits(ld, hcbN[cb]);
214 offset += (uint16_t)faad_showbits(ld, extra_bits);
215 faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]);
216 } else {
217 faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits);
220 if (offset > hcb_2_pair_table_size[cb])
222 /* printf("ERROR: offset into hcb_2_pair_table = %d >%d!\n", offset,
223 hcb_2_pair_table_size[cb]); */
224 return 10;
227 sp[0] = hcb_2_pair_table[cb][offset].x;
228 sp[1] = hcb_2_pair_table[cb][offset].y;
230 return 0;
233 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
235 uint8_t err = huffman_2step_pair(cb, ld, sp);
236 huffman_sign_bits(ld, sp, PAIR_LEN);
238 return err;
241 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp)
243 uint16_t offset = 0;
245 while (!hcb3[offset].is_leaf)
247 uint8_t b = faad_get1bit(ld
248 DEBUGVAR(1,255,"huffman_spectral_data():3"));
249 offset += hcb3[offset].data[b];
252 if (offset > hcb_bin_table_size[cb])
254 /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
255 hcb_bin_table_size[cb]); */
256 return 10;
259 sp[0] = hcb3[offset].data[0];
260 sp[1] = hcb3[offset].data[1];
261 sp[2] = hcb3[offset].data[2];
262 sp[3] = hcb3[offset].data[3];
264 return 0;
267 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
269 uint8_t err = huffman_binary_quad(cb, ld, sp);
270 huffman_sign_bits(ld, sp, QUAD_LEN);
272 return err;
275 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp)
277 uint16_t offset = 0;
279 while (!hcb_bin_table[cb][offset].is_leaf)
281 uint8_t b = faad_get1bit(ld
282 DEBUGVAR(1,255,"huffman_spectral_data():9"));
283 offset += hcb_bin_table[cb][offset].data[b];
286 if (offset > hcb_bin_table_size[cb])
288 /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
289 hcb_bin_table_size[cb]); */
290 return 10;
293 sp[0] = hcb_bin_table[cb][offset].data[0];
294 sp[1] = hcb_bin_table[cb][offset].data[1];
296 return 0;
299 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
301 uint8_t err = huffman_binary_pair(cb, ld, sp);
302 huffman_sign_bits(ld, sp, PAIR_LEN);
304 return err;
307 static int16_t huffman_codebook(uint8_t i)
309 static const uint32_t data = 16428320;
310 if (i == 0) return (int16_t)(data >> 16) & 0xFFFF;
311 else return (int16_t)data & 0xFFFF;
314 static void vcb11_check_LAV(uint8_t cb, int16_t *sp)
316 static const uint16_t vcb11_LAV_tab[] = {
317 16, 31, 47, 63, 95, 127, 159, 191, 223,
318 255, 319, 383, 511, 767, 1023, 2047
320 uint16_t max = 0;
322 if (cb < 16 || cb > 31)
323 return;
325 max = vcb11_LAV_tab[cb - 16];
327 if ((abs(sp[0]) > max) || (abs(sp[1]) > max))
329 sp[0] = 0;
330 sp[1] = 0;
334 uint8_t huffman_spectral_data(uint8_t cb, bitfile *ld, int16_t *sp)
336 switch (cb)
338 case 1: /* 2-step method for data quadruples */
339 case 2:
340 return huffman_2step_quad(cb, ld, sp);
341 case 3: /* binary search for data quadruples */
342 return huffman_binary_quad_sign(cb, ld, sp);
343 case 4: /* 2-step method for data quadruples */
344 return huffman_2step_quad_sign(cb, ld, sp);
345 case 5: /* binary search for data pairs */
346 return huffman_binary_pair(cb, ld, sp);
347 case 6: /* 2-step method for data pairs */
348 return huffman_2step_pair(cb, ld, sp);
349 case 7: /* binary search for data pairs */
350 case 9:
351 return huffman_binary_pair_sign(cb, ld, sp);
352 case 8: /* 2-step method for data pairs */
353 case 10:
354 return huffman_2step_pair_sign(cb, ld, sp);
355 case 12: {
356 uint8_t err = huffman_2step_pair(11, ld, sp);
357 sp[0] = huffman_codebook(0); sp[1] = huffman_codebook(1);
358 return err; }
359 case 11:
361 uint8_t err = huffman_2step_pair_sign(11, ld, sp);
362 sp[0] = huffman_getescape(ld, sp[0]);
363 sp[1] = huffman_getescape(ld, sp[1]);
364 return err;
366 #ifdef ERROR_RESILIENCE
367 /* VCB11 uses codebook 11 */
368 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
369 case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
371 uint8_t err = huffman_2step_pair_sign(11, ld, sp);
372 sp[0] = huffman_getescape(ld, sp[0]);
373 sp[1] = huffman_getescape(ld, sp[1]);
375 /* check LAV (Largest Absolute Value) */
376 /* this finds errors in the ESCAPE signal */
377 vcb11_check_LAV(cb, sp);
379 return err;
381 #endif
382 default:
383 /* Non existent codebook number, something went wrong */
384 return 11;
387 return 0;
391 #ifdef ERROR_RESILIENCE
393 /* Special version of huffman_spectral_data
394 Will not read from a bitfile but a bits_t structure.
395 Will keep track of the bits decoded and return the number of bits remaining.
396 Do not read more than ld->len, return -1 if codeword would be longer */
398 int8_t huffman_spectral_data_2(uint8_t cb, bits_t *ld, int16_t *sp)
400 uint32_t cw;
401 uint16_t offset = 0;
402 uint8_t extra_bits;
403 uint8_t i, vcb11 = 0;
406 switch (cb)
408 case 1: /* 2-step method for data quadruples */
409 case 2:
410 case 4:
412 cw = showbits_hcr(ld, hcbN[cb]);
413 offset = hcb_table[cb][cw].offset;
414 extra_bits = hcb_table[cb][cw].extra_bits;
416 if (extra_bits)
418 /* we know for sure it's more than hcbN[cb] bits long */
419 if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
420 offset += (uint16_t)showbits_hcr(ld, extra_bits);
421 if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]) ) return -1;
422 } else {
423 if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits) ) return -1;
426 sp[0] = hcb_2_quad_table[cb][offset].x;
427 sp[1] = hcb_2_quad_table[cb][offset].y;
428 sp[2] = hcb_2_quad_table[cb][offset].v;
429 sp[3] = hcb_2_quad_table[cb][offset].w;
430 break;
432 case 6: /* 2-step method for data pairs */
433 case 8:
434 case 10:
435 case 11:
436 /* VCB11 uses codebook 11 */
437 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
438 case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
440 if (cb >= 16)
442 /* store the virtual codebook */
443 vcb11 = cb;
444 cb = 11;
447 cw = showbits_hcr(ld, hcbN[cb]);
448 offset = hcb_table[cb][cw].offset;
449 extra_bits = hcb_table[cb][cw].extra_bits;
451 if (extra_bits)
453 /* we know for sure it's more than hcbN[cb] bits long */
454 if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
455 offset += (uint16_t)showbits_hcr(ld, extra_bits);
456 if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]) ) return -1;
457 } else {
458 if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits) ) return -1;
460 sp[0] = hcb_2_pair_table[cb][offset].x;
461 sp[1] = hcb_2_pair_table[cb][offset].y;
462 break;
464 case 3: /* binary search for data quadruples */
466 while (!hcb3[offset].is_leaf)
468 uint8_t b;
470 if ( get1bit_hcr(ld, &b) ) return -1;
471 offset += hcb3[offset].data[b];
474 sp[0] = hcb3[offset].data[0];
475 sp[1] = hcb3[offset].data[1];
476 sp[2] = hcb3[offset].data[2];
477 sp[3] = hcb3[offset].data[3];
479 break;
481 case 5: /* binary search for data pairs */
482 case 7:
483 case 9:
485 while (!hcb_bin_table[cb][offset].is_leaf)
487 uint8_t b;
489 if (get1bit_hcr(ld, &b) ) return -1;
490 offset += hcb_bin_table[cb][offset].data[b];
493 sp[0] = hcb_bin_table[cb][offset].data[0];
494 sp[1] = hcb_bin_table[cb][offset].data[1];
496 break;
499 /* decode sign bits */
500 if (unsigned_cb[cb])
502 for(i = 0; i < ((cb < FIRST_PAIR_HCB) ? QUAD_LEN : PAIR_LEN); i++)
504 if(sp[i])
506 uint8_t b;
507 if ( get1bit_hcr(ld, &b) ) return -1;
508 if (b != 0) {
509 sp[i] = -sp[i];
515 /* decode huffman escape bits */
516 if ((cb == ESC_HCB) || (cb >= 16))
518 uint8_t k;
519 for (k = 0; k < 2; k++)
521 if ((sp[k] == 16) || (sp[k] == -16))
523 uint8_t neg, i;
524 int32_t j;
525 uint32_t off;
527 neg = (sp[k] < 0) ? 1 : 0;
529 for (i = 4; ; i++)
531 uint8_t b;
532 if (get1bit_hcr(ld, &b))
533 return -1;
534 if (b == 0)
535 break;
538 if (getbits_hcr(ld, i, &off))
539 return -1;
540 j = off + (1<<i);
541 sp[k] = (int16_t)((neg) ? -j : j);
545 if (vcb11 != 0)
547 /* check LAV (Largest Absolute Value) */
548 /* this finds errors in the ESCAPE signal */
549 vcb11_check_LAV(vcb11, sp);
552 return ld->len;
555 #endif