lib/minilex.c

   1 /*
   2  * minilex.c
   3  *
   4  * High efficiency lexical state parser
   5  *
   6  * Copyright (C)2011-2013 Andy Green <andy@warmcat.com>
   7  *
   8  * Licensed under LGPL2
   9  *
  10  * Usage: gcc minilex.c -o minilex && ./minilex > lextable.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 /* set of parsable strings -- ALL LOWER CASE */
  20
  21 const char *set[] = {
  22         "get ",
  23         "post ",
  24         "host:",
  25         "connection:",
  26         "sec-websocket-key1:",
  27         "sec-websocket-key2:",
  28         "sec-websocket-protocol:",
  29         "upgrade:",
  30         "origin:",
  31         "sec-websocket-draft:",
  32         "\x0d\x0a",
  33
  34         "sec-websocket-key:",
  35         "sec-websocket-version:",
  36         "sec-websocket-origin:",
  37
  38         "sec-websocket-extensions:",
  39
  40         "sec-websocket-accept:",
  41         "sec-websocket-nonce:",
  42         "http/1.1 ",
  43
  44         "accept:",
  45         "if-modified-since:",
  46         "accept-encoding:",
  47         "accept-language:",
  48         "pragma:",
  49         "cache-control:",
  50         "authorization:",
  51         "cookie:",
  52         "content-length:",
  53         "content-type:",
  54         "date:",
  55         "range:",
  56         "referer:",
  57         "", /* not matchable */
  58
  59 };
  60
  61 unsigned char lextable[] = {
  62         #include "lextable.h"
  63 };
  64
  65 #define PARALLEL 30
  66
  67 struct state {
  68         char c[PARALLEL];
  69         int state[PARALLEL];
  70         int count;
  71         int bytepos;
  72 };
  73
  74 struct state state[1000];
  75 int next = 1;
  76
  77
  78 int lextable_decode(int pos, char c)
  79 {
  80         while (1) {
  81                 if (!lextable[pos + 1]) /* terminal marker */
  82                         return pos;
  83
  84                 if ((lextable[pos] & 0x7f) == c) /* goto */
  85                         return pos + (lextable[pos + 1] << 1);
  86
  87                 if (lextable[pos] & 0x80) /* fail */
  88                         return -1;
  89
  90                 pos += 2;
  91         }
  92 }
  93
  94
  95 int main(void)
  96 {
  97         int n = 0;
  98         int m = 0;
  99         int prev;
 100         char c;
 101         int walk;
 102         int saw;
 103         int y;
 104
 105         while (n < sizeof(set) / sizeof(set[0])) {
 106
 107                 m = 0;
 108                 walk = 0;
 109                 prev = 0;
 110
 111                 if (set[n][0] == '\0') {
 112                         n++;
 113                         continue;
 114                 }
 115
 116                 while (set[n][m]) {
 117
 118                         saw = 0;
 119                         for (y = 0; y < state[walk].count; y++)
 120                                 if (state[walk].c[y] == set[n][m]) {
 121                                         /* exists -- go forward */
 122                                         walk = state[walk].state[y];
 123                                         saw = 1;
 124                                         break;
 125                                 }
 126
 127                         if (saw)
 128                                 goto again;
 129
 130                         /* something we didn't see before */
 131
 132                         state[walk].c[state[walk].count] = set[n][m];
 133
 134                         state[walk].state[state[walk].count] = next;
 135                         state[walk].count++;
 136                         walk = next++;
 137 again:
 138                         m++;
 139                 }
 140
 141                 state[walk].c[0] = n++;
 142                 state[walk].state[0] = 0; /* terminal marker */
 143                 state[walk].count = 1;
 144         }
 145
 146         walk = 0;
 147         for (n = 0; n < next; n++) {
 148                 state[n].bytepos = walk;
 149                 walk += (2 * state[n].count);
 150         }
 151
 152         walk = 0;
 153         for (n = 0; n < next; n++) {
 154                 for (m = 0; m < state[n].count; m++) {
 155
 156                         if (!m)
 157                                 fprintf(stdout, "/* pos %3d: state %3d */ ",
 158                                                                       walk, n);
 159                         else
 160                                 fprintf(stdout, "                         ");
 161
 162                         y = state[n].c[m];
 163                         saw = state[n].state[m];
 164
 165                         if (m == state[n].count - 1)
 166                                 y |= 0x80; /* last option */
 167
 168                         if (saw == 0) // c is a terminal then
 169                                 fprintf(stdout, "   0x%02X, 0x00            "
 170                                         "/* - terminal marker %2d - */, \n",
 171                                                                   y, y - 0x80);
 172                         else { /* c is a character and we need a byte delta */
 173                                 if ((state[saw].bytepos - walk) / 2 > 0xff) {
 174                                         fprintf(stdout,
 175                                           "Tried to jump > 510 bytes ahead\n");
 176                                         return 1;
 177                                 }
 178                                 prev = y &0x7f;
 179                                 if (prev < 32 || prev > 126)
 180                                         prev = '.';
 181                                 fprintf(stdout, "   0x%02X /* '%c' */, 0x%02X  "
 182                                         "/* (to pos %3d state %3d) */,\n",
 183                                         y, prev,
 184                                         (state[saw].bytepos - walk) / 2,
 185                                         state[saw].bytepos, saw);
 186                         }
 187                         walk += 2;
 188                 }
 189         }
 190
 191         fprintf(stdout, "/* total size %d bytes */\n", walk);
 192
 193         /*
 194          * Test parser... real parser code is the same
 195          */
 196
 197         for (n = 0; n < sizeof(set) / sizeof(set[0]); n++) {
 198                 walk = 0;
 199                 m = 0;
 200
 201                 if (set[n][0] == '\0')
 202                         continue;
 203
 204                 fprintf(stderr, "Trying '%s'\n", set[n]);
 205
 206                 while (set[n][m]) {
 207                         walk = lextable_decode(walk, set[n][m]);
 208                         if (walk < 0) {
 209                                 fprintf(stderr, "failed\n");
 210                                 break;
 211                         }
 212                         if (lextable[walk + 1] == 0) {
 213                                 fprintf(stderr, "decode: %d\n",
 214                                                 lextable[walk] & 0x7f);
 215                                 break;
 216                         }
 217                         m++;
 218                 }
 219         }
 220
 221         return 0;
 222 }