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