diff options
Diffstat (limited to 'src/qpack-dec.c')
| -rw-r--r-- | src/qpack-dec.c | 563 |
1 files changed, 563 insertions, 0 deletions
diff --git a/src/qpack-dec.c b/src/qpack-dec.c new file mode 100644 index 0000000..97392bb --- /dev/null +++ b/src/qpack-dec.c @@ -0,0 +1,563 @@ +/* + * QPACK decompressor + * + * Copyright 2021 HAProxy Technologies, Frederic Lecaille <flecaille@haproxy.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 + * exclusively. + * + * 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 <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <import/ist.h> +#include <haproxy/buf.h> +#include <haproxy/chunk.h> +#include <haproxy/h3.h> +#include <haproxy/mux_quic.h> +#include <haproxy/qpack-t.h> +#include <haproxy/qpack-dec.h> +#include <haproxy/qpack-tbl.h> +#include <haproxy/hpack-huff.h> +#include <haproxy/hpack-tbl.h> +#include <haproxy/http-hdr.h> +#include <haproxy/tools.h> + +#if defined(DEBUG_QPACK) +#define qpack_debug_printf fprintf +#define qpack_debug_hexdump debug_hexdump +#else +#define qpack_debug_printf(...) do { } while (0) +#define qpack_debug_hexdump(...) do { } while (0) +#endif + +/* Encoded field line bitmask */ +#define QPACK_EFL_BITMASK 0xf0 +#define QPACK_LFL_WPBNM 0x00 // Literal field line with post-base name reference +#define QPACK_IFL_WPBI 0x10 // Indexed field line with post-based index +#define QPACK_LFL_WLN_BIT 0x20 // Literal field line with literal name +#define QPACK_LFL_WNR_BIT 0x40 // Literal field line with name reference +#define QPACK_IFL_BIT 0x80 // Indexed field line + +/* reads a varint from <raw>'s lowest <b> bits and <len> bytes max (raw included). + * returns the 64-bit value on success after updating buf and len_in. Forces + * len_in to (uint64_t)-1 on truncated input. + * Note that this function is similar to the one used for HPACK (except that is supports + * up to 62-bits integers). + */ +static uint64_t qpack_get_varint(const unsigned char **buf, uint64_t *len_in, int b) +{ + uint64_t ret = 0; + int len = *len_in; + const uint8_t *raw = *buf; + uint8_t shift = 0; + + len--; + ret = *raw++ & ((1ULL << b) - 1); + if (ret != (uint64_t)((1ULL << b) - 1)) + goto end; + + while (len && (*raw & 128)) { + ret += ((uint64_t)*raw++ & 127) << shift; + shift += 7; + len--; + } + + /* last 7 bits */ + if (!len) + goto too_short; + + len--; + ret += ((uint64_t)*raw++ & 127) << shift; + + end: + *buf = raw; + *len_in = len; + return ret; + + too_short: + *len_in = (uint64_t)-1; + return 0; +} + +/* Decode an encoder stream. + * + * Returns 0 on success else non-zero. + */ +int qpack_decode_enc(struct buffer *buf, int fin, void *ctx) +{ + struct qcs *qcs = ctx; + size_t len; + unsigned char inst; + + /* RFC 9204 4.2. Encoder and Decoder Streams + * + * The sender MUST NOT close either of these streams, and the receiver + * MUST NOT request that the sender close either of these streams. + * Closure of either unidirectional stream type MUST be treated as a + * connection error of type H3_CLOSED_CRITICAL_STREAM. + */ + if (fin) { + qcc_set_error(qcs->qcc, H3_CLOSED_CRITICAL_STREAM, 1); + return -1; + } + + len = b_data(buf); + qpack_debug_hexdump(stderr, "[QPACK-DEC-ENC] ", b_head(buf), 0, len); + + if (!len) { + qpack_debug_printf(stderr, "[QPACK-DEC-ENC] empty stream\n"); + return 0; + } + + inst = (unsigned char)*b_head(buf) & QPACK_ENC_INST_BITMASK; + if (inst == QPACK_ENC_INST_DUP) { + /* Duplicate */ + } + else if (inst & QPACK_ENC_INST_IWNR_BIT) { + /* Insert With Name Reference */ + } + else if (inst & QPACK_ENC_INST_IWLN_BIT) { + /* Insert with literal name */ + } + else if (inst & QPACK_ENC_INST_SDTC_BIT) { + /* Set dynamic table capacity */ + } + + return 0; +} + +/* Decode an decoder stream. + * + * Returns 0 on success else non-zero. + */ +int qpack_decode_dec(struct buffer *buf, int fin, void *ctx) +{ + struct qcs *qcs = ctx; + size_t len; + unsigned char inst; + + /* RFC 9204 4.2. Encoder and Decoder Streams + * + * The sender MUST NOT close either of these streams, and the receiver + * MUST NOT request that the sender close either of these streams. + * Closure of either unidirectional stream type MUST be treated as a + * connection error of type H3_CLOSED_CRITICAL_STREAM. + */ + if (fin) { + qcc_set_error(qcs->qcc, H3_CLOSED_CRITICAL_STREAM, 1); + return -1; + } + + len = b_data(buf); + qpack_debug_hexdump(stderr, "[QPACK-DEC-DEC] ", b_head(buf), 0, len); + + if (!len) { + qpack_debug_printf(stderr, "[QPACK-DEC-DEC] empty stream\n"); + return 0; + } + + inst = (unsigned char)*b_head(buf) & QPACK_DEC_INST_BITMASK; + if (inst == QPACK_DEC_INST_ICINC) { + /* Insert count increment */ + } + else if (inst & QPACK_DEC_INST_SACK) { + /* Section Acknowledgment */ + } + else if (inst & QPACK_DEC_INST_SCCL) { + /* Stream cancellation */ + } + + return 0; +} + +/* Decode a field section prefix made of <enc_ric> and <db> two varints. + * Also set the 'S' sign bit for <db>. + * Return a negative error if failed, 0 if not. + */ +static int qpack_decode_fs_pfx(uint64_t *enc_ric, uint64_t *db, int *sign_bit, + const unsigned char **raw, uint64_t *len) +{ + *enc_ric = qpack_get_varint(raw, len, 8); + if (*len == (uint64_t)-1) + return -QPACK_ERR_RIC; + + *sign_bit = **raw & 0x8; + *db = qpack_get_varint(raw, len, 7); + if (*len == (uint64_t)-1) + return -QPACK_ERR_DB; + + return 0; +} + +/* Decode a field section from the <raw> buffer of <len> bytes. Each parsed + * header is inserted into <list> of <list_size> entries max and uses <tmp> as + * a storage for some elements pointing into it. An end marker is inserted at + * the end of the list with empty strings as name/value. + * + * Returns the number of headers inserted into list excluding the end marker. + * In case of error, a negative code QPACK_ERR_* is returned. + */ +int qpack_decode_fs(const unsigned char *raw, uint64_t len, struct buffer *tmp, + struct http_hdr *list, int list_size) +{ + struct ist name, value; + uint64_t enc_ric, db; + int s; + unsigned int efl_type; + int ret; + int hdr_idx = 0; + + qpack_debug_hexdump(stderr, "[QPACK-DEC-FS] ", (const char *)raw, 0, len); + + /* parse field section prefix */ + ret = qpack_decode_fs_pfx(&enc_ric, &db, &s, &raw, &len); + if (ret < 0) { + qpack_debug_printf(stderr, "##ERR@%d(%d)\n", __LINE__, ret); + goto out; + } + + chunk_reset(tmp); + qpack_debug_printf(stderr, "enc_ric: %llu db: %llu s=%d\n", + (unsigned long long)enc_ric, (unsigned long long)db, !!s); + /* Decode field lines */ + while (len) { + if (hdr_idx >= list_size) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TOO_LARGE; + goto out; + } + + /* parse field line representation */ + efl_type = *raw & QPACK_EFL_BITMASK; + qpack_debug_printf(stderr, "efl_type=0x%02x\n", efl_type); + + if (efl_type == QPACK_LFL_WPBNM) { + /* Literal field line with post-base name reference + * TODO adjust this when dynamic table support is implemented. + */ +#if 0 + uint64_t index __maybe_unused, length; + unsigned int n __maybe_unused, h __maybe_unused; + + qpack_debug_printf(stderr, "literal field line with post-base name reference:"); + n = *raw & 0x08; + index = qpack_get_varint(&raw, &len, 3); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + qpack_debug_printf(stderr, " n=%d index=%llu", !!n, (unsigned long long)index); + h = *raw & 0x80; + length = qpack_get_varint(&raw, &len, 7); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + qpack_debug_printf(stderr, " h=%d length=%llu", !!h, (unsigned long long)length); + + if (len < length) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + raw += length; + len -= length; +#endif + + /* RFC9204 2.2.3 Invalid References + * + * If the decoder encounters a reference in a field line representation + * to a dynamic table entry that has already been evicted or that has an + * absolute index greater than or equal to the declared Required Insert + * Count (Section 4.5.1), it MUST treat this as a connection error of + * type QPACK_DECOMPRESSION_FAILED. + */ + return -QPACK_DECOMPRESSION_FAILED; + } + else if (efl_type == QPACK_IFL_WPBI) { + /* Indexed field line with post-base index + * TODO adjust this when dynamic table support is implemented. + */ +#if 0 + uint64_t index __maybe_unused; + + qpack_debug_printf(stderr, "indexed field line with post-base index:"); + index = qpack_get_varint(&raw, &len, 4); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + qpack_debug_printf(stderr, " index=%llu", (unsigned long long)index); +#endif + + /* RFC9204 2.2.3 Invalid References + * + * If the decoder encounters a reference in a field line representation + * to a dynamic table entry that has already been evicted or that has an + * absolute index greater than or equal to the declared Required Insert + * Count (Section 4.5.1), it MUST treat this as a connection error of + * type QPACK_DECOMPRESSION_FAILED. + */ + return -QPACK_DECOMPRESSION_FAILED; + } + else if (efl_type & QPACK_IFL_BIT) { + /* Indexed field line */ + uint64_t index; + unsigned int static_tbl; + + qpack_debug_printf(stderr, "indexed field line:"); + static_tbl = efl_type & 0x40; + index = qpack_get_varint(&raw, &len, 6); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + if (static_tbl && index < QPACK_SHT_SIZE) { + name = qpack_sht[index].n; + value = qpack_sht[index].v; + } + else { + /* RFC9204 2.2.3 Invalid References + * + * If the decoder encounters a reference in a field line representation + * to a dynamic table entry that has already been evicted or that has an + * absolute index greater than or equal to the declared Required Insert + * Count (Section 4.5.1), it MUST treat this as a connection error of + * type QPACK_DECOMPRESSION_FAILED. + * + * TODO adjust this when dynamic table support is implemented. + */ + return -QPACK_DECOMPRESSION_FAILED; + } + + qpack_debug_printf(stderr, " t=%d index=%llu", !!static_tbl, (unsigned long long)index); + } + else if (efl_type & QPACK_LFL_WNR_BIT) { + /* Literal field line with name reference */ + uint64_t index, length; + unsigned int static_tbl, n __maybe_unused, h; + + qpack_debug_printf(stderr, "Literal field line with name reference:"); + n = efl_type & 0x20; + static_tbl = efl_type & 0x10; + index = qpack_get_varint(&raw, &len, 4); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + if (static_tbl && index < QPACK_SHT_SIZE) { + name = qpack_sht[index].n; + } + else { + /* RFC9204 2.2.3 Invalid References + * + * If the decoder encounters a reference in a field line representation + * to a dynamic table entry that has already been evicted or that has an + * absolute index greater than or equal to the declared Required Insert + * Count (Section 4.5.1), it MUST treat this as a connection error of + * type QPACK_DECOMPRESSION_FAILED. + * + * TODO adjust this when dynamic table support is implemented. + */ + return -QPACK_DECOMPRESSION_FAILED; + } + + qpack_debug_printf(stderr, " n=%d t=%d index=%llu", !!n, !!static_tbl, (unsigned long long)index); + h = *raw & 0x80; + length = qpack_get_varint(&raw, &len, 7); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + qpack_debug_printf(stderr, " h=%d length=%llu", !!h, (unsigned long long)length); + if (h) { + char *trash; + int nlen; + + trash = chunk_newstr(tmp); + if (!trash) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_DECOMPRESSION_FAILED; + goto out; + } + nlen = huff_dec(raw, length, trash, tmp->size - tmp->data); + if (nlen == (uint32_t)-1) { + qpack_debug_printf(stderr, " can't decode huffman.\n"); + ret = -QPACK_ERR_HUFFMAN; + goto out; + } + + qpack_debug_printf(stderr, " [name huff %d->%d '%s']", (int)length, (int)nlen, trash); + /* makes an ist from tmp storage */ + b_add(tmp, nlen); + value = ist2(trash, nlen); + } + else { + value = ist2(raw, length); + } + + if (len < length) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + raw += length; + len -= length; + } + else if (efl_type & QPACK_LFL_WLN_BIT) { + /* Literal field line with literal name */ + unsigned int n __maybe_unused, hname, hvalue; + uint64_t name_len, value_len; + + qpack_debug_printf(stderr, "Literal field line with literal name:"); + n = *raw & 0x10; + hname = *raw & 0x08; + name_len = qpack_get_varint(&raw, &len, 3); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + qpack_debug_printf(stderr, " n=%d hname=%d name_len=%llu", !!n, !!hname, (unsigned long long)name_len); + /* Name string */ + + if (len < name_len) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + if (hname) { + char *trash; + int nlen; + + trash = chunk_newstr(tmp); + if (!trash) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_DECOMPRESSION_FAILED; + goto out; + } + nlen = huff_dec(raw, name_len, trash, tmp->size - tmp->data); + if (nlen == (uint32_t)-1) { + qpack_debug_printf(stderr, " can't decode huffman.\n"); + ret = -QPACK_ERR_HUFFMAN; + goto out; + } + + qpack_debug_printf(stderr, " [name huff %d->%d '%s']", (int)name_len, (int)nlen, trash); + /* makes an ist from tmp storage */ + b_add(tmp, nlen); + name = ist2(trash, nlen); + } + else { + name = ist2(raw, name_len); + } + + raw += name_len; + len -= name_len; + + hvalue = *raw & 0x80; + value_len = qpack_get_varint(&raw, &len, 7); + if (len == (uint64_t)-1) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + qpack_debug_printf(stderr, " hvalue=%d value_len=%llu", !!hvalue, (unsigned long long)value_len); + + if (len < value_len) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TRUNCATED; + goto out; + } + + if (hvalue) { + char *trash; + int nlen; + + trash = chunk_newstr(tmp); + if (!trash) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_DECOMPRESSION_FAILED; + goto out; + } + nlen = huff_dec(raw, value_len, trash, tmp->size - tmp->data); + if (nlen == (uint32_t)-1) { + qpack_debug_printf(stderr, " can't decode huffman.\n"); + ret = -QPACK_ERR_HUFFMAN; + goto out; + } + + qpack_debug_printf(stderr, " [name huff %d->%d '%s']", (int)value_len, (int)nlen, trash); + /* makes an ist from tmp storage */ + b_add(tmp, nlen); + value = ist2(trash, nlen); + } + else { + value = ist2(raw, value_len); + } + + raw += value_len; + len -= value_len; + } + + /* We must not accept empty header names (forbidden by the spec and used + * as a list termination). + */ + if (!name.len) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_DECOMPRESSION_FAILED; + goto out; + } + + list[hdr_idx].n = name; + list[hdr_idx].v = value; + ++hdr_idx; + + qpack_debug_printf(stderr, "\n"); + } + + if (hdr_idx >= list_size) { + qpack_debug_printf(stderr, "##ERR@%d\n", __LINE__); + ret = -QPACK_ERR_TOO_LARGE; + goto out; + } + + /* put an end marker */ + list[hdr_idx].n = list[hdr_idx].v = IST_NULL; + ret = hdr_idx; + + out: + qpack_debug_printf(stderr, "-- done: ret=%d\n", ret); + return ret; +} |