diff options
author | Dominik Riebeling <Dominik.Riebeling@gmail.com> | 2021-12-15 21:04:28 +0100 |
---|---|---|
committer | Dominik Riebeling <Dominik.Riebeling@gmail.com> | 2021-12-24 18:05:53 +0100 |
commit | c876d3bbefe0dc00c27ca0c12d29da5874946962 (patch) | |
tree | 69f468a185a369b01998314bc3ecc19b70f4fcaa /utils/rbutilqt/mspack/readhuff.h | |
parent | 6c6f0757d7a902feb293be165d1490c42bc8e7ad (diff) | |
download | rockbox-c876d3bbefe0dc00c27ca0c12d29da5874946962.tar.gz rockbox-c876d3bbefe0dc00c27ca0c12d29da5874946962.zip |
rbutil: Merge rbutil with utils folder.
rbutil uses several components from the utils folder, and can be
considered part of utils too. Having it in a separate folder is an
arbitrary split that doesn't help anymore these days, so merge them.
This also allows other utils to easily use libtools.make without the
need to navigate to a different folder.
Change-Id: I3fc2f4de19e3e776553efb5dea5f779dfec0dc21
Diffstat (limited to 'utils/rbutilqt/mspack/readhuff.h')
-rw-r--r-- | utils/rbutilqt/mspack/readhuff.h | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/utils/rbutilqt/mspack/readhuff.h b/utils/rbutilqt/mspack/readhuff.h new file mode 100644 index 0000000000..4d94225789 --- /dev/null +++ b/utils/rbutilqt/mspack/readhuff.h | |||
@@ -0,0 +1,172 @@ | |||
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 | */ | ||
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 | ||