Visual walkthrough — HTTP - 2 — multiplexing, header compression (HPACK), server push

Step 1 — What a byte even is, and why 8 slots

WHAT. A byte is a row of 8 bits. A bit is a single slot holding a $0$ or a $1$. That is the smallest thing the wire carries — everything in HTTP/2, every frame, every header, is ultimately rows of these 8-slot bytes.

WHY start here. HPACK's whole cleverness is reusing the same byte for two jobs: a few of the 8 slots say what kind of thing this is (a flag), and the rest carry a number. You cannot understand "5-bit prefix" until you can see the 8 slots and point at which ones are flags.

PICTURE. Below, the 8 slots of one byte. Each slot has a "place value" — the leftmost slot is worth $128$, then $64,32,16,8,4,2,1$. A slot set to $1$ adds its place value; a slot set to $0$ adds nothing. To read a byte, you sum the place values of the slots that are $1$.

Step 2 — Splitting one byte into "flag bits" + "number bits"

WHAT. HPACK does not use all 8 slots for the number. It reserves the top few slots as flags (a code saying how to interpret this header), and leaves the bottom $N$ slots for the number. That bottom region is the ==$N$-bit prefix==.

WHY. Every header field has to announce its representation type first: "I am a fully indexed header" ($1$ in the top slot), or "I am a literal that should be remembered" ($01$ in the top two slots), and so on. Those type-bits eat some of the 8 slots. Whatever is left over is where the actual index number lives. Different types leave a different number of slots — that is exactly why the spec keeps saying "$N$-bit prefix" instead of a fixed number: $N$ depends on how many flag bits that representation used.

PICTURE. Same byte, now painted in two colours: burnt-orange flag slots on the left, teal number slots on the right. For the "indexed" case ($1$ flag) the prefix is $N=7$ slots. For "literal with incremental indexing" ($01$ flag) the prefix is $N=6$ slots. For a plain literal-name reference it is $N=4$.

Step 3 — The easy case: the number fits in the prefix

WHAT. If our number $I$ is small enough to fit in the $N$ slots, we just write it there and we are done. "Small enough" means strictly less than $2^N-1$.

WHY the $2^N-1$ boundary (not $2^N$)? The $N$ slots can hold values $0$ up to $2^N-1$. But HPACK reserves the all-ones pattern ($2^N-1$) as a special signal meaning "I overflowed — keep reading more bytes". So the values that fit-and-stop are $0$ through $2^N-2$. The instant $I$ equals $2^N-1$, we are not allowed to just write it; that pattern is the "continue" flag. That is the single most important rule on this page.

PICTURE. A 5-bit prefix ($N=5$, so $2^5-1=31$). We store $I=10$. Since $10<31$, the teal slots become $01010$ and the orange flag slots sit untouched on top. One byte total.

Step 4 — Why we need continuation bytes at all

WHAT. What if $I\ge 2^N-1$? The prefix cannot hold it. So we do two moves: (1) fill the prefix with all-ones $(2^N-1)$ — the "keep reading" signal — and (2) store the remainder $I^{\prime }=I-(2^N-1)$ in extra bytes that follow.

WHY subtract $2^N-1$ first? Because the prefix already "used up" that much magnitude just by being all-ones. We do not want to count it twice. Storing the leftover $I^{\prime }$ keeps the numbers as small as possible, which keeps the byte-count down. This is the classic variable-length integer idea: small numbers cost few bytes, big numbers cost more, and nothing has a fixed wasteful size.

PICTURE. A number too big for the 5-bit prefix. The prefix turns solid ($11111=31$), and an arrow points out of the byte toward the continuation bytes we are about to build in Step 5.

Step 5 — The 7-bit continuation groups (the varint engine)

WHAT. We encode the leftover $I^{\prime }$ in continuation bytes. In each such byte, the top slot is a flag ($1$ = "another byte follows", $0$ = "this is the last one") and the bottom 7 slots carry a chunk of the number. We peel off 7 bits of $I^{\prime }$ at a time.

WHY 7, not 8? Because we spent 1 slot per byte on the "more follows?" flag. That leaves 7 slots for data. So each continuation byte carries a value $0$–$127$, and $128$ (the top slot) becomes the "keep going" marker. The loop:

$\text{while }{I}^{\prime }\ge 128:\text{emit }(I^{\prime }\mathrm{mod}128)+128;I^{\prime }\leftarrow \lfloor I^{\prime }/128\rfloor$ $\text{then emit the final }{I}^{\prime }(\text{now}<128,\text{top bit }0)$

• $I^{\prime }\mathrm{mod}128$ — the lowest 7 bits (the current chunk).
• $+128$ — set the top slot to say "more bytes coming".
• $\lfloor I^{\prime }/128\rfloor$ — shift right by 7 bits, exposing the next chunk.
• The final emit has $I^{\prime }<128$, so its top slot is $0$ → decoder stops.

PICTURE. The remainder $I^{\prime }$ shown as a tall stack, sliced into 7-bit chunks bottom-up. Each slice becomes a byte; all but the last wear a burnt-orange "continue" top bit; the last wears a teal "stop" top bit.

Step 6 — Decoding: reading it back

WHAT. The decoder reverses everything. Read the prefix. If it is less than $2^N-1$, that IS the number, stop. If it equals $2^N-1$, keep reading continuation bytes, accumulating 7 bits at a time, until a byte with top slot $0$.

WHY it is unambiguous. The all-ones prefix and the top "continue" bits are self-describing: at every byte the decoder knows whether to expect more without any length field. That is what makes a varint safe to drop into a byte stream.

PICTURE. The decode of 31, 154, 10 back to $1337$: prefix $31$ says "overflow, start at base $31$"; then $154$ contributes its low 7 bits $26$ at weight $128^0$; then $10$ (stop) contributes at weight $128^1$; sum $31+26+10\cdot 128=1337$.

Step 7 — Edge & degenerate cases (never leave the reader stranded)

WHAT & WHY, each with its own row in the figure:

• $I=0$. Fits in any prefix ($0<2^N-1$). Written as all-zeros in the number slots. One byte.
• $I=2^N-2$ (the largest that still fits). E.g. $N=5\Rightarrow 30$. Still one byte — because $30<31$. This is the last "cheap" value.
• $I=2^N-1$ (the trap). E.g. $N=5\Rightarrow 31$. Does not fit-and-stop! Prefix goes all-ones and remainder $I^{\prime }=31-31=0$, so we still emit one continuation byte ($0$, top bit off). Total two bytes to store $31$. This surprises people: $30$ costs one byte, $31$ costs two.
• Multiple of 128 as remainder. If $I^{\prime }=128$ exactly: $128\mathrm{mod}128=0$ so emit $0+128=128$, then $\lfloor 128/128\rfloor =1<128$ emit $1$. Two continuation bytes.

PICTURE. A little table-figure: the "cliff" at $2^N-1$ where byte-count jumps from 1 to 2, plus the $I=0$ and $I^{\prime }=128$ cases drawn out.

The one-picture summary

This final figure runs the whole machine on one number: a byte split into orange flags + teal $N$-bit prefix; the fit-or-overflow decision; and the 7-bit continuation chain feeding out to the right, top-bit meaning "more". That is all of HPACK integer encoding — the mechanism that turns a repeated 200-byte cookie into a single referencing byte once it lives in the dynamic table.

Related: this varint trick reappears whole in Varint-encoding; the reason HPACK avoids generic gzip lives in CRIME-and-BREACH-attacks; the literal-string path uses Huffman-Coding; and the whole scheme sits over TCP/TLS, superseded transport-wise by HTTP-3-and-QUIC.

Quick self-checks: