Repository: trafficserver Updated Branches: refs/heads/master 53e56ffc7 -> 34a9a719a
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/fa6c830f/proxy/http2/HTTP2.cc ---------------------------------------------------------------------- diff --git a/proxy/http2/HTTP2.cc b/proxy/http2/HTTP2.cc index 59b1e0f..1760ade 100644 --- a/proxy/http2/HTTP2.cc +++ b/proxy/http2/HTTP2.cc @@ -22,6 +22,8 @@ */ #include "HTTP2.h" +#include "HPACK.h" +#include "HuffmanCodec.h" #include "ink_assert.h" const char * const HTTP2_CONNECTION_PREFACE = "PRI * HTTP/2.0\r\n\r\nSM\r\n\r\n"; @@ -267,3 +269,506 @@ http2_parse_settings_parameter(IOVec iov, Http2SettingsParameter& param) return true; } + +MIMEParseResult +convert_from_2_to_1_1_header(HTTPHdr* headers) +{ + MIMEField* field; + + ink_assert(http_hdr_type_get(headers->m_http) != HTTP_TYPE_UNKNOWN); + + if (http_hdr_type_get(headers->m_http) == HTTP_TYPE_REQUEST) { + const char *scheme, *authority, *path, *method; + int scheme_len, authority_len, path_len, method_len; + + // Get values of :scheme, :authority and :path to assemble requested URL + if ((field = headers->field_find(HPACK_VALUE_SCHEME, HPACK_LEN_SCHEME)) != NULL) { + scheme = field->value_get(&scheme_len); + } else { + return PARSE_ERROR; + } + + if ((field = headers->field_find(HPACK_VALUE_AUTHORITY, HPACK_LEN_AUTHORITY)) != NULL) { + authority = field->value_get(&authority_len); + } else { + return PARSE_ERROR; + } + + if ((field = headers->field_find(HPACK_VALUE_PATH, HPACK_LEN_PATH)) != NULL) { + path = field->value_get(&path_len); + } else { + return PARSE_ERROR; + } + + // Parse URL + Arena arena; + size_t url_length = scheme_len + 3 + authority_len + path_len; + char* url = arena.str_alloc(url_length); + const char* url_start = url; + strncpy(url, scheme, scheme_len); + strncpy(url+scheme_len, "://", 3); + strncpy(url+scheme_len+3, authority, authority_len); + strncpy(url+scheme_len+3+authority_len, path, path_len); + url_parse(headers->m_heap, headers->m_http->u.req.m_url_impl, &url_start, url + url_length, 1); + arena.str_free(url); + + // Get value of :method + if ((field = headers->field_find(HPACK_VALUE_METHOD, HPACK_LEN_METHOD)) != NULL) { + method = field->value_get(&method_len); + + int method_wks_idx = hdrtoken_tokenize(method, method_len); + http_hdr_method_set(headers->m_heap, headers->m_http, + method, method_wks_idx, method_len, 0); + } else { + return PARSE_ERROR; + } + + // Convert HTTP version to 1.1 + int32_t version = HTTP_VERSION(1, 1); + http_hdr_version_set(headers->m_http, version); + + // Remove HTTP/2 style headers + headers->field_delete(HPACK_VALUE_SCHEME, HPACK_LEN_SCHEME); + headers->field_delete(HPACK_VALUE_METHOD, HPACK_LEN_METHOD); + headers->field_delete(HPACK_VALUE_AUTHORITY, HPACK_LEN_AUTHORITY); + headers->field_delete(HPACK_VALUE_PATH, HPACK_LEN_PATH); + } else { + int status_len; + const char* status; + + if ((field = headers->field_find(HPACK_VALUE_STATUS, HPACK_LEN_STATUS)) != NULL) { + status = field->value_get(&status_len); + headers->status_set(http_parse_status(status, status + status_len)); + } else { + return PARSE_ERROR; + } + + // Remove HTTP/2 style headers + headers->field_delete(HPACK_VALUE_STATUS, HPACK_LEN_STATUS); + } + + return PARSE_DONE; +} + +int64_t +convert_from_1_1_to_2_header(HTTPHdr* in, uint8_t* out, uint64_t out_len, Http2HeaderTable& /* header_table */) +{ + uint8_t *p = out; + uint8_t *end = out + out_len; + int64_t len; + + ink_assert(http_hdr_type_get(in->m_http) != HTTP_TYPE_UNKNOWN); + + // TODO Get a index value from the tables for the header field, and then choose a representation type. + // TODO Each indexing types per field should be passed by a caller, HTTP/2 implementation. + + MIMEField* field; + MIMEFieldIter field_iter; + for (field = in->iter_get_first(&field_iter); field != NULL; field = in->iter_get_next(&field_iter)) { + do { + MIMEFieldWrapper header(field, in->m_heap, in->m_http->m_fields_impl); + if ((len = encode_literal_header_field(p, end, header, INC_INDEXING)) == -1) { + return -1; + } + p += len; + } while (field->has_dups() && (field = field->m_next_dup) != NULL); + } + + return p - out; +} + +MIMEParseResult +http2_parse_header_fragment(HTTPHdr * hdr, IOVec iov, Http2HeaderTable& header_table) +{ + uint8_t * buf_start = (uint8_t *)iov.iov_base; + uint8_t * buf_end = (uint8_t *)iov.iov_base + iov.iov_len; + + uint8_t * cursor = buf_start; + HdrHeap * heap = hdr->m_heap; + HTTPHdrImpl * hh = hdr->m_http; + + do { + int64_t read_bytes = 0; + + if ((read_bytes = update_header_table_size(cursor, buf_end, header_table)) == -1) { + return PARSE_ERROR; + } + + // decode a header field encoded by HPACK + MIMEField *field = mime_field_create(heap, hh->m_fields_impl); + MIMEFieldWrapper header(field, heap, hh->m_fields_impl); + if (*cursor & 0x80) { + if ((read_bytes = decode_indexed_header_field(header, cursor, buf_end, header_table)) == -1) { + return PARSE_ERROR; + } + cursor += read_bytes; + } else { + if ((read_bytes = decode_literal_header_field(header, cursor, buf_end, header_table)) == -1) { + return PARSE_ERROR; + } + cursor += read_bytes; + } + + // Store to HdrHeap + mime_hdr_field_attach(hh->m_fields_impl, field, 1, NULL); + } while (cursor < buf_end); + + return PARSE_DONE; +} + +#if TS_HAS_TESTS + +#include "TestBox.h" + +// Constants for regression test +const static int BUFSIZE_FOR_REGRESSION_TEST = 128; +const static int MAX_TEST_FIELD_NUM = 8; + +/*********************************************************************************** + * * + * Test cases for regression test * + * * + * Some test cases are based on examples of specification. * + * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-09#appendix-D * + * * + ***********************************************************************************/ + +// D.1. Integer Representation Examples +const static struct { + uint32_t raw_integer; + uint8_t* encoded_field; + int encoded_field_len; + int prefix; +} integer_test_case[] = { + { 10, (uint8_t*)"\x0A", 1, 5 }, + { 1337, (uint8_t*)"\x1F\x9A\x0A", 3, 5 }, + { 42, (uint8_t*)"\x2A", 1, 8 } +}; + +// Example: custom-key: custom-header +const static struct { + char* raw_string; + uint32_t raw_string_len; + uint8_t* encoded_field; + int encoded_field_len; +} string_test_case[] = { + { (char*)"custom-key", 10, (uint8_t*)"\xA" "custom-key", 11 }, + { (char*)"custom-key", 10, (uint8_t*)"\x88" "\x25\xa8\x49\xe9\x5b\xa9\x7d\x7f", 9 } +}; + +// D.2.4. Indexed Header Field +const static struct { + int index; + char* raw_name; + char* raw_value; + uint8_t* encoded_field; + int encoded_field_len; +} indexed_test_case[] = { + { 2, (char*)":method", (char*)"GET", (uint8_t*)"\x82", 1 } +}; + +// D.2. Header Field Representation Examples +const static struct { + char* raw_name; + char* raw_value; + int index; + HEADER_INDEXING_TYPE type; + uint8_t* encoded_field; + int encoded_field_len; +} literal_test_case[] = { + { (char*)"custom-key", (char*)"custom-header", 0, INC_INDEXING, (uint8_t*)"\x40\x0a" "custom-key\x0d" "custom-header", 26 }, + { (char*)"custom-key", (char*)"custom-header", 0, WITHOUT_INDEXING, (uint8_t*)"\x00\x0a" "custom-key\x0d" "custom-header", 26 }, + { (char*)"custom-key", (char*)"custom-header", 0, NEVER_INDEXED, (uint8_t*)"\x10\x0a" "custom-key\x0d" "custom-header", 26 }, + { (char*)":path", (char*)"/sample/path", 4, INC_INDEXING, (uint8_t*)"\x44\x0c" "/sample/path", 14 }, + { (char*)":path", (char*)"/sample/path", 4, WITHOUT_INDEXING, (uint8_t*)"\x04\x0c" "/sample/path", 14 }, + { (char*)":path", (char*)"/sample/path", 4, NEVER_INDEXED, (uint8_t*)"\x14\x0c" "/sample/path", 14 }, + { (char*)"password", (char*)"secret", 0, INC_INDEXING, (uint8_t*)"\x40\x08" "password\x06" "secret", 17 }, + { (char*)"password", (char*)"secret", 0, WITHOUT_INDEXING, (uint8_t*)"\x00\x08" "password\x06" "secret", 17 }, + { (char*)"password", (char*)"secret", 0, NEVER_INDEXED, (uint8_t*)"\x10\x08" "password\x06" "secret", 17 } +}; + +// D.3. Request Examples without Huffman Coding - D.3.1. First Request +const static struct { + char* raw_name; + char* raw_value; +} raw_field_test_case[][MAX_TEST_FIELD_NUM] = { + { + { (char*)":method", (char*)"GET" }, + { (char*)":scheme", (char*)"http" }, + { (char*)":path", (char*)"/" }, + { (char*)":authority", (char*)"www.example.com" }, + { (char*)"", (char*)"" } // End of this test case + } +}; +const static struct { + uint8_t* encoded_field; + int encoded_field_len; +} encoded_field_test_case[] = { + { + (uint8_t*)"\x40" "\x7:method" "\x3GET" + "\x40" "\x7:scheme" "\x4http" + "\x40" "\x5:path" "\x1/" + "\x40" "\xa:authority" "\xfwww.example.com", + 64 + } +}; + +/*********************************************************************************** + * * + * Regression test codes * + * * + ***********************************************************************************/ + +REGRESSION_TEST(HPACK_EncodeInteger)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + + for (unsigned int i=0; i<sizeof(integer_test_case)/sizeof(integer_test_case[0]); i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + int len = encode_integer(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, integer_test_case[i].raw_integer, integer_test_case[i].prefix); + + box.check(len == integer_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, integer_test_case[i].encoded_field_len); + box.check(memcmp(buf, integer_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } +} + +REGRESSION_TEST(HPACK_EncodeString)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + int len; + + // FIXME Current encoder don't support huffman conding. + for (unsigned int i=0; i<1; i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + len = encode_string(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, string_test_case[i].raw_string, string_test_case[i].raw_string_len); + + box.check(len == string_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, integer_test_case[i].encoded_field_len); + box.check(memcmp(buf, string_test_case[i].encoded_field, len) == 0, "encoded string was invalid"); + } +} + +REGRESSION_TEST(HPACK_EncodeIndexedHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + + for (unsigned int i=0; i<sizeof(indexed_test_case)/sizeof(indexed_test_case[0]); i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + int len = encode_indexed_header_field(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, indexed_test_case[i].index); + + box.check(len == indexed_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, indexed_test_case[i].encoded_field_len); + box.check(memcmp(buf, indexed_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } +} + +REGRESSION_TEST(HPACK_EncodeLiteralHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + int len; + + for (unsigned int i=0; i<sizeof(literal_test_case)/sizeof(literal_test_case[0]); i++) { + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_RESPONSE); + MIMEField *field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + MIMEFieldWrapper header(field, headers->m_heap, headers->m_http->m_fields_impl); + + header.value_set(literal_test_case[i].raw_value, strlen(literal_test_case[i].raw_value)); + if (literal_test_case[i].index > 0) { + len = encode_literal_header_field(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, header, literal_test_case[i].index, literal_test_case[i].type); + } else { + header.name_set(literal_test_case[i].raw_name, strlen(literal_test_case[i].raw_name)); + len = encode_literal_header_field(buf, buf+BUFSIZE_FOR_REGRESSION_TEST, header, literal_test_case[i].type); + } + + box.check(len == literal_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", len, literal_test_case[i].encoded_field_len); + box.check(memcmp(buf, literal_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } + +} + +REGRESSION_TEST(HPACK_Encode)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint8_t buf[BUFSIZE_FOR_REGRESSION_TEST]; + Http2HeaderTable header_table; + + // FIXME Current encoder don't support indexing. + for (unsigned int i=0; i<sizeof(encoded_field_test_case)/sizeof(encoded_field_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + + for (unsigned int j=0; j<sizeof(raw_field_test_case[i])/sizeof(raw_field_test_case[i][0]); j++) { + const char* expected_name = raw_field_test_case[i][j].raw_name; + const char* expected_value = raw_field_test_case[i][j].raw_value; + if (strlen(expected_name) == 0) break; + + MIMEField* field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + mime_field_name_value_set(headers->m_heap, headers->m_http->m_fields_impl, field, -1, + expected_name, strlen(expected_name), expected_value, strlen(expected_value), + true, strlen(expected_name) + strlen(expected_value), 1); + mime_hdr_field_attach(headers->m_http->m_fields_impl, field, 1, NULL); + } + + memset(buf, 0, BUFSIZE_FOR_REGRESSION_TEST); + int len = convert_from_1_1_to_2_header(headers, buf, BUFSIZE_FOR_REGRESSION_TEST, header_table); + + box.check(len == encoded_field_test_case[i].encoded_field_len, "encoded length was %d, expecting %d", + len, encoded_field_test_case[i].encoded_field_len); + box.check(memcmp(buf, encoded_field_test_case[i].encoded_field, len) == 0, "encoded value was invalid"); + } +} + +REGRESSION_TEST(HPACK_DecodeInteger)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + uint32_t actual; + + for (unsigned int i=0; i<sizeof(integer_test_case)/sizeof(integer_test_case[0]); i++) { + int len = decode_integer(actual, integer_test_case[i].encoded_field, + integer_test_case[i].encoded_field + integer_test_case[i].encoded_field_len, + integer_test_case[i].prefix); + + box.check(len == integer_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, integer_test_case[i].encoded_field_len); + box.check(actual == integer_test_case[i].raw_integer, "decoded value was %d, expected %d", + actual, integer_test_case[i].raw_integer); + } +} + +REGRESSION_TEST(HPACK_DecodeString)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + char* actual; + uint32_t actual_len; + + hpack_huffman_init(); + + for (unsigned int i=0; i<sizeof(string_test_case)/sizeof(string_test_case[0]); i++) { + int len = decode_string(&actual, actual_len, string_test_case[i].encoded_field, + string_test_case[i].encoded_field + string_test_case[i].encoded_field_len); + + box.check(len == string_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, string_test_case[i].encoded_field_len); + box.check(actual_len == string_test_case[i].raw_string_len, "length of decoded string was %d, expecting %d", + actual_len, string_test_case[i].raw_string_len); + box.check(memcmp(actual, string_test_case[i].raw_string, actual_len) == 0, "decoded string was invalid"); + + ats_free(actual); + } +} + +REGRESSION_TEST(HPACK_DecodeIndexedHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Http2HeaderTable header_table; + + for (unsigned int i=0; i<sizeof(indexed_test_case)/sizeof(indexed_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + MIMEField *field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + MIMEFieldWrapper header(field, headers->m_heap, headers->m_http->m_fields_impl); + + int len = decode_indexed_header_field(header, indexed_test_case[i].encoded_field, + indexed_test_case[i].encoded_field+indexed_test_case[i].encoded_field_len, header_table); + + box.check(len == indexed_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, indexed_test_case[i].encoded_field_len); + + int name_len; + const char* name = header.name_get(&name_len); + box.check(memcmp(name, indexed_test_case[i].raw_name, name_len) == 0, + "decoded header name was invalid"); + + int actual_value_len; + const char* actual_value = header.value_get(&actual_value_len); + box.check(memcmp(actual_value, indexed_test_case[i].raw_value, actual_value_len) == 0, + "decoded header value was invalid"); + } +} + +REGRESSION_TEST(HPACK_DecodeLiteralHeaderField)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Http2HeaderTable header_table; + + for (unsigned int i=0; i<sizeof(literal_test_case)/sizeof(literal_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + MIMEField *field = mime_field_create(headers->m_heap, headers->m_http->m_fields_impl); + MIMEFieldWrapper header(field, headers->m_heap, headers->m_http->m_fields_impl); + + int len = decode_literal_header_field(header, literal_test_case[i].encoded_field, + literal_test_case[i].encoded_field+literal_test_case[i].encoded_field_len, header_table); + + box.check(len == literal_test_case[i].encoded_field_len, "decoded length was %d, expecting %d", + len, literal_test_case[i].encoded_field_len); + + int name_len; + const char* name = header.name_get(&name_len); + box.check(memcmp(name, literal_test_case[i].raw_name, name_len) == 0, + "decoded header name was invalid"); + + int actual_value_len; + const char* actual_value = header.value_get(&actual_value_len); + box.check(memcmp(actual_value, literal_test_case[i].raw_value, actual_value_len) == 0, + "decoded header value was invalid"); + } +} + +REGRESSION_TEST(HPACK_Decode)(RegressionTest * t, int, int *pstatus) +{ + TestBox box(t, pstatus); + box = REGRESSION_TEST_PASSED; + + Http2HeaderTable header_table; + + for (unsigned int i=0; i<sizeof(encoded_field_test_case)/sizeof(encoded_field_test_case[0]); i++) { + HTTPHdr* headers = new HTTPHdr(); + headers->create(HTTP_TYPE_REQUEST); + + http2_parse_header_fragment(headers, make_iovec(encoded_field_test_case[i].encoded_field, encoded_field_test_case[i].encoded_field_len), header_table); + + for (unsigned int j=0; j<sizeof(raw_field_test_case[i])/sizeof(raw_field_test_case[i][0]); j++) { + const char* expected_name = raw_field_test_case[i][j].raw_name; + const char* expected_value = raw_field_test_case[i][j].raw_value; + if (strlen(expected_name) == 0) break; + + MIMEField* field = headers->field_find(expected_name, strlen(expected_name)); + box.check(field != NULL, "A MIMEField that has \"%s\" as name doesn't exist", expected_name); + + int actual_value_len; + const char* actual_value = field->value_get(&actual_value_len); + box.check(strncmp(expected_value, actual_value, actual_value_len) == 0, "A MIMEField that has \"%s\" as value doesn't exist", expected_value); + } + } +} + +#endif /* TS_HAS_TESTS */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/fa6c830f/proxy/http2/HTTP2.h ---------------------------------------------------------------------- diff --git a/proxy/http2/HTTP2.h b/proxy/http2/HTTP2.h index 306d69d..d43028c 100644 --- a/proxy/http2/HTTP2.h +++ b/proxy/http2/HTTP2.h @@ -26,6 +26,10 @@ #include "ink_defs.h" #include "ink_memory.h" +#include "HPACK.h" +#include "MIME.h" + +class HTTPHdr; typedef unsigned Http2StreamId; @@ -250,4 +254,13 @@ http2_settings_parameter_is_valid(const Http2SettingsParameter&); bool http2_parse_settings_parameter(IOVec, Http2SettingsParameter&); +MIMEParseResult +http2_parse_header_fragment(HTTPHdr *, IOVec, Http2HeaderTable&); + +MIMEParseResult +convert_from_2_to_1_1_header(HTTPHdr * header); + +int64_t +convert_from_1_1_to_2_header(HTTPHdr * in, uint8_t * out, uint64_t out_len, Http2HeaderTable& header_table); + #endif /* __HTTP2_H__ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/fa6c830f/proxy/http2/HuffmanCodec.cc ---------------------------------------------------------------------- diff --git a/proxy/http2/HuffmanCodec.cc b/proxy/http2/HuffmanCodec.cc new file mode 100644 index 0000000..4dbdfec --- /dev/null +++ b/proxy/http2/HuffmanCodec.cc @@ -0,0 +1,389 @@ +/** @file + + A brief file description + + @section license License + + 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. + */ + +#include "HuffmanCodec.h" +#include "libts.h" + +struct huffman_entry +{ + uint32_t code_as_hex; + uint32_t bit_len; +}; + +static const huffman_entry huffman_table[] = { + {0x1ff8, 13}, + {0x7fffd8, 23}, + {0xfffffe2, 28}, + {0xfffffe3, 28}, + {0xfffffe4, 28}, + {0xfffffe5, 28}, + {0xfffffe6, 28}, + {0xfffffe7, 28}, + {0xfffffe8, 28}, + {0xffffea, 24}, + {0x3ffffffc, 30}, + {0xfffffe9, 28}, + {0xfffffea, 28}, + {0x3ffffffd, 30}, + {0xfffffeb, 28}, + {0xfffffec, 28}, + {0xfffffed, 28}, + {0xfffffee, 28}, + {0xfffffef, 28}, + {0xffffff0, 28}, + {0xffffff1, 28}, + {0xffffff2, 28}, + {0x3ffffffe, 30}, + {0xffffff3, 28}, + {0xffffff4, 28}, + {0xffffff5, 28}, + {0xffffff6, 28}, + {0xffffff7, 28}, + {0xffffff8, 28}, + {0xffffff9, 28}, + {0xffffffa, 28}, + {0xffffffb, 28}, + {0x14, 6}, + {0x3f8, 10}, + {0x3f9, 10}, + {0xffa, 12}, + {0x1ff9, 13}, + {0x15, 6}, + {0xf8, 8}, + {0x7fa, 11}, + {0x3fa, 10}, + {0x3fb, 10}, + {0xf9, 8}, + {0x7fb, 11}, + {0xfa, 8}, + {0x16, 6}, + {0x17, 6}, + {0x18, 6}, + {0x0, 5}, + {0x1, 5}, + {0x2, 5}, + {0x19, 6}, + {0x1a, 6}, + {0x1b, 6}, + {0x1c, 6}, + {0x1d, 6}, + {0x1e, 6}, + {0x1f, 6}, + {0x5c, 7}, + {0xfb, 8}, + {0x7ffc, 15}, + {0x20, 6}, + {0xffb, 12}, + {0x3fc, 10}, + {0x1ffa, 13}, + {0x21, 6}, + {0x5d, 7}, + {0x5e, 7}, + {0x5f, 7}, + {0x60, 7}, + {0x61, 7}, + {0x62, 7}, + {0x63, 7}, + {0x64, 7}, + {0x65, 7}, + {0x66, 7}, + {0x67, 7}, + {0x68, 7}, + {0x69, 7}, + {0x6a, 7}, + {0x6b, 7}, + {0x6c, 7}, + {0x6d, 7}, + {0x6e, 7}, + {0x6f, 7}, + {0x70, 7}, + {0x71, 7}, + {0x72, 7}, + {0xfc, 8}, + {0x73, 7}, + {0xfd, 8}, + {0x1ffb, 13}, + {0x7fff0, 19}, + {0x1ffc, 13}, + {0x3ffc, 14}, + {0x22, 6}, + {0x7ffd, 15}, + {0x3, 5}, + {0x23, 6}, + {0x4, 5}, + {0x24, 6}, + {0x5, 5}, + {0x25, 6}, + {0x26, 6}, + {0x27, 6}, + {0x6, 5}, + {0x74, 7}, + {0x75, 7}, + {0x28, 6}, + {0x29, 6}, + {0x2a, 6}, + {0x7, 5}, + {0x2b, 6}, + {0x76, 7}, + {0x2c, 6}, + {0x8, 5}, + {0x9, 5}, + {0x2d, 6}, + {0x77, 7}, + {0x78, 7}, + {0x79, 7}, + {0x7a, 7}, + {0x7b, 7}, + {0x7ffe, 15}, + {0x7fc, 11}, + {0x3ffd, 14}, + {0x1ffd, 13}, + {0xffffffc, 28}, + {0xfffe6, 20}, + {0x3fffd2, 22}, + {0xfffe7, 20}, + {0xfffe8, 20}, + {0x3fffd3, 22}, + {0x3fffd4, 22}, + {0x3fffd5, 22}, + {0x7fffd9, 23}, + {0x3fffd6, 22}, + {0x7fffda, 23}, + {0x7fffdb, 23}, + {0x7fffdc, 23}, + {0x7fffdd, 23}, + {0x7fffde, 23}, + {0xffffeb, 23}, + {0x7fffdf, 23}, + {0xffffec, 24}, + {0xffffed, 24}, + {0x3fffd7, 22}, + {0x7fffe0, 23}, + {0xffffee, 24}, + {0x7fffe1, 23}, + {0x7fffe2, 23}, + {0x7fffe3, 23}, + {0x7fffe4, 23}, + {0x1fffdc, 21}, + {0x3fffd8, 22}, + {0x7fffe5, 23}, + {0x3fffd9, 22}, + {0x7fffe6, 23}, + {0x7fffe7, 23}, + {0xffffef, 24}, + {0x3fffda, 22}, + {0x1fffdd, 21}, + {0xfffe9, 20}, + {0x3fffdb, 22}, + {0x3fffdc, 22}, + {0x7fffe8, 23}, + {0x7fffe9, 23}, + {0x1fffde, 21}, + {0x7fffde, 23}, + {0x3fffdd, 22}, + {0x3fffde, 22}, + {0xfffff0, 24}, + {0x1fffdf, 21}, + {0x3fffdf, 22}, + {0x7fffeb, 23}, + {0x7fffec, 23}, + {0x1fffe0, 21}, + {0x1fffe1, 21}, + {0x3fffe0, 22}, + {0x1fffe2, 21}, + {0x7fffed, 23}, + {0x3fffe1, 22}, + {0x7fffee, 23}, + {0x7fffef, 23}, + {0xfffea, 20}, + {0x3fffe2, 22}, + {0x3fffe3, 22}, + {0x3fffe4, 22}, + {0x7ffff0, 23}, + {0x3fffe5, 22}, + {0x3fffe6, 22}, + {0x7ffff1, 23}, + {0x3ffffe0, 26}, + {0x3ffffe1, 26}, + {0xfffeb, 20}, + {0x7fff1, 19}, + {0x3fffe7, 22}, + {0x7ffff2, 23}, + {0x3fffe8, 22}, + {0x1ffffec, 25}, + {0x3ffffe2, 26}, + {0x3ffffe3, 26}, + {0x3ffffe4, 26}, + {0x7ffffde, 27}, + {0x7ffffdf, 27}, + {0x3ffffe5, 26}, + {0xfffff1, 24}, + {0x1ffffed, 25}, + {0x7fff2, 19}, + {0x1fffe3, 21}, + {0x3ffffe6, 26}, + {0x7ffffe0, 27}, + {0x7ffffe1, 27}, + {0x3ffffe7, 26}, + {0x3ffffe2, 27}, + {0xfffff2, 24}, + {0x1fffe4, 21}, + {0x1fffe5, 21}, + {0x3ffffe8, 26}, + {0x3ffffe9, 26}, + {0xffffffd, 28}, + {0x7ffffe3, 27}, + {0x7ffffe4, 27}, + {0x7ffffe5, 27}, + {0xfffec, 20}, + {0xfffff3, 24}, + {0xfffed, 20}, + {0x1fffe6, 21}, + {0x3fffe9, 22}, + {0x1fffe7, 21}, + {0x1fffe8, 21}, + {0x7ffff3, 23}, + {0x3fffea, 22}, + {0x3fffeb, 22}, + {0x1ffffee, 25}, + {0x1ffffef, 25}, + {0xfffff4, 24}, + {0xfffff5, 24}, + {0x3ffffea, 26}, + {0x7ffff4, 23}, + {0x3ffffeb, 26}, + {0x7ffffe6, 27}, + {0x3ffffec, 26}, + {0x3ffffed, 26}, + {0x7ffffe7, 27}, + {0x7ffffe8, 27}, + {0x7ffffe9, 27}, + {0x7ffffea, 27}, + {0x7ffffeb, 27}, + {0xffffffe, 28}, + {0x7ffffec, 27}, + {0x7ffffed, 27}, + {0x7ffffee, 27}, + {0x7ffffef, 27}, + {0x7fffff0, 27}, + {0x3ffffee, 26}, + {0x3fffffff, 30} +}; + +typedef struct node { + node *left, *right; + char ascii_code; +} Node; + +Node* HUFFMAN_TREE_ROOT; + +static Node* +make_huffman_tree_node() +{ + Node *n = static_cast<Node *>(ats_malloc(sizeof(Node))); + n->left = NULL; + n->right = NULL; + n->ascii_code = '\0'; + return n; +} + +static Node* +make_huffman_tree() +{ + Node* root = make_huffman_tree_node(); + Node* current; + uint32_t bit_len; + // insert leafs for each ascii code + for (unsigned i = 0; i < countof(huffman_table); i++){ + bit_len = huffman_table[i].bit_len; + current = root; + while (bit_len > 0){ + if (huffman_table[i].code_as_hex & (1 << (bit_len-1))) { + if (!current->right) + current->right = make_huffman_tree_node(); + current = current->right; + } else { + if (!current->left) + current->left = make_huffman_tree_node(); + current = current->left; + } + bit_len--; + } + current->ascii_code = i; + } + return root; +} + +static void +free_huffman_tree(Node* node) +{ + if (node->left) + free_huffman_tree(node->left); + if (node->right) + free_huffman_tree(node->right); + + ats_free(node); +} + +void hpack_huffman_init() +{ + if (!HUFFMAN_TREE_ROOT) + HUFFMAN_TREE_ROOT = make_huffman_tree(); +} + +void hpack_huffman_fin() +{ + if (HUFFMAN_TREE_ROOT) + free_huffman_tree(HUFFMAN_TREE_ROOT); +} + +int64_t +huffman_decode(char* dst_start, const uint8_t* src, uint32_t src_len) +{ + char* dst_end = dst_start; + uint8_t shift = 7; + Node* current = HUFFMAN_TREE_ROOT; + + while (src_len) { + if (*src & (1 << shift)) { + current = current->right; + } else { + current = current->left; + } + + if (current->ascii_code) { + *dst_end = current->ascii_code; + ++dst_end; + current = HUFFMAN_TREE_ROOT; + } + if (shift) { + --shift; + } else { + shift = 7; + ++src; + --src_len; + } + } + + return dst_end - dst_start; +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/fa6c830f/proxy/http2/HuffmanCodec.h ---------------------------------------------------------------------- diff --git a/proxy/http2/HuffmanCodec.h b/proxy/http2/HuffmanCodec.h new file mode 100644 index 0000000..0037a72 --- /dev/null +++ b/proxy/http2/HuffmanCodec.h @@ -0,0 +1,34 @@ +/** @file + + A brief file description + + @section license License + + 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. + */ + +#ifndef __HPACK_HUFFMAN_H__ +#define __HPACK_HUFFMAN_H__ + +#include <stddef.h> +#include <stdint.h> + +void hpack_huffman_init(); +void hpack_huffman_fin(); +int64_t huffman_decode(char* dst_start, const uint8_t* src, uint32_t src_len); + +#endif /* __HPACK_Huffman_H__ */ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/fa6c830f/proxy/http2/Makefile.am ---------------------------------------------------------------------- diff --git a/proxy/http2/Makefile.am b/proxy/http2/Makefile.am index 6207bd9..177d9e6 100644 --- a/proxy/http2/Makefile.am +++ b/proxy/http2/Makefile.am @@ -34,7 +34,15 @@ AM_CPPFLAGS = \ noinst_LIBRARIES = libhttp2.a libhttp2_a_SOURCES = \ + HPACK.cc \ + HPACK.h \ HTTP2.cc \ + HTTP2.h \ Http2ClientSession.cc \ + Http2ClientSession.h \ Http2ConnectionState.cc \ - Http2SessionAccept.cc + Http2ConnectionState.h \ + Http2SessionAccept.cc \ + Http2SessionAccept.h \ + HuffmanCodec.cc \ + HuffmanCodec.h
