libfaad2/huffman.c

   1 /*
   2 ** FAAD2 - Freeware Advanced Audio (AAC) Decoder including SBR decoding
   3 ** Copyright (C) 2003 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.4 2003/09/09 18:12:00 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 int8_t huffman_scale_factor(bitfile *ld)
  42 {
  43     uint16_t offset = 0;
  44
  45     while (hcb_sf[offset][1])
  46     {
  47         uint8_t b = faad_get1bit(ld
  48             DEBUGVAR(1,255,"huffman_scale_factor()"));
  49         offset += hcb_sf[offset][b];
  50
  51         if (offset > 240)
  52         {
  53             /* printf("ERROR: offset into hcb_sf = %d >240!\n", offset); */
  54             return -1;
  55         }
  56     }
  57
  58     return hcb_sf[offset][0];
  59 }
  60
  61
  62 hcb *hcb_table[] = {
  63     0, hcb1_1, hcb2_1, 0, hcb4_1, 0, hcb6_1, 0, hcb8_1, 0, hcb10_1, hcb11_1
  64 };
  65
  66 hcb_2_quad *hcb_2_quad_table[] = {
  67     0, hcb1_2, hcb2_2, 0, hcb4_2, 0, 0, 0, 0, 0, 0, 0
  68 };
  69
  70 hcb_2_pair *hcb_2_pair_table[] = {
  71     0, 0, 0, 0, 0, 0, hcb6_2, 0, hcb8_2, 0, hcb10_2, hcb11_2
  72 };
  73
  74 hcb_bin_pair *hcb_bin_table[] = {
  75     0, 0, 0, 0, 0, hcb5, 0, hcb7, 0, hcb9, 0, 0
  76 };
  77
  78 uint8_t hcbN[] = { 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 6, 5 };
  79
  80 /* defines whether a huffman codebook is unsigned or not */
  81 /* Table 4.6.2 */
  82 uint8_t unsigned_cb[] = { 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
  83   /* codebook 16 to 31 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
  84 };
  85
  86 int hcb_2_quad_table_size[] = { 0, 114, 86, 0, 185, 0, 0, 0, 0, 0, 0, 0 };
  87 int hcb_2_pair_table_size[] = { 0, 0, 0, 0, 0, 0, 126, 0, 83, 0, 210, 373 };
  88 int hcb_bin_table_size[] = { 0, 0, 0, 161, 0, 161, 0, 127, 0, 337, 0, 0 };
  89
  90 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len)
  91 {
  92     uint8_t i;
  93
  94     for (i = 0; i < len; i++)
  95     {
  96         if(sp[i])
  97         {
  98             if(faad_get1bit(ld
  99                 DEBUGVAR(1,5,"huffman_sign_bits(): sign bit")) & 1)
 100             {
 101                 sp[i] = -sp[i];
 102             }
 103         }
 104     }
 105 }
 106
 107 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp)
 108 {
 109     uint8_t neg, i;
 110     int16_t j;
 111         int32_t off;
 112
 113     if (sp < 0)
 114     {
 115         if (sp != -16)
 116             return sp;
 117         neg = 1;
 118     } else {
 119         if(sp != 16)
 120             return sp;
 121         neg = 0;
 122     }
 123
 124     for (i = 4; ; i++)
 125     {
 126         if (faad_get1bit(ld
 127             DEBUGVAR(1,6,"huffman_getescape(): escape size")) == 0)
 128         {
 129             break;
 130         }
 131     }
 132
 133     off = faad_getbits(ld, i
 134         DEBUGVAR(1,9,"huffman_getescape(): escape"));
 135
 136     j = off + (1<<i);
 137     if (neg)
 138         j = -j;
 139
 140     return j;
 141 }
 142
 143 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp)
 144 {
 145     uint32_t cw;
 146     uint16_t offset = 0;
 147     uint8_t extra_bits;
 148
 149     cw = faad_showbits(ld, hcbN[cb]);
 150     offset = hcb_table[cb][cw].offset;
 151     extra_bits = hcb_table[cb][cw].extra_bits;
 152
 153     if (extra_bits)
 154     {
 155         /* we know for sure it's more than hcbN[cb] bits long */
 156         faad_flushbits(ld, hcbN[cb]);
 157         offset += (uint16_t)faad_showbits(ld, extra_bits);
 158         faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]);
 159     } else {
 160         faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits);
 161     }
 162
 163     if (offset > hcb_2_quad_table_size[cb])
 164     {
 165         /* printf("ERROR: offset into hcb_2_quad_table = %d >%d!\n", offset,
 166            hcb_2_quad_table_size[cb]); */
 167         return 10;
 168     }
 169
 170     sp[0] = hcb_2_quad_table[cb][offset].x;
 171     sp[1] = hcb_2_quad_table[cb][offset].y;
 172     sp[2] = hcb_2_quad_table[cb][offset].v;
 173     sp[3] = hcb_2_quad_table[cb][offset].w;
 174
 175     return 0;
 176 }
 177
 178 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 179 {
 180     uint8_t err = huffman_2step_quad(cb, ld, sp);
 181     huffman_sign_bits(ld, sp, QUAD_LEN);
 182
 183     return err;
 184 }
 185
 186 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp)
 187 {
 188     uint32_t cw;
 189     uint16_t offset = 0;
 190     uint8_t extra_bits;
 191
 192     cw = faad_showbits(ld, hcbN[cb]);
 193     offset = hcb_table[cb][cw].offset;
 194     extra_bits = hcb_table[cb][cw].extra_bits;
 195
 196     if (extra_bits)
 197     {
 198         /* we know for sure it's more than hcbN[cb] bits long */
 199         faad_flushbits(ld, hcbN[cb]);
 200         offset += (uint16_t)faad_showbits(ld, extra_bits);
 201         faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]);
 202     } else {
 203         faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits);
 204     }
 205
 206     if (offset > hcb_2_pair_table_size[cb])
 207     {
 208         /* printf("ERROR: offset into hcb_2_pair_table = %d >%d!\n", offset,
 209            hcb_2_pair_table_size[cb]); */
 210         return 10;
 211     }
 212
 213     sp[0] = hcb_2_pair_table[cb][offset].x;
 214     sp[1] = hcb_2_pair_table[cb][offset].y;
 215
 216     return 0;
 217 }
 218
 219 static huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 220 {
 221     uint8_t err = huffman_2step_pair(cb, ld, sp);
 222     huffman_sign_bits(ld, sp, PAIR_LEN);
 223
 224     return err;
 225 }
 226
 227 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp)
 228 {
 229     uint16_t offset = 0;
 230
 231     while (!hcb3[offset].is_leaf)
 232     {
 233         uint8_t b = faad_get1bit(ld
 234             DEBUGVAR(1,255,"huffman_spectral_data():3"));
 235         offset += hcb3[offset].data[b];
 236     }
 237
 238     if (offset > hcb_bin_table_size[cb])
 239     {
 240         /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
 241            hcb_bin_table_size[cb]); */
 242         return 10;
 243     }
 244
 245     sp[0] = hcb3[offset].data[0];
 246     sp[1] = hcb3[offset].data[1];
 247     sp[2] = hcb3[offset].data[2];
 248     sp[3] = hcb3[offset].data[3];
 249
 250     return 0;
 251 }
 252
 253 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 254 {
 255     uint8_t err = huffman_binary_quad(cb, ld, sp);
 256     huffman_sign_bits(ld, sp, QUAD_LEN);
 257
 258     return err;
 259 }
 260
 261 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp)
 262 {
 263     uint16_t offset = 0;
 264
 265     while (!hcb_bin_table[cb][offset].is_leaf)
 266     {
 267         uint8_t b = faad_get1bit(ld
 268             DEBUGVAR(1,255,"huffman_spectral_data():9"));
 269         offset += hcb_bin_table[cb][offset].data[b];
 270     }
 271
 272     if (offset > hcb_bin_table_size[cb])
 273     {
 274         /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
 275            hcb_bin_table_size[cb]); */
 276         return 10;
 277     }
 278
 279     sp[0] = hcb_bin_table[cb][offset].data[0];
 280     sp[1] = hcb_bin_table[cb][offset].data[1];
 281
 282     return 0;
 283 }
 284
 285 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
 286 {
 287     uint8_t err = huffman_binary_pair(cb, ld, sp);
 288     huffman_sign_bits(ld, sp, PAIR_LEN);
 289
 290     return err;
 291 }
 292
 293 static int16_t huffman_codebook(uint8_t i)
 294 {
 295     static const uint32_t data = 16428320;
 296     if (i == 0) return (int16_t)(data >> 16) & 0xFFFF;
 297     else        return (int16_t)data & 0xFFFF;
 298 }
 299
 300 uint8_t huffman_spectral_data(uint8_t cb, bitfile *ld, int16_t *sp)
 301 {
 302     switch (cb)
 303     {
 304     case 1: /* 2-step method for data quadruples */
 305     case 2:
 306         return huffman_2step_quad(cb, ld, sp);
 307     case 3: /* binary search for data quadruples */
 308         return huffman_binary_quad_sign(cb, ld, sp);
 309     case 4: /* 2-step method for data quadruples */
 310         return huffman_2step_quad_sign(cb, ld, sp);
 311     case 5: /* binary search for data pairs */
 312         return huffman_binary_pair(cb, ld, sp);
 313     case 6: /* 2-step method for data pairs */
 314         return huffman_2step_pair(cb, ld, sp);
 315     case 7: /* binary search for data pairs */
 316     case 9:
 317         return huffman_binary_pair_sign(cb, ld, sp);
 318     case 8: /* 2-step method for data pairs */
 319     case 10:
 320         return huffman_2step_pair_sign(cb, ld, sp);
 321     case 12: {
 322         uint8_t err = huffman_2step_quad(1, ld, sp);
 323         sp[0] = huffman_codebook(0); sp[1] = huffman_codebook(1);
 324         return err; }
 325     case 11:
 326 #ifdef ERROR_RESILIENCE
 327     /* VCB11 uses codebook 11 */
 328     case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
 329     case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
 330         /* TODO: If ER is used, some extra error checking should be done */
 331 #endif
 332     {
 333         uint8_t err = huffman_2step_pair_sign(11, ld, sp);
 334         sp[0] = huffman_getescape(ld, sp[0]);
 335         sp[1] = huffman_getescape(ld, sp[1]);
 336         return err;
 337     }
 338     default:
 339         /* Non existent codebook number, something went wrong */
 340         return 11;
 341     }
 342
 343     return 0;
 344 }
 345
 346
 347 #ifdef ERROR_RESILIENCE
 348
 349 /* Special version of huffman_spectral_data
 350 Will not read from a bitfile but a bits_t structure.
 351 Will keep track of the bits decoded and return the number of bits remaining.
 352 Do not read more than ld->len, return -1 if codeword would be longer */
 353
 354 int8_t huffman_spectral_data_2(uint8_t cb, bits_t *ld, int16_t *sp)
 355 {
 356     uint32_t cw;
 357     uint16_t offset = 0;
 358     uint8_t extra_bits;
 359     uint8_t i;
 360     uint8_t save_cb = cb;
 361
 362
 363     switch (cb)
 364     {
 365     case 1: /* 2-step method for data quadruples */
 366     case 2:
 367     case 4:
 368
 369         cw = showbits_hcr(ld, hcbN[cb]);
 370         offset = hcb_table[cb][cw].offset;
 371         extra_bits = hcb_table[cb][cw].extra_bits;
 372
 373         if (extra_bits)
 374         {
 375             /* we know for sure it's more than hcbN[cb] bits long */
 376             if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
 377             offset += (uint16_t)showbits_hcr(ld, extra_bits);
 378             if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]) ) return -1;
 379         } else {
 380             if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits) ) return -1;
 381         }
 382
 383         sp[0] = hcb_2_quad_table[cb][offset].x;
 384         sp[1] = hcb_2_quad_table[cb][offset].y;
 385         sp[2] = hcb_2_quad_table[cb][offset].v;
 386         sp[3] = hcb_2_quad_table[cb][offset].w;
 387         break;
 388
 389     case 6: /* 2-step method for data pairs */
 390     case 8:
 391     case 10:
 392     case 11:
 393     /* VCB11 uses codebook 11 */
 394     case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
 395     case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
 396
 397         /* TODO: If ER is used, some extra error checking should be done */
 398         if (cb >= 16)
 399             cb = 11;
 400
 401         cw = showbits_hcr(ld, hcbN[cb]);
 402         offset = hcb_table[cb][cw].offset;
 403         extra_bits = hcb_table[cb][cw].extra_bits;
 404
 405         if (extra_bits)
 406         {
 407             /* we know for sure it's more than hcbN[cb] bits long */
 408             if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
 409             offset += (uint16_t)showbits_hcr(ld, extra_bits);
 410             if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]) ) return -1;
 411         } else {
 412             if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits) ) return -1;
 413         }
 414         sp[0] = hcb_2_pair_table[cb][offset].x;
 415         sp[1] = hcb_2_pair_table[cb][offset].y;
 416         break;
 417
 418     case 3: /* binary search for data quadruples */
 419
 420         while (!hcb3[offset].is_leaf)
 421         {
 422             uint8_t b;
 423
 424             if ( get1bit_hcr(ld, &b) ) return -1;
 425             offset += hcb3[offset].data[b];
 426         }
 427
 428         sp[0] = hcb3[offset].data[0];
 429         sp[1] = hcb3[offset].data[1];
 430         sp[2] = hcb3[offset].data[2];
 431         sp[3] = hcb3[offset].data[3];
 432
 433         break;
 434
 435     case 5: /* binary search for data pairs */
 436     case 7:
 437     case 9:
 438
 439         while (!hcb_bin_table[cb][offset].is_leaf)
 440         {
 441             uint8_t b;
 442
 443             if (get1bit_hcr(ld, &b) ) return -1;
 444             offset += hcb_bin_table[cb][offset].data[b];
 445         }
 446
 447         sp[0] = hcb_bin_table[cb][offset].data[0];
 448         sp[1] = hcb_bin_table[cb][offset].data[1];
 449
 450         break;
 451     }
 452
 453         /* decode sign bits */
 454     if (unsigned_cb[cb]) {
 455
 456         for(i = 0; i < ((cb < FIRST_PAIR_HCB) ? QUAD_LEN : PAIR_LEN); i++)
 457         {
 458             if(sp[i])
 459             {
 460                 uint8_t b;
 461                 if ( get1bit_hcr(ld, &b) ) return -1;
 462                 if (b != 0) {
 463                     sp[i] = -sp[i];
 464                 }
 465            }
 466         }
 467     }
 468
 469     /* decode huffman escape bits */
 470     if ((cb == ESC_HCB) || (cb >= 16))
 471     {
 472         uint8_t k;
 473         for (k = 0; k < 2; k++)
 474         {
 475             if ((sp[k] == 16) || (sp[k] == -16))
 476             {
 477                 uint8_t neg, i;
 478                 int32_t j;
 479                 uint32_t off;
 480
 481                 neg = (sp[k] < 0) ? 1 : 0;
 482
 483                 for (i = 4; ; i++)
 484                 {
 485                     uint8_t b;
 486                     if (get1bit_hcr(ld, &b))
 487                         return -1;
 488                     if (b == 0)
 489                         break;
 490                 }
 491 // TODO: here we would need to test "off" if VCB11 is used!
 492                 if (getbits_hcr(ld, i, &off))
 493                     return -1;
 494                 j = off + (1<<i);
 495                 sp[k] = (int16_t)((neg) ? -j : j);
 496             }
 497         }
 498     }
 499     return ld->len;
 500 }
 501
 502 #endif
 503