1package com.squareup.okhttp.internal.spdy;
2
3import com.squareup.okhttp.internal.BitArray;
4import java.io.IOException;
5import java.util.ArrayList;
6import java.util.Arrays;
7import java.util.Collections;
8import java.util.LinkedHashMap;
9import java.util.List;
10import java.util.Map;
11import okio.BufferedSource;
12import okio.ByteString;
13import okio.OkBuffer;
14import okio.Okio;
15import okio.Source;
16
17/**
18 * Read and write HPACK v05.
19 *
20 * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05
21 *
22 * This implementation uses an array for the header table with a bitset for
23 * references.  Dynamic entries are added to the array, starting in the last
24 * position moving forward.  When the array fills, it is doubled.
25 */
26final class HpackDraft05 {
27  private static final int PREFIX_6_BITS = 0x3f;
28  private static final int PREFIX_7_BITS = 0x7f;
29
30  private static final Header[] STATIC_HEADER_TABLE = new Header[] {
31      new Header(Header.TARGET_AUTHORITY, ""),
32      new Header(Header.TARGET_METHOD, "GET"),
33      new Header(Header.TARGET_METHOD, "POST"),
34      new Header(Header.TARGET_PATH, "/"),
35      new Header(Header.TARGET_PATH, "/index.html"),
36      new Header(Header.TARGET_SCHEME, "http"),
37      new Header(Header.TARGET_SCHEME, "https"),
38      new Header(Header.RESPONSE_STATUS, "200"),
39      new Header(Header.RESPONSE_STATUS, "500"),
40      new Header(Header.RESPONSE_STATUS, "404"),
41      new Header(Header.RESPONSE_STATUS, "403"),
42      new Header(Header.RESPONSE_STATUS, "400"),
43      new Header(Header.RESPONSE_STATUS, "401"),
44      new Header("accept-charset", ""),
45      new Header("accept-encoding", ""),
46      new Header("accept-language", ""),
47      new Header("accept-ranges", ""),
48      new Header("accept", ""),
49      new Header("access-control-allow-origin", ""),
50      new Header("age", ""),
51      new Header("allow", ""),
52      new Header("authorization", ""),
53      new Header("cache-control", ""),
54      new Header("content-disposition", ""),
55      new Header("content-encoding", ""),
56      new Header("content-language", ""),
57      new Header("content-length", ""),
58      new Header("content-location", ""),
59      new Header("content-range", ""),
60      new Header("content-type", ""),
61      new Header("cookie", ""),
62      new Header("date", ""),
63      new Header("etag", ""),
64      new Header("expect", ""),
65      new Header("expires", ""),
66      new Header("from", ""),
67      new Header("host", ""),
68      new Header("if-match", ""),
69      new Header("if-modified-since", ""),
70      new Header("if-none-match", ""),
71      new Header("if-range", ""),
72      new Header("if-unmodified-since", ""),
73      new Header("last-modified", ""),
74      new Header("link", ""),
75      new Header("location", ""),
76      new Header("max-forwards", ""),
77      new Header("proxy-authenticate", ""),
78      new Header("proxy-authorization", ""),
79      new Header("range", ""),
80      new Header("referer", ""),
81      new Header("refresh", ""),
82      new Header("retry-after", ""),
83      new Header("server", ""),
84      new Header("set-cookie", ""),
85      new Header("strict-transport-security", ""),
86      new Header("transfer-encoding", ""),
87      new Header("user-agent", ""),
88      new Header("vary", ""),
89      new Header("via", ""),
90      new Header("www-authenticate", "")
91  };
92
93  private HpackDraft05() {
94  }
95
96  // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-4.1.2
97  static final class Reader {
98    private final Huffman.Codec huffmanCodec;
99
100    private final List<Header> emittedHeaders = new ArrayList<Header>();
101    private final BufferedSource source;
102    private int maxHeaderTableByteCount;
103
104    // Visible for testing.
105    Header[] headerTable = new Header[8];
106    // Array is populated back to front, so new entries always have lowest index.
107    int nextHeaderIndex = headerTable.length - 1;
108    int headerCount = 0;
109
110    /**
111     * Set bit positions indicate {@code headerTable[pos]} should be emitted.
112     */
113    // Using a BitArray as it has left-shift operator.
114    BitArray referencedHeaders = new BitArray.FixedCapacity();
115
116    /**
117     * Set bit positions indicate {@code headerTable[pos]} was already emitted.
118     */
119    BitArray emittedReferencedHeaders = new BitArray.FixedCapacity();
120    int headerTableByteCount = 0;
121
122    Reader(boolean client, int maxHeaderTableByteCount, Source source) {
123      this.huffmanCodec = client ? Huffman.Codec.RESPONSE : Huffman.Codec.REQUEST;
124      this.maxHeaderTableByteCount = maxHeaderTableByteCount;
125      this.source = Okio.buffer(source);
126    }
127
128    int maxHeaderTableByteCount() {
129      return maxHeaderTableByteCount;
130    }
131
132    /**
133     * Called by the reader when the peer sent a new header table size setting.
134     * <p>
135     * Evicts entries or clears the table as needed.
136     */
137    void maxHeaderTableByteCount(int newMaxHeaderTableByteCount) {
138      this.maxHeaderTableByteCount = newMaxHeaderTableByteCount;
139      if (maxHeaderTableByteCount < headerTableByteCount) {
140        if (maxHeaderTableByteCount == 0) {
141          clearHeaderTable();
142        } else {
143          evictToRecoverBytes(headerTableByteCount - maxHeaderTableByteCount);
144        }
145      }
146    }
147
148    private void clearHeaderTable() {
149      clearReferenceSet();
150      Arrays.fill(headerTable, null);
151      nextHeaderIndex = headerTable.length - 1;
152      headerCount = 0;
153      headerTableByteCount = 0;
154    }
155
156    /** Returns the count of entries evicted. */
157    private int evictToRecoverBytes(int bytesToRecover) {
158      int entriesToEvict = 0;
159      if (bytesToRecover > 0) {
160        // determine how many headers need to be evicted.
161        for (int j = headerTable.length - 1; j >= nextHeaderIndex && bytesToRecover > 0; j--) {
162          bytesToRecover -= headerTable[j].hpackSize;
163          headerTableByteCount -= headerTable[j].hpackSize;
164          headerCount--;
165          entriesToEvict++;
166        }
167        referencedHeaders.shiftLeft(entriesToEvict);
168        emittedReferencedHeaders.shiftLeft(entriesToEvict);
169        System.arraycopy(headerTable, nextHeaderIndex + 1, headerTable,
170            nextHeaderIndex + 1 + entriesToEvict, headerCount);
171        nextHeaderIndex += entriesToEvict;
172      }
173      return entriesToEvict;
174    }
175
176    /**
177     * Read {@code byteCount} bytes of headers from the source stream into the
178     * set of emitted headers.
179     */
180    void readHeaders() throws IOException {
181      while (!source.exhausted()) {
182        int b = source.readByte() & 0xff;
183        if (b == 0x80) { // 10000000
184          clearReferenceSet();
185        } else if ((b & 0x80) == 0x80) { // 1NNNNNNN
186          int index = readInt(b, PREFIX_7_BITS);
187          readIndexedHeader(index - 1);
188        } else { // 0NNNNNNN
189          if (b == 0x40) { // 01000000
190            readLiteralHeaderWithoutIndexingNewName();
191          } else if ((b & 0x40) == 0x40) {  // 01NNNNNN
192            int index = readInt(b, PREFIX_6_BITS);
193            readLiteralHeaderWithoutIndexingIndexedName(index - 1);
194          } else if (b == 0) { // 00000000
195            readLiteralHeaderWithIncrementalIndexingNewName();
196          } else if ((b & 0xc0) == 0) { // 00NNNNNN
197            int index = readInt(b, PREFIX_6_BITS);
198            readLiteralHeaderWithIncrementalIndexingIndexedName(index - 1);
199          } else {
200            // TODO: we should throw something that we can coerce to a PROTOCOL_ERROR
201            throw new AssertionError("unhandled byte: " + Integer.toBinaryString(b));
202          }
203        }
204      }
205    }
206
207    private void clearReferenceSet() {
208      referencedHeaders.clear();
209      emittedReferencedHeaders.clear();
210    }
211
212    void emitReferenceSet() {
213      for (int i = headerTable.length - 1; i != nextHeaderIndex; --i) {
214        if (referencedHeaders.get(i) && !emittedReferencedHeaders.get(i)) {
215          emittedHeaders.add(headerTable[i]);
216        }
217      }
218    }
219
220    /**
221     * Returns all headers emitted since they were last cleared, then clears the
222     * emitted headers.
223     */
224    List<Header> getAndReset() {
225      List<Header> result = new ArrayList<Header>(emittedHeaders);
226      emittedHeaders.clear();
227      emittedReferencedHeaders.clear();
228      return result;
229    }
230
231    private void readIndexedHeader(int index) {
232      if (isStaticHeader(index)) {
233        Header staticEntry = STATIC_HEADER_TABLE[index - headerCount];
234        if (maxHeaderTableByteCount == 0) {
235          emittedHeaders.add(staticEntry);
236        } else {
237          insertIntoHeaderTable(-1, staticEntry);
238        }
239      } else {
240        int headerTableIndex = headerTableIndex(index);
241        if (!referencedHeaders.get(headerTableIndex)) { // When re-referencing, emit immediately.
242          emittedHeaders.add(headerTable[headerTableIndex]);
243          emittedReferencedHeaders.set(headerTableIndex);
244        }
245        referencedHeaders.toggle(headerTableIndex);
246      }
247    }
248
249    // referencedHeaders is relative to nextHeaderIndex + 1.
250    private int headerTableIndex(int index) {
251      return nextHeaderIndex + 1 + index;
252    }
253
254    private void readLiteralHeaderWithoutIndexingIndexedName(int index) throws IOException {
255      ByteString name = getName(index);
256      ByteString value = readByteString(false);
257      emittedHeaders.add(new Header(name, value));
258    }
259
260    private void readLiteralHeaderWithoutIndexingNewName() throws IOException {
261      ByteString name = readByteString(true);
262      ByteString value = readByteString(false);
263      emittedHeaders.add(new Header(name, value));
264    }
265
266    private void readLiteralHeaderWithIncrementalIndexingIndexedName(int nameIndex)
267        throws IOException {
268      ByteString name = getName(nameIndex);
269      ByteString value = readByteString(false);
270      insertIntoHeaderTable(-1, new Header(name, value));
271    }
272
273    private void readLiteralHeaderWithIncrementalIndexingNewName() throws IOException {
274      ByteString name = readByteString(true);
275      ByteString value = readByteString(false);
276      insertIntoHeaderTable(-1, new Header(name, value));
277    }
278
279    private ByteString getName(int index) {
280      if (isStaticHeader(index)) {
281        return STATIC_HEADER_TABLE[index - headerCount].name;
282      } else {
283        return headerTable[headerTableIndex(index)].name;
284      }
285    }
286
287    private boolean isStaticHeader(int index) {
288      return index >= headerCount;
289    }
290
291    /** index == -1 when new. */
292    private void insertIntoHeaderTable(int index, Header entry) {
293      int delta = entry.hpackSize;
294      if (index != -1) { // Index -1 == new header.
295        delta -= headerTable[headerTableIndex(index)].hpackSize;
296      }
297
298      // if the new or replacement header is too big, drop all entries.
299      if (delta > maxHeaderTableByteCount) {
300        clearHeaderTable();
301        // emit the large header to the callback.
302        emittedHeaders.add(entry);
303        return;
304      }
305
306      // Evict headers to the required length.
307      int bytesToRecover = (headerTableByteCount + delta) - maxHeaderTableByteCount;
308      int entriesEvicted = evictToRecoverBytes(bytesToRecover);
309
310      if (index == -1) { // Adding a value to the header table.
311        if (headerCount + 1 > headerTable.length) { // Need to grow the header table.
312          Header[] doubled = new Header[headerTable.length * 2];
313          System.arraycopy(headerTable, 0, doubled, headerTable.length, headerTable.length);
314          if (doubled.length == 64) {
315            referencedHeaders = ((BitArray.FixedCapacity) referencedHeaders).toVariableCapacity();
316            emittedReferencedHeaders =
317                ((BitArray.FixedCapacity) emittedReferencedHeaders).toVariableCapacity();
318          }
319          referencedHeaders.shiftLeft(headerTable.length);
320          emittedReferencedHeaders.shiftLeft(headerTable.length);
321          nextHeaderIndex = headerTable.length - 1;
322          headerTable = doubled;
323        }
324        index = nextHeaderIndex--;
325        referencedHeaders.set(index);
326        headerTable[index] = entry;
327        headerCount++;
328      } else { // Replace value at same position.
329        index += headerTableIndex(index) + entriesEvicted;
330        referencedHeaders.set(index);
331        headerTable[index] = entry;
332      }
333      headerTableByteCount += delta;
334    }
335
336    private int readByte() throws IOException {
337      return source.readByte() & 0xff;
338    }
339
340    int readInt(int firstByte, int prefixMask) throws IOException {
341      int prefix = firstByte & prefixMask;
342      if (prefix < prefixMask) {
343        return prefix; // This was a single byte value.
344      }
345
346      // This is a multibyte value. Read 7 bits at a time.
347      int result = prefixMask;
348      int shift = 0;
349      while (true) {
350        int b = readByte();
351        if ((b & 0x80) != 0) { // Equivalent to (b >= 128) since b is in [0..255].
352          result += (b & 0x7f) << shift;
353          shift += 7;
354        } else {
355          result += b << shift; // Last byte.
356          break;
357        }
358      }
359      return result;
360    }
361
362    /**
363     * Reads a potentially Huffman encoded string byte string. When
364     * {@code asciiLowercase} is true, bytes will be converted to lowercase.
365     */
366    ByteString readByteString(boolean asciiLowercase) throws IOException {
367      int firstByte = readByte();
368      boolean huffmanDecode = (firstByte & 0x80) == 0x80; // 1NNNNNNN
369      int length = readInt(firstByte, PREFIX_7_BITS);
370
371      ByteString byteString = source.readByteString(length);
372
373      if (huffmanDecode) {
374        byteString = huffmanCodec.decode(byteString); // TODO: streaming Huffman!
375      }
376
377      if (asciiLowercase) {
378        byteString = byteString.toAsciiLowercase();
379      }
380
381      return byteString;
382    }
383  }
384
385  private static final Map<ByteString, Integer> NAME_TO_FIRST_INDEX = nameToFirstIndex();
386
387  private static Map<ByteString, Integer> nameToFirstIndex() {
388    Map<ByteString, Integer> result =
389        new LinkedHashMap<ByteString, Integer>(STATIC_HEADER_TABLE.length);
390    for (int i = 0; i < STATIC_HEADER_TABLE.length; i++) {
391      if (!result.containsKey(STATIC_HEADER_TABLE[i].name)) {
392        result.put(STATIC_HEADER_TABLE[i].name, i);
393      }
394    }
395    return Collections.unmodifiableMap(result);
396  }
397
398  static final class Writer {
399    private final OkBuffer out;
400
401    Writer(OkBuffer out) {
402      this.out = out;
403    }
404
405    void writeHeaders(List<Header> headerBlock) throws IOException {
406      // TODO: implement index tracking
407      for (int i = 0, size = headerBlock.size(); i < size; i++) {
408        ByteString name = headerBlock.get(i).name;
409        Integer staticIndex = NAME_TO_FIRST_INDEX.get(name);
410        if (staticIndex != null) {
411          // Literal Header Field without Indexing - Indexed Name.
412          writeInt(staticIndex + 1, PREFIX_6_BITS, 0x40);
413          writeByteString(headerBlock.get(i).value);
414        } else {
415          out.writeByte(0x40); // Literal Header without Indexing - New Name.
416          writeByteString(name);
417          writeByteString(headerBlock.get(i).value);
418        }
419      }
420    }
421
422    // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-05#section-4.1.1
423    void writeInt(int value, int prefixMask, int bits) throws IOException {
424      // Write the raw value for a single byte value.
425      if (value < prefixMask) {
426        out.writeByte(bits | value);
427        return;
428      }
429
430      // Write the mask to start a multibyte value.
431      out.writeByte(bits | prefixMask);
432      value -= prefixMask;
433
434      // Write 7 bits at a time 'til we're done.
435      while (value >= 0x80) {
436        int b = value & 0x7f;
437        out.writeByte(b | 0x80);
438        value >>>= 7;
439      }
440      out.writeByte(value);
441    }
442
443    void writeByteString(ByteString data) throws IOException {
444      writeInt(data.size(), PREFIX_7_BITS, 0);
445      out.write(data);
446    }
447  }
448}
449