tools/codegen/core/gen_hpack_tables.c

/*
 *
 * Copyright 2015-2016, 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 <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++;
  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;
}