cellos-supervisor 0.5.1

//! HPACK static Huffman decoder (RFC 7541 Appendix B).
//!
//! The 257-symbol canonical code table from RFC 7541 Appendix B is encoded
//! verbatim as `(code, length)` pairs indexed by symbol (0..=255 for octets;
//! 256 is the EOS symbol — MUST NOT appear in encoded streams). We decode
//! bit-by-bit through the bitstream, accumulating up to `length` bits at a
//! time, looking up by `(accumulated_bits, length_so_far)`. Choice rationale:
//!
//! * **Bit-by-bit** is ~50 lines of arithmetic with no precomputed structures
//!   — less code to audit than a multi-megabyte lookup table approach.
//! * The proxy decodes :authority — bounded by RFC 7230 §3.2.3 to 253 octets;
//!   the bit-by-bit cost is negligible relative to the network round-trip the
//!   proxy is gating.
//! * No `unsafe`, no `static mut`, no allocator pressure beyond the output
//!   `String` itself.
//!
//! ## RFC 7541 §5.2 rejection rules
//!
//! * The EOS symbol (#256, 30-bit code `0x3FFFFFFF`) MUST NOT appear in the
//!   encoded stream — emit [`H2ParseError::HuffmanInvalid`] if matched.
//! * Padding MUST be the most-significant bits of the EOS code AND MUST NOT
//!   exceed 7 bits — anything else is malformed.
//! * Defence-in-depth: cap decoded length at [`MAX_DECODED_LEN`] (8 KiB).
//!   `:authority` is bounded to 253 octets but other headers may use this
//!   path in future slices; 8 KiB is generous and bounds memory.

use super::super::error::H2ParseError;

