net/spdy/hpack_constants.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/spdy/hpack_constants.h"
   6
   7 #include <bitset>
   8
   9 #include "base/logging.h"
  10 #include "base/memory/scoped_ptr.h"
  11 #include "base/memory/singleton.h"
  12 #include "net/spdy/hpack_huffman_table.h"
  13
  14 namespace net {
  15
  16 namespace {
  17
  18 uint32 bits32(const std::string& bitstring) {
  19   return std::bitset<32>(bitstring).to_ulong();
  20 }
  21
  22 // SharedHpackHuffmanTable is a Singleton wrapping a HpackHuffmanTable
  23 // instance initialized with |kHpackHuffmanCode|.
  24 struct SharedHpackHuffmanTable {
  25  public:
  26   SharedHpackHuffmanTable() {
  27     std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
  28     scoped_ptr<HpackHuffmanTable> mutable_table(new HpackHuffmanTable());
  29     CHECK(mutable_table->Initialize(&code[0], code.size()));
  30     CHECK(mutable_table->IsInitialized());
  31     table.reset(mutable_table.release());
  32   }
  33
  34   static SharedHpackHuffmanTable* GetInstance() {
  35     return Singleton<SharedHpackHuffmanTable>::get();
  36   }
  37
  38   scoped_ptr<const HpackHuffmanTable> table;
  39 };
  40
  41 }  // namespace
  42
  43 // Produced by applying the python program [1] to tables provided by [2].
  44 // [1]
  45 // import re, sys
  46 // count = 0
  47 // for l in sys.stdin:
  48 //   m = re.match(
  49 //     r"^ +('.+'|EOS)? \( *(\d+)\)  \|([10\|]+) +\w+  \[ ?(\d+)\]", l)
  50 //   if m:
  51 //     g = m.groups()
  52 //     print('  {0b%s, %02s, %03s},%s' % (
  53 //       g[2].replace('|','').ljust(32,'0'), g[3], g[1],
  54 //       ('  // %s' % g[0]) if g[0] else ''))
  55 //     count += 1
  56 // print("Total: %s" % count)
  57 //
  58 // [2] http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07
  59
  60 // HpackHuffmanSymbol entries are initialized as {code, length, id}.
  61 // Codes are specified in the |length| most-significant bits of |code|.
  62 std::vector<HpackHuffmanSymbol> HpackHuffmanCode() {
  63   const HpackHuffmanSymbol kHpackHuffmanCode[] = {
  64     {bits32("11111111110000000000000000000000"), 13,   0},
  65     {bits32("11111111111111111011000000000000"), 23,   1},
  66     {bits32("11111111111111111111111000100000"), 28,   2},
  67     {bits32("11111111111111111111111000110000"), 28,   3},
  68     {bits32("11111111111111111111111001000000"), 28,   4},
  69     {bits32("11111111111111111111111001010000"), 28,   5},
  70     {bits32("11111111111111111111111001100000"), 28,   6},
  71     {bits32("11111111111111111111111001110000"), 28,   7},
  72     {bits32("11111111111111111111111010000000"), 28,   8},
  73     {bits32("11111111111111111110101000000000"), 24,   9},
  74     {bits32("11111111111111111111111111110000"), 30,  10},
  75     {bits32("11111111111111111111111010010000"), 28,  11},
  76     {bits32("11111111111111111111111010100000"), 28,  12},
  77     {bits32("11111111111111111111111111110100"), 30,  13},
  78     {bits32("11111111111111111111111010110000"), 28,  14},
  79     {bits32("11111111111111111111111011000000"), 28,  15},
  80     {bits32("11111111111111111111111011010000"), 28,  16},
  81     {bits32("11111111111111111111111011100000"), 28,  17},
  82     {bits32("11111111111111111111111011110000"), 28,  18},
  83     {bits32("11111111111111111111111100000000"), 28,  19},
  84     {bits32("11111111111111111111111100010000"), 28,  20},
  85     {bits32("11111111111111111111111100100000"), 28,  21},
  86     {bits32("11111111111111111111111111111000"), 30,  22},
  87     {bits32("11111111111111111111111100110000"), 28,  23},
  88     {bits32("11111111111111111111111101000000"), 28,  24},
  89     {bits32("11111111111111111111111101010000"), 28,  25},
  90     {bits32("11111111111111111111111101100000"), 28,  26},
  91     {bits32("11111111111111111111111101110000"), 28,  27},
  92     {bits32("11111111111111111111111110000000"), 28,  28},
  93     {bits32("11111111111111111111111110010000"), 28,  29},
  94     {bits32("11111111111111111111111110100000"), 28,  30},
  95     {bits32("11111111111111111111111110110000"), 28,  31},
  96     {bits32("01010000000000000000000000000000"),  6,  32},  // ' '
  97     {bits32("11111110000000000000000000000000"), 10,  33},  // '!'
  98     {bits32("11111110010000000000000000000000"), 10,  34},  // '"'
  99     {bits32("11111111101000000000000000000000"), 12,  35},  // '#'
 100     {bits32("11111111110010000000000000000000"), 13,  36},  // '$'
 101     {bits32("01010100000000000000000000000000"),  6,  37},  // '%'
 102     {bits32("11111000000000000000000000000000"),  8,  38},  // '&'
 103     {bits32("11111111010000000000000000000000"), 11,  39},  // '''
 104     {bits32("11111110100000000000000000000000"), 10,  40},  // '('
 105     {bits32("11111110110000000000000000000000"), 10,  41},  // ')'
 106     {bits32("11111001000000000000000000000000"),  8,  42},  // '*'
 107     {bits32("11111111011000000000000000000000"), 11,  43},  // '+'
 108     {bits32("11111010000000000000000000000000"),  8,  44},  // ','
 109     {bits32("01011000000000000000000000000000"),  6,  45},  // '-'
 110     {bits32("01011100000000000000000000000000"),  6,  46},  // '.'
 111     {bits32("01100000000000000000000000000000"),  6,  47},  // '/'
 112     {bits32("00000000000000000000000000000000"),  5,  48},  // '0'
 113     {bits32("00001000000000000000000000000000"),  5,  49},  // '1'
 114     {bits32("00010000000000000000000000000000"),  5,  50},  // '2'
 115     {bits32("01100100000000000000000000000000"),  6,  51},  // '3'
 116     {bits32("01101000000000000000000000000000"),  6,  52},  // '4'
 117     {bits32("01101100000000000000000000000000"),  6,  53},  // '5'
 118     {bits32("01110000000000000000000000000000"),  6,  54},  // '6'
 119     {bits32("01110100000000000000000000000000"),  6,  55},  // '7'
 120     {bits32("01111000000000000000000000000000"),  6,  56},  // '8'
 121     {bits32("01111100000000000000000000000000"),  6,  57},  // '9'
 122     {bits32("10111000000000000000000000000000"),  7,  58},  // ':'
 123     {bits32("11111011000000000000000000000000"),  8,  59},  // ';'
 124     {bits32("11111111111110000000000000000000"), 15,  60},  // '<'
 125     {bits32("10000000000000000000000000000000"),  6,  61},  // '='
 126     {bits32("11111111101100000000000000000000"), 12,  62},  // '>'
 127     {bits32("11111111000000000000000000000000"), 10,  63},  // '?'
 128     {bits32("11111111110100000000000000000000"), 13,  64},  // '@'
 129     {bits32("10000100000000000000000000000000"),  6,  65},  // 'A'
 130     {bits32("10111010000000000000000000000000"),  7,  66},  // 'B'
 131     {bits32("10111100000000000000000000000000"),  7,  67},  // 'C'
 132     {bits32("10111110000000000000000000000000"),  7,  68},  // 'D'
 133     {bits32("11000000000000000000000000000000"),  7,  69},  // 'E'
 134     {bits32("11000010000000000000000000000000"),  7,  70},  // 'F'
 135     {bits32("11000100000000000000000000000000"),  7,  71},  // 'G'
 136     {bits32("11000110000000000000000000000000"),  7,  72},  // 'H'
 137     {bits32("11001000000000000000000000000000"),  7,  73},  // 'I'
 138     {bits32("11001010000000000000000000000000"),  7,  74},  // 'J'
 139     {bits32("11001100000000000000000000000000"),  7,  75},  // 'K'
 140     {bits32("11001110000000000000000000000000"),  7,  76},  // 'L'
 141     {bits32("11010000000000000000000000000000"),  7,  77},  // 'M'
 142     {bits32("11010010000000000000000000000000"),  7,  78},  // 'N'
 143     {bits32("11010100000000000000000000000000"),  7,  79},  // 'O'
 144     {bits32("11010110000000000000000000000000"),  7,  80},  // 'P'
 145     {bits32("11011000000000000000000000000000"),  7,  81},  // 'Q'
 146     {bits32("11011010000000000000000000000000"),  7,  82},  // 'R'
 147     {bits32("11011100000000000000000000000000"),  7,  83},  // 'S'
 148     {bits32("11011110000000000000000000000000"),  7,  84},  // 'T'
 149     {bits32("11100000000000000000000000000000"),  7,  85},  // 'U'
 150     {bits32("11100010000000000000000000000000"),  7,  86},  // 'V'
 151     {bits32("11100100000000000000000000000000"),  7,  87},  // 'W'
 152     {bits32("11111100000000000000000000000000"),  8,  88},  // 'X'
 153     {bits32("11100110000000000000000000000000"),  7,  89},  // 'Y'
 154     {bits32("11111101000000000000000000000000"),  8,  90},  // 'Z'
 155     {bits32("11111111110110000000000000000000"), 13,  91},  // '['
 156     {bits32("11111111111111100000000000000000"), 19,  92},  // '\'
 157     {bits32("11111111111000000000000000000000"), 13,  93},  // ']'
 158     {bits32("11111111111100000000000000000000"), 14,  94},  // '^'
 159     {bits32("10001000000000000000000000000000"),  6,  95},  // '_'
 160     {bits32("11111111111110100000000000000000"), 15,  96},  // '`'
 161     {bits32("00011000000000000000000000000000"),  5,  97},  // 'a'
 162     {bits32("10001100000000000000000000000000"),  6,  98},  // 'b'
 163     {bits32("00100000000000000000000000000000"),  5,  99},  // 'c'
 164     {bits32("10010000000000000000000000000000"),  6, 100},  // 'd'
 165     {bits32("00101000000000000000000000000000"),  5, 101},  // 'e'
 166     {bits32("10010100000000000000000000000000"),  6, 102},  // 'f'
 167     {bits32("10011000000000000000000000000000"),  6, 103},  // 'g'
 168     {bits32("10011100000000000000000000000000"),  6, 104},  // 'h'
 169     {bits32("00110000000000000000000000000000"),  5, 105},  // 'i'
 170     {bits32("11101000000000000000000000000000"),  7, 106},  // 'j'
 171     {bits32("11101010000000000000000000000000"),  7, 107},  // 'k'
 172     {bits32("10100000000000000000000000000000"),  6, 108},  // 'l'
 173     {bits32("10100100000000000000000000000000"),  6, 109},  // 'm'
 174     {bits32("10101000000000000000000000000000"),  6, 110},  // 'n'
 175     {bits32("00111000000000000000000000000000"),  5, 111},  // 'o'
 176     {bits32("10101100000000000000000000000000"),  6, 112},  // 'p'
 177     {bits32("11101100000000000000000000000000"),  7, 113},  // 'q'
 178     {bits32("10110000000000000000000000000000"),  6, 114},  // 'r'
 179     {bits32("01000000000000000000000000000000"),  5, 115},  // 's'
 180     {bits32("01001000000000000000000000000000"),  5, 116},  // 't'
 181     {bits32("10110100000000000000000000000000"),  6, 117},  // 'u'
 182     {bits32("11101110000000000000000000000000"),  7, 118},  // 'v'
 183     {bits32("11110000000000000000000000000000"),  7, 119},  // 'w'
 184     {bits32("11110010000000000000000000000000"),  7, 120},  // 'x'
 185     {bits32("11110100000000000000000000000000"),  7, 121},  // 'y'
 186     {bits32("11110110000000000000000000000000"),  7, 122},  // 'z'
 187     {bits32("11111111111111000000000000000000"), 15, 123},  // '{'
 188     {bits32("11111111100000000000000000000000"), 11, 124},  // '|'
 189     {bits32("11111111111101000000000000000000"), 14, 125},  // '}'
 190     {bits32("11111111111010000000000000000000"), 13, 126},  // '~'
 191     {bits32("11111111111111111111111111000000"), 28, 127},
 192     {bits32("11111111111111100110000000000000"), 20, 128},
 193     {bits32("11111111111111110100100000000000"), 22, 129},
 194     {bits32("11111111111111100111000000000000"), 20, 130},
 195     {bits32("11111111111111101000000000000000"), 20, 131},
 196     {bits32("11111111111111110100110000000000"), 22, 132},
 197     {bits32("11111111111111110101000000000000"), 22, 133},
 198     {bits32("11111111111111110101010000000000"), 22, 134},
 199     {bits32("11111111111111111011001000000000"), 23, 135},
 200     {bits32("11111111111111110101100000000000"), 22, 136},
 201     {bits32("11111111111111111011010000000000"), 23, 137},
 202     {bits32("11111111111111111011011000000000"), 23, 138},
 203     {bits32("11111111111111111011100000000000"), 23, 139},
 204     {bits32("11111111111111111011101000000000"), 23, 140},
 205     {bits32("11111111111111111011110000000000"), 23, 141},
 206     {bits32("11111111111111111110101100000000"), 24, 142},
 207     {bits32("11111111111111111011111000000000"), 23, 143},
 208     {bits32("11111111111111111110110000000000"), 24, 144},
 209     {bits32("11111111111111111110110100000000"), 24, 145},
 210     {bits32("11111111111111110101110000000000"), 22, 146},
 211     {bits32("11111111111111111100000000000000"), 23, 147},
 212     {bits32("11111111111111111110111000000000"), 24, 148},
 213     {bits32("11111111111111111100001000000000"), 23, 149},
 214     {bits32("11111111111111111100010000000000"), 23, 150},
 215     {bits32("11111111111111111100011000000000"), 23, 151},
 216     {bits32("11111111111111111100100000000000"), 23, 152},
 217     {bits32("11111111111111101110000000000000"), 21, 153},
 218     {bits32("11111111111111110110000000000000"), 22, 154},
 219     {bits32("11111111111111111100101000000000"), 23, 155},
 220     {bits32("11111111111111110110010000000000"), 22, 156},
 221     {bits32("11111111111111111100110000000000"), 23, 157},
 222     {bits32("11111111111111111100111000000000"), 23, 158},
 223     {bits32("11111111111111111110111100000000"), 24, 159},
 224     {bits32("11111111111111110110100000000000"), 22, 160},
 225     {bits32("11111111111111101110100000000000"), 21, 161},
 226     {bits32("11111111111111101001000000000000"), 20, 162},
 227     {bits32("11111111111111110110110000000000"), 22, 163},
 228     {bits32("11111111111111110111000000000000"), 22, 164},
 229     {bits32("11111111111111111101000000000000"), 23, 165},
 230     {bits32("11111111111111111101001000000000"), 23, 166},
 231     {bits32("11111111111111101111000000000000"), 21, 167},
 232     {bits32("11111111111111111101010000000000"), 23, 168},
 233     {bits32("11111111111111110111010000000000"), 22, 169},
 234     {bits32("11111111111111110111100000000000"), 22, 170},
 235     {bits32("11111111111111111111000000000000"), 24, 171},
 236     {bits32("11111111111111101111100000000000"), 21, 172},
 237     {bits32("11111111111111110111110000000000"), 22, 173},
 238     {bits32("11111111111111111101011000000000"), 23, 174},
 239     {bits32("11111111111111111101100000000000"), 23, 175},
 240     {bits32("11111111111111110000000000000000"), 21, 176},
 241     {bits32("11111111111111110000100000000000"), 21, 177},
 242     {bits32("11111111111111111000000000000000"), 22, 178},
 243     {bits32("11111111111111110001000000000000"), 21, 179},
 244     {bits32("11111111111111111101101000000000"), 23, 180},
 245     {bits32("11111111111111111000010000000000"), 22, 181},
 246     {bits32("11111111111111111101110000000000"), 23, 182},
 247     {bits32("11111111111111111101111000000000"), 23, 183},
 248     {bits32("11111111111111101010000000000000"), 20, 184},
 249     {bits32("11111111111111111000100000000000"), 22, 185},
 250     {bits32("11111111111111111000110000000000"), 22, 186},
 251     {bits32("11111111111111111001000000000000"), 22, 187},
 252     {bits32("11111111111111111110000000000000"), 23, 188},
 253     {bits32("11111111111111111001010000000000"), 22, 189},
 254     {bits32("11111111111111111001100000000000"), 22, 190},
 255     {bits32("11111111111111111110001000000000"), 23, 191},
 256     {bits32("11111111111111111111100000000000"), 26, 192},
 257     {bits32("11111111111111111111100001000000"), 26, 193},
 258     {bits32("11111111111111101011000000000000"), 20, 194},
 259     {bits32("11111111111111100010000000000000"), 19, 195},
 260     {bits32("11111111111111111001110000000000"), 22, 196},
 261     {bits32("11111111111111111110010000000000"), 23, 197},
 262     {bits32("11111111111111111010000000000000"), 22, 198},
 263     {bits32("11111111111111111111011000000000"), 25, 199},
 264     {bits32("11111111111111111111100010000000"), 26, 200},
 265     {bits32("11111111111111111111100011000000"), 26, 201},
 266     {bits32("11111111111111111111100100000000"), 26, 202},
 267     {bits32("11111111111111111111101111000000"), 27, 203},
 268     {bits32("11111111111111111111101111100000"), 27, 204},
 269     {bits32("11111111111111111111100101000000"), 26, 205},
 270     {bits32("11111111111111111111000100000000"), 24, 206},
 271     {bits32("11111111111111111111011010000000"), 25, 207},
 272     {bits32("11111111111111100100000000000000"), 19, 208},
 273     {bits32("11111111111111110001100000000000"), 21, 209},
 274     {bits32("11111111111111111111100110000000"), 26, 210},
 275     {bits32("11111111111111111111110000000000"), 27, 211},
 276     {bits32("11111111111111111111110000100000"), 27, 212},
 277     {bits32("11111111111111111111100111000000"), 26, 213},
 278     {bits32("11111111111111111111110001000000"), 27, 214},
 279     {bits32("11111111111111111111001000000000"), 24, 215},
 280     {bits32("11111111111111110010000000000000"), 21, 216},
 281     {bits32("11111111111111110010100000000000"), 21, 217},
 282     {bits32("11111111111111111111101000000000"), 26, 218},
 283     {bits32("11111111111111111111101001000000"), 26, 219},
 284     {bits32("11111111111111111111111111010000"), 28, 220},
 285     {bits32("11111111111111111111110001100000"), 27, 221},
 286     {bits32("11111111111111111111110010000000"), 27, 222},
 287     {bits32("11111111111111111111110010100000"), 27, 223},
 288     {bits32("11111111111111101100000000000000"), 20, 224},
 289     {bits32("11111111111111111111001100000000"), 24, 225},
 290     {bits32("11111111111111101101000000000000"), 20, 226},
 291     {bits32("11111111111111110011000000000000"), 21, 227},
 292     {bits32("11111111111111111010010000000000"), 22, 228},
 293     {bits32("11111111111111110011100000000000"), 21, 229},
 294     {bits32("11111111111111110100000000000000"), 21, 230},
 295     {bits32("11111111111111111110011000000000"), 23, 231},
 296     {bits32("11111111111111111010100000000000"), 22, 232},
 297     {bits32("11111111111111111010110000000000"), 22, 233},
 298     {bits32("11111111111111111111011100000000"), 25, 234},
 299     {bits32("11111111111111111111011110000000"), 25, 235},
 300     {bits32("11111111111111111111010000000000"), 24, 236},
 301     {bits32("11111111111111111111010100000000"), 24, 237},
 302     {bits32("11111111111111111111101010000000"), 26, 238},
 303     {bits32("11111111111111111110100000000000"), 23, 239},
 304     {bits32("11111111111111111111101011000000"), 26, 240},
 305     {bits32("11111111111111111111110011000000"), 27, 241},
 306     {bits32("11111111111111111111101100000000"), 26, 242},
 307     {bits32("11111111111111111111101101000000"), 26, 243},
 308     {bits32("11111111111111111111110011100000"), 27, 244},
 309     {bits32("11111111111111111111110100000000"), 27, 245},
 310     {bits32("11111111111111111111110100100000"), 27, 246},
 311     {bits32("11111111111111111111110101000000"), 27, 247},
 312     {bits32("11111111111111111111110101100000"), 27, 248},
 313     {bits32("11111111111111111111111111100000"), 28, 249},
 314     {bits32("11111111111111111111110110000000"), 27, 250},
 315     {bits32("11111111111111111111110110100000"), 27, 251},
 316     {bits32("11111111111111111111110111000000"), 27, 252},
 317     {bits32("11111111111111111111110111100000"), 27, 253},
 318     {bits32("11111111111111111111111000000000"), 27, 254},
 319     {bits32("11111111111111111111101110000000"), 26, 255},
 320     {bits32("11111111111111111111111111111100"), 30, 256},  // EOS
 321   };
 322   return std::vector<HpackHuffmanSymbol>(
 323       kHpackHuffmanCode,
 324       kHpackHuffmanCode + arraysize(kHpackHuffmanCode));
 325 }
 326
 327 const HpackHuffmanTable& ObtainHpackHuffmanTable() {
 328   return *SharedHpackHuffmanTable::GetInstance()->table;
 329 }
 330
 331 }  // namespace net