skip to content

What guarantee does a stored-raw fallback block give a lossless container, and what does it cost?

level: middleimportance: should knowfreq 37%

answer

  1. escape hatch for a losing block
  2. measure coded against raw
  3. header flag says stored or coded
  4. expansion capped by the header
  5. smaller blocks, bigger tax

basics

~20 s

A stored-raw block lets the writer emit a block's original bytes whenever coding them would be bigger, so worst-case expansion is capped by that block's small header rather than by the coder's behaviour — usually a small fraction of a percent.

solid answer

~40 s

Counting says no lossless scheme shrinks everything, so a format needs an answer for the blocks it loses on. The answer is an escape hatch: code the block, compare the coded size against the raw size, and emit whichever is smaller with a flag in the header saying `stored` or `coded`. The decoder reads the flag and either decodes or copies the bytes straight through. The guarantee this buys is a **bound on expansion** rather than a promise of shrinkage: the worst case becomes one block header per block plus the stream's fixed overhead. With roughly 64 KiB blocks and a five-byte header that is about 0.008%; with 4 KiB blocks the same header is about 0.12%. Smaller blocks buy finer random access and pay a bigger tax.

code

pseudocode · 16 lines
pseudocode
for each block in input:
    coded = code_block(block)

    if length(coded) + CODED_HEADER < length(block) + STORED_HEADER:
        emit_header(kind = CODED, size = length(coded))
        emit(coded)
    else:
        emit_header(kind = STORED, size = length(block))
        emit(block)                  # original bytes, untouched

# decoder side
for each header, payload in stream:
    if header.kind == CODED:
        append(decode_block(payload))
    else:
        append(payload)              # copied through

go deeper

for a junior

Remember that a container can write a block's original bytes untouched, with a flag saying so, when coding them would have made the block bigger.

for a middle

Describe the emit decision and the arithmetic it buys: coded against raw per block, and a worst case of one header per block rather than an open-ended expansion.

for a senior

Use the per-block shape to attribute a real size delta, and set the block size against the random-access granularity the workload needs.

for a principal

Frame the guarantee you can actually offer a storage budget: bounded growth, not guaranteed shrinkage, and the block size that sets where that bound lands.

## Why a format needs an escape hatch A lossless container has to be honest about the bound it lives under. Counting guarantees that some inputs will not shrink, and that any scheme shrinking one input expands another, so a format that only knew how to emit coded blocks would have no bounded answer for its bad cases: it would emit a coded block that happens to be longer than what it read, and on a corpus of such blocks the archive could swell badly. The escape hatch is a block type that means **stored**: the header says how many bytes follow and that they are the original bytes, uncoded. DEFLATE is the best-known example of the family, reserving a stored block type whose payload is the literal bytes with a length field beside it. The mechanism is general and every block-based lossless format has some version of it. ## The emit decision, block by block 1. Read a block of the input. 2. Run the coder over it and measure the coded payload. 3. Compare `coded payload + coded header` against `raw bytes + stored header`. 4. Emit the smaller of the two, with the block header recording which kind it is. 5. The decoder branches on that flag: decode, or copy the payload through unchanged. The comparison happens **after** coding, not before, because prediction is a heuristic and this is a guarantee. Some writers sample a block first and skip the coding attempt when the sample looks hopeless, which saves processor time, but the bound itself comes from the measured comparison. ## What it costs The cost is one block header on every block, including the ones that fall back. On a wholly incompressible input every block falls back, so the whole cost is visible at once: | Block size | Per-block header | Worst-case expansion | |---|---|---| | 4 KiB | 5 bytes | about 0.12% | | 64 KiB | 5 bytes | about 0.008% | | 1 MiB | 5 bytes | about 0.0005% | Two consequences follow from the table: - **Bigger blocks amortise the header** and shrink the worst case, but they coarsen random access: reading one record means decoding a whole block, and the writer needs more memory in flight. - **The tax never goes negative.** Enlarging blocks pushes the expansion toward zero and never past it, which is the counting bound showing up as arithmetic. ## What the fallback does and does not buy - **Does:** convert an unbounded worst case into a bounded one, so a size budget can be written down. Storage planning can assume 'never more than the input plus a header per block plus a constant'. - **Does:** make the format safe to point at unknown data. A pipeline that compresses whatever arrives cannot be embarrassed by a corpus of already-compressed payloads; it just breaks even minus a rounding error. - **Does not:** beat the counting bound. The blocks that fall back are exactly the inputs that had to pay, and paying a header is the payment. - **Does not:** make the archive smaller than the input for every file. That claim is impossible for any lossless format, with or without the fallback. - **Does not:** require the decoder to attempt a decode of a stored block. The flag is read first, and the payload is copied. ## Reading a real size delta Because the cost is per block rather than per file, a suspicious delta is easy to attribute: divide the growth by the number of blocks. A few bytes per block is the fallback working as designed. Hundreds of bytes per block means coded blocks are being emitted where a stored block would have been smaller, which usually means the writer is shipping a model or code-table description alongside payloads that do not repay it. That is a defect in the emit decision, not in the bound. ## Why an interviewer asks this one It is the point where the theory turns into a line in a design document. The counting argument alone tells you a guarantee of universal shrinkage is impossible; the stored-raw fallback is the standard engineering response, and being able to describe it shows the candidate knows what a format does with its own bad cases rather than just knowing that bad cases exist. The follow-up question in an interview is almost always the arithmetic: how much can this archive grow, worst case, and the expected answer is a header per block, not a shrug.

  • Why does the writer compare sizes after coding instead of predicting which blocks will code well?
    Because a prediction is a heuristic and will be wrong sometimes, which would break the bound. Measuring costs one coding pass and gives an exact answer per block. Sampling ahead of time is a legitimate optimisation to skip hopeless blocks, but the guarantee still rests on the comparison.
  • What is the floor on the stored size of a wholly incompressible file in such a format?
    The original bytes, plus one block header for every block, plus the stream's fixed preamble, trailer and integrity check. Nothing in the format can go below that, and the only lever that moves it is the block size, which changes how many headers are written.

saying these in an interview costs you the question

  • Claims the fallback lets the format shrink every input
  • Thinks the decoder must attempt to decode a stored block
  • Says worst-case growth is a fixed number of bytes per file
  • Says the writer picks stored blocks from the file type, not measured size
  • Confuses the stored flag with the block's integrity check