/// RFC 7541 Appendix B canonical Huffman code table. One entry per symbol.
/// Symbol 256 is the EOS marker.
const HUFFMAN_TABLE: [(u32, u8); 257] = [
    (0x00001ff8, 13), // 0
    (0x007fffd8, 23), // 1
    (0x0fffffe2, 28), // 2
    (0x0fffffe3, 28), // 3
    (0x0fffffe4, 28), // 4
    (0x0fffffe5, 28), // 5
    (0x0fffffe6, 28), // 6
    (0x0fffffe7, 28), // 7
    (0x0fffffe8, 28), // 8
    (0x00ffffea, 24), // 9
    (0x3ffffffc, 30), // 10
    (0x0fffffe9, 28), // 11
    (0x0fffffea, 28), // 12
    (0x3ffffffd, 30), // 13
    (0x0fffffeb, 28), // 14
    (0x0fffffec, 28), // 15
    (0x0fffffed, 28), // 16
    (0x0fffffee, 28), // 17
    (0x0fffffef, 28), // 18
    (0x0ffffff0, 28), // 19
    (0x0ffffff1, 28), // 20
    (0x0ffffff2, 28), // 21
    (0x3ffffffe, 30), // 22
    (0x0ffffff3, 28), // 23
    (0x0ffffff4, 28), // 24
    (0x0ffffff5, 28), // 25
    (0x0ffffff6, 28), // 26
    (0x0ffffff7, 28), // 27
    (0x0ffffff8, 28), // 28
    (0x0ffffff9, 28), // 29
    (0x0ffffffa, 28), // 30
    (0x0ffffffb, 28), // 31
    (0x00000014, 6),  // 32 ' '
    (0x000003f8, 10), // 33 '!'
    (0x000003f9, 10), // 34 '"'
    (0x00000ffa, 12), // 35 '#'
    (0x00001ff9, 13), // 36 '$'
    (0x00000015, 6),  // 37 '%'
    (0x000000f8, 8),  // 38 '&'
    (0x000007fa, 11), // 39 '\''
    (0x000003fa, 10), // 40 '('
    (0x000003fb, 10), // 41 ')'
    (0x000000f9, 8),  // 42 '*'
    (0x000007fb, 11), // 43 '+'
    (0x000000fa, 8),  // 44 ','
    (0x00000016, 6),  // 45 '-'
    (0x00000017, 6),  // 46 '.'
    (0x00000018, 6),  // 47 '/'
    (0x00000000, 5),  // 48 '0'
    (0x00000001, 5),  // 49 '1'
    (0x00000002, 5),  // 50 '2'
    (0x00000019, 6),  // 51 '3'
    (0x0000001a, 6),  // 52 '4'
    (0x0000001b, 6),  // 53 '5'
    (0x0000001c, 6),  // 54 '6'
    (0x0000001d, 6),  // 55 '7'
    (0x0000001e, 6),  // 56 '8'
    (0x0000001f, 6),  // 57 '9'
    (0x0000005c, 7),  // 58 ':'
    (0x000000fb, 8),  // 59 ';'
    (0x00007ffc, 15), // 60 '<'
    (0x00000020, 6),  // 61 '='
    (0x00000ffb, 12), // 62 '>'
    (0x000003fc, 10), // 63 '?'
    (0x00001ffa, 13), // 64 '@'
    (0x00000021, 6),  // 65 'A'
    (0x0000005d, 7),  // 66 'B'
    (0x0000005e, 7),  // 67 'C'
    (0x0000005f, 7),  // 68 'D'
    (0x00000060, 7),  // 69 'E'
    (0x00000061, 7),  // 70 'F'
    (0x00000062, 7),  // 71 'G'
    (0x00000063, 7),  // 72 'H'
    (0x00000064, 7),  // 73 'I'
    (0x00000065, 7),  // 74 'J'
    (0x00000066, 7),  // 75 'K'
    (0x00000067, 7),  // 76 'L'
    (0x00000068, 7),  // 77 'M'
    (0x00000069, 7),  // 78 'N'
    (0x0000006a, 7),  // 79 'O'
    (0x0000006b, 7),  // 80 'P'
    (0x0000006c, 7),  // 81 'Q'
    (0x0000006d, 7),  // 82 'R'
    (0x0000006e, 7),  // 83 'S'
    (0x0000006f, 7),  // 84 'T'
    (0x00000070, 7),  // 85 'U'
    (0x00000071, 7),  // 86 'V'
    (0x00000072, 7),  // 87 'W'
    (0x000000fc, 8),  // 88 'X'
    (0x00000073, 7),  // 89 'Y'
    (0x000000fd, 8),  // 90 'Z'
    (0x00001ffb, 13), // 91 '['
    (0x0007fff0, 19), // 92 '\\'
    (0x00001ffc, 13), // 93 ']'
    (0x00003ffc, 14), // 94 '^'
    (0x00000022, 6),  // 95 '_'
    (0x00007ffd, 15), // 96 '`'
    (0x00000003, 5),  // 97 'a'
    (0x00000023, 6),  // 98 'b'
    (0x00000004, 5),  // 99 'c'
    (0x00000024, 6),  // 100 'd'
    (0x00000005, 5),  // 101 'e'
    (0x00000025, 6),  // 102 'f'
    (0x00000026, 6),  // 103 'g'
    (0x00000027, 6),  // 104 'h'
    (0x00000006, 5),  // 105 'i'
    (0x00000074, 7),  // 106 'j'
    (0x00000075, 7),  // 107 'k'
    (0x00000028, 6),  // 108 'l'
    (0x00000029, 6),  // 109 'm'
    (0x0000002a, 6),  // 110 'n'
    (0x00000007, 5),  // 111 'o'
    (0x0000002b, 6),  // 112 'p'
    (0x00000076, 7),  // 113 'q'
    (0x0000002c, 6),  // 114 'r'
    (0x00000008, 5),  // 115 's'
    (0x00000009, 5),  // 116 't'
    (0x0000002d, 6),  // 117 'u'
    (0x00000077, 7),  // 118 'v'
    (0x00000078, 7),  // 119 'w'
    (0x00000079, 7),  // 120 'x'
    (0x0000007a, 7),  // 121 'y'
    (0x0000007b, 7),  // 122 'z'
    (0x00007ffe, 15), // 123 '{'
    (0x000007fc, 11), // 124 '|'
    (0x00003ffd, 14), // 125 '}'
    (0x00001ffd, 13), // 126 '~'
    (0x0ffffffc, 28), // 127
    (0x000fffe6, 20), // 128
    (0x003fffd2, 22), // 129
    (0x000fffe7, 20), // 130
    (0x000fffe8, 20), // 131
    (0x003fffd3, 22), // 132
    (0x003fffd4, 22), // 133
    (0x003fffd5, 22), // 134
    (0x007fffd9, 23), // 135
    (0x003fffd6, 22), // 136
    (0x007fffda, 23), // 137
    (0x007fffdb, 23), // 138
    (0x007fffdc, 23), // 139
    (0x007fffdd, 23), // 140
    (0x007fffde, 23), // 141
    (0x00ffffeb, 24), // 142
    (0x007fffdf, 23), // 143
    (0x00ffffec, 24), // 144
    (0x00ffffed, 24), // 145
    (0x003fffd7, 22), // 146
    (0x007fffe0, 23), // 147
    (0x00ffffee, 24), // 148
    (0x007fffe1, 23), // 149
    (0x007fffe2, 23), // 150
    (0x007fffe3, 23), // 151
    (0x007fffe4, 23), // 152
    (0x001fffdc, 21), // 153
    (0x003fffd8, 22), // 154
    (0x007fffe5, 23), // 155
    (0x003fffd9, 22), // 156
    (0x007fffe6, 23), // 157
    (0x007fffe7, 23), // 158
    (0x00ffffef, 24), // 159
    (0x003fffda, 22), // 160
    (0x001fffdd, 21), // 161
    (0x000fffe9, 20), // 162
    (0x003fffdb, 22), // 163
    (0x003fffdc, 22), // 164
    (0x007fffe8, 23), // 165
    (0x007fffe9, 23), // 166
    (0x001fffde, 21), // 167
    (0x007fffea, 23), // 168
    (0x003fffdd, 22), // 169
    (0x003fffde, 22), // 170
    (0x00fffff0, 24), // 171
    (0x001fffdf, 21), // 172
    (0x003fffdf, 22), // 173
    (0x007fffeb, 23), // 174
    (0x007fffec, 23), // 175
    (0x001fffe0, 21), // 176
    (0x001fffe1, 21), // 177
    (0x003fffe0, 22), // 178
    (0x001fffe2, 21), // 179
    (0x007fffed, 23), // 180
    (0x003fffe1, 22), // 181
    (0x007fffee, 23), // 182
    (0x007fffef, 23), // 183
    (0x000fffea, 20), // 184
    (0x003fffe2, 22), // 185
    (0x003fffe3, 22), // 186
    (0x003fffe4, 22), // 187
    (0x007ffff0, 23), // 188
    (0x003fffe5, 22), // 189
    (0x003fffe6, 22), // 190
    (0x007ffff1, 23), // 191
    (0x03ffffe0, 26), // 192
    (0x03ffffe1, 26), // 193
    (0x000fffeb, 20), // 194
    (0x0007fff1, 19), // 195
    (0x003fffe7, 22), // 196
    (0x007ffff2, 23), // 197
    (0x003fffe8, 22), // 198
    (0x01ffffec, 25), // 199
    (0x03ffffe2, 26), // 200
    (0x03ffffe3, 26), // 201
    (0x03ffffe4, 26), // 202
    (0x07ffffde, 27), // 203
    (0x07ffffdf, 27), // 204
    (0x03ffffe5, 26), // 205
    (0x00fffff1, 24), // 206
    (0x01ffffed, 25), // 207
    (0x0007fff2, 19), // 208
    (0x001fffe3, 21), // 209
    (0x03ffffe6, 26), // 210
    (0x07ffffe0, 27), // 211
    (0x07ffffe1, 27), // 212
    (0x03ffffe7, 26), // 213
    (0x07ffffe2, 27), // 214
    (0x00fffff2, 24), // 215
    (0x001fffe4, 21), // 216
    (0x001fffe5, 21), // 217
    (0x03ffffe8, 26), // 218
    (0x03ffffe9, 26), // 219
    (0x0ffffffd, 28), // 220
    (0x07ffffe3, 27), // 221
    (0x07ffffe4, 27), // 222
    (0x07ffffe5, 27), // 223
    (0x000fffec, 20), // 224
    (0x00fffff3, 24), // 225
    (0x000fffed, 20), // 226
    (0x001fffe6, 21), // 227
    (0x003fffe9, 22), // 228
    (0x001fffe7, 21), // 229
    (0x001fffe8, 21), // 230
    (0x007ffff3, 23), // 231
    (0x003fffea, 22), // 232
    (0x003fffeb, 22), // 233
    (0x01ffffee, 25), // 234
    (0x01ffffef, 25), // 235
    (0x00fffff4, 24), // 236
    (0x00fffff5, 24), // 237
    (0x03ffffea, 26), // 238
    (0x007ffff4, 23), // 239
    (0x03ffffeb, 26), // 240
    (0x07ffffe6, 27), // 241
    (0x03ffffec, 26), // 242
    (0x03ffffed, 26), // 243
    (0x07ffffe7, 27), // 244
    (0x07ffffe8, 27), // 245
    (0x07ffffe9, 27), // 246
    (0x07ffffea, 27), // 247
    (0x07ffffeb, 27), // 248
    (0x0ffffffe, 28), // 249
    (0x07ffffec, 27), // 250
    (0x07ffffed, 27), // 251
    (0x07ffffee, 27), // 252
    (0x07ffffef, 27), // 253
    (0x07fffff0, 27), // 254
    (0x03ffffee, 26), // 255
    (0x3fffffff, 30), // 256 EOS
];

