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