lib/minilex.c

   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 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         "options ",
  25         "host:",
  26         "connection:",
  27         "sec-websocket-key1:",
  28         "sec-websocket-key2:",
  29         "sec-websocket-protocol:",
  30         "upgrade:",
  31         "origin:",
  32         "sec-websocket-draft:",
  33         "\x0d\x0a",
  34
  35         "sec-websocket-key:",
  36         "sec-websocket-version:",
  37         "sec-websocket-origin:",
  38
  39         "sec-websocket-extensions:",
  40
  41         "sec-websocket-accept:",
  42         "sec-websocket-nonce:",
  43         "http/1.1 ",
  44
  45         "accept:",
  46         "access-control-request-headers:",
  47         "if-modified-since:",
  48         "if-none-match:",
  49         "accept-encoding:",
  50         "accept-language:",
  51         "pragma:",
  52         "cache-control:",
  53         "authorization:",
  54         "cookie:",
  55         "content-length:",
  56         "content-type:",
  57         "date:",
  58         "range:",
  59         "referer:",
  60         "", /* not matchable */
  61
  62 };
  63
  64 /*
  65  * b7 = 0 = 1-byte seq
  66  *          0x08 = fail
  67  *          2-byte seq
  68  *          0x00 - 0x07, then terminal as given in 2nd byte
  69             3-byte seq
  70  *          no match: go fwd 3 byte, match: jump fwd by amt in +1/+2 bytes
  71  *    = 1 = 1-byte seq
  72  *          no match: die, match go fwd 1 byte
  73  */
  74
  75 unsigned char lextable[] = {
  76         #include "lextable.h"
  77 };
  78
  79 #define PARALLEL 30
  80
  81 struct state {
  82         char c[PARALLEL];
  83         int state[PARALLEL];
  84         int count;
  85         int bytepos;
  86
  87         int real_pos;
  88 };
  89
  90 struct state state[1000];
  91 int next = 1;
  92
  93 #define FAIL_CHAR 0x08
  94
  95 int lextable_decode(int pos, char c)
  96 {
  97
  98         while (1) {
  99                 if (lextable[pos] & (1 << 7)) { /* 1-byte, fail on mismatch */
 100                         if ((lextable[pos] & 0x7f) != c)
 101                                 return -1;
 102                         /* fall thru */
 103                         pos++;
 104                         if (lextable[pos] == FAIL_CHAR)
 105                                 return -1;
 106                         return pos;
 107                 } else { /* b7 = 0, end or 3-byte */
 108                         if (lextable[pos] < FAIL_CHAR) /* terminal marker */
 109                                 return pos;
 110
 111                         if (lextable[pos] == c) /* goto */
 112                                 return pos + (lextable[pos + 1]) +
 113                                                 (lextable[pos + 2] << 8);
 114                         /* fall thru goto */
 115                         pos += 3;
 116                         /* continue */
 117                 }
 118         }
 119 }
 120
 121 int main(void)
 122 {
 123         int n = 0;
 124         int m = 0;
 125         int prev;
 126         char c;
 127         int walk;
 128         int saw;
 129         int y;
 130         int j;
 131         int pos = 0;
 132
 133         while (n < sizeof(set) / sizeof(set[0])) {
 134
 135                 m = 0;
 136                 walk = 0;
 137                 prev = 0;
 138
 139                 if (set[n][0] == '\0') {
 140                         n++;
 141                         continue;
 142                 }
 143
 144                 while (set[n][m]) {
 145
 146                         saw = 0;
 147                         for (y = 0; y < state[walk].count; y++)
 148                                 if (state[walk].c[y] == set[n][m]) {
 149                                         /* exists -- go forward */
 150                                         walk = state[walk].state[y];
 151                                         saw = 1;
 152                                         break;
 153                                 }
 154
 155                         if (saw)
 156                                 goto again;
 157
 158                         /* something we didn't see before */
 159
 160                         state[walk].c[state[walk].count] = set[n][m];
 161
 162                         state[walk].state[state[walk].count] = next;
 163                         state[walk].count++;
 164                         walk = next++;
 165 again:
 166                         m++;
 167                 }
 168
 169                 state[walk].c[0] = n++;
 170                 state[walk].state[0] = 0; /* terminal marker */
 171                 state[walk].count = 1;
 172         }
 173
 174         walk = 0;
 175         for (n = 0; n < next; n++) {
 176                 state[n].bytepos = walk;
 177                 walk += (2 * state[n].count);
 178         }
 179
 180         /* compute everyone's position first */
 181
 182         pos = 0;
 183         walk = 0;
 184         for (n = 0; n < next; n++) {
 185
 186                 state[n].real_pos = pos;
 187
 188                 for (m = 0; m < state[n].count; m++) {
 189
 190                         if (state[n].state[m] == 0)
 191                                 pos += 2; /* terminal marker */
 192                         else { /* c is a character */
 193                                 if ((state[state[n].state[m]].bytepos -
 194                                                                 walk) == 2)
 195                                         pos++;
 196                                 else {
 197                                         pos += 3;
 198                                         if (m == state[n].count - 1)
 199                                                 pos++; /* fail */
 200                                 }
 201                         }
 202                         walk += 2;
 203                 }
 204         }
 205
 206         walk = 0;
 207         pos = 0;
 208         for (n = 0; n < next; n++) {
 209                 for (m = 0; m < state[n].count; m++) {
 210
 211                         if (!m)
 212                                 fprintf(stdout, "/* pos %04x: %3d */ ",
 213                                                           state[n].real_pos, n);
 214                         else
 215                                 fprintf(stdout, "                    ");
 216
 217                         y = state[n].c[m];
 218                         saw = state[n].state[m];
 219
 220                         if (saw == 0) { // c is a terminal then
 221
 222                                 if (y > 0x7ff) {
 223                                         fprintf(stderr, "terminal too big\n");
 224                                         return 2;
 225                                 }
 226
 227                                 fprintf(stdout, "   0x%02X, 0x%02X           "
 228                                         "       "
 229                                         "/* - terminal marker %2d - */,\n",
 230                                                     y >> 8, y & 0xff, y & 0x7f);
 231                                 pos += 2;
 232                                 walk += 2;
 233                                 continue;
 234                         }
 235
 236                         /* c is a character */
 237
 238                         prev = y &0x7f;
 239                         if (prev < 32 || prev > 126)
 240                                 prev = '.';
 241
 242
 243                         if ((state[saw].bytepos - walk) == 2) {
 244                                 fprintf(stdout, "   0x%02X /* '%c' -> */,\n",
 245                                                 y | 0x80, prev);
 246                                 pos++;
 247                                 walk += 2;
 248                                 continue;
 249                         }
 250
 251                         j = state[saw].real_pos - pos;
 252
 253                         if (j > 0xffff) {
 254                                 fprintf(stderr,
 255                                   "Jump > 64K bytes ahead (%d to %d)\n",
 256                                         state[n].real_pos, state[saw].real_pos);
 257                                 return 1;
 258                         }
 259                         fprintf(stdout, "   0x%02X /* '%c' */, 0x%02X, 0x%02X  "
 260                                 "/* (to 0x%04X state %3d) */,\n",
 261                                 y, prev,
 262                                 j & 0xff, j >> 8,
 263                                 state[saw].real_pos, saw);
 264                         pos += 3;
 265
 266                         if (m == state[n].count - 1) {
 267                                 fprintf(stdout,
 268                                   "                       0x%02X, /* fail */\n",
 269                                                                 FAIL_CHAR);
 270                                 pos++; /* fail */
 271                         }
 272
 273                         walk += 2;
 274                 }
 275         }
 276
 277         fprintf(stdout, "/* total size %d bytes */\n", pos);
 278
 279         /*
 280          * Try to parse every legal input string
 281          */
 282
 283         for (n = 0; n < sizeof(set) / sizeof(set[0]); n++) {
 284                 walk = 0;
 285                 m = 0;
 286                 y = -1;
 287
 288                 if (set[n][0] == '\0')
 289                         continue;
 290
 291                 fprintf(stderr, "  trying '%s'\n", set[n]);
 292
 293                 while (set[n][m]) {
 294                         walk = lextable_decode(walk, set[n][m]);
 295                         if (walk < 0) {
 296                                 fprintf(stderr, "failed\n");
 297                                 return 3;
 298                         }
 299
 300                         if (lextable[walk] < FAIL_CHAR) {
 301                                 y = (lextable[walk] << 8) + lextable[walk + 1];
 302                                 break;
 303                         }
 304                         m++;
 305                 }
 306
 307                 if (y != n) {
 308                         fprintf(stderr, "decode failed %d\n", y);
 309                         return 4;
 310                 }
 311         }
 312
 313         fprintf(stderr, "All decode OK\n");
 314
 315         return 0;
 316 }