[PATCH] HTTP/2: HPACK Huffman encoding
Valentin V. Bartenev
vbart at nginx.com
Tue Jan 19 17:20:25 UTC 2016
On Thursday 17 December 2015 03:49:32 Vlad Krasnov wrote:
> # HG changeset patch
> # User Vlad Krasnov <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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: http2_huff_encode.patch
Type: text/x-patch
Size: 25116 bytes
Desc: not available
URL: <http://mailman.nginx.org/pipermail/nginx-devel/attachments/20160119/b70ace6a/attachment.bin>
More information about the nginx-devel
mailing list