- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# huffman.c

    00001 /*
    00002 ** FAAD2 - Freeware Advanced Audio (AAC) Decoder including SBR decoding
    00003 ** Copyright (C) 2003-2005 M. Bakker, Ahead Software AG, http://www.nero.com
    00004 **
    00005 ** This program is free software; you can redistribute it and/or modify
    00006 ** it under the terms of the GNU General Public License as published by
    00007 ** the Free Software Foundation; either version 2 of the License, or
    00008 ** (at your option) any later version.
    00009 **
    00010 ** This program is distributed in the hope that it will be useful,
    00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
    00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00013 ** GNU General Public License for more details.
    00014 **
    00015 ** You should have received a copy of the GNU General Public License
    00016 ** along with this program; if not, write to the Free Software
    00017 ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
    00018 **
    00019 ** Any non-GPL usage of this software or parts of this software is strictly
    00020 ** forbidden.
    00021 **
    00022 ** Software using this code must display the following message visibly in the
    00023 ** software:
    00024 ** "FAAD2 AAC/HE-AAC/HE-AACv2/DRM decoder (c) Ahead Software, www.nero.com"
    00025 ** in, for example, the about-box or help/startup screen.
    00026 **
    00027 ** Commercial non-GPL licensing of this software is possible.
    00028 ** For more info contact Ahead Software through Mpeg4AAClicense@nero.com.
    00029 **
    00030 ** $Id: huffman.c,v 1.2 2005/11/01 21:41:43 gabest Exp $
    00031 **/
    00032
    00033 #include "common.h"
    00034 #include "structs.h"
    00035
    00036 #include <stdlib.h>
    00037 #ifdef ANALYSIS
    00038 #include <stdio.h>
    00039 #endif
    00040
    00041 #include "bits.h"
    00042 #include "huffman.h"
    00043 #include "codebook/hcb.h"
    00044
    00045
    00046 /* static function declarations */
    00047 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len);
    00048 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp);
    00049 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp);
    00050 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp);
    00051 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp);
    00052 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp);
    00053 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp);
    00054 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp);
    00055 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp);
    00056 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp);
    00057 static int16_t huffman_codebook(uint8_t i);
    00058 static void vcb11_check_LAV(uint8_t cb, int16_t *sp);
    00059
    00060 int8_t huffman_scale_factor(bitfile *ld)
    00061 {
    00062     uint16_t offset = 0;
    00063
    00064     while (hcb_sf[offset][1])
    00065     {
    00066         uint8_t b = faad_get1bit(ld
    00067             DEBUGVAR(1,255,"huffman_scale_factor()"));
    00068         offset += hcb_sf[offset][b];
    00069
    00070         if (offset > 240)
    00071         {
    00072             /* printf("ERROR: offset into hcb_sf = %d >240!\n", offset); */
    00073             return -1;
    00074         }
    00075     }
    00076
    00077     return hcb_sf[offset][0];
    00078 }
    00079
    00080
    00081 hcb *hcb_table[] = {
    00082     0, hcb1_1, hcb2_1, 0, hcb4_1, 0, hcb6_1, 0, hcb8_1, 0, hcb10_1, hcb11_1
    00083 };
    00084
    00085 hcb_2_quad *hcb_2_quad_table[] = {
    00086     0, hcb1_2, hcb2_2, 0, hcb4_2, 0, 0, 0, 0, 0, 0, 0
    00087 };
    00088
    00089 hcb_2_pair *hcb_2_pair_table[] = {
    00090     0, 0, 0, 0, 0, 0, hcb6_2, 0, hcb8_2, 0, hcb10_2, hcb11_2
    00091 };
    00092
    00093 hcb_bin_pair *hcb_bin_table[] = {
    00094     0, 0, 0, 0, 0, hcb5, 0, hcb7, 0, hcb9, 0, 0
    00095 };
    00096
    00097 uint8_t hcbN[] = { 0, 5, 5, 0, 5, 0, 5, 0, 5, 0, 6, 5 };
    00098
    00099 /* defines whether a huffman codebook is unsigned or not */
    00100 /* Table 4.6.2 */
    00101 uint8_t unsigned_cb[] = { 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
    00102   /* codebook 16 to 31 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
    00103 };
    00104
    00105 int hcb_2_quad_table_size[] = { 0, 114, 86, 0, 185, 0, 0, 0, 0, 0, 0, 0 };
    00106 int hcb_2_pair_table_size[] = { 0, 0, 0, 0, 0, 0, 126, 0, 83, 0, 210, 373 };
    00107 int hcb_bin_table_size[] = { 0, 0, 0, 161, 0, 161, 0, 127, 0, 337, 0, 0 };
    00108
    00109 static INLINE void huffman_sign_bits(bitfile *ld, int16_t *sp, uint8_t len)
    00110 {
    00111     uint8_t i;
    00112
    00113     for (i = 0; i < len; i++)
    00114     {
    00115         if(sp[i])
    00116         {
    00117             if(faad_get1bit(ld
    00118                 DEBUGVAR(1,5,"huffman_sign_bits(): sign bit")) & 1)
    00119             {
    00120                 sp[i] = -sp[i];
    00121             }
    00122         }
    00123     }
    00124 }
    00125
    00126 static INLINE int16_t huffman_getescape(bitfile *ld, int16_t sp)
    00127 {
    00128     uint8_t neg, i;
    00129     int16_t j;
    00130         int16_t off;
    00131
    00132     if (sp < 0)
    00133     {
    00134         if (sp != -16)
    00135             return sp;
    00136         neg = 1;
    00137     } else {
    00138         if (sp != 16)
    00139             return sp;
    00140         neg = 0;
    00141     }
    00142
    00143     for (i = 4; ; i++)
    00144     {
    00145         if (faad_get1bit(ld
    00146             DEBUGVAR(1,6,"huffman_getescape(): escape size")) == 0)
    00147         {
    00148             break;
    00149         }
    00150     }
    00151
    00152     off = (int16_t)faad_getbits(ld, i
    00153         DEBUGVAR(1,9,"huffman_getescape(): escape"));
    00154
    00155     j = off | (1<<i);
    00156     if (neg)
    00157         j = -j;
    00158
    00159     return j;
    00160 }
    00161
    00162 static uint8_t huffman_2step_quad(uint8_t cb, bitfile *ld, int16_t *sp)
    00163 {
    00164     uint32_t cw;
    00165     uint16_t offset = 0;
    00166     uint8_t extra_bits;
    00167
    00168     cw = faad_showbits(ld, hcbN[cb]);
    00169     offset = hcb_table[cb][cw].offset;
    00170     extra_bits = hcb_table[cb][cw].extra_bits;
    00171
    00172     if (extra_bits)
    00173     {
    00174         /* we know for sure it's more than hcbN[cb] bits long */
    00175         faad_flushbits(ld, hcbN[cb]);
    00176         offset += (uint16_t)faad_showbits(ld, extra_bits);
    00177         faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]);
    00178     } else {
    00179         faad_flushbits(ld, hcb_2_quad_table[cb][offset].bits);
    00180     }
    00181
    00182     if (offset > hcb_2_quad_table_size[cb])
    00183     {
    00184         /* printf("ERROR: offset into hcb_2_quad_table = %d >%d!\n", offset,
    00185            hcb_2_quad_table_size[cb]); */
    00186         return 10;
    00187     }
    00188
    00189     sp[0] = hcb_2_quad_table[cb][offset].x;
    00190     sp[1] = hcb_2_quad_table[cb][offset].y;
    00191     sp[2] = hcb_2_quad_table[cb][offset].v;
    00192     sp[3] = hcb_2_quad_table[cb][offset].w;
    00193
    00194     return 0;
    00195 }
    00196
    00197 static uint8_t huffman_2step_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
    00198 {
    00199     uint8_t err = huffman_2step_quad(cb, ld, sp);
    00200     huffman_sign_bits(ld, sp, QUAD_LEN);
    00201
    00202     return err;
    00203 }
    00204
    00205 static uint8_t huffman_2step_pair(uint8_t cb, bitfile *ld, int16_t *sp)
    00206 {
    00207     uint32_t cw;
    00208     uint16_t offset = 0;
    00209     uint8_t extra_bits;
    00210
    00211     cw = faad_showbits(ld, hcbN[cb]);
    00212     offset = hcb_table[cb][cw].offset;
    00213     extra_bits = hcb_table[cb][cw].extra_bits;
    00214
    00215     if (extra_bits)
    00216     {
    00217         /* we know for sure it's more than hcbN[cb] bits long */
    00218         faad_flushbits(ld, hcbN[cb]);
    00219         offset += (uint16_t)faad_showbits(ld, extra_bits);
    00220         faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]);
    00221     } else {
    00222         faad_flushbits(ld, hcb_2_pair_table[cb][offset].bits);
    00223     }
    00224
    00225     if (offset > hcb_2_pair_table_size[cb])
    00226     {
    00227         /* printf("ERROR: offset into hcb_2_pair_table = %d >%d!\n", offset,
    00228            hcb_2_pair_table_size[cb]); */
    00229         return 10;
    00230     }
    00231
    00232     sp[0] = hcb_2_pair_table[cb][offset].x;
    00233     sp[1] = hcb_2_pair_table[cb][offset].y;
    00234
    00235     return 0;
    00236 }
    00237
    00238 static uint8_t huffman_2step_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
    00239 {
    00240     uint8_t err = huffman_2step_pair(cb, ld, sp);
    00241     huffman_sign_bits(ld, sp, PAIR_LEN);
    00242
    00243     return err;
    00244 }
    00245
    00246 static uint8_t huffman_binary_quad(uint8_t cb, bitfile *ld, int16_t *sp)
    00247 {
    00248     uint16_t offset = 0;
    00249
    00250     while (!hcb3[offset].is_leaf)
    00251     {
    00252         uint8_t b = faad_get1bit(ld
    00253             DEBUGVAR(1,255,"huffman_spectral_data():3"));
    00254         offset += hcb3[offset].data[b];
    00255     }
    00256
    00257     if (offset > hcb_bin_table_size[cb])
    00258     {
    00259         /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
    00260            hcb_bin_table_size[cb]); */
    00261         return 10;
    00262     }
    00263
    00264     sp[0] = hcb3[offset].data[0];
    00265     sp[1] = hcb3[offset].data[1];
    00266     sp[2] = hcb3[offset].data[2];
    00267     sp[3] = hcb3[offset].data[3];
    00268
    00269     return 0;
    00270 }
    00271
    00272 static uint8_t huffman_binary_quad_sign(uint8_t cb, bitfile *ld, int16_t *sp)
    00273 {
    00274     uint8_t err = huffman_binary_quad(cb, ld, sp);
    00275     huffman_sign_bits(ld, sp, QUAD_LEN);
    00276
    00277     return err;
    00278 }
    00279
    00280 static uint8_t huffman_binary_pair(uint8_t cb, bitfile *ld, int16_t *sp)
    00281 {
    00282     uint16_t offset = 0;
    00283
    00284     while (!hcb_bin_table[cb][offset].is_leaf)
    00285     {
    00286         uint8_t b = faad_get1bit(ld
    00287             DEBUGVAR(1,255,"huffman_spectral_data():9"));
    00288         offset += hcb_bin_table[cb][offset].data[b];
    00289     }
    00290
    00291     if (offset > hcb_bin_table_size[cb])
    00292     {
    00293         /* printf("ERROR: offset into hcb_bin_table = %d >%d!\n", offset,
    00294            hcb_bin_table_size[cb]); */
    00295         return 10;
    00296     }
    00297
    00298     sp[0] = hcb_bin_table[cb][offset].data[0];
    00299     sp[1] = hcb_bin_table[cb][offset].data[1];
    00300
    00301     return 0;
    00302 }
    00303
    00304 static uint8_t huffman_binary_pair_sign(uint8_t cb, bitfile *ld, int16_t *sp)
    00305 {
    00306     uint8_t err = huffman_binary_pair(cb, ld, sp);
    00307     huffman_sign_bits(ld, sp, PAIR_LEN);
    00308
    00309     return err;
    00310 }
    00311
    00312 static int16_t huffman_codebook(uint8_t i)
    00313 {
    00314     static const uint32_t data = 16428320;
    00315     if (i == 0) return (int16_t)(data >> 16) & 0xFFFF;
    00316     else        return (int16_t)data & 0xFFFF;
    00317 }
    00318
    00319 static void vcb11_check_LAV(uint8_t cb, int16_t *sp)
    00320 {
    00321     static const uint16_t vcb11_LAV_tab[] = {
    00322         16, 31, 47, 63, 95, 127, 159, 191, 223,
    00323         255, 319, 383, 511, 767, 1023, 2047
    00324     };
    00325     uint16_t max = 0;
    00326
    00327     if (cb < 16 || cb > 31)
    00328         return;
    00329
    00330     max = vcb11_LAV_tab[cb - 16];
    00331
    00332     if ((abs(sp[0]) > max) || (abs(sp[1]) > max))
    00333     {
    00334         sp[0] = 0;
    00335         sp[1] = 0;
    00336     }
    00337 }
    00338
    00339 uint8_t huffman_spectral_data(uint8_t cb, bitfile *ld, int16_t *sp)
    00340 {
    00341     switch (cb)
    00342     {
    00343     case 1: /* 2-step method for data quadruples */
    00344     case 2:
    00345         return huffman_2step_quad(cb, ld, sp);
    00346     case 3: /* binary search for data quadruples */
    00347         return huffman_binary_quad_sign(cb, ld, sp);
    00348     case 4: /* 2-step method for data quadruples */
    00349         return huffman_2step_quad_sign(cb, ld, sp);
    00350     case 5: /* binary search for data pairs */
    00351         return huffman_binary_pair(cb, ld, sp);
    00352     case 6: /* 2-step method for data pairs */
    00353         return huffman_2step_pair(cb, ld, sp);
    00354     case 7: /* binary search for data pairs */
    00355     case 9:
    00356         return huffman_binary_pair_sign(cb, ld, sp);
    00357     case 8: /* 2-step method for data pairs */
    00358     case 10:
    00359         return huffman_2step_pair_sign(cb, ld, sp);
    00360     case 12: {
    00361         uint8_t err = huffman_2step_pair(11, ld, sp);
    00362         sp[0] = huffman_codebook(0); sp[1] = huffman_codebook(1);
    00363         return err; }
    00364     case 11:
    00365     {
    00366         uint8_t err = huffman_2step_pair_sign(11, ld, sp);
    00367         sp[0] = huffman_getescape(ld, sp[0]);
    00368         sp[1] = huffman_getescape(ld, sp[1]);
    00369         return err;
    00370     }
    00371 #ifdef ERROR_RESILIENCE
    00372     /* VCB11 uses codebook 11 */
    00373     case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
    00374     case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
    00375     {
    00376         uint8_t err = huffman_2step_pair_sign(11, ld, sp);
    00377         sp[0] = huffman_getescape(ld, sp[0]);
    00378         sp[1] = huffman_getescape(ld, sp[1]);
    00379
    00380         /* check LAV (Largest Absolute Value) */
    00381         /* this finds errors in the ESCAPE signal */
    00382         vcb11_check_LAV(cb, sp);
    00383
    00384         return err;
    00385     }
    00386 #endif
    00387     default:
    00388         /* Non existent codebook number, something went wrong */
    00389         return 11;
    00390     }
    00391
    00392     return 0;
    00393 }
    00394
    00395
    00396 #ifdef ERROR_RESILIENCE
    00397
    00398 /* Special version of huffman_spectral_data
    00399 Will not read from a bitfile but a bits_t structure.
    00400 Will keep track of the bits decoded and return the number of bits remaining.
    00401 Do not read more than ld->len, return -1 if codeword would be longer */
    00402
    00403 int8_t huffman_spectral_data_2(uint8_t cb, bits_t *ld, int16_t *sp)
    00404 {
    00405     uint32_t cw;
    00406     uint16_t offset = 0;
    00407     uint8_t extra_bits;
    00408     uint8_t i, vcb11 = 0;
    00409
    00410
    00411     switch (cb)
    00412     {
    00413     case 1: /* 2-step method for data quadruples */
    00414     case 2:
    00415     case 4:
    00416
    00417         cw = showbits_hcr(ld, hcbN[cb]);
    00418         offset = hcb_table[cb][cw].offset;
    00419         extra_bits = hcb_table[cb][cw].extra_bits;
    00420
    00421         if (extra_bits)
    00422         {
    00423             /* we know for sure it's more than hcbN[cb] bits long */
    00424             if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
    00425             offset += (uint16_t)showbits_hcr(ld, extra_bits);
    00426             if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits - hcbN[cb]) ) return -1;
    00427         } else {
    00428             if ( flushbits_hcr(ld, hcb_2_quad_table[cb][offset].bits) ) return -1;
    00429         }
    00430
    00431         sp[0] = hcb_2_quad_table[cb][offset].x;
    00432         sp[1] = hcb_2_quad_table[cb][offset].y;
    00433         sp[2] = hcb_2_quad_table[cb][offset].v;
    00434         sp[3] = hcb_2_quad_table[cb][offset].w;
    00435         break;
    00436
    00437     case 6: /* 2-step method for data pairs */
    00438     case 8:
    00439     case 10:
    00440     case 11:
    00441     /* VCB11 uses codebook 11 */
    00442     case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
    00443     case 24: case 25: case 26: case 27: case 28: case 29: case 30: case 31:
    00444
    00445         if (cb >= 16)
    00446         {
    00447             /* store the virtual codebook */
    00448             vcb11 = cb;
    00449             cb = 11;
    00450         }
    00451
    00452         cw = showbits_hcr(ld, hcbN[cb]);
    00453         offset = hcb_table[cb][cw].offset;
    00454         extra_bits = hcb_table[cb][cw].extra_bits;
    00455
    00456         if (extra_bits)
    00457         {
    00458             /* we know for sure it's more than hcbN[cb] bits long */
    00459             if ( flushbits_hcr(ld, hcbN[cb]) ) return -1;
    00460             offset += (uint16_t)showbits_hcr(ld, extra_bits);
    00461             if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits - hcbN[cb]) ) return -1;
    00462         } else {
    00463             if ( flushbits_hcr(ld, hcb_2_pair_table[cb][offset].bits) ) return -1;
    00464         }
    00465         sp[0] = hcb_2_pair_table[cb][offset].x;
    00466         sp[1] = hcb_2_pair_table[cb][offset].y;
    00467         break;
    00468
    00469     case 3: /* binary search for data quadruples */
    00470
    00471         while (!hcb3[offset].is_leaf)
    00472         {
    00473             uint8_t b;
    00474
    00475             if ( get1bit_hcr(ld, &b) ) return -1;
    00476             offset += hcb3[offset].data[b];
    00477         }
    00478
    00479         sp[0] = hcb3[offset].data[0];
    00480         sp[1] = hcb3[offset].data[1];
    00481         sp[2] = hcb3[offset].data[2];
    00482         sp[3] = hcb3[offset].data[3];
    00483
    00484         break;
    00485
    00486     case 5: /* binary search for data pairs */
    00487     case 7:
    00488     case 9:
    00489
    00490         while (!hcb_bin_table[cb][offset].is_leaf)
    00491         {
    00492             uint8_t b;
    00493
    00494             if (get1bit_hcr(ld, &b) ) return -1;
    00495             offset += hcb_bin_table[cb][offset].data[b];
    00496         }
    00497
    00498         sp[0] = hcb_bin_table[cb][offset].data[0];
    00499         sp[1] = hcb_bin_table[cb][offset].data[1];
    00500
    00501         break;
    00502     }
    00503
    00504         /* decode sign bits */
    00505     if (unsigned_cb[cb])
    00506     {
    00507         for(i = 0; i < ((cb < FIRST_PAIR_HCB) ? QUAD_LEN : PAIR_LEN); i++)
    00508         {
    00509             if(sp[i])
    00510             {
    00511                 uint8_t b;
    00512                 if ( get1bit_hcr(ld, &b) ) return -1;
    00513                 if (b != 0) {
    00514                     sp[i] = -sp[i];
    00515                 }
    00516            }
    00517         }
    00518     }
    00519
    00520     /* decode huffman escape bits */
    00521     if ((cb == ESC_HCB) || (cb >= 16))
    00522     {
    00523         uint8_t k;
    00524         for (k = 0; k < 2; k++)
    00525         {
    00526             if ((sp[k] == 16) || (sp[k] == -16))
    00527             {
    00528                 uint8_t neg, i;
    00529                 int32_t j;
    00530                 uint32_t off;
    00531
    00532                 neg = (sp[k] < 0) ? 1 : 0;
    00533
    00534                 for (i = 4; ; i++)
    00535                 {
    00536                     uint8_t b;
    00537                     if (get1bit_hcr(ld, &b))
    00538                         return -1;
    00539                     if (b == 0)
    00540                         break;
    00541                 }
    00542
    00543                 if (getbits_hcr(ld, i, &off))
    00544                     return -1;
    00545                 j = off + (1<<i);
    00546                 sp[k] = (int16_t)((neg) ? -j : j);
    00547             }
    00548         }
    00549
    00550         if (vcb11 != 0)
    00551         {
    00552             /* check LAV (Largest Absolute Value) */
    00553             /* this finds errors in the ESCAPE signal */
    00554             vcb11_check_LAV(vcb11, sp);
    00555         }
    00556     }
    00557     return ld->len;
    00558 }
    00559
    00560 #endif
    00561