nish/net/hpack

HPACK, the header compression of HTTP/2, as RFC 7541 defines it: the §5.1 integer with an N-bit prefix, the §5.2 string literal with Appendix B's Huffman code, the Appendix A static table, the §2.3.2 dynamic table with its §4 size accounting and eviction, and the four §6 representations.

import {
  HPACK_COPY_FACTOR,
  HPACK_DEFAULT_TABLE_SIZE,
  HPACK_ENTRY_OVERHEAD,
  HPACK_ERR_COPY_BUDGET,
  HPACK_ERR_HUFFMAN_EOS,
  HPACK_ERR_HUFFMAN_PADDING,
  HPACK_ERR_INDEX,
  HPACK_ERR_INTEGER_OVERFLOW,
  HPACK_ERR_SIZE_UPDATE_MISSING,
  HPACK_ERR_SIZE_UPDATE_POSITION,
  HPACK_ERR_TABLE_SIZE,
  HPACK_ERR_TRUNCATED,
  HPACK_INDEX_INCREMENTAL,
  HPACK_INDEX_NEVER,
  HPACK_INDEX_WITHOUT,
  HPACK_LIST_TOO_LARGE,
  HPACK_OK,
  HPACK_STATIC_LENGTH,
  HpackCursor,
  HpackDecoder,
  HpackEncoder,
  HpackHuffman,
  HpackTable,
  HpackWork,
  hpackDecodeInteger,
  hpackDecodeString,
  hpackEncodeInteger,
  hpackEncodeString,
  hpackHuffmanDecode,
  hpackHuffmanEncode,
  hpackHuffmanLength,
} from "nish/net/hpack";
import { HpackDecoder, HpackEncoder, HPACK_INDEX_INCREMENTAL, HPACK_OK } from "nish/net/hpack";

const name: u8[] = [58, 112, 97, 116, 104];   // ":path"
const value: u8[] = [47];                     // "/"

const enc = new HpackEncoder(4096);
const block: u8[] = [];
enc.encodeField(block, name, value, HPACK_INDEX_INCREMENTAL, true);

const dec = new HpackDecoder(4096, 65536);
if (dec.decode(block, 0, toI32(block.length)) === HPACK_OK) {
  // dec.names[i], dec.values[i], dec.neverIndexed[i], until the next decode
}

It is sans-IO, like every lane of WP34 §5 below the sockets: a header block goes in as bytes and comes out as fields, and fields go in and come out as bytes. Framing the block (HEADERS and CONTINUATION) is HTTP/2's job, not this module's, so a block handed to HpackDecoder.decode is already whole.

Names and values are octets (u8[]), not strings, because a field value is an octet sequence (RFC 9113 §8.2.1) and HPACK neither knows nor checks what it spells. Checking a name or value is HTTP/2's job, one layer up.

The decoder refuses a block that would leave its table out of step with the peer's, and it answers a negative HPACK_ERR_* code: a block that ends inside a representation, an integer past 2^31 - 1 (or one padded past the five continuation bytes such an integer needs), an index of zero or past the end of the tables, Huffman padding longer than seven bits or not all ones, the EOS symbol inside a string, a table size update above the SETTINGS limit or after the block's first field, and a block that does not begin with the update a lowered limit requires (§4.2).

Each of those is HTTP/2's COMPRESSION_ERROR, which closes the connection, so the code is sticky: every later decode answers it again without reading anything. So is HPACK_ERR_COPY_BUDGET, a block that would make the table copy more than HPACK_COPY_FACTOR times the larger of its size and the block's length, which HTTP/2 answers with ENHANCE_YOUR_CALM.

A header list larger than the caller's limit is not one of them. The block is still decoded to its end, so that the table stays in step with the encoder's (RFC 9113 §10.5.1 requires it unless the connection closes), but the fields past the limit are dropped and decode answers HPACK_LIST_TOO_LARGE, which is positive: the next block decodes normally. HTTP/2 answers that one with a 431 or a stream reset, not a GOAWAY.

The encoder's choices are the caller's

Huffman or not is a per-field argument, as is the representation: incremental indexing, without indexing, or never indexed. A field the caller marks never indexed is always sent as a literal, even when the table holds it, so that an intermediary re-encoding it keeps it out of every table (§7.1.3). The encoder answers the smallest representation the tables allow otherwise, which is what RFC 7541 Appendix C's encoder does: a full match by index, else the name by index, the static table before the dynamic one and the lowest index first.

