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