On Thursday 17 December 2015 03:49:32 Vlad Krasnov wrote:
> # HG changeset patch
> # User Vlad Krasnov <[email protected]>
> # 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
# HG changeset patch
# User Valentin Bartenev <[email protected]>
# Date 1453223957 -10800
# Tue Jan 19 20:19:17 2016 +0300
# Node ID 0f286286df8a91ce872762f2cf27a7dc17daad0c
# Parent 02abce4764b7c964e7ee6e10b1a7abf1fee95f79
HTTP/2: implemented HPACK Huffman encoding for response headers.
This reduces the size of headers by over 30% on average.
Based on the patch by Vlad Krasnov:
http://mailman.nginx.org/pipermail/nginx-devel/2015-December/007682.html
diff -r 02abce4764b7 -r 0f286286df8a auto/cc/conf
--- a/auto/cc/conf Tue Jan 12 19:19:07 2016 +0300
+++ b/auto/cc/conf Tue Jan 19 20:19:17 2016 +0300
@@ -203,6 +203,16 @@ if [ "$NGX_PLATFORM" != win32 ]; then
. auto/feature
+ ngx_feature="gcc builtin 64 bits byteswap"
+ ngx_feature_name="NGX_HAVE_GCC_BSWAP64"
+ ngx_feature_run=no
+ ngx_feature_incs=
+ ngx_feature_path=
+ ngx_feature_libs=
+ ngx_feature_test="__builtin_bswap64(0)"
+ . auto/feature
+
+
# ngx_feature="inline"
# ngx_feature_name=
# ngx_feature_run=no
diff -r 02abce4764b7 -r 0f286286df8a src/http/v2/ngx_http_v2.h
--- a/src/http/v2/ngx_http_v2.h Tue Jan 12 19:19:07 2016 +0300
+++ b/src/http/v2/ngx_http_v2.h Tue Jan 19 20:19:17 2016 +0300
@@ -275,6 +275,8 @@ ngx_int_t ngx_http_v2_table_size(ngx_htt
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);
+ngx_int_t ngx_http_v2_huff_encode(u_char *src, size_t len, u_char *dst,
+ ngx_uint_t lower);
#define ngx_http_v2_prefix(bits) ((1 << (bits)) - 1)
diff -r 02abce4764b7 -r 0f286286df8a src/http/v2/ngx_http_v2_filter_module.c
--- a/src/http/v2/ngx_http_v2_filter_module.c Tue Jan 12 19:19:07 2016 +0300
+++ b/src/http/v2/ngx_http_v2_filter_module.c Tue Jan 19 20:19:17 2016 +0300
@@ -46,6 +46,8 @@
#define NGX_HTTP_V2_VARY_INDEX 59
+static u_char *ngx_http_v2_string_encode(u_char *src, size_t len, u_char *dst,
+ u_char *tmp, ngx_uint_t lower);
static u_char *ngx_http_v2_write_int(u_char *pos, ngx_uint_t prefix,
ngx_uint_t value);
static ngx_http_v2_out_frame_t *ngx_http_v2_create_headers_frame(
@@ -119,8 +121,8 @@ static ngx_http_output_header_filter_pt
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, *tmp;
+ size_t len, tmp_len;
ngx_str_t host, location;
ngx_uint_t i, port;
ngx_list_part_t *part;
@@ -136,6 +138,11 @@ ngx_http_v2_header_filter(ngx_http_reque
#endif
u_char addr[NGX_SOCKADDR_STRLEN];
+ static const u_char nginx[] = "\xaa\x63\x55\xE7";
+#if (NGX_HTTP_GZIP)
+ static const u_char accept_encoding[] =
+ "\x84\x84\x2d\x69\x5b\x05\x44\x3c\x86\xaa\x6f";
+#endif
if (!r->stream) {
return ngx_http_next_header_filter(r);
@@ -216,7 +223,7 @@ ngx_http_v2_header_filter(ngx_http_reque
if (r->headers_out.server == NULL) {
len += 1 + clcf->server_tokens ? ngx_http_v2_literal_size(NGINX_VER)
- : ngx_http_v2_literal_size("nginx");
+ : ngx_http_v2_literal_size(nginx);
}
if (r->headers_out.date == NULL) {
@@ -343,7 +350,7 @@ ngx_http_v2_header_filter(ngx_http_reque
#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 +361,8 @@ ngx_http_v2_header_filter(ngx_http_reque
part = &r->headers_out.headers.part;
header = part->elts;
+ tmp_len = len;
+
for (i = 0; /* void */; i++) {
if (i >= part->nelts) {
@@ -386,10 +395,20 @@ ngx_http_v2_header_filter(ngx_http_reque
len += 1 + NGX_HTTP_V2_INT_OCTETS + header[i].key.len
+ NGX_HTTP_V2_INT_OCTETS + header[i].value.len;
+
+ if (header[i].key.len > tmp_len) {
+ tmp_len = header[i].key.len;
+ }
+
+ if (header[i].value.len > tmp_len) {
+ tmp_len = header[i].value.len;
+ }
}
pos = ngx_palloc(r->pool, len);
- if (pos == NULL) {
+ tmp = ngx_palloc(r->pool, tmp_len);
+
+ if (pos == NULL || tmp == NULL) {
return NGX_ERROR;
}
@@ -408,21 +427,21 @@ ngx_http_v2_header_filter(ngx_http_reque
*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, tmp,
+ 0);
} else {
- *pos++ = NGX_HTTP_V2_ENCODE_RAW | (sizeof("nginx") - 1);
- pos = ngx_cpymem(pos, "nginx", sizeof("nginx") - 1);
+ *pos++ = NGX_HTTP_V2_ENCODE_HUFF | (sizeof(nginx) - 1);
+ pos = ngx_cpymem(pos, nginx, sizeof(nginx) - 1);
}
}
if (r->headers_out.date == NULL) {
*pos++ = ngx_http_v2_inc_indexed(NGX_HTTP_V2_DATE_INDEX);
- *pos++ = (u_char) ngx_cached_http_time.len;
-
- pos = ngx_cpymem(pos, ngx_cached_http_time.data,
- ngx_cached_http_time.len);
+ pos = ngx_http_v2_string_encode(ngx_cached_http_time.data,
+ ngx_cached_http_time.len,
+ pos, tmp, 0);
}
if (r->headers_out.content_type.len) {
@@ -431,34 +450,29 @@ ngx_http_v2_header_filter(ngx_http_reque
if (r->headers_out.content_type_len == r->headers_out.content_type.len
&& r->headers_out.charset.len)
{
- *pos = NGX_HTTP_V2_ENCODE_RAW;
- pos = ngx_http_v2_write_int(pos, ngx_http_v2_prefix(7),
- r->headers_out.content_type.len
- + sizeof("; charset=") - 1
- + r->headers_out.charset.len);
+ len = r->headers_out.content_type.len + sizeof("; charset=") - 1
+ + r->headers_out.charset.len;
- p = pos;
+ p = ngx_pnalloc(r->pool, len);
+ if (p == NULL) {
+ return NGX_ERROR;
+ }
- pos = ngx_cpymem(pos, r->headers_out.content_type.data,
+ r->headers_out.content_type.len = len;
+ r->headers_out.content_type.data = p;
+
+ p = ngx_cpymem(p, r->headers_out.content_type.data,
r->headers_out.content_type.len);
- pos = ngx_cpymem(pos, "; charset=", sizeof("; charset=") - 1);
+ p = ngx_cpymem(p, "; charset=", sizeof("; charset=") - 1);
- pos = ngx_cpymem(pos, r->headers_out.charset.data,
- r->headers_out.charset.len);
+ ngx_memcpy(p, r->headers_out.charset.data,
+ r->headers_out.charset.len);
+ }
- /* update r->headers_out.content_type for possible logging */
-
- r->headers_out.content_type.len = pos - p;
- r->headers_out.content_type.data = p;
-
- } else {
- *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, tmp, 0);
}
if (r->headers_out.content_length == NULL
@@ -476,26 +490,28 @@ ngx_http_v2_header_filter(ngx_http_reque
{
*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);
+ ngx_http_time(pos, r->headers_out.last_modified_time);
+ len = sizeof("Wed, 31 Dec 1986 18:00:00 GMT") - 1;
+
+ /*
+ * Date will always be encoded using huffman through the temp buffer,
+ * so it's safe here to use *src and *dst pointing to the same address.
+ */
+ pos = ngx_http_v2_string_encode(pos, len, pos, tmp, 0);
}
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;
- 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, tmp, 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 +536,13 @@ ngx_http_v2_header_filter(ngx_http_reque
*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, tmp, 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, tmp, 0);
}
frame = ngx_http_v2_create_headers_frame(r, start, pos);
@@ -557,6 +570,36 @@ ngx_http_v2_header_filter(ngx_http_reque
static u_char *
+ngx_http_v2_string_encode(u_char *src, size_t len, u_char *dst, u_char *tmp,
+ ngx_uint_t lower)
+{
+ ngx_int_t hlen;
+
+ hlen = ngx_http_v2_huff_encode(src, len, tmp, lower);
+
+ if (hlen > 0) {
+ *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;
+}
+
+
+static u_char *
ngx_http_v2_write_int(u_char *pos, ngx_uint_t prefix, ngx_uint_t value)
{
if (value < prefix) {
diff -r 02abce4764b7 -r 0f286286df8a src/http/v2/ngx_http_v2_huff_encode.c
--- a/src/http/v2/ngx_http_v2_huff_encode.c Tue Jan 12 19:19:07 2016 +0300
+++ b/src/http/v2/ngx_http_v2_huff_encode.c Tue Jan 19 20:19:17 2016 +0300
@@ -1,6 +1,7 @@
/*
* Copyright (C) Nginx, Inc.
+ * Copyright (C) Vlad Krasnov
* Copyright (C) Valentin V. Bartenev
*/
@@ -8,3 +9,240 @@
#include <ngx_config.h>
#include <ngx_core.h>
#include <ngx_http.h>
+
+
+typedef struct {
+ uint32_t code;
+ uint32_t len;
+} ngx_http_v2_huff_encode_code_t;
+
+
+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 embeds lowercase transformation */
+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_PTR_SIZE == 8)
+
+#if (NGX_HAVE_LITTLE_ENDIAN)
+
+#if (NGX_HAVE_GCC_BSWAP64)
+#define ngx_http_v2_huff_encode_buf(d, b) \
+ (*(uint64_t *) (d) = __builtin_bswap64(b))
+#else
+#define ngx_http_v2_huff_encode_buf(d, b) \
+ ((d)[0] = (u_char) ((b) >> 56), \
+ (d)[1] = (u_char) ((b) >> 48), \
+ (d)[2] = (u_char) ((b) >> 40), \
+ (d)[3] = (u_char) ((b) >> 32), \
+ (d)[4] = (u_char) ((b) >> 24), \
+ (d)[5] = (u_char) ((b) >> 16), \
+ (d)[6] = (u_char) ((b) >> 8), \
+ (d)[7] = (u_char) (b))
+#endif
+
+#else /* !NGX_HAVE_LITTLE_ENDIAN */
+#define ngx_http_v2_huff_encode_buf(d, b) (*(uint64_t *) (d) = (b))
+#endif
+
+#else /* NGX_PTR_SIZE == 4 */
+
+#define ngx_http_v2_huff_encode_buf(d, b) (*(uint32_t *) (d) = htonl(b))
+
+#endif
+
+
+ngx_int_t
+ngx_http_v2_huff_encode(u_char *src, size_t len, u_char *dst, ngx_uint_t lower)
+{
+ u_char *end;
+ ngx_uint_t buf, hlen, pending, code;
+ ngx_http_v2_huff_encode_code_t *table, *next;
+
+ table = lower ? ngx_http_v2_huff_encode_codes_low
+ : ngx_http_v2_huff_encode_codes;
+
+ hlen = 0;
+ buf = 0;
+ pending = 0;
+
+ end = src + len;
+
+ while (src != end) {
+ next = &table[*src++];
+
+ code = next->code;
+ pending += next->len;
+
+ /* accumulate bits */
+ if (pending < sizeof(ngx_uint_t) * 8) {
+ buf ^= code << (sizeof(ngx_uint_t) * 8 - pending);
+ continue;
+ }
+
+ if ((hlen + sizeof(ngx_uint_t)) >= len) {
+ return NGX_DECLINED;
+ }
+
+ pending -= sizeof(ngx_uint_t) * 8;
+
+ buf ^= code >> pending;
+
+ ngx_http_v2_huff_encode_buf(&dst[hlen], buf);
+
+ hlen += sizeof(ngx_uint_t);
+
+ buf = pending ? code << (sizeof(ngx_uint_t) * 8 - pending) : 0;
+ }
+
+ buf ^= (ngx_uint_t) -1 >> pending;
+
+ pending = (pending + 7) & (8 | 16 | 32 | 64);
+
+ if ((hlen + pending / 8) >= len) {
+ return NGX_DECLINED;
+ }
+
+ buf >>= sizeof(ngx_uint_t) * 8 - pending;
+
+ while (pending) {
+ pending -= 8;
+ dst[hlen++] = (u_char) (buf >> pending);
+ }
+
+ return hlen;
+}
_______________________________________________
nginx-devel mailing list
[email protected]
http://mailman.nginx.org/mailman/listinfo/nginx-devel
