1/*
2 * Copyright (C) 2013 Square, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package com.squareup.okhttp.internal.spdy;
17
18import java.io.IOException;
19import java.util.Arrays;
20import java.util.List;
21import okio.ByteString;
22import okio.OkBuffer;
23import org.junit.Before;
24import org.junit.Test;
25
26import static com.squareup.okhttp.internal.Util.headerEntries;
27import static org.junit.Assert.assertEquals;
28import static org.junit.Assert.assertFalse;
29import static org.junit.Assert.assertTrue;
30
31public class HpackDraft05Test {
32
33  private final OkBuffer bytesIn = new OkBuffer();
34  private HpackDraft05.Reader hpackReader;
35  private OkBuffer bytesOut = new OkBuffer();
36  private HpackDraft05.Writer hpackWriter;
37
38  @Before public void reset() {
39    hpackReader = newReader(bytesIn);
40    hpackWriter = new HpackDraft05.Writer(bytesOut);
41  }
42
43  /**
44   * Variable-length quantity special cases strings which are longer than 127
45   * bytes.  Values such as cookies can be 4KiB, and should be possible to send.
46   *
47   * <p> http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-4.1.2
48   */
49  @Test public void largeHeaderValue() throws IOException {
50    char[] value = new char[4096];
51    Arrays.fill(value, '!');
52    List<Header> headerBlock = headerEntries("cookie", new String(value));
53
54    hpackWriter.writeHeaders(headerBlock);
55    bytesIn.write(bytesOut, bytesOut.size());
56    hpackReader.readHeaders();
57    hpackReader.emitReferenceSet();
58
59    assertEquals(0, hpackReader.headerCount);
60
61    assertEquals(headerBlock, hpackReader.getAndReset());
62  }
63
64  /**
65   * HPACK has a max header table size, which can be smaller than the max header message.
66   * Ensure the larger header content is not lost.
67   */
68  @Test public void tooLargeToHPackIsStillEmitted() throws IOException {
69    OkBuffer out = new OkBuffer();
70
71    out.writeByte(0x00); // Literal indexed
72    out.writeByte(0x0a); // Literal name (len = 10)
73    out.writeUtf8("custom-key");
74
75    out.writeByte(0x0d); // Literal value (len = 13)
76    out.writeUtf8("custom-header");
77
78    bytesIn.write(out, out.size());
79    hpackReader.maxHeaderTableByteCount(1);
80    hpackReader.readHeaders();
81    hpackReader.emitReferenceSet();
82
83    assertEquals(0, hpackReader.headerCount);
84
85    assertEquals(headerEntries("custom-key", "custom-header"), hpackReader.getAndReset());
86  }
87
88  /** Oldest entries are evicted to support newer ones. */
89  @Test public void testEviction() throws IOException {
90    OkBuffer out = new OkBuffer();
91
92    out.writeByte(0x00); // Literal indexed
93    out.writeByte(0x0a); // Literal name (len = 10)
94    out.writeUtf8("custom-foo");
95
96    out.writeByte(0x0d); // Literal value (len = 13)
97    out.writeUtf8("custom-header");
98
99    out.writeByte(0x00); // Literal indexed
100    out.writeByte(0x0a); // Literal name (len = 10)
101    out.writeUtf8("custom-bar");
102
103    out.writeByte(0x0d); // Literal value (len = 13)
104    out.writeUtf8("custom-header");
105
106    out.writeByte(0x00); // Literal indexed
107    out.writeByte(0x0a); // Literal name (len = 10)
108    out.writeUtf8("custom-baz");
109
110    out.writeByte(0x0d); // Literal value (len = 13)
111    out.writeUtf8("custom-header");
112
113    bytesIn.write(out, out.size());
114    // Set to only support 110 bytes (enough for 2 headers).
115    hpackReader.maxHeaderTableByteCount(110);
116    hpackReader.readHeaders();
117    hpackReader.emitReferenceSet();
118
119    assertEquals(2, hpackReader.headerCount);
120
121    Header entry = hpackReader.headerTable[headerTableLength() - 1];
122    checkEntry(entry, "custom-bar", "custom-header", 55);
123    assertHeaderReferenced(headerTableLength() - 1);
124
125    entry = hpackReader.headerTable[headerTableLength() - 2];
126    checkEntry(entry, "custom-baz", "custom-header", 55);
127    assertHeaderReferenced(headerTableLength() - 2);
128
129    // foo isn't here as it is no longer in the table.
130    // TODO: emit before eviction?
131    assertEquals(headerEntries("custom-bar", "custom-header", "custom-baz", "custom-header"),
132        hpackReader.getAndReset());
133
134    // Simulate receiving a small settings frame, that implies eviction.
135    hpackReader.maxHeaderTableByteCount(55);
136    assertEquals(1, hpackReader.headerCount);
137  }
138
139  /** Header table backing array is initially 8 long, let's ensure it grows. */
140  @Test public void dynamicallyGrowsBeyond64Entries() throws IOException {
141    OkBuffer out = new OkBuffer();
142
143    for (int i = 0; i < 256; i++) {
144      out.writeByte(0x00); // Literal indexed
145      out.writeByte(0x0a); // Literal name (len = 10)
146      out.writeUtf8("custom-foo");
147
148      out.writeByte(0x0d); // Literal value (len = 13)
149      out.writeUtf8("custom-header");
150    }
151
152    bytesIn.write(out, out.size());
153    hpackReader.maxHeaderTableByteCount(16384); // Lots of headers need more room!
154    hpackReader.readHeaders();
155    hpackReader.emitReferenceSet();
156
157    assertEquals(256, hpackReader.headerCount);
158    assertHeaderReferenced(headerTableLength() - 1);
159    assertHeaderReferenced(headerTableLength() - hpackReader.headerCount);
160  }
161
162  @Test public void huffmanDecodingSupported() throws IOException {
163    OkBuffer out = new OkBuffer();
164
165    out.writeByte(0x04); // == Literal indexed ==
166                         // Indexed name (idx = 4) -> :path
167    out.writeByte(0x8b); // Literal value Huffman encoded 11 bytes
168                         // decodes to www.example.com which is length 15
169    byte[] huffmanBytes = new byte[] {
170        (byte) 0xdb, (byte) 0x6d, (byte) 0x88, (byte) 0x3e,
171        (byte) 0x68, (byte) 0xd1, (byte) 0xcb, (byte) 0x12,
172        (byte) 0x25, (byte) 0xba, (byte) 0x7f};
173    out.write(huffmanBytes, 0, huffmanBytes.length);
174
175    bytesIn.write(out, out.size());
176    hpackReader.readHeaders();
177    hpackReader.emitReferenceSet();
178
179    assertEquals(1, hpackReader.headerCount);
180    assertEquals(52, hpackReader.headerTableByteCount);
181
182    Header entry = hpackReader.headerTable[headerTableLength() - 1];
183    checkEntry(entry, ":path", "www.example.com", 52);
184    assertHeaderReferenced(headerTableLength() - 1);
185  }
186
187  /**
188   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-E.1.1
189   */
190  @Test public void readLiteralHeaderFieldWithIndexing() throws IOException {
191    OkBuffer out = new OkBuffer();
192
193    out.writeByte(0x00); // Literal indexed
194    out.writeByte(0x0a); // Literal name (len = 10)
195    out.writeUtf8("custom-key");
196
197    out.writeByte(0x0d); // Literal value (len = 13)
198    out.writeUtf8("custom-header");
199
200    bytesIn.write(out, out.size());
201    hpackReader.readHeaders();
202    hpackReader.emitReferenceSet();
203
204    assertEquals(1, hpackReader.headerCount);
205    assertEquals(55, hpackReader.headerTableByteCount);
206
207    Header entry = hpackReader.headerTable[headerTableLength() - 1];
208    checkEntry(entry, "custom-key", "custom-header", 55);
209    assertHeaderReferenced(headerTableLength() - 1);
210
211    assertEquals(headerEntries("custom-key", "custom-header"), hpackReader.getAndReset());
212  }
213
214  /**
215   * Literal Header Field without Indexing - New Name
216   */
217  @Test public void literalHeaderFieldWithoutIndexingNewName() throws IOException {
218    List<Header> headerBlock = headerEntries("custom-key", "custom-header");
219
220    OkBuffer expectedBytes = new OkBuffer();
221
222    expectedBytes.writeByte(0x40); // Not indexed
223    expectedBytes.writeByte(0x0a); // Literal name (len = 10)
224    expectedBytes.write("custom-key".getBytes(), 0, 10);
225
226    expectedBytes.writeByte(0x0d); // Literal value (len = 13)
227    expectedBytes.write("custom-header".getBytes(), 0, 13);
228
229    hpackWriter.writeHeaders(headerBlock);
230    assertEquals(expectedBytes, bytesOut);
231
232    bytesIn.write(bytesOut, bytesOut.size());
233    hpackReader.readHeaders();
234    hpackReader.emitReferenceSet();
235
236    assertEquals(0, hpackReader.headerCount);
237
238    assertEquals(headerBlock, hpackReader.getAndReset());
239  }
240
241  /**
242   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-E.1.2
243   */
244  @Test public void literalHeaderFieldWithoutIndexingIndexedName() throws IOException {
245    List<Header> headerBlock = headerEntries(":path", "/sample/path");
246
247    OkBuffer expectedBytes = new OkBuffer();
248    expectedBytes.writeByte(0x44); // == Literal not indexed ==
249                                   // Indexed name (idx = 4) -> :path
250    expectedBytes.writeByte(0x0c); // Literal value (len = 12)
251    expectedBytes.write("/sample/path".getBytes(), 0, 12);
252
253    hpackWriter.writeHeaders(headerBlock);
254    assertEquals(expectedBytes, bytesOut);
255
256    bytesIn.write(bytesOut, bytesOut.size());
257    hpackReader.readHeaders();
258    hpackReader.emitReferenceSet();
259
260    assertEquals(0, hpackReader.headerCount);
261
262    assertEquals(headerBlock, hpackReader.getAndReset());
263  }
264
265  /**
266   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-E.1.3
267   */
268  @Test public void readIndexedHeaderField() throws IOException {
269    bytesIn.writeByte(0x82); // == Indexed - Add ==
270                             // idx = 2 -> :method: GET
271
272    hpackReader.readHeaders();
273    hpackReader.emitReferenceSet();
274
275    assertEquals(1, hpackReader.headerCount);
276    assertEquals(42, hpackReader.headerTableByteCount);
277
278    Header entry = hpackReader.headerTable[headerTableLength() - 1];
279    checkEntry(entry, ":method", "GET", 42);
280    assertHeaderReferenced(headerTableLength() - 1);
281
282    assertEquals(headerEntries(":method", "GET"), hpackReader.getAndReset());
283  }
284
285  /**
286   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-3.2.1
287   */
288  @Test public void toggleIndex() throws IOException {
289    // Static table entries are copied to the top of the reference set.
290    bytesIn.writeByte(0x82); // == Indexed - Add ==
291                             // idx = 2 -> :method: GET
292    // Specifying an index to an entry in the reference set removes it.
293    bytesIn.writeByte(0x81); // == Indexed - Remove ==
294                             // idx = 1 -> :method: GET
295
296    hpackReader.readHeaders();
297    hpackReader.emitReferenceSet();
298
299    assertEquals(1, hpackReader.headerCount);
300    assertEquals(42, hpackReader.headerTableByteCount);
301
302    Header entry = hpackReader.headerTable[headerTableLength() - 1];
303    checkEntry(entry, ":method", "GET", 42);
304    assertHeaderNotReferenced(headerTableLength() - 1);
305
306    assertTrue(hpackReader.getAndReset().isEmpty());
307  }
308
309  /** Ensure a later toggle of the same index emits! */
310  @Test public void toggleIndexOffOn() throws IOException {
311
312    bytesIn.writeByte(0x82); // Copy static header 1 to the header table as index 1.
313    bytesIn.writeByte(0x81); // Remove index 1 from the reference set.
314
315    hpackReader.readHeaders();
316    hpackReader.emitReferenceSet();
317    assertEquals(1, hpackReader.headerCount);
318    assertTrue(hpackReader.getAndReset().isEmpty());
319
320    bytesIn.writeByte(0x81); // Add index 1 back to the reference set.
321
322    hpackReader.readHeaders();
323    hpackReader.emitReferenceSet();
324    assertEquals(1, hpackReader.headerCount);
325    assertEquals(headerEntries(":method", "GET"), hpackReader.getAndReset());
326  }
327
328  /** Check later toggle of the same index for large header sets. */
329  @Test public void toggleIndexOffBeyond64Entries() throws IOException {
330    int expectedHeaderCount = 65;
331
332    for (int i = 0; i < expectedHeaderCount; i++) {
333      bytesIn.writeByte(0x82 + i); // Copy static header 1 to the header table as index 1.
334      bytesIn.writeByte(0x81); // Remove index 1 from the reference set.
335    }
336
337    hpackReader.readHeaders();
338    hpackReader.emitReferenceSet();
339    assertEquals(expectedHeaderCount, hpackReader.headerCount);
340    assertTrue(hpackReader.getAndReset().isEmpty());
341
342    bytesIn.writeByte(0x81); // Add index 1 back to the reference set.
343
344    hpackReader.readHeaders();
345    hpackReader.emitReferenceSet();
346    assertEquals(expectedHeaderCount, hpackReader.headerCount);
347    assertHeaderReferenced(headerTableLength() - expectedHeaderCount);
348    assertEquals(headerEntries(":method", "GET"), hpackReader.getAndReset());
349  }
350
351  /**
352   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-E.1.4
353   */
354  @Test public void readIndexedHeaderFieldFromStaticTableWithoutBuffering() throws IOException {
355    bytesIn.writeByte(0x82); // == Indexed - Add ==
356                             // idx = 2 -> :method: GET
357
358    hpackReader.maxHeaderTableByteCount(0); // SETTINGS_HEADER_TABLE_SIZE == 0
359    hpackReader.readHeaders();
360    hpackReader.emitReferenceSet();
361
362    // Not buffered in header table.
363    assertEquals(0, hpackReader.headerCount);
364
365    assertEquals(headerEntries(":method", "GET"), hpackReader.getAndReset());
366  }
367
368  /**
369   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-E.2
370   */
371  @Test public void readRequestExamplesWithoutHuffman() throws IOException {
372    OkBuffer out = firstRequestWithoutHuffman();
373    bytesIn.write(out, out.size());
374    hpackReader.readHeaders();
375    hpackReader.emitReferenceSet();
376    checkReadFirstRequestWithoutHuffman();
377
378    out = secondRequestWithoutHuffman();
379    bytesIn.write(out, out.size());
380    hpackReader.readHeaders();
381    hpackReader.emitReferenceSet();
382    checkReadSecondRequestWithoutHuffman();
383
384    out = thirdRequestWithoutHuffman();
385    bytesIn.write(out, out.size());
386    hpackReader.readHeaders();
387    hpackReader.emitReferenceSet();
388    checkReadThirdRequestWithoutHuffman();
389  }
390
391  private OkBuffer firstRequestWithoutHuffman() {
392    OkBuffer out = new OkBuffer();
393
394    out.writeByte(0x82); // == Indexed - Add ==
395                         // idx = 2 -> :method: GET
396    out.writeByte(0x87); // == Indexed - Add ==
397                         // idx = 7 -> :scheme: http
398    out.writeByte(0x86); // == Indexed - Add ==
399                         // idx = 6 -> :path: /
400    out.writeByte(0x04); // == Literal indexed ==
401                         // Indexed name (idx = 4) -> :authority
402    out.writeByte(0x0f); // Literal value (len = 15)
403    out.writeUtf8("www.example.com");
404
405    return out;
406  }
407
408  private void checkReadFirstRequestWithoutHuffman() {
409    assertEquals(4, hpackReader.headerCount);
410
411    // [  1] (s =  57) :authority: www.example.com
412    Header entry = hpackReader.headerTable[headerTableLength() - 4];
413    checkEntry(entry, ":authority", "www.example.com", 57);
414    assertHeaderReferenced(headerTableLength() - 4);
415
416    // [  2] (s =  38) :path: /
417    entry = hpackReader.headerTable[headerTableLength() - 3];
418    checkEntry(entry, ":path", "/", 38);
419    assertHeaderReferenced(headerTableLength() - 3);
420
421    // [  3] (s =  43) :scheme: http
422    entry = hpackReader.headerTable[headerTableLength() - 2];
423    checkEntry(entry, ":scheme", "http", 43);
424    assertHeaderReferenced(headerTableLength() - 2);
425
426    // [  4] (s =  42) :method: GET
427    entry = hpackReader.headerTable[headerTableLength() - 1];
428    checkEntry(entry, ":method", "GET", 42);
429    assertHeaderReferenced(headerTableLength() - 1);
430
431    // Table size: 180
432    assertEquals(180, hpackReader.headerTableByteCount);
433
434    // Decoded header set:
435    assertEquals(headerEntries(
436        ":method", "GET",
437        ":scheme", "http",
438        ":path", "/",
439        ":authority", "www.example.com"), hpackReader.getAndReset());
440  }
441
442  private OkBuffer secondRequestWithoutHuffman() {
443    OkBuffer out = new OkBuffer();
444
445    out.writeByte(0x1b); // == Literal indexed ==
446                         // Indexed name (idx = 27) -> cache-control
447    out.writeByte(0x08); // Literal value (len = 8)
448    out.writeUtf8("no-cache");
449
450    return out;
451  }
452
453  private void checkReadSecondRequestWithoutHuffman() {
454    assertEquals(5, hpackReader.headerCount);
455
456    // [  1] (s =  53) cache-control: no-cache
457    Header entry = hpackReader.headerTable[headerTableLength() - 5];
458    checkEntry(entry, "cache-control", "no-cache", 53);
459    assertHeaderReferenced(headerTableLength() - 5);
460
461    // [  2] (s =  57) :authority: www.example.com
462    entry = hpackReader.headerTable[headerTableLength() - 4];
463    checkEntry(entry, ":authority", "www.example.com", 57);
464    assertHeaderReferenced(headerTableLength() - 4);
465
466    // [  3] (s =  38) :path: /
467    entry = hpackReader.headerTable[headerTableLength() - 3];
468    checkEntry(entry, ":path", "/", 38);
469    assertHeaderReferenced(headerTableLength() - 3);
470
471    // [  4] (s =  43) :scheme: http
472    entry = hpackReader.headerTable[headerTableLength() - 2];
473    checkEntry(entry, ":scheme", "http", 43);
474    assertHeaderReferenced(headerTableLength() - 2);
475
476    // [  5] (s =  42) :method: GET
477    entry = hpackReader.headerTable[headerTableLength() - 1];
478    checkEntry(entry, ":method", "GET", 42);
479    assertHeaderReferenced(headerTableLength() - 1);
480
481    // Table size: 233
482    assertEquals(233, hpackReader.headerTableByteCount);
483
484    // Decoded header set:
485    assertEquals(headerEntries(
486        ":method", "GET",
487        ":scheme", "http",
488        ":path", "/",
489        ":authority", "www.example.com",
490        "cache-control", "no-cache"), hpackReader.getAndReset());
491  }
492
493  private OkBuffer thirdRequestWithoutHuffman() {
494    OkBuffer out = new OkBuffer();
495
496    out.writeByte(0x80); // == Empty reference set ==
497    out.writeByte(0x85); // == Indexed - Add ==
498                         // idx = 5 -> :method: GET
499    out.writeByte(0x8c); // == Indexed - Add ==
500                         // idx = 12 -> :scheme: https
501    out.writeByte(0x8b); // == Indexed - Add ==
502                         // idx = 11 -> :path: /index.html
503    out.writeByte(0x84); // == Indexed - Add ==
504                         // idx = 4 -> :authority: www.example.com
505    out.writeByte(0x00); // Literal indexed
506    out.writeByte(0x0a); // Literal name (len = 10)
507    out.writeUtf8("custom-key");
508    out.writeByte(0x0c); // Literal value (len = 12)
509    out.writeUtf8("custom-value");
510
511    return out;
512  }
513
514  private void checkReadThirdRequestWithoutHuffman() {
515    assertEquals(8, hpackReader.headerCount);
516
517    // [  1] (s =  54) custom-key: custom-value
518    Header entry = hpackReader.headerTable[headerTableLength() - 8];
519    checkEntry(entry, "custom-key", "custom-value", 54);
520    assertHeaderReferenced(headerTableLength() - 8);
521
522    // [  2] (s =  48) :path: /index.html
523    entry = hpackReader.headerTable[headerTableLength() - 7];
524    checkEntry(entry, ":path", "/index.html", 48);
525    assertHeaderReferenced(headerTableLength() - 7);
526
527    // [  3] (s =  44) :scheme: https
528    entry = hpackReader.headerTable[headerTableLength() - 6];
529    checkEntry(entry, ":scheme", "https", 44);
530    assertHeaderReferenced(headerTableLength() - 6);
531
532    // [  4] (s =  53) cache-control: no-cache
533    entry = hpackReader.headerTable[headerTableLength() - 5];
534    checkEntry(entry, "cache-control", "no-cache", 53);
535    assertHeaderNotReferenced(headerTableLength() - 5);
536
537    // [  5] (s =  57) :authority: www.example.com
538    entry = hpackReader.headerTable[headerTableLength() - 4];
539    checkEntry(entry, ":authority", "www.example.com", 57);
540    assertHeaderReferenced(headerTableLength() - 4);
541
542    // [  6] (s =  38) :path: /
543    entry = hpackReader.headerTable[headerTableLength() - 3];
544    checkEntry(entry, ":path", "/", 38);
545    assertHeaderNotReferenced(headerTableLength() - 3);
546
547    // [  7] (s =  43) :scheme: http
548    entry = hpackReader.headerTable[headerTableLength() - 2];
549    checkEntry(entry, ":scheme", "http", 43);
550    assertHeaderNotReferenced(headerTableLength() - 2);
551
552    // [  8] (s =  42) :method: GET
553    entry = hpackReader.headerTable[headerTableLength() - 1];
554    checkEntry(entry, ":method", "GET", 42);
555    assertHeaderReferenced(headerTableLength() - 1);
556
557    // Table size: 379
558    assertEquals(379, hpackReader.headerTableByteCount);
559
560    // Decoded header set:
561    // TODO: order is not correct per docs, but then again, the spec doesn't require ordering.
562    assertEquals(headerEntries(
563        ":method", "GET",
564        ":authority", "www.example.com",
565        ":scheme", "https",
566        ":path", "/index.html",
567        "custom-key", "custom-value"), hpackReader.getAndReset());
568  }
569
570  /**
571   * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#appendix-E.3
572   */
573  @Test public void readRequestExamplesWithHuffman() throws IOException {
574    OkBuffer out = firstRequestWithHuffman();
575    bytesIn.write(out, out.size());
576    hpackReader.readHeaders();
577    hpackReader.emitReferenceSet();
578    checkReadFirstRequestWithHuffman();
579
580    out = secondRequestWithHuffman();
581    bytesIn.write(out, out.size());
582    hpackReader.readHeaders();
583    hpackReader.emitReferenceSet();
584    checkReadSecondRequestWithHuffman();
585
586    out = thirdRequestWithHuffman();
587    bytesIn.write(out, out.size());
588    hpackReader.readHeaders();
589    hpackReader.emitReferenceSet();
590    checkReadThirdRequestWithHuffman();
591  }
592
593  private OkBuffer firstRequestWithHuffman() {
594    OkBuffer out = new OkBuffer();
595
596    out.writeByte(0x82); // == Indexed - Add ==
597                         // idx = 2 -> :method: GET
598    out.writeByte(0x87); // == Indexed - Add ==
599                         // idx = 7 -> :scheme: http
600    out.writeByte(0x86); // == Indexed - Add ==
601                         // idx = 6 -> :path: /
602    out.writeByte(0x04); // == Literal indexed ==
603                         // Indexed name (idx = 4) -> :authority
604    out.writeByte(0x8b); // Literal value Huffman encoded 11 bytes
605                         // decodes to www.example.com which is length 15
606    byte[] huffmanBytes = new byte[] {
607        (byte) 0xdb, (byte) 0x6d, (byte) 0x88, (byte) 0x3e,
608        (byte) 0x68, (byte) 0xd1, (byte) 0xcb, (byte) 0x12,
609        (byte) 0x25, (byte) 0xba, (byte) 0x7f};
610    out.write(huffmanBytes, 0, huffmanBytes.length);
611
612    return out;
613  }
614
615  private void checkReadFirstRequestWithHuffman() {
616    assertEquals(4, hpackReader.headerCount);
617
618    // [  1] (s =  57) :authority: www.example.com
619    Header entry = hpackReader.headerTable[headerTableLength() - 4];
620    checkEntry(entry, ":authority", "www.example.com", 57);
621    assertHeaderReferenced(headerTableLength() - 4);
622
623    // [  2] (s =  38) :path: /
624    entry = hpackReader.headerTable[headerTableLength() - 3];
625    checkEntry(entry, ":path", "/", 38);
626    assertHeaderReferenced(headerTableLength() - 3);
627
628    // [  3] (s =  43) :scheme: http
629    entry = hpackReader.headerTable[headerTableLength() - 2];
630    checkEntry(entry, ":scheme", "http", 43);
631    assertHeaderReferenced(headerTableLength() - 2);
632
633    // [  4] (s =  42) :method: GET
634    entry = hpackReader.headerTable[headerTableLength() - 1];
635    checkEntry(entry, ":method", "GET", 42);
636    assertHeaderReferenced(headerTableLength() - 1);
637
638    // Table size: 180
639    assertEquals(180, hpackReader.headerTableByteCount);
640
641    // Decoded header set:
642    assertEquals(headerEntries(
643        ":method", "GET",
644        ":scheme", "http",
645        ":path", "/",
646        ":authority", "www.example.com"), hpackReader.getAndReset());
647  }
648
649  private OkBuffer secondRequestWithHuffman() {
650    OkBuffer out = new OkBuffer();
651
652    out.writeByte(0x1b); // == Literal indexed ==
653                         // Indexed name (idx = 27) -> cache-control
654    out.writeByte(0x86); // Literal value Huffman encoded 6 bytes
655                         // decodes to no-cache which is length 8
656    byte[] huffmanBytes = new byte[] {
657        (byte) 0x63, (byte) 0x65, (byte) 0x4a, (byte) 0x13,
658        (byte) 0x98, (byte) 0xff};
659    out.write(huffmanBytes, 0, huffmanBytes.length);
660
661    return out;
662  }
663
664  private void checkReadSecondRequestWithHuffman() {
665    assertEquals(5, hpackReader.headerCount);
666
667    // [  1] (s =  53) cache-control: no-cache
668    Header entry = hpackReader.headerTable[headerTableLength() - 5];
669    checkEntry(entry, "cache-control", "no-cache", 53);
670    assertHeaderReferenced(headerTableLength() - 5);
671
672    // [  2] (s =  57) :authority: www.example.com
673    entry = hpackReader.headerTable[headerTableLength() - 4];
674    checkEntry(entry, ":authority", "www.example.com", 57);
675    assertHeaderReferenced(headerTableLength() - 4);
676
677    // [  3] (s =  38) :path: /
678    entry = hpackReader.headerTable[headerTableLength() - 3];
679    checkEntry(entry, ":path", "/", 38);
680    assertHeaderReferenced(headerTableLength() - 3);
681
682    // [  4] (s =  43) :scheme: http
683    entry = hpackReader.headerTable[headerTableLength() - 2];
684    checkEntry(entry, ":scheme", "http", 43);
685    assertHeaderReferenced(headerTableLength() - 2);
686
687    // [  5] (s =  42) :method: GET
688    entry = hpackReader.headerTable[headerTableLength() - 1];
689    checkEntry(entry, ":method", "GET", 42);
690    assertHeaderReferenced(headerTableLength() - 1);
691
692    // Table size: 233
693    assertEquals(233, hpackReader.headerTableByteCount);
694
695    // Decoded header set:
696    assertEquals(headerEntries(
697        ":method", "GET",
698        ":scheme", "http",
699        ":path", "/",
700        ":authority", "www.example.com",
701        "cache-control", "no-cache"), hpackReader.getAndReset());
702  }
703
704  private OkBuffer thirdRequestWithHuffman() {
705    OkBuffer out = new OkBuffer();
706
707    out.writeByte(0x80); // == Empty reference set ==
708    out.writeByte(0x85); // == Indexed - Add ==
709                         // idx = 5 -> :method: GET
710    out.writeByte(0x8c); // == Indexed - Add ==
711                         // idx = 12 -> :scheme: https
712    out.writeByte(0x8b); // == Indexed - Add ==
713                         // idx = 11 -> :path: /index.html
714    out.writeByte(0x84); // == Indexed - Add ==
715                         // idx = 4 -> :authority: www.example.com
716    out.writeByte(0x00); // Literal indexed
717    out.writeByte(0x88); // Literal name Huffman encoded 8 bytes
718                         // decodes to custom-key which is length 10
719    byte[] huffmanBytes = new byte[] {
720        (byte) 0x4e, (byte) 0xb0, (byte) 0x8b, (byte) 0x74,
721        (byte) 0x97, (byte) 0x90, (byte) 0xfa, (byte) 0x7f};
722    out.write(huffmanBytes, 0, huffmanBytes.length);
723    out.writeByte(0x89); // Literal value Huffman encoded 6 bytes
724                         // decodes to custom-value which is length 12
725    huffmanBytes = new byte[] {
726        (byte) 0x4e, (byte) 0xb0, (byte) 0x8b, (byte) 0x74,
727        (byte) 0x97, (byte) 0x9a, (byte) 0x17, (byte) 0xa8,
728        (byte) 0xff};
729    out.write(huffmanBytes, 0, huffmanBytes.length);
730
731    return out;
732  }
733
734  private void checkReadThirdRequestWithHuffman() {
735    assertEquals(8, hpackReader.headerCount);
736
737    // [  1] (s =  54) custom-key: custom-value
738    Header entry = hpackReader.headerTable[headerTableLength() - 8];
739    checkEntry(entry, "custom-key", "custom-value", 54);
740    assertHeaderReferenced(headerTableLength() - 8);
741
742    // [  2] (s =  48) :path: /index.html
743    entry = hpackReader.headerTable[headerTableLength() - 7];
744    checkEntry(entry, ":path", "/index.html", 48);
745    assertHeaderReferenced(headerTableLength() - 7);
746
747    // [  3] (s =  44) :scheme: https
748    entry = hpackReader.headerTable[headerTableLength() - 6];
749    checkEntry(entry, ":scheme", "https", 44);
750    assertHeaderReferenced(headerTableLength() - 6);
751
752    // [  4] (s =  53) cache-control: no-cache
753    entry = hpackReader.headerTable[headerTableLength() - 5];
754    checkEntry(entry, "cache-control", "no-cache", 53);
755    assertHeaderNotReferenced(headerTableLength() - 5);
756
757    // [  5] (s =  57) :authority: www.example.com
758    entry = hpackReader.headerTable[headerTableLength() - 4];
759    checkEntry(entry, ":authority", "www.example.com", 57);
760    assertHeaderReferenced(headerTableLength() - 4);
761
762    // [  6] (s =  38) :path: /
763    entry = hpackReader.headerTable[headerTableLength() - 3];
764    checkEntry(entry, ":path", "/", 38);
765    assertHeaderNotReferenced(headerTableLength() - 3);
766
767    // [  7] (s =  43) :scheme: http
768    entry = hpackReader.headerTable[headerTableLength() - 2];
769    checkEntry(entry, ":scheme", "http", 43);
770    assertHeaderNotReferenced(headerTableLength() - 2);
771
772    // [  8] (s =  42) :method: GET
773    entry = hpackReader.headerTable[headerTableLength() - 1];
774    checkEntry(entry, ":method", "GET", 42);
775    assertHeaderReferenced(headerTableLength() - 1);
776
777    // Table size: 379
778    assertEquals(379, hpackReader.headerTableByteCount);
779
780    // Decoded header set:
781    // TODO: order is not correct per docs, but then again, the spec doesn't require ordering.
782    assertEquals(headerEntries(
783        ":method", "GET",
784        ":authority", "www.example.com",
785        ":scheme", "https",
786        ":path", "/index.html",
787        "custom-key", "custom-value"), hpackReader.getAndReset());
788  }
789
790  @Test public void readSingleByteInt() throws IOException {
791    assertEquals(10, newReader(byteStream()).readInt(10, 31));
792    assertEquals(10, newReader(byteStream()).readInt(0xe0 | 10, 31));
793  }
794
795  @Test public void readMultibyteInt() throws IOException {
796    assertEquals(1337, newReader(byteStream(154, 10)).readInt(31, 31));
797  }
798
799  @Test public void writeSingleByteInt() throws IOException {
800    hpackWriter.writeInt(10, 31, 0);
801    assertBytes(10);
802    hpackWriter.writeInt(10, 31, 0xe0);
803    assertBytes(0xe0 | 10);
804  }
805
806  @Test public void writeMultibyteInt() throws IOException {
807    hpackWriter.writeInt(1337, 31, 0);
808    assertBytes(31, 154, 10);
809    hpackWriter.writeInt(1337, 31, 0xe0);
810    assertBytes(0xe0 | 31, 154, 10);
811  }
812
813  @Test public void max31BitValue() throws IOException {
814    hpackWriter.writeInt(0x7fffffff, 31, 0);
815    assertBytes(31, 224, 255, 255, 255, 7);
816    assertEquals(0x7fffffff,
817        newReader(byteStream(224, 255, 255, 255, 7)).readInt(31, 31));
818  }
819
820  @Test public void prefixMask() throws IOException {
821    hpackWriter.writeInt(31, 31, 0);
822    assertBytes(31, 0);
823    assertEquals(31, newReader(byteStream(0)).readInt(31, 31));
824  }
825
826  @Test public void prefixMaskMinusOne() throws IOException {
827    hpackWriter.writeInt(30, 31, 0);
828    assertBytes(30);
829    assertEquals(31, newReader(byteStream(0)).readInt(31, 31));
830  }
831
832  @Test public void zero() throws IOException {
833    hpackWriter.writeInt(0, 31, 0);
834    assertBytes(0);
835    assertEquals(0, newReader(byteStream()).readInt(0, 31));
836  }
837
838  @Test public void headerName() throws IOException {
839    hpackWriter.writeByteString(ByteString.encodeUtf8("foo"));
840    assertBytes(3, 'f', 'o', 'o');
841    assertEquals("foo", newReader(byteStream(3, 'F', 'o', 'o')).readByteString(true).utf8());
842  }
843
844  @Test public void emptyHeaderName() throws IOException {
845    hpackWriter.writeByteString(ByteString.encodeUtf8(""));
846    assertBytes(0);
847    assertEquals(ByteString.EMPTY, newReader(byteStream(0)).readByteString(true));
848    assertEquals(ByteString.EMPTY, newReader(byteStream(0)).readByteString(false));
849  }
850
851  private HpackDraft05.Reader newReader(OkBuffer source) {
852    return new HpackDraft05.Reader(false, 4096, source);
853  }
854
855  private OkBuffer byteStream(int... bytes) {
856    return new OkBuffer().write(intArrayToByteArray(bytes));
857  }
858
859  private void checkEntry(Header entry, String name, String value, int size) {
860    assertEquals(name, entry.name.utf8());
861    assertEquals(value, entry.value.utf8());
862    assertEquals(size, entry.hpackSize);
863  }
864
865  private void assertBytes(int... bytes) {
866    ByteString expected = intArrayToByteArray(bytes);
867    ByteString actual = bytesOut.readByteString(bytesOut.size());
868    assertEquals(expected, actual);
869  }
870
871  private ByteString intArrayToByteArray(int[] bytes) {
872    byte[] data = new byte[bytes.length];
873    for (int i = 0; i < bytes.length; i++) {
874      data[i] = (byte) bytes[i];
875    }
876    return ByteString.of(data);
877  }
878
879  private void assertHeaderReferenced(int index) {
880    assertTrue(hpackReader.referencedHeaders.get(index));
881  }
882
883  private void assertHeaderNotReferenced(int index) {
884    assertFalse(hpackReader.referencedHeaders.get(index));
885  }
886
887  private int headerTableLength() {
888    return hpackReader.headerTable.length;
889  }
890}
891