Adding upstream version 2.9.5.upstream/2.9.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 793 insertions, 0 deletions

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 <ctype.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <haproxy/chunk.h>
+#include <haproxy/hpack-dec.h>
+
+#define MAX_RQ_SIZE 65536
+#define MAX_HDR_NUM 1000
+
+char hex[MAX_RQ_SIZE*3+3]; // enough for "[ XX]* <CR> <LF> \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 <len> long memory block at <buf>, assuming first byte of <buf>
+ * has address <baseaddr>. String <pfx> may be placed as a prefix in front of
+ * each line. It may be NULL if unused. The output is emitted to file <out>.
+ */
+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 <hex> and stops at the first LF, '#' or \0. Converts from hex to
+ * binary, ignoring spaces, tabs, CR, "-" and ','. The output is sent into
+ * <bin> for no more than <size> 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
+ * <len><idx><name> and a table pointing to the first <len> of each series.
+ * The end of the stream is marked by <len>=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 <ctype.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <import/ist.h>
+#include <haproxy/hpack-tbl-t.h>
+#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 <name> 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 <len> <idx> <name> 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 <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* 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;
+}