1 // Copyright 2014 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package hpack 6 7 import ( 8 "bufio" 9 "bytes" 10 "encoding/hex" 11 "fmt" 12 "math/rand" 13 "reflect" 14 "regexp" 15 "strconv" 16 "strings" 17 "testing" 18 "time" 19 ) 20 21 func TestStaticTable(t *testing.T) { 22 fromSpec := ` 23 +-------+-----------------------------+---------------+ 24 | 1 | :authority | | 25 | 2 | :method | GET | 26 | 3 | :method | POST | 27 | 4 | :path | / | 28 | 5 | :path | /index.html | 29 | 6 | :scheme | http | 30 | 7 | :scheme | https | 31 | 8 | :status | 200 | 32 | 9 | :status | 204 | 33 | 10 | :status | 206 | 34 | 11 | :status | 304 | 35 | 12 | :status | 400 | 36 | 13 | :status | 404 | 37 | 14 | :status | 500 | 38 | 15 | accept-charset | | 39 | 16 | accept-encoding | gzip, deflate | 40 | 17 | accept-language | | 41 | 18 | accept-ranges | | 42 | 19 | accept | | 43 | 20 | access-control-allow-origin | | 44 | 21 | age | | 45 | 22 | allow | | 46 | 23 | authorization | | 47 | 24 | cache-control | | 48 | 25 | content-disposition | | 49 | 26 | content-encoding | | 50 | 27 | content-language | | 51 | 28 | content-length | | 52 | 29 | content-location | | 53 | 30 | content-range | | 54 | 31 | content-type | | 55 | 32 | cookie | | 56 | 33 | date | | 57 | 34 | etag | | 58 | 35 | expect | | 59 | 36 | expires | | 60 | 37 | from | | 61 | 38 | host | | 62 | 39 | if-match | | 63 | 40 | if-modified-since | | 64 | 41 | if-none-match | | 65 | 42 | if-range | | 66 | 43 | if-unmodified-since | | 67 | 44 | last-modified | | 68 | 45 | link | | 69 | 46 | location | | 70 | 47 | max-forwards | | 71 | 48 | proxy-authenticate | | 72 | 49 | proxy-authorization | | 73 | 50 | range | | 74 | 51 | referer | | 75 | 52 | refresh | | 76 | 53 | retry-after | | 77 | 54 | server | | 78 | 55 | set-cookie | | 79 | 56 | strict-transport-security | | 80 | 57 | transfer-encoding | | 81 | 58 | user-agent | | 82 | 59 | vary | | 83 | 60 | via | | 84 | 61 | www-authenticate | | 85 +-------+-----------------------------+---------------+ 86 ` 87 bs := bufio.NewScanner(strings.NewReader(fromSpec)) 88 re := regexp.MustCompile(`\| (\d+)\s+\| (\S+)\s*\| (\S(.*\S)?)?\s+\|`) 89 for bs.Scan() { 90 l := bs.Text() 91 if !strings.Contains(l, "|") { 92 continue 93 } 94 m := re.FindStringSubmatch(l) 95 if m == nil { 96 continue 97 } 98 i, err := strconv.Atoi(m[1]) 99 if err != nil { 100 t.Errorf("Bogus integer on line %q", l) 101 continue 102 } 103 if i < 1 || i > len(staticTable) { 104 t.Errorf("Bogus index %d on line %q", i, l) 105 continue 106 } 107 if got, want := staticTable[i-1].Name, m[2]; got != want { 108 t.Errorf("header index %d name = %q; want %q", i, got, want) 109 } 110 if got, want := staticTable[i-1].Value, m[3]; got != want { 111 t.Errorf("header index %d value = %q; want %q", i, got, want) 112 } 113 } 114 if err := bs.Err(); err != nil { 115 t.Error(err) 116 } 117 } 118 119 func (d *Decoder) mustAt(idx int) HeaderField { 120 if hf, ok := d.at(uint64(idx)); !ok { 121 panic(fmt.Sprintf("bogus index %d", idx)) 122 } else { 123 return hf 124 } 125 } 126 127 func TestDynamicTableAt(t *testing.T) { 128 d := NewDecoder(4096, nil) 129 at := d.mustAt 130 if got, want := at(2), (pair(":method", "GET")); got != want { 131 t.Errorf("at(2) = %v; want %v", got, want) 132 } 133 d.dynTab.add(pair("foo", "bar")) 134 d.dynTab.add(pair("blake", "miz")) 135 if got, want := at(len(staticTable)+1), (pair("blake", "miz")); got != want { 136 t.Errorf("at(dyn 1) = %v; want %v", got, want) 137 } 138 if got, want := at(len(staticTable)+2), (pair("foo", "bar")); got != want { 139 t.Errorf("at(dyn 2) = %v; want %v", got, want) 140 } 141 if got, want := at(3), (pair(":method", "POST")); got != want { 142 t.Errorf("at(3) = %v; want %v", got, want) 143 } 144 } 145 146 func TestDynamicTableSearch(t *testing.T) { 147 dt := dynamicTable{} 148 dt.setMaxSize(4096) 149 150 dt.add(pair("foo", "bar")) 151 dt.add(pair("blake", "miz")) 152 dt.add(pair(":method", "GET")) 153 154 tests := []struct { 155 hf HeaderField 156 wantI uint64 157 wantMatch bool 158 }{ 159 // Name and Value match 160 {pair("foo", "bar"), 3, true}, 161 {pair(":method", "GET"), 1, true}, 162 163 // Only name match because of Sensitive == true 164 {HeaderField{"blake", "miz", true}, 2, false}, 165 166 // Only Name matches 167 {pair("foo", "..."), 3, false}, 168 {pair("blake", "..."), 2, false}, 169 {pair(":method", "..."), 1, false}, 170 171 // None match 172 {pair("foo-", "bar"), 0, false}, 173 } 174 for _, tt := range tests { 175 if gotI, gotMatch := dt.search(tt.hf); gotI != tt.wantI || gotMatch != tt.wantMatch { 176 t.Errorf("d.search(%+v) = %v, %v; want %v, %v", tt.hf, gotI, gotMatch, tt.wantI, tt.wantMatch) 177 } 178 } 179 } 180 181 func TestDynamicTableSizeEvict(t *testing.T) { 182 d := NewDecoder(4096, nil) 183 if want := uint32(0); d.dynTab.size != want { 184 t.Fatalf("size = %d; want %d", d.dynTab.size, want) 185 } 186 add := d.dynTab.add 187 add(pair("blake", "eats pizza")) 188 if want := uint32(15 + 32); d.dynTab.size != want { 189 t.Fatalf("after pizza, size = %d; want %d", d.dynTab.size, want) 190 } 191 add(pair("foo", "bar")) 192 if want := uint32(15 + 32 + 6 + 32); d.dynTab.size != want { 193 t.Fatalf("after foo bar, size = %d; want %d", d.dynTab.size, want) 194 } 195 d.dynTab.setMaxSize(15 + 32 + 1 /* slop */) 196 if want := uint32(6 + 32); d.dynTab.size != want { 197 t.Fatalf("after setMaxSize, size = %d; want %d", d.dynTab.size, want) 198 } 199 if got, want := d.mustAt(len(staticTable)+1), (pair("foo", "bar")); got != want { 200 t.Errorf("at(dyn 1) = %v; want %v", got, want) 201 } 202 add(pair("long", strings.Repeat("x", 500))) 203 if want := uint32(0); d.dynTab.size != want { 204 t.Fatalf("after big one, size = %d; want %d", d.dynTab.size, want) 205 } 206 } 207 208 func TestDecoderDecode(t *testing.T) { 209 tests := []struct { 210 name string 211 in []byte 212 want []HeaderField 213 wantDynTab []HeaderField // newest entry first 214 }{ 215 // C.2.1 Literal Header Field with Indexing 216 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.1 217 {"C.2.1", dehex("400a 6375 7374 6f6d 2d6b 6579 0d63 7573 746f 6d2d 6865 6164 6572"), 218 []HeaderField{pair("custom-key", "custom-header")}, 219 []HeaderField{pair("custom-key", "custom-header")}, 220 }, 221 222 // C.2.2 Literal Header Field without Indexing 223 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.2 224 {"C.2.2", dehex("040c 2f73 616d 706c 652f 7061 7468"), 225 []HeaderField{pair(":path", "/sample/path")}, 226 []HeaderField{}}, 227 228 // C.2.3 Literal Header Field never Indexed 229 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.3 230 {"C.2.3", dehex("1008 7061 7373 776f 7264 0673 6563 7265 74"), 231 []HeaderField{{"password", "secret", true}}, 232 []HeaderField{}}, 233 234 // C.2.4 Indexed Header Field 235 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.4 236 {"C.2.4", []byte("\x82"), 237 []HeaderField{pair(":method", "GET")}, 238 []HeaderField{}}, 239 } 240 for _, tt := range tests { 241 d := NewDecoder(4096, nil) 242 hf, err := d.DecodeFull(tt.in) 243 if err != nil { 244 t.Errorf("%s: %v", tt.name, err) 245 continue 246 } 247 if !reflect.DeepEqual(hf, tt.want) { 248 t.Errorf("%s: Got %v; want %v", tt.name, hf, tt.want) 249 } 250 gotDynTab := d.dynTab.reverseCopy() 251 if !reflect.DeepEqual(gotDynTab, tt.wantDynTab) { 252 t.Errorf("%s: dynamic table after = %v; want %v", tt.name, gotDynTab, tt.wantDynTab) 253 } 254 } 255 } 256 257 func (dt *dynamicTable) reverseCopy() (hf []HeaderField) { 258 hf = make([]HeaderField, len(dt.ents)) 259 for i := range hf { 260 hf[i] = dt.ents[len(dt.ents)-1-i] 261 } 262 return 263 } 264 265 type encAndWant struct { 266 enc []byte 267 want []HeaderField 268 wantDynTab []HeaderField 269 wantDynSize uint32 270 } 271 272 // C.3 Request Examples without Huffman Coding 273 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.3 274 func TestDecodeC3_NoHuffman(t *testing.T) { 275 testDecodeSeries(t, 4096, []encAndWant{ 276 {dehex("8286 8441 0f77 7777 2e65 7861 6d70 6c65 2e63 6f6d"), 277 []HeaderField{ 278 pair(":method", "GET"), 279 pair(":scheme", "http"), 280 pair(":path", "/"), 281 pair(":authority", "www.example.com"), 282 }, 283 []HeaderField{ 284 pair(":authority", "www.example.com"), 285 }, 286 57, 287 }, 288 {dehex("8286 84be 5808 6e6f 2d63 6163 6865"), 289 []HeaderField{ 290 pair(":method", "GET"), 291 pair(":scheme", "http"), 292 pair(":path", "/"), 293 pair(":authority", "www.example.com"), 294 pair("cache-control", "no-cache"), 295 }, 296 []HeaderField{ 297 pair("cache-control", "no-cache"), 298 pair(":authority", "www.example.com"), 299 }, 300 110, 301 }, 302 {dehex("8287 85bf 400a 6375 7374 6f6d 2d6b 6579 0c63 7573 746f 6d2d 7661 6c75 65"), 303 []HeaderField{ 304 pair(":method", "GET"), 305 pair(":scheme", "https"), 306 pair(":path", "/index.html"), 307 pair(":authority", "www.example.com"), 308 pair("custom-key", "custom-value"), 309 }, 310 []HeaderField{ 311 pair("custom-key", "custom-value"), 312 pair("cache-control", "no-cache"), 313 pair(":authority", "www.example.com"), 314 }, 315 164, 316 }, 317 }) 318 } 319 320 // C.4 Request Examples with Huffman Coding 321 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.4 322 func TestDecodeC4_Huffman(t *testing.T) { 323 testDecodeSeries(t, 4096, []encAndWant{ 324 {dehex("8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff"), 325 []HeaderField{ 326 pair(":method", "GET"), 327 pair(":scheme", "http"), 328 pair(":path", "/"), 329 pair(":authority", "www.example.com"), 330 }, 331 []HeaderField{ 332 pair(":authority", "www.example.com"), 333 }, 334 57, 335 }, 336 {dehex("8286 84be 5886 a8eb 1064 9cbf"), 337 []HeaderField{ 338 pair(":method", "GET"), 339 pair(":scheme", "http"), 340 pair(":path", "/"), 341 pair(":authority", "www.example.com"), 342 pair("cache-control", "no-cache"), 343 }, 344 []HeaderField{ 345 pair("cache-control", "no-cache"), 346 pair(":authority", "www.example.com"), 347 }, 348 110, 349 }, 350 {dehex("8287 85bf 4088 25a8 49e9 5ba9 7d7f 8925 a849 e95b b8e8 b4bf"), 351 []HeaderField{ 352 pair(":method", "GET"), 353 pair(":scheme", "https"), 354 pair(":path", "/index.html"), 355 pair(":authority", "www.example.com"), 356 pair("custom-key", "custom-value"), 357 }, 358 []HeaderField{ 359 pair("custom-key", "custom-value"), 360 pair("cache-control", "no-cache"), 361 pair(":authority", "www.example.com"), 362 }, 363 164, 364 }, 365 }) 366 } 367 368 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.5 369 // "This section shows several consecutive header lists, corresponding 370 // to HTTP responses, on the same connection. The HTTP/2 setting 371 // parameter SETTINGS_HEADER_TABLE_SIZE is set to the value of 256 372 // octets, causing some evictions to occur." 373 func TestDecodeC5_ResponsesNoHuff(t *testing.T) { 374 testDecodeSeries(t, 256, []encAndWant{ 375 {dehex(` 376 4803 3330 3258 0770 7269 7661 7465 611d 377 4d6f 6e2c 2032 3120 4f63 7420 3230 3133 378 2032 303a 3133 3a32 3120 474d 546e 1768 379 7474 7073 3a2f 2f77 7777 2e65 7861 6d70 380 6c65 2e63 6f6d 381 `), 382 []HeaderField{ 383 pair(":status", "302"), 384 pair("cache-control", "private"), 385 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 386 pair("location", "https://www.example.com"), 387 }, 388 []HeaderField{ 389 pair("location", "https://www.example.com"), 390 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 391 pair("cache-control", "private"), 392 pair(":status", "302"), 393 }, 394 222, 395 }, 396 {dehex("4803 3330 37c1 c0bf"), 397 []HeaderField{ 398 pair(":status", "307"), 399 pair("cache-control", "private"), 400 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 401 pair("location", "https://www.example.com"), 402 }, 403 []HeaderField{ 404 pair(":status", "307"), 405 pair("location", "https://www.example.com"), 406 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 407 pair("cache-control", "private"), 408 }, 409 222, 410 }, 411 {dehex(` 412 88c1 611d 4d6f 6e2c 2032 3120 4f63 7420 413 3230 3133 2032 303a 3133 3a32 3220 474d 414 54c0 5a04 677a 6970 7738 666f 6f3d 4153 415 444a 4b48 514b 425a 584f 5157 454f 5049 416 5541 5851 5745 4f49 553b 206d 6178 2d61 417 6765 3d33 3630 303b 2076 6572 7369 6f6e 418 3d31 419 `), 420 []HeaderField{ 421 pair(":status", "200"), 422 pair("cache-control", "private"), 423 pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"), 424 pair("location", "https://www.example.com"), 425 pair("content-encoding", "gzip"), 426 pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"), 427 }, 428 []HeaderField{ 429 pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"), 430 pair("content-encoding", "gzip"), 431 pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"), 432 }, 433 215, 434 }, 435 }) 436 } 437 438 // http://http2.github.io/http2-spec/compression.html#rfc.section.C.6 439 // "This section shows the same examples as the previous section, but 440 // using Huffman encoding for the literal values. The HTTP/2 setting 441 // parameter SETTINGS_HEADER_TABLE_SIZE is set to the value of 256 442 // octets, causing some evictions to occur. The eviction mechanism 443 // uses the length of the decoded literal values, so the same 444 // evictions occurs as in the previous section." 445 func TestDecodeC6_ResponsesHuffman(t *testing.T) { 446 testDecodeSeries(t, 256, []encAndWant{ 447 {dehex(` 448 4882 6402 5885 aec3 771a 4b61 96d0 7abe 449 9410 54d4 44a8 2005 9504 0b81 66e0 82a6 450 2d1b ff6e 919d 29ad 1718 63c7 8f0b 97c8 451 e9ae 82ae 43d3 452 `), 453 []HeaderField{ 454 pair(":status", "302"), 455 pair("cache-control", "private"), 456 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 457 pair("location", "https://www.example.com"), 458 }, 459 []HeaderField{ 460 pair("location", "https://www.example.com"), 461 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 462 pair("cache-control", "private"), 463 pair(":status", "302"), 464 }, 465 222, 466 }, 467 {dehex("4883 640e ffc1 c0bf"), 468 []HeaderField{ 469 pair(":status", "307"), 470 pair("cache-control", "private"), 471 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 472 pair("location", "https://www.example.com"), 473 }, 474 []HeaderField{ 475 pair(":status", "307"), 476 pair("location", "https://www.example.com"), 477 pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), 478 pair("cache-control", "private"), 479 }, 480 222, 481 }, 482 {dehex(` 483 88c1 6196 d07a be94 1054 d444 a820 0595 484 040b 8166 e084 a62d 1bff c05a 839b d9ab 485 77ad 94e7 821d d7f2 e6c7 b335 dfdf cd5b 486 3960 d5af 2708 7f36 72c1 ab27 0fb5 291f 487 9587 3160 65c0 03ed 4ee5 b106 3d50 07 488 `), 489 []HeaderField{ 490 pair(":status", "200"), 491 pair("cache-control", "private"), 492 pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"), 493 pair("location", "https://www.example.com"), 494 pair("content-encoding", "gzip"), 495 pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"), 496 }, 497 []HeaderField{ 498 pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"), 499 pair("content-encoding", "gzip"), 500 pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"), 501 }, 502 215, 503 }, 504 }) 505 } 506 507 func testDecodeSeries(t *testing.T, size uint32, steps []encAndWant) { 508 d := NewDecoder(size, nil) 509 for i, step := range steps { 510 hf, err := d.DecodeFull(step.enc) 511 if err != nil { 512 t.Fatalf("Error at step index %d: %v", i, err) 513 } 514 if !reflect.DeepEqual(hf, step.want) { 515 t.Fatalf("At step index %d: Got headers %v; want %v", i, hf, step.want) 516 } 517 gotDynTab := d.dynTab.reverseCopy() 518 if !reflect.DeepEqual(gotDynTab, step.wantDynTab) { 519 t.Errorf("After step index %d, dynamic table = %v; want %v", i, gotDynTab, step.wantDynTab) 520 } 521 if d.dynTab.size != step.wantDynSize { 522 t.Errorf("After step index %d, dynamic table size = %v; want %v", i, d.dynTab.size, step.wantDynSize) 523 } 524 } 525 } 526 527 func TestHuffmanDecodeExcessPadding(t *testing.T) { 528 tests := [][]byte{ 529 {0xff}, // Padding Exceeds 7 bits 530 {0x1f, 0xff}, // {"a", 1 byte excess padding} 531 {0x1f, 0xff, 0xff}, // {"a", 2 byte excess padding} 532 {0x1f, 0xff, 0xff, 0xff}, // {"a", 3 byte excess padding} 533 {0xff, 0x9f, 0xff, 0xff, 0xff}, // {"a", 29 bit excess padding} 534 {'R', 0xbc, '0', 0xff, 0xff, 0xff, 0xff}, // Padding ends on partial symbol. 535 } 536 for i, in := range tests { 537 var buf bytes.Buffer 538 if _, err := HuffmanDecode(&buf, in); err != ErrInvalidHuffman { 539 t.Errorf("test-%d: decode(%q) = %v; want ErrInvalidHuffman", i, in, err) 540 } 541 } 542 } 543 544 func TestHuffmanDecodeEOS(t *testing.T) { 545 in := []byte{0xff, 0xff, 0xff, 0xff, 0xfc} // {EOS, "?"} 546 var buf bytes.Buffer 547 if _, err := HuffmanDecode(&buf, in); err != ErrInvalidHuffman { 548 t.Errorf("error = %v; want ErrInvalidHuffman", err) 549 } 550 } 551 552 func TestHuffmanDecodeMaxLengthOnTrailingByte(t *testing.T) { 553 in := []byte{0x00, 0x01} // {"0", "0", "0"} 554 var buf bytes.Buffer 555 if err := huffmanDecode(&buf, 2, in); err != ErrStringLength { 556 t.Errorf("error = %v; want ErrStringLength", err) 557 } 558 } 559 560 func TestHuffmanDecodeCorruptPadding(t *testing.T) { 561 in := []byte{0x00} 562 var buf bytes.Buffer 563 if _, err := HuffmanDecode(&buf, in); err != ErrInvalidHuffman { 564 t.Errorf("error = %v; want ErrInvalidHuffman", err) 565 } 566 } 567 568 func TestHuffmanDecode(t *testing.T) { 569 tests := []struct { 570 inHex, want string 571 }{ 572 {"f1e3 c2e5 f23a 6ba0 ab90 f4ff", "www.example.com"}, 573 {"a8eb 1064 9cbf", "no-cache"}, 574 {"25a8 49e9 5ba9 7d7f", "custom-key"}, 575 {"25a8 49e9 5bb8 e8b4 bf", "custom-value"}, 576 {"6402", "302"}, 577 {"aec3 771a 4b", "private"}, 578 {"d07a be94 1054 d444 a820 0595 040b 8166 e082 a62d 1bff", "Mon, 21 Oct 2013 20:13:21 GMT"}, 579 {"9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 d3", "https://www.example.com"}, 580 {"9bd9 ab", "gzip"}, 581 {"94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 3160 65c0 03ed 4ee5 b106 3d50 07", 582 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"}, 583 } 584 for i, tt := range tests { 585 var buf bytes.Buffer 586 in, err := hex.DecodeString(strings.Replace(tt.inHex, " ", "", -1)) 587 if err != nil { 588 t.Errorf("%d. hex input error: %v", i, err) 589 continue 590 } 591 if _, err := HuffmanDecode(&buf, in); err != nil { 592 t.Errorf("%d. decode error: %v", i, err) 593 continue 594 } 595 if got := buf.String(); tt.want != got { 596 t.Errorf("%d. decode = %q; want %q", i, got, tt.want) 597 } 598 } 599 } 600 601 func TestAppendHuffmanString(t *testing.T) { 602 tests := []struct { 603 in, want string 604 }{ 605 {"www.example.com", "f1e3 c2e5 f23a 6ba0 ab90 f4ff"}, 606 {"no-cache", "a8eb 1064 9cbf"}, 607 {"custom-key", "25a8 49e9 5ba9 7d7f"}, 608 {"custom-value", "25a8 49e9 5bb8 e8b4 bf"}, 609 {"302", "6402"}, 610 {"private", "aec3 771a 4b"}, 611 {"Mon, 21 Oct 2013 20:13:21 GMT", "d07a be94 1054 d444 a820 0595 040b 8166 e082 a62d 1bff"}, 612 {"https://www.example.com", "9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 d3"}, 613 {"gzip", "9bd9 ab"}, 614 {"foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", 615 "94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 3160 65c0 03ed 4ee5 b106 3d50 07"}, 616 } 617 for i, tt := range tests { 618 buf := []byte{} 619 want := strings.Replace(tt.want, " ", "", -1) 620 buf = AppendHuffmanString(buf, tt.in) 621 if got := hex.EncodeToString(buf); want != got { 622 t.Errorf("%d. encode = %q; want %q", i, got, want) 623 } 624 } 625 } 626 627 func TestHuffmanMaxStrLen(t *testing.T) { 628 const msg = "Some string" 629 huff := AppendHuffmanString(nil, msg) 630 631 testGood := func(max int) { 632 var out bytes.Buffer 633 if err := huffmanDecode(&out, max, huff); err != nil { 634 t.Errorf("For maxLen=%d, unexpected error: %v", max, err) 635 } 636 if out.String() != msg { 637 t.Errorf("For maxLen=%d, out = %q; want %q", max, out.String(), msg) 638 } 639 } 640 testGood(0) 641 testGood(len(msg)) 642 testGood(len(msg) + 1) 643 644 var out bytes.Buffer 645 if err := huffmanDecode(&out, len(msg)-1, huff); err != ErrStringLength { 646 t.Errorf("err = %v; want ErrStringLength", err) 647 } 648 } 649 650 func TestHuffmanRoundtripStress(t *testing.T) { 651 const Len = 50 // of uncompressed string 652 input := make([]byte, Len) 653 var output bytes.Buffer 654 var huff []byte 655 656 n := 5000 657 if testing.Short() { 658 n = 100 659 } 660 seed := time.Now().UnixNano() 661 t.Logf("Seed = %v", seed) 662 src := rand.New(rand.NewSource(seed)) 663 var encSize int64 664 for i := 0; i < n; i++ { 665 for l := range input { 666 input[l] = byte(src.Intn(256)) 667 } 668 huff = AppendHuffmanString(huff[:0], string(input)) 669 encSize += int64(len(huff)) 670 output.Reset() 671 if err := huffmanDecode(&output, 0, huff); err != nil { 672 t.Errorf("Failed to decode %q -> %q -> error %v", input, huff, err) 673 continue 674 } 675 if !bytes.Equal(output.Bytes(), input) { 676 t.Errorf("Roundtrip failure on %q -> %q -> %q", input, huff, output.Bytes()) 677 } 678 } 679 t.Logf("Compressed size of original: %0.02f%% (%v -> %v)", 100*(float64(encSize)/(Len*float64(n))), Len*n, encSize) 680 } 681 682 func TestHuffmanDecodeFuzz(t *testing.T) { 683 const Len = 50 // of compressed 684 var buf, zbuf bytes.Buffer 685 686 n := 5000 687 if testing.Short() { 688 n = 100 689 } 690 seed := time.Now().UnixNano() 691 t.Logf("Seed = %v", seed) 692 src := rand.New(rand.NewSource(seed)) 693 numFail := 0 694 for i := 0; i < n; i++ { 695 zbuf.Reset() 696 if i == 0 { 697 // Start with at least one invalid one. 698 zbuf.WriteString("00\x91\xff\xff\xff\xff\xc8") 699 } else { 700 for l := 0; l < Len; l++ { 701 zbuf.WriteByte(byte(src.Intn(256))) 702 } 703 } 704 705 buf.Reset() 706 if err := huffmanDecode(&buf, 0, zbuf.Bytes()); err != nil { 707 if err == ErrInvalidHuffman { 708 numFail++ 709 continue 710 } 711 t.Errorf("Failed to decode %q: %v", zbuf.Bytes(), err) 712 continue 713 } 714 } 715 t.Logf("%0.02f%% are invalid (%d / %d)", 100*float64(numFail)/float64(n), numFail, n) 716 if numFail < 1 { 717 t.Error("expected at least one invalid huffman encoding (test starts with one)") 718 } 719 } 720 721 func TestReadVarInt(t *testing.T) { 722 type res struct { 723 i uint64 724 consumed int 725 err error 726 } 727 tests := []struct { 728 n byte 729 p []byte 730 want res 731 }{ 732 // Fits in a byte: 733 {1, []byte{0}, res{0, 1, nil}}, 734 {2, []byte{2}, res{2, 1, nil}}, 735 {3, []byte{6}, res{6, 1, nil}}, 736 {4, []byte{14}, res{14, 1, nil}}, 737 {5, []byte{30}, res{30, 1, nil}}, 738 {6, []byte{62}, res{62, 1, nil}}, 739 {7, []byte{126}, res{126, 1, nil}}, 740 {8, []byte{254}, res{254, 1, nil}}, 741 742 // Doesn't fit in a byte: 743 {1, []byte{1}, res{0, 0, errNeedMore}}, 744 {2, []byte{3}, res{0, 0, errNeedMore}}, 745 {3, []byte{7}, res{0, 0, errNeedMore}}, 746 {4, []byte{15}, res{0, 0, errNeedMore}}, 747 {5, []byte{31}, res{0, 0, errNeedMore}}, 748 {6, []byte{63}, res{0, 0, errNeedMore}}, 749 {7, []byte{127}, res{0, 0, errNeedMore}}, 750 {8, []byte{255}, res{0, 0, errNeedMore}}, 751 752 // Ignoring top bits: 753 {5, []byte{255, 154, 10}, res{1337, 3, nil}}, // high dummy three bits: 111 754 {5, []byte{159, 154, 10}, res{1337, 3, nil}}, // high dummy three bits: 100 755 {5, []byte{191, 154, 10}, res{1337, 3, nil}}, // high dummy three bits: 101 756 757 // Extra byte: 758 {5, []byte{191, 154, 10, 2}, res{1337, 3, nil}}, // extra byte 759 760 // Short a byte: 761 {5, []byte{191, 154}, res{0, 0, errNeedMore}}, 762 763 // integer overflow: 764 {1, []byte{255, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128}, res{0, 0, errVarintOverflow}}, 765 } 766 for _, tt := range tests { 767 i, remain, err := readVarInt(tt.n, tt.p) 768 consumed := len(tt.p) - len(remain) 769 got := res{i, consumed, err} 770 if got != tt.want { 771 t.Errorf("readVarInt(%d, %v ~ %x) = %+v; want %+v", tt.n, tt.p, tt.p, got, tt.want) 772 } 773 } 774 } 775 776 // Fuzz crash, originally reported at https://github.com/bradfitz/http2/issues/56 777 func TestHuffmanFuzzCrash(t *testing.T) { 778 got, err := HuffmanDecodeToString([]byte("00\x91\xff\xff\xff\xff\xc8")) 779 if got != "" { 780 t.Errorf("Got %q; want empty string", got) 781 } 782 if err != ErrInvalidHuffman { 783 t.Errorf("Err = %v; want ErrInvalidHuffman", err) 784 } 785 } 786 787 func dehex(s string) []byte { 788 s = strings.Replace(s, " ", "", -1) 789 s = strings.Replace(s, "\n", "", -1) 790 b, err := hex.DecodeString(s) 791 if err != nil { 792 panic(err) 793 } 794 return b 795 } 796 797 func TestEmitEnabled(t *testing.T) { 798 var buf bytes.Buffer 799 enc := NewEncoder(&buf) 800 enc.WriteField(HeaderField{Name: "foo", Value: "bar"}) 801 enc.WriteField(HeaderField{Name: "foo", Value: "bar"}) 802 803 numCallback := 0 804 var dec *Decoder 805 dec = NewDecoder(8<<20, func(HeaderField) { 806 numCallback++ 807 dec.SetEmitEnabled(false) 808 }) 809 if !dec.EmitEnabled() { 810 t.Errorf("initial emit enabled = false; want true") 811 } 812 if _, err := dec.Write(buf.Bytes()); err != nil { 813 t.Error(err) 814 } 815 if numCallback != 1 { 816 t.Errorf("num callbacks = %d; want 1", numCallback) 817 } 818 if dec.EmitEnabled() { 819 t.Errorf("emit enabled = true; want false") 820 } 821 } 822 823 func TestSaveBufLimit(t *testing.T) { 824 const maxStr = 1 << 10 825 var got []HeaderField 826 dec := NewDecoder(initialHeaderTableSize, func(hf HeaderField) { 827 got = append(got, hf) 828 }) 829 dec.SetMaxStringLength(maxStr) 830 var frag []byte 831 frag = append(frag[:0], encodeTypeByte(false, false)) 832 frag = appendVarInt(frag, 7, 3) 833 frag = append(frag, "foo"...) 834 frag = appendVarInt(frag, 7, 3) 835 frag = append(frag, "bar"...) 836 837 if _, err := dec.Write(frag); err != nil { 838 t.Fatal(err) 839 } 840 841 want := []HeaderField{{Name: "foo", Value: "bar"}} 842 if !reflect.DeepEqual(got, want) { 843 t.Errorf("After small writes, got %v; want %v", got, want) 844 } 845 846 frag = append(frag[:0], encodeTypeByte(false, false)) 847 frag = appendVarInt(frag, 7, maxStr*3) 848 frag = append(frag, make([]byte, maxStr*3)...) 849 850 _, err := dec.Write(frag) 851 if err != ErrStringLength { 852 t.Fatalf("Write error = %v; want ErrStringLength", err) 853 } 854 } 855