src/lib/doslib/ext/faad/huffman.c

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