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