build_hpack_constants.py 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305
  1. #!/usr/bin/env python
  2. # Copyright 2014 The Chromium Authors. All rights reserved.
  3. # Use of this source code is governed by a BSD-style license that can be
  4. # found in the LICENSE file.
  5. """This script builds a table that has to be manully inserted into
  6. net/spdy/hpack/hpack_constants.cc. It also contains data that potentially has to
  7. be updated if the http hpack algorithm changes its constants."""
  8. import re
  9. # This is from
  10. # http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08
  11. # It may include dummy rows as long as those don't look too much like real
  12. # data.
  13. SPEC_DATA_DRAFT_08 = r"""
  14. code
  15. code as bits as hex len
  16. sym aligned to MSB aligned in
  17. to LSB bits
  18. ( 0) |11111111|11000 1ff8 [13]
  19. ( 1) |11111111|11111111|1011000 7fffd8 [23]
  20. ( 2) |11111111|11111111|11111110|0010 fffffe2 [28]
  21. ( 3) |11111111|11111111|11111110|0011 fffffe3 [28]
  22. ( 4) |11111111|11111111|11111110|0100 fffffe4 [28]
  23. ( 5) |11111111|11111111|11111110|0101 fffffe5 [28]
  24. ( 6) |11111111|11111111|11111110|0110 fffffe6 [28]
  25. ( 7) |11111111|11111111|11111110|0111 fffffe7 [28]
  26. ( 8) |11111111|11111111|11111110|1000 fffffe8 [28]
  27. ( 9) |11111111|11111111|11101010 ffffea [24]
  28. ( 10) |11111111|11111111|11111111|111100 3ffffffc [30]
  29. ( 11) |11111111|11111111|11111110|1001 fffffe9 [28]
  30. ( 12) |11111111|11111111|11111110|1010 fffffea [28]
  31. ( 13) |11111111|11111111|11111111|111101 3ffffffd [30]
  32. ( 14) |11111111|11111111|11111110|1011 fffffeb [28]
  33. ( 15) |11111111|11111111|11111110|1100 fffffec [28]
  34. ( 16) |11111111|11111111|11111110|1101 fffffed [28]
  35. ( 17) |11111111|11111111|11111110|1110 fffffee [28]
  36. ( 18) |11111111|11111111|11111110|1111 fffffef [28]
  37. ( 19) |11111111|11111111|11111111|0000 ffffff0 [28]
  38. ( 20) |11111111|11111111|11111111|0001 ffffff1 [28]
  39. ( 21) |11111111|11111111|11111111|0010 ffffff2 [28]
  40. ( 22) |11111111|11111111|11111111|111110 3ffffffe [30]
  41. ( 23) |11111111|11111111|11111111|0011 ffffff3 [28]
  42. ( 24) |11111111|11111111|11111111|0100 ffffff4 [28]
  43. ( 25) |11111111|11111111|11111111|0101 ffffff5 [28]
  44. ( 26) |11111111|11111111|11111111|0110 ffffff6 [28]
  45. ( 27) |11111111|11111111|11111111|0111 ffffff7 [28]
  46. ( 28) |11111111|11111111|11111111|1000 ffffff8 [28]
  47. ( 29) |11111111|11111111|11111111|1001 ffffff9 [28]
  48. ( 30) |11111111|11111111|11111111|1010 ffffffa [28]
  49. ( 31) |11111111|11111111|11111111|1011 ffffffb [28]
  50. ' ' ( 32) |010100 14 [ 6]
  51. '!' ( 33) |11111110|00 3f8 [10]
  52. '"' ( 34) |11111110|01 3f9 [10]
  53. '#' ( 35) |11111111|1010 ffa [12]
  54. '$' ( 36) |11111111|11001 1ff9 [13]
  55. '%' ( 37) |010101 15 [ 6]
  56. '&' ( 38) |11111000 f8 [ 8]
  57. ''' ( 39) |11111111|010 7fa [11]
  58. '(' ( 40) |11111110|10 3fa [10]
  59. ')' ( 41) |11111110|11 3fb [10]
  60. '*' ( 42) |11111001 f9 [ 8]
  61. '+' ( 43) |11111111|011 7fb [11]
  62. ',' ( 44) |11111010 fa [ 8]
  63. '-' ( 45) |010110 16 [ 6]
  64. '.' ( 46) |010111 17 [ 6]
  65. '/' ( 47) |011000 18 [ 6]
  66. '0' ( 48) |00000 0 [ 5]
  67. '1' ( 49) |00001 1 [ 5]
  68. '2' ( 50) |00010 2 [ 5]
  69. '3' ( 51) |011001 19 [ 6]
  70. '4' ( 52) |011010 1a [ 6]
  71. '5' ( 53) |011011 1b [ 6]
  72. '6' ( 54) |011100 1c [ 6]
  73. '7' ( 55) |011101 1d [ 6]
  74. '8' ( 56) |011110 1e [ 6]
  75. '9' ( 57) |011111 1f [ 6]
  76. ':' ( 58) |1011100 5c [ 7]
  77. ';' ( 59) |11111011 fb [ 8]
  78. '<' ( 60) |11111111|1111100 7ffc [15]
  79. '=' ( 61) |100000 20 [ 6]
  80. '>' ( 62) |11111111|1011 ffb [12]
  81. '?' ( 63) |11111111|00 3fc [10]
  82. '@' ( 64) |11111111|11010 1ffa [13]
  83. 'A' ( 65) |100001 21 [ 6]
  84. 'B' ( 66) |1011101 5d [ 7]
  85. 'C' ( 67) |1011110 5e [ 7]
  86. 'D' ( 68) |1011111 5f [ 7]
  87. 'E' ( 69) |1100000 60 [ 7]
  88. 'F' ( 70) |1100001 61 [ 7]
  89. 'G' ( 71) |1100010 62 [ 7]
  90. 'H' ( 72) |1100011 63 [ 7]
  91. 'I' ( 73) |1100100 64 [ 7]
  92. 'J' ( 74) |1100101 65 [ 7]
  93. 'K' ( 75) |1100110 66 [ 7]
  94. 'L' ( 76) |1100111 67 [ 7]
  95. 'M' ( 77) |1101000 68 [ 7]
  96. 'N' ( 78) |1101001 69 [ 7]
  97. 'O' ( 79) |1101010 6a [ 7]
  98. 'P' ( 80) |1101011 6b [ 7]
  99. 'Q' ( 81) |1101100 6c [ 7]
  100. 'R' ( 82) |1101101 6d [ 7]
  101. 'S' ( 83) |1101110 6e [ 7]
  102. 'T' ( 84) |1101111 6f [ 7]
  103. 'U' ( 85) |1110000 70 [ 7]
  104. 'V' ( 86) |1110001 71 [ 7]
  105. 'W' ( 87) |1110010 72 [ 7]
  106. 'X' ( 88) |11111100 fc [ 8]
  107. 'Y' ( 89) |1110011 73 [ 7]
  108. 'Z' ( 90) |11111101 fd [ 8]
  109. '[' ( 91) |11111111|11011 1ffb [13]
  110. '\' ( 92) |11111111|11111110|000 7fff0 [19]
  111. ']' ( 93) |11111111|11100 1ffc [13]
  112. '^' ( 94) |11111111|111100 3ffc [14]
  113. '_' ( 95) |100010 22 [ 6]
  114. '`' ( 96) |11111111|1111101 7ffd [15]
  115. 'a' ( 97) |00011 3 [ 5]
  116. 'b' ( 98) |100011 23 [ 6]
  117. 'c' ( 99) |00100 4 [ 5]
  118. 'd' (100) |100100 24 [ 6]
  119. 'e' (101) |00101 5 [ 5]
  120. 'f' (102) |100101 25 [ 6]
  121. 'g' (103) |100110 26 [ 6]
  122. 'h' (104) |100111 27 [ 6]
  123. 'i' (105) |00110 6 [ 5]
  124. 'j' (106) |1110100 74 [ 7]
  125. 'k' (107) |1110101 75 [ 7]
  126. 'l' (108) |101000 28 [ 6]
  127. 'm' (109) |101001 29 [ 6]
  128. 'n' (110) |101010 2a [ 6]
  129. 'o' (111) |00111 7 [ 5]
  130. 'p' (112) |101011 2b [ 6]
  131. 'q' (113) |1110110 76 [ 7]
  132. 'r' (114) |101100 2c [ 6]
  133. 's' (115) |01000 8 [ 5]
  134. 't' (116) |01001 9 [ 5]
  135. 'u' (117) |101101 2d [ 6]
  136. 'v' (118) |1110111 77 [ 7]
  137. 'w' (119) |1111000 78 [ 7]
  138. 'x' (120) |1111001 79 [ 7]
  139. 'y' (121) |1111010 7a [ 7]
  140. 'z' (122) |1111011 7b [ 7]
  141. '{' (123) |11111111|1111110 7ffe [15]
  142. '|' (124) |11111111|100 7fc [11]
  143. '}' (125) |11111111|111101 3ffd [14]
  144. '~' (126) |11111111|11101 1ffd [13]
  145. (127) |11111111|11111111|11111111|1100 ffffffc [28]
  146. (128) |11111111|11111110|0110 fffe6 [20]
  147. (129) |11111111|11111111|010010 3fffd2 [22]
  148. (130) |11111111|11111110|0111 fffe7 [20]
  149. (131) |11111111|11111110|1000 fffe8 [20]
  150. (132) |11111111|11111111|010011 3fffd3 [22]
  151. (133) |11111111|11111111|010100 3fffd4 [22]
  152. (134) |11111111|11111111|010101 3fffd5 [22]
  153. (135) |11111111|11111111|1011001 7fffd9 [23]
  154. (136) |11111111|11111111|010110 3fffd6 [22]
  155. (137) |11111111|11111111|1011010 7fffda [23]
  156. (138) |11111111|11111111|1011011 7fffdb [23]
  157. (139) |11111111|11111111|1011100 7fffdc [23]
  158. (140) |11111111|11111111|1011101 7fffdd [23]
  159. (141) |11111111|11111111|1011110 7fffde [23]
  160. (142) |11111111|11111111|11101011 ffffeb [24]
  161. (143) |11111111|11111111|1011111 7fffdf [23]
  162. (144) |11111111|11111111|11101100 ffffec [24]
  163. (145) |11111111|11111111|11101101 ffffed [24]
  164. (146) |11111111|11111111|010111 3fffd7 [22]
  165. (147) |11111111|11111111|1100000 7fffe0 [23]
  166. (148) |11111111|11111111|11101110 ffffee [24]
  167. (149) |11111111|11111111|1100001 7fffe1 [23]
  168. (150) |11111111|11111111|1100010 7fffe2 [23]
  169. (151) |11111111|11111111|1100011 7fffe3 [23]
  170. (152) |11111111|11111111|1100100 7fffe4 [23]
  171. (153) |11111111|11111110|11100 1fffdc [21]
  172. (154) |11111111|11111111|011000 3fffd8 [22]
  173. (155) |11111111|11111111|1100101 7fffe5 [23]
  174. (156) |11111111|11111111|011001 3fffd9 [22]
  175. (157) |11111111|11111111|1100110 7fffe6 [23]
  176. (158) |11111111|11111111|1100111 7fffe7 [23]
  177. (159) |11111111|11111111|11101111 ffffef [24]
  178. (160) |11111111|11111111|011010 3fffda [22]
  179. (161) |11111111|11111110|11101 1fffdd [21]
  180. (162) |11111111|11111110|1001 fffe9 [20]
  181. (163) |11111111|11111111|011011 3fffdb [22]
  182. (164) |11111111|11111111|011100 3fffdc [22]
  183. (165) |11111111|11111111|1101000 7fffe8 [23]
  184. (166) |11111111|11111111|1101001 7fffe9 [23]
  185. (167) |11111111|11111110|11110 1fffde [21]
  186. (168) |11111111|11111111|1101010 7fffea [23]
  187. (169) |11111111|11111111|011101 3fffdd [22]
  188. (170) |11111111|11111111|011110 3fffde [22]
  189. (171) |11111111|11111111|11110000 fffff0 [24]
  190. (172) |11111111|11111110|11111 1fffdf [21]
  191. (173) |11111111|11111111|011111 3fffdf [22]
  192. (174) |11111111|11111111|1101011 7fffeb [23]
  193. (175) |11111111|11111111|1101100 7fffec [23]
  194. (176) |11111111|11111111|00000 1fffe0 [21]
  195. (177) |11111111|11111111|00001 1fffe1 [21]
  196. (178) |11111111|11111111|100000 3fffe0 [22]
  197. (179) |11111111|11111111|00010 1fffe2 [21]
  198. (180) |11111111|11111111|1101101 7fffed [23]
  199. (181) |11111111|11111111|100001 3fffe1 [22]
  200. (182) |11111111|11111111|1101110 7fffee [23]
  201. (183) |11111111|11111111|1101111 7fffef [23]
  202. (184) |11111111|11111110|1010 fffea [20]
  203. (185) |11111111|11111111|100010 3fffe2 [22]
  204. (186) |11111111|11111111|100011 3fffe3 [22]
  205. (187) |11111111|11111111|100100 3fffe4 [22]
  206. (188) |11111111|11111111|1110000 7ffff0 [23]
  207. (189) |11111111|11111111|100101 3fffe5 [22]
  208. (190) |11111111|11111111|100110 3fffe6 [22]
  209. (191) |11111111|11111111|1110001 7ffff1 [23]
  210. (192) |11111111|11111111|11111000|00 3ffffe0 [26]
  211. (193) |11111111|11111111|11111000|01 3ffffe1 [26]
  212. (194) |11111111|11111110|1011 fffeb [20]
  213. (195) |11111111|11111110|001 7fff1 [19]
  214. (196) |11111111|11111111|100111 3fffe7 [22]
  215. (197) |11111111|11111111|1110010 7ffff2 [23]
  216. (198) |11111111|11111111|101000 3fffe8 [22]
  217. (199) |11111111|11111111|11110110|0 1ffffec [25]
  218. (200) |11111111|11111111|11111000|10 3ffffe2 [26]
  219. (201) |11111111|11111111|11111000|11 3ffffe3 [26]
  220. (202) |11111111|11111111|11111001|00 3ffffe4 [26]
  221. (203) |11111111|11111111|11111011|110 7ffffde [27]
  222. (204) |11111111|11111111|11111011|111 7ffffdf [27]
  223. (205) |11111111|11111111|11111001|01 3ffffe5 [26]
  224. (206) |11111111|11111111|11110001 fffff1 [24]
  225. (207) |11111111|11111111|11110110|1 1ffffed [25]
  226. (208) |11111111|11111110|010 7fff2 [19]
  227. (209) |11111111|11111111|00011 1fffe3 [21]
  228. (210) |11111111|11111111|11111001|10 3ffffe6 [26]
  229. (211) |11111111|11111111|11111100|000 7ffffe0 [27]
  230. (212) |11111111|11111111|11111100|001 7ffffe1 [27]
  231. (213) |11111111|11111111|11111001|11 3ffffe7 [26]
  232. (214) |11111111|11111111|11111100|010 7ffffe2 [27]
  233. (215) |11111111|11111111|11110010 fffff2 [24]
  234. (216) |11111111|11111111|00100 1fffe4 [21]
  235. (217) |11111111|11111111|00101 1fffe5 [21]
  236. (218) |11111111|11111111|11111010|00 3ffffe8 [26]
  237. (219) |11111111|11111111|11111010|01 3ffffe9 [26]
  238. (220) |11111111|11111111|11111111|1101 ffffffd [28]
  239. (221) |11111111|11111111|11111100|011 7ffffe3 [27]
  240. (222) |11111111|11111111|11111100|100 7ffffe4 [27]
  241. (223) |11111111|11111111|11111100|101 7ffffe5 [27]
  242. (224) |11111111|11111110|1100 fffec [20]
  243. (225) |11111111|11111111|11110011 fffff3 [24]
  244. (226) |11111111|11111110|1101 fffed [20]
  245. (227) |11111111|11111111|00110 1fffe6 [21]
  246. (228) |11111111|11111111|101001 3fffe9 [22]
  247. (229) |11111111|11111111|00111 1fffe7 [21]
  248. (230) |11111111|11111111|01000 1fffe8 [21]
  249. (231) |11111111|11111111|1110011 7ffff3 [23]
  250. (232) |11111111|11111111|101010 3fffea [22]
  251. (233) |11111111|11111111|101011 3fffeb [22]
  252. (234) |11111111|11111111|11110111|0 1ffffee [25]
  253. (235) |11111111|11111111|11110111|1 1ffffef [25]
  254. (236) |11111111|11111111|11110100 fffff4 [24]
  255. (237) |11111111|11111111|11110101 fffff5 [24]
  256. (238) |11111111|11111111|11111010|10 3ffffea [26]
  257. (239) |11111111|11111111|1110100 7ffff4 [23]
  258. (240) |11111111|11111111|11111010|11 3ffffeb [26]
  259. (241) |11111111|11111111|11111100|110 7ffffe6 [27]
  260. (242) |11111111|11111111|11111011|00 3ffffec [26]
  261. (243) |11111111|11111111|11111011|01 3ffffed [26]
  262. (244) |11111111|11111111|11111100|111 7ffffe7 [27]
  263. (245) |11111111|11111111|11111101|000 7ffffe8 [27]
  264. (246) |11111111|11111111|11111101|001 7ffffe9 [27]
  265. (247) |11111111|11111111|11111101|010 7ffffea [27]
  266. (248) |11111111|11111111|11111101|011 7ffffeb [27]
  267. (249) |11111111|11111111|11111111|1110 ffffffe [28]
  268. (250) |11111111|11111111|11111101|100 7ffffec [27]
  269. (251) |11111111|11111111|11111101|101 7ffffed [27]
  270. (252) |11111111|11111111|11111101|110 7ffffee [27]
  271. (253) |11111111|11111111|11111101|111 7ffffef [27]
  272. (254) |11111111|11111111|11111110|000 7fffff0 [27]
  273. (255) |11111111|11111111|11111011|10 3ffffee [26]
  274. EOS (256) |11111111|11111111|11111111|111111 3fffffff [30]
  275. """
  276. count = 0
  277. spec_lines = SPEC_DATA_DRAFT_08.splitlines()
  278. for l in spec_lines:
  279. m = re.match(
  280. r"^\s*('.+'|EOS)? \( *(\d+)\) \|([10\|]+) +\w+ \[ ?(\d+)\]", l)
  281. if m:
  282. g = m.groups()
  283. spec_comment = g[0]
  284. spec_bitstring = g[2]
  285. bitstring = spec_bitstring.replace('|','').ljust(32,'0')
  286. bitvalue = int(bitstring, 2)
  287. bitcount = g[3]
  288. valueid = g[1]
  289. comment = ' // %s' % spec_bitstring
  290. if spec_comment:
  291. comment = ' // %3s %s' % (spec_comment, spec_bitstring)
  292. else:
  293. comment = ' // %s' % spec_bitstring
  294. print(' {0x%08xul, %02s, %03s},%s' % (
  295. bitvalue, bitcount, valueid, comment))
  296. assert int(valueid) == count, "Expected data for %s, got %s." % (count,
  297. valueid)
  298. count += 1
  299. print("Total: %s" % count)
  300. assert count == 257, "Expected 257 values, got %d." % count