libfaad2/huffman.c

   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.
  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 ** Commercial non-GPL licensing of this software is possible.
  23 ** For more info contact Ahead Software through Mpeg4AAClicense@nero.com.
  24 **
  25 ** $Id: huffman.c,v 1.22 2004/09/04 14:56:28 menno Exp $
  26 **/
  27
  28 #include "common.h"
  29 #include "structs.h"
  30
  31 #include <stdlib.h>
  32 #ifdef ANALYSIS
  33 #include <stdio.h>
  34 #endif
  35
  36 #include "bits.h"
  37 #include "huffman.h"
  38 #include "codebook/hcb.h"
  39
  40
  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);
  54
  55 int8_t huffman_scale_factor(bitfile *ld)
  56 {
  57     uint16_t offset = 0;
  58
  59     while (hcb_sf[offset][1])
  60     {
  61         uint8_t b = faad_get1bit(ld
  62             DEBUGVAR(1,255,"huffman_scale_factor()"));
  63         offset += hcb_sf[offset][b];
  64
  65         if (offset > 240)
  66         {
  67             /* printf("ERROR: offset into hcb_sf = %d >240!\n", offset); */
  68             return -1;
  69         }
  70     }
  71
  72     return hcb_sf[offset][0];
  73 }
  74
  75
  76 hcb *hcb_table[] = {
  77     0, hcb1_1, hcb2_1, 0, hcb4_1, 0, hcb6_1, 0, hcb8_1, 0, hcb10_1, hcb11_1
  78 };
  79
  80 hcb_2_quad *hcb_2_quad_table[] = {
  81     0, hcb1_2, hcb2_2, 0, hcb4_2, 0, 0, 0, 0, 0, 0, 0
  82 };
  83
  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
  86 };
  87
  88 hcb_bin_pair *hcb_bin_table[] = {
  89     0, 0, 0, 0, 0, hcb5, 0, hcb7, 0, hcb9, 0, 0
  90 };
  91
  92 uint8_t hcbN[] = { 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 6, 5 };
  93
  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
  98 };
  99
 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 };
 103
 104 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len)
 105 {
 106     uint8_t i;
 107
 108     for (i = 0; i < len; i++)
 109     {
 110         if(sp[i])
 111         {
 112             if(faad_get1bit(ld
 113                 DEBUGVAR(1,5,"huffman_sign_bits(): sign bit")) & 1)
 114             {
 115                 sp[i] = -sp[i];
 116             }
 117         }
 118     }
 119 }
 120
 121 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp)
 122 {
 123     uint8_t neg, i;
 124     int16_t j;
 125         int16_t off;
 126
 127     if (sp < 0)
 128     {
 129         if (sp != -16)
 130             return sp;
 131         neg = 1;
 132     } else {
 133         if (sp != 16)
 134             return sp;
 135         neg = 0;
 136     }
 137
 138     for (i = 4; ; i++)
 139     {
 140         if (faad_get1bit(ld
 141             DEBUGVAR(1,6,"huffman_getescape(): escape size")) == 0)
 142         {
 143             break;
 144         }
 145     }
 146
 147     off = (int16_t)faad_getbits(ld, i
 148         DEBUGVAR(1,9,"huffman_getescape(): escape"));
 149
 150     j = off | (1<<i);
 151     if (neg)
 152         j = -j;
 153
 154     return j;
 155 }
 156
 157 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp)
 158 {
 159     uint32_t cw;
 160     uint16_t offset = 0;
 161     uint8_t extra_bits;
 162
 163     cw = faad_showbits(ld, hcbN[cb]);
 164     offset = hcb_table[cb][cw].offset;
 165     extra_bits = hcb_table[cb][cw].extra_bits;
 166
 167     if (extra_bits)
 168     {
 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);
 175     }
 176
 177     if (offset > hcb_2_quad_table_size[cb])
 178     {
 179         /* printf("ERROR: offset into hcb_2_quad_table = %d >%d!\n", offset,
 180            hcb_2_quad_table_size[cb]); */
 181         return 10;
 182     }
 183
 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;
 188
 189     return 0;
 190 }
 191
 192 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 193 {
 194     uint8_t err = huffman_2step_quad(cb, ld, sp);
 195     huffman_sign_bits(ld, sp, QUAD_LEN);
 196
 197     return err;
 198 }
 199
 200 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp)
 201 {
 202     uint32_t cw;
 203     uint16_t offset = 0;
 204     uint8_t extra_bits;
 205
 206     cw = faad_showbits(ld, hcbN[cb]);
 207     offset = hcb_table[cb][cw].offset;
 208     extra_bits = hcb_table[cb][cw].extra_bits;
 209
 210     if (extra_bits)
 211     {
 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);
 218     }
 219
 220     if (offset > hcb_2_pair_table_size[cb])
 221     {
 222         /* printf("ERROR: offset into hcb_2_pair_table = %d >%d!\n", offset,
 223            hcb_2_pair_table_size[cb]); */
 224         return 10;
 225     }
 226
 227     sp[0] = hcb_2_pair_table[cb][offset].x;
 228     sp[1] = hcb_2_pair_table[cb][offset].y;
 229
 230     return 0;
 231 }
 232
 233 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 234 {
 235     uint8_t err = huffman_2step_pair(cb, ld, sp);
 236     huffman_sign_bits(ld, sp, PAIR_LEN);
 237
 238     return err;
 239 }
 240
 241 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp)
 242 {
 243     uint16_t offset = 0;
 244
 245     while (!hcb3[offset].is_leaf)
 246     {
 247         uint8_t b = faad_get1bit(ld
 248             DEBUGVAR(1,255,"huffman_spectral_data():3"));
 249         offset += hcb3[offset].data[b];
 250     }
 251
 252     if (offset > hcb_bin_table_size[cb])
 253     {
 254         /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
 255            hcb_bin_table_size[cb]); */
 256         return 10;
 257     }
 258
 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];
 263
 264     return 0;
 265 }
 266
 267 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 268 {
 269     uint8_t err = huffman_binary_quad(cb, ld, sp);
 270     huffman_sign_bits(ld, sp, QUAD_LEN);
 271
 272     return err;
 273 }
 274
 275 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp)
 276 {
 277     uint16_t offset = 0;
 278
 279     while (!hcb_bin_table[cb][offset].is_leaf)
 280     {
 281         uint8_t b = faad_get1bit(ld
 282             DEBUGVAR(1,255,"huffman_spectral_data():9"));
 283         offset += hcb_bin_table[cb][offset].data[b];
 284     }
 285
 286     if (offset > hcb_bin_table_size[cb])
 287     {
 288         /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
 289            hcb_bin_table_size[cb]); */
 290         return 10;
 291     }
 292
 293     sp[0] = hcb_bin_table[cb][offset].data[0];
 294     sp[1] = hcb_bin_table[cb][offset].data[1];
 295
 296     return 0;
 297 }
 298
 299 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 300 {
 301     uint8_t err = huffman_binary_pair(cb, ld, sp);
 302     huffman_sign_bits(ld, sp, PAIR_LEN);
 303
 304     return err;
 305 }
 306
 307 static int16_t huffman_codebook(uint8_t i)
 308 {
 309     static const uint32_t data = 16428320;
 310     if (i == 0) return (int16_t)(data >> 16) & 0xFFFF;
 311     else        return (int16_t)data & 0xFFFF;
 312 }
 313
 314 static void vcb11_check_LAV(uint8_t cb, int16_t *sp)
 315 {
 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
 319     };
 320     uint16_t max = 0;
 321
 322     if (cb < 16 || cb > 31)
 323         return;
 324
 325     max = vcb11_LAV_tab[cb - 16];
 326
 327     if ((abs(sp[0]) > max) || (abs(sp[1]) > max))
 328     {
 329         sp[0] = 0;
 330         sp[1] = 0;
 331     }
 332 }
 333
 334 uint8_t huffman_spectral_data(uint8_t cb, bitfile *ld, int16_t *sp)
 335 {
 336     switch (cb)
 337     {
 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:
 360     {
 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;
 365     }
 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:
 370     {
 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]);
 374
 375         /* check LAV (Largest Absolute Value) */
 376         /* this finds errors in the ESCAPE signal */
 377         vcb11_check_LAV(cb, sp);
 378
 379         return err;
 380     }
 381 #endif
 382     default:
 383         /* Non existent codebook number, something went wrong */
 384         return 11;
 385     }
 386
 387     return 0;
 388 }
 389
 390
 391 #ifdef ERROR_RESILIENCE
 392
 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 */
 397
 398 int8_t huffman_spectral_data_2(uint8_t cb, bits_t *ld, int16_t *sp)
 399 {
 400     uint32_t cw;
 401     uint16_t offset = 0;
 402     uint8_t extra_bits;
 403     uint8_t i, vcb11 = 0;
 404
 405
 406     switch (cb)
 407     {
 408     case 1: /* 2-step method for data quadruples */
 409     case 2:
 410     case 4:
 411
 412         cw = showbits_hcr(ld, hcbN[cb]);
 413         offset = hcb_table[cb][cw].offset;
 414         extra_bits = hcb_table[cb][cw].extra_bits;
 415
 416         if (extra_bits)
 417         {
 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;
 424         }
 425
 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;
 431
 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:
 439
 440         if (cb >= 16)
 441         {
 442             /* store the virtual codebook */
 443             vcb11 = cb;
 444             cb = 11;
 445         }
 446
 447         cw = showbits_hcr(ld, hcbN[cb]);
 448         offset = hcb_table[cb][cw].offset;
 449         extra_bits = hcb_table[cb][cw].extra_bits;
 450
 451         if (extra_bits)
 452         {
 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;
 459         }
 460         sp[0] = hcb_2_pair_table[cb][offset].x;
 461         sp[1] = hcb_2_pair_table[cb][offset].y;
 462         break;
 463
 464     case 3: /* binary search for data quadruples */
 465
 466         while (!hcb3[offset].is_leaf)
 467         {
 468             uint8_t b;
 469
 470             if ( get1bit_hcr(ld, &b) ) return -1;
 471             offset += hcb3[offset].data[b];
 472         }
 473
 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];
 478
 479         break;
 480
 481     case 5: /* binary search for data pairs */
 482     case 7:
 483     case 9:
 484
 485         while (!hcb_bin_table[cb][offset].is_leaf)
 486         {
 487             uint8_t b;
 488
 489             if (get1bit_hcr(ld, &b) ) return -1;
 490             offset += hcb_bin_table[cb][offset].data[b];
 491         }
 492
 493         sp[0] = hcb_bin_table[cb][offset].data[0];
 494         sp[1] = hcb_bin_table[cb][offset].data[1];
 495
 496         break;
 497     }
 498
 499         /* decode sign bits */
 500     if (unsigned_cb[cb])
 501     {
 502         for(i = 0; i < ((cb < FIRST_PAIR_HCB) ? QUAD_LEN : PAIR_LEN); i++)
 503         {
 504             if(sp[i])
 505             {
 506                 uint8_t b;
 507                 if ( get1bit_hcr(ld, &b) ) return -1;
 508                 if (b != 0) {
 509                     sp[i] = -sp[i];
 510                 }
 511            }
 512         }
 513     }
 514
 515     /* decode huffman escape bits */
 516     if ((cb == ESC_HCB) || (cb >= 16))
 517     {
 518         uint8_t k;
 519         for (k = 0; k < 2; k++)
 520         {
 521             if ((sp[k] == 16) || (sp[k] == -16))
 522             {
 523                 uint8_t neg, i;
 524                 int32_t j;
 525                 uint32_t off;
 526
 527                 neg = (sp[k] < 0) ? 1 : 0;
 528
 529                 for (i = 4; ; i++)
 530                 {
 531                     uint8_t b;
 532                     if (get1bit_hcr(ld, &b))
 533                         return -1;
 534                     if (b == 0)
 535                         break;
 536                 }
 537
 538                 if (getbits_hcr(ld, i, &off))
 539                     return -1;
 540                 j = off + (1<<i);
 541                 sp[k] = (int16_t)((neg) ? -j : j);
 542             }
 543         }
 544
 545         if (vcb11 != 0)
 546         {
 547             /* check LAV (Largest Absolute Value) */
 548             /* this finds errors in the ESCAPE signal */
 549             vcb11_check_LAV(vcb11, sp);
 550         }
 551     }
 552     return ld->len;
 553 }
 554
 555 #endif
 556