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
}
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.
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.
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).
hpackEncodeString
Appends data as a §5.2 string literal: Huffman-coded when huffman is true, else 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.
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).
hpackHuffmanLength
The length of src[off, off + len) once Huffman-coded, in bytes, padding included.
HpackCursor
A read position in a header block: the bytes, where the next read starts, and where the block ends.
HpackDecoder
One HTTP/2 connection's receiving side: its dynamic table, the SETTINGS limit the table may grow to, and the header-list limit.
HpackEncoder
One HTTP/2 connection's sending side: its dynamic table and the size updates it owes the peer.
HpackHuffman
Appendix B's Huffman code, rebuilt from its lengths, with the tables that both directions read.
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.
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.
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
cHpackCursorrequiredWhere to read; its position moves past every byte read, also when the answer is an error.
prefixBitsi32requiredHow 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
hHpackHuffmanrequiredThe 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[]requiredWhere 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.
prefixBitsi32requiredHow many low bits of the first byte the integer starts in, 1 to 8.
valuei32requiredThe 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
hHpackHuffmanrequiredThe code to encode with when huffman is true.
outu8[]requiredWhere the literal goes, appended after what it holds: its length with a 7-bit prefix and the H bit, then the octets.
datau8[]requiredThe octets to write, all of them; only read.
huffmanbooleanrequiredWhether 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
hHpackHuffmanrequiredThe code to decode with.
srcu8[]requiredThe coded bytes, the peer's; only read.
offi32requiredWhere the window starts, an index into src.
leni32requiredHow 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
hHpackHuffmanrequiredThe code to encode with.
srcu8[]requiredThe octets to encode; only read.
offi32requiredWhere the window starts, an index into src.
leni32requiredHow many octets from off on to encode.
outu8[]requiredWhere 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
hHpackHuffmanrequiredThe code to measure with.
srcu8[]requiredThe octets to measure; only read.
offi32requiredWhere the window starts, an index into src.
leni32requiredHow many octets from off on to measure.
returnsi32The 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).

