Fountain codes in a stream of QR codes

Q: How many packets does a file need?

Roughly `ceil(file_bytes / (packet_size − 4))` packets. With the 368-byte packet size, a 1 MiB file is about 2,881 blocks, far below the 64,000-block limit for a single fountain, plus whatever extra packets the measured loss rate demands.

Direct answer

QRTP encodes each stream with a Wirehair fountain code. The sender emits an endless supply of source and repair packets, and the receiver reconstructs the original bytes once it has solved enough independent equations. Because the QR link is one-way, there is no retransmission — recovery depends on how many distinct packets were seen, not which ones.

Key takeaways

A fountain code turns a source blob into packets that are linear equations, so the receiver can ignore arrival order and keep solving until the rank is complete.
Wirehair allows up to 64,000 blocks per fountain; a larger source splits into several fountains, and block_id names both the fountain and the block within it.
Each stream's packet size is fixed for its life — 368 bytes for the large size, 40 bytes for the small one — and Wirehair payload is packet_size − 4 bytes because a 4-byte block_id prefixes it.
Payloads that fit inside one packet use direct mode: the packet is the source verbatim, zero-padded, and any single packet recovers it.
--ecc and --packets-per-qr set the redundancy budget; repair packets consume the same bandwidth as source packets.

Why a one-way link needs a fountain

Automatic repeat request needs a back channel, and QRTP deliberately has none: the sender is a screen, the receiver is a camera, and the only direction with designed capacity is screen to lens. A fountain code removes the need for feedback — the sender produces packets forever without knowing what arrived, and the receiver finishes whenever it has seen enough distinct packets. The inner Reed–Solomon code inside each symbol repairs damaged modules; the fountain sits one layer above and repairs whole frames that were blurred, missed, or never drawn. See QRTP for the frame layout around those packets.

Source packets, repair packets, and solving for the original

Wirehair splits a stream's source message into K source blocks. Each packet is the XOR of a pseudo-random subset of them, and the packet's block_id is the seed that lets the receiver regenerate which subset that was. Every packet is therefore one linear equation in K unknowns. The sender emits source packets first, then repair packets from the same generator, and the receiver cannot tell them apart because it does not need to: it runs Gaussian elimination as packets arrive and finishes when the rank reaches K, with a small constant overhead of extra packets in practice.

fountain packet:  block_id: u32 | Wirehair payload: u8[packet_size - 4]
direct packet:    source bytes | 0x00 padding up to packet_size

What "enough" means in practice

Three constants define the arithmetic of a stream.

Packet size is fixed per stream. The large size is 368 bytes and the small one 40 bytes, chosen once and kept for the stream's life. Wirehair's minimum packet is 12 bytes, and its usable payload is packet_size − 4.
One fountain holds at most 64,000 blocks. The largest fountain is payload_bytes × 64,000 bytes, where payload_bytes is packet_size − 4. A larger source splits into ceil(source_total_bytes / max_fountain_size_bytes) fountains; the 64,000 is a wire constant that is never transmitted, and both ends derive the split from it.
block_id maps across fountains. block_id % fountain_count names the fountain and block_id / fountain_count the block inside it, so a receiver must tolerate packets from different fountains interleaved in the same transfer.

A 1 MiB file over the 368-byte packet size is about 2,881 blocks, comfortably inside one fountain; only multi-gigabyte sources reach the ceiling and get split.

Direct mode and the cost of the 4-byte prefix

When packet_size exceeds source_total_bytes, the stream is degenerate and the encoder switches to direct mode: the packet is the source verbatim, zero-padded, and any single packet completes the stream because there is no rank to reach. That is the normal case for the tiny network-metadata stream carrying the WebRTC/PeerJS handshake, which is why it can repeat on every frame with a 16-byte packet and still be recovered within a few frames.

In fountain mode the block_id is a fixed tax: 4 bytes out of 368 is about 1.1% of goodput, while 4 out of 40 is 10%. That asymmetry is why the small packet size serves streams whose value is repetition rather than volume.

Dropped, misread and out-of-order frames

