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