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