// Copyright (c) 2019-2024 Alexander Medvednikov. All rights reserved.
// Use of this source code is governed by an MIT license
// that can be found in the LICENSE file.
module http

// This file implements HPACK header compression (RFC 7541), used by HTTP/2.
// It is self-contained: it only depends on the static and Huffman tables in
// the sibling h2_hpack_*.v files, and does not touch the rest of net.http.

// h2_hpack_default_table_size is the default maximum size of the HPACK
// dynamic table, in bytes (RFC 7541 Section 4.2, and the default value of
// SETTINGS_HEADER_TABLE_SIZE).
pub const h2_hpack_default_table_size = 4096

// H2HeaderField is a single HTTP/2 header field (a name/value pair).
// Field names are expected to be lowercase, as required by RFC 7540.
pub struct H2HeaderField {
pub:
    name  string
    value string
}

// H2DynEntry is one entry in the HPACK dynamic table.
struct H2DynEntry {
    name  string
    value string
    size  int // name.len + value.len + 32 (RFC 7541 Section 4.1)
}

// H2DynTable is the HPACK dynamic table: a size-bounded FIFO of header fields.
// entries[0] is always the most recently added entry, which corresponds to the
// lowest dynamic index in the HPACK index space.
struct H2DynTable {
mut:
    entries  []H2DynEntry
    cur_size int
    max_size int = h2_hpack_default_table_size
}

// add inserts a new entry at the front of the table, evicting the oldest
// entries until it fits. Per RFC 7541 Section 4.4, an entry larger than the
// whole table empties it and is not added.
fn (mut t H2DynTable) add(name string, value string) {
    sz := name.len + value.len + 32
    for t.entries.len > 0 && t.cur_size + sz > t.max_size {
        t.cur_size -= t.entries.last().size
        t.entries.delete_last()
    }
    if sz > t.max_size {
        return
    }
    t.entries.insert(0, H2DynEntry{
        name:  name
        value: value
        size:  sz
    })
    t.cur_size += sz
}

// set_max_size updates the maximum table size, evicting oldest entries as
// needed to respect the new limit.
fn (mut t H2DynTable) set_max_size(n int) {
    t.max_size = n
    for t.entries.len > 0 && t.cur_size > t.max_size {
        t.cur_size -= t.entries.last().size
        t.entries.delete_last()
    }
}

// get returns the dynamic-table entry at 1-based dynamic index `i`
// (i.e. i==1 is the newest entry), or none if out of range.
fn (t &H2DynTable) get(i int) ?H2HeaderField {
    if i < 1 || i > t.entries.len {
        return none
    }
    e := t.entries[i - 1]
    return H2HeaderField{
        name:  e.name
        value: e.value
    }
}

// H2HpackReader is a cursor over an HPACK header block being decoded.
struct H2HpackReader {
    buf []u8
mut:
    pos int
}

// read_int reads an HPACK variable-length integer with a prefix of
// `prefix_bits` bits at the current position, advancing past it
// (RFC 7541 Section 5.1).
fn (mut r H2HpackReader) read_int(prefix_bits int) !u64 {
    if r.pos >= r.buf.len {
        return error('hpack: integer truncated')
    }
    max_prefix := u64((1 << prefix_bits) - 1)
    mut value := u64(r.buf[r.pos]) & max_prefix
    r.pos++
    if value < max_prefix {
        return value
    }
    mut m := 0
    for {
        if r.pos >= r.buf.len {
            return error('hpack: integer continuation truncated')
        }
        b := r.buf[r.pos]
        r.pos++
        value += u64(b & 0x7f) << m
        m += 7
        // A 64-bit value never needs more than 9 continuation bytes; reject
        // pathological inputs early (RFC 7541 Section 5.1 security note).
        if m > 63 {
            return error('hpack: integer overflow')
        }
        if b & 0x80 == 0 {
            break
        }
    }
    return value
}

// read_string reads an HPACK string literal at the current position,
// advancing past it and decoding Huffman coding when the H bit is set.
fn (mut r H2HpackReader) read_string() !string {
    if r.pos >= r.buf.len {
        return error('hpack: string truncated')
    }
    huffman := (r.buf[r.pos] & 0x80) != 0
    length := r.read_int(7)!
    // Compare in u64 space, before narrowing to int, so an oversized length
    // from a malicious peer cannot truncate past this bounds check.
    if length > u64(r.buf.len - r.pos) {
        return error('hpack: string length exceeds buffer')
    }
    n := int(length)
    raw := r.buf[r.pos..r.pos + n]
    r.pos += n
    if huffman {
        return h2_huffman_decode(raw)!.bytestr()
    }
    return raw.bytestr()
}

// h2_hpack_write_int appends an HPACK variable-length integer to `out`, using
// a prefix of `prefix_bits` bits whose high bits are set from `high_bits`.
fn h2_hpack_write_int(mut out []u8, value u64, prefix_bits int, high_bits u8) {
    max_prefix := u64((1 << prefix_bits) - 1)
    if value < max_prefix {
        out << high_bits | u8(value)
        return
    }
    out << high_bits | u8(max_prefix)
    mut v := value - max_prefix
    for v >= 0x80 {
        out << u8((v & 0x7f) | 0x80)
        v >>= 7
    }
    out << u8(v)
}

// h2_encode_string appends an HPACK string literal to `out`, choosing Huffman
// coding when it is shorter than the raw bytes (RFC 7541 Section 5.2).
fn h2_encode_string(mut out []u8, s string) {
    raw := s.bytes()
    huff := h2_huffman_encode(raw)
    if huff.len < raw.len {
        h2_hpack_write_int(mut out, u64(huff.len), 7, 0x80) // H = 1
        out << huff
    } else {
        h2_hpack_write_int(mut out, u64(raw.len), 7, 0x00) // H = 0
        out << raw
    }
}

