Author: remm Date: Fri Mar 20 18:47:03 2015 New Revision: 1668116 URL: http://svn.apache.org/r1668116 Log: 57732: Add encoder/decoder module to support the HPACK specification ( http://http2.github.io/http2-spec/compression.html ). Code contributed by Stuart Douglas, with some adaptations to Tomcat.
Added: tomcat/trunk/java/org/apache/coyote/http2/ tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java (with props) tomcat/trunk/java/org/apache/coyote/http2/Hpack.java (with props) tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java (with props) tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java (with props) tomcat/trunk/java/org/apache/coyote/http2/HpackException.java (with props) tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties (with props) tomcat/trunk/test/org/apache/coyote/http2/ tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java (with props) Modified: tomcat/trunk/webapps/docs/changelog.xml Added: tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java (added) +++ tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java Fri Mar 20 18:47:03 2015 @@ -0,0 +1,561 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.coyote.http2; + +import java.nio.ByteBuffer; +import java.util.Arrays; +import java.util.HashSet; +import java.util.Set; + +import org.apache.tomcat.util.res.StringManager; + +public class HPackHuffman { + + protected static final StringManager sm = StringManager.getManager(HPackHuffman.class); + + private static final HuffmanCode[] HUFFMAN_CODES; + + /** + * array based tree representation of a huffman code. + * <p/> + * the high two bytes corresponds to the tree node if the bit is set, and the low two bytes for if it is clear + * if the high bit is set it is a terminal node, otherwise it contains the next node position. + */ + private static final int[] DECODING_TABLE; + + private static final int LOW_TERMINAL_BIT = (0b10000000) << 8; + private static final int HIGH_TERMINAL_BIT = (0b10000000) << 24; + private static final int LOW_MASK = 0b0111111111111111; + + + static { + + HuffmanCode[] codes = new HuffmanCode[257]; + + codes[0] = new HuffmanCode(0x1ff8, 13); + codes[1] = new HuffmanCode(0x7fffd8, 23); + codes[2] = new HuffmanCode(0xfffffe2, 28); + codes[3] = new HuffmanCode(0xfffffe3, 28); + codes[4] = new HuffmanCode(0xfffffe4, 28); + codes[5] = new HuffmanCode(0xfffffe5, 28); + codes[6] = new HuffmanCode(0xfffffe6, 28); + codes[7] = new HuffmanCode(0xfffffe7, 28); + codes[8] = new HuffmanCode(0xfffffe8, 28); + codes[9] = new HuffmanCode(0xffffea, 24); + codes[10] = new HuffmanCode(0x3ffffffc, 30); + codes[11] = new HuffmanCode(0xfffffe9, 28); + codes[12] = new HuffmanCode(0xfffffea, 28); + codes[13] = new HuffmanCode(0x3ffffffd, 30); + codes[14] = new HuffmanCode(0xfffffeb, 28); + codes[15] = new HuffmanCode(0xfffffec, 28); + codes[16] = new HuffmanCode(0xfffffed, 28); + codes[17] = new HuffmanCode(0xfffffee, 28); + codes[18] = new HuffmanCode(0xfffffef, 28); + codes[19] = new HuffmanCode(0xffffff0, 28); + codes[20] = new HuffmanCode(0xffffff1, 28); + codes[21] = new HuffmanCode(0xffffff2, 28); + codes[22] = new HuffmanCode(0x3ffffffe, 30); + codes[23] = new HuffmanCode(0xffffff3, 28); + codes[24] = new HuffmanCode(0xffffff4, 28); + codes[25] = new HuffmanCode(0xffffff5, 28); + codes[26] = new HuffmanCode(0xffffff6, 28); + codes[27] = new HuffmanCode(0xffffff7, 28); + codes[28] = new HuffmanCode(0xffffff8, 28); + codes[29] = new HuffmanCode(0xffffff9, 28); + codes[30] = new HuffmanCode(0xffffffa, 28); + codes[31] = new HuffmanCode(0xffffffb, 28); + codes[32] = new HuffmanCode(0x14, 6); + codes[33] = new HuffmanCode(0x3f8, 10); + codes[34] = new HuffmanCode(0x3f9, 10); + codes[35] = new HuffmanCode(0xffa, 12); + codes[36] = new HuffmanCode(0x1ff9, 13); + codes[37] = new HuffmanCode(0x15, 6); + codes[38] = new HuffmanCode(0xf8, 8); + codes[39] = new HuffmanCode(0x7fa, 11); + codes[40] = new HuffmanCode(0x3fa, 10); + codes[41] = new HuffmanCode(0x3fb, 10); + codes[42] = new HuffmanCode(0xf9, 8); + codes[43] = new HuffmanCode(0x7fb, 11); + codes[44] = new HuffmanCode(0xfa, 8); + codes[45] = new HuffmanCode(0x16, 6); + codes[46] = new HuffmanCode(0x17, 6); + codes[47] = new HuffmanCode(0x18, 6); + codes[48] = new HuffmanCode(0x0, 5); + codes[49] = new HuffmanCode(0x1, 5); + codes[50] = new HuffmanCode(0x2, 5); + codes[51] = new HuffmanCode(0x19, 6); + codes[52] = new HuffmanCode(0x1a, 6); + codes[53] = new HuffmanCode(0x1b, 6); + codes[54] = new HuffmanCode(0x1c, 6); + codes[55] = new HuffmanCode(0x1d, 6); + codes[56] = new HuffmanCode(0x1e, 6); + codes[57] = new HuffmanCode(0x1f, 6); + codes[58] = new HuffmanCode(0x5c, 7); + codes[59] = new HuffmanCode(0xfb, 8); + codes[60] = new HuffmanCode(0x7ffc, 15); + codes[61] = new HuffmanCode(0x20, 6); + codes[62] = new HuffmanCode(0xffb, 12); + codes[63] = new HuffmanCode(0x3fc, 10); + codes[64] = new HuffmanCode(0x1ffa, 13); + codes[65] = new HuffmanCode(0x21, 6); + codes[66] = new HuffmanCode(0x5d, 7); + codes[67] = new HuffmanCode(0x5e, 7); + codes[68] = new HuffmanCode(0x5f, 7); + codes[69] = new HuffmanCode(0x60, 7); + codes[70] = new HuffmanCode(0x61, 7); + codes[71] = new HuffmanCode(0x62, 7); + codes[72] = new HuffmanCode(0x63, 7); + codes[73] = new HuffmanCode(0x64, 7); + codes[74] = new HuffmanCode(0x65, 7); + codes[75] = new HuffmanCode(0x66, 7); + codes[76] = new HuffmanCode(0x67, 7); + codes[77] = new HuffmanCode(0x68, 7); + codes[78] = new HuffmanCode(0x69, 7); + codes[79] = new HuffmanCode(0x6a, 7); + codes[80] = new HuffmanCode(0x6b, 7); + codes[81] = new HuffmanCode(0x6c, 7); + codes[82] = new HuffmanCode(0x6d, 7); + codes[83] = new HuffmanCode(0x6e, 7); + codes[84] = new HuffmanCode(0x6f, 7); + codes[85] = new HuffmanCode(0x70, 7); + codes[86] = new HuffmanCode(0x71, 7); + codes[87] = new HuffmanCode(0x72, 7); + codes[88] = new HuffmanCode(0xfc, 8); + codes[89] = new HuffmanCode(0x73, 7); + codes[90] = new HuffmanCode(0xfd, 8); + codes[91] = new HuffmanCode(0x1ffb, 13); + codes[92] = new HuffmanCode(0x7fff0, 19); + codes[93] = new HuffmanCode(0x1ffc, 13); + codes[94] = new HuffmanCode(0x3ffc, 14); + codes[95] = new HuffmanCode(0x22, 6); + codes[96] = new HuffmanCode(0x7ffd, 15); + codes[97] = new HuffmanCode(0x3, 5); + codes[98] = new HuffmanCode(0x23, 6); + codes[99] = new HuffmanCode(0x4, 5); + codes[100] = new HuffmanCode(0x24, 6); + codes[101] = new HuffmanCode(0x5, 5); + codes[102] = new HuffmanCode(0x25, 6); + codes[103] = new HuffmanCode(0x26, 6); + codes[104] = new HuffmanCode(0x27, 6); + codes[105] = new HuffmanCode(0x6, 5); + codes[106] = new HuffmanCode(0x74, 7); + codes[107] = new HuffmanCode(0x75, 7); + codes[108] = new HuffmanCode(0x28, 6); + codes[109] = new HuffmanCode(0x29, 6); + codes[110] = new HuffmanCode(0x2a, 6); + codes[111] = new HuffmanCode(0x7, 5); + codes[112] = new HuffmanCode(0x2b, 6); + codes[113] = new HuffmanCode(0x76, 7); + codes[114] = new HuffmanCode(0x2c, 6); + codes[115] = new HuffmanCode(0x8, 5); + codes[116] = new HuffmanCode(0x9, 5); + codes[117] = new HuffmanCode(0x2d, 6); + codes[118] = new HuffmanCode(0x77, 7); + codes[119] = new HuffmanCode(0x78, 7); + codes[120] = new HuffmanCode(0x79, 7); + codes[121] = new HuffmanCode(0x7a, 7); + codes[122] = new HuffmanCode(0x7b, 7); + codes[123] = new HuffmanCode(0x7ffe, 15); + codes[124] = new HuffmanCode(0x7fc, 11); + codes[125] = new HuffmanCode(0x3ffd, 14); + codes[126] = new HuffmanCode(0x1ffd, 13); + codes[127] = new HuffmanCode(0xffffffc, 28); + codes[128] = new HuffmanCode(0xfffe6, 20); + codes[129] = new HuffmanCode(0x3fffd2, 22); + codes[130] = new HuffmanCode(0xfffe7, 20); + codes[131] = new HuffmanCode(0xfffe8, 20); + codes[132] = new HuffmanCode(0x3fffd3, 22); + codes[133] = new HuffmanCode(0x3fffd4, 22); + codes[134] = new HuffmanCode(0x3fffd5, 22); + codes[135] = new HuffmanCode(0x7fffd9, 23); + codes[136] = new HuffmanCode(0x3fffd6, 22); + codes[137] = new HuffmanCode(0x7fffda, 23); + codes[138] = new HuffmanCode(0x7fffdb, 23); + codes[139] = new HuffmanCode(0x7fffdc, 23); + codes[140] = new HuffmanCode(0x7fffdd, 23); + codes[141] = new HuffmanCode(0x7fffde, 23); + codes[142] = new HuffmanCode(0xffffeb, 24); + codes[143] = new HuffmanCode(0x7fffdf, 23); + codes[144] = new HuffmanCode(0xffffec, 24); + codes[145] = new HuffmanCode(0xffffed, 24); + codes[146] = new HuffmanCode(0x3fffd7, 22); + codes[147] = new HuffmanCode(0x7fffe0, 23); + codes[148] = new HuffmanCode(0xffffee, 24); + codes[149] = new HuffmanCode(0x7fffe1, 23); + codes[150] = new HuffmanCode(0x7fffe2, 23); + codes[151] = new HuffmanCode(0x7fffe3, 23); + codes[152] = new HuffmanCode(0x7fffe4, 23); + codes[153] = new HuffmanCode(0x1fffdc, 21); + codes[154] = new HuffmanCode(0x3fffd8, 22); + codes[155] = new HuffmanCode(0x7fffe5, 23); + codes[156] = new HuffmanCode(0x3fffd9, 22); + codes[157] = new HuffmanCode(0x7fffe6, 23); + codes[158] = new HuffmanCode(0x7fffe7, 23); + codes[159] = new HuffmanCode(0xffffef, 24); + codes[160] = new HuffmanCode(0x3fffda, 22); + codes[161] = new HuffmanCode(0x1fffdd, 21); + codes[162] = new HuffmanCode(0xfffe9, 20); + codes[163] = new HuffmanCode(0x3fffdb, 22); + codes[164] = new HuffmanCode(0x3fffdc, 22); + codes[165] = new HuffmanCode(0x7fffe8, 23); + codes[166] = new HuffmanCode(0x7fffe9, 23); + codes[167] = new HuffmanCode(0x1fffde, 21); + codes[168] = new HuffmanCode(0x7fffea, 23); + codes[169] = new HuffmanCode(0x3fffdd, 22); + codes[170] = new HuffmanCode(0x3fffde, 22); + codes[171] = new HuffmanCode(0xfffff0, 24); + codes[172] = new HuffmanCode(0x1fffdf, 21); + codes[173] = new HuffmanCode(0x3fffdf, 22); + codes[174] = new HuffmanCode(0x7fffeb, 23); + codes[175] = new HuffmanCode(0x7fffec, 23); + codes[176] = new HuffmanCode(0x1fffe0, 21); + codes[177] = new HuffmanCode(0x1fffe1, 21); + codes[178] = new HuffmanCode(0x3fffe0, 22); + codes[179] = new HuffmanCode(0x1fffe2, 21); + codes[180] = new HuffmanCode(0x7fffed, 23); + codes[181] = new HuffmanCode(0x3fffe1, 22); + codes[182] = new HuffmanCode(0x7fffee, 23); + codes[183] = new HuffmanCode(0x7fffef, 23); + codes[184] = new HuffmanCode(0xfffea, 20); + codes[185] = new HuffmanCode(0x3fffe2, 22); + codes[186] = new HuffmanCode(0x3fffe3, 22); + codes[187] = new HuffmanCode(0x3fffe4, 22); + codes[188] = new HuffmanCode(0x7ffff0, 23); + codes[189] = new HuffmanCode(0x3fffe5, 22); + codes[190] = new HuffmanCode(0x3fffe6, 22); + codes[191] = new HuffmanCode(0x7ffff1, 23); + codes[192] = new HuffmanCode(0x3ffffe0, 26); + codes[193] = new HuffmanCode(0x3ffffe1, 26); + codes[194] = new HuffmanCode(0xfffeb, 20); + codes[195] = new HuffmanCode(0x7fff1, 19); + codes[196] = new HuffmanCode(0x3fffe7, 22); + codes[197] = new HuffmanCode(0x7ffff2, 23); + codes[198] = new HuffmanCode(0x3fffe8, 22); + codes[199] = new HuffmanCode(0x1ffffec, 25); + codes[200] = new HuffmanCode(0x3ffffe2, 26); + codes[201] = new HuffmanCode(0x3ffffe3, 26); + codes[202] = new HuffmanCode(0x3ffffe4, 26); + codes[203] = new HuffmanCode(0x7ffffde, 27); + codes[204] = new HuffmanCode(0x7ffffdf, 27); + codes[205] = new HuffmanCode(0x3ffffe5, 26); + codes[206] = new HuffmanCode(0xfffff1, 24); + codes[207] = new HuffmanCode(0x1ffffed, 25); + codes[208] = new HuffmanCode(0x7fff2, 19); + codes[209] = new HuffmanCode(0x1fffe3, 21); + codes[210] = new HuffmanCode(0x3ffffe6, 26); + codes[211] = new HuffmanCode(0x7ffffe0, 27); + codes[212] = new HuffmanCode(0x7ffffe1, 27); + codes[213] = new HuffmanCode(0x3ffffe7, 26); + codes[214] = new HuffmanCode(0x7ffffe2, 27); + codes[215] = new HuffmanCode(0xfffff2, 24); + codes[216] = new HuffmanCode(0x1fffe4, 21); + codes[217] = new HuffmanCode(0x1fffe5, 21); + codes[218] = new HuffmanCode(0x3ffffe8, 26); + codes[219] = new HuffmanCode(0x3ffffe9, 26); + codes[220] = new HuffmanCode(0xffffffd, 28); + codes[221] = new HuffmanCode(0x7ffffe3, 27); + codes[222] = new HuffmanCode(0x7ffffe4, 27); + codes[223] = new HuffmanCode(0x7ffffe5, 27); + codes[224] = new HuffmanCode(0xfffec, 20); + codes[225] = new HuffmanCode(0xfffff3, 24); + codes[226] = new HuffmanCode(0xfffed, 20); + codes[227] = new HuffmanCode(0x1fffe6, 21); + codes[228] = new HuffmanCode(0x3fffe9, 22); + codes[229] = new HuffmanCode(0x1fffe7, 21); + codes[230] = new HuffmanCode(0x1fffe8, 21); + codes[231] = new HuffmanCode(0x7ffff3, 23); + codes[232] = new HuffmanCode(0x3fffea, 22); + codes[233] = new HuffmanCode(0x3fffeb, 22); + codes[234] = new HuffmanCode(0x1ffffee, 25); + codes[235] = new HuffmanCode(0x1ffffef, 25); + codes[236] = new HuffmanCode(0xfffff4, 24); + codes[237] = new HuffmanCode(0xfffff5, 24); + codes[238] = new HuffmanCode(0x3ffffea, 26); + codes[239] = new HuffmanCode(0x7ffff4, 23); + codes[240] = new HuffmanCode(0x3ffffeb, 26); + codes[241] = new HuffmanCode(0x7ffffe6, 27); + codes[242] = new HuffmanCode(0x3ffffec, 26); + codes[243] = new HuffmanCode(0x3ffffed, 26); + codes[244] = new HuffmanCode(0x7ffffe7, 27); + codes[245] = new HuffmanCode(0x7ffffe8, 27); + codes[246] = new HuffmanCode(0x7ffffe9, 27); + codes[247] = new HuffmanCode(0x7ffffea, 27); + codes[248] = new HuffmanCode(0x7ffffeb, 27); + codes[249] = new HuffmanCode(0xffffffe, 28); + codes[250] = new HuffmanCode(0x7ffffec, 27); + codes[251] = new HuffmanCode(0x7ffffed, 27); + codes[252] = new HuffmanCode(0x7ffffee, 27); + codes[253] = new HuffmanCode(0x7ffffef, 27); + codes[254] = new HuffmanCode(0x7fffff0, 27); + codes[255] = new HuffmanCode(0x3ffffee, 26); + codes[256] = new HuffmanCode(0x3fffffff, 30); + HUFFMAN_CODES = codes; + + //lengths determined by experimentation, just set it to something large then see how large it actually ends up + int[] codingTree = new int[256]; + //the current position in the tree + int pos = 0; + int allocated = 1; //the next position to allocate to + //map of the current state at a given position + //only used while building the tree + HuffmanCode[] currentCode = new HuffmanCode[256]; + currentCode[0] = new HuffmanCode(0, 0); + + final Set<HuffmanCode> allCodes = new HashSet<>(); + allCodes.addAll(Arrays.asList(HUFFMAN_CODES)); + + while (!allCodes.isEmpty()) { + int length = currentCode[pos].length; + int code = currentCode[pos].value; + + int newLength = length + 1; + HuffmanCode high = new HuffmanCode(code << 1 | 1, newLength); + HuffmanCode low = new HuffmanCode(code << 1, newLength); + int newVal = 0; + boolean highTerminal = allCodes.remove(high); + if (highTerminal) { + //bah, linear search + int i = 0; + for (i = 0; i < codes.length; ++i) { + if (codes[i].equals(high)) { + break; + } + } + newVal = LOW_TERMINAL_BIT | i; + } else { + int highPos = allocated++; + currentCode[highPos] = high; + newVal = highPos; + } + newVal <<= 16; + boolean lowTerminal = allCodes.remove(low); + if (lowTerminal) { + //bah, linear search + int i = 0; + for (i = 0; i < codes.length; ++i) { + if (codes[i].equals(low)) { + break; + } + } + newVal |= LOW_TERMINAL_BIT | i; + } else { + int lowPos = allocated++; + currentCode[lowPos] = low; + newVal |= lowPos; + } + codingTree[pos] = newVal; + pos++; + } + DECODING_TABLE = codingTree; + } + + /** + * Decodes a huffman encoded string into the target StringBuilder. There must be enough space left in the buffer + * for this method to succeed. + * + * @param data The byte buffer + * @param length The data length + * @param target The target for the decompressed data + */ + public static void decode(ByteBuffer data, int length, StringBuilder target) throws HpackException { + assert data.remaining() >= length; + int treePos = 0; + boolean eosBits = true; + for (int i = 0; i < length; ++i) { + byte b = data.get(); + int bitPos = 7; + while (bitPos >= 0) { + int val = DECODING_TABLE[treePos]; + if (((1 << bitPos) & b) == 0) { + eosBits = false; + //bit not set, we want the lower part of the tree + if ((val & LOW_TERMINAL_BIT) == 0) { + treePos = val & LOW_MASK; + } else { + target.append((char) (val & LOW_MASK)); + treePos = 0; + eosBits = true; + } + } else { + //bit not set, we want the lower part of the tree + if ((val & HIGH_TERMINAL_BIT) == 0) { + treePos = (val >> 16) & LOW_MASK; + } else { + target.append((char) ((val >> 16) & LOW_MASK)); + treePos = 0; + eosBits = true; + } + } + bitPos--; + } + } + if (!eosBits) { + throw new HpackException(sm.getString("hpackhuffman.huffmanEncodedHpackValueDidNotEndWithEOS")); + } + } + + + /** + * Encodes the given string into the buffer. If there is not enough space in the buffer, or the encoded + * version is bigger than the original it will return false and not modify the buffers position + * + * @param buffer The buffer to encode into + * @param toEncode The string to encode + * @param forceLowercase If the string should be encoded in lower case + * @return true if encoding succeeded + */ + public static boolean encode(ByteBuffer buffer, String toEncode, boolean forceLowercase) { + if (buffer.remaining() <= toEncode.length()) { + return false; + } + int start = buffer.position(); + //this sucks, but we need to put the length first + //and we don't really have any option but to calculate it in advance to make sure we have left enough room + //so we end up iterating twice + int length = 0; + for (int i = 0; i < toEncode.length(); ++i) { + byte c = (byte) toEncode.charAt(i); + if(forceLowercase) { + c = Hpack.toLower(c); + } + HuffmanCode code = HUFFMAN_CODES[c]; + length += code.length; + } + int byteLength = length / 8 + (length % 8 == 0 ? 0 : 1); + + buffer.put((byte) (1 << 7)); + Hpack.encodeInteger(buffer, byteLength, 7); + + + int bytePos = 0; + byte currentBufferByte = 0; + for (int i = 0; i < toEncode.length(); ++i) { + byte c = (byte) toEncode.charAt(i); + if(forceLowercase) { + c = Hpack.toLower(c); + } + HuffmanCode code = HUFFMAN_CODES[c]; + if (code.length + bytePos <= 8) { + //it fits in the current byte + currentBufferByte |= ((code.value & 0xFF) << 8 - (code.length + bytePos)); + bytePos += code.length; + } else { + //it does not fit, it may need up to 4 bytes + int val = code.value; + int rem = code.length; + while (rem > 0) { + if (!buffer.hasRemaining()) { + buffer.position(start); + return false; + } + int remainingInByte = 8 - bytePos; + if (rem > remainingInByte) { + currentBufferByte |= (val >> (rem - remainingInByte)); + } else { + currentBufferByte |= (val << (remainingInByte - rem)); + } + if (rem > remainingInByte) { + buffer.put(currentBufferByte); + currentBufferByte = 0; + bytePos = 0; + } else { + bytePos = rem; + } + rem -= remainingInByte; + } + } + if (bytePos == 8) { + if (!buffer.hasRemaining()) { + buffer.position(start); + return false; + } + buffer.put(currentBufferByte); + currentBufferByte = 0; + bytePos = 0; + } + if (buffer.position() - start > toEncode.length()) { + //the encoded version is longer than the original + //just return false + buffer.position(start); + return false; + } + } + if (bytePos > 0) { + //add the EOS bytes if we have not finished on a single byte + if (!buffer.hasRemaining()) { + buffer.position(start); + return false; + } + buffer.put((byte) (currentBufferByte | ((0xFF) >> bytePos))); + } + return true; + } + + protected static class HuffmanCode { + /** + * The value of the least significan't bits of the code + */ + int value; + /** + * length of the code, in bits + */ + int length; + + public HuffmanCode(int value, int length) { + this.value = value; + this.length = length; + } + + public int getValue() { + return value; + } + + public int getLength() { + return length; + } + + @Override + public boolean equals(Object o) { + + + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + + HuffmanCode that = (HuffmanCode) o; + + if (length != that.length) return false; + if (value != that.value) return false; + + return true; + } + + @Override + public int hashCode() { + int result = value; + result = 31 * result + length; + return result; + } + + @Override + public String toString() { + return "HuffmanCode{" + + "value=" + value + + ", length=" + length + + '}'; + } + } +} Propchange: tomcat/trunk/java/org/apache/coyote/http2/HPackHuffman.java ------------------------------------------------------------------------------ svn:eol-style = native Added: tomcat/trunk/java/org/apache/coyote/http2/Hpack.java URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/Hpack.java?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/java/org/apache/coyote/http2/Hpack.java (added) +++ tomcat/trunk/java/org/apache/coyote/http2/Hpack.java Fri Mar 20 18:47:03 2015 @@ -0,0 +1,215 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.coyote.http2; + +import java.nio.ByteBuffer; + +import org.apache.tomcat.util.res.StringManager; + +final class Hpack { + + protected static final StringManager sm = StringManager.getManager(Hpack.class); + + private static final byte LOWER_DIFF = 'a' - 'A'; + static final int DEFAULT_TABLE_SIZE = 4096; + private static final int MAX_INTEGER_OCTETS = 8; //not sure what a good value for this is, but the spec says we need to provide an upper bound + + /** + * table that contains powers of two, + * used as both bitmask and to quickly calculate 2^n + */ + private static final int[] PREFIX_TABLE; + + + static final HeaderField[] STATIC_TABLE; + static final int STATIC_TABLE_LENGTH; + + static { + PREFIX_TABLE = new int[32]; + for (int i = 0; i < 32; ++i) { + int n = 0; + for (int j = 0; j < i; ++j) { + n = n << 1; + n |= 1; + } + PREFIX_TABLE[i] = n; + } + + HeaderField[] fields = new HeaderField[62]; + //note that zero is not used + fields[1] = new HeaderField(":authority", null); + fields[2] = new HeaderField(":method", "GET"); + fields[3] = new HeaderField(":method", "POST"); + fields[4] = new HeaderField(":path", "/"); + fields[5] = new HeaderField(":path", "/index.html"); + fields[6] = new HeaderField(":scheme", "http"); + fields[7] = new HeaderField(":scheme", "https"); + fields[8] = new HeaderField(":status", "200"); + fields[9] = new HeaderField(":status", "204"); + fields[10] = new HeaderField(":status", "206"); + fields[11] = new HeaderField(":status", "304"); + fields[12] = new HeaderField(":status", "400"); + fields[13] = new HeaderField(":status", "404"); + fields[14] = new HeaderField(":status", "500"); + fields[15] = new HeaderField("accept-charset", null); + fields[16] = new HeaderField("accept-encoding", "gzip, deflate"); + fields[17] = new HeaderField("accept-language", null); + fields[18] = new HeaderField("accept-ranges", null); + fields[19] = new HeaderField("accept", null); + fields[20] = new HeaderField("access-control-allow-origin", null); + fields[21] = new HeaderField("age", null); + fields[22] = new HeaderField("allow", null); + fields[23] = new HeaderField("authorization", null); + fields[24] = new HeaderField("cache-control", null); + fields[25] = new HeaderField("content-disposition", null); + fields[26] = new HeaderField("content-encoding", null); + fields[27] = new HeaderField("content-language", null); + fields[28] = new HeaderField("content-length", null); + fields[29] = new HeaderField("content-location", null); + fields[30] = new HeaderField("content-range", null); + fields[31] = new HeaderField("content-type", null); + fields[32] = new HeaderField("cookie", null); + fields[33] = new HeaderField("date", null); + fields[34] = new HeaderField("etag", null); + fields[35] = new HeaderField("expect", null); + fields[36] = new HeaderField("expires", null); + fields[37] = new HeaderField("from", null); + fields[38] = new HeaderField("host", null); + fields[39] = new HeaderField("if-match", null); + fields[40] = new HeaderField("if-modified-since", null); + fields[41] = new HeaderField("if-none-match", null); + fields[42] = new HeaderField("if-range", null); + fields[43] = new HeaderField("if-unmodified-since", null); + fields[44] = new HeaderField("last-modified", null); + fields[45] = new HeaderField("link", null); + fields[46] = new HeaderField("location", null); + fields[47] = new HeaderField("max-forwards", null); + fields[48] = new HeaderField("proxy-authenticate", null); + fields[49] = new HeaderField("proxy-authorization", null); + fields[50] = new HeaderField("range", null); + fields[51] = new HeaderField("referer", null); + fields[52] = new HeaderField("refresh", null); + fields[53] = new HeaderField("retry-after", null); + fields[54] = new HeaderField("server", null); + fields[55] = new HeaderField("set-cookie", null); + fields[56] = new HeaderField("strict-transport-security", null); + fields[57] = new HeaderField("transfer-encoding", null); + fields[58] = new HeaderField("user-agent", null); + fields[59] = new HeaderField("vary", null); + fields[60] = new HeaderField("via", null); + fields[61] = new HeaderField("www-authenticate", null); + STATIC_TABLE = fields; + STATIC_TABLE_LENGTH = STATIC_TABLE.length - 1; + } + + static class HeaderField { + final String name; + final String value; + final int size; + + HeaderField(String name, String value) { + this.name = name; + this.value = value; + if (value != null) { + this.size = 32 + name.length() + value.length(); + } else { + this.size = -1; + } + } + } + + /** + * Decodes an integer in the HPACK prefex format. If the return value is -1 + * it means that there was not enough data in the buffer to complete the decoding + * sequence. + * <p/> + * If this method returns -1 then the source buffer will not have been modified. + * + * @param source The buffer that contains the integer + * @param n The encoding prefix length + * @return The encoded integer, or -1 if there was not enough data + */ + static int decodeInteger(ByteBuffer source, int n) throws HpackException { + if (source.remaining() == 0) { + return -1; + } + int count = 1; + int sp = source.position(); + int mask = PREFIX_TABLE[n]; + + int i = mask & source.get(); + int b; + if (i < PREFIX_TABLE[n]) { + return i; + } else { + int m = 0; + do { + if(count++ > MAX_INTEGER_OCTETS) { + throw new HpackException(sm.getString("hpack.integerEncodedOverTooManyOctets", MAX_INTEGER_OCTETS)); + } + if (source.remaining() == 0) { + //we have run out of data + //reset + source.position(sp); + return -1; + } + b = source.get(); + i = i + (b & 127) * (PREFIX_TABLE[m] + 1); + m += 7; + } while ((b & 128) == 128); + } + return i; + } + + /** + * Encodes an integer in the HPACK prefix format. + * <p/> + * This method assumes that the buffer has already had the first 8-n bits filled. + * As such it will modify the last byte that is already present in the buffer, and + * potentially add more if required + * + * @param source The buffer that contains the integer + * @param value The integer to encode + * @param n The encoding prefix length + */ + static void encodeInteger(ByteBuffer source, int value, int n) { + int twoNminus1 = PREFIX_TABLE[n]; + int pos = source.position() - 1; + if (value < twoNminus1) { + source.put(pos, (byte) (source.get(pos) | value)); + } else { + source.put(pos, (byte) (source.get(pos) | twoNminus1)); + value = value - twoNminus1; + while (value >= 128) { + source.put((byte) (value % 128 + 128)); + value = value / 128; + } + source.put((byte) value); + } + } + + + static byte toLower(byte b) { + if (b >= 'A' && b <= 'Z') { + return (byte) (b + LOWER_DIFF); + } + return b; + } + + private Hpack() {} + +} Propchange: tomcat/trunk/java/org/apache/coyote/http2/Hpack.java ------------------------------------------------------------------------------ svn:eol-style = native Added: tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java (added) +++ tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java Fri Mar 20 18:47:03 2015 @@ -0,0 +1,362 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.coyote.http2; + +import java.nio.ByteBuffer; + +import org.apache.tomcat.util.res.StringManager; + +import static org.apache.coyote.http2.Hpack.HeaderField; + +/** + * A decoder for HPACK. + */ +public class HpackDecoder { + + protected static final StringManager sm = StringManager.getManager(HpackDecoder.class); + + private static final int DEFAULT_RING_BUFFER_SIZE = 10; + + /** + * The object that receives the headers that are emitted from this decoder + */ + private HeaderEmitter headerEmitter; + + /** + * The header table + */ + private HeaderField[] headerTable; + + /** + * The current HEAD position of the header table. We use a ring buffer type + * construct as it would be silly to actually shuffle the items around in the + * array. + */ + private int firstSlotPosition = 0; + + /** + * The current table size by index (aka the number of index positions that are filled up) + */ + private int filledTableSlots = 0; + + /** + * the current calculates memory size, as per the HPACK algorithm + */ + private int currentMemorySize = 0; + + /** + * The maximum allowed memory size + */ + private int maxMemorySize; + + private final StringBuilder stringBuilder = new StringBuilder(); + + public HpackDecoder(int maxMemorySize) { + this.maxMemorySize = maxMemorySize; + headerTable = new HeaderField[DEFAULT_RING_BUFFER_SIZE]; + } + + public HpackDecoder() { + this(Hpack.DEFAULT_TABLE_SIZE); + } + + /** + * Decodes the provided frame data. If this method leaves data in the buffer then + * this buffer should be compacted so this data is preserved, unless there is no + * more data in which case this should be considered a protocol error. + * + * @param buffer The buffer + */ + public void decode(ByteBuffer buffer) throws HpackException { + while (buffer.hasRemaining()) { + int originalPos = buffer.position(); + byte b = buffer.get(); + if ((b & 0b10000000) != 0) { + //if the first bit is set it is an indexed header field + buffer.position(buffer.position() - 1); //unget the byte + int index = Hpack.decodeInteger(buffer, 7); //prefix is 7 + if (index == -1) { + buffer.position(originalPos); + return; + } else if(index == 0) { + throw new HpackException(sm.getString("hpackdecoder.zeroNotValidHeaderTableIndex")); + } + handleIndex(index); + } else if ((b & 0b01000000) != 0) { + //Literal Header Field with Incremental Indexing + String headerName = readHeaderName(buffer, 6); + if (headerName == null) { + buffer.position(originalPos); + return; + } + String headerValue = readHpackString(buffer); + if (headerValue == null) { + buffer.position(originalPos); + return; + } + headerEmitter.emitHeader(headerName, headerValue, false); + addEntryToHeaderTable(new HeaderField(headerName, headerValue)); + } else if ((b & 0b11110000) == 0) { + //Literal Header Field without Indexing + String headerName = readHeaderName(buffer, 4); + if (headerName == null) { + buffer.position(originalPos); + return; + } + String headerValue = readHpackString(buffer); + if (headerValue == null) { + buffer.position(originalPos); + return; + } + headerEmitter.emitHeader(headerName, headerValue, false); + } else if ((b & 0b11110000) == 0b00010000) { + //Literal Header Field never indexed + String headerName = readHeaderName(buffer, 4); + if (headerName == null) { + buffer.position(originalPos); + return; + } + String headerValue = readHpackString(buffer); + if (headerValue == null) { + buffer.position(originalPos); + return; + } + headerEmitter.emitHeader(headerName, headerValue, true); + } else if ((b & 0b11100000) == 0b00100000) { + //context update max table size change + if (!handleMaxMemorySizeChange(buffer, originalPos)) { + return; + } + } else { + throw new RuntimeException("Not yet implemented"); + } + } + } + + private boolean handleMaxMemorySizeChange(ByteBuffer buffer, int originalPos) throws HpackException { + buffer.position(buffer.position() - 1); //unget the byte + int size = Hpack.decodeInteger(buffer, 5); + if (size == -1) { + buffer.position(originalPos); + return false; + } + maxMemorySize = size; + if (currentMemorySize > maxMemorySize) { + int newTableSlots = filledTableSlots; + int tableLength = headerTable.length; + int newSize = currentMemorySize; + while (newSize > maxMemorySize) { + int clearIndex = firstSlotPosition; + firstSlotPosition++; + if (firstSlotPosition == tableLength) { + firstSlotPosition = 0; + } + HeaderField oldData = headerTable[clearIndex]; + headerTable[clearIndex] = null; + newSize -= oldData.size; + newTableSlots--; + } + this.filledTableSlots = newTableSlots; + currentMemorySize = newSize; + } + return true; + } + + private String readHeaderName(ByteBuffer buffer, int prefixLength) throws HpackException { + buffer.position(buffer.position() - 1); //unget the byte + int index = Hpack.decodeInteger(buffer, prefixLength); + if (index == -1) { + return null; + } else if (index != 0) { + return handleIndexedHeaderName(index); + } else { + return readHpackString(buffer); + } + } + + private String readHpackString(ByteBuffer buffer) throws HpackException { + if (!buffer.hasRemaining()) { + return null; + } + byte data = buffer.get(buffer.position()); + + int length = Hpack.decodeInteger(buffer, 7); + if (buffer.remaining() < length) { + return null; + } + boolean huffman = (data & 0b10000000) != 0; + if (huffman) { + return readHuffmanString(length, buffer); + } + for (int i = 0; i < length; ++i) { + stringBuilder.append((char) buffer.get()); + } + String ret = stringBuilder.toString(); + stringBuilder.setLength(0); + return ret; + } + + private String readHuffmanString(int length, ByteBuffer buffer) throws HpackException { + HPackHuffman.decode(buffer, length, stringBuilder); + String ret = stringBuilder.toString(); + stringBuilder.setLength(0); + return ret; + } + + private String handleIndexedHeaderName(int index) throws HpackException { + if (index <= Hpack.STATIC_TABLE_LENGTH) { + return Hpack.STATIC_TABLE[index].name; + } else { + if (index >= Hpack.STATIC_TABLE_LENGTH + filledTableSlots) { + throw new HpackException(); + } + int adjustedIndex = getRealIndex(index - Hpack.STATIC_TABLE_LENGTH); + HeaderField res = headerTable[adjustedIndex]; + if (res == null) { + throw new HpackException(); + } + return res.name; + } + } + + /** + * Handle an indexed header representation + * + * @param index The index + * @throws HpackException + */ + private void handleIndex(int index) throws HpackException { + if (index <= Hpack.STATIC_TABLE_LENGTH) { + addStaticTableEntry(index); + } else { + int adjustedIndex = getRealIndex(index - Hpack.STATIC_TABLE_LENGTH); + HeaderField headerField = headerTable[adjustedIndex]; + headerEmitter.emitHeader(headerField.name, headerField.value, false); + } + } + + /** + * because we use a ring buffer type construct, and don't actually shuffle + * items in the array, we need to figure out the real index to use. + * <p/> + * package private for unit tests + * + * @param index The index from the hpack + * @return the real index into the array + */ + int getRealIndex(int index) { + //the index is one based, but our table is zero based, hence -1 + //also because of our ring buffer setup the indexes are reversed + //index = 1 is at position firstSlotPosition + filledSlots + return (firstSlotPosition + (filledTableSlots - index)) % headerTable.length; + } + + private void addStaticTableEntry(int index) throws HpackException { + //adds an entry from the static table. + //this must be an entry with a value as far as I can determine + HeaderField entry = Hpack.STATIC_TABLE[index]; + if (entry.value == null) { + throw new HpackException(); + } + headerEmitter.emitHeader(entry.name, entry.value, false); + } + + private void addEntryToHeaderTable(HeaderField entry) { + if (entry.size > maxMemorySize) { + //it is to big to fit, so we just completely clear the table. + while (filledTableSlots > 0) { + headerTable[firstSlotPosition] = null; + firstSlotPosition++; + if (firstSlotPosition == headerTable.length) { + firstSlotPosition = 0; + } + filledTableSlots--; + } + currentMemorySize = 0; + return; + } + resizeIfRequired(); + int newTableSlots = filledTableSlots + 1; + int tableLength = headerTable.length; + int index = (firstSlotPosition + filledTableSlots) % tableLength; + headerTable[index] = entry; + int newSize = currentMemorySize + entry.size; + while (newSize > maxMemorySize) { + int clearIndex = firstSlotPosition; + firstSlotPosition++; + if (firstSlotPosition == tableLength) { + firstSlotPosition = 0; + } + HeaderField oldData = headerTable[clearIndex]; + headerTable[clearIndex] = null; + newSize -= oldData.size; + newTableSlots--; + } + this.filledTableSlots = newTableSlots; + currentMemorySize = newSize; + } + + private void resizeIfRequired() { + if(filledTableSlots == headerTable.length) { + HeaderField[] newArray = new HeaderField[headerTable.length + 10]; //we only grow slowly + for(int i = 0; i < headerTable.length; ++i) { + newArray[i] = headerTable[(firstSlotPosition + i) % headerTable.length]; + } + firstSlotPosition = 0; + headerTable = newArray; + } + } + + + /** + * Interface that can be used to immediately validate headers (ex: uppercase detection). + */ + public interface HeaderEmitter { + void emitHeader(String name, String value, boolean neverIndex); + } + + + public HeaderEmitter getHeaderEmitter() { + return headerEmitter; + } + + public void setHeaderEmitter(HeaderEmitter headerEmitter) { + this.headerEmitter = headerEmitter; + } + + //package private fields for unit tests + + int getFirstSlotPosition() { + return firstSlotPosition; + } + + HeaderField[] getHeaderTable() { + return headerTable; + } + + int getFilledTableSlots() { + return filledTableSlots; + } + + int getCurrentMemorySize() { + return currentMemorySize; + } + + int getMaxMemorySize() { + return maxMemorySize; + } +} Propchange: tomcat/trunk/java/org/apache/coyote/http2/HpackDecoder.java ------------------------------------------------------------------------------ svn:eol-style = native Added: tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java (added) +++ tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java Fri Mar 20 18:47:03 2015 @@ -0,0 +1,390 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.coyote.http2; + +import java.nio.ByteBuffer; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Deque; +import java.util.HashMap; +import java.util.List; +import java.util.Locale; +import java.util.Map; + +import org.apache.tomcat.util.http.MimeHeaders; + +import static org.apache.coyote.http2.Hpack.HeaderField; +import static org.apache.coyote.http2.Hpack.STATIC_TABLE; +import static org.apache.coyote.http2.Hpack.STATIC_TABLE_LENGTH; +import static org.apache.coyote.http2.Hpack.encodeInteger; + +/** + * Encoder for HPACK frames. + */ +public class HpackEncoder { + + public static final HpackHeaderFunction DEFAULT_HEADER_FUNCTION = new HpackHeaderFunction() { + @Override + public boolean shouldUseIndexing(String headerName, String value) { + //content length and date change all the time + //no need to index them, or they will churn the table + return !headerName.equals("content-length") && !headerName.equals("date"); + } + + @Override + public boolean shouldUseHuffman(String header, String value) { + return value.length() > 5; //TODO: figure out a good value for this + } + + @Override + public boolean shouldUseHuffman(String header) { + return header.length() > 5; //TODO: figure out a good value for this + } + + + }; + + private int headersIterator = -1; + private boolean firstPass = true; + + private MimeHeaders currentHeaders; + + private int entryPositionCounter; + + private int newMaxHeaderSize = -1; //if the max header size has been changed + private int minNewMaxHeaderSize = -1; //records the smallest value of newMaxHeaderSize, as per section 4.1 + + private static final Map<String, TableEntry[]> ENCODING_STATIC_TABLE; + + private final Deque<TableEntry> evictionQueue = new ArrayDeque<>(); + private final Map<String, List<TableEntry>> dynamicTable = new HashMap<>(); //TODO: use a custom data structure to reduce allocations + + static { + Map<String, TableEntry[]> map = new HashMap<>(); + for (int i = 1; i < STATIC_TABLE.length; ++i) { + HeaderField m = STATIC_TABLE[i]; + TableEntry[] existing = map.get(m.name); + if (existing == null) { + map.put(m.name, new TableEntry[]{new TableEntry(m.name, m.value, i)}); + } else { + TableEntry[] newEntry = new TableEntry[existing.length + 1]; + System.arraycopy(existing, 0, newEntry, 0, existing.length); + newEntry[existing.length] = new TableEntry(m.name, m.value, i); + map.put(m.name, newEntry); + } + } + ENCODING_STATIC_TABLE = Collections.unmodifiableMap(map); + } + + /** + * The maximum table size + */ + private int maxTableSize; + + /** + * The current table size + */ + private int currentTableSize; + + private final HpackHeaderFunction hpackHeaderFunction; + + public HpackEncoder(int maxTableSize, HpackHeaderFunction headerFunction) { + this.maxTableSize = maxTableSize; + this.hpackHeaderFunction = headerFunction; + } + + public HpackEncoder(int maxTableSize) { + this(maxTableSize, DEFAULT_HEADER_FUNCTION); + } + + /** + * Encodes the headers into a buffer. + * + * @param headers + * @param target + */ + public State encode(MimeHeaders headers, ByteBuffer target) { + int it = headersIterator; + if (headersIterator == -1) { + handleTableSizeChange(target); + //new headers map + it = 0; + currentHeaders = headers; + } else { + if (headers != currentHeaders) { + throw new IllegalStateException(); + } + } + while (it < currentHeaders.size()) { + // FIXME: Review lowercase policy + String headerName = headers.getName(it).toString().toLowerCase(Locale.US); + boolean skip = false; + if (firstPass) { + if (headerName.charAt(0) != ':') { + skip = true; + } + } else { + if (headerName.charAt(0) == ':') { + skip = true; + } + } + if (!skip) { + + int required = 11 + headerName.length(); //we use 11 to make sure we have enough room for the variable length integers + + String val = headers.getValue(it).toString(); + TableEntry tableEntry = findInTable(headerName, val); + + required += (1 + val.length()); + + if (target.remaining() < required) { + this.headersIterator = it; + return State.UNDERFLOW; + } + boolean canIndex = hpackHeaderFunction.shouldUseIndexing(headerName, val) && (headerName.length() + val.length() + 32) < maxTableSize; //only index if it will fit + if (tableEntry == null && canIndex) { + //add the entry to the dynamic table + target.put((byte) (1 << 6)); + writeHuffmanEncodableName(target, headerName); + writeHuffmanEncodableValue(target, headerName, val); + addToDynamicTable(headerName, val); + } else if (tableEntry == null) { + //literal never indexed + target.put((byte) (1 << 4)); + writeHuffmanEncodableName(target, headerName); + writeHuffmanEncodableValue(target, headerName, val); + } else { + //so we know something is already in the table + if (val.equals(tableEntry.value)) { + //the whole thing is in the table + target.put((byte) (1 << 7)); + encodeInteger(target, tableEntry.getPosition(), 7); + } else { + if (canIndex) { + //add the entry to the dynamic table + target.put((byte) (1 << 6)); + encodeInteger(target, tableEntry.getPosition(), 6); + writeHuffmanEncodableValue(target, headerName, val); + addToDynamicTable(headerName, val); + + } else { + target.put((byte) (1 << 4)); + encodeInteger(target, tableEntry.getPosition(), 4); + writeHuffmanEncodableValue(target, headerName, val); + } + } + } + + } + if (++it == currentHeaders.size() && firstPass) { + firstPass = false; + it = 0; + } + } + headersIterator = -1; + firstPass = true; + return State.COMPLETE; + } + + private void writeHuffmanEncodableName(ByteBuffer target, String headerName) { + if (hpackHeaderFunction.shouldUseHuffman(headerName)) { + if(HPackHuffman.encode(target, headerName.toString(), true)) { + return; + } + } + target.put((byte) 0); //to use encodeInteger we need to place the first byte in the buffer. + encodeInteger(target, headerName.length(), 7); + for (int j = 0; j < headerName.length(); ++j) { + target.put(Hpack.toLower((byte) headerName.charAt(j))); + } + + } + + private void writeHuffmanEncodableValue(ByteBuffer target, String headerName, String val) { + if (hpackHeaderFunction.shouldUseHuffman(headerName, val)) { + if (!HPackHuffman.encode(target, val, false)) { + writeValueString(target, val); + } + } else { + writeValueString(target, val); + } + } + + private void writeValueString(ByteBuffer target, String val) { + target.put((byte) 0); //to use encodeInteger we need to place the first byte in the buffer. + encodeInteger(target, val.length(), 7); + for (int j = 0; j < val.length(); ++j) { + target.put((byte) val.charAt(j)); + } + } + + private void addToDynamicTable(String headerName, String val) { + int pos = entryPositionCounter++; + DynamicTableEntry d = new DynamicTableEntry(headerName, val, -pos); + List<TableEntry> existing = dynamicTable.get(headerName); + if (existing == null) { + dynamicTable.put(headerName, existing = new ArrayList<TableEntry>(1)); + } + existing.add(d); + evictionQueue.add(d); + currentTableSize += d.size; + runEvictionIfRequired(); + if (entryPositionCounter == Integer.MAX_VALUE) { + //prevent rollover + preventPositionRollover(); + } + + } + + + private void preventPositionRollover() { + //if the position counter is about to roll over we iterate all the table entries + //and set their position to their actual position + for (Map.Entry<String, List<TableEntry>> entry : dynamicTable.entrySet()) { + for (TableEntry t : entry.getValue()) { + t.position = t.getPosition(); + } + } + entryPositionCounter = 0; + } + + private void runEvictionIfRequired() { + + while (currentTableSize > maxTableSize) { + TableEntry next = evictionQueue.poll(); + if (next == null) { + return; + } + currentTableSize -= next.size; + List<TableEntry> list = dynamicTable.get(next.name); + list.remove(next); + if (list.isEmpty()) { + dynamicTable.remove(next.name); + } + } + } + + private TableEntry findInTable(String headerName, String value) { + TableEntry[] staticTable = ENCODING_STATIC_TABLE.get(headerName); + if (staticTable != null) { + for (TableEntry st : staticTable) { + if (st.value != null && st.value.equals(value)) { //todo: some form of lookup? + return st; + } + } + } + List<TableEntry> dynamic = dynamicTable.get(headerName); + if (dynamic != null) { + for (TableEntry st : dynamic) { + if (st.value.equals(value)) { //todo: some form of lookup? + return st; + } + } + } + if (staticTable != null) { + return staticTable[0]; + } + return null; + } + + public void setMaxTableSize(int newSize) { + this.newMaxHeaderSize = newSize; + if (minNewMaxHeaderSize == -1) { + minNewMaxHeaderSize = newSize; + } else { + minNewMaxHeaderSize = Math.min(newSize, minNewMaxHeaderSize); + } + } + + private void handleTableSizeChange(ByteBuffer target) { + if (newMaxHeaderSize == -1) { + return; + } + if (minNewMaxHeaderSize != newMaxHeaderSize) { + target.put((byte) (1 << 5)); + encodeInteger(target, minNewMaxHeaderSize, 5); + } + target.put((byte) (1 << 5)); + encodeInteger(target, newMaxHeaderSize, 5); + maxTableSize = newMaxHeaderSize; + runEvictionIfRequired(); + newMaxHeaderSize = -1; + minNewMaxHeaderSize = -1; + } + + public enum State { + COMPLETE, + UNDERFLOW, + + } + + static class TableEntry { + final String name; + final String value; + final int size; + int position; + + TableEntry(String name, String value, int position) { + this.name = name; + this.value = value; + this.position = position; + if (value != null) { + this.size = 32 + name.length() + value.length(); + } else { + this.size = -1; + } + } + + public int getPosition() { + return position; + } + } + + class DynamicTableEntry extends TableEntry { + + DynamicTableEntry(String name, String value, int position) { + super(name, value, position); + } + + @Override + public int getPosition() { + return super.getPosition() + entryPositionCounter + STATIC_TABLE_LENGTH; + } + } + + public interface HpackHeaderFunction { + boolean shouldUseIndexing(String header, String value); + + /** + * Returns true if huffman encoding should be used on the header value + * + * @param header The header name + * @param value The header value to be encoded + * @return <code>true</code> if the value should be encoded + */ + boolean shouldUseHuffman(String header, String value); + + /** + * Returns true if huffman encoding should be used on the header name + * + * @param header The header name to be encoded + * @return <code>true</code> if the value should be encoded + */ + boolean shouldUseHuffman(String header); + } +} Propchange: tomcat/trunk/java/org/apache/coyote/http2/HpackEncoder.java ------------------------------------------------------------------------------ svn:eol-style = native Added: tomcat/trunk/java/org/apache/coyote/http2/HpackException.java URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/HpackException.java?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/java/org/apache/coyote/http2/HpackException.java (added) +++ tomcat/trunk/java/org/apache/coyote/http2/HpackException.java Fri Mar 20 18:47:03 2015 @@ -0,0 +1,34 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.coyote.http2; + +/** + * Exception that is thrown when the HPACK compress context is broken. + * <p/> + * In this case the connection must be closed. + */ +public class HpackException extends Exception { + public HpackException(String message, Throwable cause) { + super(message, cause); + } + public HpackException(String message) { + super(message); + } + public HpackException() { + super(); + } +} Propchange: tomcat/trunk/java/org/apache/coyote/http2/HpackException.java ------------------------------------------------------------------------------ svn:eol-style = native Added: tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties URL: http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties (added) +++ tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties Fri Mar 20 18:47:03 2015 @@ -0,0 +1,20 @@ +# Licensed to the Apache Software Foundation (ASF) under one or more +# contributor license agreements. See the NOTICE file distributed with +# this work for additional information regarding copyright ownership. +# The ASF licenses this file to You under the Apache License, Version 2.0 +# (the "License"); you may not use this file except in compliance with +# the License. You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +hpack.integerEncodedOverTooManyOctets=HPACK variable length integer encoded over too many octets, max is {0} + +hpackdecoder.zeroNotValidHeaderTableIndex=Zero is not a valid header table index + +hpackhuffman.huffmanEncodedHpackValueDidNotEndWithEOS=Huffman encoded value in HPACK headers did not end with EOS padding \ No newline at end of file Propchange: tomcat/trunk/java/org/apache/coyote/http2/LocalStrings.properties ------------------------------------------------------------------------------ svn:eol-style = native Added: tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java URL: http://svn.apache.org/viewvc/tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java?rev=1668116&view=auto ============================================================================== --- tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java (added) +++ tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java Fri Mar 20 18:47:03 2015 @@ -0,0 +1,85 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.coyote.http2; + +import java.nio.ByteBuffer; + +import org.apache.tomcat.util.http.MimeHeaders; +import org.junit.Assert; +import org.junit.Test; + +public class TestHpack { + + @Test + public void testEncode() throws Exception { + MimeHeaders headers = new MimeHeaders(); + headers.setValue("header1").setString("value1"); + headers.setValue(":status").setString("200"); + headers.setValue("header2").setString("value2"); + ByteBuffer output = ByteBuffer.allocate(512); + HpackEncoder encoder = new HpackEncoder(1024); + encoder.encode(headers, output); + output.flip(); + // Size is supposed to be 33 without huffman, or 27 with it + // TODO: use the HpackHeaderFunction to enable huffman predictably + Assert.assertEquals(27, output.remaining()); + output.clear(); + encoder.encode(headers, output); + output.flip(); + // Size is now 3 after using the table + Assert.assertEquals(3, output.remaining()); + } + + @Test + public void testDecode() throws Exception { + MimeHeaders headers = new MimeHeaders(); + headers.setValue("header1").setString("value1"); + headers.setValue(":status").setString("200"); + headers.setValue("header2").setString("value2"); + ByteBuffer output = ByteBuffer.allocate(512); + HpackEncoder encoder = new HpackEncoder(1024); + encoder.encode(headers, output); + output.flip(); + MimeHeaders headers2 = new MimeHeaders(); + HpackDecoder decoder = new HpackDecoder(); + decoder.setHeaderEmitter(new HeadersListener(headers2)); + decoder.decode(output); + // Redo (table is supposed to be updated) + output.clear(); + encoder.encode(headers, output); + output.flip(); + headers2.recycle(); + Assert.assertEquals(3, output.remaining()); + // Check that the decoder is using the table right + decoder.decode(output); + Assert.assertEquals("value2", headers2.getHeader("header2")); + } + + private static class HeadersListener implements HpackDecoder.HeaderEmitter { + private final MimeHeaders headers; + public HeadersListener(MimeHeaders headers) { + this.headers = headers; + } + @Override + public void emitHeader(String name, String value, boolean neverIndex) { + headers.setValue(name).setString(value); + } + } + + // TODO: Write more complete tests + +} Propchange: tomcat/trunk/test/org/apache/coyote/http2/TestHpack.java ------------------------------------------------------------------------------ svn:eol-style = native Modified: tomcat/trunk/webapps/docs/changelog.xml URL: http://svn.apache.org/viewvc/tomcat/trunk/webapps/docs/changelog.xml?rev=1668116&r1=1668115&r2=1668116&view=diff ============================================================================== --- tomcat/trunk/webapps/docs/changelog.xml (original) +++ tomcat/trunk/webapps/docs/changelog.xml Fri Mar 20 18:47:03 2015 @@ -73,6 +73,10 @@ <bug>55988</bug>: Add support for Java 8 JSSE server-preferred TLS cipher suite ordering. Patch provided by Ognjen Blagojevic. (schultz) </fix> + <add> + Add support for HPACK header encoding and decoding, contributed + by Stuart Douglas. (remm) + </add> </changelog> </subsection> <subsection name="Tribes"> --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@tomcat.apache.org For additional commands, e-mail: dev-h...@tomcat.apache.org