huff.c

Application (fix point) for playing MP3 data on embedded systems. mp3play is designed to be able to

   { 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
   255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
   255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
   { 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
   59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
   226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
   252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
};

static const UINT32 *tables[32] = {
   0,   h1,  h2,  h3,  0,   h5,  h6,  h7,  h8,  h9,  h10, h11, h12, h13, 0,   h15,
   h16, h16, h16, h16, h16, h16, h16, h16, h24, h24, h24, h24, h24, h24, h24, h24 };

static const INT16 t_linbits[32]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,6,8,10,13,4,5,6,7,8,9,11,13}; /* #4 Added const */

int HUFF_decode_pair( HUFFMAN *h, INT16 table, INT16 count, INT16 *x )
{
static const UINT32 mask[ 20 ] = { /* #4 Added const */
   0x00000000, 0x80000000, 0xC0000000, 0xE0000000,
   0xF0000000, 0xF8000000, 0xFC000000, 0xFE000000,
   0xFF000000, 0xFF800000, 0xFFC00000, 0xFFE00000,
   0xFFF00000, 0xFFF80000, 0xFFFC0000, 0xFFFE0000,
   0xFFFF0000, 0xFFFF8000, 0xFFFFC000, 0xFFFFE000
};

   const UINT32 *ht = tables[ table ];
   register const UINT32 *h_tab;
   UINT32 chunk;
   INT32 chunk_cache = 0;
   INT16 cache_size = 0;
   INT16 linbits = t_linbits[ table ];
   INT16 len, lag, dir_flag;
   int pos;
   INT16 tmp;
   const UINT8 *cue;

   if( !ht ) {
      while( count-- ) {
         x[ 0 ] = x[ 1 ] = 0;
         x += 2;
      }
      return 0;
   }

   cue = h_cue[ table ];

   while( count-- ) {

      if( cache_size < (NC_O+2) ) { // NC_O+1+1 (1+1 for signs of pair)
         chunk_cache |= HUFF_read_bits( h, 32-cache_size );
         cache_size = 32;
      }
      tmp = (UINT32)chunk_cache >> (32-NC_O);
      h_tab = ht + cue[ tmp ];
      len = (*h_tab >> 8) & 0x1F;

      if( ((*h_tab ^ chunk_cache) & mask[ len ]) || (len > NC_O) ) {
         if( cache_size < 21 ) { // 19+1+1 (1+1 for signs of pair)
            chunk_cache |= HUFF_read_bits( h, 32-cache_size );
            cache_size = 32;
         }

         lag = cue[ tmp+1 ] - cue[ tmp ];
         chunk = chunk_cache | 0x1FFF; // #3 Appended one 'F'
         dir_flag = 0;
         while( lag > 1 ) { // Dichotomic search
            if( !dir_flag ) h_tab += lag>>1;
            else h_tab -= lag>>1;
            if( *h_tab > chunk ) {
               if( !dir_flag ) lag >>= 1;
               else lag -= lag>>1;
               dir_flag = -1;
            } else {
               if( !dir_flag ) lag -= lag>>1;
               else lag >>= 1;
               dir_flag = 0;
            }
         }
         len = (*h_tab >> 8) & 0x1F;
         if( (*h_tab ^ chunk_cache) & mask[ len ] ) {
            if( !dir_flag ) h_tab++;
            else h_tab--;
            len = (*h_tab >> 8) & 0x1F;
         }
      }

      chunk_cache <<= len;
      cache_size -= len;

      x[ 0 ] = (*h_tab >> 4) & 0x0F;
      x[ 1 ] = *h_tab & 0x0F;

      if( !linbits ) {
         if( x[ 0 ] ) {
            if( chunk_cache < 0 ) x[ 0 ] = -x[ 0 ];
            chunk_cache <<= 1;
            cache_size--;
         }
         if( x[ 1 ] ) {
            if( chunk_cache < 0 ) x[ 1 ] = -x[ 1 ];
            chunk_cache <<= 1;
            cache_size--;
         }
      }
      else {
         if( x[ 0 ] == 15 ) {
            chunk_cache |= HUFF_read_bits( h, 32-cache_size );
            cache_size = 32 - linbits;
            x[ 0 ] += (UINT32)chunk_cache >> (cache_size);
            chunk_cache <<= linbits;
         }
         if( x[ 0 ] ) {
            if( chunk_cache < 0 ) x[ 0 ] = -x[ 0 ];
            chunk_cache <<= 1;
            cache_size--;
         }
         if( x[ 1 ] == 15 ) {
            chunk_cache |= HUFF_read_bits( h, 32-cache_size );
            cache_size = 32 - linbits;
            x[ 1 ] += (UINT32)chunk_cache >> (cache_size);
            chunk_cache <<= linbits;
         }
         if( x[ 1 ] ) {
            if( chunk_cache < 0 ) x[ 1 ] = -x[ 1 ];
            chunk_cache <<= 1;
            cache_size--;
         }
      }
      x += 2;
   }

   pos = HUFF_pos( h );
   pos -= cache_size;
   HUFF_seek( h, pos );

   return 0;

} /* HUFF_decode_pair */

int HUFF_decode_quad( HUFFMAN *h, INT16 table, INT16 max_bits,
                      INT16 val_count, INT16 val_top, INT16 *isp )
{
   static const UINT8 huff_quad_tab1[ 64 ] = { // [<hlen:4><vwxy>],...
      0x6B, 0x6F, 0x6D, 0x6E, 0x67, 0x65,
      0x59, 0x59, 0x56, 0x56, 0x53, 0x53, 0x5A, 0x5A, 0x5C, 0x5C,
      0x42, 0x42, 0x42, 0x42, 0x41, 0x41, 0x41, 0x41,
      0x44, 0x44, 0x44, 0x44, 0x48, 0x48, 0x48, 0x48,
      0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10,
      0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10,
      0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10,
      0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10
   };
   register UINT8 q;
   register UINT32 bit_cache = 0;
   register INT16 bit_cache_size = 0;
   register INT16 len;
   register INT16 *x;

   x = isp;
   while( (max_bits > 0) && (val_count < val_top) ) {
      if( bit_cache_size < 10 ) {
         bit_cache |= HUFF_read_bits( h, 32-bit_cache_size );
         bit_cache_size = 32;
      }
      max_bits -= bit_cache_size;
      if( table ) {
         q = bit_cache >> (32-4);
         bit_cache <<= 4;
         bit_cache_size -= 4;
         q ^= 0xF;
      }
      else {
         q = huff_quad_tab1[ (INT16)(bit_cache >> (32-6)) ];
         len = q >> 4;
         q &= 0xF;
         bit_cache <<= len;
         bit_cache_size -= len;
      }
      if( q ) {
         x[ 0 ] = (q>>3) & 1;
         x[ 1 ] = (q>>2) & 1;
         x[ 2 ] = (q>>1) & 1;
         x[ 3 ] = q & 1;

         q = 4;
         while( q-- ) {
            if( *x ) {
               if( bit_cache & 0x80000000 ) *x = -*x;
               bit_cache <<= 1;
               bit_cache_size--;
            }
            x++;
         }
      }
      else {
         *x++ = 0;
         *x++ = 0;
         *x++ = 0;
         *x++ = 0;
      }
      val_count += 4,
      max_bits += bit_cache_size;
   }

   // Zero rest of band
   len = h->nul_begin - val_count;
   while( (len--) > 0 ) *x++ = 0;
   h->nul_begin = val_count; // Update zero begin

   return 0;

} /* HUFF_decode_quad */