[PATCH] HTTP/2: HPACK Huffman encoding

Vlad Krasnov vlad at cloudflare.com
Thu Dec 17 11:49:32 UTC 2015


# 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

Implement HPACK Huffman encoding for HTTP/2.
This reduces the size of headers by over 30% on average.

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);
 
@@ -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"
+
+
 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;
     }
 
     pos = ngx_palloc(r->pool, len);
+    huff = ngx_palloc(r->pool, hlen);
     if (pos == NULL) {
         return NGX_ERROR;
     }
@@ -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);
+
         }
     }
 
@@ -453,11 +459,9 @@
             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, 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);
     }
 
     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, 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
+
+
+typedef struct {
+    ngx_uint_t  code;
+    ngx_uint_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 embedes to lower case transformations */
+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)
+{
+    *(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
+
+
+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;
+    ngx_http_v2_huff_encode_code_t  next;
+    ngx_http_v2_huff_encode_code_t *table;
+
+    if (!lower) {
+        table = ngx_http_v2_huff_encode_codes;
+
+    } else {
+        table = ngx_http_v2_huff_encode_codes_low;
+    }
+
+    inp = 0;
+    outp = 0;
+    pending = 0;
+    buf = 0;
+
+    while (inp < len) {
+        next = table[src[inp]];
+        /* Accumulate 64 bits */
+        if ((next.len + pending) < 64) {
+            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));
+
+            if (pending) {
+                buf = (uint64_t)next.code << (64 - pending);
+
+            } else {
+                buf = 0;
+            }
+        }
+
+        inp++;
+    }
+
+    buf ^= 0xffffffffffffffffUL >> pending;
+
+    while (pending > 0) {
+        dst[outp] = buf >> 56;
+        buf <<= 8;
+        pending -= 8;
+        outp++;
+
+        if (outp >= len) {
+            return NGX_ERROR;
+        }
+    }
+
+    ngx_log_debug2(NGX_LOG_DEBUG_HTTP, log, 0,
+                   "http2 huffman encoding successful; "
+                   "input len: %d, output len %d", len, outp);
+
+    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;
+    
+    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;
+}



More information about the nginx-devel mailing list