lib/minilex.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 const char *set[] = {
   6         "GET ",
   7         "Host:",
   8         "Connection:",
   9         "Sec-WebSocket-Key1:",
  10         "Sec-WebSocket-Key2:",
  11         "Sec-WebSocket-Protocol:",
  12         "Upgrade:",
  13         "Origin:",
  14         "Sec-WebSocket-Draft:",
  15         "\x0d\x0a",
  16
  17         "Sec-WebSocket-Key:",
  18         "Sec-WebSocket-Version:",
  19         "Sec-WebSocket-Origin:",
  20
  21         "Sec-WebSocket-Extensions:",
  22
  23         "Sec-WebSocket-Accept:",
  24         "Sec-WebSocket-Nonce:",
  25         "HTTP/1.1 ",
  26 };
  27
  28 unsigned char lextable[] = {
  29 /* pos 0: state 0 */
  30    0x47 /* 'G' */, 0x07 /* to pos 14 state 1 */,
  31    0x48 /* 'H' */, 0x0A /* to pos 22 state 5 */,
  32    0x43 /* 'C' */, 0x0F /* to pos 34 state 10 */,
  33    0x53 /* 'S' */, 0x19 /* to pos 56 state 21 */,
  34    0x55 /* 'U' */, 0x3F /* to pos 134 state 51 */,
  35    0x4F /* 'O' */, 0x46 /* to pos 150 state 59 */,
  36    0x8D /* '.' */, 0x52 /* to pos 176 state 72 */,
  37 /* pos 14: state 1 */
  38    0xC5 /* 'E' */, 0x01 /* to pos 16 state 2 */,
  39 /* pos 16: state 2 */
  40    0xD4 /* 'T' */, 0x01 /* to pos 18 state 3 */,
  41 /* pos 18: state 3 */
  42    0xA0 /* ' ' */, 0x01 /* to pos 20 state 4 */,
  43 /* pos 20: state 4 */
  44    0x80, 0x00 /* terminal marker */,
  45 /* pos 22: state 5 */
  46    0x6F /* 'o' */, 0x02 /* to pos 26 state 6 */,
  47    0xD4 /* 'T' */, 0x76 /* to pos 260 state 114 */,
  48 /* pos 26: state 6 */
  49    0xF3 /* 's' */, 0x01 /* to pos 28 state 7 */,
  50 /* pos 28: state 7 */
  51    0xF4 /* 't' */, 0x01 /* to pos 30 state 8 */,
  52 /* pos 30: state 8 */
  53    0xBA /* ':' */, 0x01 /* to pos 32 state 9 */,
  54 /* pos 32: state 9 */
  55    0x81, 0x00 /* terminal marker */,
  56 /* pos 34: state 10 */
  57    0xEF /* 'o' */, 0x01 /* to pos 36 state 11 */,
  58 /* pos 36: state 11 */
  59    0xEE /* 'n' */, 0x01 /* to pos 38 state 12 */,
  60 /* pos 38: state 12 */
  61    0xEE /* 'n' */, 0x01 /* to pos 40 state 13 */,
  62 /* pos 40: state 13 */
  63    0xE5 /* 'e' */, 0x01 /* to pos 42 state 14 */,
  64 /* pos 42: state 14 */
  65    0xE3 /* 'c' */, 0x01 /* to pos 44 state 15 */,
  66 /* pos 44: state 15 */
  67    0xF4 /* 't' */, 0x01 /* to pos 46 state 16 */,
  68 /* pos 46: state 16 */
  69    0xE9 /* 'i' */, 0x01 /* to pos 48 state 17 */,
  70 /* pos 48: state 17 */
  71    0xEF /* 'o' */, 0x01 /* to pos 50 state 18 */,
  72 /* pos 50: state 18 */
  73    0xEE /* 'n' */, 0x01 /* to pos 52 state 19 */,
  74 /* pos 52: state 19 */
  75    0xBA /* ':' */, 0x01 /* to pos 54 state 20 */,
  76 /* pos 54: state 20 */
  77    0x82, 0x00 /* terminal marker */,
  78 /* pos 56: state 21 */
  79    0xE5 /* 'e' */, 0x01 /* to pos 58 state 22 */,
  80 /* pos 58: state 22 */
  81    0xE3 /* 'c' */, 0x01 /* to pos 60 state 23 */,
  82 /* pos 60: state 23 */
  83    0xAD /* '-' */, 0x01 /* to pos 62 state 24 */,
  84 /* pos 62: state 24 */
  85    0xD7 /* 'W' */, 0x01 /* to pos 64 state 25 */,
  86 /* pos 64: state 25 */
  87    0xE5 /* 'e' */, 0x01 /* to pos 66 state 26 */,
  88 /* pos 66: state 26 */
  89    0xE2 /* 'b' */, 0x01 /* to pos 68 state 27 */,
  90 /* pos 68: state 27 */
  91    0xD3 /* 'S' */, 0x01 /* to pos 70 state 28 */,
  92 /* pos 70: state 28 */
  93    0xEF /* 'o' */, 0x01 /* to pos 72 state 29 */,
  94 /* pos 72: state 29 */
  95    0xE3 /* 'c' */, 0x01 /* to pos 74 state 30 */,
  96 /* pos 74: state 30 */
  97    0xEB /* 'k' */, 0x01 /* to pos 76 state 31 */,
  98 /* pos 76: state 31 */
  99    0xE5 /* 'e' */, 0x01 /* to pos 78 state 32 */,
 100 /* pos 78: state 32 */
 101    0xF4 /* 't' */, 0x01 /* to pos 80 state 33 */,
 102 /* pos 80: state 33 */
 103    0xAD /* '-' */, 0x01 /* to pos 82 state 34 */,
 104 /* pos 82: state 34 */
 105    0x4B /* 'K' */, 0x08 /* to pos 98 state 35 */,
 106    0x50 /* 'P' */, 0x10 /* to pos 116 state 42 */,
 107    0x44 /* 'D' */, 0x27 /* to pos 164 state 66 */,
 108    0x56 /* 'V' */, 0x2F /* to pos 182 state 75 */,
 109    0x4F /* 'O' */, 0x36 /* to pos 198 state 83 */,
 110    0x45 /* 'E' */, 0x3C /* to pos 212 state 90 */,
 111    0x41 /* 'A' */, 0x46 /* to pos 234 state 101 */,
 112    0xCE /* 'N' */, 0x4C /* to pos 248 state 108 */,
 113 /* pos 98: state 35 */
 114    0xE5 /* 'e' */, 0x01 /* to pos 100 state 36 */,
 115 /* pos 100: state 36 */
 116    0xF9 /* 'y' */, 0x01 /* to pos 102 state 37 */,
 117 /* pos 102: state 37 */
 118    0x31 /* '1' */, 0x03 /* to pos 108 state 38 */,
 119    0x32 /* '2' */, 0x04 /* to pos 112 state 40 */,
 120    0xBA /* ':' */, 0x25 /* to pos 180 state 74 */,
 121 /* pos 108: state 38 */
 122    0xBA /* ':' */, 0x01 /* to pos 110 state 39 */,
 123 /* pos 110: state 39 */
 124    0x83, 0x00 /* terminal marker */,
 125 /* pos 112: state 40 */
 126    0xBA /* ':' */, 0x01 /* to pos 114 state 41 */,
 127 /* pos 114: state 41 */
 128    0x84, 0x00 /* terminal marker */,
 129 /* pos 116: state 42 */
 130    0xF2 /* 'r' */, 0x01 /* to pos 118 state 43 */,
 131 /* pos 118: state 43 */
 132    0xEF /* 'o' */, 0x01 /* to pos 120 state 44 */,
 133 /* pos 120: state 44 */
 134    0xF4 /* 't' */, 0x01 /* to pos 122 state 45 */,
 135 /* pos 122: state 45 */
 136    0xEF /* 'o' */, 0x01 /* to pos 124 state 46 */,
 137 /* pos 124: state 46 */
 138    0xE3 /* 'c' */, 0x01 /* to pos 126 state 47 */,
 139 /* pos 126: state 47 */
 140    0xEF /* 'o' */, 0x01 /* to pos 128 state 48 */,
 141 /* pos 128: state 48 */
 142    0xEC /* 'l' */, 0x01 /* to pos 130 state 49 */,
 143 /* pos 130: state 49 */
 144    0xBA /* ':' */, 0x01 /* to pos 132 state 50 */,
 145 /* pos 132: state 50 */
 146    0x85, 0x00 /* terminal marker */,
 147 /* pos 134: state 51 */
 148    0xF0 /* 'p' */, 0x01 /* to pos 136 state 52 */,
 149 /* pos 136: state 52 */
 150    0xE7 /* 'g' */, 0x01 /* to pos 138 state 53 */,
 151 /* pos 138: state 53 */
 152    0xF2 /* 'r' */, 0x01 /* to pos 140 state 54 */,
 153 /* pos 140: state 54 */
 154    0xE1 /* 'a' */, 0x01 /* to pos 142 state 55 */,
 155 /* pos 142: state 55 */
 156    0xE4 /* 'd' */, 0x01 /* to pos 144 state 56 */,
 157 /* pos 144: state 56 */
 158    0xE5 /* 'e' */, 0x01 /* to pos 146 state 57 */,
 159 /* pos 146: state 57 */
 160    0xBA /* ':' */, 0x01 /* to pos 148 state 58 */,
 161 /* pos 148: state 58 */
 162    0x86, 0x00 /* terminal marker */,
 163 /* pos 150: state 59 */
 164    0xF2 /* 'r' */, 0x01 /* to pos 152 state 60 */,
 165 /* pos 152: state 60 */
 166    0xE9 /* 'i' */, 0x01 /* to pos 154 state 61 */,
 167 /* pos 154: state 61 */
 168    0xE7 /* 'g' */, 0x01 /* to pos 156 state 62 */,
 169 /* pos 156: state 62 */
 170    0xE9 /* 'i' */, 0x01 /* to pos 158 state 63 */,
 171 /* pos 158: state 63 */
 172    0xEE /* 'n' */, 0x01 /* to pos 160 state 64 */,
 173 /* pos 160: state 64 */
 174    0xBA /* ':' */, 0x01 /* to pos 162 state 65 */,
 175 /* pos 162: state 65 */
 176    0x87, 0x00 /* terminal marker */,
 177 /* pos 164: state 66 */
 178    0xF2 /* 'r' */, 0x01 /* to pos 166 state 67 */,
 179 /* pos 166: state 67 */
 180    0xE1 /* 'a' */, 0x01 /* to pos 168 state 68 */,
 181 /* pos 168: state 68 */
 182    0xE6 /* 'f' */, 0x01 /* to pos 170 state 69 */,
 183 /* pos 170: state 69 */
 184    0xF4 /* 't' */, 0x01 /* to pos 172 state 70 */,
 185 /* pos 172: state 70 */
 186    0xBA /* ':' */, 0x01 /* to pos 174 state 71 */,
 187 /* pos 174: state 71 */
 188    0x88, 0x00 /* terminal marker */,
 189 /* pos 176: state 72 */
 190    0x8A /* '.' */, 0x01 /* to pos 178 state 73 */,
 191 /* pos 178: state 73 */
 192    0x89, 0x00 /* terminal marker */,
 193 /* pos 180: state 74 */
 194    0x8A, 0x00 /* terminal marker */,
 195 /* pos 182: state 75 */
 196    0xE5 /* 'e' */, 0x01 /* to pos 184 state 76 */,
 197 /* pos 184: state 76 */
 198    0xF2 /* 'r' */, 0x01 /* to pos 186 state 77 */,
 199 /* pos 186: state 77 */
 200    0xF3 /* 's' */, 0x01 /* to pos 188 state 78 */,
 201 /* pos 188: state 78 */
 202    0xE9 /* 'i' */, 0x01 /* to pos 190 state 79 */,
 203 /* pos 190: state 79 */
 204    0xEF /* 'o' */, 0x01 /* to pos 192 state 80 */,
 205 /* pos 192: state 80 */
 206    0xEE /* 'n' */, 0x01 /* to pos 194 state 81 */,
 207 /* pos 194: state 81 */
 208    0xBA /* ':' */, 0x01 /* to pos 196 state 82 */,
 209 /* pos 196: state 82 */
 210    0x8B, 0x00 /* terminal marker */,
 211 /* pos 198: state 83 */
 212    0xF2 /* 'r' */, 0x01 /* to pos 200 state 84 */,
 213 /* pos 200: state 84 */
 214    0xE9 /* 'i' */, 0x01 /* to pos 202 state 85 */,
 215 /* pos 202: state 85 */
 216    0xE7 /* 'g' */, 0x01 /* to pos 204 state 86 */,
 217 /* pos 204: state 86 */
 218    0xE9 /* 'i' */, 0x01 /* to pos 206 state 87 */,
 219 /* pos 206: state 87 */
 220    0xEE /* 'n' */, 0x01 /* to pos 208 state 88 */,
 221 /* pos 208: state 88 */
 222    0xBA /* ':' */, 0x01 /* to pos 210 state 89 */,
 223 /* pos 210: state 89 */
 224    0x8C, 0x00 /* terminal marker */,
 225 /* pos 212: state 90 */
 226    0xF8 /* 'x' */, 0x01 /* to pos 214 state 91 */,
 227 /* pos 214: state 91 */
 228    0xF4 /* 't' */, 0x01 /* to pos 216 state 92 */,
 229 /* pos 216: state 92 */
 230    0xE5 /* 'e' */, 0x01 /* to pos 218 state 93 */,
 231 /* pos 218: state 93 */
 232    0xEE /* 'n' */, 0x01 /* to pos 220 state 94 */,
 233 /* pos 220: state 94 */
 234    0xF3 /* 's' */, 0x01 /* to pos 222 state 95 */,
 235 /* pos 222: state 95 */
 236    0xE9 /* 'i' */, 0x01 /* to pos 224 state 96 */,
 237 /* pos 224: state 96 */
 238    0xEF /* 'o' */, 0x01 /* to pos 226 state 97 */,
 239 /* pos 226: state 97 */
 240    0xEE /* 'n' */, 0x01 /* to pos 228 state 98 */,
 241 /* pos 228: state 98 */
 242    0xF3 /* 's' */, 0x01 /* to pos 230 state 99 */,
 243 /* pos 230: state 99 */
 244    0xBA /* ':' */, 0x01 /* to pos 232 state 100 */,
 245 /* pos 232: state 100 */
 246    0x8D, 0x00 /* terminal marker */,
 247 /* pos 234: state 101 */
 248    0xE3 /* 'c' */, 0x01 /* to pos 236 state 102 */,
 249 /* pos 236: state 102 */
 250    0xE3 /* 'c' */, 0x01 /* to pos 238 state 103 */,
 251 /* pos 238: state 103 */
 252    0xE5 /* 'e' */, 0x01 /* to pos 240 state 104 */,
 253 /* pos 240: state 104 */
 254    0xF0 /* 'p' */, 0x01 /* to pos 242 state 105 */,
 255 /* pos 242: state 105 */
 256    0xF4 /* 't' */, 0x01 /* to pos 244 state 106 */,
 257 /* pos 244: state 106 */
 258    0xBA /* ':' */, 0x01 /* to pos 246 state 107 */,
 259 /* pos 246: state 107 */
 260    0x8E, 0x00 /* terminal marker */,
 261 /* pos 248: state 108 */
 262    0xEF /* 'o' */, 0x01 /* to pos 250 state 109 */,
 263 /* pos 250: state 109 */
 264    0xEE /* 'n' */, 0x01 /* to pos 252 state 110 */,
 265 /* pos 252: state 110 */
 266    0xE3 /* 'c' */, 0x01 /* to pos 254 state 111 */,
 267 /* pos 254: state 111 */
 268    0xE5 /* 'e' */, 0x01 /* to pos 256 state 112 */,
 269 /* pos 256: state 112 */
 270    0xBA /* ':' */, 0x01 /* to pos 258 state 113 */,
 271 /* pos 258: state 113 */
 272    0x8F, 0x00 /* terminal marker */,
 273 /* pos 260: state 114 */
 274    0xD4 /* 'T' */, 0x01 /* to pos 262 state 115 */,
 275 /* pos 262: state 115 */
 276    0xD0 /* 'P' */, 0x01 /* to pos 264 state 116 */,
 277 /* pos 264: state 116 */
 278    0xAF /* '/' */, 0x01 /* to pos 266 state 117 */,
 279 /* pos 266: state 117 */
 280    0xB1 /* '1' */, 0x01 /* to pos 268 state 118 */,
 281 /* pos 268: state 118 */
 282    0xAE /* '.' */, 0x01 /* to pos 270 state 119 */,
 283 /* pos 270: state 119 */
 284    0xB1 /* '1' */, 0x01 /* to pos 272 state 120 */,
 285 /* pos 272: state 120 */
 286    0xA0 /* ' ' */, 0x01 /* to pos 274 state 121 */,
 287 /* pos 274: state 121 */
 288    0x90, 0x00 /* terminal marker */,
 289 /* total size 276 bytes */
 290
 291
 292 };
 293
 294 #define PARALLEL 30
 295
 296 struct state {
 297         char c[PARALLEL];
 298         int state[PARALLEL];
 299         int count;
 300         int bytepos;
 301 };
 302
 303 struct state state[1000];
 304 int next = 1;
 305
 306 int lextable_decode(int pos, char c)
 307 {
 308         while (1) {
 309                 if (lextable[pos + 1] == 0) // terminal marker
 310                         return pos;
 311
 312                 if ((lextable[pos] & 0x7f) == c)
 313                         return pos + (lextable[pos + 1] << 1);
 314
 315                 if (lextable[pos] & 0x80)
 316                         return -1;
 317
 318                 pos += 2;
 319         }
 320         return pos;
 321 }
 322
 323
 324 int main(void)
 325 {
 326         int n = 0;
 327         int m = 0;
 328         int prev;
 329         char c;
 330         int walk;
 331         int saw;
 332         int y;
 333
 334         while (n < sizeof(set) / sizeof(set[0])) {
 335
 336                 m = 0;
 337                 walk = 0;
 338                 prev = 0;
 339
 340                 while (set[n][m]) {
 341
 342                         saw = 0;
 343                         for (y = 0; y < state[walk].count; y++)
 344                                 if (state[walk].c[y] == set[n][m]) { /* exists */
 345                                         walk = state[walk].state[y]; /* go forward */
 346                                         saw = 1;
 347                                         break;
 348                                 }
 349
 350                         if (saw)
 351                                 goto again;
 352
 353                         /* something we didn't see before */
 354
 355                         state[walk].c[state[walk].count] = set[n][m];
 356
 357                         state[walk].state[state[walk].count] = next;
 358                         state[walk].count++;
 359
 360 //                      if (set[n][m + 1] == '\0') /* terminal */
 361                                 walk = next++;
 362 again:
 363                         m++;
 364                 }
 365
 366                 state[walk].c[0] = n;
 367                 state[walk].state[0] = 0; /* terminal marker */
 368                 state[walk].count = 1;
 369
 370                 n++;
 371
 372         }
 373
 374         walk = 0;
 375         for (n = 0; n < next; n++) {
 376                 state[n].bytepos = walk;
 377                 walk += (2 * state[n].count);
 378         }
 379 #if 0
 380         for (n = 0; n < next; n++) {
 381                 fprintf(stderr, "State %d\n", n);
 382                 for (m = 0; m < state[n].count; m++)
 383                         fprintf(stderr, "'%c' -> %d\n", state[n].c[m], state[n].state[m]);
 384                 fprintf(stderr, "(stop)\n");
 385         }
 386 #endif
 387
 388         walk = 0;
 389         for (n = 0; n < next; n++) {
 390                 fprintf(stderr, "/* pos %d: state %d */\n", walk, n);
 391                 for (m = 0; m < state[n].count; m++) {
 392                         y = state[n].c[m];
 393                         saw = state[n].state[m];
 394
 395                         if (m == state[n].count - 1)
 396                                 y |= 0x80; /* last option */
 397
 398                         if (saw == 0) // c is a terminal then
 399                                 fprintf(stderr, "   0x%02X, 0x00 /* terminal marker */, \n", y);
 400                         else { // c is a character and we need a byte delta
 401                                 if ((state[saw].bytepos - walk) / 2 > 0xff) {
 402                                         fprintf(stderr, "Tried to jump > 510 bytes ahead\n");
 403                                         return 1;
 404                                 }
 405                                 prev = y &0x7f;
 406                                 if (prev < 32 || prev > 126)
 407                                         prev = '.';
 408                                 fprintf(stderr, "   0x%02X /* '%c' */, 0x%02X /* to pos %d state %d */,\n", y, prev, (state[saw].bytepos - walk) / 2, state[saw].bytepos, saw);
 409                         }
 410                         walk += 2;
 411                 }
 412         }
 413
 414         fprintf(stderr, "/* total size %d bytes */\n", walk);
 415
 416         for (n = 0; n < sizeof(set) / sizeof(set[0]); n++) {
 417                 walk = 0;
 418                 m = 0;
 419
 420                 fprintf(stderr, "Trying %s\n", set[n]);
 421
 422                 while (set[n][m]) {
 423                         walk = lextable_decode(walk, set[n][m]);
 424                         if (walk < 0) {
 425                                 fprintf(stderr, "failed\n");
 426                                 break;
 427                         }
 428                         if (lextable[walk + 1] == 0) {
 429                                 fprintf(stderr, "decode: %d\n", lextable[walk] & 0x7f);
 430                                 break;
 431                         }
 432                         m++;
 433                 }
 434         }
 435
 436         return 0;
 437 }
 438
 439
 440