| // 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 <bitset> |
| |
| #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<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
| scoped_ptr<HpackHuffmanTable> 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<SharedHpackHuffmanTable>::get(); |
| } |
| |
| scoped_ptr<const HpackHuffmanTable> 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<HpackHuffmanSymbol> HpackHuffmanCode() { |
| const HpackHuffmanSymbol kHpackHuffmanCode[] = { |
| {bits32("11111111111111111110111010000000"), 26, 0}, |
| {bits32("11111111111111111110111011000000"), 26, 1}, |
| {bits32("11111111111111111110111100000000"), 26, 2}, |
| {bits32("11111111111111111110111101000000"), 26, 3}, |
| {bits32("11111111111111111110111110000000"), 26, 4}, |
| {bits32("11111111111111111110111111000000"), 26, 5}, |
| {bits32("11111111111111111111000000000000"), 26, 6}, |
| {bits32("11111111111111111111000001000000"), 26, 7}, |
| {bits32("11111111111111111111000010000000"), 26, 8}, |
| {bits32("11111111111111111111000011000000"), 26, 9}, |
| {bits32("11111111111111111111000100000000"), 26, 10}, |
| {bits32("11111111111111111111000101000000"), 26, 11}, |
| {bits32("11111111111111111111000110000000"), 26, 12}, |
| {bits32("11111111111111111111000111000000"), 26, 13}, |
| {bits32("11111111111111111111001000000000"), 26, 14}, |
| {bits32("11111111111111111111001001000000"), 26, 15}, |
| {bits32("11111111111111111111001010000000"), 26, 16}, |
| {bits32("11111111111111111111001011000000"), 26, 17}, |
| {bits32("11111111111111111111001100000000"), 26, 18}, |
| {bits32("11111111111111111111001101000000"), 26, 19}, |
| {bits32("11111111111111111111001110000000"), 26, 20}, |
| {bits32("11111111111111111111001111000000"), 26, 21}, |
| {bits32("11111111111111111111010000000000"), 26, 22}, |
| {bits32("11111111111111111111010001000000"), 26, 23}, |
| {bits32("11111111111111111111010010000000"), 26, 24}, |
| {bits32("11111111111111111111010011000000"), 26, 25}, |
| {bits32("11111111111111111111010100000000"), 26, 26}, |
| {bits32("11111111111111111111010101000000"), 26, 27}, |
| {bits32("11111111111111111111010110000000"), 26, 28}, |
| {bits32("11111111111111111111010111000000"), 26, 29}, |
| {bits32("11111111111111111111011000000000"), 26, 30}, |
| {bits32("11111111111111111111011001000000"), 26, 31}, |
| {bits32("00110000000000000000000000000000"), 5, 32}, // ' ' |
| {bits32("11111111111000000000000000000000"), 13, 33}, // '!' |
| {bits32("11111000000000000000000000000000"), 9, 34}, // '"' |
| {bits32("11111111111100000000000000000000"), 14, 35}, // '#' |
| {bits32("11111111111110000000000000000000"), 15, 36}, // '$' |
| {bits32("01111000000000000000000000000000"), 6, 37}, // '%' |
| {bits32("11001000000000000000000000000000"), 7, 38}, // '&' |
| {bits32("11111111111010000000000000000000"), 13, 39}, // ''' |
| {bits32("11111110100000000000000000000000"), 10, 40}, // '(' |
| {bits32("11111000100000000000000000000000"), 9, 41}, // ')' |
| {bits32("11111110110000000000000000000000"), 10, 42}, // '*' |
| {bits32("11111111000000000000000000000000"), 10, 43}, // '+' |
| {bits32("11001010000000000000000000000000"), 7, 44}, // ',' |
| {bits32("11001100000000000000000000000000"), 7, 45}, // '-' |
| {bits32("01111100000000000000000000000000"), 6, 46}, // '.' |
| {bits32("00111000000000000000000000000000"), 5, 47}, // '/' |
| {bits32("00000000000000000000000000000000"), 4, 48}, // '0' |
| {bits32("00010000000000000000000000000000"), 4, 49}, // '1' |
| {bits32("00100000000000000000000000000000"), 4, 50}, // '2' |
| {bits32("01000000000000000000000000000000"), 5, 51}, // '3' |
| {bits32("10000000000000000000000000000000"), 6, 52}, // '4' |
| {bits32("10000100000000000000000000000000"), 6, 53}, // '5' |
| {bits32("10001000000000000000000000000000"), 6, 54}, // '6' |
| {bits32("10001100000000000000000000000000"), 6, 55}, // '7' |
| {bits32("10010000000000000000000000000000"), 6, 56}, // '8' |
| {bits32("10010100000000000000000000000000"), 6, 57}, // '9' |
| {bits32("10011000000000000000000000000000"), 6, 58}, // ':' |
| {bits32("11101100000000000000000000000000"), 8, 59}, // ';' |
| {bits32("11111111111111100000000000000000"), 17, 60}, // '<' |
| {bits32("10011100000000000000000000000000"), 6, 61}, // '=' |
| {bits32("11111111111110100000000000000000"), 15, 62}, // '>' |
| {bits32("11111111010000000000000000000000"), 10, 63}, // '?' |
| {bits32("11111111111111000000000000000000"), 15, 64}, // '@' |
| {bits32("11001110000000000000000000000000"), 7, 65}, // 'A' |
| {bits32("11101101000000000000000000000000"), 8, 66}, // 'B' |
| {bits32("11101110000000000000000000000000"), 8, 67}, // 'C' |
| {bits32("11010000000000000000000000000000"), 7, 68}, // 'D' |
| {bits32("11101111000000000000000000000000"), 8, 69}, // 'E' |
| {bits32("11010010000000000000000000000000"), 7, 70}, // 'F' |
| {bits32("11010100000000000000000000000000"), 7, 71}, // 'G' |
| {bits32("11111001000000000000000000000000"), 9, 72}, // 'H' |
| {bits32("11110000000000000000000000000000"), 8, 73}, // 'I' |
| {bits32("11111001100000000000000000000000"), 9, 74}, // 'J' |
| {bits32("11111010000000000000000000000000"), 9, 75}, // 'K' |
| {bits32("11111010100000000000000000000000"), 9, 76}, // 'L' |
| {bits32("11010110000000000000000000000000"), 7, 77}, // 'M' |
| {bits32("11011000000000000000000000000000"), 7, 78}, // 'N' |
| {bits32("11110001000000000000000000000000"), 8, 79}, // 'O' |
| {bits32("11110010000000000000000000000000"), 8, 80}, // 'P' |
| {bits32("11111011000000000000000000000000"), 9, 81}, // 'Q' |
| {bits32("11111011100000000000000000000000"), 9, 82}, // 'R' |
| {bits32("11011010000000000000000000000000"), 7, 83}, // 'S' |
| {bits32("10100000000000000000000000000000"), 6, 84}, // 'T' |
| {bits32("11110011000000000000000000000000"), 8, 85}, // 'U' |
| {bits32("11111100000000000000000000000000"), 9, 86}, // 'V' |
| {bits32("11111100100000000000000000000000"), 9, 87}, // 'W' |
| {bits32("11110100000000000000000000000000"), 8, 88}, // 'X' |
| {bits32("11111101000000000000000000000000"), 9, 89}, // 'Y' |
| {bits32("11111101100000000000000000000000"), 9, 90}, // 'Z' |
| {bits32("11111111100000000000000000000000"), 11, 91}, // '[' |
| {bits32("11111111111111111111011010000000"), 26, 92}, // '\' |
| {bits32("11111111101000000000000000000000"), 11, 93}, // ']' |
| {bits32("11111111111101000000000000000000"), 14, 94}, // '^' |
| {bits32("11011100000000000000000000000000"), 7, 95}, // '_' |
| {bits32("11111111111111111000000000000000"), 18, 96}, // '`' |
| {bits32("01001000000000000000000000000000"), 5, 97}, // 'a' |
| {bits32("11011110000000000000000000000000"), 7, 98}, // 'b' |
| {bits32("01010000000000000000000000000000"), 5, 99}, // 'c' |
| {bits32("10100100000000000000000000000000"), 6, 100}, // 'd' |
| {bits32("01011000000000000000000000000000"), 5, 101}, // 'e' |
| {bits32("11100000000000000000000000000000"), 7, 102}, // 'f' |
| {bits32("10101000000000000000000000000000"), 6, 103}, // 'g' |
| {bits32("10101100000000000000000000000000"), 6, 104}, // 'h' |
| {bits32("01100000000000000000000000000000"), 5, 105}, // 'i' |
| {bits32("11110101000000000000000000000000"), 8, 106}, // 'j' |
| {bits32("11110110000000000000000000000000"), 8, 107}, // 'k' |
| {bits32("10110000000000000000000000000000"), 6, 108}, // 'l' |
| {bits32("10110100000000000000000000000000"), 6, 109}, // 'm' |
| {bits32("10111000000000000000000000000000"), 6, 110}, // 'n' |
| {bits32("01101000000000000000000000000000"), 5, 111}, // 'o' |
| {bits32("10111100000000000000000000000000"), 6, 112}, // 'p' |
| {bits32("11111110000000000000000000000000"), 9, 113}, // 'q' |
| {bits32("11000000000000000000000000000000"), 6, 114}, // 'r' |
| {bits32("11000100000000000000000000000000"), 6, 115}, // 's' |
| {bits32("01110000000000000000000000000000"), 5, 116}, // 't' |
| {bits32("11100010000000000000000000000000"), 7, 117}, // 'u' |
| {bits32("11100100000000000000000000000000"), 7, 118}, // 'v' |
| {bits32("11100110000000000000000000000000"), 7, 119}, // 'w' |
| {bits32("11101000000000000000000000000000"), 7, 120}, // 'x' |
| {bits32("11101010000000000000000000000000"), 7, 121}, // 'y' |
| {bits32("11110111000000000000000000000000"), 8, 122}, // 'z' |
| {bits32("11111111111111101000000000000000"), 17, 123}, // '{' |
| {bits32("11111111110000000000000000000000"), 12, 124}, // '|' |
| {bits32("11111111111111110000000000000000"), 17, 125}, // '}' |
| {bits32("11111111110100000000000000000000"), 12, 126}, // '~' |
| {bits32("11111111111111111111011011000000"), 26, 127}, |
| {bits32("11111111111111111111011100000000"), 26, 128}, |
| {bits32("11111111111111111111011101000000"), 26, 129}, |
| {bits32("11111111111111111111011110000000"), 26, 130}, |
| {bits32("11111111111111111111011111000000"), 26, 131}, |
| {bits32("11111111111111111111100000000000"), 26, 132}, |
| {bits32("11111111111111111111100001000000"), 26, 133}, |
| {bits32("11111111111111111111100010000000"), 26, 134}, |
| {bits32("11111111111111111111100011000000"), 26, 135}, |
| {bits32("11111111111111111111100100000000"), 26, 136}, |
| {bits32("11111111111111111111100101000000"), 26, 137}, |
| {bits32("11111111111111111111100110000000"), 26, 138}, |
| {bits32("11111111111111111111100111000000"), 26, 139}, |
| {bits32("11111111111111111111101000000000"), 26, 140}, |
| {bits32("11111111111111111111101001000000"), 26, 141}, |
| {bits32("11111111111111111111101010000000"), 26, 142}, |
| {bits32("11111111111111111111101011000000"), 26, 143}, |
| {bits32("11111111111111111111101100000000"), 26, 144}, |
| {bits32("11111111111111111111101101000000"), 26, 145}, |
| {bits32("11111111111111111111101110000000"), 26, 146}, |
| {bits32("11111111111111111111101111000000"), 26, 147}, |
| {bits32("11111111111111111111110000000000"), 26, 148}, |
| {bits32("11111111111111111111110001000000"), 26, 149}, |
| {bits32("11111111111111111111110010000000"), 26, 150}, |
| {bits32("11111111111111111111110011000000"), 26, 151}, |
| {bits32("11111111111111111111110100000000"), 26, 152}, |
| {bits32("11111111111111111111110101000000"), 26, 153}, |
| {bits32("11111111111111111111110110000000"), 26, 154}, |
| {bits32("11111111111111111111110111000000"), 26, 155}, |
| {bits32("11111111111111111111111000000000"), 26, 156}, |
| {bits32("11111111111111111111111001000000"), 26, 157}, |
| {bits32("11111111111111111111111010000000"), 26, 158}, |
| {bits32("11111111111111111111111011000000"), 26, 159}, |
| {bits32("11111111111111111111111100000000"), 26, 160}, |
| {bits32("11111111111111111111111101000000"), 26, 161}, |
| {bits32("11111111111111111111111110000000"), 26, 162}, |
| {bits32("11111111111111111111111111000000"), 26, 163}, |
| {bits32("11111111111111111100000000000000"), 25, 164}, |
| {bits32("11111111111111111100000010000000"), 25, 165}, |
| {bits32("11111111111111111100000100000000"), 25, 166}, |
| {bits32("11111111111111111100000110000000"), 25, 167}, |
| {bits32("11111111111111111100001000000000"), 25, 168}, |
| {bits32("11111111111111111100001010000000"), 25, 169}, |
| {bits32("11111111111111111100001100000000"), 25, 170}, |
| {bits32("11111111111111111100001110000000"), 25, 171}, |
| {bits32("11111111111111111100010000000000"), 25, 172}, |
| {bits32("11111111111111111100010010000000"), 25, 173}, |
| {bits32("11111111111111111100010100000000"), 25, 174}, |
| {bits32("11111111111111111100010110000000"), 25, 175}, |
| {bits32("11111111111111111100011000000000"), 25, 176}, |
| {bits32("11111111111111111100011010000000"), 25, 177}, |
| {bits32("11111111111111111100011100000000"), 25, 178}, |
| {bits32("11111111111111111100011110000000"), 25, 179}, |
| {bits32("11111111111111111100100000000000"), 25, 180}, |
| {bits32("11111111111111111100100010000000"), 25, 181}, |
| {bits32("11111111111111111100100100000000"), 25, 182}, |
| {bits32("11111111111111111100100110000000"), 25, 183}, |
| {bits32("11111111111111111100101000000000"), 25, 184}, |
| {bits32("11111111111111111100101010000000"), 25, 185}, |
| {bits32("11111111111111111100101100000000"), 25, 186}, |
| {bits32("11111111111111111100101110000000"), 25, 187}, |
| {bits32("11111111111111111100110000000000"), 25, 188}, |
| {bits32("11111111111111111100110010000000"), 25, 189}, |
| {bits32("11111111111111111100110100000000"), 25, 190}, |
| {bits32("11111111111111111100110110000000"), 25, 191}, |
| {bits32("11111111111111111100111000000000"), 25, 192}, |
| {bits32("11111111111111111100111010000000"), 25, 193}, |
| {bits32("11111111111111111100111100000000"), 25, 194}, |
| {bits32("11111111111111111100111110000000"), 25, 195}, |
| {bits32("11111111111111111101000000000000"), 25, 196}, |
| {bits32("11111111111111111101000010000000"), 25, 197}, |
| {bits32("11111111111111111101000100000000"), 25, 198}, |
| {bits32("11111111111111111101000110000000"), 25, 199}, |
| {bits32("11111111111111111101001000000000"), 25, 200}, |
| {bits32("11111111111111111101001010000000"), 25, 201}, |
| {bits32("11111111111111111101001100000000"), 25, 202}, |
| {bits32("11111111111111111101001110000000"), 25, 203}, |
| {bits32("11111111111111111101010000000000"), 25, 204}, |
| {bits32("11111111111111111101010010000000"), 25, 205}, |
| {bits32("11111111111111111101010100000000"), 25, 206}, |
| {bits32("11111111111111111101010110000000"), 25, 207}, |
| {bits32("11111111111111111101011000000000"), 25, 208}, |
| {bits32("11111111111111111101011010000000"), 25, 209}, |
| {bits32("11111111111111111101011100000000"), 25, 210}, |
| {bits32("11111111111111111101011110000000"), 25, 211}, |
| {bits32("11111111111111111101100000000000"), 25, 212}, |
| {bits32("11111111111111111101100010000000"), 25, 213}, |
| {bits32("11111111111111111101100100000000"), 25, 214}, |
| {bits32("11111111111111111101100110000000"), 25, 215}, |
| {bits32("11111111111111111101101000000000"), 25, 216}, |
| {bits32("11111111111111111101101010000000"), 25, 217}, |
| {bits32("11111111111111111101101100000000"), 25, 218}, |
| {bits32("11111111111111111101101110000000"), 25, 219}, |
| {bits32("11111111111111111101110000000000"), 25, 220}, |
| {bits32("11111111111111111101110010000000"), 25, 221}, |
| {bits32("11111111111111111101110100000000"), 25, 222}, |
| {bits32("11111111111111111101110110000000"), 25, 223}, |
| {bits32("11111111111111111101111000000000"), 25, 224}, |
| {bits32("11111111111111111101111010000000"), 25, 225}, |
| {bits32("11111111111111111101111100000000"), 25, 226}, |
| {bits32("11111111111111111101111110000000"), 25, 227}, |
| {bits32("11111111111111111110000000000000"), 25, 228}, |
| {bits32("11111111111111111110000010000000"), 25, 229}, |
| {bits32("11111111111111111110000100000000"), 25, 230}, |
| {bits32("11111111111111111110000110000000"), 25, 231}, |
| {bits32("11111111111111111110001000000000"), 25, 232}, |
| {bits32("11111111111111111110001010000000"), 25, 233}, |
| {bits32("11111111111111111110001100000000"), 25, 234}, |
| {bits32("11111111111111111110001110000000"), 25, 235}, |
| {bits32("11111111111111111110010000000000"), 25, 236}, |
| {bits32("11111111111111111110010010000000"), 25, 237}, |
| {bits32("11111111111111111110010100000000"), 25, 238}, |
| {bits32("11111111111111111110010110000000"), 25, 239}, |
| {bits32("11111111111111111110011000000000"), 25, 240}, |
| {bits32("11111111111111111110011010000000"), 25, 241}, |
| {bits32("11111111111111111110011100000000"), 25, 242}, |
| {bits32("11111111111111111110011110000000"), 25, 243}, |
| {bits32("11111111111111111110100000000000"), 25, 244}, |
| {bits32("11111111111111111110100010000000"), 25, 245}, |
| {bits32("11111111111111111110100100000000"), 25, 246}, |
| {bits32("11111111111111111110100110000000"), 25, 247}, |
| {bits32("11111111111111111110101000000000"), 25, 248}, |
| {bits32("11111111111111111110101010000000"), 25, 249}, |
| {bits32("11111111111111111110101100000000"), 25, 250}, |
| {bits32("11111111111111111110101110000000"), 25, 251}, |
| {bits32("11111111111111111110110000000000"), 25, 252}, |
| {bits32("11111111111111111110110010000000"), 25, 253}, |
| {bits32("11111111111111111110110100000000"), 25, 254}, |
| {bits32("11111111111111111110110110000000"), 25, 255}, |
| {bits32("11111111111111111110111000000000"), 25, 256}, // EOS |
| }; |
| return std::vector<HpackHuffmanSymbol>( |
| kHpackHuffmanCode, |
| kHpackHuffmanCode + arraysize(kHpackHuffmanCode)); |
| } |
| |
| const HpackHuffmanTable& ObtainHpackHuffmanTable() { |
| return *SharedHpackHuffmanTable::GetInstance()->table; |
| } |
| |
| } // namespace net |