/* * * Copyright 2015, Google Inc. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following disclaimer * in the documentation and/or other materials provided with the * distribution. * * Neither the name of Google Inc. nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ /* generates constant tables for hpack.c */ #include #include #include #include #include #include "src/core/transport/chttp2/huffsyms.h" /* * first byte LUT generation */ typedef struct { const char *call; /* bit prefix for the field type */ unsigned char prefix; /* length of the bit prefix for the field type */ unsigned char prefix_length; /* index value: 0 = all zeros, 2 = all ones, 1 otherwise */ unsigned char index; } spec; static const spec fields[] = { {"INDEXED_FIELD", 0X80, 1, 1}, {"INDEXED_FIELD_X", 0X80, 1, 2}, {"LITHDR_INCIDX", 0X40, 2, 1}, {"LITHDR_INCIDX_X", 0X40, 2, 2}, {"LITHDR_INCIDX_V", 0X40, 2, 0}, {"LITHDR_NOTIDX", 0X00, 4, 1}, {"LITHDR_NOTIDX_X", 0X00, 4, 2}, {"LITHDR_NOTIDX_V", 0X00, 4, 0}, {"LITHDR_NVRIDX", 0X10, 4, 1}, {"LITHDR_NVRIDX_X", 0X10, 4, 2}, {"LITHDR_NVRIDX_V", 0X10, 4, 0}, {"MAX_TBL_SIZE", 0X20, 3, 1}, {"MAX_TBL_SIZE_X", 0X20, 3, 2}, }; static const int num_fields = sizeof(fields) / sizeof(*fields); static unsigned char prefix_mask(unsigned char prefix_len) { unsigned char i; unsigned char out = 0; for (i = 0; i < prefix_len; i++) { /* NB: the following integer arithmetic operation needs to be in its * expanded form due to the "integral promotion" performed (see section * 3.2.1.1 of the C89 draft standard). A cast to the smaller container type * is then required to avoid the compiler warning */ out = (unsigned char)(out | (unsigned char)(1 << (7 - i))); } return out; } static unsigned char suffix_mask(unsigned char prefix_len) { return (unsigned char)~prefix_mask(prefix_len); } static void generate_first_byte_lut(void) { int i, j, n; const spec *chrspec; unsigned char suffix; n = printf("static CALLTYPE first_byte[256] = {"); /* for each potential first byte of a header */ for (i = 0; i < 256; i++) { /* find the field type that matches it */ chrspec = NULL; for (j = 0; j < num_fields; j++) { if ((prefix_mask(fields[j].prefix_length) & i) == fields[j].prefix) { /* NB: the following integer arithmetic operation needs to be in its * expanded form due to the "integral promotion" performed (see section * 3.2.1.1 of the C89 draft standard). A cast to the smaller container * type is then required to avoid the compiler warning */ suffix = (unsigned char)(suffix_mask(fields[j].prefix_length) & (unsigned char)i); if (suffix == suffix_mask(fields[j].prefix_length)) { if (fields[j].index != 2) continue; } else if (suffix == 0) { if (fields[j].index != 0) continue; } else { if (fields[j].index != 1) continue; } GPR_ASSERT(chrspec == NULL); chrspec = &fields[j]; } } if (chrspec) { n += printf("%s, ", chrspec->call); } else { n += printf("ILLEGAL, "); } /* make some small effort towards readable output */ if (n > 70) { printf("\n "); n = 2; } } printf("};\n"); } /* * Huffman decoder table generation */ #define MAXHUFFSTATES 1024 /* represents a set of symbols as an array of booleans indicating inclusion */ typedef struct { char included[GRPC_CHTTP2_NUM_HUFFSYMS]; } symset; /* represents a lookup table indexed by a nibble */ typedef struct { unsigned values[16]; } nibblelut; #define NOT_SET (~(unsigned)0) /* returns a symset that includes all possible symbols */ static symset symset_all(void) { symset x; memset(x.included, 1, sizeof(x.included)); return x; } /* returns a symset that includes no symbols */ static symset symset_none(void) { symset x; memset(x.included, 0, sizeof(x.included)); return x; } /* returns an empty nibblelut */ static nibblelut nibblelut_empty(void) { nibblelut x; int i; for (i = 0; i < 16; i++) { x.values[i] = NOT_SET; } return x; } /* counts symbols in a symset - only used for debug builds */ #ifndef NDEBUG static int nsyms(symset s) { int i; int c = 0; for (i = 0; i < GRPC_CHTTP2_NUM_HUFFSYMS; i++) { c += s.included[i] != 0; } return c; } #endif /* global table of discovered huffman decoding states */ static struct { /* the bit offset that this state starts at */ unsigned bitofs; /* the set of symbols that this state started with */ symset syms; /* lookup table for the next state */ nibblelut next; /* lookup table for what to emit */ nibblelut emit; } huffstates[MAXHUFFSTATES]; static unsigned nhuffstates = 0; /* given a number of decoded bits and a set of symbols that are live, return the index into the decoder table for this state. set isnew to 1 if this state was previously undiscovered */ static unsigned state_index(unsigned bitofs, symset syms, unsigned *isnew) { unsigned i; for (i = 0; i < nhuffstates; i++) { if (huffstates[i].bitofs != bitofs) continue; if (0 != memcmp(huffstates[i].syms.included, syms.included, GRPC_CHTTP2_NUM_HUFFSYMS)) continue; *isnew = 0; return i; } GPR_ASSERT(nhuffstates != MAXHUFFSTATES); i = nhuffstates++; huffstates[i].bitofs = bitofs; huffstates[i].syms = syms; huffstates[i].next = nibblelut_empty(); huffstates[i].emit = nibblelut_empty(); *isnew = 1; return i; } /* recursively build a decoding table state - the huffman state that we are trying to fill in nibble - the current nibble nibbits - the number of bits in the nibble that have been filled in bitofs - the number of bits of symbol that have been decoded emit - the symbol to emit on this nibble (or -1 if no symbol has been found) syms - the set of symbols that could be matched */ static void build_dec_tbl(unsigned state, unsigned nibble, int nibbits, unsigned bitofs, unsigned emit, symset syms) { unsigned i; unsigned bit; /* If we have four bits in the nibble we're looking at, then we can fill in a slot in the lookup tables. */ if (nibbits == 4) { unsigned isnew; /* Find the state that we are in: this may be a new state, in which case we recurse to fill it in, or we may have already seen this state, in which case the recursion terminates */ unsigned st = state_index(bitofs, syms, &isnew); GPR_ASSERT(huffstates[state].next.values[nibble] == NOT_SET); huffstates[state].next.values[nibble] = st; huffstates[state].emit.values[nibble] = emit; if (isnew) { build_dec_tbl(st, 0, 0, bitofs, NOT_SET, syms); } return; } assert(nsyms(syms)); /* A bit can be 0 or 1 */ for (bit = 0; bit < 2; bit++) { /* walk over active symbols and see if they have this bit set */ symset nextsyms = symset_none(); for (i = 0; i < GRPC_CHTTP2_NUM_HUFFSYMS; i++) { if (!syms.included[i]) continue; /* disregard inactive symbols */ if (((grpc_chttp2_huffsyms[i].bits >> (grpc_chttp2_huffsyms[i].length - bitofs - 1)) & 1) == bit) { /* the bit is set, include it in the next recursive set */ if (grpc_chttp2_huffsyms[i].length == bitofs + 1) { /* additionally, we've gotten to the end of a symbol - this is a special recursion step: re-activate all the symbols, reset bitofs to zero, and recurse */ build_dec_tbl(state, (nibble << 1) | bit, nibbits + 1, 0, i, symset_all()); /* skip the remainder of this loop */ goto next; } nextsyms.included[i] = 1; } } /* recurse down for this bit */ build_dec_tbl(state, (nibble << 1) | bit, nibbits + 1, bitofs + 1, emit, nextsyms); next:; } } static nibblelut ctbl[MAXHUFFSTATES]; static int nctbl; static int ctbl_idx(nibblelut x) { int i; for (i = 0; i < nctbl; i++) { if (0 == memcmp(&x, ctbl + i, sizeof(nibblelut))) return i; } ctbl[i] = x; nctbl++; return i; } static void dump_ctbl(const char *name) { int i, j; printf("static const gpr_int16 %s[%d*16] = {\n", name, nctbl); for (i = 0; i < nctbl; i++) { for (j = 0; j < 16; j++) { printf("%d,", ctbl[i].values[j]); } printf("\n"); } printf("};\n"); } static void generate_huff_tables(void) { unsigned i; build_dec_tbl(state_index(0, symset_all(), &i), 0, 0, 0, NOT_SET, symset_all()); nctbl = 0; printf("static const gpr_uint8 next_tbl[%d] = {", nhuffstates); for (i = 0; i < nhuffstates; i++) { printf("%d,", ctbl_idx(huffstates[i].next)); } printf("};\n"); dump_ctbl("next_sub_tbl"); nctbl = 0; printf("static const gpr_uint16 emit_tbl[%d] = {", nhuffstates); for (i = 0; i < nhuffstates; i++) { printf("%d,", ctbl_idx(huffstates[i].emit)); } printf("};\n"); dump_ctbl("emit_sub_tbl"); } static void generate_base64_huff_encoder_table(void) { static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; int i; printf( "static const struct { gpr_uint16 bits, gpr_uint8 length } " "base64_syms[64] = {\n"); for (i = 0; i < 64; i++) { printf("{0x%x, %d},", grpc_chttp2_huffsyms[(unsigned char)alphabet[i]].bits, grpc_chttp2_huffsyms[(unsigned char)alphabet[i]].length); } printf("};\n"); } static void generate_base64_inverse_table(void) { static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; unsigned char inverse[256]; unsigned i; memset(inverse, 255, sizeof(inverse)); for (i = 0; i < strlen(alphabet); i++) { inverse[(unsigned char)alphabet[i]] = (unsigned char)i; } printf("static const gpr_uint8 inverse_base64[256] = {"); for (i = 0; i < 256; i++) { printf("%d,", inverse[i]); } printf("};\n"); } int main(void) { generate_huff_tables(); generate_first_byte_lut(); generate_base64_huff_encoder_table(); generate_base64_inverse_table(); return 0; }