1 /*
2 * minilex.c
3 *
4 * High efficiency lexical state parser
5 *
6 * Copyright (C)2011-2014 Andy Green <andy@warmcat.com>
7 *
8 * Licensed under MIT
9 *
10 * Usage: gcc minihuf.c -o minihuf && ./minihuf > huftable.h
11 *
12 * Run it twice to test parsing on the generated table on stderr
13 */
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18
19 #define LWS_ARRAY_SIZE(n) (sizeof(n) / sizeof(n[0]))
20
21 struct huf {
22 unsigned int code;
23 unsigned char len;
24 };
25
26 static struct huf huf_literal[] = {
27 /* 0x00 */ { 0x1ff8, 13 },
28 /* 0x01 */ { 0x7fffd8, 23 },
29 /* 0x02 */ { 0xfffffe2, 28 },
30 /* 0x03 */ { 0xfffffe3, 28 },
31 /* 0x04 */ { 0xfffffe4, 28 },
32 /* 0x05 */ { 0xfffffe5, 28 },
33 /* 0x06 */ { 0xfffffe6, 28 },
34 /* 0x07 */ { 0xfffffe7, 28 },
35 /* 0x08 */ { 0xfffffe8, 28 },
36 /* 0x09 */ { 0xffffea, 24 },
37 /* 0x0a */ { 0x3ffffffc, 30 },
38 /* 0x0b */ { 0xfffffe9, 28 },
39
40 /* 0x0c */ { 0xfffffea, 28 },
41 /* 0x0d */ { 0x3ffffffd, 30 },
42 /* 0x0e */ { 0xfffffeb, 28 },
43 /* 0x0f */ { 0xfffffec, 28 },
44 /* 0x10 */ { 0xfffffed, 28 },
45 /* 0x11 */ { 0xfffffee, 28 },
46 /* 0x12 */ { 0xfffffef, 28 },
47 /* 0x13 */ { 0xffffff0, 28 },
48 /* 0x14 */ { 0xffffff1, 28 },
49 /* 0x15 */ { 0xffffff2, 28 },
50 /* 0x16 */ { 0x3ffffffe, 30 },
51 /* 0x17 */ { 0xffffff3, 28 },
52 /* 0x18 */ { 0xffffff4, 28 },
53 /* 0x19 */ { 0xffffff5, 28 },
54 /* 0x1a */ { 0xffffff6, 28 },
55 /* 0x1b */ { 0xffffff7, 28 },
56 /* 0x1c */ { 0xffffff8, 28 },
57 /* 0x1d */ { 0xffffff9, 28 },
58 /* 0x1e */ { 0xffffffa, 28 },
59 /* 0x1f */ { 0xffffffb, 28 },
60 /* 0x20 */ { 0x14, 6 },
61 /* 0x21 */ { 0x3f8, 10 },
62 /* 0x22 */ { 0x3f9, 10 },
63 /* 0x23 */ { 0xffa, 12 },
64 /* 0x24 */ { 0x1ff9, 13 },
65 /* 0x25 */ { 0x15, 6 },
66 /* 0x26 */ { 0xf8, 8 },
67 /* 0x27 */ { 0x7fa, 11 },
68 /* 0x28 */ { 0x3fa, 10 },
69 /* 0x29 */ { 0x3fb, 10 },
70 /* 0x2a */ { 0xf9, 8 },
71 /* 0x2b */ { 0x7fb, 11 },
72 /* 0x2c */ { 0xfa, 8 },
73 /* 0x2d */ { 0x16, 6 },
74 /* 0x2e */ { 0x17, 6 },
75 /* 0x2f */ { 0x18, 6 },
76 /* 0x30 */ { 0x0, 5 },
77 /* 0x31 */ { 0x1, 5 },
78 /* 0x32 */ { 0x2, 5 },
79 /* 0x33 */ { 0x19, 6 },
80 /* 0x34 */ { 0x1a, 6 },
81 /* 0x35 */ { 0x1b, 6 },
82 /* 0x36 */ { 0x1c, 6 },
83 /* 0x37 */ { 0x1d, 6 },
84 /* 0x38 */ { 0x1e, 6 },
85 /* 0x39 */ { 0x1f, 6 },
86 /* 0x3a */ { 0x5c, 7 },
87 /* 0x3b */ { 0xfb, 8 },
88
89 /* 0x3c */ { 0x7ffc, 15 },
90 /* 0x3d */ { 0x20, 6 },
91 /* 0x3e */ { 0xffb, 12 },
92 /* 0x3f */ { 0x3fc, 10 },
93 /* 0x40 */ { 0x1ffa, 13 },
94 /* 0x41 */ { 0x21, 6 },
95 /* 0x42 */ { 0x5d, 7 },
96 /* 0x43 */ { 0x5e, 7 },
97 /* 0x44 */ { 0x5f, 7 },
98 /* 0x45 */ { 0x60, 7 },
99 /* 0x46 */ { 0x61, 7 },
100 /* 0x47 */ { 0x62, 7 },
101 /* 0x48 */ { 0x63, 7 },
102 /* 0x49 */ { 0x64, 7 },
103 /* 0x4a */ { 0x65, 7 },
104 /* 0x4b */ { 0x66, 7 },
105 /* 0x4c */ { 0x67, 7 },
106 /* 0x4d */ { 0x68, 7 },
107 /* 0x4e */ { 0x69, 7 },
108 /* 0x4f */ { 0x6a, 7 },
109 /* 0x50 */ { 0x6b, 7 },
110 /* 0x51 */ { 0x6c, 7 },
111 /* 0x52 */ { 0x6d, 7 },
112 /* 0x53 */ { 0x6e, 7 },
113 /* 0x54 */ { 0x6f, 7 },
114 /* 0x55 */ { 0x70, 7 },
115 /* 0x56 */ { 0x71, 7 },
116 /* 0x57 */ { 0x72, 7 },
117 /* 0x58 */ { 0xfc, 8 },
118 /* 0x59 */ { 0x73, 7 },
119 /* 0x5a */ { 0xfd, 8 },
120 /* 0x5b */ { 0x1ffb, 13 },
121 /* 0x5c */ { 0x7fff0, 19 },
122 /* 0x5d */ { 0x1ffc, 13 },
123 /* 0x5e */ { 0x3ffc, 14 },
124 /* 0x5f */ { 0x22, 6 },
125 /* 0x60 */ { 0x7ffd, 15 },
126 /* 0x61 */ { 0x3, 5 },
127 /* 0x62 */ { 0x23, 6 },
128 /* 0x63 */ { 0x4, 5 },
129 /* 0x64 */ { 0x24, 6 },
130 /* 0x65 */ { 0x5, 5 },
131 /* 0x66 */ { 0x25, 6 },
132 /* 0x67 */ { 0x26, 6 },
133 /* 0x68 */ { 0x27, 6 },
134 /* 0x69 */ { 0x6, 5 },
135 /* 0x6a */ { 0x74, 7 },
136 /* 0x6b */ { 0x75, 7 },
137
138
139 /* 0x6c */ { 0x28, 6 },
140 /* 0x6d */ { 0x29, 6 },
141 /* 0x6e */ { 0x2a, 6 },
142 /* 0x6f */ { 0x7, 5 },
143 /* 0x70 */ { 0x2b, 6 },
144 /* 0x71 */ { 0x76, 7 },
145 /* 0x72 */ { 0x2c, 6 },
146 /* 0x73 */ { 0x8, 5 },
147 /* 0x74 */ { 0x9, 5 },
148 /* 0x75 */ { 0x2d, 6 },
149 /* 0x76 */ { 0x77, 7 },
150 /* 0x77 */ { 0x78, 7 },
151 /* 0x78 */ { 0x79, 7 },
152 /* 0x79 */ { 0x7a, 7 },
153 /* 0x7a */ { 0x7b, 7 },
154 /* 0x7b */ { 0x7ffe, 15 },
155 /* 0x7c */ { 0x7fc, 11 },
156 /* 0x7d */ { 0x3ffd, 14 },
157 /* 0x7e */ { 0x1ffd, 13 },
158 /* 0x7f */ { 0xffffffc, 28 },
159 /* 0x80 */ { 0xfffe6, 20 },
160 /* 0x81 */ { 0x3fffd2, 22 },
161 /* 0x82 */ { 0xfffe7, 20 },
162 /* 0x83 */ { 0xfffe8, 20 },
163 /* 0x84 */ { 0x3fffd3, 22 },
164 /* 0x85 */ { 0x3fffd4, 22 },
165 /* 0x86 */ { 0x3fffd5, 22 },
166 /* 0x87 */ { 0x7fffd9, 23 },
167 /* 0x88 */ { 0x3fffd6, 22 },
168 /* 0x89 */ { 0x7fffda, 23 },
169 /* 0x8a */ { 0x7fffdb, 23 },
170 /* 0x8b */ { 0x7fffdc, 23 },
171 /* 0x8c */ { 0x7fffdd, 23 },
172 /* 0x8d */ { 0x7fffde, 23 },
173 /* 0x8e */ { 0xffffeb, 24 },
174 /* 0x8f */ { 0x7fffdf, 23 },
175 /* 0x90 */ { 0xffffec, 24 },
176 /* 0x91 */ { 0xffffed, 24 },
177 /* 0x92 */ { 0x3fffd7, 22 },
178 /* 0x93 */ { 0x7fffe0, 23 },
179 /* 0x94 */ { 0xffffee, 24 },
180 /* 0x95 */ { 0x7fffe1, 23 },
181 /* 0x96 */ { 0x7fffe2, 23 },
182 /* 0x97 */ { 0x7fffe3, 23 },
183 /* 0x98 */ { 0x7fffe4, 23 },
184 /* 0x99 */ { 0x1fffdc, 21 },
185 /* 0x9a */ { 0x3fffd8, 22 },
186 /* 0x9b */ { 0x7fffe5, 23 },
187
188 /* 0x9c */ { 0x3fffd9, 22 },
189 /* 0x9d */ { 0x7fffe6, 23 },
190 /* 0x9e */ { 0x7fffe7, 23 },
191 /* 0x9f */ { 0xffffef, 24 },
192 /* 0xa0 */ { 0x3fffda, 22 },
193 /* 0xa1 */ { 0x1fffdd, 21 },
194 /* 0xa2 */ { 0xfffe9, 20 },
195 /* 0xa3 */ { 0x3fffdb, 22 },
196 /* 0xa4 */ { 0x3fffdc, 22 },
197 /* 0xa5 */ { 0x7fffe8, 23 },
198 /* 0xa6 */ { 0x7fffe9, 23 },
199 /* 0xa7 */ { 0x1fffde, 21 },
200 /* 0xa8 */ { 0x7fffea, 23 },
201 /* 0xa9 */ { 0x3fffdd, 22 },
202 /* 0xaa */ { 0x3fffde, 22 },
203 /* 0xab */ { 0xfffff0, 24 },
204 /* 0xac */ { 0x1fffdf, 21 },
205 /* 0xad */ { 0x3fffdf, 22 },
206 /* 0xae */ { 0x7fffeb, 23 },
207 /* 0xaf */ { 0x7fffec, 23 },
208 /* 0xb0 */ { 0x1fffe0, 21 },
209 /* 0xb1 */ { 0x1fffe1, 21 },
210 /* 0xb2 */ { 0x3fffe0, 22 },
211 /* 0xb3 */ { 0x1fffe2, 21 },
212 /* 0xb4 */ { 0x7fffed, 23 },
213 /* 0xb5 */ { 0x3fffe1, 22 },
214 /* 0xb6 */ { 0x7fffee, 23 },
215 /* 0xb7 */ { 0x7fffef, 23 },
216 /* 0xb8 */ { 0xfffea, 20 },
217 /* 0xb9 */ { 0x3fffe2, 22 },
218 /* 0xba */ { 0x3fffe3, 22 },
219 /* 0xbb */ { 0x3fffe4, 22 },
220 /* 0xbc */ { 0x7ffff0, 23 },
221 /* 0xbd */ { 0x3fffe5, 22 },
222 /* 0xbe */ { 0x3fffe6, 22 },
223 /* 0xbf */ { 0x7ffff1, 23 },
224 /* 0xc0 */ { 0x3ffffe0, 26 },
225 /* 0xc1 */ { 0x3ffffe1, 26 },
226 /* 0xc2 */ { 0xfffeb, 20 },
227 /* 0xc3 */ { 0x7fff1, 19 },
228 /* 0xc4 */ { 0x3fffe7, 22 },
229 /* 0xc5 */ { 0x7ffff2, 23 },
230 /* 0xc6 */ { 0x3fffe8, 22 },
231 /* 0xc7 */ { 0x1ffffec, 25 },
232 /* 0xc8 */ { 0x3ffffe2, 26 },
233 /* 0xc9 */ { 0x3ffffe3, 26 },
234 /* 0xca */ { 0x3ffffe4, 26 },
235 /* 0xcb */ { 0x7ffffde, 27 },
236
237 /* 0xcc */ { 0x7ffffdf, 27 },
238 /* 0xcd */ { 0x3ffffe5, 26 },
239 /* 0xce */ { 0xfffff1, 24 },
240 /* 0xcf */ { 0x1ffffed, 25 },
241 /* 0xd0 */ { 0x7fff2, 19 },
242 /* 0xd1 */ { 0x1fffe3, 21 },
243 /* 0xd2 */ { 0x3ffffe6, 26 },
244 /* 0xd3 */ { 0x7ffffe0, 27 },
245 /* 0xd4 */ { 0x7ffffe1, 27 },
246 /* 0xd5 */ { 0x3ffffe7, 26 },
247 /* 0xd6 */ { 0x7ffffe2, 27 },
248 /* 0xd7 */ { 0xfffff2, 24 },
249 /* 0xd8 */ { 0x1fffe4, 21 },
250 /* 0xd9 */ { 0x1fffe5, 21 },
251 /* 0xda */ { 0x3ffffe8, 26 },
252 /* 0xdb */ { 0x3ffffe9, 26 },
253 /* 0xdc */ { 0xffffffd, 28 },
254 /* 0xdd */ { 0x7ffffe3, 27 },
255 /* 0xde */ { 0x7ffffe4, 27 },
256 /* 0xdf */ { 0x7ffffe5, 27 },
257 /* 0xe0 */ { 0xfffec, 20 },
258 /* 0xe1 */ { 0xfffff3, 24 },
259 /* 0xe2 */ { 0xfffed, 20 },
260 /* 0xe3 */ { 0x1fffe6, 21 },
261 /* 0xe4 */ { 0x3fffe9, 22 },
262 /* 0xe5 */ { 0x1fffe7, 21 },
263 /* 0xe6 */ { 0x1fffe8, 21 },
264 /* 0xe7 */ { 0x7ffff3, 23 },
265 /* 0xe8 */ { 0x3fffea, 22 },
266 /* 0xe9 */ { 0x3fffeb, 22 },
267 /* 0xea */ { 0x1ffffee, 25 },
268 /* 0xeb */ { 0x1ffffef, 25 },
269 /* 0xec */ { 0xfffff4, 24 },
270 /* 0xed */ { 0xfffff5, 24 },
271 /* 0xee */ { 0x3ffffea, 26 },
272 /* 0xef */ { 0x7ffff4, 23 },
273 /* 0xf0 */ { 0x3ffffeb, 26 },
274 /* 0xf1 */ { 0x7ffffe6, 27 },
275 /* 0xf2 */ { 0x3ffffec, 26 },
276 /* 0xf3 */ { 0x3ffffed, 26 },
277 /* 0xf4 */ { 0x7ffffe7, 27 },
278 /* 0xf5 */ { 0x7ffffe8, 27 },
279 /* 0xf6 */ { 0x7ffffe9, 27 },
280 /* 0xf7 */ { 0x7ffffea, 27 },
281 /* 0xf8 */ { 0x7ffffeb, 27 },
282 /* 0xf9 */ { 0xffffffe, 28 },
283 /* 0xfa */ { 0x7ffffec, 27 },
284 /* 0xfb */ { 0x7ffffed, 27 },
285
286 /* 0xfc */ { 0x7ffffee, 27 },
287 /* 0xfd */ { 0x7ffffef, 27 },
288 /* 0xfe */ { 0x7fffff0, 27 },
289 /* 0xff */ { 0x3ffffee, 26 },
290 /* 0x100 */ { 0x3fffffff, 30 },
291 };
292
code_bit(int idx,int bit)293 int code_bit(int idx, int bit)
294 {
295 if (bit < huf_literal[idx].len)
296 return !!(huf_literal[idx].code & (1 << (huf_literal[idx].len - 1 - bit)));
297
298 return -1;
299 }
300
301 #include "huftable.h"
302
303 #define PARALLEL 2
304
305 struct state {
306 int terminal;
307 int state[PARALLEL];
308 int bytepos;
309
310 int real_pos;
311 };
312
313 struct state state[2000];
314 unsigned char terms[2000];
315 int next = 1;
316
lextable_decode(int pos,char c)317 int lextable_decode(int pos, char c)
318 {
319 int q = pos + !!c;
320
321 if (lextable_terms[q >> 3] & (1 << (q & 7))) /* terminal */
322 return lextable[q] | 0x8000;
323
324 return pos + (lextable[q] << 1);
325 }
326
main(void)327 int main(void)
328 {
329 int n = 0;
330 int m = 0;
331 int prev;
332 char c;
333 int walk;
334 int saw;
335 int y;
336 int j;
337 int pos = 0;
338 int biggest = 0;
339 int fails = 0;
340
341 m = 0;
342 while (m < LWS_ARRAY_SIZE(state)) {
343 for (j = 0; j < PARALLEL; j++) {
344 state[m].state[j] = 0xffff;
345 state[m].terminal = 0;
346 }
347 m++;
348 }
349
350 while (n < LWS_ARRAY_SIZE(huf_literal)) {
351
352 m = 0;
353 walk = 0;
354 prev = 0;
355
356 while (m < huf_literal[n].len) {
357
358 saw = 0;
359 if (state[walk].state[code_bit(n, m)] != 0xffff) {
360 /* exists -- go forward */
361 walk = state[walk].state[code_bit(n, m)];
362 goto again;
363 }
364
365 /* something we didn't see before */
366
367 state[walk].state[code_bit(n, m)] = next;
368 walk = next++;
369 again:
370 m++;
371 }
372
373 state[walk].terminal = n++;
374 state[walk].state[0] = 0; /* terminal marker */
375 }
376
377 walk = 0;
378 for (n = 0; n < next; n++) {
379 state[n].bytepos = walk;
380 walk += (2 * 2);
381 }
382
383 /* compute everyone's position first */
384
385 pos = 0;
386 walk = 0;
387 for (n = 0; n < next; n++) {
388
389 state[n].real_pos = pos;
390
391 if (state[n].state[0]) /* nonterminal */
392 pos += 2;
393
394 walk ++;
395 }
396
397 fprintf(stdout, "static unsigned char lextable[] = {\n");
398
399 #define TERMINAL_MASK 0x8000
400
401 walk = 0;
402 pos = 0;
403
404 for (n = 0; n < next; n++) {
405 for (m = 0; m < 2; m++) {
406 saw = state[n].state[m];
407
408 if (saw == 0) { // c is a terminal then
409 m = 2;
410 continue;
411 }
412 if (!m)
413 fprintf(stdout, "/* pos %04x: %3d */ ",
414 state[n].real_pos, n);
415 else
416 fprintf(stdout, " ");
417
418 if (saw == 0xffff) {
419 fprintf(stdout,
420 " 0xff, 0xff, /* 0 = fail */\n ");
421 pos ++; /* fail */
422 fails++;
423 continue;
424 }
425
426 if (state[saw].state[0] == 0) { /* points to terminal */
427 fprintf(stdout, " /* terminal %d */ 0x%02X,\n",
428 state[saw].terminal,
429 state[saw].terminal & 0xff);
430 terms[(state[n].real_pos + m) >> 3] |=
431 1 << ((state[n].real_pos + m) & 7);
432 pos++;
433 walk++;
434 continue;
435 }
436
437 j = (state[saw].real_pos - q) >> 1;
438
439 if (j > biggest)
440 biggest = j;
441
442 if (j > 0xffff) {
443 fprintf(stderr,
444 "Jump > 64K bytes ahead (%d to %d)\n",
445 state[n].real_pos, state[saw].real_pos);
446 return 1;
447 }
448
449 fprintf(stdout, " /* %d */ 0x%02X "
450 "/* (to 0x%04X state %3d) */,\n",
451 m,
452 j & 0xff,
453 state[saw].real_pos, saw);
454 pos++;
455
456 walk++;
457 }
458 }
459
460 fprintf(stdout, "/* total size %d bytes, biggest jump %d/256, fails=%d */\n};\n"
461 "\n static unsigned char lextable_terms[] = {\n",
462 pos, biggest, fails);
463
464 for (n = 0; n < (walk + 7) / 8; n++) {
465 if (!(n & 7))
466 fprintf(stdout, "\n\t");
467 fprintf(stdout, "0x%02x, ", terms[n]);
468 }
469 fprintf(stdout, "\n};\n");
470
471 /*
472 * Try to parse every legal input string
473 */
474
475 for (n = 0; n < LWS_ARRAY_SIZE(huf_literal); n++) {
476 walk = 0;
477 m = 0;
478 y = -1;
479
480 fprintf(stderr, " trying %d\n", n);
481
482 while (m < huf_literal[n].len) {
483 prev = walk;
484 walk = lextable_decode(walk, code_bit(n, m));
485
486 if (walk == 0xffff) {
487 fprintf(stderr, "failed\n");
488 return 3;
489 }
490
491 if (walk & 0x8000) {
492 y = walk & 0x7fff;
493 if (y == 0 && m == 29) {
494 y |= 0x100;
495 fprintf(stdout,
496 "\n/* state that points to "
497 "0x100 for disambiguation with "
498 "0x0 */\n"
499 "#define HUFTABLE_0x100_PREV "
500 "%d\n", prev);
501 }
502 break;
503 }
504 m++;
505 }
506
507 if (y != n) {
508 fprintf(stderr, "decode failed %d got %d (0x%x)\n", n, y, y);
509 return 4;
510 }
511 }
512
513 fprintf(stderr, "All decode OK\n");
514
515 return 0;
516 }
517