tools/codegen/core/gen_hpack_tables.cc - third_party/grpc - Git at Google

 /*
  *
  * Copyright 2015 gRPC authors.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  *
  */

 /* generates constant tables for hpack.cc */

 #include <assert.h>
 #include <stddef.h>
 #include <stdio.h>
 #include <string.h>

 #include <grpc/support/log.h>
 #include "src/core/ext/transport/chttp2/transport/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;
   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;
 }
	/*
	*
	* Copyright 2015 gRPC authors.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*
	*/

	/* generates constant tables for hpack.cc */

	#include <assert.h>
	#include <stddef.h>
	#include <stdio.h>
	#include <string.h>

	#include <grpc/support/log.h>
	#include "src/core/ext/transport/chttp2/transport/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;
	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;
	}