From b46aad6df449445a9fc4aa7b32bd40005438e3f7 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 13 Apr 2024 14:18:05 +0200 Subject: Adding upstream version 2.9.5. Signed-off-by: Daniel Baumann --- dev/hpack/README | 4 + dev/hpack/decode.c | 215 ++++++++++++++++++++++++++++++ dev/hpack/gen-enc.c | 205 +++++++++++++++++++++++++++++ dev/hpack/gen-rht.c | 369 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 793 insertions(+) create mode 100644 dev/hpack/README create mode 100644 dev/hpack/decode.c create mode 100644 dev/hpack/gen-enc.c create mode 100644 dev/hpack/gen-rht.c (limited to 'dev/hpack') diff --git a/dev/hpack/README b/dev/hpack/README new file mode 100644 index 0000000..d7258b5 --- /dev/null +++ b/dev/hpack/README @@ -0,0 +1,4 @@ +This needs to be built from the top makefile, for example : + + make dev/hpack/{decode,gen-enc,gen-rht} + diff --git a/dev/hpack/decode.c b/dev/hpack/decode.c new file mode 100644 index 0000000..13c95c7 --- /dev/null +++ b/dev/hpack/decode.c @@ -0,0 +1,215 @@ +/* + * HPACK stream decoder. Takes a series of hex codes on stdin using one line + * per HEADERS frame. Spaces, tabs, CR, '-' and ',' are silently skipped. + * e.g. : + * echo 82864188f439ce75c875fa5784 | dev/hpack/decode + * + * The DHT size may optionally be changed in argv[1]. + * + * Build like this : + * gcc -I../../include -O0 -g -fno-strict-aliasing -fwrapv \ + * -o decode decode.c + */ + +#define HPACK_STANDALONE + +#include +#include +#include +#include +#include +#include +#include + +#define MAX_RQ_SIZE 65536 +#define MAX_HDR_NUM 1000 + +char hex[MAX_RQ_SIZE*3+3]; // enough for "[ XX]* \0" +uint8_t buf[MAX_RQ_SIZE]; + +char trash_buf[MAX_RQ_SIZE]; +char tmp_buf[MAX_RQ_SIZE]; + +THREAD_LOCAL struct buffer trash = { .area = trash_buf, .data = 0, .size = sizeof(trash_buf) }; +struct buffer tmp = { .area = tmp_buf, .data = 0, .size = sizeof(tmp_buf) }; + +/* displays a long memory block at , assuming first byte of + * has address . String may be placed as a prefix in front of + * each line. It may be NULL if unused. The output is emitted to file . + */ +void debug_hexdump(FILE *out, const char *pfx, const char *buf, + unsigned int baseaddr, int len) +{ + unsigned int i; + int b, j; + + for (i = 0; i < (len + (baseaddr & 15)); i += 16) { + b = i - (baseaddr & 15); + fprintf(out, "%s%08x: ", pfx ? pfx : "", i + (baseaddr & ~15)); + for (j = 0; j < 8; j++) { + if (b + j >= 0 && b + j < len) + fprintf(out, "%02x ", (unsigned char)buf[b + j]); + else + fprintf(out, " "); + } + + if (b + j >= 0 && b + j < len) + fputc('-', out); + else + fputc(' ', out); + + for (j = 8; j < 16; j++) { + if (b + j >= 0 && b + j < len) + fprintf(out, " %02x", (unsigned char)buf[b + j]); + else + fprintf(out, " "); + } + + fprintf(out, " "); + for (j = 0; j < 16; j++) { + if (b + j >= 0 && b + j < len) { + if (isprint((unsigned char)buf[b + j])) + fputc((unsigned char)buf[b + j], out); + else + fputc('.', out); + } + else + fputc(' ', out); + } + fputc('\n', out); + } +} + +/* enable DEBUG_HPACK to show each individual hpack code */ +#define DEBUG_HPACK +#include "../src/hpack-huff.c" +#include "../src/hpack-tbl.c" +#include "../src/hpack-dec.c" + +/* display the message and exit with the code */ +__attribute__((noreturn)) void die(int code, const char *format, ...) +{ + va_list args; + + if (format) { + va_start(args, format); + vfprintf(stderr, format, args); + va_end(args); + } + exit(code); +} + +/* reads and stops at the first LF, '#' or \0. Converts from hex to + * binary, ignoring spaces, tabs, CR, "-" and ','. The output is sent into + * for no more than bytes. The number of bytes placed there is + * returned, or a negative value in case of parsing error. + */ +int hex2bin(const char *hex, uint8_t *bin, int size) +{ + int a, b, c; + uint8_t code; + int len = 0; + + a = b = -1; + + for (; *hex; hex++) { + c = *hex; + if (c == ' ' || c == '\t' || c == '\r' || + c == '-' || c == ',') + continue; + + if (c == '\n' || c == '#') + break; + + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'a' && c <= 'f') + c -= 'a' - 10; + else if (c >= 'A' && c <= 'F') + c -= 'A' - 10; + else + return -1; + + if (a == -1) + a = c; + else + b = c; + + if (b == -1) + continue; + + code = (a << 4) | b; + a = b = -1; + if (len >= size) + return -2; + + bin[len] = code; + len++; + } + if (a >= 0 || b >= 0) + return -3; + return len; +} + +int main(int argc, char **argv) +{ + struct hpack_dht *dht; + struct http_hdr list[MAX_HDR_NUM]; + struct pool_head pool; + int outlen; + int dht_size = 4096; + int len, idx; + int line; + + /* first arg: dht size */ + if (argc > 1) { + dht_size = atoi(argv[1]); + argv++; argc--; + } + + pool.size = dht_size; + pool_head_hpack_tbl = &pool; + dht = hpack_dht_alloc(); + if (!dht) { + die(1, "cannot initialize dht\n"); + return 1; + } + + for (line = 1; fgets(hex, sizeof(hex), stdin); line++) { + len = hex2bin(hex, buf, sizeof(buf)); + if (len <= 0) + continue; + printf("###### line %d : frame len=%d #######\n", line, len); + debug_hexdump(stdout, " ", (const char *)buf, 0, len); + + outlen = hpack_decode_frame(dht, buf, len, list, + sizeof(list)/sizeof(list[0]), &tmp); + if (outlen <= 0) { + printf(" HPACK decoding failed: %d\n", outlen); + continue; + } + + printf("<<< Found %d headers :\n", outlen); + for (idx = 0; idx < outlen - 1; idx++) { + //printf(" \e[1;34m%s\e[0m: ", + // list[idx].n.ptr ? istpad(trash.str, list[idx].n).ptr : h2_phdr_to_str(list[idx].n.len)); + + //printf("\e[1;35m%s\e[0m\n", istpad(trash.str, list[idx].v).ptr); + + printf(" %s: ", list[idx].n.ptr ? + istpad(trash.area, list[idx].n).ptr : + h2_phdr_to_str(list[idx].n.len)); + + printf("%s [n=(%p,%d) v=(%p,%d)]\n", + istpad(trash.area, list[idx].v).ptr, + list[idx].n.ptr, (int)list[idx].n.len, list[idx].v.ptr, (int)list[idx].v.len); + } + puts(">>>"); +#ifdef DEBUG_HPACK + printf("<<=== DHT dump [ptr=%p]:\n", dht); + hpack_dht_dump(stdout, dht); + puts("===>>"); +#endif + } + return 0; +} diff --git a/dev/hpack/gen-enc.c b/dev/hpack/gen-enc.c new file mode 100644 index 0000000..3fc5ef9 --- /dev/null +++ b/dev/hpack/gen-enc.c @@ -0,0 +1,205 @@ +/* + * HPACK encoding table generator. It produces a stream of + * and a table pointing to the first of each series. + * The end of the stream is marked by =0. In parallel, a length-indexed + * table is built to access the first entry of each length. + * + * Build like this : + * gcc -I../../include -o gen-enc gen-enc.c + */ +#define HPACK_STANDALONE + +#include +#include +#include +#include +#include +#include +#include +#include "../../src/hpack-tbl.c" + +struct idxhdr { + const char *ptr; + int len; + int idx; +}; + +struct idxhdr idxhdr[HPACK_SHT_SIZE]; +static int positions[32]; +static char known_hdr[1024]; + +/* preferred ordering of headers of similar size. Those not mentioned will be + * less prioritized. + */ +const struct { + const char *name; + const int rank; +} ranks[] = { + { .name = "age", .rank = 1 }, + { .name = "via", .rank = 2 }, + + { .name = "date", .rank = 1 }, + { .name = "host", .rank = 2 }, + + { .name = "accept", .rank = 1 }, + { .name = "server", .rank = 2 }, + { .name = "cookie", .rank = 3 }, + + { .name = "referer", .rank = 1 }, + { .name = "expires", .rank = 2 }, + + { .name = "location", .rank = 1 }, + + { .name = "user-agent", .rank = 1 }, + { .name = "set-cookie", .rank = 2 }, + + { .name = "content-type", .rank = 1 }, + + { .name = "cache-control", .rank = 1 }, + { .name = "last-modified", .rank = 2 }, + { .name = "accept-ranges", .rank = 3 }, + { .name = "if-none-match", .rank = 4 }, + + { .name = "content-length", .rank = 1 }, + + { .name = "accept-encoding", .rank = 1 }, + { .name = "accept-language", .rank = 2 }, + + { .name = "content-encoding", .rank = 1 }, + + { .name = "transfer-encoding", .rank = 1 }, + { .name = "if-modified-since", .rank = 2 }, + + { .name = "content-disposition", .rank = 1 }, +}; + +/* returns the rank of header or 255 if not found */ +int get_hdr_rank(const char *name) +{ + int i; + + for (i = 0; i < sizeof(ranks) / sizeof(ranks[0]); i++) { + if (strcmp(ranks[i].name, name) == 0) + return ranks[i].rank; + } + return 255; +} + +/* sorts first on the length, second on the name, and third on the idx, so that + * headers which appear with multiple occurrences are always met first. + */ +int cmp_idx(const void *l, const void *r) +{ + const struct idxhdr *a = l, *b = r; + int ranka, rankb; + int ret; + + if (a->len < b->len) + return -1; + else if (a->len > b->len) + return 1; + + ranka = get_hdr_rank(a->ptr); + rankb = get_hdr_rank(b->ptr); + + if (ranka < rankb) + return -1; + else if (ranka > rankb) + return 1; + + /* same rank, check for duplicates and use index */ + ret = strcmp(a->ptr, b->ptr); + if (ret != 0) + return ret; + + if (a->idx < b->idx) + return -1; + else if (a->idx > b->idx) + return 1; + else + return 0; +} + +int main(int argc, char **argv) +{ + int pos; + int prev; + int len; + int i; + + for (len = 0; len < 32; len++) + positions[len] = -1; + + for (i = 0; i < HPACK_SHT_SIZE; i++) { + idxhdr[i].ptr = hpack_sht[i].n.ptr; + idxhdr[i].len = hpack_sht[i].n.len; + idxhdr[i].idx = i; + } + + /* sorts all header names by length first, then by name, and finally by + * idx so that we meet smaller headers first, that within a length they + * appear in frequency order, and that multiple occurrences appear with + * the smallest index first. + */ + qsort(&idxhdr[1], HPACK_SHT_SIZE - 1, sizeof(idxhdr[0]), cmp_idx); + + pos = 0; + prev = -1; + for (i = 1; i < HPACK_SHT_SIZE; i++) { + len = idxhdr[i].len; + if (len > 31) { + //printf("skipping %s (len=%d)\n", idxhdr[i].ptr, idxhdr[i].len); + continue; + } + + /* first occurrence of this length? */ + if (positions[len] == -1) + positions[len] = pos; + else if (prev >= 0 && + memcmp(&known_hdr[prev] + 2, idxhdr[i].ptr, len) == 0) { + /* duplicate header field */ + continue; + } + + /* store in the output array */ + + if (pos + 1 + len + 2 >= sizeof(known_hdr)) + abort(); + + prev = pos; + known_hdr[pos++] = len; + known_hdr[pos++] = idxhdr[i].idx; + memcpy(&known_hdr[pos], idxhdr[i].ptr, len); + pos += len; + //printf("%d %d %s\n", len, idxhdr[i].idx, idxhdr[i].ptr); + } + + if (pos + 1 >= sizeof(known_hdr)) + abort(); + known_hdr[pos++] = 0; // size zero ends the stream + + printf("const char hpack_enc_stream[%d] = {\n", pos); + for (i = 0; i < pos; i++) { + if ((i & 7) == 0) + printf("\t /* % 4d: */", i); + + printf(" 0x%02x,", known_hdr[i]); + + if ((i & 7) == 7 || (i == pos - 1)) + putchar('\n'); + } + printf("};\n\n"); + + printf("const signed short hpack_pos_len[32] = {\n"); + for (i = 0; i < 32; i++) { + if ((i & 7) == 0) + printf("\t /* % 4d: */", i); + + printf(" % 4d,", positions[i]); + + if ((i & 7) == 7 || (i == pos - 1)) + putchar('\n'); + } + printf("};\n\n"); + return 0; +} diff --git a/dev/hpack/gen-rht.c b/dev/hpack/gen-rht.c new file mode 100644 index 0000000..4260ffb --- /dev/null +++ b/dev/hpack/gen-rht.c @@ -0,0 +1,369 @@ +/* Reverse Huffman table generator for HPACK decoder - 2017-05-19 Willy Tarreau + * + * rht_bit31_24[256] is indexed on bits 31..24 when < 0xfe + * rht_bit24_17[256] is indexed on bits 24..17 when 31..24 >= 0xfe + * rht_bit15_11_fe[32] is indexed on bits 15..11 when 24..17 == 0xfe + * rht_bit15_8[256] is indexed on bits 15..8 when 24..17 == 0xff + * rht_bit11_4[256] is indexed on bits 11..4 when 15..8 == 0xff + * when 11..4 == 0xff, 3..2 provide the following mapping : + * 00 => 0x0a, 01 => 0x0d, 10 => 0x16, 11 => EOS + */ + +#include +#include +#include +#include + +/* from RFC7541 Appendix B */ +static const struct huff { + uint32_t c; /* code point */ + int b; /* bits */ +} ht[257] = { + [0] = { .c = 0x00001ff8, .b = 13 }, + [1] = { .c = 0x007fffd8, .b = 23 }, + [2] = { .c = 0x0fffffe2, .b = 28 }, + [3] = { .c = 0x0fffffe3, .b = 28 }, + [4] = { .c = 0x0fffffe4, .b = 28 }, + [5] = { .c = 0x0fffffe5, .b = 28 }, + [6] = { .c = 0x0fffffe6, .b = 28 }, + [7] = { .c = 0x0fffffe7, .b = 28 }, + [8] = { .c = 0x0fffffe8, .b = 28 }, + [9] = { .c = 0x00ffffea, .b = 24 }, + [10] = { .c = 0x3ffffffc, .b = 30 }, + [11] = { .c = 0x0fffffe9, .b = 28 }, + [12] = { .c = 0x0fffffea, .b = 28 }, + [13] = { .c = 0x3ffffffd, .b = 30 }, + [14] = { .c = 0x0fffffeb, .b = 28 }, + [15] = { .c = 0x0fffffec, .b = 28 }, + [16] = { .c = 0x0fffffed, .b = 28 }, + [17] = { .c = 0x0fffffee, .b = 28 }, + [18] = { .c = 0x0fffffef, .b = 28 }, + [19] = { .c = 0x0ffffff0, .b = 28 }, + [20] = { .c = 0x0ffffff1, .b = 28 }, + [21] = { .c = 0x0ffffff2, .b = 28 }, + [22] = { .c = 0x3ffffffe, .b = 30 }, + [23] = { .c = 0x0ffffff3, .b = 28 }, + [24] = { .c = 0x0ffffff4, .b = 28 }, + [25] = { .c = 0x0ffffff5, .b = 28 }, + [26] = { .c = 0x0ffffff6, .b = 28 }, + [27] = { .c = 0x0ffffff7, .b = 28 }, + [28] = { .c = 0x0ffffff8, .b = 28 }, + [29] = { .c = 0x0ffffff9, .b = 28 }, + [30] = { .c = 0x0ffffffa, .b = 28 }, + [31] = { .c = 0x0ffffffb, .b = 28 }, + [32] = { .c = 0x00000014, .b = 6 }, + [33] = { .c = 0x000003f8, .b = 10 }, + [34] = { .c = 0x000003f9, .b = 10 }, + [35] = { .c = 0x00000ffa, .b = 12 }, + [36] = { .c = 0x00001ff9, .b = 13 }, + [37] = { .c = 0x00000015, .b = 6 }, + [38] = { .c = 0x000000f8, .b = 8 }, + [39] = { .c = 0x000007fa, .b = 11 }, + [40] = { .c = 0x000003fa, .b = 10 }, + [41] = { .c = 0x000003fb, .b = 10 }, + [42] = { .c = 0x000000f9, .b = 8 }, + [43] = { .c = 0x000007fb, .b = 11 }, + [44] = { .c = 0x000000fa, .b = 8 }, + [45] = { .c = 0x00000016, .b = 6 }, + [46] = { .c = 0x00000017, .b = 6 }, + [47] = { .c = 0x00000018, .b = 6 }, + [48] = { .c = 0x00000000, .b = 5 }, + [49] = { .c = 0x00000001, .b = 5 }, + [50] = { .c = 0x00000002, .b = 5 }, + [51] = { .c = 0x00000019, .b = 6 }, + [52] = { .c = 0x0000001a, .b = 6 }, + [53] = { .c = 0x0000001b, .b = 6 }, + [54] = { .c = 0x0000001c, .b = 6 }, + [55] = { .c = 0x0000001d, .b = 6 }, + [56] = { .c = 0x0000001e, .b = 6 }, + [57] = { .c = 0x0000001f, .b = 6 }, + [58] = { .c = 0x0000005c, .b = 7 }, + [59] = { .c = 0x000000fb, .b = 8 }, + [60] = { .c = 0x00007ffc, .b = 15 }, + [61] = { .c = 0x00000020, .b = 6 }, + [62] = { .c = 0x00000ffb, .b = 12 }, + [63] = { .c = 0x000003fc, .b = 10 }, + [64] = { .c = 0x00001ffa, .b = 13 }, + [65] = { .c = 0x00000021, .b = 6 }, + [66] = { .c = 0x0000005d, .b = 7 }, + [67] = { .c = 0x0000005e, .b = 7 }, + [68] = { .c = 0x0000005f, .b = 7 }, + [69] = { .c = 0x00000060, .b = 7 }, + [70] = { .c = 0x00000061, .b = 7 }, + [71] = { .c = 0x00000062, .b = 7 }, + [72] = { .c = 0x00000063, .b = 7 }, + [73] = { .c = 0x00000064, .b = 7 }, + [74] = { .c = 0x00000065, .b = 7 }, + [75] = { .c = 0x00000066, .b = 7 }, + [76] = { .c = 0x00000067, .b = 7 }, + [77] = { .c = 0x00000068, .b = 7 }, + [78] = { .c = 0x00000069, .b = 7 }, + [79] = { .c = 0x0000006a, .b = 7 }, + [80] = { .c = 0x0000006b, .b = 7 }, + [81] = { .c = 0x0000006c, .b = 7 }, + [82] = { .c = 0x0000006d, .b = 7 }, + [83] = { .c = 0x0000006e, .b = 7 }, + [84] = { .c = 0x0000006f, .b = 7 }, + [85] = { .c = 0x00000070, .b = 7 }, + [86] = { .c = 0x00000071, .b = 7 }, + [87] = { .c = 0x00000072, .b = 7 }, + [88] = { .c = 0x000000fc, .b = 8 }, + [89] = { .c = 0x00000073, .b = 7 }, + [90] = { .c = 0x000000fd, .b = 8 }, + [91] = { .c = 0x00001ffb, .b = 13 }, + [92] = { .c = 0x0007fff0, .b = 19 }, + [93] = { .c = 0x00001ffc, .b = 13 }, + [94] = { .c = 0x00003ffc, .b = 14 }, + [95] = { .c = 0x00000022, .b = 6 }, + [96] = { .c = 0x00007ffd, .b = 15 }, + [97] = { .c = 0x00000003, .b = 5 }, + [98] = { .c = 0x00000023, .b = 6 }, + [99] = { .c = 0x00000004, .b = 5 }, + [100] = { .c = 0x00000024, .b = 6 }, + [101] = { .c = 0x00000005, .b = 5 }, + [102] = { .c = 0x00000025, .b = 6 }, + [103] = { .c = 0x00000026, .b = 6 }, + [104] = { .c = 0x00000027, .b = 6 }, + [105] = { .c = 0x00000006, .b = 5 }, + [106] = { .c = 0x00000074, .b = 7 }, + [107] = { .c = 0x00000075, .b = 7 }, + [108] = { .c = 0x00000028, .b = 6 }, + [109] = { .c = 0x00000029, .b = 6 }, + [110] = { .c = 0x0000002a, .b = 6 }, + [111] = { .c = 0x00000007, .b = 5 }, + [112] = { .c = 0x0000002b, .b = 6 }, + [113] = { .c = 0x00000076, .b = 7 }, + [114] = { .c = 0x0000002c, .b = 6 }, + [115] = { .c = 0x00000008, .b = 5 }, + [116] = { .c = 0x00000009, .b = 5 }, + [117] = { .c = 0x0000002d, .b = 6 }, + [118] = { .c = 0x00000077, .b = 7 }, + [119] = { .c = 0x00000078, .b = 7 }, + [120] = { .c = 0x00000079, .b = 7 }, + [121] = { .c = 0x0000007a, .b = 7 }, + [122] = { .c = 0x0000007b, .b = 7 }, + [123] = { .c = 0x00007ffe, .b = 15 }, + [124] = { .c = 0x000007fc, .b = 11 }, + [125] = { .c = 0x00003ffd, .b = 14 }, + [126] = { .c = 0x00001ffd, .b = 13 }, + [127] = { .c = 0x0ffffffc, .b = 28 }, + [128] = { .c = 0x000fffe6, .b = 20 }, + [129] = { .c = 0x003fffd2, .b = 22 }, + [130] = { .c = 0x000fffe7, .b = 20 }, + [131] = { .c = 0x000fffe8, .b = 20 }, + [132] = { .c = 0x003fffd3, .b = 22 }, + [133] = { .c = 0x003fffd4, .b = 22 }, + [134] = { .c = 0x003fffd5, .b = 22 }, + [135] = { .c = 0x007fffd9, .b = 23 }, + [136] = { .c = 0x003fffd6, .b = 22 }, + [137] = { .c = 0x007fffda, .b = 23 }, + [138] = { .c = 0x007fffdb, .b = 23 }, + [139] = { .c = 0x007fffdc, .b = 23 }, + [140] = { .c = 0x007fffdd, .b = 23 }, + [141] = { .c = 0x007fffde, .b = 23 }, + [142] = { .c = 0x00ffffeb, .b = 24 }, + [143] = { .c = 0x007fffdf, .b = 23 }, + [144] = { .c = 0x00ffffec, .b = 24 }, + [145] = { .c = 0x00ffffed, .b = 24 }, + [146] = { .c = 0x003fffd7, .b = 22 }, + [147] = { .c = 0x007fffe0, .b = 23 }, + [148] = { .c = 0x00ffffee, .b = 24 }, + [149] = { .c = 0x007fffe1, .b = 23 }, + [150] = { .c = 0x007fffe2, .b = 23 }, + [151] = { .c = 0x007fffe3, .b = 23 }, + [152] = { .c = 0x007fffe4, .b = 23 }, + [153] = { .c = 0x001fffdc, .b = 21 }, + [154] = { .c = 0x003fffd8, .b = 22 }, + [155] = { .c = 0x007fffe5, .b = 23 }, + [156] = { .c = 0x003fffd9, .b = 22 }, + [157] = { .c = 0x007fffe6, .b = 23 }, + [158] = { .c = 0x007fffe7, .b = 23 }, + [159] = { .c = 0x00ffffef, .b = 24 }, + [160] = { .c = 0x003fffda, .b = 22 }, + [161] = { .c = 0x001fffdd, .b = 21 }, + [162] = { .c = 0x000fffe9, .b = 20 }, + [163] = { .c = 0x003fffdb, .b = 22 }, + [164] = { .c = 0x003fffdc, .b = 22 }, + [165] = { .c = 0x007fffe8, .b = 23 }, + [166] = { .c = 0x007fffe9, .b = 23 }, + [167] = { .c = 0x001fffde, .b = 21 }, + [168] = { .c = 0x007fffea, .b = 23 }, + [169] = { .c = 0x003fffdd, .b = 22 }, + [170] = { .c = 0x003fffde, .b = 22 }, + [171] = { .c = 0x00fffff0, .b = 24 }, + [172] = { .c = 0x001fffdf, .b = 21 }, + [173] = { .c = 0x003fffdf, .b = 22 }, + [174] = { .c = 0x007fffeb, .b = 23 }, + [175] = { .c = 0x007fffec, .b = 23 }, + [176] = { .c = 0x001fffe0, .b = 21 }, + [177] = { .c = 0x001fffe1, .b = 21 }, + [178] = { .c = 0x003fffe0, .b = 22 }, + [179] = { .c = 0x001fffe2, .b = 21 }, + [180] = { .c = 0x007fffed, .b = 23 }, + [181] = { .c = 0x003fffe1, .b = 22 }, + [182] = { .c = 0x007fffee, .b = 23 }, + [183] = { .c = 0x007fffef, .b = 23 }, + [184] = { .c = 0x000fffea, .b = 20 }, + [185] = { .c = 0x003fffe2, .b = 22 }, + [186] = { .c = 0x003fffe3, .b = 22 }, + [187] = { .c = 0x003fffe4, .b = 22 }, + [188] = { .c = 0x007ffff0, .b = 23 }, + [189] = { .c = 0x003fffe5, .b = 22 }, + [190] = { .c = 0x003fffe6, .b = 22 }, + [191] = { .c = 0x007ffff1, .b = 23 }, + [192] = { .c = 0x03ffffe0, .b = 26 }, + [193] = { .c = 0x03ffffe1, .b = 26 }, + [194] = { .c = 0x000fffeb, .b = 20 }, + [195] = { .c = 0x0007fff1, .b = 19 }, + [196] = { .c = 0x003fffe7, .b = 22 }, + [197] = { .c = 0x007ffff2, .b = 23 }, + [198] = { .c = 0x003fffe8, .b = 22 }, + [199] = { .c = 0x01ffffec, .b = 25 }, + [200] = { .c = 0x03ffffe2, .b = 26 }, + [201] = { .c = 0x03ffffe3, .b = 26 }, + [202] = { .c = 0x03ffffe4, .b = 26 }, + [203] = { .c = 0x07ffffde, .b = 27 }, + [204] = { .c = 0x07ffffdf, .b = 27 }, + [205] = { .c = 0x03ffffe5, .b = 26 }, + [206] = { .c = 0x00fffff1, .b = 24 }, + [207] = { .c = 0x01ffffed, .b = 25 }, + [208] = { .c = 0x0007fff2, .b = 19 }, + [209] = { .c = 0x001fffe3, .b = 21 }, + [210] = { .c = 0x03ffffe6, .b = 26 }, + [211] = { .c = 0x07ffffe0, .b = 27 }, + [212] = { .c = 0x07ffffe1, .b = 27 }, + [213] = { .c = 0x03ffffe7, .b = 26 }, + [214] = { .c = 0x07ffffe2, .b = 27 }, + [215] = { .c = 0x00fffff2, .b = 24 }, + [216] = { .c = 0x001fffe4, .b = 21 }, + [217] = { .c = 0x001fffe5, .b = 21 }, + [218] = { .c = 0x03ffffe8, .b = 26 }, + [219] = { .c = 0x03ffffe9, .b = 26 }, + [220] = { .c = 0x0ffffffd, .b = 28 }, + [221] = { .c = 0x07ffffe3, .b = 27 }, + [222] = { .c = 0x07ffffe4, .b = 27 }, + [223] = { .c = 0x07ffffe5, .b = 27 }, + [224] = { .c = 0x000fffec, .b = 20 }, + [225] = { .c = 0x00fffff3, .b = 24 }, + [226] = { .c = 0x000fffed, .b = 20 }, + [227] = { .c = 0x001fffe6, .b = 21 }, + [228] = { .c = 0x003fffe9, .b = 22 }, + [229] = { .c = 0x001fffe7, .b = 21 }, + [230] = { .c = 0x001fffe8, .b = 21 }, + [231] = { .c = 0x007ffff3, .b = 23 }, + [232] = { .c = 0x003fffea, .b = 22 }, + [233] = { .c = 0x003fffeb, .b = 22 }, + [234] = { .c = 0x01ffffee, .b = 25 }, + [235] = { .c = 0x01ffffef, .b = 25 }, + [236] = { .c = 0x00fffff4, .b = 24 }, + [237] = { .c = 0x00fffff5, .b = 24 }, + [238] = { .c = 0x03ffffea, .b = 26 }, + [239] = { .c = 0x007ffff4, .b = 23 }, + [240] = { .c = 0x03ffffeb, .b = 26 }, + [241] = { .c = 0x07ffffe6, .b = 27 }, + [242] = { .c = 0x03ffffec, .b = 26 }, + [243] = { .c = 0x03ffffed, .b = 26 }, + [244] = { .c = 0x07ffffe7, .b = 27 }, + [245] = { .c = 0x07ffffe8, .b = 27 }, + [246] = { .c = 0x07ffffe9, .b = 27 }, + [247] = { .c = 0x07ffffea, .b = 27 }, + [248] = { .c = 0x07ffffeb, .b = 27 }, + [249] = { .c = 0x0ffffffe, .b = 28 }, + [250] = { .c = 0x07ffffec, .b = 27 }, + [251] = { .c = 0x07ffffed, .b = 27 }, + [252] = { .c = 0x07ffffee, .b = 27 }, + [253] = { .c = 0x07ffffef, .b = 27 }, + [254] = { .c = 0x07fffff0, .b = 27 }, + [255] = { .c = 0x03ffffee, .b = 26 }, + [256] = { .c = 0x3fffffff, .b = 30 }, /* EOS */ +}; + + +int main(int argc, char **argv) +{ + uint32_t c, i, j; + + /* fill first byte */ + printf("struct rht rht_bit31_24[256] = {\n"); + for (j = 0; j < 256; j++) { + for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) { + if (ht[i].b > 8) + continue; + c = ht[i].c << (32 - ht[i].b); + + if (((c ^ (j << 24)) & -(1 << (32 - ht[i].b)) & 0xff000000) == 0) { + printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b); + break; + } + } + } + printf("};\n\n"); + + printf("struct rht rht_bit24_17[256] = {\n"); + for (j = 0; j < 256; j++) { + for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) { + if (ht[i].b <= 8 || ht[i].b > 16) + continue; + c = ht[i].c << (32 - ht[i].b); + + if (((c ^ (j << 17)) & -(1 << (32 - ht[i].b)) & 0x01fe0000) == 0) { + printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b); + break; + } + } + } + printf("};\n\n"); + + printf("struct rht rht_bit15_11_fe[32] = {\n"); + for (j = 0; j < 32; j++) { + for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) { + if (ht[i].b <= 16 || ht[i].b > 21) + continue; + c = ht[i].c << (32 - ht[i].b); + if ((c & 0x00ff0000) != 0x00fe0000) + continue; + + if (((c ^ (j << 11)) & -(1 << (32 - ht[i].b)) & 0x0000f800) == 0) { + printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b); + break; + } + } + } + printf("};\n\n"); + + printf("struct rht rht_bit15_8[256] = {\n"); + for (j = 0; j < 256; j++) { + for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) { + if (ht[i].b <= 16 || ht[i].b > 24) + continue; + c = ht[i].c << (32 - ht[i].b); + if ((c & 0x00ff0000) != 0x00ff0000) + continue; + + if (((c ^ (j << 8)) & -(1 << (32 - ht[i].b)) & 0x0000ff00) == 0) { + printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b); + break; + } + } + } + printf("};\n\n"); + + printf("struct rht rht_bit11_4[256] = {\n"); + /* fill fourth byte after 0xff 0xff 0xf6-0xff. Only 0xfffffffx are not distinguished */ + for (j = 0; j < 256; j++) { + for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) { + if (ht[i].b <= 24) + continue; + c = ht[i].c << (32 - ht[i].b); + + if (((c ^ (j << 4)) & -(1 << (32 - ht[i].b)) & 0x00000ff0) == 0) { + //printf("\tj=%02x i=%02x c=%08x l=%d c/l=%08x j/l=%08x xor=%08x\n", j, i, c, ht[i].b, c & -(1 << (32 - ht[i].b)), ((j << 4) & -(1 << (32 - ht[i].b))), (c ^ (j << 4)) & -(1 << (32 - ht[i].b))); + printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b); + break; + } + } + } + printf("\t/* Note, when l==30, bits 3..2 give 00:0x0a, 01:0x0d, 10:0x16, 11:EOS */\n"); + printf("};\n\n"); + return 0; +} -- cgit v1.2.3