Adding upstream version 1.44.3.upstream/1.44.3upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 917 insertions, 0 deletions

diff --git a/web/server/h2o/libh2o/lib/http2/hpack.c b/web/server/h2o/libh2o/lib/http2/hpack.c
new file mode 100644
index 00000000..4adb15cd
--- /dev/null
+++ b/web/server/h2o/libh2o/lib/http2/hpack.c
@@ -0,0 +1,917 @@
+/*
+ * Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku, Fastly, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
+ * deal in the Software without restriction, including without limitation the
+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "h2o.h"
+#include "h2o/http2.h"
+#include "h2o/http2_internal.h"
+
+#define HEADER_TABLE_OFFSET 62
+#define HEADER_TABLE_ENTRY_SIZE_OFFSET 32
+#define STATUS_HEADER_MAX_SIZE 5
+#define CONTENT_LENGTH_HEADER_MAX_SIZE                                                                                             \
+    (3 + sizeof(H2O_UINT64_LONGEST_STR) - 1) /* uses Literal Header Field without Indexing (RFC7541 6.2.2) */
+
+struct st_h2o_hpack_static_table_entry_t {
+    const h2o_token_t *name;
+    const h2o_iovec_t value;
+};
+
+struct st_h2o_decode_header_result_t {
+    h2o_iovec_t *name;
+    h2o_iovec_t *value;
+};
+
+#include "hpack_huffman_table.h"
+#include "hpack_static_table.h"
+
+static inline int value_is_part_of_static_table(const h2o_iovec_t *value)
+{
+    return &h2o_hpack_static_table[0].value <= value &&
+           value <= &h2o_hpack_static_table[sizeof(h2o_hpack_static_table) / sizeof(h2o_hpack_static_table[0]) - 1].value;
+}
+
+static h2o_iovec_t *alloc_buf(h2o_mem_pool_t *pool, size_t len)
+{
+    h2o_iovec_t *buf = h2o_mem_alloc_shared(pool, sizeof(h2o_iovec_t) + len + 1, NULL);
+    buf->base = (char *)buf + sizeof(h2o_iovec_t);
+    buf->len = len;
+    return buf;
+}
+
+/* validate a header value against https://tools.ietf.org/html/rfc7230#section-3.2 */
+static int contains_invalid_field_value_char(const char *s, size_t len)
+{
+    /* all printable chars + horizontal tab */
+    static const char valid_h2_field_value_char[] = {
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*    0-31 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /*   32-63 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /*   64-95 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /*  96-127 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 128-159 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 160-191 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 192-223 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 224-255 */
+    };
+
+    for (; len != 0; ++s, --len) {
+        unsigned char ch = (unsigned char)*s;
+        if (!valid_h2_field_value_char[ch]) {
+            return 1;
+        }
+    }
+    return 0;
+}
+
+static const char *err_found_upper_case_in_header_name = "found an upper-case letter in header name";
+static const char *soft_err_found_invalid_char_in_header_name = "found an invalid character in header name";
+static const char *soft_err_found_invalid_char_in_header_value = "found an invalid character in header value";
+
+/* validate a header name against https://tools.ietf.org/html/rfc7230#section-3.2,
+ * in addition to that, we disallow upper case chars as well.
+ * This sets @err_desc for all invalid characters, but only returns true
+ * for upper case characters, this is because we return a protocol error
+ * in that case. */
+static const char *validate_header_name(const char *s, size_t len)
+{
+    const char *ret = NULL;
+    /* all printable chars, except upper case and separator characters */
+    static const char valid_h2_header_name_char[] = {
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*    0-31 */
+        0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /*   32-63 */
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, /*   64-95 */
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, /*  96-127 */
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 128-159 */
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 160-191 */
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 192-223 */
+        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 224-255 */
+    };
+
+    for (; len != 0; ++s, --len) {
+        unsigned char ch = (unsigned char)*s;
+        if (!valid_h2_header_name_char[ch]) {
+            if (ch - 'A' < 26U) {
+                return err_found_upper_case_in_header_name;
+            }
+            ret = soft_err_found_invalid_char_in_header_name;
+        }
+    }
+    return ret;
+}
+
+static int32_t decode_int(const uint8_t **src, const uint8_t *src_end, size_t prefix_bits)
+{
+    int32_t value, mult;
+    uint8_t prefix_max = (1 << prefix_bits) - 1;
+
+    if (*src >= src_end)
+        return -1;
+
+    value = (uint8_t) * (*src)++ & prefix_max;
+    if (value != prefix_max) {
+        return value;
+    }
+
+    /* we only allow at most 4 octets (excluding prefix) to be used as int (== 2**(4*7) == 2**28) */
+    if (src_end - *src > 4)
+        src_end = *src + 4;
+
+    value = prefix_max;
+    for (mult = 1;; mult *= 128) {
+        if (*src >= src_end)
+            return -1;
+        value += (**src & 127) * mult;
+        if ((*(*src)++ & 128) == 0)
+            return value;
+    }
+}
+
+static char *huffdecode4(char *dst, uint8_t in, uint8_t *state, int *maybe_eos, uint8_t *seen_char_types)
+{
+    const nghttp2_huff_decode *entry = huff_decode_table[*state] + in;
+
+    if ((entry->flags & NGHTTP2_HUFF_FAIL) != 0)
+        return NULL;
+    if ((entry->flags & NGHTTP2_HUFF_SYM) != 0) {
+        *dst++ = entry->sym;
+        *seen_char_types |= (entry->flags & NGHTTP2_HUFF_INVALID_CHARS);
+    }
+    *state = entry->state;
+    *maybe_eos = (entry->flags & NGHTTP2_HUFF_ACCEPTED) != 0;
+
+    return dst;
+}
+
+static h2o_iovec_t *decode_huffman(h2o_mem_pool_t *pool, const uint8_t *src, size_t len, uint8_t *seen_char_types)
+{
+    const uint8_t *src_end = src + len;
+    char *dst;
+    uint8_t state = 0;
+    int maybe_eos = 1;
+    h2o_iovec_t *dst_buf = alloc_buf(pool, len * 2); /* max compression ratio is >= 0.5 */
+
+    dst = dst_buf->base;
+    for (; src < src_end; src++) {
+        if ((dst = huffdecode4(dst, *src >> 4, &state, &maybe_eos, seen_char_types)) == NULL)
+            return NULL;
+        if ((dst = huffdecode4(dst, *src & 0xf, &state, &maybe_eos, seen_char_types)) == NULL)
+            return NULL;
+    }
+
+    if (!maybe_eos)
+        return NULL;
+
+    *dst = '\0';
+    dst_buf->len = dst - dst_buf->base;
+    return dst_buf;
+}
+
+static h2o_iovec_t *decode_string(h2o_mem_pool_t *pool, const uint8_t **src, const uint8_t *src_end, int is_header_name,
+                                  const char **err_desc)
+{
+    h2o_iovec_t *ret;
+    int is_huffman;
+    int32_t len;
+
+    if (*src >= src_end)
+        return NULL;
+
+    is_huffman = (**src & 0x80) != 0;
+    if ((len = decode_int(src, src_end, 7)) == -1)
+        return NULL;
+
+    if (is_huffman) {
+        uint8_t hflags = 0;
+        if (*src + len > src_end)
+            return NULL;
+        if ((ret = decode_huffman(pool, *src, len, &hflags)) == NULL)
+            return NULL;
+        if (is_header_name) {
+            if (ret->len <= 0) {
+                return NULL;
+            }
+            /* pseudo-headers are checked later in `decode_header` */
+            if (hflags & NGHTTP2_HUFF_INVALID_FOR_HEADER_NAME && ret->base[0] != ':') {
+                if (hflags & NGHTTP2_HUFF_UPPER_CASE_CHAR) {
+                    *err_desc = err_found_upper_case_in_header_name;
+                    return NULL;
+                } else {
+                    *err_desc = soft_err_found_invalid_char_in_header_name;
+                }
+            }
+        } else {
+            if (hflags & NGHTTP2_HUFF_INVALID_FOR_HEADER_VALUE) {
+                *err_desc = soft_err_found_invalid_char_in_header_value;
+            }
+        }
+    } else {
+        if (*src + len > src_end)
+            return NULL;
+        if (is_header_name) {
+            /* pseudo-headers are checked later in `decode_header` */
+            if (**src != (uint8_t)':') {
+                *err_desc = validate_header_name((char *)*src, len);
+                if (*err_desc == err_found_upper_case_in_header_name) {
+                    return NULL;
+                }
+            }
+        } else {
+            if (contains_invalid_field_value_char((char *)*src, len)) {
+                *err_desc = soft_err_found_invalid_char_in_header_value;
+            }
+        }
+        ret = alloc_buf(pool, len);
+        memcpy(ret->base, *src, len);
+        ret->base[len] = '\0';
+    }
+    *src += len;
+
+    return ret;
+}
+
+static void header_table_evict_one(h2o_hpack_header_table_t *table)
+{
+    struct st_h2o_hpack_header_table_entry_t *entry;
+    assert(table->num_entries != 0);
+
+    entry = h2o_hpack_header_table_get(table, --table->num_entries);
+    table->hpack_size -= entry->name->len + entry->value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET;
+    if (!h2o_iovec_is_token(entry->name))
+        h2o_mem_release_shared(entry->name);
+    if (!value_is_part_of_static_table(entry->value))
+        h2o_mem_release_shared(entry->value);
+    memset(entry, 0, sizeof(*entry));
+}
+
+static struct st_h2o_hpack_header_table_entry_t *header_table_add(h2o_hpack_header_table_t *table, size_t size_add,
+                                                                  size_t max_num_entries)
+{
+    /* adjust the size */
+    while (table->num_entries != 0 && table->hpack_size + size_add > table->hpack_capacity)
+        header_table_evict_one(table);
+    while (max_num_entries <= table->num_entries)
+        header_table_evict_one(table);
+    if (table->num_entries == 0) {
+        assert(table->hpack_size == 0);
+        if (size_add > table->hpack_capacity)
+            return NULL;
+    }
+    table->hpack_size += size_add;
+
+    /* grow the entries if full */
+    if (table->num_entries == table->entry_capacity) {
+        size_t new_capacity = table->num_entries * 2;
+        if (new_capacity < 16)
+            new_capacity = 16;
+        struct st_h2o_hpack_header_table_entry_t *new_entries =
+            h2o_mem_alloc(new_capacity * sizeof(struct st_h2o_hpack_header_table_entry_t));
+        if (table->num_entries != 0) {
+            size_t src_index = table->entry_start_index, dst_index = 0;
+            do {
+                new_entries[dst_index] = table->entries[src_index];
+                ++dst_index;
+                src_index = (src_index + 1) % table->entry_capacity;
+            } while (dst_index != table->num_entries);
+        }
+        memset(new_entries + table->num_entries, 0, sizeof(*new_entries) * (new_capacity - table->num_entries));
+        free(table->entries);
+        table->entries = new_entries;
+        table->entry_capacity = new_capacity;
+        table->entry_start_index = 0;
+    }
+
+    ++table->num_entries;
+    table->entry_start_index = (table->entry_start_index + table->entry_capacity - 1) % table->entry_capacity;
+    return table->entries + table->entry_start_index;
+}
+
+static int decode_header(h2o_mem_pool_t *pool, struct st_h2o_decode_header_result_t *result,
+                         h2o_hpack_header_table_t *hpack_header_table, const uint8_t **const src, const uint8_t *src_end,
+                         const char **err_desc)
+{
+    int32_t index = 0;
+    int value_is_indexed = 0, do_index = 0;
+
+Redo:
+    if (*src >= src_end)
+        return H2O_HTTP2_ERROR_COMPRESSION;
+
+    /* determine the mode and handle accordingly */
+    if (**src >= 128) {
+        /* indexed header field representation */
+        if ((index = decode_int(src, src_end, 7)) <= 0)
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        value_is_indexed = 1;
+    } else if (**src >= 64) {
+        /* literal header field with incremental handling */
+        if (**src == 64) {
+            ++*src;
+        } else if ((index = decode_int(src, src_end, 6)) <= 0) {
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+        do_index = 1;
+    } else if (**src < 32) {
+        /* literal header field without indexing / never indexed */
+        if ((**src & 0xf) == 0) {
+            ++*src;
+        } else if ((index = decode_int(src, src_end, 4)) <= 0) {
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+    } else {
+        /* size update */
+        int new_apacity;
+        if ((new_apacity = decode_int(src, src_end, 5)) < 0) {
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+        if (new_apacity > hpack_header_table->hpack_max_capacity) {
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+        hpack_header_table->hpack_capacity = new_apacity;
+        while (hpack_header_table->num_entries != 0 && hpack_header_table->hpack_size > hpack_header_table->hpack_capacity) {
+            header_table_evict_one(hpack_header_table);
+        }
+        goto Redo;
+    }
+
+    /* determine the header */
+    if (index > 0) {
+        /* existing name (and value?) */
+        if (index < HEADER_TABLE_OFFSET) {
+            result->name = (h2o_iovec_t *)h2o_hpack_static_table[index - 1].name;
+            if (value_is_indexed) {
+                result->value = (h2o_iovec_t *)&h2o_hpack_static_table[index - 1].value;
+            }
+        } else if (index - HEADER_TABLE_OFFSET < hpack_header_table->num_entries) {
+            struct st_h2o_hpack_header_table_entry_t *entry =
+                h2o_hpack_header_table_get(hpack_header_table, index - HEADER_TABLE_OFFSET);
+            *err_desc = entry->err_desc;
+            result->name = entry->name;
+            if (!h2o_iovec_is_token(result->name))
+                h2o_mem_link_shared(pool, result->name);
+            if (value_is_indexed) {
+                result->value = entry->value;
+                h2o_mem_link_shared(pool, result->value);
+            }
+        } else {
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+    } else {
+        /* non-existing name */
+        const h2o_token_t *name_token;
+        if ((result->name = decode_string(pool, src, src_end, 1, err_desc)) == NULL) {
+            if (*err_desc == err_found_upper_case_in_header_name) {
+                return H2O_HTTP2_ERROR_PROTOCOL;
+            }
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+        if (!*err_desc) {
+            /* predefined header names should be interned */
+            if ((name_token = h2o_lookup_token(result->name->base, result->name->len)) != NULL) {
+                result->name = (h2o_iovec_t *)&name_token->buf;
+            }
+        }
+    }
+
+    /* determine the value (if necessary) */
+    if (!value_is_indexed) {
+        if ((result->value = decode_string(pool, src, src_end, 0, err_desc)) == NULL) {
+            return H2O_HTTP2_ERROR_COMPRESSION;
+        }
+    }
+
+    /* add the decoded header to the header table if necessary */
+    if (do_index) {
+        struct st_h2o_hpack_header_table_entry_t *entry =
+            header_table_add(hpack_header_table, result->name->len + result->value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET, SIZE_MAX);
+        if (entry != NULL) {
+            entry->err_desc = *err_desc;
+            entry->name = result->name;
+            if (!h2o_iovec_is_token(entry->name))
+                h2o_mem_addref_shared(entry->name);
+            entry->value = result->value;
+            if (!value_is_part_of_static_table(entry->value))
+                h2o_mem_addref_shared(entry->value);
+        }
+    }
+
+    return *err_desc ? H2O_HTTP2_ERROR_INVALID_HEADER_CHAR : 0;
+}
+
+static uint8_t *encode_status(uint8_t *dst, int status)
+{
+    /* see also: STATUS_HEADER_MAX_SIZE */
+
+    assert(100 <= status && status <= 999);
+
+    switch (status) {
+#define COMMON_CODE(code, st)                                                                                                      \
+    case st:                                                                                                                       \
+        *dst++ = 0x80 | code;                                                                                                      \
+        break
+        COMMON_CODE(8, 200);
+        COMMON_CODE(9, 204);
+        COMMON_CODE(10, 206);
+        COMMON_CODE(11, 304);
+        COMMON_CODE(12, 400);
+        COMMON_CODE(13, 404);
+        COMMON_CODE(14, 500);
+#undef COMMON_CODE
+    default:
+        /* use literal header field without indexing - indexed name */
+        *dst++ = 8;
+        *dst++ = 3;
+        sprintf((char *)dst, "%d", status);
+        dst += 3;
+        break;
+    }
+
+    return dst;
+}
+
+static uint8_t *encode_content_length(uint8_t *dst, size_t value)
+{
+    char buf[32], *p = buf + sizeof(buf);
+    size_t l;
+
+    do {
+        *--p = '0' + value % 10;
+    } while ((value /= 10) != 0);
+    l = buf + sizeof(buf) - p;
+    *dst++ = 0x0f;
+    *dst++ = 0x0d;
+    *dst++ = (uint8_t)l;
+    memcpy(dst, p, l);
+    dst += l;
+
+    return dst;
+}
+
+void h2o_hpack_dispose_header_table(h2o_hpack_header_table_t *header_table)
+{
+    if (header_table->num_entries != 0) {
+        size_t index = header_table->entry_start_index;
+        do {
+            struct st_h2o_hpack_header_table_entry_t *entry = header_table->entries + index;
+            if (!h2o_iovec_is_token(entry->name))
+                h2o_mem_release_shared(entry->name);
+            if (!value_is_part_of_static_table(entry->value))
+                h2o_mem_release_shared(entry->value);
+            index = (index + 1) % header_table->entry_capacity;
+        } while (--header_table->num_entries != 0);
+    }
+    free(header_table->entries);
+}
+
+int h2o_hpack_parse_headers(h2o_req_t *req, h2o_hpack_header_table_t *header_table, const uint8_t *src, size_t len,
+                            int *pseudo_header_exists_map, size_t *content_length, h2o_cache_digests_t **digests,
+                            const char **err_desc)
+{
+    const uint8_t *src_end = src + len;
+
+    *content_length = SIZE_MAX;
+
+    while (src != src_end) {
+        struct st_h2o_decode_header_result_t r;
+        const char *decode_err = NULL;
+        int ret = decode_header(&req->pool, &r, header_table, &src, src_end, &decode_err);
+        if (ret != 0) {
+            if (ret == H2O_HTTP2_ERROR_INVALID_HEADER_CHAR) {
+                /* this is a soft error, we continue parsing, but register only the first error */
+                if (*err_desc == NULL) {
+                    *err_desc = decode_err;
+                }
+            } else {
+                *err_desc = decode_err;
+                return ret;
+            }
+        }
+        if (r.name->base[0] == ':') {
+            if (pseudo_header_exists_map != NULL) {
+                /* FIXME validate the chars in the value (e.g. reject SP in path) */
+                if (r.name == &H2O_TOKEN_AUTHORITY->buf) {
+                    /* FIXME should we perform this check? */
+                    if (req->input.authority.base != NULL)
+                        return H2O_HTTP2_ERROR_PROTOCOL;
+                    req->input.authority = *r.value;
+                    *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_AUTHORITY_EXISTS;
+                } else if (r.name == &H2O_TOKEN_METHOD->buf) {
+                    if (req->input.method.base != NULL)
+                        return H2O_HTTP2_ERROR_PROTOCOL;
+                    req->input.method = *r.value;
+                    *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_METHOD_EXISTS;
+                } else if (r.name == &H2O_TOKEN_PATH->buf) {
+                    if (req->input.path.base != NULL)
+                        return H2O_HTTP2_ERROR_PROTOCOL;
+                    req->input.path = *r.value;
+                    *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_PATH_EXISTS;
+                } else if (r.name == &H2O_TOKEN_SCHEME->buf) {
+                    if (req->input.scheme != NULL)
+                        return H2O_HTTP2_ERROR_PROTOCOL;
+                    if (h2o_memis(r.value->base, r.value->len, H2O_STRLIT("https"))) {
+                        req->input.scheme = &H2O_URL_SCHEME_HTTPS;
+                    } else {
+                        /* draft-16 8.1.2.3 suggests quote: ":scheme is not restricted to http and https schemed URIs" */
+                        req->input.scheme = &H2O_URL_SCHEME_HTTP;
+                    }
+                    *pseudo_header_exists_map |= H2O_HPACK_PARSE_HEADERS_SCHEME_EXISTS;
+                } else {
+                    return H2O_HTTP2_ERROR_PROTOCOL;
+                }
+            } else {
+                return H2O_HTTP2_ERROR_PROTOCOL;
+            }
+        } else {
+            pseudo_header_exists_map = NULL;
+            if (h2o_iovec_is_token(r.name)) {
+                h2o_token_t *token = H2O_STRUCT_FROM_MEMBER(h2o_token_t, buf, r.name);
+                if (token == H2O_TOKEN_CONTENT_LENGTH) {
+                    if ((*content_length = h2o_strtosize(r.value->base, r.value->len)) == SIZE_MAX)
+                        return H2O_HTTP2_ERROR_PROTOCOL;
+                } else {
+                    /* reject headers as defined in draft-16 8.1.2.2 */
+                    if (token->http2_should_reject) {
+                        if (token == H2O_TOKEN_HOST) {
+                            /* just skip (and :authority is used) */
+                            goto Next;
+                        } else if (token == H2O_TOKEN_TE && h2o_lcstris(r.value->base, r.value->len, H2O_STRLIT("trailers"))) {
+                            /* do not reject */
+                        } else {
+                            return H2O_HTTP2_ERROR_PROTOCOL;
+                        }
+                    }
+                    if (token == H2O_TOKEN_CACHE_DIGEST && digests != NULL) {
+                        /* TODO cache the decoded result in HPACK, as well as delay the decoding of the digest until being used */
+                        h2o_cache_digests_load_header(digests, r.value->base, r.value->len);
+                    }
+                    h2o_add_header(&req->pool, &req->headers, token, NULL, r.value->base, r.value->len);
+                }
+            } else {
+                h2o_add_header_by_str(&req->pool, &req->headers, r.name->base, r.name->len, 0, NULL, r.value->base, r.value->len);
+            }
+        }
+    Next:;
+    }
+
+    if (*err_desc) {
+        return H2O_HTTP2_ERROR_INVALID_HEADER_CHAR;
+    }
+    return 0;
+}
+
+static inline int encode_int_is_onebyte(uint32_t value, size_t prefix_bits)
+{
+    return value < (1 << prefix_bits) - 1;
+}
+
+static uint8_t *encode_int(uint8_t *dst, uint32_t value, size_t prefix_bits)
+{
+    if (encode_int_is_onebyte(value, prefix_bits)) {
+        *dst++ |= value;
+    } else {
+        /* see also: MAX_ENCODE_INT_LENGTH */
+        value -= (1 << prefix_bits) - 1;
+        if (value > 0x0fffffff)
+            h2o_fatal("value out of range");
+        *dst++ |= (1 << prefix_bits) - 1;
+        for (; value >= 128; value >>= 7) {
+            *dst++ = 0x80 | value;
+        }
+        *dst++ = value;
+    }
+    return dst;
+}
+
+static size_t encode_huffman(uint8_t *_dst, const uint8_t *src, size_t len)
+{
+    uint8_t *dst = _dst, *dst_end = dst + len;
+    const uint8_t *src_end = src + len;
+    uint64_t bits = 0;
+    int bits_left = 40;
+
+    while (src != src_end) {
+        const nghttp2_huff_sym *sym = huff_sym_table + *src++;
+        bits |= (uint64_t)sym->code << (bits_left - sym->nbits);
+        bits_left -= sym->nbits;
+        while (bits_left <= 32) {
+            *dst++ = bits >> 32;
+            bits <<= 8;
+            bits_left += 8;
+            if (dst == dst_end) {
+                return 0;
+            }
+        }
+    }
+
+    if (bits_left != 40) {
+        bits |= ((uint64_t)1 << bits_left) - 1;
+        *dst++ = bits >> 32;
+    }
+    if (dst == dst_end) {
+        return 0;
+    }
+
+    return dst - _dst;
+}
+
+static size_t encode_as_is(uint8_t *dst, const char *s, size_t len)
+{
+    uint8_t *start = dst;
+    *dst = '\0';
+    dst = encode_int(dst, (uint32_t)len, 7);
+    memcpy(dst, s, len);
+    dst += len;
+    return dst - start;
+}
+
+size_t h2o_hpack_encode_string(uint8_t *dst, const char *s, size_t len)
+{
+    if (H2O_LIKELY(len != 0)) {
+        /* try to encode using huffman */
+        size_t hufflen = encode_huffman(dst + 1, (const uint8_t *)s, len);
+        if (H2O_LIKELY(hufflen != 0)) {
+            size_t head_len;
+            if (H2O_LIKELY(encode_int_is_onebyte((uint32_t)hufflen, 7))) {
+                dst[0] = (uint8_t)(0x80 | hufflen);
+                head_len = 1;
+            } else {
+                uint8_t head[8];
+                head[0] = '\x80';
+                head_len = encode_int(head, (uint32_t)hufflen, 7) - head;
+                memmove(dst + head_len, dst + 1, hufflen);
+                memcpy(dst, head, head_len);
+            }
+            return head_len + hufflen;
+        }
+    }
+    return encode_as_is(dst, s, len);
+}
+
+static uint8_t *encode_header(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_iovec_t *name,
+                              const h2o_iovec_t *value)
+{
+    int name_index = 0, dont_compress = 0, name_is_token = h2o_iovec_is_token(name);
+
+    /* try to send as indexed */
+    {
+        size_t header_table_index = header_table->entry_start_index, n;
+        for (n = header_table->num_entries; n != 0; --n) {
+            struct st_h2o_hpack_header_table_entry_t *entry = header_table->entries + header_table_index;
+            if (name_is_token) {
+                if (name != entry->name)
+                    goto Next;
+            } else {
+                if (!h2o_memis(name->base, name->len, entry->name->base, entry->name->len))
+                    goto Next;
+                if (name_index == 0)
+                    name_index = (int)(header_table->num_entries - n + HEADER_TABLE_OFFSET);
+            }
+            /* name matched! */
+            if (!h2o_memis(value->base, value->len, entry->value->base, entry->value->len))
+                goto Next;
+            /* name and value matched! */
+            *dst = 0x80;
+            dst = encode_int(dst, (uint32_t)(header_table->num_entries - n + HEADER_TABLE_OFFSET), 7);
+            return dst;
+        Next:
+            ++header_table_index;
+            if (header_table_index == header_table->entry_capacity)
+                header_table_index = 0;
+        }
+    }
+
+    if (name_is_token) {
+        const h2o_token_t *name_token = H2O_STRUCT_FROM_MEMBER(h2o_token_t, buf, name);
+        name_index = name_token->http2_static_table_name_index;
+        dont_compress = (name_token->dont_compress == 1 && value->len < 20) ? 1 : 0;
+    }
+
+    if (name_index != 0) {
+        /* literal header field with indexing (indexed name). */
+        if (dont_compress == 1) {
+            /* mark the field as 'never indexed' */
+            *dst = 0x10;
+            dst = encode_int(dst, name_index, 4);
+        } else {
+            *dst = 0x40;
+            dst = encode_int(dst, name_index, 6);
+        }
+    } else {
+        /* literal header field with indexing (new name) */
+        *dst++ = 0x40;
+        dst += h2o_hpack_encode_string(dst, name->base, name->len);
+    }
+    if (dont_compress == 1) {
+        /* bypass huffman encoding */
+        dst += encode_as_is(dst, value->base, value->len);
+    } else {
+        /* add to header table (maximum number of entries in output header table is limited to 32 so that the search (see above) would
+           not take too long) */
+        dst += h2o_hpack_encode_string(dst, value->base, value->len);
+        struct st_h2o_hpack_header_table_entry_t *entry =
+            header_table_add(header_table, name->len + value->len + HEADER_TABLE_ENTRY_SIZE_OFFSET, 32);
+        if (entry != NULL) {
+            if (name_is_token) {
+                entry->name = (h2o_iovec_t *)name;
+            } else {
+                entry->name = alloc_buf(NULL, name->len);
+                entry->name->base[name->len] = '\0';
+                memcpy(entry->name->base, name->base, name->len);
+            }
+            entry->value = alloc_buf(NULL, value->len);
+            entry->value->base[value->len] = '\0';
+            memcpy(entry->value->base, value->base, value->len);
+        }
+    }
+
+    return dst;
+}
+
+static uint8_t *encode_method(h2o_hpack_header_table_t *header_table, uint8_t *dst, h2o_iovec_t value)
+{
+    if (h2o_memis(value.base, value.len, H2O_STRLIT("GET"))) {
+        *dst++ = 0x82;
+        return dst;
+    }
+    if (h2o_memis(value.base, value.len, H2O_STRLIT("POST"))) {
+        *dst++ = 0x83;
+        return dst;
+    }
+    return encode_header(header_table, dst, &H2O_TOKEN_METHOD->buf, &value);
+}
+
+static uint8_t *encode_scheme(h2o_hpack_header_table_t *header_table, uint8_t *dst, const h2o_url_scheme_t *scheme)
+{
+    if (scheme == &H2O_URL_SCHEME_HTTPS) {
+        *dst++ = 0x87;
+        return dst;
+    }
+    if (scheme == &H2O_URL_SCHEME_HTTP) {
+        *dst++ = 0x86;
+        return dst;
+    }
+    return encode_header(header_table, dst, &H2O_TOKEN_SCHEME->buf, &scheme->name);
+}
+
+static uint8_t *encode_path(h2o_hpack_header_table_t *header_table, uint8_t *dst, h2o_iovec_t value)
+{
+    if (h2o_memis(value.base, value.len, H2O_STRLIT("/"))) {
+        *dst++ = 0x84;
+        return dst;
+    }
+    if (h2o_memis(value.base, value.len, H2O_STRLIT("/index.html"))) {
+        *dst++ = 0x85;
+        return dst;
+    }
+    return encode_header(header_table, dst, &H2O_TOKEN_PATH->buf, &value);
+}
+
+static uint8_t *encode_literal_header_without_indexing(uint8_t *dst, const h2o_iovec_t *name, const h2o_iovec_t *value)
+{
+    /* literal header field without indexing / never indexed */
+    *dst++ = 0;
+    dst += h2o_hpack_encode_string(dst, name->base, name->len);
+    dst += h2o_hpack_encode_string(dst, value->base, value->len);
+    return dst;
+}
+
+static size_t calc_capacity(size_t name_len, size_t value_len)
+{
+    return name_len + value_len + 1 + H2O_HTTP2_ENCODE_INT_MAX_LENGTH * 2;
+}
+
+static size_t calc_headers_capacity(const h2o_header_t *headers, size_t num_headers)
+{
+    const h2o_header_t *header;
+    size_t capacity = 0;
+    for (header = headers; num_headers != 0; ++header, --num_headers)
+        capacity += calc_capacity(header->name->len, header->value.len);
+    return capacity;
+}
+
+static void fixup_frame_headers(h2o_buffer_t **buf, size_t start_at, uint8_t type, uint32_t stream_id, size_t max_frame_size)
+{
+    /* try to fit all data into single frame, using the preallocated space for the frame header */
+    size_t payload_size = (*buf)->size - start_at - H2O_HTTP2_FRAME_HEADER_SIZE;
+    if (payload_size <= max_frame_size) {
+        h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + start_at), payload_size, type, H2O_HTTP2_FRAME_FLAG_END_HEADERS,
+                                      stream_id);
+        return;
+    }
+
+    /* need to setup continuation frames */
+    size_t off;
+    h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + start_at), max_frame_size, type, 0, stream_id);
+    off = start_at + H2O_HTTP2_FRAME_HEADER_SIZE + max_frame_size;
+    while (1) {
+        size_t left = (*buf)->size - off;
+        h2o_buffer_reserve(buf, H2O_HTTP2_FRAME_HEADER_SIZE);
+        memmove((*buf)->bytes + off + H2O_HTTP2_FRAME_HEADER_SIZE, (*buf)->bytes + off, left);
+        (*buf)->size += H2O_HTTP2_FRAME_HEADER_SIZE;
+        if (left <= max_frame_size) {
+            h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + off), left, H2O_HTTP2_FRAME_TYPE_CONTINUATION,
+                                          H2O_HTTP2_FRAME_FLAG_END_HEADERS, stream_id);
+            break;
+        } else {
+            h2o_http2_encode_frame_header((uint8_t *)((*buf)->bytes + off), max_frame_size, H2O_HTTP2_FRAME_TYPE_CONTINUATION, 0,
+                                          stream_id);
+            off += H2O_HTTP2_FRAME_HEADER_SIZE + max_frame_size;
+        }
+    }
+}
+
+void h2o_hpack_flatten_request(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t stream_id,
+                               size_t max_frame_size, h2o_req_t *req, uint32_t parent_stream_id)
+{
+    size_t capacity = calc_headers_capacity(req->headers.entries, req->headers.size);
+    capacity += H2O_HTTP2_FRAME_HEADER_SIZE /* first frame header */
+                + 4;                        /* promised stream id */
+    capacity += calc_capacity(H2O_TOKEN_METHOD->buf.len, req->input.method.len);
+    capacity += calc_capacity(H2O_TOKEN_SCHEME->buf.len, req->input.scheme->name.len);
+    capacity += calc_capacity(H2O_TOKEN_AUTHORITY->buf.len, req->input.authority.len);
+    capacity += calc_capacity(H2O_TOKEN_PATH->buf.len, req->input.path.len);
+
+    size_t start_at = (*buf)->size;
+    uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE);
+
+    /* encode */
+    dst = h2o_http2_encode32u(dst, stream_id);
+    dst = encode_method(header_table, dst, req->input.method);
+    dst = encode_scheme(header_table, dst, req->input.scheme);
+    dst = encode_header(header_table, dst, &H2O_TOKEN_AUTHORITY->buf, &req->input.authority);
+    dst = encode_path(header_table, dst, req->input.path);
+    size_t i;
+    for (i = 0; i != req->headers.size; ++i) {
+        const h2o_header_t *header = req->headers.entries + i;
+        if (header->name == &H2O_TOKEN_ACCEPT_ENCODING->buf &&
+            h2o_memis(header->value.base, header->value.len, H2O_STRLIT("gzip, deflate"))) {
+            *dst++ = 0x90;
+        } else {
+            dst = encode_header(header_table, dst, header->name, &header->value);
+        }
+    }
+    (*buf)->size = (char *)dst - (*buf)->bytes;
+
+    /* setup the frame headers */
+    fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_PUSH_PROMISE, parent_stream_id, max_frame_size);
+}
+
+void h2o_hpack_flatten_response(h2o_buffer_t **buf, h2o_hpack_header_table_t *header_table, uint32_t stream_id,
+                                size_t max_frame_size, h2o_res_t *res, h2o_timestamp_t *ts, const h2o_iovec_t *server_name,
+                                size_t content_length)
+{
+    size_t capacity = calc_headers_capacity(res->headers.entries, res->headers.size);
+    capacity += H2O_HTTP2_FRAME_HEADER_SIZE; /* for the first header */
+    capacity += STATUS_HEADER_MAX_SIZE;      /* for :status: */
+#ifndef H2O_UNITTEST
+    capacity += 2 + H2O_TIMESTR_RFC1123_LEN; /* for Date: */
+    if (server_name->len) {
+        capacity += 5 + server_name->len; /* for Server: */
+    }
+#endif
+    if (content_length != SIZE_MAX)
+        capacity += CONTENT_LENGTH_HEADER_MAX_SIZE; /* for content-length: UINT64_MAX (with huffman compression applied) */
+
+    size_t start_at = (*buf)->size;
+    uint8_t *dst = (void *)(h2o_buffer_reserve(buf, capacity).base + H2O_HTTP2_FRAME_HEADER_SIZE); /* skip frame header */
+
+    /* encode */
+    dst = encode_status(dst, res->status);
+#ifndef H2O_UNITTEST
+    /* TODO keep some kind of reference to the indexed headers of Server and Date, and reuse them */
+    if (server_name->len) {
+        dst = encode_header(header_table, dst, &H2O_TOKEN_SERVER->buf, server_name);
+    }
+    h2o_iovec_t date_value = {ts->str->rfc1123, H2O_TIMESTR_RFC1123_LEN};
+    dst = encode_header(header_table, dst, &H2O_TOKEN_DATE->buf, &date_value);
+#endif
+    size_t i;
+    for (i = 0; i != res->headers.size; ++i)
+        dst = encode_header(header_table, dst, res->headers.entries[i].name, &res->headers.entries[i].value);
+    if (content_length != SIZE_MAX)
+        dst = encode_content_length(dst, content_length);
+    (*buf)->size = (char *)dst - (*buf)->bytes;
+
+    /* setup the frame headers */
+    fixup_frame_headers(buf, start_at, H2O_HTTP2_FRAME_TYPE_HEADERS, stream_id, max_frame_size);
+}