lib/minihuf.c

/*
 * minilex.c
 *
 * High efficiency lexical state parser
 *
 * Copyright (C)2011-2014 Andy Green <andy@warmcat.com>
 *
 * Licensed under LGPL2
 *
 * Usage: gcc minihuf.c -o minihuf && ./minihuf > huftable.h
 *
 * Run it twice to test parsing on the generated table on stderr
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAY_SIZE(n) (sizeof(n) / sizeof(n[0]))

struct huf {
	unsigned int code;
	unsigned char len;
};

static struct huf huf_literal[] = {
	/* 0x00 */ { 0x1ff8, 13 },
	/* 0x01 */ { 0x7fffd8, 23 },
	/* 0x02 */ { 0xfffffe2, 28 },
	/* 0x03 */ { 0xfffffe3, 28 },
	/* 0x04 */ { 0xfffffe4, 28 },
	/* 0x05 */ { 0xfffffe5, 28 },
	/* 0x06 */ { 0xfffffe6, 28 },
	/* 0x07 */ { 0xfffffe7, 28 },
	/* 0x08 */ { 0xfffffe8, 28 },
	/* 0x09 */ { 0xffffea, 24 },
	/* 0x0a */ { 0x3ffffffc, 30 },
	/* 0x0b */ { 0xfffffe9, 28 },
	
	/* 0x0c */ { 0xfffffea, 28 },
	/* 0x0d */ { 0x3ffffffd, 30 },
	/* 0x0e */ { 0xfffffeb, 28 },
	/* 0x0f */ { 0xfffffec, 28 },
	/* 0x10 */ { 0xfffffed, 28 },
	/* 0x11 */ { 0xfffffee, 28 },
	/* 0x12 */ { 0xfffffef, 28 },
	/* 0x13 */ { 0xffffff0, 28 },
	/* 0x14 */ { 0xffffff1, 28 },
	/* 0x15 */ { 0xffffff2, 28 },
	/* 0x16 */ { 0x3ffffffe, 30 },
	/* 0x17 */ { 0xffffff3, 28 },
	/* 0x18 */ { 0xffffff4, 28 },
	/* 0x19 */ { 0xffffff5, 28 },
	/* 0x1a */ { 0xffffff6, 28 },
	/* 0x1b */ { 0xffffff7, 28 },
	/* 0x1c */ { 0xffffff8, 28 },
	/* 0x1d */ { 0xffffff9, 28 },
	/* 0x1e */ { 0xffffffa, 28 },
	/* 0x1f */ { 0xffffffb, 28 },
	/* 0x20 */ { 0x14, 6 },
	/* 0x21 */ { 0x3f8, 10 },
	/* 0x22 */ { 0x3f9, 10 },
	/* 0x23 */ { 0xffa, 12 },
	/* 0x24 */ { 0x1ff9, 13 },
	/* 0x25 */ { 0x15, 6 },
	/* 0x26 */ { 0xf8, 8 },
	/* 0x27 */ { 0x7fa, 11 },
	/* 0x28 */ { 0x3fa, 10 },
	/* 0x29 */ { 0x3fb, 10 },
	/* 0x2a */ { 0xf9, 8 },
	/* 0x2b */ { 0x7fb, 11 },
	/* 0x2c */ { 0xfa, 8 },
	/* 0x2d */ { 0x16, 6 },
	/* 0x2e */ { 0x17, 6 },
	/* 0x2f */ { 0x18, 6 },
	/* 0x30 */ { 0x0, 5 },
	/* 0x31 */ { 0x1, 5 },
	/* 0x32 */ { 0x2, 5 },
	/* 0x33 */ { 0x19, 6 },
	/* 0x34 */ { 0x1a, 6 },
	/* 0x35 */ { 0x1b, 6 },
	/* 0x36 */ { 0x1c, 6 },
	/* 0x37 */ { 0x1d, 6 },
	/* 0x38 */ { 0x1e, 6 },
	/* 0x39 */ { 0x1f, 6 },
	/* 0x3a */ { 0x5c, 7 },
	/* 0x3b */ { 0xfb, 8 },
	
	/* 0x3c */ { 0x7ffc, 15 },
	/* 0x3d */ { 0x20, 6 },
	/* 0x3e */ { 0xffb, 12 },
	/* 0x3f */ { 0x3fc, 10 },
	/* 0x40 */ { 0x1ffa, 13 },
	/* 0x41 */ { 0x21, 6 },
	/* 0x42 */ { 0x5d, 7 },
	/* 0x43 */ { 0x5e, 7 },
	/* 0x44 */ { 0x5f, 7 },
	/* 0x45 */ { 0x60, 7 },
	/* 0x46 */ { 0x61, 7 },
	/* 0x47 */ { 0x62, 7 },
	/* 0x48 */ { 0x63, 7 },
	/* 0x49 */ { 0x64, 7 },
	/* 0x4a */ { 0x65, 7 },
	/* 0x4b */ { 0x66, 7 },
	/* 0x4c */ { 0x67, 7 },
	/* 0x4d */ { 0x68, 7 },
	/* 0x4e */ { 0x69, 7 },
	/* 0x4f */ { 0x6a, 7 },
	/* 0x50 */ { 0x6b, 7 },
	/* 0x51 */ { 0x6c, 7 },
	/* 0x52 */ { 0x6d, 7 },
	/* 0x53 */ { 0x6e, 7 },
	/* 0x54 */ { 0x6f, 7 },
	/* 0x55 */ { 0x70, 7 },
	/* 0x56 */ { 0x71, 7 },
	/* 0x57 */ { 0x72, 7 },
	/* 0x58 */ { 0xfc, 8 },
	/* 0x59 */ { 0x73, 7 },
	/* 0x5a */ { 0xfd, 8 },
	/* 0x5b */ { 0x1ffb, 13 },
	/* 0x5c */ { 0x7fff0, 19 },
	/* 0x5d */ { 0x1ffc, 13 },
	/* 0x5e */ { 0x3ffc, 14 },
	/* 0x5f */ { 0x22, 6 },
	/* 0x60 */ { 0x7ffd, 15 },
	/* 0x61 */ { 0x3, 5 },
	/* 0x62 */ { 0x23, 6 },
	/* 0x63 */ { 0x4, 5 },
	/* 0x64 */ { 0x24, 6 },
	/* 0x65 */ { 0x5, 5 },
	/* 0x66 */ { 0x25, 6 },
	/* 0x67 */ { 0x26, 6 },
	/* 0x68 */ { 0x27, 6 },
	/* 0x69 */ { 0x6, 5 },
	/* 0x6a */ { 0x74, 7 },
	/* 0x6b */ { 0x75, 7 },
	

	/* 0x6c */ { 0x28, 6 },
	/* 0x6d */ { 0x29, 6 },
	/* 0x6e */ { 0x2a, 6 },
	/* 0x6f */ { 0x7, 5 },
	/* 0x70 */ { 0x2b, 6 },
	/* 0x71 */ { 0x76, 7 },
	/* 0x72 */ { 0x2c, 6 },
	/* 0x73 */ { 0x8, 5 },
	/* 0x74 */ { 0x9, 5 },
	/* 0x75 */ { 0x2d, 6 },
	/* 0x76 */ { 0x77, 7 },
	/* 0x77 */ { 0x78, 7 },
	/* 0x78 */ { 0x79, 7 },
	/* 0x79 */ { 0x7a, 7 },
	/* 0x7a */ { 0x7b, 7 },
	/* 0x7b */ { 0x7ffe, 15 },
	/* 0x7c */ { 0x7fc, 11 },
	/* 0x7d */ { 0x3ffd, 14 },
	/* 0x7e */ { 0x1ffd, 13 },
	/* 0x7f */ { 0xffffffc, 28 },
	/* 0x80 */ { 0xfffe6, 20 },
	/* 0x81 */ { 0x3fffd2, 22 },
	/* 0x82 */ { 0xfffe7, 20 },
	/* 0x83 */ { 0xfffe8, 20 },
	/* 0x84 */ { 0x3fffd3, 22 },
	/* 0x85 */ { 0x3fffd4, 22 },
	/* 0x86 */ { 0x3fffd5, 22 },
	/* 0x87 */ { 0x7fffd9, 23 },
	/* 0x88 */ { 0x3fffd6, 22 },
	/* 0x89 */ { 0x7fffda, 23 },
	/* 0x8a */ { 0x7fffdb, 23 },
	/* 0x8b */ { 0x7fffdc, 23 },
	/* 0x8c */ { 0x7fffdd, 23 },
	/* 0x8d */ { 0x7fffde, 23 },
	/* 0x8e */ { 0xffffeb, 24 },
	/* 0x8f */ { 0x7fffdf, 23 },
	/* 0x90 */ { 0xffffec, 24 },
	/* 0x91 */ { 0xffffed, 24 },
	/* 0x92 */ { 0x3fffd7, 22 },
	/* 0x93 */ { 0x7fffe0, 23 },
	/* 0x94 */ { 0xffffee, 24 },
	/* 0x95 */ { 0x7fffe1, 23 },
	/* 0x96 */ { 0x7fffe2, 23 },
	/* 0x97 */ { 0x7fffe3, 23 },
	/* 0x98 */ { 0x7fffe4, 23 },
	/* 0x99 */ { 0x1fffdc, 21 },
	/* 0x9a */ { 0x3fffd8, 22 },
	/* 0x9b */ { 0x7fffe5, 23 },
	
	/* 0x9c */ { 0x3fffd9, 22 },
	/* 0x9d */ { 0x7fffe6, 23 },
	/* 0x9e */ { 0x7fffe7, 23 },
	/* 0x9f */ { 0xffffef, 24 },
	/* 0xa0 */ { 0x3fffda, 22 },
	/* 0xa1 */ { 0x1fffdd, 21 },
	/* 0xa2 */ { 0xfffe9, 20 },
	/* 0xa3 */ { 0x3fffdb, 22 },
	/* 0xa4 */ { 0x3fffdc, 22 },
	/* 0xa5 */ { 0x7fffe8, 23 },
	/* 0xa6 */ { 0x7fffe9, 23 },
	/* 0xa7 */ { 0x1fffde, 21 },
	/* 0xa8 */ { 0x7fffea, 23 },
	/* 0xa9 */ { 0x3fffdd, 22 },
	/* 0xaa */ { 0x3fffde, 22 },
	/* 0xab */ { 0xfffff0, 24 },
	/* 0xac */ { 0x1fffdf, 21 },
	/* 0xad */ { 0x3fffdf, 22 },
	/* 0xae */ { 0x7fffeb, 23 },
	/* 0xaf */ { 0x7fffec, 23 },
	/* 0xb0 */ { 0x1fffe0, 21 },
	/* 0xb1 */ { 0x1fffe1, 21 },
	/* 0xb2 */ { 0x3fffe0, 22 },
	/* 0xb3 */ { 0x1fffe2, 21 },
	/* 0xb4 */ { 0x7fffed, 23 },
	/* 0xb5 */ { 0x3fffe1, 22 },
	/* 0xb6 */ { 0x7fffee, 23 },
	/* 0xb7 */ { 0x7fffef, 23 },
	/* 0xb8 */ { 0xfffea, 20 },
	/* 0xb9 */ { 0x3fffe2, 22 },
	/* 0xba */ { 0x3fffe3, 22 },
	/* 0xbb */ { 0x3fffe4, 22 },
	/* 0xbc */ { 0x7ffff0, 23 },
	/* 0xbd */ { 0x3fffe5, 22 },
	/* 0xbe */ { 0x3fffe6, 22 },
	/* 0xbf */ { 0x7ffff1, 23 },
	/* 0xc0 */ { 0x3ffffe0, 26 },
	/* 0xc1 */ { 0x3ffffe1, 26 },
	/* 0xc2 */ { 0xfffeb, 20 },
	/* 0xc3 */ { 0x7fff1, 19 },
	/* 0xc4 */ { 0x3fffe7, 22 },
	/* 0xc5 */ { 0x7ffff2, 23 },
	/* 0xc6 */ { 0x3fffe8, 22 },
	/* 0xc7 */ { 0x1ffffec, 25 },
	/* 0xc8 */ { 0x3ffffe2, 26 },
	/* 0xc9 */ { 0x3ffffe3, 26 },
	/* 0xca */ { 0x3ffffe4, 26 },
	/* 0xcb */ { 0x7ffffde, 27 },
	
	/* 0xcc */ { 0x7ffffdf, 27 },
	/* 0xcd */ { 0x3ffffe5, 26 },
	/* 0xce */ { 0xfffff1, 24 },
	/* 0xcf */ { 0x1ffffed, 25 },
	/* 0xd0 */ { 0x7fff2, 19 },
	/* 0xd1 */ { 0x1fffe3, 21 },
	/* 0xd2 */ { 0x3ffffe6, 26 },
	/* 0xd3 */ { 0x7ffffe0, 27 },
	/* 0xd4 */ { 0x7ffffe1, 27 },
	/* 0xd5 */ { 0x3ffffe7, 26 },
	/* 0xd6 */ { 0x7ffffe2, 27 },
	/* 0xd7 */ { 0xfffff2, 24 },
	/* 0xd8 */ { 0x1fffe4, 21 },
	/* 0xd9 */ { 0x1fffe5, 21 },
	/* 0xda */ { 0x3ffffe8, 26 },
	/* 0xdb */ { 0x3ffffe9, 26 },
	/* 0xdc */ { 0xffffffd, 28 },
	/* 0xdd */ { 0x7ffffe3, 27 },
	/* 0xde */ { 0x7ffffe4, 27 },
	/* 0xdf */ { 0x7ffffe5, 27 },
	/* 0xe0 */ { 0xfffec, 20 },
	/* 0xe1 */ { 0xfffff3, 24 },
	/* 0xe2 */ { 0xfffed, 20 },
	/* 0xe3 */ { 0x1fffe6, 21 },
	/* 0xe4 */ { 0x3fffe9, 22 },
	/* 0xe5 */ { 0x1fffe7, 21 },
	/* 0xe6 */ { 0x1fffe8, 21 },
	/* 0xe7 */ { 0x7ffff3, 23 },
	/* 0xe8 */ { 0x3fffea, 22 },
	/* 0xe9 */ { 0x3fffeb, 22 },
	/* 0xea */ { 0x1ffffee, 25 },
	/* 0xeb */ { 0x1ffffef, 25 },
	/* 0xec */ { 0xfffff4, 24 },
	/* 0xed */ { 0xfffff5, 24 },
	/* 0xee */ { 0x3ffffea, 26 },
	/* 0xef */ { 0x7ffff4, 23 },
	/* 0xf0 */ { 0x3ffffeb, 26 },
	/* 0xf1 */ { 0x7ffffe6, 27 },
	/* 0xf2 */ { 0x3ffffec, 26 },
	/* 0xf3 */ { 0x3ffffed, 26 },
	/* 0xf4 */ { 0x7ffffe7, 27 },
	/* 0xf5 */ { 0x7ffffe8, 27 },
	/* 0xf6 */ { 0x7ffffe9, 27 },
	/* 0xf7 */ { 0x7ffffea, 27 },
	/* 0xf8 */ { 0x7ffffeb, 27 },
	/* 0xf9 */ { 0xffffffe, 28 },
	/* 0xfa */ { 0x7ffffec, 27 },
	/* 0xfb */ { 0x7ffffed, 27 },
	
	/* 0xfc */ { 0x7ffffee, 27 },
	/* 0xfd */ { 0x7ffffef, 27 },
	/* 0xfe */ { 0x7fffff0, 27 },
	/* 0xff */ { 0x3ffffee, 26 },
	/* 0x100 */ { 0x3fffffff, 30 },
};