Dropped frames are erasures: the symbol was never drawn, out of view, or too blurred for the inner code, so that packet does not exist and the receiver needs one more distinct packet later. A misread frame is handled inside the symbol — QR error correction repairs a limited number of damaged modules, and past that the scan returns nothing rather than plausible garbage, which is indistinguishable from a dropped frame. Order and repetition cost nothing: a linear system does not care about sequence, and a re-scanned block_id is a duplicate equation that is discarded. That is why a stream of QR codes can be joined mid-transfer and still converge.

Failure mode	What the receiver observes	What the decoder does
Frame never drawn or out of view	No packet at all	Waits; needs one more distinct equation
Symbol too blurred or too small	Inner error correction fails, scan yields nothing	Treats it as a dropped frame
Same frame scanned twice	Identical `block_id`	Discards the duplicate; no progress
Frames arrive shuffled	Packets in arbitrary order	No effect; rank is order-independent
Packet size changes mid-stream	New packet size in the stream descriptor	Discards the old fountain, starts a new one
Source spans more than 64,000 blocks	`block_id` beyond one fountain's range	Resolves fountain and block from `block_id`
Payload smaller than one packet	`packet_size > source_total_bytes`	Direct mode; any single packet completes it

Redundancy knobs, and what repair costs

The sender buys margin with two knobs. --ecc sets the QR error correction level: a higher level survives more blur and glare but leaves fewer data modules, pushing toward larger symbols for the same payload. --packets-per-qr sets how many fountain packets ride inside one frame: more packets per symbol mean more bytes per frame, at the cost of a denser symbol the camera must resolve.

# 15 fps, an 8x4 grid of symbols, high error correction,
# six fountain packets per symbol, looping the render
./qrsend --fps 15 --cols 8 --rows 4 --ecc H --packets-per-qr 6 ./archive.zip

# stream from stdin, single pass, four packets per symbol
cat ./firmware.bin | ./qrsend --once --packets-per-qr 4 -

Repair packets are not free insurance. A repair packet is the same size on the wire as a source packet and occupies the same slot in the frame budget, so every repair packet is a source packet that was not sent. If a transfer needs 2,900 packets to reach rank and roughly one scan in five is lost, a 25% repair budget gets it home in about the frames a perfect camera would have taken, while a 200% budget triples the wall-clock time for a channel that was mostly fine. The calculus is harshest for live media, where old data is worthless on arrival, so the repair budget must cover the loss rate of the current moment rather than a file's whole lifetime — the same reason playback never waits for a missing fragment when streaming live audio and video over QR.

Why changing packet size restarts the fountain

A fountain is defined by exactly two numbers: the source message and the packet size. block_id is meaningful only relative to that pair, because the seed expands into a subset of blocks of that size. Resize the symbol mid-transfer — a grid change that no longer fits the 368-byte packet, for instance — and every equation already collected becomes meaningless, because the receiver can no longer reproduce what those blocks were. So the encoder keeps the packet size fixed for the stream's life, and the receiver resets its decoder state for a stream when the descriptor's packet_size_words differs from the size it is currently decoding. The same reset happens when a segmented stream advances its segment_id: each live media fragment is deliberately a fresh fountain, which is what lets playback continue without ever waiting for a lost fragment.

FAQ

Do I have to scan the QR codes in order?

No. Fountain packets are order-independent linear equations, so any distinct packets count toward decoding. You can start scanning halfway through a transfer, or catch frames out of sequence, and the decoder still converges.

What happens if the camera misses a few QR codes?

Nothing special. A missed symbol is an erasure, exactly like a packet lost on a lossy wire, and the receiver simply needs that many more distinct packets before the rank reaches the source block count.

Why not re-send the QR codes that failed to scan instead of using a fountain?

Because the sender cannot know which ones failed. Retransmission needs feedback from receiver to sender, and the optical link is one-way by design. A fountain code removes the need for that knowledge entirely.

How many packets does a file need?

Roughly ceil(file_bytes / (packet_size − 4)) packets. With the 368-byte packet size, a 1 MiB file is about 2,881 blocks, far below the 64,000-block limit for a single fountain, plus whatever extra packets the measured loss rate demands.

Does a bigger QR code decode faster?

A larger symbol carries more bytes per frame, so fewer frames are needed, but it needs more camera resolution and a steadier hand to resolve each module. Raising --packets-per-qr while keeping the grid small often beats one very dense symbol, and --ecc trades module budget for tolerance in the same direction.