Nothing here is constant time. HPACK's secrets are protected by the never-indexed representation, not by the codec's timing (§7.1).

State is a class and dispatch is a switch, with no closures. A decoder answers its fields in arrays it owns and reuses, never the table's own octets, so a caller may change one without touching the table, and keeps one past the next decode by copying it. Once its arrays have grown to the largest block and header list the peer has sent, decoding allocates nothing, which bounds what a peer can make a connection hold (RFC 9113 §10.5.1; docs/security/http2.md, H2-1). Private helpers share the importing program's flat symbol namespace (docs/wp26-stdlib.md §3e), which is why each one carries the module's name.

Written from RFC 7541, not ported from another implementation. The Huffman code is Appendix B's, stored as its 257 code lengths: the code is canonical (shorter codes first, and symbols in order within a length), so the lengths alone determine every code, and tests/link/net_hpack_huffman checks each one against the appendix's table.

Functions

hpackDecodeInteger

Reads a §5.1 integer whose prefix is the low prefixBits bits of the byte at the cursor, and answers it, or HPACK_ERR_TRUNCATED or HPACK_ERR_INTEGER_OVERFLOW, both negative. A prefix outside 1 to 8 bits panics, as it does for hpackEncodeInteger.

An i32 needs at most five continuation bytes after a full prefix, so a sixth is refused even when its bits are zero; otherwise a run of 0x80 bytes would be read for as long as the peer cared to send it.

const hpackDecodeInteger: (
  c: HpackCursor,
  prefixBits: i32,
) => i32
cHpackCursorrequired

Where to read; its position moves past every byte read, also when the answer is an error.

prefixBitsi32required

How many low bits of the first byte hold the prefix, 1 to 8; the bits above are not read.

returnsi32

The integer, 0 to 2^31 - 1; HPACK_ERR_TRUNCATED when the cursor has no byte left before the integer ends, at the first byte or at a continuation byte; HPACK_ERR_INTEGER_OVERFLOW when the value passes 2^31 - 1, or when the fifth continuation byte still has its continuation bit set.

hpackDecodeString

Reads a §5.2 string literal at the cursor and appends its octets to out, answering HPACK_OK or a negative HPACK_ERR_* code. The length is checked against what the block has left before anything is read.

const hpackDecodeString: (
  h: HpackHuffman,
  c: HpackCursor,
  out: u8[],
) => i32
hHpackHuffmanrequired

The code to decode a Huffman-coded literal with.

cHpackCursorrequired

Where to read; on HPACK_OK its position is just past the literal. On an error it is wherever the read stopped.

outu8[]required

Where the string's octets go, appended after what it holds; on an error it keeps whatever was appended before the error, which a caller discards. The literal's length is bounded only by what the block has left, and a Huffman-coded one decodes to at most 8/5 of its coded length.

returnsi32

HPACK_OK when the literal was read whole; HPACK_ERR_TRUNCATED when the cursor has no byte left, the length integer ends early, or the length is more than the block has left after it; HPACK_ERR_INTEGER_OVERFLOW when the length passes 2^31 - 1 or is padded past five continuation bytes; HPACK_ERR_HUFFMAN_EOS or HPACK_ERR_HUFFMAN_PADDING from hpackHuffmanDecode for a Huffman-coded one.

hpackEncodeInteger

Appends value as a §5.1 integer with a prefixBits-bit prefix, the first byte's high bits being flags (the representation's pattern). A negative value, or a prefix outside 1 to 8 bits, panics: both are the program's choice.

const hpackEncodeInteger: (
  out: u8[],
  flags: i32,
  prefixBits: i32,
  value: i32,
) => void
outu8[]required

Where the integer's bytes go, appended after what it holds: one byte when value fits the prefix, else the prefix byte and one to five continuation bytes.

flagsi32required

The first byte's bits above the prefix; it must leave the low prefixBits bits clear, since they are or-ed with it.

prefixBitsi32required

How many low bits of the first byte the integer starts in, 1 to 8.

valuei32required

The integer, 0 to 2^31 - 1.

hpackEncodeString

Appends data as a §5.2 string literal: Huffman-coded when huffman is true, else raw. A caller who wants the shorter of the two compares hpackHuffmanLength with the raw length.

const hpackEncodeString: (
  h: HpackHuffman,
  out: u8[],
  data: u8[],
  huffman: boolean,
) => void
hHpackHuffmanrequired

The code to encode with when huffman is true.

outu8[]required

Where the literal goes, appended after what it holds: its length with a 7-bit prefix and the H bit, then the octets.