// h2_is_sensitive reports whether a header should never be added to the HPACK
// dynamic table (encoded as "never indexed"), to avoid CRIME-style attacks.
fn h2_is_sensitive(name string) bool {
    return name == 'cookie' || name == 'authorization' || name == 'proxy-authorization'
}

// h2_hpack_find_static searches the static table for `name`/`value`.
// It returns the 1-based HPACK index and whether the value also matched.
// The index is 0 when the name is not present at all.
fn h2_hpack_find_static(name string, value string) (int, bool) {
    mut name_idx := 0
    for i, f in h2_hpack_static_table {
        if f.name == name {
            if f.value == value {
                return i + 1, true
            }
            if name_idx == 0 {
                name_idx = i + 1
            }
        }
    }
    return name_idx, false
}

// H2HpackEncoder encodes header field lists into HPACK header blocks.
// This encoder never adds entries to the dynamic table: it uses indexed
// representations for static-table hits and literal-without-indexing (or
// never-indexed, for sensitive headers) otherwise. That keeps encoder and
// decoder state trivially in sync while remaining fully interoperable.
pub struct H2HpackEncoder {
pub mut:
    dyn_table H2DynTable
}

// encode returns the HPACK header block for `fields`.
pub fn (mut e H2HpackEncoder) encode(fields []H2HeaderField) []u8 {
    mut out := []u8{}
    for f in fields {
        e.encode_field(mut out, f)
    }
    return out
}

fn (mut e H2HpackEncoder) encode_field(mut out []u8, f H2HeaderField) {
    sensitive := h2_is_sensitive(f.name)
    idx, exact := h2_hpack_find_static(f.name, f.value)
    if exact && !sensitive {
        // Indexed Header Field (RFC 7541 Section 6.1).
        h2_hpack_write_int(mut out, u64(idx), 7, 0x80)
        return
    }
    // Literal Header Field without Indexing (6.2.2) or Never Indexed (6.2.3).
    pattern := if sensitive { u8(0x10) } else { u8(0x00) }
    if idx != 0 {
        h2_hpack_write_int(mut out, u64(idx), 4, pattern)
    } else {
        h2_hpack_write_int(mut out, 0, 4, pattern)
        h2_encode_string(mut out, f.name)
    }
    h2_encode_string(mut out, f.value)
}

// H2HpackDecoder decodes HPACK header blocks into header field lists,
// maintaining the dynamic table across calls on the same connection.
pub struct H2HpackDecoder {
pub mut:
    dyn_table        H2DynTable
    max_dynamic_size int = h2_hpack_default_table_size // upper bound we advertised to the peer
}

// lookup resolves a 1-based HPACK index against the static and dynamic tables.
fn (d &H2HpackDecoder) lookup(idx u64) !H2HeaderField {
    if idx == 0 {
        return error('hpack: index 0 is not valid')
    }
    if idx <= u64(h2_hpack_static_len) {
        return h2_hpack_static_table[idx - 1]
    }
    // Validate the dynamic index in u64 space before narrowing to int, so an
    // out-of-range index from a malicious peer cannot truncate onto a valid
    // dynamic entry.
    dyn_idx := idx - u64(h2_hpack_static_len)
    if dyn_idx > u64(d.dyn_table.entries.len) {
        return error('hpack: index ${idx} out of range')
    }
    return d.dyn_table.get(int(dyn_idx)) or { error('hpack: index ${idx} out of range') }
}

fn (d &H2HpackDecoder) read_literal(mut r H2HpackReader, prefix_bits int) !H2HeaderField {
    name_index := r.read_int(prefix_bits)!
    name := if name_index == 0 {
        r.read_string()!
    } else {
        d.lookup(name_index)!.name
    }
    value := r.read_string()!
    return H2HeaderField{
        name:  name
        value: value
    }
}

// decode parses one HPACK header block and returns its header fields,
// updating the dynamic table as instructed by the block.
pub fn (mut d H2HpackDecoder) decode(block []u8) ![]H2HeaderField {
    mut out := []H2HeaderField{}
    mut r := H2HpackReader{
        buf: block
    }
    mut seen_field := false
    for r.pos < block.len {
        b := block[r.pos]
        if b & 0x80 != 0 {
            // Indexed Header Field (RFC 7541 Section 6.1).
            idx := r.read_int(7)!
            out << d.lookup(idx)!
            seen_field = true
        } else if b & 0x40 != 0 {
            // Literal Header Field with Incremental Indexing (6.2.1).
            f := d.read_literal(mut r, 6)!
            d.dyn_table.add(f.name, f.value)
            out << f
            seen_field = true
        } else if b & 0x20 != 0 {
            // Dynamic Table Size Update (6.3). Must precede any header field.
            if seen_field {
                return error('hpack: dynamic table size update after a header field')
            }
            new_size := r.read_int(5)!
            if int(new_size) > d.max_dynamic_size {
                return error('hpack: dynamic table size update ${new_size} exceeds limit ${d.max_dynamic_size}')
            }
            d.dyn_table.set_max_size(int(new_size))
        } else {
            // Literal without Indexing (6.2.2) or Never Indexed (6.2.3);
            // neither updates the dynamic table.
            f := d.read_literal(mut r, 4)!
            out << f
            seen_field = true
        }
    }
    return out
}

// set_max_dynamic_size updates the maximum dynamic-table size the decoder will
// accept (i.e. the SETTINGS_HEADER_TABLE_SIZE value advertised to the peer),
// shrinking the table immediately if needed.
pub fn (mut d H2HpackDecoder) set_max_dynamic_size(n int) {
    d.max_dynamic_size = n
    if d.dyn_table.max_size > n {
        d.dyn_table.set_max_size(n)
    }
}