X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=lib%2Fminilex.c;h=3cb1e33696f4a3429aa9da68fa8cf4801ef45c0e;hb=ce2e74e5e38ba8c03620946e947e86dad0b81a76;hp=26b625c37e8c7e9f4e89ea5e5358d3fd1efa1866;hpb=ce64fb0f5833b93742307e154e23cf148edc1d6c;p=platform%2Fupstream%2Flibwebsockets.git diff --git a/lib/minilex.c b/lib/minilex.c index 26b625c..3cb1e33 100644 --- a/lib/minilex.c +++ b/lib/minilex.c @@ -3,7 +3,7 @@ * * High efficiency lexical state parser * - * Copyright (C)2011-2013 Andy Green + * Copyright (C)2011-2014 Andy Green * * Licensed under LGPL2 * @@ -16,47 +16,18 @@ #include #include -/* set of parsable strings -- ALL LOWER CASE */ - -const char *set[] = { - "get ", - "post ", - "host:", - "connection:", - "sec-websocket-key1:", - "sec-websocket-key2:", - "sec-websocket-protocol:", - "upgrade:", - "origin:", - "sec-websocket-draft:", - "\x0d\x0a", - - "sec-websocket-key:", - "sec-websocket-version:", - "sec-websocket-origin:", - - "sec-websocket-extensions:", - - "sec-websocket-accept:", - "sec-websocket-nonce:", - "http/1.1 ", - - "accept:", - "if-modified-since:", - "accept-encoding:", - "accept-language:", - "pragma:", - "cache-control:", - "authorization:", - "cookie:", - "content-length:", - "content-type:", - "date:", - "range:", - "referer:", - "", /* not matchable */ +#include "lextable-strings.h" -}; +/* + * b7 = 0 = 1-byte seq + * 0x08 = fail + * 2-byte seq + * 0x00 - 0x07, then terminal as given in 2nd byte + 3-byte seq + * no match: go fwd 3 byte, match: jump fwd by amt in +1/+2 bytes + * = 1 = 1-byte seq + * no match: die, match go fwd 1 byte + */ unsigned char lextable[] = { #include "lextable.h" @@ -69,29 +40,40 @@ struct state { int state[PARALLEL]; int count; int bytepos; + + int real_pos; }; struct state state[1000]; int next = 1; +#define FAIL_CHAR 0x08 int lextable_decode(int pos, char c) { while (1) { - if (!lextable[pos + 1]) /* terminal marker */ + if (lextable[pos] & (1 << 7)) { /* 1-byte, fail on mismatch */ + if ((lextable[pos] & 0x7f) != c) + return -1; + /* fall thru */ + pos++; + if (lextable[pos] == FAIL_CHAR) + return -1; return pos; - - if ((lextable[pos] & 0x7f) == c) /* goto */ - return pos + (lextable[pos + 1] << 1); - - if (lextable[pos] & 0x80) /* fail */ - return -1; - - pos += 2; + } else { /* b7 = 0, end or 3-byte */ + if (lextable[pos] < FAIL_CHAR) /* terminal marker */ + return pos; + + if (lextable[pos] == c) /* goto */ + return pos + (lextable[pos + 1]) + + (lextable[pos + 2] << 8); + /* fall thru goto */ + pos += 3; + /* continue */ + } } } - int main(void) { int n = 0; @@ -101,6 +83,8 @@ int main(void) int walk; int saw; int y; + int j; + int pos = 0; while (n < sizeof(set) / sizeof(set[0])) { @@ -149,74 +133,140 @@ again: walk += (2 * state[n].count); } + /* compute everyone's position first */ + + pos = 0; walk = 0; for (n = 0; n < next; n++) { + + state[n].real_pos = pos; + + for (m = 0; m < state[n].count; m++) { + + if (state[n].state[m] == 0) + pos += 2; /* terminal marker */ + else { /* c is a character */ + if ((state[state[n].state[m]].bytepos - + walk) == 2) + pos++; + else { + pos += 3; + if (m == state[n].count - 1) + pos++; /* fail */ + } + } + walk += 2; + } + } + + walk = 0; + pos = 0; + for (n = 0; n < next; n++) { for (m = 0; m < state[n].count; m++) { if (!m) - fprintf(stdout, "/* pos %3d: state %3d */ ", - walk, n); + fprintf(stdout, "/* pos %04x: %3d */ ", + state[n].real_pos, n); else - fprintf(stdout, " "); + fprintf(stdout, " "); y = state[n].c[m]; saw = state[n].state[m]; - if (m == state[n].count - 1) - y |= 0x80; /* last option */ - - if (saw == 0) // c is a terminal then - fprintf(stdout, " 0x%02X, 0x00 " - "/* - terminal marker %2d - */, \n", - y, y - 0x80); - else { /* c is a character and we need a byte delta */ - if ((state[saw].bytepos - walk) / 2 > 0xff) { - fprintf(stdout, - "Tried to jump > 510 bytes ahead\n"); - return 1; + if (saw == 0) { // c is a terminal then + + if (y > 0x7ff) { + fprintf(stderr, "terminal too big\n"); + return 2; } - prev = y &0x7f; - if (prev < 32 || prev > 126) - prev = '.'; - fprintf(stdout, " 0x%02X /* '%c' */, 0x%02X " - "/* (to pos %3d state %3d) */,\n", - y, prev, - (state[saw].bytepos - walk) / 2, - state[saw].bytepos, saw); + + fprintf(stdout, " 0x%02X, 0x%02X " + " " + "/* - terminal marker %2d - */,\n", + y >> 8, y & 0xff, y & 0x7f); + pos += 2; + walk += 2; + continue; + } + + /* c is a character */ + + prev = y &0x7f; + if (prev < 32 || prev > 126) + prev = '.'; + + + if ((state[saw].bytepos - walk) == 2) { + fprintf(stdout, " 0x%02X /* '%c' -> */,\n", + y | 0x80, prev); + pos++; + walk += 2; + continue; } + + j = state[saw].real_pos - pos; + + if (j > 0xffff) { + fprintf(stderr, + "Jump > 64K bytes ahead (%d to %d)\n", + state[n].real_pos, state[saw].real_pos); + return 1; + } + fprintf(stdout, " 0x%02X /* '%c' */, 0x%02X, 0x%02X " + "/* (to 0x%04X state %3d) */,\n", + y, prev, + j & 0xff, j >> 8, + state[saw].real_pos, saw); + pos += 3; + + if (m == state[n].count - 1) { + fprintf(stdout, + " 0x%02X, /* fail */\n", + FAIL_CHAR); + pos++; /* fail */ + } + walk += 2; } } - fprintf(stdout, "/* total size %d bytes */\n", walk); + fprintf(stdout, "/* total size %d bytes */\n", pos); /* - * Test parser... real parser code is the same + * Try to parse every legal input string */ for (n = 0; n < sizeof(set) / sizeof(set[0]); n++) { walk = 0; m = 0; + y = -1; if (set[n][0] == '\0') continue; - fprintf(stderr, "Trying '%s'\n", set[n]); + fprintf(stderr, " trying '%s'\n", set[n]); while (set[n][m]) { walk = lextable_decode(walk, set[n][m]); if (walk < 0) { fprintf(stderr, "failed\n"); - break; + return 3; } - if (lextable[walk + 1] == 0) { - fprintf(stderr, "decode: %d\n", - lextable[walk] & 0x7f); + + if (lextable[walk] < FAIL_CHAR) { + y = (lextable[walk] << 8) + lextable[walk + 1]; break; } m++; } + + if (y != n) { + fprintf(stderr, "decode failed %d\n", y); + return 4; + } } + fprintf(stderr, "All decode OK\n"); + return 0; }