1 /*
2 * mkhuff.cc --
3 *
4 * This small program generates the P64 Huffman lookup tables.
5 *
6 * Copyright (c) 1993-2002 The Regents of the University of California.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions are met:
11 *
12 * A. Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 * B. Redistributions in binary form must reproduce the above copyright notice,
15 * this list of conditions and the following disclaimer in the documentation
16 * and/or other materials provided with the distribution.
17 * C. Neither the names of the copyright holders nor the names of its
18 * contributors may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
22 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
23 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #ifndef lint
35 static const char rcsid[] =
36 "@(#) $Header: /usr/mash/src/repository/mash/mash-1/codec/p64/mkhuff.cc,v 1.12 2003/11/14 23:35:30 aswan Exp $";
37 #endif
38
39 #include <stdlib.h>
40 #include <stdio.h>
41 #include <string.h>
42 #include <sys/types.h>
43 #ifdef WIN32
44 #include <winsock.h>
45 extern "C" {
46 int getopt(int, char * const *, const char *);
47 }
48 #endif
49 #ifndef WIN32
50 # include <unistd.h>
51 #endif
52 #define HUFFSTRINGS
53 #include "p64-huff.h"
54
55
56
57 /*
58 * Convert a binary string to an integer.
59 */
60 int
61 btoi(const char* s)
62 {
63 int v = 0;
64 while (*s) {
65 v <<= 1;
66 v |= *s++ - '';
67 }
68 return (v);
69 }
70
71 struct hufftab {
72 int maxlen;
73 short *prefix;
74 };
75
76 /*
77 * Build a direct map huffman table from the array of codes given.
78 * We build a prefix table such that we can directly index
79 * table with the k-bit number at the head of the bit stream, where
80 * k is the max-length code in the table. The table tells us
81 * the value and the actual length of the code we have.
82 * We need the length so we can tear that many bits off
83 * the input stream. The length and value are packed as
84 * two 16-bit quantities in a 32-bit word. The value is stored
85 * in the upper 16-bits, so when we right-shift it over,
86 * it is automatically sign-extended.
87 */
88 void
89 huffbuild(hufftab& ht, const huffcode* codes)
90 {
91 int i = 0;
92 int maxlen = 0;
93 for (; codes[i].str != 0; ++i) {
94 int v = strlen(codes[i].str);
95 if (v > maxlen)
96 maxlen = v;
97 }
98 int size = 1 << maxlen;
99 if (size > 65536)
100 abort();
101
102 /*
103 * Build the direct-map lookup table.
104 */
105 ht.prefix = new short[size];
106 ht.maxlen = maxlen;
107
108 /*
109 * Initialize states to illegal, and arrange
110 * for max bits to be stripped off the input.
111 */
112 for (i = 0; i < size; ++i)
113 ht.prefix[i] = (SYM_ILLEGAL << 5) | maxlen;
114
115 for (i = 0; codes[i].str != 0; ++i) {
116 int codelen = strlen(codes[i].str);
117 int nbit = maxlen - codelen;
118 int code = btoi(codes[i].str) << nbit;
119 int map = (codes[i].val << 5) | codelen;
120 /*
121 * The low nbit bits are don't cares.
122 * Spin through all possible combos.
123 */
124 for (int n = 1 << nbit; --n >= 0; ) {
125 if ((code | n) >= size)
126 abort();
127 ht.prefix[code | n] = map;
128 }
129 }
130 }
131
132 int
133 skipcode(int bs, int* code, int* len, int* symbol, int n)
134 {
135 int nbit = 0;
136 for (;;) {
137 /*
138 * Find the matching huffman code that is a prefix
139 * of bs at offset off. There is either zero
140 * or one such codes, since the huffman strings have
141 * unique prefixes. The zero case means the given
142 * bit string is impossible.
143 */
144 int pbit = nbit;
145 for (int k = 0; k < n; ++k) {
146 if (len[k] < 16 - nbit) {
147 int v = bs >> (16 - nbit - len[k]);
148 v &= (1 << len[k]) - 1;
149 if (v != code[k])
150 continue;
151 nbit += len[k];
152 if (symbol[k] == SYM_ESCAPE)
153 /*
154 * This must end the prefix
155 * since it necessarily takes
156 * up more than 16 bits.
157 */
158 return (nbit + 14);
159 else if (symbol[k] == SYM_EOB)
160 return (0x80 | nbit);
161 }
162 }
163 if (nbit == 0)
164 /*
165 * Didn't find any matches.
166 */
167 return (0x40);
168 /*
169 * If we didn't find a new match,
170 * return the current result.
171 */
172 if (nbit == pbit)
173 return (nbit);
174 }
175 }
176
177 /*
178 * Build a skip table. The idea is to have a fast way
179 * of finding the boundaries in the bit stream for a block
180 * (i.e., entropy/run-length encoded set of 8x8 DCT coefficients).
181 * The bit string can then be used to hash into a cache of
182 * recently computed inverse DCTs.
183 *
184 * The table is indexed 16 bits at a time. Each 8-bit entry
185 * tells how many bits are taken up by the longest string of
186 * whole codewords in the index. The length might be greater
187 * than 16 if there is an ESCAPE character (which is great
188 * because we can just skip over the following 14-bits).
189 * Bit 7 is set if the codes are terminated by EOB,; bit 6
190 * is set if the string is impossible; the length is in bits 0-5.
191 *
192 * Note that this table works only for the AC coeffcients, because
193 * the DC decoding is complicated by macroblock type context.
194 * That's okay because we want the hash table to contain inverse
195 * DCTs with 0 DC bias because adding in the DC component during
196 * the block copy incurs no additional cost (memory is the bottleneck),
197 * and using DC=0 significantly increases the probability of a
198 * cache hit.
199 */
200 void
201 skipbuild(const huffcode* hc, u_char* skiptab)
202 {
203 int len[1024];
204 int code[1024];
205 int symbol[1024];
206
207 int n = 0;
208 for (; hc->str != 0; ++hc) {
209 len[n] = strlen(hc->str);
210 code[n] = btoi(hc->str);
211 symbol[n] = hc->val;
212 ++n;
213 }
214 for (int bs = 0; bs < 65536; ++bs)
215 skiptab[bs] = skipcode(bs, code, len, symbol, n);
216 }
217
218 struct huff {
219 const char* name;
220 const huffcode* codes;
221 };
222 struct huff hc[] = {
223 { "htd_mtype", hc_mtype },
224 { "htd_mba", hc_mba },
225 { "htd_cbp", hc_cbp },
226 { "htd_dvm", hc_dvm },
227 { "htd_tcoeff", hc_tcoeff },
228 { 0, 0 }
229 };
230
231 const huffcode*
232 mba_lookup(int mba)
233 {
234 for (const huffcode* hc = hc_mba; hc->str != 0; ++hc)
235 if (hc->val == mba)
236 return (hc);
237 abort();
238 return (0); /*NOTREACHED*/
239 }
240
241 void
242 gen_hte_mba()
243 {
244 printf("struct huffent hte_mba[33] = {\n");
245 for (int mba = 0; mba < 33; ++mba) {
246 const huffcode* hc = mba_lookup(mba + 1);
247 printf("\t{ %d, %d },\n", btoi(hc->str), strlen(hc->str));
248 }
249 printf("};\n");
250 }
251
252 const huffcode*
253 tc_lookup(int run, int level)
254 {
255 int v = TC_RUN(run) | TC_LEVEL(level);
256 if (v <= 0)
257 return (0);
258 for (const huffcode* hc = hc_tcoeff; hc->str != 0; ++hc)
259 if (hc->val == v)
260 return (hc);
261 return (0);
262 }
263
264 void
265 gen_hte_tc()
266 {
267 const huffcode* hc;
268
269 /* 5 bits of (signed) level, 6 bits of (unsigned) run */
270 printf("struct huffent hte_tc[1 << 11] = {\n");
271 for (int level = -16; level <= 15; ++level) {
272 for (int run = 0; run < 64; ++run) {
273 hc = tc_lookup(run, (level + 16) & 0x1f);
274 if (run < 32 &&
275 (hc = tc_lookup(run, (level + 16) & 0x1f)) != 0)
276 printf("\t{ %d, %d },\n",
277 btoi(hc->str), strlen(hc->str));
278 else
279 printf("\t{ 0, 0 },\n");
280
281 }
282 }
283 printf("};\n");
284 }
285
286 void
287 usage()
288 {
289 printf("usage: mkhuff [-es]\n");
290 exit(1);
291 }
292
293 int
294 main(int argc, char **argv)
295 {
296 int sflag = 0;
297 int eflag = 0;
298
299 #ifdef notyet
300 extern char *optarg;
301 extern int optind, opterr;
302 #endif
303
304 int op;
305 while ((op = getopt(argc, argv, "es")) != -1) {
306 switch (op) {
307 case 's':
308 ++sflag;
309 break;
310 case 'e':
311 ++eflag;
312 break;
313 default:
314 usage();
315 break;
316 }
317 }
318 printf("#include \"codec/p64/p64-huff.h\"\n");
319
320 printf("#ifdef _MSC_VER\n");
321 printf("#pragma warning (disable: 4305)\n");
322 printf("#endif\n");
323
324 huff* p = hc;
325 while (p->name) {
326 hufftab ht;
327 huffbuild(ht, p->codes);
328 printf("const int %s_width = %d;\n", p->name, ht.maxlen);
329 printf("const short %s[] = {", p->name);
330 int n = 1 << ht.maxlen;
331 for (int i = 0; i < n; ++i)
332 printf("%s0x%04x,", (i & 7) ? " " : "\n\t",
333 ht.prefix[i] & 0xffff);
334 printf("\n};\n");
335 ++p;
336 }
337 if (eflag) {
338 gen_hte_mba();
339 gen_hte_tc();
340 }
341 if (sflag) {
342 u_char skiptab[65536];
343 skipbuild(hc_tcoeff, skiptab);
344 printf("const unsigned char skiptab[] = {");
345 for (int i = 0; i < 65536; ++i)
346 printf("%s0x%02x,", (i & 7) ? " " : "\n\t",
347 skiptab[i]);
348 printf("\n};\n");
349 }
350
351 printf("#ifdef _MSC_VER\n");
352 printf("#pragma warning (default: 4305)\n");
353 printf("#endif\n");
354
355 return (0);
356 }
357
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.