int code_bit(int idx, int bit)
{
	if (bit < huf_literal[idx].len)
		return !!(huf_literal[idx].code & (1 << (huf_literal[idx].len - 1 - bit)));

	return -1;
}

#include "huftable.h"

#define PARALLEL 2

struct state {
	int terminal;
	int state[PARALLEL];
	int bytepos;

	int real_pos;
};

struct state state[2000];
unsigned char terms[2000];
int next = 1;

int lextable_decode(int pos, char c)
{
	int q = pos + !!c;

	if (lextable_terms[q >> 3] & (1 << (q & 7))) /* terminal */
		return lextable[q] | 0x8000;

	return pos + (lextable[q] << 1);
}

int main(void)
{
	int n = 0;
	int m = 0;
	int prev;
	char c;
	int walk;
	int saw;
	int y;
	int j;
	int q;
	int pos = 0;
	int biggest = 0;
	int fails = 0;
	
	m = 0;
	while (m < ARRAY_SIZE(state)) {
		for (j = 0; j < PARALLEL; j++) {
			state[m].state[j] = 0xffff;
			state[m].terminal = 0;
		}
		m++;
	}

	while (n < ARRAY_SIZE(huf_literal)) {

		m = 0;
		walk = 0;
		prev = 0;

		while (m < huf_literal[n].len) {

			saw = 0;
			if (state[walk].state[code_bit(n, m)] != 0xffff) {
				/* exists -- go forward */
				walk = state[walk].state[code_bit(n, m)];
				goto again;
			}

			/* something we didn't see before */

			state[walk].state[code_bit(n, m)] = next;
			walk = next++;
again:
			m++;
		}

		state[walk].terminal = n++;
		state[walk].state[0] = 0; /* terminal marker */
	}

	walk = 0;
	for (n = 0; n < next; n++) {
		state[n].bytepos = walk;
		walk += (2 * 2);
	}

	/* compute everyone's position first */

	pos = 0;
	walk = 0;
	for (n = 0; n < next; n++) {

		state[n].real_pos = pos;

		if (state[n].state[0]) /* nonterminal */
			pos += 2;
				
		walk ++;
	}
	
	fprintf(stdout, "static unsigned char lextable[] = {\n");

#define TERMINAL_MASK 0x8000
	
	walk = 0;
	pos = 0;
	q = 0;
	for (n = 0; n < next; n++) {
		q = pos;
		for (m = 0; m < 2; m++) {
			saw = state[n].state[m];

			if (saw == 0) { // c is a terminal then
				m = 2;
				continue;
			}
			if (!m)
				fprintf(stdout, "/* pos %04x: %3d */ ",
							  state[n].real_pos, n);
			else
				fprintf(stdout, "                    ");

			if (saw == 0xffff) {
				fprintf(stdout,
				  "   0xff, 0xff, /* 0 = fail */\n                    ");
				pos ++; /* fail */
				fails++;
				continue;
			}

			if (state[saw].state[0] == 0) { /* points to terminal */
				fprintf(stdout, "    /* terminal %d */ 0x%02X,\n",
					state[saw].terminal,
					state[saw].terminal & 0xff);
				terms[(state[n].real_pos + m) >> 3] |=
					1 << ((state[n].real_pos + m) & 7);
				pos++;
				walk++;
				continue;
			}
			
			j = (state[saw].real_pos - q) >> 1;
			
			if (j > biggest)
				biggest = j;

			if (j > 0xffff) {
				fprintf(stderr,
				  "Jump > 64K bytes ahead (%d to %d)\n",
					state[n].real_pos, state[saw].real_pos);
				return 1;
			}
			
			fprintf(stdout, "   /* %d */ 0x%02X  "
				"/* (to 0x%04X state %3d) */,\n",
				m,
				j & 0xff,
				state[saw].real_pos, saw);
			pos++;

			walk++;
		}
	}

	fprintf(stdout, "/* total size %d bytes, biggest jump %d/256, fails=%d */\n};\n"
			"\n static unsigned char lextable_terms[] = {\n",
	 		pos, biggest, fails);

	for (n = 0; n < (walk + 7) / 8; n++) {
		if (!(n & 7))
			fprintf(stdout, "\n\t");
		fprintf(stdout, "0x%02x, ", terms[n]);
	}
	fprintf(stdout, "\n};\n");
	
	/*
	 * Try to parse every legal input string
	 */

	for (n = 0; n < ARRAY_SIZE(huf_literal); n++) {
		walk = 0;
		m = 0;
		y = -1;

		fprintf(stderr, "  trying %d\n", n);

		while (m < huf_literal[n].len) {
			prev = walk;
			walk = lextable_decode(walk, code_bit(n, m));

			if (walk == 0xffff) {
				fprintf(stderr, "failed\n");
				return 3;
			}

			if (walk & 0x8000) {
				y = walk & 0x7fff;
				if (y == 0 && m == 29) {
					y |= 0x100;
					fprintf(stdout, 
						"\n/* state that points to "
						"0x100 for disambiguation with "
						"0x0 */\n"
						"#define HUFTABLE_0x100_PREV "
						"%d\n", prev);
				}
				break;
			}
			m++;
		}

		if (y != n) {
			fprintf(stderr, "decode failed %d got %d (0x%x)\n", n, y, y);
			return 4;
		}
	}

	fprintf(stderr, "All decode OK\n");

	return 0;
}