text: /*
   * minilex.c
   *
   * High efficiency lexical state parser
   *
   * Copyright (C)2011-2014 Andy Green <andy@warmcat.com>
   *
   * Licensed under LGPL2
   *
   * Usage: gcc minilex.c -o minilex && ./minilex > lextable.h
   *
   * Run it twice to test parsing on the generated table on stderr
   */
  
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  /* set of parsable strings -- ALL LOWER CASE */
  
  const char *set[] = {
  	"get ",
  	"post ",
  	"options ",
  	"host:",
  	"connection:",
  	"sec-websocket-key1:",
  	"sec-websocket-key2:",
  	"sec-websocket-protocol:",
  	"upgrade:",
  	"origin:",
  	"sec-websocket-draft:",
  	"\x0d\x0a",
  
  	"sec-websocket-key:",
  	"sec-websocket-version:",
  	"sec-websocket-origin:",
  
  	"sec-websocket-extensions:",
  
  	"sec-websocket-accept:",
  	"sec-websocket-nonce:",
  	"http/1.1 ",
  
  	"accept:",
  	"access-control-request-headers:",
  	"if-modified-since:",
  	"if-none-match:",
  	"accept-encoding:",
  	"accept-language:",
  	"pragma:",
  	"cache-control:",
  	"authorization:",
  	"cookie:",
  	"content-length:",
  	"content-type:",
  	"date:",
  	"range:",
  	"referer:",
  	"", /* not matchable */
  
  };
  
  /*
   * b7 = 0 = 1-byte seq
   *	    0x08 = fail
   *	    2-byte seq
   *          0x00 - 0x07, then terminal as given in 2nd byte
  	    3-byte seq
   *          no match: go fwd 3 byte, match: jump fwd by amt in +1/+2 bytes
   *    = 1 = 1-byte seq
   *          no match: die, match go fwd 1 byte
   */
  
  unsigned char lextable[] = {
  	#include "lextable.h"
  };
  
  #define PARALLEL 30
  
  struct state {
  	char c[PARALLEL];
  	int state[PARALLEL];
  	int count;
  	int bytepos;
  
  	int real_pos;
  };
  
  struct state state[1000];
  int next = 1;
  
  #define FAIL_CHAR 0x08
  
  int lextable_decode(int pos, char c)
  {
  
  	while (1) {
  		if (lextable[pos] & (1 << 7)) { /* 1-byte, fail on mismatch */
  			if ((lextable[pos] & 0x7f) != c)
  				return -1;
  			/* fall thru */
  			pos++;
  			if (lextable[pos] == FAIL_CHAR)
  				return -1;
  			return pos;
  		} else { /* b7 = 0, end or 3-byte */
  			if (lextable[pos] < FAIL_CHAR) /* terminal marker */
  				return pos;
  
  			if (lextable[pos] == c) /* goto */
  				return pos + (lextable[pos + 1]) +
  						(lextable[pos + 2] << 8);
  			/* fall thru goto */
  			pos += 3;
  			/* continue */
  		}
  	}
  }
  
  int main(void)
  {
  	int n = 0;
  	int m = 0;
  	int prev;
  	char c;
  	int walk;
  	int saw;
  	int y;
  	int j;
  	int pos = 0;
  
  	while (n < sizeof(set) / sizeof(set[0])) {
  
  		m = 0;
  		walk = 0;
  		prev = 0;
  
  		if (set[n][0] == '\0') {
  			n++;
  			continue;
  		}
  
  		while (set[n][m]) {
  
  			saw = 0;
  			for (y = 0; y < state[walk].count; y++)
  				if (state[walk].c[y] == set[n][m]) {
  					/* exists -- go forward */
  					walk = state[walk].state[y];
  					saw = 1;
  					break;
  				}
  
  			if (saw)
  				goto again;
  
  			/* something we didn't see before */
  
  			state[walk].c[state[walk].count] = set[n][m];
  
  			state[walk].state[state[walk].count] = next;
  			state[walk].count++;
  			walk = next++;
  again:
  			m++;
  		}
  
  		state[walk].c[0] = n++;
  		state[walk].state[0] = 0; /* terminal marker */
  		state[walk].count = 1;
  	}
  
  	walk = 0;
  	for (n = 0; n < next; n++) {
  		state[n].bytepos = walk;
  		walk += (2 * state[n].count);
  	}
  
  	/* compute everyone's position first */
  
  	pos = 0;
  	walk = 0;
  	for (n = 0; n < next; n++) {
  
  		state[n].real_pos = pos;
  
  		for (m = 0; m < state[n].count; m++) {
  
  			if (state[n].state[m] == 0)
  				pos += 2; /* terminal marker */
  			else { /* c is a character */
  				if ((state[state[n].state[m]].bytepos -
  								walk) == 2)
  					pos++;
  				else {
  					pos += 3;
  					if (m == state[n].count - 1)
  						pos++; /* fail */
  				}
  			}
  			walk += 2;
  		}
  	}
  
  	walk = 0;
  	pos = 0;
  	for (n = 0; n < next; n++) {
  		for (m = 0; m < state[n].count; m++) {
  
  			if (!m)
  				fprintf(stdout, "/* pos %04x: %3d */ ",
  							  state[n].real_pos, n);
  			else
  				fprintf(stdout, "                    ");
  
  			y = state[n].c[m];
  			saw = state[n].state[m];
  
  			if (saw == 0) { // c is a terminal then
  
  				if (y > 0x7ff) {
  					fprintf(stderr, "terminal too big\n");
  					return 2;
  				}
  
  				fprintf(stdout, "   0x%02X, 0x%02X           "
  					"       "
  					"/* - terminal marker %2d - */,\n",
  						    y >> 8, y & 0xff, y & 0x7f);
  				pos += 2;
  				walk += 2;
  				continue;
  			}
  
  			/* c is a character */
  
  			prev = y &0x7f;
  			if (prev < 32 || prev > 126)
  				prev = '.';
  
  
  			if ((state[saw].bytepos - walk) == 2) {
  				fprintf(stdout, "   0x%02X /* '%c' -> */,\n",
  						y | 0x80, prev);
  				pos++;
  				walk += 2;
  				continue;
  			}
  
  			j = state[saw].real_pos - pos;
  
  			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, "   0x%02X /* '%c' */, 0x%02X, 0x%02X  "
  				"/* (to 0x%04X state %3d) */,\n",
  				y, prev,
  				j & 0xff, j >> 8,
  				state[saw].real_pos, saw);
  			pos += 3;
  
  			if (m == state[n].count - 1) {
  				fprintf(stdout,
  				  "                       0x%02X, /* fail */\n",
  								FAIL_CHAR);
  				pos++; /* fail */
  			}
  
  			walk += 2;
  		}
  	}
  
  	fprintf(stdout, "/* total size %d bytes */\n", pos);
  
  	/*
  	 * Try to parse every legal input string
  	 */
  
  	for (n = 0; n < sizeof(set) / sizeof(set[0]); n++) {
  		walk = 0;
  		m = 0;
  		y = -1;
  
  		if (set[n][0] == '\0')
  			continue;
  
  		fprintf(stderr, "  trying '%s'\n", set[n]);
  
  		while (set[n][m]) {
  			walk = lextable_decode(walk, set[n][m]);
  			if (walk < 0) {
  				fprintf(stderr, "failed\n");
  				return 3;
  			}
  
  			if (lextable[walk] < FAIL_CHAR) {
  				y = (lextable[walk] << 8) + lextable[walk + 1];
  				break;
  			}
  			m++;
  		}
  
  		if (y != n) {
  			fprintf(stderr, "decode failed %d\n", y);
  			return 4;
  		}
  	}
  
  	fprintf(stderr, "All decode OK\n");
  
  	return 0;
  }
  