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