Initial checkin of gRPC to third_party/

third_party/grpc/tools/codegen/core/gen_hpack_tables.c

Index: third_party/grpc/tools/codegen/core/gen_hpack_tables.c
diff --git a/third_party/grpc/tools/codegen/core/gen_hpack_tables.c b/third_party/grpc/tools/codegen/core/gen_hpack_tables.c
new file mode 100644
index 0000000000000000000000000000000000000000..bae4e4cd7340f3b591cac3892a68090e6164ba8b
--- /dev/null
+++ b/third_party/grpc/tools/codegen/core/gen_hpack_tables.c
@@ -0,0 +1,365 @@
+/*
+ *
+ * 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 <stddef.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+
+#include <grpc/support/log.h>
+#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;
+}