[PATCH] HTTP/2: HPACK Huffman encoding
Vlad Krasnov
vlad at cloudflare.com
Wed Jan 20 22:01:15 UTC 2016
LGTM
Cheers,
Vlad
> On 19 Jan 2016, at 09:20, Valentin V. Bartenev <vbart at nginx.com> wrote:
>
> On Thursday 17 December 2015 03:49:32 Vlad Krasnov wrote:
>> # HG changeset patch
>> # User Vlad Krasnov <vlad at cloudflare.com <mailto:vlad at cloudflare.com>>
>> # Date 1450274269 28800
>> # Wed Dec 16 05:57:49 2015 -0800
>> # Node ID d672e9c2b814710986683e050491536355c90f0d
>> # Parent def9c9c9ae05cfa7467b0ec96e76afa180c23dfb
>> HTTP/2: HPACK Huffman encoding
>
> Style. The dot at the end of summary line is needed.
>
>>
>> Implement HPACK Huffman encoding for HTTP/2.
>> This reduces the size of headers by over 30% on average.
>
> See the comments below and a reworked patch in attachment.
>
>
>>
>> diff -r def9c9c9ae05 -r d672e9c2b814 src/http/v2/ngx_http_v2.h
>> --- a/src/http/v2/ngx_http_v2.h Sat Dec 12 10:32:58 2015 +0300
>> +++ b/src/http/v2/ngx_http_v2.h Wed Dec 16 05:57:49 2015 -0800
>> @@ -51,6 +51,9 @@
>> #define NGX_HTTP_V2_PRIORITY_FLAG 0x20
>>
>>
>> +#define NGX_HTTP_V2_ENCODE_RAW 0
>> +#define NGX_HTTP_V2_ENCODE_HUFF 0x80
>> +
>> typedef struct ngx_http_v2_connection_s ngx_http_v2_connection_t;
>> typedef struct ngx_http_v2_node_s ngx_http_v2_node_t;
>> typedef struct ngx_http_v2_out_frame_s ngx_http_v2_out_frame_t;
>> @@ -255,6 +258,28 @@
>> }
>>
>>
>> +static ngx_inline u_char *
>> +ngx_http_v2_write_int(u_char *pos, ngx_uint_t prefix, ngx_uint_t value)
>> +{
>> + if (value < prefix) {
>> + *pos++ |= value;
>> + return pos;
>> + }
>> +
>> + *pos++ |= prefix;
>> + value -= prefix;
>> +
>> + while (value >= 128) {
>> + *pos++ = value % 128 + 128;
>> + value /= 128;
>> + }
>> +
>> + *pos++ = (u_char) value;
>> +
>> + return pos;
>> +}
>> +
>> +
>> void ngx_http_v2_init(ngx_event_t *rev);
>> void ngx_http_v2_request_headers_init(void);
>>
> [..]
>
> It's better to put ngx_http_v2_string_encode() into the
> "ngx_http_v2_filter_module.c", than moving all these to
> the header file.
>
> Also that will be more consistent and symmetric with the
> "ngx_http_v2_huff_decode.c".
>
>
>
>> @@ -275,7 +300,8 @@
>>
>> ngx_int_t ngx_http_v2_huff_decode(u_char *state, u_char *src, size_t len,
>> u_char **dst, ngx_uint_t last, ngx_log_t *log);
>> -
>> +u_char *ngx_http_v2_string_encode(u_char *src, size_t len, u_char *dst,
>> + u_char *tmp, ngx_log_t *log, ngx_flag_t lower);
>>
>> #define ngx_http_v2_prefix(bits) ((1 << (bits)) - 1)
>>
>> diff -r def9c9c9ae05 -r d672e9c2b814 src/http/v2/ngx_http_v2_filter_module.c
>> --- a/src/http/v2/ngx_http_v2_filter_module.c Sat Dec 12 10:32:58 2015 +0300
>> +++ b/src/http/v2/ngx_http_v2_filter_module.c Wed Dec 16 05:57:49 2015 -0800
>> @@ -25,9 +25,6 @@
>> #define ngx_http_v2_indexed(i) (128 + (i))
>> #define ngx_http_v2_inc_indexed(i) (64 + (i))
>>
>> -#define NGX_HTTP_V2_ENCODE_RAW 0
>> -#define NGX_HTTP_V2_ENCODE_HUFF 0x80
>> -
>> #define NGX_HTTP_V2_STATUS_INDEX 8
>> #define NGX_HTTP_V2_STATUS_200_INDEX 8
>> #define NGX_HTTP_V2_STATUS_204_INDEX 9
>> @@ -46,8 +43,9 @@
>> #define NGX_HTTP_V2_VARY_INDEX 59
>>
>>
>> -static u_char *ngx_http_v2_write_int(u_char *pos, ngx_uint_t prefix,
>> - ngx_uint_t value);
>> +#define ACCEPT_ENCODING "\x84\x84\x2d\x69\x5b\x05\x44\x3c\x86\xaa\x6f"
>> +
>> +
>
> You should either add NGX_* prefix or define it as a local
> static constant.
>
>
>
>> static ngx_http_v2_out_frame_t *ngx_http_v2_create_headers_frame(
>> ngx_http_request_t *r, u_char *pos, u_char *end);
>>
>> @@ -119,8 +117,8 @@
>> static ngx_int_t
>> ngx_http_v2_header_filter(ngx_http_request_t *r)
>> {
>> - u_char status, *pos, *start, *p;
>> - size_t len;
>> + u_char status, *pos, *start, *p, *huff;
>> + size_t len, hlen, nlen;
>> ngx_str_t host, location;
>> ngx_uint_t i, port;
>> ngx_list_part_t *part;
>> @@ -343,7 +341,7 @@
>> #if (NGX_HTTP_GZIP)
>> if (r->gzip_vary) {
>> if (clcf->gzip_vary) {
>> - len += 1 + ngx_http_v2_literal_size("Accept-Encoding");
>> + len += 1 + ngx_http_v2_literal_size(ACCEPT_ENCODING);
>>
>> } else {
>> r->gzip_vary = 0;
>> @@ -354,6 +352,8 @@
>> part = &r->headers_out.headers.part;
>> header = part->elts;
>>
>> + hlen = len;
>> +
>> for (i = 0; /* void */; i++) {
>>
>> if (i >= part->nelts) {
>> @@ -384,11 +384,14 @@
>> return NGX_ERROR;
>> }
>>
>> - len += 1 + NGX_HTTP_V2_INT_OCTETS + header[i].key.len
>> + nlen = 1 + NGX_HTTP_V2_INT_OCTETS + header[i].key.len
>> + NGX_HTTP_V2_INT_OCTETS + header[i].value.len;
>> + len += nlen;
>> + hlen = nlen > hlen ? nlen : hlen;
>
> I don't understand why you are comparing hlen with the sum of
> header name and value including the type byte.
>
> Headers names and values are encoded separately.
>
>
>> }
>>
>> pos = ngx_palloc(r->pool, len);
>> + huff = ngx_palloc(r->pool, hlen);
>> if (pos == NULL) {
>> return NGX_ERROR;
>> }
>
> The "huff" can be NULL which will result in segfault.
>
>
>
>> @@ -408,12 +411,15 @@
>> *pos++ = ngx_http_v2_inc_indexed(NGX_HTTP_V2_SERVER_INDEX);
>>
>> if (clcf->server_tokens) {
>> - *pos++ = NGX_HTTP_V2_ENCODE_RAW | (sizeof(NGINX_VER) - 1);
>> - pos = ngx_cpymem(pos, NGINX_VER, sizeof(NGINX_VER) - 1);
>> + pos = ngx_http_v2_string_encode((u_char*)NGINX_VER,
>> + sizeof(NGINX_VER) - 1, pos, huff,
>> + r->connection->log, 0);
>>
>> } else {
>> - *pos++ = NGX_HTTP_V2_ENCODE_RAW | (sizeof("nginx") - 1);
>> - pos = ngx_cpymem(pos, "nginx", sizeof("nginx") - 1);
>> + pos = ngx_http_v2_string_encode((u_char*)"nginx",
>> + sizeof("nginx") - 1, pos, huff,
>> + r->connection->log, 0);
>
> The "nginx" constant can also be preencoded like "Accept-Encoding".
>
>
>> +
>
> Style nit. A surplus empty line.
>
>
>> }
>> }
>>
>> @@ -453,11 +459,9 @@
>> r->headers_out.content_type.data = p;
>>
>> } else {
>
> Why don't you try to encode "Content-Type" in other case,
> when the condition is true?
>
> The patch looks also incomplete without the encoding of
> "Date" header (it's simple to implement and quite useful).
>
>
>> - *pos = NGX_HTTP_V2_ENCODE_RAW;
>> - pos = ngx_http_v2_write_int(pos, ngx_http_v2_prefix(7),
>> - r->headers_out.content_type.len);
>> - pos = ngx_cpymem(pos, r->headers_out.content_type.data,
>> - r->headers_out.content_type.len);
>> + pos = ngx_http_v2_string_encode(r->headers_out.content_type.data,
>> + r->headers_out.content_type.len,
>> + pos, huff, r->connection->log, 0);
>> }
>> }
>>
>> @@ -476,26 +480,27 @@
>> {
>> *pos++ = ngx_http_v2_inc_indexed(NGX_HTTP_V2_LAST_MODIFIED_INDEX);
>>
>> - *pos++ = NGX_HTTP_V2_ENCODE_RAW
>> - | (sizeof("Wed, 31 Dec 1986 18:00:00 GMT") - 1);
>> - pos = ngx_http_time(pos, r->headers_out.last_modified_time);
>> + nlen = sizeof("Wed, 31 Dec 1986 18:00:00 GMT") - 1;
>> + ngx_http_time(pos + 1, r->headers_out.last_modified_time);
>> +
>> + pos = ngx_http_v2_string_encode(pos + 1, nlen, pos, huff,
>> + r->connection->log, 0);
>
> "pos + 1" looks wrong here.
>
> Also the safety of using *pos as source and destination requires
> a comment.
>
>
>> }
>>
>> if (r->headers_out.location && r->headers_out.location->value.len) {
>> *pos++ = ngx_http_v2_inc_indexed(NGX_HTTP_V2_LOCATION_INDEX);
>>
>> *pos = NGX_HTTP_V2_ENCODE_RAW;
>
> This assignment after the change below is surplus and misleading.
>
>
>> - pos = ngx_http_v2_write_int(pos, ngx_http_v2_prefix(7),
>> - r->headers_out.location->value.len);
>> - pos = ngx_cpymem(pos, r->headers_out.location->value.data,
>> - r->headers_out.location->value.len);
>> + pos = ngx_http_v2_string_encode(r->headers_out.location->value.data,
>> + r->headers_out.location->value.len,
>> + pos, huff, r->connection->log, 0);
>> }
>>
>> #if (NGX_HTTP_GZIP)
>> if (r->gzip_vary) {
>> *pos++ = ngx_http_v2_inc_indexed(NGX_HTTP_V2_VARY_INDEX);
>> - *pos++ = NGX_HTTP_V2_ENCODE_RAW | (sizeof("Accept-Encoding") - 1);
>> - pos = ngx_cpymem(pos, "Accept-Encoding", sizeof("Accept-Encoding") - 1);
>> + *pos++ = NGX_HTTP_V2_ENCODE_HUFF | (sizeof(ACCEPT_ENCODING) - 1);
>> + pos = ngx_cpymem(pos, ACCEPT_ENCODING, sizeof(ACCEPT_ENCODING) - 1);
>> }
>> #endif
>>
>> @@ -520,16 +525,14 @@
>>
>> *pos++ = 0;
>>
>> - *pos = NGX_HTTP_V2_ENCODE_RAW;
>> - pos = ngx_http_v2_write_int(pos, ngx_http_v2_prefix(7),
>> - header[i].key.len);
>> - ngx_strlow(pos, header[i].key.data, header[i].key.len);
>> - pos += header[i].key.len;
>> + pos = ngx_http_v2_string_encode(header[i].key.data,
>> + header[i].key.len,
>> + pos, huff, r->connection->log, 1);
>>
>> - *pos = NGX_HTTP_V2_ENCODE_RAW;
>> - pos = ngx_http_v2_write_int(pos, ngx_http_v2_prefix(7),
>> - header[i].value.len);
>> - pos = ngx_cpymem(pos, header[i].value.data, header[i].value.len);
>> + pos = ngx_http_v2_string_encode(header[i].value.data,
>> + header[i].value.len,
>> + pos, huff, r->connection->log, 0);
>> +
>> }
>>
>> frame = ngx_http_v2_create_headers_frame(r, start, pos);
>> @@ -556,28 +559,6 @@
>> }
>>
>>
>> -static u_char *
>> -ngx_http_v2_write_int(u_char *pos, ngx_uint_t prefix, ngx_uint_t value)
>> -{
>> - if (value < prefix) {
>> - *pos++ |= value;
>> - return pos;
>> - }
>> -
>> - *pos++ |= prefix;
>> - value -= prefix;
>> -
>> - while (value >= 128) {
>> - *pos++ = value % 128 + 128;
>> - value /= 128;
>> - }
>> -
>> - *pos++ = (u_char) value;
>> -
>> - return pos;
>> -}
>> -
>> -
>> static ngx_http_v2_out_frame_t *
>> ngx_http_v2_create_headers_frame(ngx_http_request_t *r, u_char *pos,
>> u_char *end)
>> diff -r def9c9c9ae05 -r d672e9c2b814 src/http/v2/ngx_http_v2_huff_encode.c
>> --- a/src/http/v2/ngx_http_v2_huff_encode.c Sat Dec 12 10:32:58 2015 +0300
>> +++ b/src/http/v2/ngx_http_v2_huff_encode.c Wed Dec 16 05:57:49 2015 -0800
>> @@ -1,10 +1,296 @@
>>
>> /*
>> * Copyright (C) Nginx, Inc.
>> - * Copyright (C) Valentin V. Bartenev
>> + * Copyright (C) Vlad Krasnov
>> */
>>
>>
>> #include <ngx_config.h>
>> #include <ngx_core.h>
>> #include <ngx_http.h>
>> +#if (__GNUC__)
>> +#include <byteswap.h>
>> +#endif
>
> IMHO from portability point of view it's better to check the presence
> of required builtin than to relate on __GNUC__.
>
>
>> +
>> +
>> +typedef struct {
>> + ngx_uint_t code;
>> + ngx_uint_t len;
>> +} ngx_http_v2_huff_encode_code_t;
>
> It's better to keep compact these tables.
> There are no need in 64 bits integers here.
>
>
>> +
>> +
>> +static ngx_http_v2_huff_encode_code_t ngx_http_v2_huff_encode_codes[256] =
>> +{
>> + {0x00001ff8, 13}, {0x007fffd8, 23}, {0x0fffffe2, 28}, {0x0fffffe3, 28},
>> + {0x0fffffe4, 28}, {0x0fffffe5, 28}, {0x0fffffe6, 28}, {0x0fffffe7, 28},
>> + {0x0fffffe8, 28}, {0x00ffffea, 24}, {0x3ffffffc, 30}, {0x0fffffe9, 28},
>> + {0x0fffffea, 28}, {0x3ffffffd, 30}, {0x0fffffeb, 28}, {0x0fffffec, 28},
>> + {0x0fffffed, 28}, {0x0fffffee, 28}, {0x0fffffef, 28}, {0x0ffffff0, 28},
>> + {0x0ffffff1, 28}, {0x0ffffff2, 28}, {0x3ffffffe, 30}, {0x0ffffff3, 28},
>> + {0x0ffffff4, 28}, {0x0ffffff5, 28}, {0x0ffffff6, 28}, {0x0ffffff7, 28},
>> + {0x0ffffff8, 28}, {0x0ffffff9, 28}, {0x0ffffffa, 28}, {0x0ffffffb, 28},
>> + {0x00000014, 6}, {0x000003f8, 10}, {0x000003f9, 10}, {0x00000ffa, 12},
>> + {0x00001ff9, 13}, {0x00000015, 6}, {0x000000f8, 8}, {0x000007fa, 11},
>> + {0x000003fa, 10}, {0x000003fb, 10}, {0x000000f9, 8}, {0x000007fb, 11},
>> + {0x000000fa, 8}, {0x00000016, 6}, {0x00000017, 6}, {0x00000018, 6},
>> + {0x00000000, 5}, {0x00000001, 5}, {0x00000002, 5}, {0x00000019, 6},
>> + {0x0000001a, 6}, {0x0000001b, 6}, {0x0000001c, 6}, {0x0000001d, 6},
>> + {0x0000001e, 6}, {0x0000001f, 6}, {0x0000005c, 7}, {0x000000fb, 8},
>> + {0x00007ffc, 15}, {0x00000020, 6}, {0x00000ffb, 12}, {0x000003fc, 10},
>> + {0x00001ffa, 13}, {0x00000021, 6}, {0x0000005d, 7}, {0x0000005e, 7},
>> + {0x0000005f, 7}, {0x00000060, 7}, {0x00000061, 7}, {0x00000062, 7},
>> + {0x00000063, 7}, {0x00000064, 7}, {0x00000065, 7}, {0x00000066, 7},
>> + {0x00000067, 7}, {0x00000068, 7}, {0x00000069, 7}, {0x0000006a, 7},
>> + {0x0000006b, 7}, {0x0000006c, 7}, {0x0000006d, 7}, {0x0000006e, 7},
>> + {0x0000006f, 7}, {0x00000070, 7}, {0x00000071, 7}, {0x00000072, 7},
>> + {0x000000fc, 8}, {0x00000073, 7}, {0x000000fd, 8}, {0x00001ffb, 13},
>> + {0x0007fff0, 19}, {0x00001ffc, 13}, {0x00003ffc, 14}, {0x00000022, 6},
>> + {0x00007ffd, 15}, {0x00000003, 5}, {0x00000023, 6}, {0x00000004, 5},
>> + {0x00000024, 6}, {0x00000005, 5}, {0x00000025, 6}, {0x00000026, 6},
>> + {0x00000027, 6}, {0x00000006, 5}, {0x00000074, 7}, {0x00000075, 7},
>> + {0x00000028, 6}, {0x00000029, 6}, {0x0000002a, 6}, {0x00000007, 5},
>> + {0x0000002b, 6}, {0x00000076, 7}, {0x0000002c, 6}, {0x00000008, 5},
>> + {0x00000009, 5}, {0x0000002d, 6}, {0x00000077, 7}, {0x00000078, 7},
>> + {0x00000079, 7}, {0x0000007a, 7}, {0x0000007b, 7}, {0x00007ffe, 15},
>> + {0x000007fc, 11}, {0x00003ffd, 14}, {0x00001ffd, 13}, {0x0ffffffc, 28},
>> + {0x000fffe6, 20}, {0x003fffd2, 22}, {0x000fffe7, 20}, {0x000fffe8, 20},
>> + {0x003fffd3, 22}, {0x003fffd4, 22}, {0x003fffd5, 22}, {0x007fffd9, 23},
>> + {0x003fffd6, 22}, {0x007fffda, 23}, {0x007fffdb, 23}, {0x007fffdc, 23},
>> + {0x007fffdd, 23}, {0x007fffde, 23}, {0x00ffffeb, 24}, {0x007fffdf, 23},
>> + {0x00ffffec, 24}, {0x00ffffed, 24}, {0x003fffd7, 22}, {0x007fffe0, 23},
>> + {0x00ffffee, 24}, {0x007fffe1, 23}, {0x007fffe2, 23}, {0x007fffe3, 23},
>> + {0x007fffe4, 23}, {0x001fffdc, 21}, {0x003fffd8, 22}, {0x007fffe5, 23},
>> + {0x003fffd9, 22}, {0x007fffe6, 23}, {0x007fffe7, 23}, {0x00ffffef, 24},
>> + {0x003fffda, 22}, {0x001fffdd, 21}, {0x000fffe9, 20}, {0x003fffdb, 22},
>> + {0x003fffdc, 22}, {0x007fffe8, 23}, {0x007fffe9, 23}, {0x001fffde, 21},
>> + {0x007fffea, 23}, {0x003fffdd, 22}, {0x003fffde, 22}, {0x00fffff0, 24},
>> + {0x001fffdf, 21}, {0x003fffdf, 22}, {0x007fffeb, 23}, {0x007fffec, 23},
>> + {0x001fffe0, 21}, {0x001fffe1, 21}, {0x003fffe0, 22}, {0x001fffe2, 21},
>> + {0x007fffed, 23}, {0x003fffe1, 22}, {0x007fffee, 23}, {0x007fffef, 23},
>> + {0x000fffea, 20}, {0x003fffe2, 22}, {0x003fffe3, 22}, {0x003fffe4, 22},
>> + {0x007ffff0, 23}, {0x003fffe5, 22}, {0x003fffe6, 22}, {0x007ffff1, 23},
>> + {0x03ffffe0, 26}, {0x03ffffe1, 26}, {0x000fffeb, 20}, {0x0007fff1, 19},
>> + {0x003fffe7, 22}, {0x007ffff2, 23}, {0x003fffe8, 22}, {0x01ffffec, 25},
>> + {0x03ffffe2, 26}, {0x03ffffe3, 26}, {0x03ffffe4, 26}, {0x07ffffde, 27},
>> + {0x07ffffdf, 27}, {0x03ffffe5, 26}, {0x00fffff1, 24}, {0x01ffffed, 25},
>> + {0x0007fff2, 19}, {0x001fffe3, 21}, {0x03ffffe6, 26}, {0x07ffffe0, 27},
>> + {0x07ffffe1, 27}, {0x03ffffe7, 26}, {0x07ffffe2, 27}, {0x00fffff2, 24},
>> + {0x001fffe4, 21}, {0x001fffe5, 21}, {0x03ffffe8, 26}, {0x03ffffe9, 26},
>> + {0x0ffffffd, 28}, {0x07ffffe3, 27}, {0x07ffffe4, 27}, {0x07ffffe5, 27},
>> + {0x000fffec, 20}, {0x00fffff3, 24}, {0x000fffed, 20}, {0x001fffe6, 21},
>> + {0x003fffe9, 22}, {0x001fffe7, 21}, {0x001fffe8, 21}, {0x007ffff3, 23},
>> + {0x003fffea, 22}, {0x003fffeb, 22}, {0x01ffffee, 25}, {0x01ffffef, 25},
>> + {0x00fffff4, 24}, {0x00fffff5, 24}, {0x03ffffea, 26}, {0x007ffff4, 23},
>> + {0x03ffffeb, 26}, {0x07ffffe6, 27}, {0x03ffffec, 26}, {0x03ffffed, 26},
>> + {0x07ffffe7, 27}, {0x07ffffe8, 27}, {0x07ffffe9, 27}, {0x07ffffea, 27},
>> + {0x07ffffeb, 27}, {0x0ffffffe, 28}, {0x07ffffec, 27}, {0x07ffffed, 27},
>> + {0x07ffffee, 27}, {0x07ffffef, 27}, {0x07fffff0, 27}, {0x03ffffee, 26}
>> +};
>> +
>> +
>> +/* Same as above, but embedes to lower case transformations */
>
> Style nit: either add dot at the end of sentence or lowercase the first letter.
>
> Also grammar: s/embedes/embeds/
>
>
>> +static ngx_http_v2_huff_encode_code_t ngx_http_v2_huff_encode_codes_low[256] =
>> +{
>> + {0x00001ff8, 13}, {0x007fffd8, 23}, {0x0fffffe2, 28}, {0x0fffffe3, 28},
>> + {0x0fffffe4, 28}, {0x0fffffe5, 28}, {0x0fffffe6, 28}, {0x0fffffe7, 28},
>> + {0x0fffffe8, 28}, {0x00ffffea, 24}, {0x3ffffffc, 30}, {0x0fffffe9, 28},
>> + {0x0fffffea, 28}, {0x3ffffffd, 30}, {0x0fffffeb, 28}, {0x0fffffec, 28},
>> + {0x0fffffed, 28}, {0x0fffffee, 28}, {0x0fffffef, 28}, {0x0ffffff0, 28},
>> + {0x0ffffff1, 28}, {0x0ffffff2, 28}, {0x3ffffffe, 30}, {0x0ffffff3, 28},
>> + {0x0ffffff4, 28}, {0x0ffffff5, 28}, {0x0ffffff6, 28}, {0x0ffffff7, 28},
>> + {0x0ffffff8, 28}, {0x0ffffff9, 28}, {0x0ffffffa, 28}, {0x0ffffffb, 28},
>> + {0x00000014, 6}, {0x000003f8, 10}, {0x000003f9, 10}, {0x00000ffa, 12},
>> + {0x00001ff9, 13}, {0x00000015, 6}, {0x000000f8, 8}, {0x000007fa, 11},
>> + {0x000003fa, 10}, {0x000003fb, 10}, {0x000000f9, 8}, {0x000007fb, 11},
>> + {0x000000fa, 8}, {0x00000016, 6}, {0x00000017, 6}, {0x00000018, 6},
>> + {0x00000000, 5}, {0x00000001, 5}, {0x00000002, 5}, {0x00000019, 6},
>> + {0x0000001a, 6}, {0x0000001b, 6}, {0x0000001c, 6}, {0x0000001d, 6},
>> + {0x0000001e, 6}, {0x0000001f, 6}, {0x0000005c, 7}, {0x000000fb, 8},
>> + {0x00007ffc, 15}, {0x00000020, 6}, {0x00000ffb, 12}, {0x000003fc, 10},
>> + {0x00001ffa, 13}, {0x00000003, 5}, {0x00000023, 6}, {0x00000004, 5},
>> + {0x00000024, 6}, {0x00000005, 5}, {0x00000025, 6}, {0x00000026, 6},
>> + {0x00000027, 6}, {0x00000006, 5}, {0x00000074, 7}, {0x00000075, 7},
>> + {0x00000028, 6}, {0x00000029, 6}, {0x0000002a, 6}, {0x00000007, 5},
>> + {0x0000002b, 6}, {0x00000076, 7}, {0x0000002c, 6}, {0x00000008, 5},
>> + {0x00000009, 5}, {0x0000002d, 6}, {0x00000077, 7}, {0x00000078, 7},
>> + {0x00000079, 7}, {0x0000007a, 7}, {0x0000007b, 7}, {0x00001ffb, 13},
>> + {0x0007fff0, 19}, {0x00001ffc, 13}, {0x00003ffc, 14}, {0x00000022, 6},
>> + {0x00007ffd, 15}, {0x00000003, 5}, {0x00000023, 6}, {0x00000004, 5},
>> + {0x00000024, 6}, {0x00000005, 5}, {0x00000025, 6}, {0x00000026, 6},
>> + {0x00000027, 6}, {0x00000006, 5}, {0x00000074, 7}, {0x00000075, 7},
>> + {0x00000028, 6}, {0x00000029, 6}, {0x0000002a, 6}, {0x00000007, 5},
>> + {0x0000002b, 6}, {0x00000076, 7}, {0x0000002c, 6}, {0x00000008, 5},
>> + {0x00000009, 5}, {0x0000002d, 6}, {0x00000077, 7}, {0x00000078, 7},
>> + {0x00000079, 7}, {0x0000007a, 7}, {0x0000007b, 7}, {0x00007ffe, 15},
>> + {0x000007fc, 11}, {0x00003ffd, 14}, {0x00001ffd, 13}, {0x0ffffffc, 28},
>> + {0x000fffe6, 20}, {0x003fffd2, 22}, {0x000fffe7, 20}, {0x000fffe8, 20},
>> + {0x003fffd3, 22}, {0x003fffd4, 22}, {0x003fffd5, 22}, {0x007fffd9, 23},
>> + {0x003fffd6, 22}, {0x007fffda, 23}, {0x007fffdb, 23}, {0x007fffdc, 23},
>> + {0x007fffdd, 23}, {0x007fffde, 23}, {0x00ffffeb, 24}, {0x007fffdf, 23},
>> + {0x00ffffec, 24}, {0x00ffffed, 24}, {0x003fffd7, 22}, {0x007fffe0, 23},
>> + {0x00ffffee, 24}, {0x007fffe1, 23}, {0x007fffe2, 23}, {0x007fffe3, 23},
>> + {0x007fffe4, 23}, {0x001fffdc, 21}, {0x003fffd8, 22}, {0x007fffe5, 23},
>> + {0x003fffd9, 22}, {0x007fffe6, 23}, {0x007fffe7, 23}, {0x00ffffef, 24},
>> + {0x003fffda, 22}, {0x001fffdd, 21}, {0x000fffe9, 20}, {0x003fffdb, 22},
>> + {0x003fffdc, 22}, {0x007fffe8, 23}, {0x007fffe9, 23}, {0x001fffde, 21},
>> + {0x007fffea, 23}, {0x003fffdd, 22}, {0x003fffde, 22}, {0x00fffff0, 24},
>> + {0x001fffdf, 21}, {0x003fffdf, 22}, {0x007fffeb, 23}, {0x007fffec, 23},
>> + {0x001fffe0, 21}, {0x001fffe1, 21}, {0x003fffe0, 22}, {0x001fffe2, 21},
>> + {0x007fffed, 23}, {0x003fffe1, 22}, {0x007fffee, 23}, {0x007fffef, 23},
>> + {0x000fffea, 20}, {0x003fffe2, 22}, {0x003fffe3, 22}, {0x003fffe4, 22},
>> + {0x007ffff0, 23}, {0x003fffe5, 22}, {0x003fffe6, 22}, {0x007ffff1, 23},
>> + {0x03ffffe0, 26}, {0x03ffffe1, 26}, {0x000fffeb, 20}, {0x0007fff1, 19},
>> + {0x003fffe7, 22}, {0x007ffff2, 23}, {0x003fffe8, 22}, {0x01ffffec, 25},
>> + {0x03ffffe2, 26}, {0x03ffffe3, 26}, {0x03ffffe4, 26}, {0x07ffffde, 27},
>> + {0x07ffffdf, 27}, {0x03ffffe5, 26}, {0x00fffff1, 24}, {0x01ffffed, 25},
>> + {0x0007fff2, 19}, {0x001fffe3, 21}, {0x03ffffe6, 26}, {0x07ffffe0, 27},
>> + {0x07ffffe1, 27}, {0x03ffffe7, 26}, {0x07ffffe2, 27}, {0x00fffff2, 24},
>> + {0x001fffe4, 21}, {0x001fffe5, 21}, {0x03ffffe8, 26}, {0x03ffffe9, 26},
>> + {0x0ffffffd, 28}, {0x07ffffe3, 27}, {0x07ffffe4, 27}, {0x07ffffe5, 27},
>> + {0x000fffec, 20}, {0x00fffff3, 24}, {0x000fffed, 20}, {0x001fffe6, 21},
>> + {0x003fffe9, 22}, {0x001fffe7, 21}, {0x001fffe8, 21}, {0x007ffff3, 23},
>> + {0x003fffea, 22}, {0x003fffeb, 22}, {0x01ffffee, 25}, {0x01ffffef, 25},
>> + {0x00fffff4, 24}, {0x00fffff5, 24}, {0x03ffffea, 26}, {0x007ffff4, 23},
>> + {0x03ffffeb, 26}, {0x07ffffe6, 27}, {0x03ffffec, 26}, {0x03ffffed, 26},
>> + {0x07ffffe7, 27}, {0x07ffffe8, 27}, {0x07ffffe9, 27}, {0x07ffffea, 27},
>> + {0x07ffffeb, 27}, {0x0ffffffe, 28}, {0x07ffffec, 27}, {0x07ffffed, 27},
>> + {0x07ffffee, 27}, {0x07ffffef, 27}, {0x07fffff0, 27}, {0x03ffffee, 26}
>> +};
>> +
>> +
>> +#if (NGX_HAVE_LITTLE_ENDIAN)
>> +#if (__GNUC__)
>> +
>> +static void
>> +put64(u_char *dst, uint64_t val)
>
> Please use ngx_* prefix.
>
>
>> +{
>> + *(uint64_t*)dst = __bswap_64(val);
>> +}
>> +
>> +#else /* !__GNUC__ */
>> +
>> +static void
>> +put64(u_char *dst, uint64_t val)
>> +{
>> + dst[0] = val >> 56;
>> + dst[1] = val >> 48;
>> + dst[2] = val >> 40;
>> + dst[3] = val >> 32;
>> + dst[4] = val >> 24;
>> + dst[5] = val >> 16;
>> + dst[6] = val >> 8;
>> + dst[7] = val;
>> +}
>> +#endif /* __GNUC__ */
>> +
>> +#else /* !NGX_HAVE_LITTLE_ENDIAN */
>> +
>> +static void
>> +put64(u_char *dst, uint64_t val)
>> +{
>> + *(uint64_t*)dst = val;
>> +}
>> +
>> +#endif
>
> In nginx is common practice to use macros for such simple expressions.
>
>
>> +
>> +
>> +static ngx_int_t
>> +ngx_http_v2_huff_encode(u_char *src, size_t len, u_char *dst, ngx_log_t *log,
>> + ngx_flag_t lower)
>> +{
>> + ngx_uint_t inp, outp;
>> + ngx_int_t pending;
>> + uint64_t buf;
>
> IMHO it's better to accumulate up to 32-bits on 32 bits platforms.
>
>
>> + ngx_http_v2_huff_encode_code_t next;
>> + ngx_http_v2_huff_encode_code_t *table;
>
> Style nit.
>
> In general, the order of variable declarations need to be arranged by
> the length of their types.
>
> Alignment rule here: two spaces between the longest type and asterisk
> or (if no asterisk) the first letter of the name.
>
> I've also changed the names of local variables to be more inline with
> what usually are used in nginx for similar tasks.
>
>
>> +
>> + if (!lower) {
>> + table = ngx_http_v2_huff_encode_codes;
>> +
>> + } else {
>> + table = ngx_http_v2_huff_encode_codes_low;
>> + }
>
> It's a good case for ternary operator.
>
>
>> +
>> + inp = 0;
>> + outp = 0;
>> + pending = 0;
>> + buf = 0;
>> +
>> + while (inp < len) {
>
> Effectively it's "for (inp = 0; inp < len; inp++)".
>
>
>> + next = table[src[inp]];
>> + /* Accumulate 64 bits */
>> + if ((next.len + pending) < 64) {
>
> Effectively it's "next.len < 64 - pending"
>
>
>> + buf ^= (uint64_t)next.code << (64 - pending - next.len);
>> + pending += next.len;
>> +
>> + } else {
>> + /* If compressed result is longer than source, no point in using it */
>> + if ((outp + 8) >= len) {
>> + return NGX_ERROR;
>> + }
>> +
>> + buf ^= (uint64_t)next.code >> (next.len - (64 - pending));
>> + put64(&dst[outp], buf);
>> + outp += 8;
>> + pending = (next.len - (64 - pending));
>
> Up to this point you have 4 equal cases of "64 - pending".
>
>
>> +
>> + if (pending) {
>> + buf = (uint64_t)next.code << (64 - pending);
>> +
>> + } else {
>> + buf = 0;
>> + }
>
> Another good case for ternary.
>
>
>> + }
>> +
>> + inp++;
>> + }
>> +
>> + buf ^= 0xffffffffffffffffUL >> pending;
>> +
>> + while (pending > 0) {
>> + dst[outp] = buf >> 56;
>> + buf <<= 8;
>> + pending -= 8;
>> + outp++;
>> +
>> + if (outp >= len) {
>> + return NGX_ERROR;
>> + }
>
> It's better to move the check out of the cycle.
>
>
>> + }
>> +
>> + ngx_log_debug2(NGX_LOG_DEBUG_HTTP, log, 0,
>> + "http2 huffman encoding successful; "
>> + "input len: %d, output len %d", len, outp);
>
> IMHO the debug is surplus here.
>
> This message is the only consumer for the log pointer.
>
>
>> +
>> + return outp;
>> +}
>> +
>> +
>> +u_char *
>> +ngx_http_v2_string_encode(u_char *src, size_t len, u_char *dst, u_char *tmp,
>> + ngx_log_t *log, ngx_flag_t lower)
>> +{
>> + ngx_int_t hlen;
>
> Style nit: two spaces between type and name.
>
>
>> +
> ^^^^
> Style nit: spaces at the beginning of the empty line.
>
>
>> + hlen = ngx_http_v2_huff_encode(src, len, tmp, log, lower);
>> +
>> + if (hlen != NGX_ERROR) {
>> + *dst = NGX_HTTP_V2_ENCODE_HUFF;
>> + dst = ngx_http_v2_write_int(dst, ngx_http_v2_prefix(7), hlen);
>> + dst = ngx_cpymem(dst, tmp, hlen);
>> +
>> + } else {
>> + *dst = NGX_HTTP_V2_ENCODE_RAW;
>> + dst = ngx_http_v2_write_int(dst, ngx_http_v2_prefix(7), len);
>> +
>> + if (lower) {
>> + ngx_strlow(dst, src, len);
>> + dst += len;
>> +
>> + } else {
>> + dst = ngx_cpymem(dst, src, len);
>> + }
>> + }
>> +
>> + return dst;
>> +}
>>
>
> See the patch in attachment where I reworked the compression
> function to be more 32-bits friendly and fixed all the mentioned
> problems.
>
> wbr, Valentin V. Bartenev
> <http2_huff_encode.patch>_______________________________________________
> nginx-devel mailing list
> nginx-devel at nginx.org <mailto:nginx-devel at nginx.org>
> http://mailman.nginx.org/mailman/listinfo/nginx-devel <http://mailman.nginx.org/mailman/listinfo/nginx-devel>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.nginx.org/pipermail/nginx-devel/attachments/20160120/f7f1f036/attachment.html>
More information about the nginx-devel
mailing list