/* * libmad - MPEG audio decoder library * Copyright (C) 2000-2003 Underbit Technologies, Inc. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA * * $Id: huffman.c,v 1.8 2003/05/27 22:40:36 rob Exp $ */# ifdef HAVE_CONFIG_H#  include "config.h"# endif# include "global.h"# include "huffman.h"/* * These are the Huffman code words for Layer III. * The data for these tables are derived from Table B.7 of ISO/IEC 11172-3. * * These tables support decoding up to 4 Huffman code bits at a time. */# if defined(__GNUC__)#  define PTR(offs, bits)	{ ptr:   { 0, bits, offs       } }#  define V(v, w, x, y, hlen)	{ value: { 1, hlen, v, w, x, y } }# else#  define PTR(offs, bits)	{ { 0, bits, offs } }#  define V(v, w, x, y, hlen)	{ { 1, hlen, (v << 0) | (w << 1) |  \                                             (x << 2) | (y << 3) } }# endifstaticunion huffquad const hufftabA[] = {  /* 0000 */ PTR(16, 2),  /* 0001 */ PTR(20, 2),  /* 0010 */ PTR(24, 1),  /* 0011 */ PTR(26, 1),  /* 0100 */ V(0, 0, 1, 0, 4),  /* 0101 */ V(0, 0, 0, 1, 4),  /* 0110 */ V(0, 1, 0, 0, 4),  /* 0111 */ V(1, 0, 0, 0, 4),  /* 1000 */ V(0, 0, 0, 0, 1),  /* 1001 */ V(0, 0, 0, 0, 1),  /* 1010 */ V(0, 0, 0, 0, 1),  /* 1011 */ V(0, 0, 0, 0, 1),  /* 1100 */ V(0, 0, 0, 0, 1),  /* 1101 */ V(0, 0, 0, 0, 1),  /* 1110 */ V(0, 0, 0, 0, 1),  /* 1111 */ V(0, 0, 0, 0, 1),  /* 0000 ... */  /* 00   */ V(1, 0, 1, 1, 2),	/* 16 */  /* 01   */ V(1, 1, 1, 1, 2),  /* 10   */ V(1, 1, 0, 1, 2),  /* 11   */ V(1, 1, 1, 0, 2),  /* 0001 ... */  /* 00   */ V(0, 1, 1, 1, 2),	/* 20 */  /* 01   */ V(0, 1, 0, 1, 2),  /* 10   */ V(1, 0, 0, 1, 1),  /* 11   */ V(1, 0, 0, 1, 1),  /* 0010 ... */  /* 0    */ V(0, 1, 1, 0, 1),	/* 24 */  /* 1    */ V(0, 0, 1, 1, 1),  /* 0011 ... */  /* 0    */ V(1, 0, 1, 0, 1),	/* 26 */  /* 1    */ V(1, 1, 0, 0, 1)};staticunion huffquad const hufftabB[] = {  /* 0000 */ V(1, 1, 1, 1, 4),  /* 0001 */ V(1, 1, 1, 0, 4),  /* 0010 */ V(1, 1, 0, 1, 4),  /* 0011 */ V(1, 1, 0, 0, 4),  /* 0100 */ V(1, 0, 1, 1, 4),  /* 0101 */ V(1, 0, 1, 0, 4),  /* 0110 */ V(1, 0, 0, 1, 4),  /* 0111 */ V(1, 0, 0, 0, 4),  /* 1000 */ V(0, 1, 1, 1, 4),  /* 1001 */ V(0, 1, 1, 0, 4),  /* 1010 */ V(0, 1, 0, 1, 4),  /* 1011 */ V(0, 1, 0, 0, 4),  /* 1100 */ V(0, 0, 1, 1, 4),  /* 1101 */ V(0, 0, 1, 0, 4),  /* 1110 */ V(0, 0, 0, 1, 4),  /* 1111 */ V(0, 0, 0, 0, 4)};# undef V# undef PTR# if defined(__GNUC__)#  define PTR(offs, bits)	{ ptr:   { 0, bits, offs } }#  define V(x, y, hlen)		{ value: { 1, hlen, x, y } }# else#  define PTR(offs, bits)	{ { 0, bits, offs } }#  define V(x, y, hlen)		{ { 1, hlen, (x << 0) | (y << 4) } }# endifstaticunion huffpair const hufftab0[] = {  /*      */ V(0, 0, 0)};staticunion huffpair const hufftab1[] = {  /* 000  */ V(1, 1, 3),  /* 001  */ V(0, 1, 3),  /* 010  */ V(1, 0, 2),  /* 011  */ V(1, 0, 2),  /* 100  */ V(0, 0, 1),  /* 101  */ V(0, 0, 1),  /* 110  */ V(0, 0, 1),  /* 111  */ V(0, 0, 1)};staticunion huffpair const hufftab2[] = {  /* 000  */ PTR(8, 3),  /* 001  */ V(1, 1, 3),  /* 010  */ V(0, 1, 3),  /* 011  */ V(1, 0, 3),  /* 100  */ V(0, 0, 1),  /* 101  */ V(0, 0, 1),  /* 110  */ V(0, 0, 1),  /* 111  */ V(0, 0, 1),  /* 000 ... */  /* 000  */ V(2, 2, 3),	/* 8 */  /* 001  */ V(0, 2, 3),  /* 010  */ V(1, 2, 2),  /* 011  */ V(1, 2, 2),  /* 100  */ V(2, 1, 2),  /* 101  */ V(2, 1, 2),  /* 110  */ V(2, 0, 2),  /* 111  */ V(2, 0, 2)};staticunion huffpair const hufftab3[] = {  /* 000  */ PTR(8, 3),  /* 001  */ V(1, 0, 3),  /* 010  */ V(1, 1, 2),  /* 011  */ V(1, 1, 2),  /* 100  */ V(0, 1, 2),  /* 101  */ V(0, 1, 2),  /* 110  */ V(0, 0, 2),  /* 111  */ V(0, 0, 2),  /* 000 ... */  /* 000  */ V(2, 2, 3),	/* 8 */  /* 001  */ V(0, 2, 3),  /* 010  */ V(1, 2, 2),  /* 011  */ V(1, 2, 2),  /* 100  */ V(2, 1, 2),  /* 101  */ V(2, 1, 2),  /* 110  */ V(2, 0, 2),  /* 111  */ V(2, 0, 2)};staticunion huffpair const hufftab5[] = {  /* 000  */ PTR(8, 4),  /* 001  */ V(1, 1, 3),  /* 010  */ V(0, 1, 3),  /* 011  */ V(1, 0, 3),  /* 100  */ V(0, 0, 1),  /* 101  */ V(0, 0, 1),  /* 110  */ V(0, 0, 1),  /* 111  */ V(0, 0, 1),  /* 000 ... */  /* 0000 */ PTR(24, 1),	/* 8 */  /* 0001 */ V(3, 2, 4),  /* 0010 */ V(3, 1, 3),  /* 0011 */ V(3, 1, 3),  /* 0100 */ V(1, 3, 4),  /* 0101 */ V(0, 3, 4),  /* 0110 */ V(3, 0, 4),  /* 0111 */ V(2, 2, 4),  /* 1000 */ V(1, 2, 3),  /* 1001 */ V(1, 2, 3),  /* 1010 */ V(2, 1, 3),  /* 1011 */ V(2, 1, 3),  /* 1100 */ V(0, 2, 3),  /* 1101 */ V(0, 2, 3),  /* 1110 */ V(2, 0, 3),  /* 1111 */ V(2, 0, 3),  /* 000 0000 ... */  /* 0    */ V(3, 3, 1),	/* 24 */  /* 1    */ V(2, 3, 1)};staticunion huffpair const hufftab6[] = {  /* 0000 */ PTR(16, 3),  /* 0001 */ PTR(24, 1),  /* 0010 */ PTR(26, 1),  /* 0011 */ V(1, 2, 4),  /* 0100 */ V(2, 1, 4),  /* 0101 */ V(2, 0, 4),  /* 0110 */ V(0, 1, 3),  /* 0111 */ V(0, 1, 3),  /* 1000 */ V(1, 1, 2),  /* 1001 */ V(1, 1, 2),  /* 1010 */ V(1, 1, 2),  /* 1011 */ V(1, 1, 2),  /* 1100 */ V(1, 0, 3),  /* 1101 */ V(1, 0, 3),  /* 1110 */ V(0, 0, 3),  /* 1111 */ V(0, 0, 3),  /* 0000 ... */  /* 000  */ V(3, 3, 3),	/* 16 */  /* 001  */ V(0, 3, 3),  /* 010  */ V(2, 3, 2),  /* 011  */ V(2, 3, 2),  /* 100  */ V(3, 2, 2),  /* 101  */ V(3, 2, 2),  /* 110  */ V(3, 0, 2),  /* 111  */ V(3, 0, 2),  /* 0001 ... */  /* 0    */ V(1, 3, 1),	/* 24 */  /* 1    */ V(3, 1, 1),  /* 0010 ... */  /* 0    */ V(2, 2, 1),	/* 26 */  /* 1    */ V(0, 2, 1)};staticunion huffpair const hufftab7[] = {  /* 0000 */ PTR(16, 4),  /* 0001 */ PTR(32, 4),  /* 0010 */ PTR(48, 2),  /* 0011 */ V(1, 1, 4),  /* 0100 */ V(0, 1, 3),  /* 0101 */ V(0, 1, 3),  /* 0110 */ V(1, 0, 3),  /* 0111 */ V(1, 0, 3),  /* 1000 */ V(0, 0, 1),  /* 1001 */ V(0, 0, 1),  /* 1010 */ V(0, 0, 1),  /* 1011 */ V(0, 0, 1),  /* 1100 */ V(0, 0, 1),  /* 1101 */ V(0, 0, 1),  /* 1110 */ V(0, 0, 1),  /* 1111 */ V(0, 0, 1),  /* 0000 ... */  /* 0000 */ PTR(52, 2),	/* 16 */  /* 0001 */ PTR(56, 1),  /* 0010 */ PTR(58, 1),  /* 0011 */ V(1, 5, 4),  /* 0100 */ V(5, 1, 4),  /* 0101 */ PTR(60, 1),  /* 0110 */ V(5, 0, 4),  /* 0111 */ PTR(62, 1),  /* 1000 */ V(2, 4, 4),  /* 1001 */ V(4, 2, 4),  /* 1010 */ V(1, 4, 3),  /* 1011 */ V(1, 4, 3),  /* 1100 */ V(4, 1, 3),  /* 1101 */ V(4, 1, 3),  /* 1110 */ V(4, 0, 3),  /* 1111 */ V(4, 0, 3),  /* 0001 ... */  /* 0000 */ V(0, 4, 4),	/* 32 */  /* 0001 */ V(2, 3, 4),  /* 0010 */ V(3, 2, 4),  /* 0011 */ V(0, 3, 4),  /* 0100 */ V(1, 3, 3),  /* 0101 */ V(1, 3, 3),  /* 0110 */ V(3, 1, 3),  /* 0111 */ V(3, 1, 3),  /* 1000 */ V(3, 0, 3),  /* 1001 */ V(3, 0, 3),  /* 1010 */ V(2, 2, 3),  /* 1011 */ V(2, 2, 3),  /* 1100 */ V(1, 2, 2),  /* 1101 */ V(1, 2, 2),  /* 1110 */ V(1, 2, 2),  /* 1111 */ V(1, 2, 2),  /* 0010 ... */  /* 00   */ V(2, 1, 1),	/* 48 */  /* 01   */ V(2, 1, 1),  /* 10   */ V(0, 2, 2),  /* 11   */ V(2, 0, 2),  /* 0000 0000 ... */  /* 00   */ V(5, 5, 2),	/* 52 */  /* 01   */ V(4, 5, 2),  /* 10   */ V(5, 4, 2),  /* 11   */ V(5, 3, 2),  /* 0000 0001 ... */  /* 0    */ V(3, 5, 1),	/* 56 */  /* 1    */ V(4, 4, 1),  /* 0000 0010 ... */  /* 0    */ V(2, 5, 1),	/* 58 */  /* 1    */ V(5, 2, 1),  /* 0000 0101 ... */  /* 0    */ V(0, 5, 1),	/* 60 */  /* 1    */ V(3, 4, 1),  /* 0000 0111 ... */  /* 0    */ V(4, 3, 1),	/* 62 */  /* 1    */ V(3, 3, 1)};# if 0/* this version saves 8 entries (16 bytes) at the expense of   an extra lookup in 4 out of 36 cases */staticunion huffpair const hufftab8[] = {  /* 0000 */ PTR(16, 4),  /* 0001 */ PTR(32, 2),  /* 0010 */ V(1, 2, 4),  /* 0011 */ V(2, 1, 4),  /* 0100 */ V(1, 1, 2),  /* 0101 */ V(1, 1, 2),  /* 0110 */ V(1, 1, 2),  /* 0111 */ V(1, 1, 2),  /* 1000 */ V(0, 1, 3),  /* 1001 */ V(0, 1, 3),  /* 1010 */ V(1, 0, 3),  /* 1011 */ V(1, 0, 3),  /* 1100 */ V(0, 0, 2),  /* 1101 */ V(0, 0, 2),  /* 1110 */ V(0, 0, 2),  /* 1111 */ V(0, 0, 2),  /* 0000 ... */  /* 0000 */ PTR(36, 3),	/* 16 */  /* 0001 */ PTR(44, 2),  /* 0010 */ PTR(48, 1),  /* 0011 */ V(1, 5, 4),  /* 0100 */ V(5, 1, 4),  /* 0101 */ PTR(50, 1),  /* 0110 */ PTR(52, 1),  /* 0111 */ V(2, 4, 4),  /* 1000 */ V(4, 2, 4),  /* 1001 */ V(1, 4, 4),  /* 1010 */ V(4, 1, 3),  /* 1011 */ V(4, 1, 3),  /* 1100 */ V(0, 4, 4),  /* 1101 */ V(4, 0, 4),  /* 1110 */ V(2, 3, 4),  /* 1111 */ V(3, 2, 4),  /* 0001 ... */  /* 00   */ PTR(54, 2),	/* 32 */  /* 01   */ V(2, 2, 2),  /* 10   */ V(0, 2, 2),  /* 11   */ V(2, 0, 2),  /* 0000 0000 ... */  /* 000  */ V(5, 5, 3),	/* 36 */  /* 001  */ V(5, 4, 3),  /* 010  */ V(4, 5, 2),  /* 011  */ V(4, 5, 2),  /* 100  */ V(5, 3, 1),  /* 101  */ V(5, 3, 1),  /* 110  */ V(5, 3, 1),  /* 111  */ V(5, 3, 1),  /* 0000 0001 ... */  /* 00   */ V(3, 5, 2),	/* 44 */  /* 01   */ V(4, 4, 2),  /* 10   */ V(2, 5, 1),  /* 11   */ V(2, 5, 1),  /* 0000 0010 ... */  /* 0    */ V(5, 2, 1),	/* 48 */  /* 1    */ V(0, 5, 1),  /* 0000 0101 ... */  /* 0    */ V(3, 4, 1),	/* 50 */  /* 1    */ V(4, 3, 1),  /* 0000 0110 ... */  /* 0    */ V(5, 0, 1),	/* 52 */  /* 1    */ V(3, 3, 1),  /* 0001 00 ... */  /* 00   */ V(1, 3, 2),	/* 54 */  /* 01   */ V(3, 1, 2),  /* 10   */ V(0, 3, 2),  /* 11   */ V(3, 0, 2),};# elsestaticunion huffpair const hufftab8[] = {  /* 0000 */ PTR(16, 4),  /* 0001 */ PTR(32, 4),  /* 0010 */ V(1, 2, 4),  /* 0011 */ V(2, 1, 4),  /* 0100 */ V(1, 1, 2),  /* 0101 */ V(1, 1, 2),  /* 0110 */ V(1, 1, 2),  /* 0111 */ V(1, 1, 2),  /* 1000 */ V(0, 1, 3),  /* 1001 */ V(0, 1, 3),  /* 1010 */ V(1, 0, 3),  /* 1011 */ V(1, 0, 3),  /* 1100 */ V(0, 0, 2),  /* 1101 */ V(0, 0, 2),  /* 1110 */ V(0, 0, 2),  /* 1111 */ V(0, 0, 2),  /* 0000 ... */  /* 0000 */ PTR(48, 3),	/* 16 */  /* 0001 */ PTR(56, 2),  /* 0010 */ PTR(60, 1),  /* 0011 */ V(1, 5, 4),  /* 0100 */ V(5, 1, 4),  /* 0101 */ PTR(62, 1),  /* 0110 */ PTR(64, 1),  /* 0111 */ V(2, 4, 4),  /* 1000 */ V(4, 2, 4),  /* 1001 */ V(1, 4, 4),  /* 1010 */ V(4, 1, 3),  /* 1011 */ V(4, 1, 3),  /* 1100 */ V(0, 4, 4),  /* 1101 */ V(4, 0, 4),  /* 1110 */ V(2, 3, 4),  /* 1111 */ V(3, 2, 4),  /* 0001 ... */  /* 0000 */ V(1, 3, 4),	/* 32 */  /* 0001 */ V(3, 1, 4),  /* 0010 */ V(0, 3, 4),  /* 0011 */ V(3, 0, 4),  /* 0100 */ V(2, 2, 2),  /* 0101 */ V(2, 2, 2),  /* 0110 */ V(2, 2, 2),  /* 0111 */ V(2, 2, 2),  /* 1000 */ V(0, 2, 2),  /* 1001 */ V(0, 2, 2),  /* 1010 */ V(0, 2, 2),  /* 1011 */ V(0, 2, 2),  /* 1100 */ V(2, 0, 2),  /* 1101 */ V(2, 0, 2),  /* 1110 */ V(2, 0, 2),  /* 1111 */ V(2, 0, 2),  /* 0000 0000 ... */  /* 000  */ V(5, 5, 3),	/* 48 */  /* 001  */ V(5, 4, 3),  /* 010  */ V(4, 5, 2),  /* 011  */ V(4, 5, 2),  /* 100  */ V(5, 3, 1),  /* 101  */ V(5, 3, 1),  /* 110  */ V(5, 3, 1),  /* 111  */ V(5, 3, 1),  /* 0000 0001 ... */  /* 00   */ V(3, 5, 2),	/* 56 */  /* 01   */ V(4, 4, 2),  /* 10   */ V(2, 5, 1),  /* 11   */ V(2, 5, 1),  /* 0000 0010 ... */  /* 0    */ V(5, 2, 1),	/* 60 */  /* 1    */ V(0, 5, 1),  /* 0000 0101 ... */  /* 0    */ V(3, 4, 1),	/* 62 */  /* 1    */ V(4, 3, 1),  /* 0000 0110 ... */  /* 0    */ V(5, 0, 1),	/* 64 */  /* 1    */ V(3, 3, 1)};# endifstaticunion huffpair const hufftab9[] = {  /* 0000 */ PTR(16, 4),  /* 0001 */ PTR(32, 3),  /* 0010 */ PTR(40, 2),  /* 0011 */ PTR(44, 2),  /* 0100 */ PTR(48, 1),  /* 0101 */ V(1, 2, 4),  /* 0110 */ V(2, 1, 4),  /* 0111 */ V(2, 0, 4),  /* 1000 */ V(1, 1, 3),  /* 1001 */ V(1, 1, 3),  /* 1010 */ V(0, 1, 3),  /* 1011 */ V(0, 1, 3),  /* 1100 */ V(1, 0, 3),  /* 1101 */ V(1, 0, 3),  /* 1110 */ V(0, 0, 3),  /* 1111 */ V(0, 0, 3),  /* 0000 ... */  /* 0000 */ PTR(50, 1),	/* 16 */  /* 0001 */ V(3, 5, 4),  /* 0010 */ V(5, 3, 4),  /* 0011 */ PTR(52, 1),  /* 0100 */ V(4, 4, 4),  /* 0101 */ V(2, 5, 4),  /* 0110 */ V(5, 2, 4),  /* 0111 */ V(1, 5, 4),  /* 1000 */ V(5, 1, 3),  /* 1001 */ V(5, 1, 3),  /* 1010 */ V(3, 4, 3),  /* 1011 */ V(3, 4, 3),  /* 1100 */ V(4, 3, 3),  /* 1101 */ V(4, 3, 3),  /* 1110 */ V(5, 0, 4),  /* 1111 */ V(0, 4, 4),  /* 0001 ... */  /* 000  */ V(2, 4, 3),	/* 32 */  /* 001  */ V(4, 2, 3),  /* 010  */ V(3, 3, 3),  /* 011  */ V(4, 0, 3),  /* 100  */ V(1, 4, 2),  /* 101  */ V(1, 4, 2),  /* 110  */ V(4, 1, 2),  /* 111  */ V(4, 1, 2),  /* 0010 ... */  /* 00   */ V(2, 3, 2),	/* 40 */  /* 01   */ V(3, 2, 2),  /* 10   */ V(1, 3, 1),  /* 11   */ V(1, 3, 1),  /* 0011 ... */  /* 00   */ V(3, 1, 1),	/* 44 */  /* 01   */ V(3, 1, 1),  /* 10   */ V(0, 3, 2),  /* 11   */ V(3, 0, 2),