| 1 |
/* This file is part of libmspack. |
| 2 |
* (C) 2003-2010 Stuart Caie. |
| 3 |
* |
| 4 |
* libmspack is free software; you can redistribute it and/or modify it under |
| 5 |
* the terms of the GNU Lesser General Public License (LGPL) version 2.1 |
| 6 |
* |
| 7 |
* For further details, see the file COPYING.LIB distributed with libmspack |
| 8 |
*/ |
| 9 |
|
| 10 |
#ifndef MSPACK_READHUFF_H |
| 11 |
#define MSPACK_READHUFF_H 1 |
| 12 |
|
| 13 |
/* This implements a fast Huffman tree decoding system. |
| 14 |
*/ |
| 15 |
|
| 16 |
#if !(defined(BITS_ORDER_MSB) || defined(BITS_ORDER_LSB)) |
| 17 |
# error "readhuff.h is used in conjunction with readbits.h, include that first" |
| 18 |
#endif |
| 19 |
#if !(defined(TABLEBITS) && defined(MAXSYMBOLS)) |
| 20 |
# error "define TABLEBITS(tbl) and MAXSYMBOLS(tbl) before using readhuff.h" |
| 21 |
#endif |
| 22 |
#if !(defined(HUFF_TABLE) && defined(HUFF_LEN)) |
| 23 |
# error "define HUFF_TABLE(tbl) and HUFF_LEN(tbl) before using readhuff.h" |
| 24 |
#endif |
| 25 |
#ifndef HUFF_ERROR |
| 26 |
# error "define HUFF_ERROR before using readhuff.h" |
| 27 |
#endif |
| 28 |
#ifndef HUFF_MAXBITS |
| 29 |
# define HUFF_MAXBITS 16 |
| 30 |
#endif |
| 31 |
|
| 32 |
/* Decodes the next huffman symbol from the input bitstream into var. |
| 33 |
* Do not use this macro on a table unless build_decode_table() succeeded. |
| 34 |
*/ |
| 35 |
#define READ_HUFFSYM(tbl, var) do { \ |
| 36 |
ENSURE_BITS(HUFF_MAXBITS); \ |
| 37 |
sym = HUFF_TABLE(tbl, PEEK_BITS(TABLEBITS(tbl))); \ |
| 38 |
if (sym >= MAXSYMBOLS(tbl)) HUFF_TRAVERSE(tbl); \ |
| 39 |
(var) = sym; \ |
| 40 |
i = HUFF_LEN(tbl, sym); \ |
| 41 |
REMOVE_BITS(i); \ |
| 42 |
} while (0) |
| 43 |
|
| 44 |
#ifdef BITS_ORDER_LSB |
| 45 |
# define HUFF_TRAVERSE(tbl) do { \ |
| 46 |
i = TABLEBITS(tbl) - 1; \ |
| 47 |
do { \ |
| 48 |
if (i++ > HUFF_MAXBITS) HUFF_ERROR; \ |
| 49 |
sym = HUFF_TABLE(tbl, \ |
| 50 |
(sym << 1) | ((bit_buffer >> i) & 1)); \ |
| 51 |
} while (sym >= MAXSYMBOLS(tbl)); \ |
| 52 |
} while (0) |
| 53 |
#else |
| 54 |
#define HUFF_TRAVERSE(tbl) do { \ |
| 55 |
i = 1 << (BITBUF_WIDTH - TABLEBITS(tbl)); \ |
| 56 |
do { \ |
| 57 |
if ((i >>= 1) == 0) HUFF_ERROR; \ |
| 58 |
sym = HUFF_TABLE(tbl, \ |
| 59 |
(sym << 1) | ((bit_buffer & i) ? 1 : 0)); \ |
| 60 |
} while (sym >= MAXSYMBOLS(tbl)); \ |
| 61 |
} while (0) |
| 62 |
#endif |
| 63 |
|
| 64 |
/* make_decode_table(nsyms, nbits, length[], table[]) |
| 65 |
* |
| 66 |
* This function was originally coded by David Tritscher. |
| 67 |
* It builds a fast huffman decoding table from |
| 68 |
* a canonical huffman code lengths table. |
| 69 |
* |
| 70 |
* nsyms = total number of symbols in this huffman tree. |
| 71 |
* nbits = any symbols with a code length of nbits or less can be decoded |
| 72 |
* in one lookup of the table. |
| 73 |
* length = A table to get code lengths from [0 to nsyms-1] |
| 74 |
* table = The table to fill up with decoded symbols and pointers. |
| 75 |
* Should be ((1<<nbits) + (nsyms*2)) in length. |
| 76 |
* |
| 77 |
* Returns 0 for OK or 1 for error |
| 78 |
*/ |
| 79 |
static int make_decode_table(unsigned int nsyms, unsigned int nbits, |
| 80 |
unsigned char *length, unsigned short *table) |
| 81 |
{ |
| 82 |
register unsigned short sym, next_symbol; |
| 83 |
register unsigned int leaf, fill; |
| 84 |
#ifdef BITS_ORDER_LSB |
| 85 |
register unsigned int reverse; |
| 86 |
#endif |
| 87 |
register unsigned char bit_num; |
| 88 |
unsigned int pos = 0; /* the current position in the decode table */ |
| 89 |
unsigned int table_mask = 1 << nbits; |
| 90 |
unsigned int bit_mask = table_mask >> 1; /* don't do 0 length codes */ |
| 91 |
|
| 92 |
/* fill entries for codes short enough for a direct mapping */ |
| 93 |
for (bit_num = 1; bit_num <= nbits; bit_num++) { |
| 94 |
for (sym = 0; sym < nsyms; sym++) { |
| 95 |
if (length[sym] != bit_num) continue; |
| 96 |
#ifdef BITS_ORDER_MSB |
| 97 |
leaf = pos; |
| 98 |
#else |
| 99 |
/* reverse the significant bits */ |
| 100 |
fill = length[sym]; reverse = pos >> (nbits - fill); leaf = 0; |
| 101 |
do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill); |
| 102 |
#endif |
| 103 |
|
| 104 |
if((pos += bit_mask) > table_mask) return 1; /* table overrun */ |
| 105 |
|
| 106 |
/* fill all possible lookups of this symbol with the symbol itself */ |
| 107 |
#ifdef BITS_ORDER_MSB |
| 108 |
for (fill = bit_mask; fill-- > 0;) table[leaf++] = sym; |
| 109 |
#else |
| 110 |
fill = bit_mask; next_symbol = 1 << bit_num; |
| 111 |
do { table[leaf] = sym; leaf += next_symbol; } while (--fill); |
| 112 |
#endif |
| 113 |
} |
| 114 |
bit_mask >>= 1; |
| 115 |
} |
| 116 |
|
| 117 |
/* exit with success if table is now complete */ |
| 118 |
if (pos == table_mask) return 0; |
| 119 |
|
| 120 |
/* mark all remaining table entries as unused */ |
| 121 |
for (sym = pos; sym < table_mask; sym++) { |
| 122 |
#ifdef BITS_ORDER_MSB |
| 123 |
table[sym] = 0xFFFF; |
| 124 |
#else |
| 125 |
reverse = sym; leaf = 0; fill = nbits; |
| 126 |
do { leaf <<= 1; leaf |= reverse & 1; reverse >>= 1; } while (--fill); |
| 127 |
table[leaf] = 0xFFFF; |
| 128 |
#endif |
| 129 |
} |
| 130 |
|
| 131 |
/* next_symbol = base of allocation for long codes */ |
| 132 |
next_symbol = ((table_mask >> 1) < nsyms) ? nsyms : (table_mask >> 1); |
| 133 |
|
| 134 |
/* give ourselves room for codes to grow by up to 16 more bits. |
| 135 |
* codes now start at bit nbits+16 and end at (nbits+16-codelength) */ |
| 136 |
pos <<= 16; |
| 137 |
table_mask <<= 16; |
| 138 |
bit_mask = 1 << 15; |
| 139 |
|
| 140 |
for (bit_num = nbits+1; bit_num <= HUFF_MAXBITS; bit_num++) { |
| 141 |
for (sym = 0; sym < nsyms; sym++) { |
| 142 |
if (length[sym] != bit_num) continue; |
| 143 |
|
| 144 |
#ifdef BITS_ORDER_MSB |
| 145 |
leaf = pos >> 16; |
| 146 |
#else |
| 147 |
/* leaf = the first nbits of the code, reversed */ |
| 148 |
reverse = pos >> 16; leaf = 0; fill = nbits; |
| 149 |
do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill); |
| 150 |
#endif |
| 151 |
for (fill = 0; fill < (bit_num - nbits); fill++) { |
| 152 |
/* if this path hasn't been taken yet, 'allocate' two entries */ |
| 153 |
if (table[leaf] == 0xFFFF) { |
| 154 |
table[(next_symbol << 1) ] = 0xFFFF; |
| 155 |
table[(next_symbol << 1) + 1 ] = 0xFFFF; |
| 156 |
table[leaf] = next_symbol++; |
| 157 |
} |
| 158 |
|
| 159 |
/* follow the path and select either left or right for next bit */ |
| 160 |
leaf = table[leaf] << 1; |
| 161 |
if ((pos >> (15-fill)) & 1) leaf++; |
| 162 |
} |
| 163 |
table[leaf] = sym; |
| 164 |
|
| 165 |
if ((pos += bit_mask) > table_mask) return 1; /* table overflow */ |
| 166 |
} |
| 167 |
bit_mask >>= 1; |
| 168 |
} |
| 169 |
|
| 170 |
/* full table? */ |
| 171 |
return (pos == table_mask) ? 0 : 1; |
| 172 |
} |
| 173 |
#endif |