datau8[]required

The octets to write, all of them; only read.

huffmanbooleanrequired

Whether to Huffman-code them, even when that is longer than raw.

hpackHuffmanDecode

Appends the Huffman decoding of src[off, off + len) to out, and answers HPACK_OK, HPACK_ERR_HUFFMAN_EOS or HPACK_ERR_HUFFMAN_PADDING.

It reads one bit at a time, and after each one asks whether the bits since the last symbol are a code of their length. Because the code is complete, thirty bits always are. What is left when the input ends is padding, which §5.2 requires to be a prefix of EOS — all ones — and shorter than a byte. out keeps what was decoded before an error; a caller discards it. A window outside src panics.

const hpackHuffmanDecode: (
  h: HpackHuffman,
  src: u8[],
  off: i32,
  len: i32,
  out: u8[],
) => i32
hHpackHuffmanrequired

The code to decode with.

srcu8[]required

The coded bytes, the peer's; only read.

offi32required

Where the window starts, an index into src.

leni32required

How many bytes from off on to decode; every one is read unless an EOS comes first.

outu8[]required

Where the decoded octets go, appended after what it holds: at most len * 8 / 5 of them, since every code is at least five bits long.

returnsi32

HPACK_OK when the window decoded whole and ended in valid padding; HPACK_ERR_HUFFMAN_EOS when a complete code was the EOS symbol, at the point it was read; HPACK_ERR_HUFFMAN_PADDING when the bits left after the last symbol are more than seven or not all ones.

hpackHuffmanEncode

Appends src[off, off + len) Huffman-coded to out, padded to a byte with the most significant bits of EOS, which are all ones (§5.2).

The accumulator holds fewer than eight waiting bits between symbols, and a code is at most 30, so it never needs more than 37 bits. A window outside src panics.

const hpackHuffmanEncode: (
  h: HpackHuffman,
  src: u8[],
  off: i32,
  len: i32,
  out: u8[],
) => void
hHpackHuffmanrequired

The code to encode with.

srcu8[]required

The octets to encode; only read.

offi32required

Where the window starts, an index into src.

leni32required

How many octets from off on to encode.

outu8[]required

Where the coded bytes go: appended after what it holds, hpackHuffmanLength of them.

hpackHuffmanLength

The length of src[off, off + len) once Huffman-coded, in bytes, padding included. A window outside src panics, as does a coded length past 2^31 - 1 bytes.

const hpackHuffmanLength: (
  h: HpackHuffman,
  src: u8[],
  off: i32,
  len: i32,
) => i32
hHpackHuffmanrequired

The code to measure with.

srcu8[]required

The octets to measure; only read.

offi32required

Where the window starts, an index into src.

leni32required

How many octets from off on to measure.

returnsi32

The number of bytes hpackHuffmanEncode would append for the same window, 0 for an empty one.

Classes

HpackCursor

A read position in a header block: the bytes, where the next read starts, and where the block ends. The primitives below advance pos.

class HpackCursor
Member
new HpackCursor(buf: u8[], off: i32, len: i32) A cursor over buf[off, off + len), which must lie inside buf: a window outside it panics.
pos: i32 Where the next read starts, as an index into the cursor's buffer. hpackDecodeInteger and hpackDecodeString move it past what they read; after a negative answer it is wherever the read stopped, which a caller should not rely on.

HpackDecoder

One HTTP/2 connection's receiving side: its dynamic table, the SETTINGS limit the table may grow to, and the header-list limit.

decode answers the block's fields in names, values and neverIndexed, which it empties and refills on every call. Each name and value is an array the decoder owns, taken from its working storage's pools by its length and given back, emptied, at the next block, so a field is valid until the next decode: a caller that keeps one past it copies it, since the next block may refill the same array with another field.

That is what keeps the storage a peer can make a connection hold bounded by the header-list limit, however many blocks it sends and whatever becomes of their streams (docs/security/http2.md, H2-1): a class j array holds a field of at least 2^(j-1) octets, so no class ever holds more than about twice the limit, and only the classes up to log2 of the limit, plus one, hold any. settingsLimit is the SETTINGS_HEADER_TABLE_SIZE this endpoint advertised and the peer acknowledged; the table starts at it. maxHeaderListSize counts each field as its name, its value and 32 bytes, as SETTINGS_MAX_HEADER_LIST_SIZE does (RFC 9113 §6.5.2).

