idnits 2.17.1 draft-rpeon-httpbis-header-compression-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 51 instances of too long lines in the document, the longest one being 79 characters in excess of 72. ** The abstract seems to contain references ([RFC2616]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 9 instances of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 289 has weird spacing: '... string strin...' == Line 290 has weird spacing: '... string strin...' == Line 795 has weird spacing: '... size time ...' == Line 867 has weird spacing: '... size time ...' == Line 1204 has weird spacing: '... sym as ...' == (1 more instance...) == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (Mar 18, 2013) is 4057 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 666 -- Looks like a reference, but probably isn't: '4' on line 1521 -- Looks like a reference, but probably isn't: '6' on line 1588 -- Looks like a reference, but probably isn't: '15122' on line 226 -- Looks like a reference, but probably isn't: '76' on line 226 -- Looks like a reference, but probably isn't: '3' on line 226 -- Looks like a reference, but probably isn't: '0' on line 665 -- Looks like a reference, but probably isn't: '27' on line 1366 -- Looks like a reference, but probably isn't: '12' on line 1562 -- Looks like a reference, but probably isn't: '14' on line 1595 -- Looks like a reference, but probably isn't: '15' on line 1565 -- Looks like a reference, but probably isn't: '7' on line 1586 -- Looks like a reference, but probably isn't: '10' on line 1561 -- Looks like a reference, but probably isn't: '5' on line 1727 -- Looks like a reference, but probably isn't: '9' on line 1593 -- Looks like a reference, but probably isn't: '18' on line 1567 -- Looks like a reference, but probably isn't: '17' on line 1596 -- Looks like a reference, but probably isn't: '13' on line 1510 -- Looks like a reference, but probably isn't: '8' on line 1592 -- Looks like a reference, but probably isn't: '11' on line 1564 -- Looks like a reference, but probably isn't: '19' on line 1301 -- Looks like a reference, but probably isn't: '26' on line 1631 -- Looks like a reference, but probably isn't: '16' on line 1597 -- Looks like a reference, but probably isn't: '25' on line 1726 ** Obsolete normative reference: RFC 2616 (Obsoleted by RFC 7230, RFC 7231, RFC 7232, RFC 7233, RFC 7234, RFC 7235) Summary: 4 errors (**), 0 flaws (~~), 9 warnings (==), 26 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 HTTPbis Working Group R. Peon 3 Internet-Draft Google, Inc 4 Intended status: Informational Mar 18, 2013 5 Expires: September 19, 2013 7 Header Delta-Compression for HTTP/2.0 8 draft-rpeon-httpbis-header-compression-03 10 Abstract 12 This document describes a mechanism for compressing streams of groups 13 of key-value pairs, often known as Headers in an HTTP session. See 14 RFC 2616 [RFC2616] or successors for more information about headers. 16 Status of this Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on September 19, 2013. 33 Copyright Notice 35 Copyright (c) 2013 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 51 2. How it works . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 3. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 4. Header pre-processing . . . . . . . . . . . . . . . . . . . . 4 54 4.1. Mapping the first-line . . . . . . . . . . . . . . . . . . 4 55 4.2. Mapping HTTP key-values . . . . . . . . . . . . . . . . . 4 56 5. Compressor and Decompressor State . . . . . . . . . . . . . . 5 57 6. Header Block Wire Format . . . . . . . . . . . . . . . . . . . 6 58 7. String Encoding . . . . . . . . . . . . . . . . . . . . . . . 8 59 8. Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 8 60 9. Decompressor algorithm . . . . . . . . . . . . . . . . . . . . 9 61 10. Compression . . . . . . . . . . . . . . . . . . . . . . . . . 12 62 11. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 63 11.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 15 64 11.2. Example Serialization . . . . . . . . . . . . . . . . . . 16 65 12. Unfinished components . . . . . . . . . . . . . . . . . . . . 25 66 13. Security Considerations . . . . . . . . . . . . . . . . . . . 25 67 14. Requirements Notation . . . . . . . . . . . . . . . . . . . . 25 68 15. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 69 16. Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . 25 70 17. Appendix B . . . . . . . . . . . . . . . . . . . . . . . . . . 27 71 18. Appendix C . . . . . . . . . . . . . . . . . . . . . . . . . . 32 72 19. Normative References . . . . . . . . . . . . . . . . . . . . . 38 73 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 38 75 1. Overview 77 There have been several problems pointed out with the use of the gzip 78 compressor in SPDY [SPDY]. The biggest of these problems is that it 79 is possible for a smart attacker to inject content into the 80 compressor, and then to test hypotheses about the prior contents of 81 the compressor by examining the output size after each such content 82 injection. The other issue is that gzip often consumes more CPU than 83 many would like, especially in situations where one is doing forward 84 or reverse proxying. The compressor proposed here intends to solve 85 the first issue and significantly mitigate the second, while 86 providing compression that is not too much worse than gzip. 88 2. How it works 90 The 'delta' compressor works by examining the difference between what 91 it is told to compress and the state that it has stored about what it 92 knows about the past. The previous state is encoded in two separate 93 pieces: An LRU of key-value pairs which the compressor 'saw' in the 94 past (including a static group of key-value pairs which every 95 compressor is assumed to have seen), and a set of references into the 96 LRU which is called a header-group, which the compressor uses to 97 determine what has changed between the current input and the past 98 input. 99 It then encodes this difference by changing the header-group by 100 adding references to stored key-values, and it removes references to 101 key-values which should no longer be part of the output. If a key- 102 value exists in the to-be-compressed data, but is not present in the 103 LRU, then the LRU is modified by having new data added. When new 104 data is added, a reference to that new data is added to the header- 105 group. The mechanism of adding new data takes two forms: Adding an 106 entire new key-value, or by referring to the key part of a stored 107 key-value, and providing a new value. 108 When the LRU has reached its size limit, The oldest elements are 109 popped off the end, and, any reference to that element is removed. 110 All keys are assumed to have been lowercased, and if not, will be. 112 3. Definitions 114 user-agent: The program or device which a human interacts with 115 directly and which typically initiates the transport layer 116 connection or session 118 client: Synonym for user-agent 120 server: The computer or device which typically accepts a connection, 121 stores, and serves data 123 proxy: An entity acting as a server for the client, and a client for 124 the server 126 header: A complete set of key-value pairs, either request-headers, 127 or response-headers as defined in RFC2616 [RFC2616] section 5.3 128 or 6.2, respectively 130 4. Header pre-processing 132 4.1. Mapping the first-line 134 Before the data is input into the compressor (which works only on 135 key-value pairs), the first line of the HTTP message must be made 136 into key-value pairs. 138 Requests are mapped as follows: 139 "METHOD PATH VERSION" becomes: 141 [ 142 (":method", "METHOD"), 143 (":path", "PATH"), 144 (":version", "VERSION") 145 ] 147 Responses are mapped as follows: 148 "VERSION STATUS-CODE PHRASE" becomes: 150 [ 151 (":version", "VERSION"), 152 (":status", "STATUS-CODE"), 153 (":status-text", "PHRASE") 154 ] 156 4.2. Mapping HTTP key-values 158 The rest of the HTTP key-values are simply added to the key-values as 159 mapped from the first-line, with the keys made to be all lowercase, 160 and with cookies split into crumbs by breaking apart the cookie 161 string on semicolons and treating each as if it were a separate 162 header-line. 164 As an example, the following key-value pairs: 166 Host: www.foo.com 167 User-Agent: Browser/1.x (FooOS; Bar) baz 168 Accept-Language: en-US,en;q=0.5 169 Cookie: foo;bar; baz 171 become: 173 [ 174 ("host", "www.foo.com") 175 ("user-agent", "Browser/1.x (FooOS; Bar) baz"), 176 ("accept-language", "en-US,en;q=0.5"), 177 ("cookie", "foo"), 178 ("cookie", "bar"), 179 ("cookie", "baz") 180 ] 182 5. Compressor and Decompressor State 184 The header delta de/compression scheme consists of a state machine 185 which executes opcodes, emits output, and modifies internal, 186 persistent, state. The de/compressor state consists of: 188 static_entries: 189 a number of static (unchanging) entries consisting of key-value 190 pairs. These are listed in appendix A. 191 e.g. static_entries=[ ("key1", "val1"), ("key2", "val2), ...] 192 an lru-idx references into the static key-value pairs if the 193 value of the lru-idx is < len(static-entries) 194 static_entries[lru_idx] 196 lru: 197 a queue of key-value pairs 198 e.g. lru = deque([(RefCntString("key1"), "val1"), 199 (RefCntstring("key2", "val2")), ...]) 200 an lru-idx references a value in the lru if the lru-idx is >= 201 len(static_entries). The mapping of an lru-idx to a offset 202 from the front of the LRU is as follows: 204 if lru.first_idx > lru_idx: 205 queue_idx = 2**16 - lru.first_idx + lru_idx - len(static_entries) 206 else: 207 queue_idx = lru_idx - lru.first_idx 209 The oldest elements of the LRU are popped before inserting a 210 new value if either: 212 Adding a new entry would exceed the maximum allowable 213 length 215 Adding a new entry would exceed the maximum allowable 216 byte length 218 header_groups: (default-size: 1)(max: 255) 219 a map of group-id to set of lru-idx. An lru-idx is a reference 220 into either the static key-value pairs or the lru's key-value 221 pairs. The maximum number of header-groups is limited by 222 default to 1, unless a higher-level of the protocol changes 223 this. The maximum number of header_groups is 255. It is not 224 currently allowed to assert that there are '0' allowed header 225 groups. 226 e.g. header_groups = {0: set([1,4,6,15122]), 1: set([6,76,3], 227 ...)} 229 lru.first_idx: 230 an int indicating the lru-idx of the oldest element in the 231 queue of key-value pairs 233 max_byte_size: (default: 4k) (max:2**32-1) 234 an int indicating the maximum allowable amount of storage used 235 by the strings of the queue's key-value pairs. Unless a 236 higher-level of the protocol changes this, this is assumed to 237 be 4k 239 max_lru_entries: (default: 1024) (max:2**16-1) 240 an int indicating the maximum allowable number of key-value 241 pairs in the queue. Unless a higher-level of the protocol 242 changes this, this is assumed to be 1024 244 lru.length: 245 an int indicating the total number of key-value pairs currently 246 stored in the lru 248 lru.stored_byte_size: 249 an int indicating the total number of bytes of storage used by 250 strings in the queue. Note that the bytes in a ref-counted 251 string are counted only once, regardless of how many times that 252 string is referenced. 254 6. Header Block Wire Format 256 The decompressor is fed a header-block which may span multiple 257 HEADERs frames by the HTTP/2 framing layer, the format of which 258 follows: 260 All ints are in network byte order. 262 header-block: group-id 263 ( (ekvsto-opcode ekvsto-count ekvsto-field{ekvsto-count})* | 264 (eclone-opcode eclone-count eclone-field{eclone-count})* | 265 (etrang-opcode etrang-count etrang-field{etrang-count})* | 266 (strang-opcode etrang-count strang-field{etrang-count})* | 267 (etoggl-opcode etoggl-count etoggl-field{etoggl-count})* | 268 (stoggl-opcode stoggl-count stoggl-field{stoggl-count})* )* 269 (clone-opcode clone-count clone-field{clone-count})* 270 (kvsto-opcode kvsto-count kvsto-field{kvsto-count})* 271 ; 273 group-id: UINT8; 274 etoggl-count: UINT8; 275 stoggl-count: UINT8; 276 etrang-count: UINT8; 277 strang-count: UINT8; 278 eclone-count: UINT8; 279 sclone-count: UINT8; 280 ekvsto-count: UINT8; 281 skvsto-count: UINT8; 283 stoggl-field: lru-idx; 284 etoggl-field: lru-idx; 285 strang-field: lru-idx lru-idx; 286 etrang-field: lru-idx lru-idx; 287 eclone-field: lru-idx string; 288 sclone-field: lru-idx string; 289 ekvsto-field: string string; 290 skvsto-field: string string; 292 stoggl-opcode: UINT8(0x00); 293 etoggl-opcode: UINT8(0x01); 294 strang-opcode: UINT8(0x02); 295 etrang-opcode: UINT8(0x03); 296 skvsto-opcode: UINT8(0x04); 297 ekvsto-opcode: UINT8(0x05); 298 sclone-opcode: UINT8(0x06); 299 eclone-opcode: UINT8(0x07); 301 lru_idx: UINT16; 303 string: (HUFFMAN-ENCODED-CHAR)* HUFFMAN-EOF 304 padding-to-nearest-byte-boundary; 305 padding-to-nearest-byte-boundary: 0{0-7}; 307 7. String Encoding 309 Strings are huffman encoded [HUFF] using a canonical huffman coding 310 [CANON]. In the future, the opcode byte will be permuted to allow 311 alternate encodings, such as raw text, binary, or perhaps other 312 options. 314 The huffman code is constructed by taking the frequency-tables in 315 Appendix B, adding 1 to all entries, then generating a canonical 316 huffman coding. If/while this results in a code with a max-length of 317 greater than 32 bits, divide all frequencies by two, capping the 318 minimum frequency at '1', and regenerate until the max code-length is 319 32 bits or less. The EOF symbol, when decoded, is represented as 320 256, which allows for any 8-bit value to be encoded and decoded. 322 8. Operations 324 For all operations below, the 's' prefix stands for 'State 325 modifying', whereas the 'e' prefix stands for 'Ephemeral', and does 326 not modify state. 328 The *kvsto family of opcodes encode a new key-value entirely by 329 providing a new string for key and a new string for val. 331 The *clone family of opcodes encode a backreference to the key part 332 of a pre-existing key-value from either the static-entries or the 333 lru, and a new string value. 335 The *toggl family of opcodes encode a backreference to an entire key- 336 value from either the static-entries, or the lru. 338 The *trang family of opcodes is the same as the toggle family, except 339 that it encodes a range of indices instead of a single index 341 With four families of opcodes, and two variations (ephemeral vs 342 state-changing) per family, we have eight valid opcodes: 344 skvsto: (Stateful Key-Value STOre) 345 state-modifying kvsto. The new key and value are inserted into 346 the headers and also inserted into the LRU. 348 ekvsto: (Ephemeral Key-Value STOre) 349 ephemeral, non-state-modifying kvsto. The new key and value 350 are inserted into the headers but the LRU is untouched. 352 sclone (Stateful key CLONE): 353 state-modifying clone. The key part of the referenced key- 354 value is paired with the new value and inserted into the 355 headers and also inserted into the LRU 357 eclone (Ephemeral key CLONE): 358 ephemeral, non-state-modifying clone. The key part of the 359 referenced key-value is paired with the new value and inserted 360 into the headers. No persistent state is modified. 362 stoggl (Stateful TOGGLe): 363 state-modifying toggle. If the index exists in the current 364 header group, it will be turned off, else it will be turned on. 366 etoggl (Ephemeral TOGGLe): 367 ephemeral, non-state-modifying toggle. If the provided index 368 does not exist in the current header group after all stoggles 369 have modified it, then the key-value as referenced by the 370 provided index will be present in the output, else, that index 371 of the current header group will be temporarily suppressed and 372 will not be included in the headers 374 strang (Stateful Toggle RANGe): 375 encodes a range of stoggls 377 etrang (Ephemeral ToggleRANGe): 378 encodes a range of etoggls 380 9. Decompressor algorithm 382 The pseudo-code below provides a definition of how the header-block 383 is executed by the decompressor. 385 ParseAndExecuteHeaderBlock(header_block): 386 store_later = deque() 387 etoggles = set() 388 stoggles = set() 389 headers = dict() 390 # the HTTP/2 framing layer determines when the header_block 391 # has finished reading. 392 group_id = header_block.read_uint8() 393 current_header_group = header_groups[group_id] 395 while data in header_block: 396 opcode = header_block.read_uint8() 397 num_fields = header_block.read_uint8() 398 if opcode == stoggl: 400 repeat num_fields times: 401 lru_idx = header_block.read_uint16() 402 stoggles = set_symmetric_difference(stoggles, [lru_idx]) 403 elif opcode == etoggl: 404 repeat num_fields times: 405 lru_idx = header_block.read_uint16() 406 etoggles = set_symmetric_difference(etoggles, [lru_idx]) 407 elif opcode == strang: 408 repeat num_fields times: 409 lru_idx_first = header_block.read_uint16() 410 lru_idx_last = header_block.read_uint16() 411 for lru_idx in (lru_idx_first, lru_idx_last) inclusive: 412 stoggles = set_symmetric_difference(stoggles, [lru_idx]) 413 stoggles.add(lru_idx) 414 elif opcode == etrang: 415 repeat num_fields times: 416 lru_idx_first = header_block.read_uint16() 417 lru_idx_last = header_block.read_uint16() 418 for lru_idx in (lru_idx_first, lru_idx_last) inclusive: 419 etoggles = set_symmetric_difference(etoggles, [lru_idx]) 420 elif opcode == sclone: 421 repeat num_fields times: 422 lru_idx = header_block.read_uint16() 423 val = header_block.read_huffman_string() 424 kv = lookup_idx_from_static_entries_or_lru(lru_idx) 425 AddToCurrentHeaders(headers, kv.key, val) 426 store_later.append(KV(kv.key, val)) 427 elif opcode == eclone: 428 repeat num_fields times: 429 lru_idx = header_block.read_uint16() 430 val = header_block.read_huffman_string() 431 kv = lookup_idx_from_static_entries_or_lru(lru_idx) 432 AddToCurrentHeaders(headers, kv.key, val) 433 elif opcode == skvsto: 434 repeat num_fields times: 435 key = header_block.read_huffman_string() 436 val = header_block.read_huffman_string() 437 AddToCurrentHeaders(headers, key, val) 438 store_later.append(KV(key, val)) 439 elif opcode == ekvsto: 440 repeat num_fields times: 441 key = header_block.read_huffman_string() 442 val = header_block.read_huffman_string() 443 AddToCurrentHeaders(headers, key, val) 445 # store the state changes to the header-group. 446 current_header_group = \ 447 set_symmetric_difference(current_header_group, stoggles) 449 kv_references = set_symmetric_difference(current_header_group, 450 etoggles) 452 for lru_idx in sorted(kv_references): 453 kv = lookup_idx_from_static_entries_or_lru(lru_idx) 454 AddToCurrentHeaders(headers, kv.key, kv.val) 456 if 'cookie' in headers: 457 headers['cookie'] = headers['cookie'].replace('\0', '; ') 459 older_headers = [] 460 for lru_idx in sorted(current_header_group): 461 # sorting by idx is suboptimal when the idxs wrap 2**16. 462 # As a refinement, we probably want to change this in the 463 # future to something which sorts based on the order in 464 # which the elements were first mentioned, which can be 465 # done by a smart implementation without actually sorting. 466 kv = lookup_idx_from_static_entries_or_lru(lru_idx) 467 older_headers.append(kv) 468 store_later = older_headers + store_later 470 # make state changes to the LRU. Note that this may remove 471 # items from the header-group if elements that the header-group 472 # refers to are removed from the LRU 473 for kv in store_later: 474 new_lru_idx = lru.store(kv.key, kv.val) 476 return headers 478 lru.clear(): 479 while length > 0: 480 pop_oldest() 482 lru.store(key, val): 483 reserve_size = val.size + key.size 484 if max_lru_entries == 0 or 485 max_byte_size < reserve_size): 486 lru.clear() 487 return -1 488 while length + 1 >= max_lru_entries: 489 pop_oldest() 490 while true: 491 reserve_size = val.size 492 if key.refcnt == 1: 493 reserve_size += key.size 494 if stored_byte_size + reserve_size < max_byte_size: 495 break 496 pop_oldest() 498 push(KV(key, val)) 499 new_lru_idx = lru.first + length 500 if new_lru_idx >= 2**16: 501 new_lru_idx -= 2**16 502 new_lru_idx += static_entries.size: 503 return new_lru_idx 505 lru.pop_oldest(): 506 kv = queue.front() 507 length -= 1 508 if kv.key.refcnt == 1: 509 stored_byte_size -= kv.key.size 510 stored_byte_size -= kv.val.size 511 for header_group in header_groups: 512 if first_idx in header_group: 513 header_group.remove(first_idx) 514 first_idx = get_next_idx(first_idx) 515 queue.pop_front() 517 lru.push(kv): 518 length += 1 519 if kv.key.refcnt == 1: 520 stored_byte_size += kv.key.size 521 stored_byte_size += kv.val.size 522 queue.push_back(kv) 524 lru.get_next_idx(idx): 525 idx += 1 526 if idx >= 2**16 - 1: 527 return decompressor.static_entries.size 528 return idx 530 lookup_idx_from_static_entries_or_lru(lru_idx): 531 if lru_idx < static_entries.size: 532 return static_entries[lru_idx]: 533 if lru.first_idx > lru_idx: 534 queue_idx = 2**16 - lru.first_idx + lru_idx - static_entries.size 535 else: 536 queue_idx = lru_idx - lru.first_idx 537 return lru.queue[queue_idx] 539 10. Compression 541 The compressor generates a sequence of instructions which the 542 decompressor executes. There are various ways by which the 543 compressor can determine how to construct these operations. Pseudo- 544 code follows showing one approach. group_id is defined by the sender, 545 but must always be less than the maximum allowed number. A 546 reasonable implementation might assign the same group_id to a set of 547 headers which are likely to be similar, for instance those which go 548 to the same hostname or the same hostname suffix. 550 # assumptions: headers is a dict(), where multiple key:values with 551 # the same key are encoded as key:value1\0value2\0value3... 552 # group_id is provided by some other implementation-dependent 553 # code 555 # This compressor does not use all of the opcodes and serves simply 556 # as an example of a workable, if suboptimal, implementation 557 MakeOperations(self, headers, group_id): 558 headers_set = set() 559 for (key, val) in headers: 560 splittoken = '\0' 561 if key == 'cookie': 562 splittoken = ';' 563 for partial_val in split(val, ';'): 564 headers_set.add( (key, partial_val) ) 565 # Note that this discards duplicates. 566 # If we decide we care about that generate an 'ekvsto' or 567 # 'eclone' for that (duplicate) key-value here. 569 keep_set = set() 570 done_set = set() 571 for idx in header_groups[group_id]: 572 kv = lookup_idx_from_static_entries_or_lru(idx) 573 if kv in headers_set: 574 # If the KV referenced by the idx in the header-group 575 # is also in the to-be-compressed headers, then we 576 # keep using that reference (don't remove it from the 577 # header-group) 578 keep_set.add(idx) # we want to keep this one 579 headers_set.remove(kv) 580 else: 581 # If we're not finding the KV referenced by the idx in 582 # the header-group in the to-be-compressed-header, then 583 # this idx needs to be removed from the header-group. 584 done_set.add(idx) # we'll want to remove it 586 instructions = dict() 587 toggls = set() 588 clones = [] 589 kvstos = [] 590 erefs = [] 591 for (key, val) in headers_set: 592 # The following 'if' block is a demonstration of an 593 # optimization-- since path and referer are rarely 594 # backreferenced, and since they are often large and 595 # they would, if included in the LRU, cause other entries 596 # to be expired from the LRU, we ensure that these don't 597 # get stored in the LRU by emitting an 'ephemeral' operation 598 if key in [":path", "referer"]: 599 instructions['ekvsto'].append( (key, val) ) 600 continue 601 # FindEntryIdx looks for a matching key-value in the LRU, and then 602 # in the static-entries, recording the first matching key it finds 603 # while searching for the whole match. If it does find a whole 604 # match then v_idx will be valid. If it finds an entry with a key 605 # which matches, then k_idx will be valid. 606 (k_idx, v_idx) = FindEntryIdx(key, val) 607 if both k_idx and v_idx are valid: 608 # if we found a index for all of the kv, we'll generate 609 # a new toggle which backreferences that entire kv. 610 toggls.add(v_idx) 611 elif only k_idx is valid: 612 # Otherwise, if we did't find all of the kv pre-existing, 613 # but there was something that already had that key, 614 # generate a clone, which backreferences the key and provides 615 # a new value. 616 instructions['sclone'].append( (k_idx, val) ) 617 else: 618 # Otherwise, we'll need to store a new key and value, both. 619 instructions['skvstos'].append( (key, val) ) 621 full_toggl_list = union(toggls, done_set) 622 # convert runs of toggls into trangs 623 (trangs, toggls) = ComputeTrangsFromRawToggles(full_toggl_list) 624 instructions['stoggl'] = toggls 625 instructions['strang'] = trangs 627 header_block = SerializeInstructions(instructions, group_id) 629 # Execute the instructions just like you would when decompressing. 630 # We're throwing away the computed headers here, because all 631 # we care about is the side-effects to the header_groups and the 632 # lru from executing the generated instructions. 633 ParseAndExecuteHeaderBlock(header_block) 634 return header_block 636 SerializeInstructions(instructions, group_id): 637 outbuf.write_uint8(group_id) 638 for opcode in ['stoggl', 'etoggl', 639 'strang', 'etrang', 640 'eclone', 'ekvsto', 641 'sclone', 'skvsto']: 642 if not opcode in instructions: 643 continue 644 ops_idx = 0 645 ops_len = len(instructions[opcode]) 646 while ops_len > ops_idx: 647 ops_to_go = ops_len - ops_idx 648 outbuf.write_uint8(OpcodeToOpcodeVal(opcode)) 649 # a value of '0' in this field means '1'. 650 # a value of '255' in this field means '256', 651 # thus, subtract one from the actual value when 652 # preparing to write to the wire. 653 outbuf.write_uint8(min(256, ops_to_go) - 1) 654 orig_idx = ops_idx 655 for i in xrange(ops_to_go): 656 if opcode in ['stoggl', 'etoggl']: 657 outbuf.write_uint16(instructions[ops_idx]) 658 elif opcode in ['strang', 'etrang']: 659 outbuf.write_uint16(instructions[ops_idx][0]) 660 outbuf.write_uint16(instructions[ops_idx][1]) 661 elif opcide in ['sclone', 'eclone']: 662 outbuf.write_uint16(instructions[ops_idx][0]) 663 outbuf.encode_and_write_string(instructions[ops_idx][1]) 664 elif opcode in ['skvsto', 'ekvsto']: 665 outbuf.encode_and_write_string(instructions[ops_idx][0]) 666 outbuf.encode_and_write_string(instructions[ops_idx][1]) 667 ops_idx += 1 668 return outbuf 670 If the resulting output buffer is larger than the maximum allowed 671 frame size, then the buffer shall be split into maximum-allowed- 672 payload-size or smaller sections, and sent in separate HEADERS 673 frames, with only the last indicating that the frame is finished by 674 asserting the FRAME_FINISHED flag. 676 11. Example 678 11.1. Background 680 Here is a simple example showing an input, the changing part of the 681 compressor state, and an ascii-ified version of what would be 682 serialized on the wire. 684 GET / HTTP/1.0 685 Host: www.foo.com 686 User-Agent: bar-ua baz stuff 687 Accept-Language: en-US,en;q=0.5 689 The first stage of processing is to break the first line into key- 690 value pairs. The first line becomes: 692 [ 693 (":method": "GET"), 694 (":path": "/"), 695 (":version": "HTTP/1.0") 696 ] 698 This gets integrated with the rest of the headers, becoming: 700 [ 701 (":method", "GET"), 702 (":path", "/"), 703 (":version", "HTTP/1.0"), 704 ("host", "www.foo.com"), 705 ("user-agent", "bar-ua baz stuff"), 706 ("accept-language", "en-US,en;q=0.5"), 707 ] 709 The compressor now goes through each key-value, determining if it is 710 already present in the header-group, in the LRU or static state, and 711 determines what it needs to emit. 713 11.2. Example Serialization 715 This is sample output from a program which implements the compression 716 specification above. It prints out the stream ID, then the group ID, 717 then the instructions that the encoder created, then the serialized 718 form of these instructions, followed last by the decompressed output. 720 * http2-demo: 2 req messages 721 ################################################################################ 722 # delta2 request 1 (of 2) for http2-demo 724 stream_id: 1234 group_id: 1 725 {'opcode': 'eclone', 'index': 0, 'val': '/http2_sample.html'} 726 {'opcode': 'stoggl', 'index': 1} 727 {'opcode': 'stoggl', 'index': 3} 728 {'opcode': 'sclone', 'index': 38, 'val': 'no-cache'} 729 {'opcode': 'sclone', 'index': 10, 'val': 'ISO-8859-1,utf-8;q=0.7,*;q=0.3'} 730 {'opcode': 'sclone', 'index': 11, 'val': 'gzip,deflate,sdch'} 731 {'opcode': 'sclone', 'index': 9, 'val': 'text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8'} 732 {'opcode': 'sclone', 'index': 16, 'val': 'no-cache'} 733 {'opcode': 'sclone', 'index': 4, 'val': 'http2-demo'} 734 {'opcode': 'sclone', 'index': 12, 'val': 'en-US,en;q=0.8'} 735 {'opcode': 'sclone', 'index': 51, 'val': 'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31'} 737 00 FE 08 01 80 00 04 D2 01 05 00 00 00 0C C8 9E | ................ 738 9B A2 AD 5F A0 9B 32 D7 49 00 00 01 00 01 00 03 | ..._..2.I....... 739 04 07 00 26 6B A7 5A 97 98 C8 00 0A F6 FD 3E 33 | ...&k.Z.......>3 740 F3 E7 4D 73 A3 F8 D8 B1 9F 9F A3 F5 69 CD 57 F1 | ..Ms........i.W. 741 FF 5E 8F D5 A7 35 12 00 0B CB F6 C7 FF 18 0E 3A | .^...5.........: 742 28 87 F8 8E 0B CE 40 00 09 21 F2 20 CC B5 D3 F8 | (.....@..!. .... 743 53 DF A3 16 A2 63 9A 1E 59 96 BA 7F DF 96 BA 7F | S....c..Y....... 744 0A 7B F4 62 D4 4C 73 43 CB 5D 3D 1F AB 4E 6A FF | .{.b.LsC.]=..Nj. 745 8F FA 0F FA F4 7E AD 39 B9 C8 00 10 6B A7 5A 97 | .....~.9....k.Z. 746 98 C8 00 04 CC 89 E9 9F 01 D5 D2 00 0C 16 CF F6 | ................ 747 FA 7F 02 DF 47 EA D3 9B 9C 80 00 33 F7 BB F6 CD | ....G......3.... 748 34 50 52 63 FF B7 FC 7E 50 8F 47 FB 7B 98 DD BC | 4PRc...~P.G.{... 749 BF DB CB 9F 2B B9 71 FF 9F F6 EC 7B F4 1F C0 DF | ....+.q....{.... 750 FE 98 41 4D 15 1A 84 7F B7 FC 7F AF 67 D7 DF EE | ..AM........g... 751 FE 3F DB 46 78 0F FB 7A C5 7E 0E FF 9F F6 EE CE | .?.Fx..z.~...... 752 0E D4 41 3C 8C 73 23 8A 0E 64 F3 FF 6F A2 B1 54 | ..A<.s#..d..o..T 753 18 14 D1 51 A8 44 80 | ...Q.D. 755 ###### decompressed ###### 756 get /http2_sample.html HTTP/1.1 757 accept-language: en-US,en;q=0.8 758 accept-encoding: gzip,deflate,sdch 759 accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8 760 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 761 :scheme: http 762 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 763 pragma: no-cache 764 cache-control: no-cache 765 host: http2-demo 767 ################################################################################ 768 # delta2 request 2 (of 2) for http2-demo 770 stream_id: 1234 group_id: 1 771 {'opcode': 'eclone', 'index': 0, 'val': '/s/http2_fractal.jpg'} 772 {'opcode': 'sclone', 'index': 42, 'val': 'http://http2-demo/http2_sample.html'} 773 {'opcode': 'sclone', 'index': 70, 'val': '*/*'} 774 {'opcode': 'strang', 'index': 69, 'index_start': 67} 775 {'opcode': 'strang', 'index': 74, 'index_start': 71} 776 00 3E 08 01 80 00 04 D2 01 05 00 00 00 08 86 64 | .>.............d 777 4F 4D D8 C1 4B 25 68 6E AF CA 40 04 01 00 2A CC | OM..K%hn..@...*. 778 89 F6 00 66 44 F4 CF 80 EA E0 CC 89 E9 BA 2A D5 | ...fD.........*. 779 FA 09 B3 2D 74 90 00 46 FF A0 FF A9 00 02 01 00 | ...-t..F........ 780 45 00 43 00 4A 00 47 | E.C.J.G 782 ###### decompressed ###### 783 get /s/http2_fractal.jpg HTTP/1.1 784 accept-language: en-US,en;q=0.8 785 pragma: no-cache 786 accept: */* 787 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 788 :scheme: http 789 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 790 referer: http://http2-demo/http2_sample.html 791 cache-control: no-cache 792 host: http2-demo 793 accept-encoding: gzip,deflate,sdch 795 size time | ratio min max std 796 delta2 334 0.00 | 1.00 1.00 1.00 0.00 798 * http2-demo: 2 res messages 799 ################################################################################ 800 # delta2 response 1 (of 2) for http2-demo 802 stream_id: 1234 group_id: 1 803 {'opcode': 'stoggl', 'index': 6} 804 {'opcode': 'sclone', 'index': 16, 'val': 'public, max-age=3600000000'} 805 {'opcode': 'sclone', 'index': 27, 'val': 'Fri, 1 Jan 2100 12:00:00 GMT'} 806 {'opcode': 'sclone', 'index': 18, 'val': 'gzip'} 807 {'opcode': 'sclone', 'index': 13, 'val': 'bytes'} 808 {'opcode': 'sclone', 'index': 52, 'val': 'Accept-Encoding'} 809 {'opcode': 'sclone', 'index': 19, 'val': '797'} 810 {'opcode': 'sclone', 'index': 34, 'val': 'Thu, 08 Nov 2012 17:24:16 GMT'} 811 {'opcode': 'sclone', 'index': 24, 'val': 'Tue, 12 Mar 2013 23:12:44 GMT'} 812 {'opcode': 'sclone', 'index': 44, 'val': 'Apache/2.2.22 (Ubuntu)'} 813 {'opcode': 'sclone', 'index': 23, 'val': 'text/html'} 815 00 99 08 01 80 00 04 D2 01 00 00 00 06 04 09 00 | ................ 816 10 C3 3D BC 6D AE 60 E5 0F 39 E1 BE 3A 91 40 88 | ..=.m.`..9..:.@. 817 88 88 8C 80 00 1B EC C6 D9 80 83 B6 17 01 90 88 | ................ 818 11 B8 45 C2 21 4D 4F 90 00 12 DF FB B7 09 00 00 | ..E.!MO......... 819 0D DB E9 94 79 C8 00 34 D7 5D 71 C3 29 FA EE AE | ....y..4.]q.)... 820 FB 2D BB 7C 80 00 13 5B 57 20 00 22 7F 0C E6 01 | .-.|...[W .".... 821 60 77 5F E2 06 24 60 4B 71 A5 C5 40 53 53 E4 00 | `w_..$`Kq..@SS.. 822 18 7E 71 98 08 C2 A8 62 06 24 80 34 38 8D C9 48 | .~q....b.$.48..H 823 53 53 E4 00 2C D7 84 2B E1 1E 83 D2 7A 4C C3 D7 | SS..,..+....zL.. 824 F5 DB 9D D9 67 EC 90 00 17 CA 3E 79 74 70 CB 97 | ....g.....>ytp.. 825 19 00 | .. 827 ###### decompressed ###### 828 HTTP/1.1 200 ? 829 content-length: 797 830 content-encoding: gzip 831 accept-ranges: bytes 832 expires: Fri, 1 Jan 2100 12:00:00 GMT 833 vary: Accept-Encoding 834 server: Apache/2.2.22 (Ubuntu) 835 last-modified: Thu, 08 Nov 2012 17:24:16 GMT 836 cache-control: public, max-age=3600000000 837 date: Tue, 12 Mar 2013 23:12:44 GMT 838 content-type: text/html 840 ################################################################################ 841 # delta2 response 2 (of 2) for http2-demo 843 stream_id: 1234 group_id: 1 844 {'opcode': 'stoggl', 'index': 69} 845 {'opcode': 'sclone', 'index': 75, 'val': 'image/jpeg'} 846 {'opcode': 'sclone', 'index': 71, 'val': '365'} 847 {'opcode': 'sclone', 'index': 72, 'val': 'Tue, 23 Oct 2012 02:26:33 GMT'} 848 {'opcode': 'strang', 'index': 67, 'index_start': 66} 849 {'opcode': 'strang', 'index': 74, 'index_start': 73} 851 00 35 08 01 80 00 04 D2 01 00 00 00 45 04 02 00 | .5..........E... 852 4B B7 94 37 C7 A3 F1 84 77 C8 00 47 45 0A 90 00 | K..7....w..GE... 853 48 7E 71 98 0D 01 DF 5E 40 62 46 02 6E 3A 1C 84 | H~q....^@bF.n:.. 854 05 35 3E 40 02 01 00 43 00 42 00 4A 00 49 | .5>@...C.B.J.I 856 ###### decompressed ###### 857 HTTP/1.1 200 ? 858 content-length: 365 859 accept-ranges: bytes 860 expires: Fri, 1 Jan 2100 12:00:00 GMT 861 server: Apache/2.2.22 (Ubuntu) 862 last-modified: Tue, 23 Oct 2012 02:26:33 GMT 863 cache-control: public, max-age=3600000000 864 date: Tue, 12 Mar 2013 23:12:44 GMT 865 content-type: image/jpeg 867 size time | ratio min max std 868 delta2 224 0.00 | 1.00 1.00 1.00 0.00 870 * http2-demo1: 5 req messages 871 ################################################################################ 872 # delta2 request 1 (of 5) for http2-demo1 874 stream_id: 1234 group_id: 2 875 {'opcode': 'eclone', 'index': 0, 'val': '/s/0.png'} 876 {'opcode': 'sclone', 'index': 81, 'val': 'http2-demo1'} 877 {'opcode': 'strang', 'index': 80, 'index_start': 75} 878 {'opcode': 'strang', 'index': 85, 'index_start': 82} 880 00 20 08 01 80 00 04 D2 02 05 00 00 00 08 81 CC | . .............. 881 F6 E5 20 04 00 00 51 CC 89 E9 9F 01 D5 C8 90 02 | .. ...Q......... 882 01 00 50 00 4B 00 55 00 52 | ..P.K.U.R 884 ###### decompressed ###### 885 get /s/0.png HTTP/1.1 886 accept-language: en-US,en;q=0.8 887 accept: */* 888 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 889 :scheme: http 890 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 891 referer: http://http2-demo/http2_sample.html 892 pragma: no-cache 893 cache-control: no-cache 894 host: http2-demo1 895 accept-encoding: gzip,deflate,sdch 897 ################################################################################ 898 # delta2 request 2 (of 5) for http2-demo1 900 stream_id: 1234 group_id: 2 901 {'opcode': 'eclone', 'index': 0, 'val': '/s/6.png'} 902 {'opcode': 'stoggl', 'index': 96} 904 00 0E 08 01 80 00 04 D2 02 05 00 00 00 08 87 23 | ...............# 905 3D B9 48 00 00 00 60 | =.H...` 907 ###### decompressed ###### 908 get /s/6.png HTTP/1.1 909 accept-language: en-US,en;q=0.8 910 accept: */* 911 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 912 :scheme: http 913 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 914 referer: http://http2-demo/http2_sample.html 915 pragma: no-cache 916 cache-control: no-cache 917 host: http2-demo1 918 accept-encoding: gzip,deflate,sdch 920 ################################################################################ 921 # delta2 request 3 (of 5) for http2-demo1 923 stream_id: 1234 group_id: 2 924 {'opcode': 'eclone', 'index': 0, 'val': '/s/12.png'} 926 00 0B 08 01 80 00 04 D2 02 05 00 00 00 08 82 12 | ................ 927 67 B7 29 00 | g.). 929 ###### decompressed ###### 930 get /s/12.png HTTP/1.1 931 accept-language: en-US,en;q=0.8 932 accept: */* 933 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 934 :scheme: http 935 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 936 referer: http://http2-demo/http2_sample.html 937 pragma: no-cache 938 cache-control: no-cache 939 host: http2-demo1 940 accept-encoding: gzip,deflate,sdch 942 ################################################################################ 943 # delta2 request 4 (of 5) for http2-demo1 945 stream_id: 1234 group_id: 2 946 {'opcode': 'eclone', 'index': 0, 'val': '/s/18.png'} 948 00 0B 08 01 80 00 04 D2 02 05 00 00 00 08 82 39 | ...............9 949 99 ED CA 40 | ...@ 951 ###### decompressed ###### 952 get /s/18.png HTTP/1.1 953 accept-language: en-US,en;q=0.8 954 accept: */* 955 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 956 :scheme: http 957 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 958 referer: http://http2-demo/http2_sample.html 959 pragma: no-cache 960 cache-control: no-cache 961 host: http2-demo1 962 accept-encoding: gzip,deflate,sdch 964 ################################################################################ 965 # delta2 request 5 (of 5) for http2-demo1 967 stream_id: 1234 group_id: 2 968 {'opcode': 'eclone', 'index': 0, 'val': '/s/24.png'} 970 00 0B 08 01 80 00 04 D2 02 05 00 00 00 08 82 78 | ...............x 971 99 ED CA 40 | ...@ 973 ###### decompressed ###### 974 get /s/24.png HTTP/1.1 975 accept-language: en-US,en;q=0.8 976 accept: */* 977 user-agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.31 (KHTML, like Gecko) Chrome/26.0.1410.28 Safari/537.31 978 :scheme: http 979 accept-charset: ISO-8859-1,utf-8;q=0.7,*;q=0.3 980 referer: http://http2-demo/http2_sample.html 981 pragma: no-cache 982 cache-control: no-cache 983 host: http2-demo1 984 accept-encoding: gzip,deflate,sdch 986 * http2-demo1: 5 res messages 987 ################################################################################ 988 # delta2 response 1 (of 5) for http2-demo1 990 stream_id: 1234 group_id: 2 991 {'opcode': 'sclone', 'index': 82, 'val': 'image/png'} 992 {'opcode': 'sclone', 'index': 84, 'val': 'Sat, 23 Jun 2012 02:03:47 GMT'} 993 {'opcode': 'sclone', 'index': 83, 'val': '338'} 994 {'opcode': 'strang', 'index': 81, 'index_start': 76} 996 00 2C 08 01 80 00 04 D2 02 04 02 00 52 B7 94 37 | .,..........R..7 997 C7 A3 0B B7 C8 00 54 D9 0C A6 03 40 76 E7 70 18 | ......T....@v.p. 998 91 80 9B 85 0E 4A C2 9A 9F 20 00 53 42 19 20 02 | .....J... .SB. . 999 00 00 51 00 4C | ..Q.L 1001 ###### decompressed ###### 1002 HTTP/1.1 200 ? 1003 content-length: 338 1004 accept-ranges: bytes 1005 expires: Fri, 1 Jan 2100 12:00:00 GMT 1006 server: Apache/2.2.22 (Ubuntu) 1007 last-modified: Sat, 23 Jun 2012 02:03:47 GMT 1008 cache-control: public, max-age=3600000000 1009 date: Tue, 12 Mar 2013 23:12:44 GMT 1010 content-type: image/png 1012 ################################################################################ 1013 # delta2 response 2 (of 5) for http2-demo1 1015 stream_id: 1234 group_id: 2 1016 {'opcode': 'strang', 'index': 93, 'index_start': 91} 1018 00 06 08 01 80 00 04 D2 02 02 00 00 5D 00 5B | ............].[ 1020 ###### decompressed ###### 1021 HTTP/1.1 200 ? 1022 content-length: 338 1023 accept-ranges: bytes 1024 expires: Fri, 1 Jan 2100 12:00:00 GMT 1025 server: Apache/2.2.22 (Ubuntu) 1026 last-modified: Sat, 23 Jun 2012 02:03:47 GMT 1027 cache-control: public, max-age=3600000000 1028 date: Tue, 12 Mar 2013 23:12:44 GMT 1029 content-type: image/png 1031 ################################################################################ 1032 # delta2 response 3 (of 5) for http2-demo1 1034 stream_id: 1234 group_id: 2 1035 {'opcode': 'stoggl', 'index': 93} 1036 {'opcode': 'sclone', 'index': 102, 'val': '358'} 1038 00 0B 08 01 80 00 04 D2 02 00 00 00 5D 04 00 00 | ............]... 1039 66 42 99 20 | fB. 1041 ###### decompressed ###### 1042 HTTP/1.1 200 ? 1043 content-length: 358 1044 accept-ranges: bytes 1045 expires: Fri, 1 Jan 2100 12:00:00 GMT 1046 server: Apache/2.2.22 (Ubuntu) 1047 last-modified: Sat, 23 Jun 2012 02:03:47 GMT 1048 cache-control: public, max-age=3600000000 1049 date: Tue, 12 Mar 2013 23:12:44 GMT 1050 content-type: image/png 1051 ################################################################################ 1052 # delta2 response 4 (of 5) for http2-demo1 1054 stream_id: 1234 group_id: 2 1055 {'opcode': 'sclone', 'index': 111, 'val': '397'} 1057 00 07 08 01 80 00 04 D2 02 04 00 00 6F 43 57 20 | ............oCW 1059 ###### decompressed ###### 1060 HTTP/1.1 200 ? 1061 content-length: 397 1062 accept-ranges: bytes 1063 expires: Fri, 1 Jan 2100 12:00:00 GMT 1064 server: Apache/2.2.22 (Ubuntu) 1065 last-modified: Sat, 23 Jun 2012 02:03:47 GMT 1066 cache-control: public, max-age=3600000000 1067 date: Tue, 12 Mar 2013 23:12:44 GMT 1068 content-type: image/png 1070 ################################################################################ 1071 # delta2 response 5 (of 5) for http2-demo1 1073 stream_id: 1234 group_id: 2 1074 {'opcode': 'stoggl', 'index': 92} 1075 {'opcode': 'sclone', 'index': 119, 'val': 'Sat, 23 Jun 2012 02:03:46 GMT'} 1076 {'opcode': 'sclone', 'index': 120, 'val': '345'} 1078 00 20 08 01 80 00 04 D2 02 00 00 00 5C 04 01 00 | . ..........\... 1079 77 D9 0C A6 03 40 76 E7 70 18 91 80 9B 85 0E 4D | w....@v.p......M 1080 01 4D 4F 90 00 78 42 55 20 | .MO..xBU 1082 ###### decompressed ###### 1083 HTTP/1.1 200 ? 1084 content-length: 345 1085 accept-ranges: bytes 1086 expires: Fri, 1 Jan 2100 12:00:00 GMT 1087 server: Apache/2.2.22 (Ubuntu) 1088 last-modified: Sat, 23 Jun 2012 02:03:46 GMT 1089 cache-control: public, max-age=3600000000 1090 date: Tue, 12 Mar 2013 23:12:44 GMT 1091 content-type: image/png 1092 12. Unfinished components 1094 These are components that must be added in the future. 1096 Encoding of raw or ascii bytes 1098 Describing safe mechanisms for changing the allowable compressor 1099 state size downwards. 1101 The frequency table used to generate the huffman encoding should 1102 be updated with a more comprehensive analysis of header-character 1103 frequency. 1105 13. Security Considerations 1107 The compressor algorithm described here is expected to be immune to 1108 the current attacks against encrypted stream-based compressors such 1109 as TLS+gzip, but more scrutiny is warranted. The reason that it is 1110 believed that the algorithm(s) expressed here is immune is that any 1111 backreference to a header key or value always requires a whole-text 1112 match, and thus any probe of the compression context confirms no 1113 hypothesis unless the attacker has guessed the entire plaintext key 1114 and value simultaneously. 1116 14. Requirements Notation 1118 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 1119 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 1120 document are to be interpreted as described in [RFC2119]. 1122 15. Acknowledgements 1124 16. Appendix A 1126 Appendix A (static-entries) : 1128 # (key, val) 1129 # Order does matter... 1130 static_entries = [ 1131 (':path', '/'), 1132 (':scheme', 'http'), 1133 (':scheme', 'https'), 1134 (':method', 'get'), 1135 (':host', ''), 1136 ('cookie', ''), 1137 (':status', '200'), 1138 (':status-text', 'OK'), 1139 (':version', '1.1'), 1140 ('accept', ''), 1141 ('accept-charset', ''), 1142 ('accept-encoding', ''), 1143 ('accept-language', ''), 1144 ('accept-ranges', ''), 1145 ('allow', ''), 1146 ('authorizations', ''), 1147 ('cache-control', ''), 1148 ('content-base', ''), 1149 ('content-encoding', ''), 1150 ('content-length', ''), 1151 ('content-location', ''), 1152 ('content-md5', ''), 1153 ('content-range', ''), 1154 ('content-type', ''), 1155 ('date', ''), 1156 ('etag', ''), 1157 ('expect', ''), 1158 ('expires', ''), 1159 ('from', ''), 1160 ('if-match', ''), 1161 ('if-modified-since', ''), 1162 ('if-none-match', ''), 1163 ('if-range', ''), 1164 ('if-unmodified-since', ''), 1165 ('last-modified', ''), 1166 ('location', ''), 1167 ('max-forwards', ''), 1168 ('origin', ''), 1169 ('pragma', ''), 1170 ('proxy-authenticate', ''), 1171 ('proxy-authorization', ''), 1172 ('range', ''), 1173 ('referer', ''), 1174 ('retry-after', ''), 1175 ('server', ''), 1176 ('set-cookie', ''), 1177 ('status', ''), 1178 ('te', ''), 1179 ('trailer', ''), 1180 ('transfer-encoding', ''), 1181 ('upgrade', ''), 1182 ('user-agent', ''), 1183 ('vary', ''), 1184 ('via', ''), 1185 ('warning', ''), 1186 ('www-authenticate', ''), 1187 ('access-control-allow-origin', ''), 1188 ('content-disposition', ''), 1189 ('get-dictionary', ''), 1190 ('p3p', ''), 1191 ('x-content-type-options', ''), 1192 ('x-frame-options', ''), 1193 ('x-powered-by', ''), 1194 ('x-xss-protection', ''), 1195 ] 1197 17. Appendix B 1199 Appendix B huffman code-table for requests 1201 aligned aligned 1202 to to 1203 MSB LSB 1204 sym as bits len as hex len 1205 ( 0) |11111111|11111111|11110111|100 [27] 7ffffbc [27] 1206 ( 1) |11111111|11111111|11110111|101 [27] 7ffffbd [27] 1207 ( 2) |11111111|11111111|11110111|110 [27] 7ffffbe [27] 1208 ( 3) |11111111|11111111|11110111|111 [27] 7ffffbf [27] 1209 ( 4) |11111111|11111111|11111000|000 [27] 7ffffc0 [27] 1210 ( 5) |11111111|11111111|11111000|001 [27] 7ffffc1 [27] 1211 ( 6) |11111111|11111111|11111000|010 [27] 7ffffc2 [27] 1212 ( 7) |11111111|11111111|11111000|011 [27] 7ffffc3 [27] 1213 ( 8) |11111111|11111111|11111000|100 [27] 7ffffc4 [27] 1214 ( 9) |11111111|11111111|11111000|101 [27] 7ffffc5 [27] 1215 ( 10) |11111111|11111111|11111000|110 [27] 7ffffc6 [27] 1216 ( 11) |11111111|11111111|11111000|111 [27] 7ffffc7 [27] 1217 ( 12) |11111111|11111111|11111001|000 [27] 7ffffc8 [27] 1218 ( 13) |11111111|11111111|11111001|001 [27] 7ffffc9 [27] 1219 ( 14) |11111111|11111111|11111001|010 [27] 7ffffca [27] 1220 ( 15) |11111111|11111111|11111001|011 [27] 7ffffcb [27] 1221 ( 16) |11111111|11111111|11111001|100 [27] 7ffffcc [27] 1222 ( 17) |11111111|11111111|11111001|101 [27] 7ffffcd [27] 1223 ( 18) |11111111|11111111|11111001|110 [27] 7ffffce [27] 1224 ( 19) |11111111|11111111|11111001|111 [27] 7ffffcf [27] 1225 ( 20) |11111111|11111111|11111010|000 [27] 7ffffd0 [27] 1226 ( 21) |11111111|11111111|11111010|001 [27] 7ffffd1 [27] 1227 ( 22) |11111111|11111111|11111010|010 [27] 7ffffd2 [27] 1228 ( 23) |11111111|11111111|11111010|011 [27] 7ffffd3 [27] 1229 ( 24) |11111111|11111111|11111010|100 [27] 7ffffd4 [27] 1230 ( 25) |11111111|11111111|11111010|101 [27] 7ffffd5 [27] 1231 ( 26) |11111111|11111111|11111010|110 [27] 7ffffd6 [27] 1232 ( 27) |11111111|11111111|11111010|111 [27] 7ffffd7 [27] 1233 ( 28) |11111111|11111111|11111011|000 [27] 7ffffd8 [27] 1234 ( 29) |11111111|11111111|11111011|001 [27] 7ffffd9 [27] 1235 ( 30) |11111111|11111111|11111011|010 [27] 7ffffda [27] 1236 ( 31) |11111111|11111111|11111011|011 [27] 7ffffdb [27] 1237 ' ' ( 32) |11111111|0110 [12] ff6 [12] 1238 '!' ( 33) |11111111|0111 [12] ff7 [12] 1239 '"' ( 34) |11111111|111010 [14] 3ffa [14] 1240 '#' ( 35) |11111111|1111100 [15] 7ffc [15] 1241 '$' ( 36) |11111111|1111101 [15] 7ffd [15] 1242 '%' ( 37) |100110 [6] 26 [6] 1243 '&' ( 38) |1110000 [7] 70 [7] 1244 ''' ( 39) |11111111|1111110 [15] 7ffe [15] 1245 '(' ( 40) |11111111|1000 [12] ff8 [12] 1246 ')' ( 41) |11111111|1001 [12] ff9 [12] 1247 '*' ( 42) |11111111|1010 [12] ffa [12] 1248 '+' ( 43) |11111111|1011 [12] ffb [12] 1249 ',' ( 44) |11111110|00 [10] 3f8 [10] 1250 '-' ( 45) |100111 [6] 27 [6] 1251 '.' ( 46) |00110 [5] 6 [5] 1252 '/' ( 47) |0000 [4] 0 [4] 1253 '0' ( 48) |00111 [5] 7 [5] 1254 '1' ( 49) |01000 [5] 8 [5] 1255 '2' ( 50) |01001 [5] 9 [5] 1256 '3' ( 51) |101000 [6] 28 [6] 1257 '4' ( 52) |1110001 [7] 71 [7] 1258 '5' ( 53) |101001 [6] 29 [6] 1259 '6' ( 54) |1110010 [7] 72 [7] 1260 '7' ( 55) |101010 [6] 2a [6] 1261 '8' ( 56) |1110011 [7] 73 [7] 1262 '9' ( 57) |101011 [6] 2b [6] 1263 ':' ( 58) |101100 [6] 2c [6] 1264 ';' ( 59) |11110100|0 [9] 1e8 [9] 1265 '<' ( 60) |11111111|11111111|10 [18] 3fffe [18] 1266 '=' ( 61) |101101 [6] 2d [6] 1267 '>' ( 62) |11111111|11111110|0 [17] 1fffc [17] 1268 '?' ( 63) |11110100|1 [9] 1e9 [9] 1269 '@' ( 64) |11111111|11100 [13] 1ffc [13] 1270 'A' ( 65) |11101100 [8] ec [8] 1271 'B' ( 66) |11101101 [8] ed [8] 1272 'C' ( 67) |11101110 [8] ee [8] 1273 'D' ( 68) |11101111 [8] ef [8] 1274 'E' ( 69) |11110101|0 [9] 1ea [9] 1275 'F' ( 70) |1110100 [7] 74 [7] 1276 'G' ( 71) |11110101|1 [9] 1eb [9] 1277 'H' ( 72) |11110110|0 [9] 1ec [9] 1278 'I' ( 73) |11110110|1 [9] 1ed [9] 1279 'J' ( 74) |11111110|01 [10] 3f9 [10] 1280 'K' ( 75) |11111111|010 [11] 7fa [11] 1281 'L' ( 76) |11110111|0 [9] 1ee [9] 1282 'M' ( 77) |11110111|1 [9] 1ef [9] 1283 'N' ( 78) |11111000|0 [9] 1f0 [9] 1284 'O' ( 79) |11111000|1 [9] 1f1 [9] 1285 'P' ( 80) |11111001|0 [9] 1f2 [9] 1286 'Q' ( 81) |11111110|10 [10] 3fa [10] 1287 'R' ( 82) |11111001|1 [9] 1f3 [9] 1288 'S' ( 83) |11111010|0 [9] 1f4 [9] 1289 'T' ( 84) |11111010|1 [9] 1f5 [9] 1290 'U' ( 85) |11111011|0 [9] 1f6 [9] 1291 'V' ( 86) |11111011|1 [9] 1f7 [9] 1292 'W' ( 87) |11111100|0 [9] 1f8 [9] 1293 'X' ( 88) |11111100|1 [9] 1f9 [9] 1294 'Y' ( 89) |11111110|11 [10] 3fb [10] 1295 'Z' ( 90) |11111111|00 [10] 3fc [10] 1296 '[' ( 91) |11111111|111011 [14] 3ffb [14] 1297 '\' ( 92) |11111111|11111111|11111011|100 [27] 7ffffdc [27] 1298 ']' ( 93) |11111111|111100 [14] 3ffc [14] 1299 '^' ( 94) |11111111|111101 [14] 3ffd [14] 1300 '_' ( 95) |101110 [6] 2e [6] 1301 '`' ( 96) |11111111|11111111|110 [19] 7fffe [19] 1302 'a' ( 97) |01010 [5] a [5] 1303 'b' ( 98) |101111 [6] 2f [6] 1304 'c' ( 99) |01011 [5] b [5] 1305 'd' (100) |110000 [6] 30 [6] 1306 'e' (101) |0001 [4] 1 [4] 1307 'f' (102) |110001 [6] 31 [6] 1308 'g' (103) |110010 [6] 32 [6] 1309 'h' (104) |110011 [6] 33 [6] 1310 'i' (105) |01100 [5] c [5] 1311 'j' (106) |1110101 [7] 75 [7] 1312 'k' (107) |11110000 [8] f0 [8] 1313 'l' (108) |110100 [6] 34 [6] 1314 'm' (109) |110101 [6] 35 [6] 1315 'n' (110) |01101 [5] d [5] 1316 'o' (111) |01110 [5] e [5] 1317 'p' (112) |01111 [5] f [5] 1318 'q' (113) |11111101|0 [9] 1fa [9] 1319 'r' (114) |10000 [5] 10 [5] 1320 's' (115) |10001 [5] 11 [5] 1321 't' (116) |0010 [4] 2 [4] 1322 'u' (117) |110110 [6] 36 [6] 1323 'v' (118) |11110001 [8] f1 [8] 1324 'w' (119) |110111 [6] 37 [6] 1325 'x' (120) |11110010 [8] f2 [8] 1326 'y' (121) |11110011 [8] f3 [8] 1327 'z' (122) |11111101|1 [9] 1fb [9] 1328 '{' (123) |11111111|11111110|1 [17] 1fffd [17] 1329 '|' (124) |11111111|1100 [12] ffc [12] 1330 '}' (125) |11111111|11111111|0 [17] 1fffe [17] 1331 '~' (126) |11111111|1101 [12] ffd [12] 1332 (127) |11111111|11111111|11111011|101 [27] 7ffffdd [27] 1333 (128) |11111111|11111111|11111011|110 [27] 7ffffde [27] 1334 (129) |11111111|11111111|11111011|111 [27] 7ffffdf [27] 1335 (130) |11111111|11111111|11111100|000 [27] 7ffffe0 [27] 1336 (131) |11111111|11111111|11111100|001 [27] 7ffffe1 [27] 1337 (132) |11111111|11111111|11111100|010 [27] 7ffffe2 [27] 1338 (133) |11111111|11111111|11111100|011 [27] 7ffffe3 [27] 1339 (134) |11111111|11111111|11111100|100 [27] 7ffffe4 [27] 1340 (135) |11111111|11111111|11111100|101 [27] 7ffffe5 [27] 1341 (136) |11111111|11111111|11111100|110 [27] 7ffffe6 [27] 1342 (137) |11111111|11111111|11111100|111 [27] 7ffffe7 [27] 1343 (138) |11111111|11111111|11111101|000 [27] 7ffffe8 [27] 1344 (139) |11111111|11111111|11111101|001 [27] 7ffffe9 [27] 1345 (140) |11111111|11111111|11111101|010 [27] 7ffffea [27] 1346 (141) |11111111|11111111|11111101|011 [27] 7ffffeb [27] 1347 (142) |11111111|11111111|11111101|100 [27] 7ffffec [27] 1348 (143) |11111111|11111111|11111101|101 [27] 7ffffed [27] 1349 (144) |11111111|11111111|11111101|110 [27] 7ffffee [27] 1350 (145) |11111111|11111111|11111101|111 [27] 7ffffef [27] 1351 (146) |11111111|11111111|11111110|000 [27] 7fffff0 [27] 1352 (147) |11111111|11111111|11111110|001 [27] 7fffff1 [27] 1353 (148) |11111111|11111111|11111110|010 [27] 7fffff2 [27] 1354 (149) |11111111|11111111|11111110|011 [27] 7fffff3 [27] 1355 (150) |11111111|11111111|11111110|100 [27] 7fffff4 [27] 1356 (151) |11111111|11111111|11111110|101 [27] 7fffff5 [27] 1357 (152) |11111111|11111111|11111110|110 [27] 7fffff6 [27] 1358 (153) |11111111|11111111|11111110|111 [27] 7fffff7 [27] 1359 (154) |11111111|11111111|11111111|000 [27] 7fffff8 [27] 1360 (155) |11111111|11111111|11111111|001 [27] 7fffff9 [27] 1361 (156) |11111111|11111111|11111111|010 [27] 7fffffa [27] 1362 (157) |11111111|11111111|11111111|011 [27] 7fffffb [27] 1363 (158) |11111111|11111111|11111111|100 [27] 7fffffc [27] 1364 (159) |11111111|11111111|11111111|101 [27] 7fffffd [27] 1365 (160) |11111111|11111111|11111111|110 [27] 7fffffe [27] 1366 (161) |11111111|11111111|11111111|111 [27] 7ffffff [27] 1367 (162) |11111111|11111111|11100000|00 [26] 3ffff80 [26] 1368 (163) |11111111|11111111|11100000|01 [26] 3ffff81 [26] 1369 (164) |11111111|11111111|11100000|10 [26] 3ffff82 [26] 1370 (165) |11111111|11111111|11100000|11 [26] 3ffff83 [26] 1371 (166) |11111111|11111111|11100001|00 [26] 3ffff84 [26] 1372 (167) |11111111|11111111|11100001|01 [26] 3ffff85 [26] 1373 (168) |11111111|11111111|11100001|10 [26] 3ffff86 [26] 1374 (169) |11111111|11111111|11100001|11 [26] 3ffff87 [26] 1375 (170) |11111111|11111111|11100010|00 [26] 3ffff88 [26] 1376 (171) |11111111|11111111|11100010|01 [26] 3ffff89 [26] 1377 (172) |11111111|11111111|11100010|10 [26] 3ffff8a [26] 1378 (173) |11111111|11111111|11100010|11 [26] 3ffff8b [26] 1379 (174) |11111111|11111111|11100011|00 [26] 3ffff8c [26] 1380 (175) |11111111|11111111|11100011|01 [26] 3ffff8d [26] 1381 (176) |11111111|11111111|11100011|10 [26] 3ffff8e [26] 1382 (177) |11111111|11111111|11100011|11 [26] 3ffff8f [26] 1383 (178) |11111111|11111111|11100100|00 [26] 3ffff90 [26] 1384 (179) |11111111|11111111|11100100|01 [26] 3ffff91 [26] 1385 (180) |11111111|11111111|11100100|10 [26] 3ffff92 [26] 1386 (181) |11111111|11111111|11100100|11 [26] 3ffff93 [26] 1387 (182) |11111111|11111111|11100101|00 [26] 3ffff94 [26] 1388 (183) |11111111|11111111|11100101|01 [26] 3ffff95 [26] 1389 (184) |11111111|11111111|11100101|10 [26] 3ffff96 [26] 1390 (185) |11111111|11111111|11100101|11 [26] 3ffff97 [26] 1391 (186) |11111111|11111111|11100110|00 [26] 3ffff98 [26] 1392 (187) |11111111|11111111|11100110|01 [26] 3ffff99 [26] 1393 (188) |11111111|11111111|11100110|10 [26] 3ffff9a [26] 1394 (189) |11111111|11111111|11100110|11 [26] 3ffff9b [26] 1395 (190) |11111111|11111111|11100111|00 [26] 3ffff9c [26] 1396 (191) |11111111|11111111|11100111|01 [26] 3ffff9d [26] 1397 (192) |11111111|11111111|11100111|10 [26] 3ffff9e [26] 1398 (193) |11111111|11111111|11100111|11 [26] 3ffff9f [26] 1399 (194) |11111111|11111111|11101000|00 [26] 3ffffa0 [26] 1400 (195) |11111111|11111111|11101000|01 [26] 3ffffa1 [26] 1401 (196) |11111111|11111111|11101000|10 [26] 3ffffa2 [26] 1402 (197) |11111111|11111111|11101000|11 [26] 3ffffa3 [26] 1403 (198) |11111111|11111111|11101001|00 [26] 3ffffa4 [26] 1404 (199) |11111111|11111111|11101001|01 [26] 3ffffa5 [26] 1405 (200) |11111111|11111111|11101001|10 [26] 3ffffa6 [26] 1406 (201) |11111111|11111111|11101001|11 [26] 3ffffa7 [26] 1407 (202) |11111111|11111111|11101010|00 [26] 3ffffa8 [26] 1408 (203) |11111111|11111111|11101010|01 [26] 3ffffa9 [26] 1409 (204) |11111111|11111111|11101010|10 [26] 3ffffaa [26] 1410 (205) |11111111|11111111|11101010|11 [26] 3ffffab [26] 1411 (206) |11111111|11111111|11101011|00 [26] 3ffffac [26] 1412 (207) |11111111|11111111|11101011|01 [26] 3ffffad [26] 1413 (208) |11111111|11111111|11101011|10 [26] 3ffffae [26] 1414 (209) |11111111|11111111|11101011|11 [26] 3ffffaf [26] 1415 (210) |11111111|11111111|11101100|00 [26] 3ffffb0 [26] 1416 (211) |11111111|11111111|11101100|01 [26] 3ffffb1 [26] 1417 (212) |11111111|11111111|11101100|10 [26] 3ffffb2 [26] 1418 (213) |11111111|11111111|11101100|11 [26] 3ffffb3 [26] 1419 (214) |11111111|11111111|11101101|00 [26] 3ffffb4 [26] 1420 (215) |11111111|11111111|11101101|01 [26] 3ffffb5 [26] 1421 (216) |11111111|11111111|11101101|10 [26] 3ffffb6 [26] 1422 (217) |11111111|11111111|11101101|11 [26] 3ffffb7 [26] 1423 (218) |11111111|11111111|11101110|00 [26] 3ffffb8 [26] 1424 (219) |11111111|11111111|11101110|01 [26] 3ffffb9 [26] 1425 (220) |11111111|11111111|11101110|10 [26] 3ffffba [26] 1426 (221) |11111111|11111111|11101110|11 [26] 3ffffbb [26] 1427 (222) |11111111|11111111|11101111|00 [26] 3ffffbc [26] 1428 (223) |11111111|11111111|11101111|01 [26] 3ffffbd [26] 1429 (224) |11111111|11111111|11101111|10 [26] 3ffffbe [26] 1430 (225) |11111111|11111111|11101111|11 [26] 3ffffbf [26] 1431 (226) |11111111|11111111|11110000|00 [26] 3ffffc0 [26] 1432 (227) |11111111|11111111|11110000|01 [26] 3ffffc1 [26] 1433 (228) |11111111|11111111|11110000|10 [26] 3ffffc2 [26] 1434 (229) |11111111|11111111|11110000|11 [26] 3ffffc3 [26] 1435 (230) |11111111|11111111|11110001|00 [26] 3ffffc4 [26] 1436 (231) |11111111|11111111|11110001|01 [26] 3ffffc5 [26] 1437 (232) |11111111|11111111|11110001|10 [26] 3ffffc6 [26] 1438 (233) |11111111|11111111|11110001|11 [26] 3ffffc7 [26] 1439 (234) |11111111|11111111|11110010|00 [26] 3ffffc8 [26] 1440 (235) |11111111|11111111|11110010|01 [26] 3ffffc9 [26] 1441 (236) |11111111|11111111|11110010|10 [26] 3ffffca [26] 1442 (237) |11111111|11111111|11110010|11 [26] 3ffffcb [26] 1443 (238) |11111111|11111111|11110011|00 [26] 3ffffcc [26] 1444 (239) |11111111|11111111|11110011|01 [26] 3ffffcd [26] 1445 (240) |11111111|11111111|11110011|10 [26] 3ffffce [26] 1446 (241) |11111111|11111111|11110011|11 [26] 3ffffcf [26] 1447 (242) |11111111|11111111|11110100|00 [26] 3ffffd0 [26] 1448 (243) |11111111|11111111|11110100|01 [26] 3ffffd1 [26] 1449 (244) |11111111|11111111|11110100|10 [26] 3ffffd2 [26] 1450 (245) |11111111|11111111|11110100|11 [26] 3ffffd3 [26] 1451 (246) |11111111|11111111|11110101|00 [26] 3ffffd4 [26] 1452 (247) |11111111|11111111|11110101|01 [26] 3ffffd5 [26] 1453 (248) |11111111|11111111|11110101|10 [26] 3ffffd6 [26] 1454 (249) |11111111|11111111|11110101|11 [26] 3ffffd7 [26] 1455 (250) |11111111|11111111|11110110|00 [26] 3ffffd8 [26] 1456 (251) |11111111|11111111|11110110|01 [26] 3ffffd9 [26] 1457 (252) |11111111|11111111|11110110|10 [26] 3ffffda [26] 1458 (253) |11111111|11111111|11110110|11 [26] 3ffffdb [26] 1459 (254) |11111111|11111111|11110111|00 [26] 3ffffdc [26] 1460 (255) |11111111|11111111|11110111|01 [26] 3ffffdd [26] 1461 (256) |10010 [5] 12 [5] 1463 18. Appendix C 1465 Appendix C huffman code-table for responses 1467 aligned aligned 1468 to to 1469 MSB LSB 1470 sym as bits len as hex len 1471 ( 0) |11111111|11111111|11101111|10 [26] 3ffffbe [26] 1472 ( 1) |11111111|11111111|11101111|11 [26] 3ffffbf [26] 1473 ( 2) |11111111|11111111|11110000|00 [26] 3ffffc0 [26] 1474 ( 3) |11111111|11111111|11110000|01 [26] 3ffffc1 [26] 1475 ( 4) |11111111|11111111|11110000|10 [26] 3ffffc2 [26] 1476 ( 5) |11111111|11111111|11110000|11 [26] 3ffffc3 [26] 1477 ( 6) |11111111|11111111|11110001|00 [26] 3ffffc4 [26] 1478 ( 7) |11111111|11111111|11110001|01 [26] 3ffffc5 [26] 1479 ( 8) |11111111|11111111|11110001|10 [26] 3ffffc6 [26] 1480 ( 9) |11111111|11111111|11110001|11 [26] 3ffffc7 [26] 1481 ( 10) |11111111|11111111|11110010|00 [26] 3ffffc8 [26] 1482 ( 11) |11111111|11111111|11110010|01 [26] 3ffffc9 [26] 1483 ( 12) |11111111|11111111|11110010|10 [26] 3ffffca [26] 1484 ( 13) |11111111|11111111|11110010|11 [26] 3ffffcb [26] 1485 ( 14) |11111111|11111111|11110011|00 [26] 3ffffcc [26] 1486 ( 15) |11111111|11111111|11110011|01 [26] 3ffffcd [26] 1487 ( 16) |11111111|11111111|11110011|10 [26] 3ffffce [26] 1488 ( 17) |11111111|11111111|11110011|11 [26] 3ffffcf [26] 1489 ( 18) |11111111|11111111|11110100|00 [26] 3ffffd0 [26] 1490 ( 19) |11111111|11111111|11110100|01 [26] 3ffffd1 [26] 1491 ( 20) |11111111|11111111|11110100|10 [26] 3ffffd2 [26] 1492 ( 21) |11111111|11111111|11110100|11 [26] 3ffffd3 [26] 1493 ( 22) |11111111|11111111|11110101|00 [26] 3ffffd4 [26] 1494 ( 23) |11111111|11111111|11110101|01 [26] 3ffffd5 [26] 1495 ( 24) |11111111|11111111|11110101|10 [26] 3ffffd6 [26] 1496 ( 25) |11111111|11111111|11110101|11 [26] 3ffffd7 [26] 1497 ( 26) |11111111|11111111|11110110|00 [26] 3ffffd8 [26] 1498 ( 27) |11111111|11111111|11110110|01 [26] 3ffffd9 [26] 1499 ( 28) |11111111|11111111|11110110|10 [26] 3ffffda [26] 1500 ( 29) |11111111|11111111|11110110|11 [26] 3ffffdb [26] 1501 ( 30) |11111111|11111111|11110111|00 [26] 3ffffdc [26] 1502 ( 31) |11111111|11111111|11110111|01 [26] 3ffffdd [26] 1503 ' ' ( 32) |0000 [4] 0 [4] 1504 '!' ( 33) |11111111|1010 [12] ffa [12] 1505 '"' ( 34) |1101000 [7] 68 [7] 1506 '#' ( 35) |11111111|111010 [14] 3ffa [14] 1507 '$' ( 36) |11111111|1111100 [15] 7ffc [15] 1508 '%' ( 37) |11110101|0 [9] 1ea [9] 1509 '&' ( 38) |11111110|00 [10] 3f8 [10] 1510 ''' ( 39) |11111111|11100 [13] 1ffc [13] 1511 '(' ( 40) |11110101|1 [9] 1eb [9] 1512 ')' ( 41) |11110110|0 [9] 1ec [9] 1513 '*' ( 42) |11111111|1011 [12] ffb [12] 1514 '+' ( 43) |11111110|01 [10] 3f9 [10] 1515 ',' ( 44) |100110 [6] 26 [6] 1516 '-' ( 45) |100111 [6] 27 [6] 1517 '.' ( 46) |1101001 [7] 69 [7] 1518 '/' ( 47) |11101000 [8] e8 [8] 1519 '0' ( 48) |0001 [4] 1 [4] 1520 '1' ( 49) |0010 [4] 2 [4] 1521 '2' ( 50) |0011 [4] 3 [4] 1522 '3' ( 51) |01000 [5] 8 [5] 1523 '4' ( 52) |01001 [5] 9 [5] 1524 '5' ( 53) |01010 [5] a [5] 1525 '6' ( 54) |101000 [6] 28 [6] 1526 '7' ( 55) |01011 [5] b [5] 1527 '8' ( 56) |01100 [5] c [5] 1528 '9' ( 57) |01101 [5] d [5] 1529 ':' ( 58) |01110 [5] e [5] 1530 ';' ( 59) |11110110|1 [9] 1ed [9] 1531 '<' ( 60) |11111111|11111100 [16] fffc [16] 1532 '=' ( 61) |1101010 [7] 6a [7] 1533 '>' ( 62) |11111111|111011 [14] 3ffb [14] 1534 '?' ( 63) |11111111|1100 [12] ffc [12] 1535 '@' ( 64) |11111111|11111110|0 [17] 1fffc [17] 1536 'A' ( 65) |1101011 [7] 6b [7] 1537 'B' ( 66) |11110111|0 [9] 1ee [9] 1538 'C' ( 67) |11101001 [8] e9 [8] 1539 'D' ( 68) |11101010 [8] ea [8] 1540 'E' ( 69) |11101011 [8] eb [8] 1541 'F' ( 70) |11101100 [8] ec [8] 1542 'G' ( 71) |101001 [6] 29 [6] 1543 'H' ( 72) |11110111|1 [9] 1ef [9] 1544 'I' ( 73) |11111000|0 [9] 1f0 [9] 1545 'J' ( 74) |11101101 [8] ed [8] 1546 'K' ( 75) |11111110|10 [10] 3fa [10] 1547 'L' ( 76) |11111000|1 [9] 1f1 [9] 1548 'M' ( 77) |101010 [6] 2a [6] 1549 'N' ( 78) |11101110 [8] ee [8] 1550 'O' ( 79) |11101111 [8] ef [8] 1551 'P' ( 80) |11111001|0 [9] 1f2 [9] 1552 'Q' ( 81) |11111001|1 [9] 1f3 [9] 1553 'R' ( 82) |11111010|0 [9] 1f4 [9] 1554 'S' ( 83) |1101100 [7] 6c [7] 1555 'T' ( 84) |01111 [5] f [5] 1556 'U' ( 85) |11111010|1 [9] 1f5 [9] 1557 'V' ( 86) |11111011|0 [9] 1f6 [9] 1558 'W' ( 87) |11110000 [8] f0 [8] 1559 'X' ( 88) |11111110|11 [10] 3fb [10] 1560 'Y' ( 89) |11111111|00 [10] 3fc [10] 1561 'Z' ( 90) |11111111|01 [10] 3fd [10] 1562 '[' ( 91) |11111111|1101 [12] ffd [12] 1563 '\' ( 92) |11111111|111100 [14] 3ffc [14] 1564 ']' ( 93) |11111111|100 [11] 7fc [11] 1565 '^' ( 94) |11111111|1111101 [15] 7ffd [15] 1566 '_' ( 95) |11111011|1 [9] 1f7 [9] 1567 '`' ( 96) |11111111|11111111|10 [18] 3fffe [18] 1568 'a' ( 97) |10000 [5] 10 [5] 1569 'b' ( 98) |1101101 [7] 6d [7] 1570 'c' ( 99) |101011 [6] 2b [6] 1571 'd' (100) |101100 [6] 2c [6] 1572 'e' (101) |10001 [5] 11 [5] 1573 'f' (102) |1101110 [7] 6e [7] 1574 'g' (103) |1101111 [7] 6f [7] 1575 'h' (104) |1110000 [7] 70 [7] 1576 'i' (105) |101101 [6] 2d [6] 1577 'j' (106) |11111100|0 [9] 1f8 [9] 1578 'k' (107) |11111100|1 [9] 1f9 [9] 1579 'l' (108) |1110001 [7] 71 [7] 1580 'm' (109) |1110010 [7] 72 [7] 1581 'n' (110) |101110 [6] 2e [6] 1582 'o' (111) |101111 [6] 2f [6] 1583 'p' (112) |110000 [6] 30 [6] 1584 'q' (113) |11111101|0 [9] 1fa [9] 1585 'r' (114) |110001 [6] 31 [6] 1586 's' (115) |1110011 [7] 73 [7] 1587 't' (116) |110010 [6] 32 [6] 1588 'u' (117) |110011 [6] 33 [6] 1589 'v' (118) |11110001 [8] f1 [8] 1590 'w' (119) |11110010 [8] f2 [8] 1591 'x' (120) |11110011 [8] f3 [8] 1592 'y' (121) |11110100 [8] f4 [8] 1593 'z' (122) |11111101|1 [9] 1fb [9] 1594 '{' (123) |11111111|11111110|1 [17] 1fffd [17] 1595 '|' (124) |11111111|111101 [14] 3ffd [14] 1596 '}' (125) |11111111|11111111|0 [17] 1fffe [17] 1597 '~' (126) |11111111|11111101 [16] fffd [16] 1598 (127) |11111111|11111111|11110111|10 [26] 3ffffde [26] 1599 (128) |11111111|11111111|11110111|11 [26] 3ffffdf [26] 1600 (129) |11111111|11111111|11111000|00 [26] 3ffffe0 [26] 1601 (130) |11111111|11111111|11111000|01 [26] 3ffffe1 [26] 1602 (131) |11111111|11111111|11111000|10 [26] 3ffffe2 [26] 1603 (132) |11111111|11111111|11111000|11 [26] 3ffffe3 [26] 1604 (133) |11111111|11111111|11111001|00 [26] 3ffffe4 [26] 1605 (134) |11111111|11111111|11111001|01 [26] 3ffffe5 [26] 1606 (135) |11111111|11111111|11111001|10 [26] 3ffffe6 [26] 1607 (136) |11111111|11111111|11111001|11 [26] 3ffffe7 [26] 1608 (137) |11111111|11111111|11111010|00 [26] 3ffffe8 [26] 1609 (138) |11111111|11111111|11111010|01 [26] 3ffffe9 [26] 1610 (139) |11111111|11111111|11111010|10 [26] 3ffffea [26] 1611 (140) |11111111|11111111|11111010|11 [26] 3ffffeb [26] 1612 (141) |11111111|11111111|11111011|00 [26] 3ffffec [26] 1613 (142) |11111111|11111111|11111011|01 [26] 3ffffed [26] 1614 (143) |11111111|11111111|11111011|10 [26] 3ffffee [26] 1615 (144) |11111111|11111111|11111011|11 [26] 3ffffef [26] 1616 (145) |11111111|11111111|11111100|00 [26] 3fffff0 [26] 1617 (146) |11111111|11111111|11111100|01 [26] 3fffff1 [26] 1618 (147) |11111111|11111111|11111100|10 [26] 3fffff2 [26] 1619 (148) |11111111|11111111|11111100|11 [26] 3fffff3 [26] 1620 (149) |11111111|11111111|11111101|00 [26] 3fffff4 [26] 1621 (150) |11111111|11111111|11111101|01 [26] 3fffff5 [26] 1622 (151) |11111111|11111111|11111101|10 [26] 3fffff6 [26] 1623 (152) |11111111|11111111|11111101|11 [26] 3fffff7 [26] 1624 (153) |11111111|11111111|11111110|00 [26] 3fffff8 [26] 1625 (154) |11111111|11111111|11111110|01 [26] 3fffff9 [26] 1626 (155) |11111111|11111111|11111110|10 [26] 3fffffa [26] 1627 (156) |11111111|11111111|11111110|11 [26] 3fffffb [26] 1628 (157) |11111111|11111111|11111111|00 [26] 3fffffc [26] 1629 (158) |11111111|11111111|11111111|01 [26] 3fffffd [26] 1630 (159) |11111111|11111111|11111111|10 [26] 3fffffe [26] 1631 (160) |11111111|11111111|11111111|11 [26] 3ffffff [26] 1632 (161) |11111111|11111111|11000000|0 [25] 1ffff80 [25] 1633 (162) |11111111|11111111|11000000|1 [25] 1ffff81 [25] 1634 (163) |11111111|11111111|11000001|0 [25] 1ffff82 [25] 1635 (164) |11111111|11111111|11000001|1 [25] 1ffff83 [25] 1636 (165) |11111111|11111111|11000010|0 [25] 1ffff84 [25] 1637 (166) |11111111|11111111|11000010|1 [25] 1ffff85 [25] 1638 (167) |11111111|11111111|11000011|0 [25] 1ffff86 [25] 1639 (168) |11111111|11111111|11000011|1 [25] 1ffff87 [25] 1640 (169) |11111111|11111111|11000100|0 [25] 1ffff88 [25] 1641 (170) |11111111|11111111|11000100|1 [25] 1ffff89 [25] 1642 (171) |11111111|11111111|11000101|0 [25] 1ffff8a [25] 1643 (172) |11111111|11111111|11000101|1 [25] 1ffff8b [25] 1644 (173) |11111111|11111111|11000110|0 [25] 1ffff8c [25] 1645 (174) |11111111|11111111|11000110|1 [25] 1ffff8d [25] 1646 (175) |11111111|11111111|11000111|0 [25] 1ffff8e [25] 1647 (176) |11111111|11111111|11000111|1 [25] 1ffff8f [25] 1648 (177) |11111111|11111111|11001000|0 [25] 1ffff90 [25] 1649 (178) |11111111|11111111|11001000|1 [25] 1ffff91 [25] 1650 (179) |11111111|11111111|11001001|0 [25] 1ffff92 [25] 1651 (180) |11111111|11111111|11001001|1 [25] 1ffff93 [25] 1652 (181) |11111111|11111111|11001010|0 [25] 1ffff94 [25] 1653 (182) |11111111|11111111|11001010|1 [25] 1ffff95 [25] 1654 (183) |11111111|11111111|11001011|0 [25] 1ffff96 [25] 1655 (184) |11111111|11111111|11001011|1 [25] 1ffff97 [25] 1656 (185) |11111111|11111111|11001100|0 [25] 1ffff98 [25] 1657 (186) |11111111|11111111|11001100|1 [25] 1ffff99 [25] 1658 (187) |11111111|11111111|11001101|0 [25] 1ffff9a [25] 1659 (188) |11111111|11111111|11001101|1 [25] 1ffff9b [25] 1660 (189) |11111111|11111111|11001110|0 [25] 1ffff9c [25] 1661 (190) |11111111|11111111|11001110|1 [25] 1ffff9d [25] 1662 (191) |11111111|11111111|11001111|0 [25] 1ffff9e [25] 1663 (192) |11111111|11111111|11001111|1 [25] 1ffff9f [25] 1664 (193) |11111111|11111111|11010000|0 [25] 1ffffa0 [25] 1665 (194) |11111111|11111111|11010000|1 [25] 1ffffa1 [25] 1666 (195) |11111111|11111111|11010001|0 [25] 1ffffa2 [25] 1667 (196) |11111111|11111111|11010001|1 [25] 1ffffa3 [25] 1668 (197) |11111111|11111111|11010010|0 [25] 1ffffa4 [25] 1669 (198) |11111111|11111111|11010010|1 [25] 1ffffa5 [25] 1670 (199) |11111111|11111111|11010011|0 [25] 1ffffa6 [25] 1671 (200) |11111111|11111111|11010011|1 [25] 1ffffa7 [25] 1672 (201) |11111111|11111111|11010100|0 [25] 1ffffa8 [25] 1673 (202) |11111111|11111111|11010100|1 [25] 1ffffa9 [25] 1674 (203) |11111111|11111111|11010101|0 [25] 1ffffaa [25] 1675 (204) |11111111|11111111|11010101|1 [25] 1ffffab [25] 1676 (205) |11111111|11111111|11010110|0 [25] 1ffffac [25] 1677 (206) |11111111|11111111|11010110|1 [25] 1ffffad [25] 1678 (207) |11111111|11111111|11010111|0 [25] 1ffffae [25] 1679 (208) |11111111|11111111|11010111|1 [25] 1ffffaf [25] 1680 (209) |11111111|11111111|11011000|0 [25] 1ffffb0 [25] 1681 (210) |11111111|11111111|11011000|1 [25] 1ffffb1 [25] 1682 (211) |11111111|11111111|11011001|0 [25] 1ffffb2 [25] 1683 (212) |11111111|11111111|11011001|1 [25] 1ffffb3 [25] 1684 (213) |11111111|11111111|11011010|0 [25] 1ffffb4 [25] 1685 (214) |11111111|11111111|11011010|1 [25] 1ffffb5 [25] 1686 (215) |11111111|11111111|11011011|0 [25] 1ffffb6 [25] 1687 (216) |11111111|11111111|11011011|1 [25] 1ffffb7 [25] 1688 (217) |11111111|11111111|11011100|0 [25] 1ffffb8 [25] 1689 (218) |11111111|11111111|11011100|1 [25] 1ffffb9 [25] 1690 (219) |11111111|11111111|11011101|0 [25] 1ffffba [25] 1691 (220) |11111111|11111111|11011101|1 [25] 1ffffbb [25] 1692 (221) |11111111|11111111|11011110|0 [25] 1ffffbc [25] 1693 (222) |11111111|11111111|11011110|1 [25] 1ffffbd [25] 1694 (223) |11111111|11111111|11011111|0 [25] 1ffffbe [25] 1695 (224) |11111111|11111111|11011111|1 [25] 1ffffbf [25] 1696 (225) |11111111|11111111|11100000|0 [25] 1ffffc0 [25] 1697 (226) |11111111|11111111|11100000|1 [25] 1ffffc1 [25] 1698 (227) |11111111|11111111|11100001|0 [25] 1ffffc2 [25] 1699 (228) |11111111|11111111|11100001|1 [25] 1ffffc3 [25] 1700 (229) |11111111|11111111|11100010|0 [25] 1ffffc4 [25] 1701 (230) |11111111|11111111|11100010|1 [25] 1ffffc5 [25] 1702 (231) |11111111|11111111|11100011|0 [25] 1ffffc6 [25] 1703 (232) |11111111|11111111|11100011|1 [25] 1ffffc7 [25] 1704 (233) |11111111|11111111|11100100|0 [25] 1ffffc8 [25] 1705 (234) |11111111|11111111|11100100|1 [25] 1ffffc9 [25] 1706 (235) |11111111|11111111|11100101|0 [25] 1ffffca [25] 1707 (236) |11111111|11111111|11100101|1 [25] 1ffffcb [25] 1708 (237) |11111111|11111111|11100110|0 [25] 1ffffcc [25] 1709 (238) |11111111|11111111|11100110|1 [25] 1ffffcd [25] 1710 (239) |11111111|11111111|11100111|0 [25] 1ffffce [25] 1711 (240) |11111111|11111111|11100111|1 [25] 1ffffcf [25] 1712 (241) |11111111|11111111|11101000|0 [25] 1ffffd0 [25] 1713 (242) |11111111|11111111|11101000|1 [25] 1ffffd1 [25] 1714 (243) |11111111|11111111|11101001|0 [25] 1ffffd2 [25] 1715 (244) |11111111|11111111|11101001|1 [25] 1ffffd3 [25] 1716 (245) |11111111|11111111|11101010|0 [25] 1ffffd4 [25] 1717 (246) |11111111|11111111|11101010|1 [25] 1ffffd5 [25] 1718 (247) |11111111|11111111|11101011|0 [25] 1ffffd6 [25] 1719 (248) |11111111|11111111|11101011|1 [25] 1ffffd7 [25] 1720 (249) |11111111|11111111|11101100|0 [25] 1ffffd8 [25] 1721 (250) |11111111|11111111|11101100|1 [25] 1ffffd9 [25] 1722 (251) |11111111|11111111|11101101|0 [25] 1ffffda [25] 1723 (252) |11111111|11111111|11101101|1 [25] 1ffffdb [25] 1724 (253) |11111111|11111111|11101110|0 [25] 1ffffdc [25] 1725 (254) |11111111|11111111|11101110|1 [25] 1ffffdd [25] 1726 (255) |11111111|11111111|11101111|0 [25] 1ffffde [25] 1727 (256) |10010 [5] 12 [5] 1729 19. Normative References 1731 [CANON] Schwartz, E. S. and Kallick, B., "Generating a canonical 1732 prefix encoding", Comm. ACM, 7,3 (March 1964), pp 166- 1733 169 . 1735 [HUFF] Huffman, D. A., "A Method for the Construction of Minimim 1736 Redundancy Codes", Proceedings of the Institute of Radio 1737 Engineers, September 1952, Volume 40, Number 9, pp. 1098- 1738 1101 . 1740 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1741 Requirement Levels", BCP 14, RFC 2119, March 1997. 1743 [RFC2616] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., 1744 Masinter, L., Leach, P., and T. Berners-Lee, "Hypertext 1745 Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999. 1747 [SPDY] Belshe, M. and R. Peon, "SPDY PROTOCOL", 1748 . 1750 Author's Address 1752 Roberto Peon 1753 Google, Inc 1755 Email: fenix@google.com