/// EOS symbol id per RFC 7541 §5.2.
const EOS_SYMBOL: usize = 256;

/// Maximum decoded length we accept. `:authority` is bounded by RFC 7230
/// §3.2.3 to 253 octets but be generous to allow other headers in the
/// future. 8 KiB.
pub const MAX_DECODED_LEN: usize = 8 * 1024;

/// Decode a Huffman-coded byte stream into a `String`.
///
/// Implementation: bit-by-bit walk. We maintain `accum` (current code being
/// built — left-aligned into a 32-bit integer) and `bits` (length of
/// `accum`). On each byte from the input, fold the 8 new bits in. After
/// each bit added, scan the table for a match where the symbol's encoded
/// length equals `bits` and its left-aligned code equals the accumulator —
/// if the EOS symbol matches, reject.
///
/// To keep the inner loop cheap, we precompute the *left-aligned* form of
/// each table entry and the ranges of entries by code length. RFC 7541
/// codes are at most 30 bits so we do all work in `u32`.
pub fn decode(input: &[u8]) -> Result<String, H2ParseError> {
    let mut out: Vec<u8> = Vec::new();
    // `accum` holds the bits we've consumed but not yet matched, **left-
    // aligned** in a 32-bit accumulator. `bits` is how many bits are valid.
    let mut accum: u32 = 0;
    let mut bits: u32 = 0;

    for &byte in input {
        // Fold this byte into the accumulator (left-shift by 8 then OR).
        // We keep up to 30 unmatched bits at a time; if `bits + 8 > 32`
        // we have a malformed stream (no valid prefix in 30 bits of input).
        if bits > 24 {
            // We should have decoded SOMETHING in the last 24 bits — RFC 7541
            // codes are at most 30 bits and any prefix of valid input
            // resolves within 30 bits. If we haven't decoded for >24 bits
            // and another byte arrives, the stream is malformed.
            return Err(H2ParseError::HuffmanInvalid);
        }
        accum |= (byte as u32) << (24 - bits);
        bits += 8;

        // Try to peel as many symbols as we can from the accumulator.
        loop {
            if bits == 0 {
                break;
            }
            // Find the shortest matching symbol whose code length ≤ bits.
            // The Huffman code is canonical and prefix-free; for each
            // length we mask the top `len` bits of `accum` (i.e. accum >>
            // (32 - len)) and compare against the symbol's stored code.
            let mut matched: Option<(usize, u8)> = None;
            for len in 5..=30u8 {
                if (len as u32) > bits {
                    break;
                }
                let candidate = accum >> (32 - len as u32);
                // Symbols with this length: linear scan. The 256-symbol
                // table is small enough that this is cheap; sub-millisecond
                // even for kilobyte-scale inputs.
                for (sym, (code, code_len)) in HUFFMAN_TABLE.iter().enumerate() {
                    if *code_len == len && *code == candidate {
                        matched = Some((sym, len));
                        break;
                    }
                }
                if matched.is_some() {
                    break;
                }
            }

            let (sym, len) = match matched {
                Some(m) => m,
                None => break, // need more bits
            };

            if sym == EOS_SYMBOL {
                // RFC 7541 §5.2: EOS MUST NOT appear in the encoded stream.
                return Err(H2ParseError::HuffmanInvalid);
            }

            // Consume `len` bits.
            accum <<= len;
            bits -= len as u32;
            out.push(sym as u8);

            if out.len() > MAX_DECODED_LEN {
                return Err(H2ParseError::HuffmanOversized {
                    max: MAX_DECODED_LEN,
                });
            }
        }
    }

    // RFC 7541 §5.2: pad MUST be the most-significant bits of the EOS code
    // (which begins with all-ones) AND MUST NOT exceed 7 bits.
    if bits > 7 {
        return Err(H2ParseError::HuffmanInvalid);
    }
    if bits > 0 {
        // The remaining `bits` bits MUST all be ones (top bits of EOS).
        let mask = ((1u32 << bits) - 1) << (32 - bits);
        if accum & mask != mask {
            return Err(H2ParseError::HuffmanInvalid);
        }
    }

    String::from_utf8(out).map_err(|_| H2ParseError::NonAsciiAuthority)
}

/// Test-only encoder: produce a Huffman-coded byte string of `s`. NOT used
/// in production — the proxy never encodes.
#[cfg(test)]
pub fn encode(s: &str) -> Vec<u8> {
    let mut out: Vec<u8> = Vec::new();
    let mut accum: u64 = 0;
    let mut bits: u32 = 0;
    for &b in s.as_bytes() {
        let (code, len) = HUFFMAN_TABLE[b as usize];
        accum = (accum << len) | (code as u64);
        bits += len as u32;
        while bits >= 8 {
            bits -= 8;
            let byte = ((accum >> bits) & 0xFF) as u8;
            out.push(byte);
        }
    }
    if bits > 0 {
        // Pad with EOS-prefix ones.
        let pad = 8 - bits;
        accum = (accum << pad) | ((1u64 << pad) - 1);
        out.push((accum & 0xFF) as u8);
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn decodes_empty_string() {
        assert_eq!(decode(&[]).unwrap(), "");
    }

    #[test]
    fn decodes_short_authority() {
        let encoded = encode("a.com");
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, "a.com");
    }

    #[test]
    fn decodes_lowercase_authority_value() {
        let encoded = encode("api.example.com");
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, "api.example.com");
    }

    #[test]
    fn decodes_authority_with_dot_and_dash() {
        let encoded = encode("my-service.example.com");
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, "my-service.example.com");
    }

    #[test]
    fn decodes_long_authority() {
        let s = "very-long-subdomain-of-example.com";
        let encoded = encode(s);
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, s);
    }

    #[test]
    fn decodes_authority_starting_with_digit() {
        let encoded = encode("3rd-party.example.com");
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, "3rd-party.example.com");
    }

    #[test]
    fn decodes_punycode_a_label() {
        // Punycode IDN labels are pure ASCII (`xn--...`) — Huffman handles
        // them natively without any IDN-aware logic.
        let encoded = encode("xn--nxasmq6b");
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, "xn--nxasmq6b");
    }

    #[test]
    fn decodes_authority_with_port_then_round_trip() {
        let s = "api.example.com:8443";
        let encoded = encode(s);
        let decoded = decode(&encoded).unwrap();
        assert_eq!(decoded, s);
    }

    #[test]
    fn rejects_eos_symbol_in_stream() {
        // EOS code is 0x3FFFFFFF over 30 bits. Pack it left-aligned into 4
        // bytes (32 bits), pad the remaining 2 bits with ones (EOS prefix).
        // Layout: 0x3FFFFFFF << 2 | 0b11 = 0xFFFFFFFF.
        let bytes = [0xFF, 0xFF, 0xFF, 0xFF];
        let err = decode(&bytes).unwrap_err();
        assert_eq!(err, H2ParseError::HuffmanInvalid);
    }

    #[test]
    fn rejects_oversized_decoded_output() {
        // Encode a string just over MAX_DECODED_LEN. 'a' (5-bit code) ×
        // (MAX_DECODED_LEN + 1) → encoded is well under 8 KiB but decoded
        // is over.
        let s: String = std::iter::repeat_n('a', MAX_DECODED_LEN + 1).collect();
        let encoded = encode(&s);
        let err = decode(&encoded).unwrap_err();
        assert!(matches!(err, H2ParseError::HuffmanOversized { .. }));
    }

    #[test]
    fn rejects_too_long_padding() {
        // Encode 'a' (5-bit code = 0b00011) then append a full extra byte
        // of all-ones — that's 13 bits of padding, well over the 7-bit
        // limit. Must reject.
        let mut bytes = encode("a"); // 1 byte, 3 bits of pad
        bytes.push(0xFF);
        let err = decode(&bytes).unwrap_err();
        assert_eq!(err, H2ParseError::HuffmanInvalid);
    }

    #[test]
    fn rejects_non_eos_padding() {
        // Encode 'a' then flip the last bit to 0 — the 3 padding bits no
        // longer match the EOS top-bits-are-ones requirement.
        let mut bytes = encode("a");
        let last = bytes.len() - 1;
        bytes[last] &= 0xFE; // clear bit 0 → padding has a 0 in it
        let err = decode(&bytes).unwrap_err();
        assert_eq!(err, H2ParseError::HuffmanInvalid);
    }
}