/*
+ * lib/hpack.c
+ *
+ * Copyright (C) 2014 Andy Green <andy@warmcat.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation:
+ * version 2.1 of the License.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02110-1301 USA
+ */
+
+#include "private-libwebsockets.h"
+
+/*
* Official static header table for HPACK
* +-------+-----------------------------+---------------+
| 1 | :authority | |
WSI_TOKEN_HTTP_EXPECT,
WSI_TOKEN_HTTP_EXPIRES,
WSI_TOKEN_HTTP_FROM,
- WSI_TOKEN_HTTP_HOST,
+ WSI_TOKEN_HOST,
WSI_TOKEN_HTTP_IF_MATCH,
WSI_TOKEN_HTTP_IF_MODIFIED_SINCE,
WSI_TOKEN_HTTP_IF_NONE_MATCH,
WSI_TOKEN_HTTP_WWW_AUTHENTICATE,
};
+/* some of the entries imply values as well as header names */
+
static const char * const http2_canned[] = {
"",
"",
"200",
"204",
"206",
- "300",
"304",
"400",
"404",
"gzip, deflate"
};
+/* see minihuf.c */
+
#include "huftable.h"
-int lextable_decode(int pos, char c)
+static int huftable_decode(int pos, char c)
{
int q = pos + !!c;
return pos + (lextable[q] << 1);
}
-static int lws_add_header(int header, const char *payload, int len)
+static int lws_hpack_update_table_size(struct lws *wsi, int idx)
+{
+ lwsl_info("hpack set table size %d\n", idx);
+ return 0;
+}
+
+static int lws_frag_start(struct lws *wsi, int hdr_token_idx)
+{
+ struct allocated_headers * ah = wsi->u.http2.http.ah;
+
+ if (!hdr_token_idx) {
+ lwsl_err("%s: zero hdr_token_idx\n", __func__);
+ return 1;
+ }
+
+ if (ah->nfrag >= ARRAY_SIZE(ah->frag_index)) {
+ lwsl_err("%s: frag index %d too big\n", __func__, ah->nfrag);
+ return 1;
+ }
+
+ ah->frags[ah->nfrag].offset = ah->pos;
+ ah->frags[ah->nfrag].len = 0;
+ ah->frags[ah->nfrag].nfrag = 0;
+
+ ah->frag_index[hdr_token_idx] = ah->nfrag;
+
+ return 0;
+}
+
+static int lws_frag_append(struct lws *wsi, unsigned char c)
+{
+ struct allocated_headers * ah = wsi->u.http2.http.ah;
+
+ ah->data[ah->pos++] = c;
+ ah->frags[ah->nfrag].len++;
+
+ return ah->pos >= wsi->context->max_http_header_data;
+}
+
+static int lws_frag_end(struct lws *wsi)
+{
+ if (lws_frag_append(wsi, 0))
+ return 1;
+
+ wsi->u.http2.http.ah->nfrag++;
+ return 0;
+}
+
+static void lws_dump_header(struct lws *wsi, int hdr)
{
- wsi->u.ah.frag_index[header]
+ char s[200];
+ int len = lws_hdr_copy(wsi, s, sizeof(s) - 1, hdr);
+ s[len] = '\0';
+ lwsl_info(" hdr tok %d (%s) = '%s'\n", hdr, lws_token_to_string(hdr), s);
}
-int lws_hpack_interpret(struct libwebsocket *wsi, unsigned char c)
+static int
+lws_token_from_index(struct lws *wsi, int index, char **arg, int *len)
{
+ struct hpack_dynamic_table *dyn;
+
+ /* dynamic table only belongs to network wsi */
+
+ wsi = lws_http2_get_network_wsi(wsi);
+
+ dyn = wsi->u.http2.hpack_dyn_table;
+
+ if (index < ARRAY_SIZE(static_token))
+ return static_token[index];
+
+ if (!dyn)
+ return 0;
+
+ index -= ARRAY_SIZE(static_token);
+ if (index >= dyn->num_entries)
+ return 0;
+
+ if (arg && len) {
+ *arg = dyn->args + dyn->entries[index].arg_offset;
+ *len = dyn->entries[index].arg_len;
+ }
+
+ return dyn->entries[index].token;
+}
+
+static int
+lws_hpack_add_dynamic_header(struct lws *wsi, int token, char *arg, int len)
+{
+ struct hpack_dynamic_table *dyn;
+ int ret = 1;
+
+ wsi = lws_http2_get_network_wsi(wsi);
+ dyn = wsi->u.http2.hpack_dyn_table;
+
+ if (!dyn) {
+ dyn = lws_zalloc(sizeof(*dyn));
+ if (!dyn)
+ return 1;
+ wsi->u.http2.hpack_dyn_table = dyn;
+
+ dyn->args = lws_malloc(1024);
+ if (!dyn->args)
+ goto bail1;
+ dyn->args_length = 1024;
+ dyn->entries = lws_malloc(sizeof(dyn->entries[0]) * 20);
+ if (!dyn->entries)
+ goto bail2;
+ dyn->num_entries = 20;
+ }
+
+ if (dyn->next == dyn->num_entries)
+ return 1;
+
+ if (dyn->args_length - dyn->pos < len)
+ return 1;
+
+ dyn->entries[dyn->next].token = token;
+ dyn->entries[dyn->next].arg_offset = dyn->pos;
+ if (len)
+ memcpy(dyn->args + dyn->pos, arg, len);
+ dyn->entries[dyn->next].arg_len = len;
+
+ lwsl_info("%s: added dynamic hdr %d, token %d (%s), len %d\n",
+ __func__, dyn->next, token, lws_token_to_string(token), len);
+
+ dyn->pos += len;
+ dyn->next++;
+
+ return 0;
+
+bail2:
+ lws_free(dyn->args);
+bail1:
+ lws_free(dyn);
+ wsi->u.http2.hpack_dyn_table = NULL;
+
+ return ret;
+}
+
+static int lws_write_indexed_hdr(struct lws *wsi, int idx)
+{
+ const char *p;
+ int tok = lws_token_from_index(wsi, idx, NULL, 0);
+
+ lwsl_info("writing indexed hdr %d (tok %d '%s')\n", idx, tok,
+ lws_token_to_string(tok));
+
+ if (lws_frag_start(wsi, tok))
+ return 1;
+
+ if (idx < ARRAY_SIZE(http2_canned)) {
+ p = http2_canned[idx];
+ while (*p)
+ if (lws_frag_append(wsi, *p++))
+ return 1;
+ }
+ if (lws_frag_end(wsi))
+ return 1;
+
+ lws_dump_header(wsi, tok);
+
+ return 0;
+}
+
+int lws_hpack_interpret(struct lws *wsi, unsigned char c)
+{
+ unsigned int prev;
+ unsigned char c1;
+ int n;
+
+ lwsl_debug(" state %d\n", wsi->u.http2.hpack);
+
switch (wsi->u.http2.hpack) {
+ case HPKS_OPT_PADDING:
+ wsi->u.http2.padding = c;
+ lwsl_info("padding %d\n", c);
+ if (wsi->u.http2.flags & LWS_HTTP2_FLAG_PRIORITY) {
+ wsi->u.http2.hpack = HKPS_OPT_E_DEPENDENCY;
+ wsi->u.http2.hpack_m = 4;
+ } else
+ wsi->u.http2.hpack = HPKS_TYPE;
+ break;
+ case HKPS_OPT_E_DEPENDENCY:
+ wsi->u.http2.hpack_e_dep <<= 8;
+ wsi->u.http2.hpack_e_dep |= c;
+ if (! --wsi->u.http2.hpack_m) {
+ lwsl_info("hpack_e_dep = 0x%x\n", wsi->u.http2.hpack_e_dep);
+ wsi->u.http2.hpack = HKPS_OPT_WEIGHT;
+ }
+ break;
+ case HKPS_OPT_WEIGHT:
+ /* weight */
+ wsi->u.http2.hpack = HPKS_TYPE;
+ break;
+
case HPKS_TYPE:
+
+ if (wsi->u.http2.count > (wsi->u.http2.length - wsi->u.http2.padding)) {
+ lwsl_info("padding eat\n");
+ break;
+ }
+
if (c & 0x80) { /* indexed header field only */
+ /* just a possibly-extended integer */
+ wsi->u.http2.hpack_type = HPKT_INDEXED_HDR_7;
+ lwsl_debug("HKPS_TYPE setting header_index %d\n", c & 0x7f);
wsi->u.http2.header_index = c & 0x7f;
+ if ((c & 0x7f) == 0x7f) {
+ wsi->u.http2.hpack_len = c & 0x7f;
+ wsi->u.http2.hpack_m = 0;
+ wsi->u.http2.hpack = HPKS_IDX_EXT;
+ break;
+ }
+ lwsl_debug("HKPS_TYPE: %d\n", c & 0x7f);
+ if (lws_write_indexed_hdr(wsi, c & 0x7f))
+ return 1;
/* stay at same state */
break;
}
if (c & 0x40) { /* literal header incr idx */
+ /*
+ * [possibly-extended hdr idx (6) | new literal hdr name]
+ * H + possibly-extended value length
+ * literal value
+ */
+ lwsl_debug("HKPS_TYPE 2 setting header_index %d\n", 0);
+ wsi->u.http2.header_index = 0;
if (c == 0x40) { /* literal name */
- wsi->u.http2.header_index = 0;
- wsi->u.http2.hpack
+ wsi->u.http2.hpack_type = HPKT_LITERAL_HDR_VALUE_INCR;
+ wsi->u.http2.value = 0;
wsi->u.http2.hpack = HPKS_HLEN;
break;
}
/* indexed name */
+ wsi->u.http2.hpack_type = HPKT_INDEXED_HDR_6_VALUE_INCR;
+ if ((c & 0x3f) == 0x3f) {
+ wsi->u.http2.hpack_len = c & 0x3f;
+ wsi->u.http2.hpack_m = 0;
+ wsi->u.http2.hpack = HPKS_IDX_EXT;
+ break;
+ }
+ lwsl_debug("HKPS_TYPE 3 setting header_index %d\n", c & 0x3f);
wsi->u.http2.header_index = c & 0x3f;
+ wsi->u.http2.value = 1;
wsi->u.http2.hpack = HPKS_HLEN;
break;
}
switch(c & 0xf0) {
+ case 0x10: /* literal header never index */
case 0: /* literal header without indexing */
+ /*
+ * follows 0x40 except 4-bit hdr idx
+ * and don't add to index
+ */
if (c == 0) { /* literal name */
- wsi->u.http2.hpack = HPKS_NAME_HLEN;
+ wsi->u.http2.hpack_type = HPKT_LITERAL_HDR_VALUE;
+ wsi->u.http2.hpack = HPKS_HLEN;
+ wsi->u.http2.value = 0;
break;
}
+ //lwsl_debug("indexed\n");
/* indexed name */
- wsi->u.http2.header_index = c & 0xf;
- wsi->u.http2.hpack = HPKS_VALUE_HLEN;
- break;
- case 0x10: /* literal header never indexed */
- if (c == 0x10) { /* literal name */
- wsi->u.http2.header_index = 0;
- wsi->u.http2.hpack = HPKS_NAME_HLEN;
+ wsi->u.http2.hpack_type = HPKT_INDEXED_HDR_4_VALUE;
+ wsi->u.http2.header_index = 0;
+ if ((c & 0xf) == 0xf) {
+ wsi->u.http2.hpack_len = c & 0xf;
+ wsi->u.http2.hpack_m = 0;
+ wsi->u.http2.hpack = HPKS_IDX_EXT;
break;
}
- /* indexed name */
+ //lwsl_err("HKPS_TYPE 5 setting header_index %d\n", c & 0xf);
wsi->u.http2.header_index = c & 0xf;
- wsi->u.http2.hpack = HPKS_NAME_HLEN;
+ wsi->u.http2.value = 1;
+ wsi->u.http2.hpack = HPKS_HLEN;
break;
+
case 0x20:
case 0x30: /* header table size update */
- /* = c & 0x1f */
- /* stay at same state */
+ /* possibly-extended size value (5) */
+ wsi->u.http2.hpack_type = HPKT_SIZE_5;
+ if ((c & 0x1f) == 0x1f) {
+ wsi->u.http2.hpack_len = c & 0x1f;
+ wsi->u.http2.hpack_m = 0;
+ wsi->u.http2.hpack = HPKS_IDX_EXT;
+ break;
+ }
+ lws_hpack_update_table_size(wsi, c & 0x1f);
+ /* stay at HPKS_TYPE state */
break;
}
- break;
- case HPKS_HLEN:
+ break;
+
+ case HPKS_IDX_EXT:
+ wsi->u.http2.hpack_len += (c & 0x7f) << wsi->u.http2.hpack_m;
+ wsi->u.http2.hpack_m += 7;
+ if (!(c & 0x80)) {
+ switch (wsi->u.http2.hpack_type) {
+ case HPKT_INDEXED_HDR_7:
+ //lwsl_err("HKPS_IDX_EXT hdr idx %d\n", wsi->u.http2.hpack_len);
+ if (lws_write_indexed_hdr(wsi, wsi->u.http2.hpack_len))
+ return 1;
+ wsi->u.http2.hpack = HPKS_TYPE;
+ break;
+ default:
+ // lwsl_err("HKPS_IDX_EXT setting header_index %d\n",
+ // wsi->u.http2.hpack_len);
+ wsi->u.http2.header_index = wsi->u.http2.hpack_len;
+ wsi->u.http2.value = 1;
+ wsi->u.http2.hpack = HPKS_HLEN;
+ break;
+ }
+ }
+ break;
+
+ case HPKS_HLEN: /* [ H | 7+ ] */
wsi->u.http2.huff = !!(c & 0x80);
+ wsi->u.http2.hpack_pos = 0;
wsi->u.http2.hpack_len = c & 0x7f;
- if (wsi->u.http2.hpack_len < 127) {
- wsi->u.http2.hpack = HPKS_NAME_DATA;
+ if (wsi->u.http2.hpack_len < 0x7f) {
+pre_data:
+ if (wsi->u.http2.value) {
+ if (wsi->u.http2.header_index)
+ if (lws_frag_start(wsi, lws_token_from_index(wsi,
+ wsi->u.http2.header_index,
+ NULL, NULL))) {
+ // lwsl_notice("%s: hlen failed\n", __func__);
+ return 1;
+ }
+ } else
+ wsi->u.hdr.parser_state = WSI_TOKEN_NAME_PART;
+ wsi->u.http2.hpack = HPKS_DATA;
break;
}
wsi->u.http2.hpack_m = 0;
- wsi->u.http2.hpack = HPKS_NAME_HLEN_EXT;
+ wsi->u.http2.hpack = HPKS_HLEN_EXT;
break;
+
case HPKS_HLEN_EXT:
- wsi->u.http2.hpack_len += (c & 0x7f) << wsi->u.http2.hpack_m;
+ wsi->u.http2.hpack_len += (c & 0x7f) <<
+ wsi->u.http2.hpack_m;
wsi->u.http2.hpack_m += 7;
if (!(c & 0x80))
- wsi->u.http2.hpack = HPKS_NAME_DATA;
+ goto pre_data;
+
break;
case HPKS_DATA:
+ for (n = 0; n < 8; n++) {
+ if (wsi->u.http2.huff) {
+ prev = wsi->u.http2.hpack_pos;
+ wsi->u.http2.hpack_pos = huftable_decode(
+ wsi->u.http2.hpack_pos,
+ (c >> 7) & 1);
+ c <<= 1;
+ if (wsi->u.http2.hpack_pos == 0xffff)
+ return 1;
+ if (!(wsi->u.http2.hpack_pos & 0x8000))
+ continue;
+ c1 = wsi->u.http2.hpack_pos & 0x7fff;
+ wsi->u.http2.hpack_pos = 0;
+
+ if (!c1 && prev == HUFTABLE_0x100_PREV)
+ ; /* EOT */
+ } else {
+ n = 8;
+ c1 = c;
+ }
+ if (wsi->u.http2.value) { /* value */
+ if (wsi->u.http2.header_index)
+ if (lws_frag_append(wsi, c1))
+ return 1;
+ } else { /* name */
+ if (lws_parse(wsi, c1))
+ return 1;
+
+ }
+ }
+ if (--wsi->u.http2.hpack_len == 0) {
+
+ switch (wsi->u.http2.hpack_type) {
+ case HPKT_LITERAL_HDR_VALUE_INCR:
+ case HPKT_INDEXED_HDR_6_VALUE_INCR: // !!!
+ if (lws_hpack_add_dynamic_header(wsi,
+ lws_token_from_index(wsi,
+ wsi->u.http2.header_index,
+ NULL, NULL), NULL, 0))
+ return 1;
+ break;
+ default:
+ break;
+ }
+
+ n = 8;
+ if (wsi->u.http2.value) {
+ if (lws_frag_end(wsi))
+ return 1;
+ // lwsl_err("data\n");
+ lws_dump_header(wsi, lws_token_from_index(
+ wsi, wsi->u.http2.header_index,
+ NULL, NULL));
+ if (wsi->u.http2.count + wsi->u.http2.padding ==
+ wsi->u.http2.length)
+ wsi->u.http2.hpack = HKPS_OPT_DISCARD_PADDING;
+ else
+ wsi->u.http2.hpack = HPKS_TYPE;
+ } else { /* name */
+ //if (wsi->u.hdr.parser_state < WSI_TOKEN_COUNT)
+
+ wsi->u.http2.value = 1;
+ wsi->u.http2.hpack = HPKS_HLEN;
+ }
+ }
+ break;
+ case HKPS_OPT_DISCARD_PADDING:
+ lwsl_info("eating padding %x\n", c);
+ if (! --wsi->u.http2.padding)
+ wsi->u.http2.hpack = HPKS_TYPE;
+ break;
+ }
+
+ return 0;
+}
+
+static int lws_http2_num(int starting_bits, unsigned long num,
+ unsigned char **p, unsigned char *end)
+{
+ int mask = (1 << starting_bits) - 1;
+ if (num < mask) {
+ *((*p)++) |= num;
+ return *p >= end;
}
+
+ *((*p)++) |= mask;
+ if (*p >= end)
+ return 1;
+
+ num -= mask;
+ while (num >= 128) {
+ *((*p)++) = 0x80 | (num & 0x7f);
+ if (*p >= end)
+ return 1;
+ num >>= 7;
+ }
+
+ return 0;
+}
+
+int lws_add_http2_header_by_name(struct lws *wsi,
+ const unsigned char *name,
+ const unsigned char *value, int length,
+ unsigned char **p, unsigned char *end)
+{
+ int len;
+
+ lwsl_info("%s: %p %s:%s\n", __func__, *p, name, value);
+
+ len = strlen((char *)name);
+ if (len)
+ if (name[len - 1] == ':')
+ len--;
+
+ if (end - *p < len + length + 8)
+ return 1;
+
+ *((*p)++) = 0; /* not indexed, literal name */
+
+ **p = 0; /* non-HUF */
+ if (lws_http2_num(7, len, p, end))
+ return 1;
+ memcpy(*p, name, len);
+ *p += len;
+
+ *(*p) = 0; /* non-HUF */
+ if (lws_http2_num(7, length, p, end))
+ return 1;
+
+ memcpy(*p, value, length);
+ *p += length;
+
+ return 0;
+}
+
+int lws_add_http2_header_by_token(struct lws *wsi, enum lws_token_indexes token,
+ const unsigned char *value, int length,
+ unsigned char **p, unsigned char *end)
+{
+ const unsigned char *name;
+
+ name = lws_token_to_string(token);
+ if (!name)
+ return 1;
+
+ return lws_add_http2_header_by_name(wsi, name, value, length, p, end);
+}
+
+int lws_add_http2_header_status(struct lws *wsi,
+ unsigned int code, unsigned char **p,
+ unsigned char *end)
+{
+ unsigned char status[10];
+ int n;
+
+ wsi->u.http2.send_END_STREAM = !!(code >= 400);
+
+ n = sprintf((char *)status, "%u", code);
+ if (lws_add_http2_header_by_token(wsi, WSI_TOKEN_HTTP_COLON_STATUS,
+ status, n, p, end))
+
+ return 1;
+
+ return 0;
}