class HpackDecoder
Member
new HpackDecoder(settingsLimit: i32, maxHeaderListSize: i32) A decoder with an empty table, holding no working storage until the first decode.
maxHeaderListSize: i32 The header-list limit, in octets counted as RFC 9113 §6.5.2 counts them: the field that takes the block's running total past it, and every one after, is dropped and decode answers HPACK_LIST_TOO_LARGE.
names: u8[][] The names of the last block's fields, in order: the fields before the list passed its limit, and none after a negative answer. Each array is the decoder's, valid until the next decode.
neverIndexed: boolean[] Whether each field of the last block came never indexed (§6.2.3), by the same position as names.
settingsLimit: i32 The SETTINGS_HEADER_TABLE_SIZE in force, in octets: a size update above it is refused. Set by the constructor and setSettingsLimit, and put back to 4096 by http2.ts's restart.
table: HpackTable The dynamic table, as the blocks decoded so far have left it.
tableCopied: i64 The octets the decoder has moved through its dynamic table, counted where they move: each name or value it copies out of the dynamic table (a static entry's do not count), and each octet table.add pushes in. The budget (HPACK_COPY_FACTOR) is charged before a literal's copies, from the sizes it will copy; this counts what was copied, so that tests can hold the two equal. It is public so that tests can read it.
values: u8[][] The values of the last block's fields, by the same position as names, and valid as long.
decode(block: u8[], off: i32, len: i32): i32 Decodes one whole header block, block[off, off + len), and answers HPACK_OK, HPACK_LIST_TOO_LARGE or a negative HPACK_ERR_* code; the module comment lists what each means. After a negative answer the fields are empty and the decoder is spent.
setSettingsLimit(limit: i32): void Takes a new SETTINGS_HEADER_TABLE_SIZE, once the peer has acknowledged it. A limit below the table's current maximum obliges the peer's encoder to begin its next block with an update to at most the smallest limit set since its last one (§4.2); the decoder holds it to that.

HpackEncoder

One HTTP/2 connection's sending side: its dynamic table and the size updates it owes the peer.

The table starts at maxSize, which both ends must already agree on — HTTP/2's 4096 until SETTINGS say otherwise — so no update is sent for it.

class HpackEncoder
Member
new HpackEncoder(maxSize: i32) An encoder with an empty table, owing no size update.
table: HpackTable The dynamic table, which encodeField adds to and setMaxTableSize resizes.
encodeField(out: u8[], name: u8[], value: u8[], indexing: i32, huffman: boolean): void Appends one field to the block in out: by index when a table holds it and indexing is not HPACK_INDEX_NEVER, else as a literal of the kind indexing names, its name by index when a table has it and its strings Huffman-coded when huffman is true. Any other indexing panics.
setMaxTableSize(maxSize: i32): void Sets the table's maximum size, which must not pass the peer's SETTINGS_HEADER_TABLE_SIZE; the encoder cannot know that limit, so it is the caller's to keep. Call it between blocks: the next encodeField begins with the update, or with two when the size went down and then up again, the smallest first (§4.2).

HpackHuffman

Appendix B's Huffman code, rebuilt from its lengths, with the tables that both directions read. Built once per encoder or decoder rather than once per string; a program may build its own to call hpackHuffmanEncode and hpackHuffmanDecode directly.

Canonical means that the codes of one length are consecutive integers in symbol order, and that the first code of a length is one past the last code of the length before, shifted left by the difference. So the first code of each length and how many codes it has say which L-bit integers are codes, and a list of the symbols in code order, with where each length starts in it, turns such a code into its symbol: decoding needs no tree.

class HpackHuffman
Member
new HpackHuffman() Rebuilds the code from Appendix B's 257 code lengths. Build one and reuse it: each build allocates.

HpackTable

The dynamic table (§2.3.2, §4): a FIFO of fields, newest first by index, whose size — every entry's name and value plus 32 — never passes maxSize.

Every entry's octets live in one store, bytes: its name, then its value, oldest entry first. An index says where each entry sits, two numbers to an entry — where it starts in bytes and how long its name is; its value runs to where the next one starts — oldest first from entry first on, so that adding one is two pushes and evicting one moves first.

The evicted prefix of the index, and of bytes, is shifted out in place once it is half of either, which keeps both amortised constant time without a ring's index arithmetic. Shifting and popping keep an array's storage, and bytes never holds more than three times maxSize, so a table the peer fills and empties for as long as it likes stops allocating once its arrays have grown that far (docs/security/http2.md, H2-1). Dynamic index 1, the newest entry, is the last.

class HpackTable
Member
new HpackTable(maxSize: i32) An empty table.
bytes: u8[] Every entry's octets, its name then its value, oldest first, after any evicted entries' octets not yet shifted out. Any change to the table may move what it holds.
first: i32 How many evicted entries the table still records before its oldest live one: eviction moves it up, and shifting the evicted ones out returns it to 0.
maxSize: i32 The most size may be, in octets (§4.2); set by the constructor and resize.
size: i32 The table's size as §4.1 counts it, in octets: every entry's name and value plus 32; at most maxSize.
add(name: u8[], value: u8[]): i32 Adds a field as the newest entry, copying its octets in, evicting first to make room. An entry larger than the whole table empties it and is not added (§4.4): that is not an error. Neither array may be bytes itself, since eviction may move what it holds. Returns the octets it pushed into bytes: none for an entry it did not add.
count(): i32 How many entries the table holds.
name(i: i32): u8[] A fresh copy of the name of dynamic entry i. It allocates; the codec reads the window instead.
nameStart(i: i32): i32 Where the name of dynamic entry i starts in bytes.
resize(maxSize: i32): void Sets the maximum size, evicting what no longer fits (§4.3).
value(i: i32): u8[] A fresh copy of the value of dynamic entry i, as name makes the name.

HpackWork

What an HpackDecoder decodes a block with: the read position, reset for each block; a literal's name and value as they are read, before they are counted, copied or indexed; and the arrays the fields gave back, by size class, each class made when first needed.

class HpackWork
Member
new HpackWork() Empty scratch arrays, a cursor over nothing, and no pools until a field needs one.

Constants

4

HPACK_COPY_FACTOR: i32

How many times the larger of the table's maximum size and a block's length the decoder copies into its table for one block, at most (docs/security/http2.md, H2-1). An index naming a dynamic entry is one or two octets, and a literal with incremental indexing that names it copies the name out of the table and back in, so without a budget a block of them costs about three times the table's size of work per two octets it holds. Four leaves an encoder room to re-add a full table's worth of fields twice over in one block, which none needs, since every add past the table's size evicts one of its own.

4,096

HPACK_DEFAULT_TABLE_SIZE: i32

SETTINGS_HEADER_TABLE_SIZE's initial value (RFC 9113 §6.5.2).

32

HPACK_ENTRY_OVERHEAD: i32

What an entry costs beyond its name and value (§4.1).

-9

HPACK_ERR_COPY_BUDGET: i32

A block that asked the table to take more octets than its copy budget allows: HPACK_COPY_FACTOR times the larger of the table's maximum size and the block's own length. Valid HPACK, but no encoder needs it, and HTTP/2 answers it with ENHANCE_YOUR_CALM, not COMPRESSION_ERROR.

-5

HPACK_ERR_HUFFMAN_EOS: i32

The EOS symbol inside a Huffman-coded string (§5.2).

-4

HPACK_ERR_HUFFMAN_PADDING: i32

Huffman padding longer than seven bits, or not all ones (§5.2).

-3

HPACK_ERR_INDEX: i32

An index of zero, or one past the end of both tables (§2.3.3, §6.1).

-2

HPACK_ERR_INTEGER_OVERFLOW: i32

An integer past 2^31 - 1, or padded past five continuation bytes (§5.1).

-8

HPACK_ERR_SIZE_UPDATE_MISSING: i32

A block after the SETTINGS limit was lowered below the table's size that did not begin with an update to at most the smallest limit since (§4.2).

-7

HPACK_ERR_SIZE_UPDATE_POSITION: i32

A table size update after the block's first field (§4.2).

-6

HPACK_ERR_TABLE_SIZE: i32

A table size update above the limit the decoder's SETTINGS allow (§6.3).

-1

HPACK_ERR_TRUNCATED: i32

The block ended inside a representation, an integer or a string.

0

HPACK_INDEX_INCREMENTAL: i32

Add the field to the dynamic table (§6.2.1).

2

HPACK_INDEX_NEVER: i32

Never add the field to any table, here or downstream (§6.2.3).

1

HPACK_INDEX_WITHOUT: i32

Do not add the field, but let an intermediary choose (§6.2.2).

1

HPACK_LIST_TOO_LARGE: i32

A decode that read the whole block and kept the table in step, but dropped the fields past the caller's header-list limit. Not fatal.

0

HPACK_OK: i32

A decode that read the whole block and answered every field.

61

HPACK_STATIC_LENGTH: i32

The number of entries in the static table (Appendix A).