Bit output and byte buffering

Writing a three-bit header, two eight-bit literals and several shorter codes with an ordinary “write one byte” operation would leave gaps between fields. The decoder needs those bits adjacent. The bit writer joins a sequence of (value, width) fields into one bit sequence, splits off complete bytes, and retains the unfinished tail.

Continue with the final fixed block for ABABABAB: the inputs are the header, A, B, length 6, distance 2 and end code, totaling 38 bits. The output is 73 74 82 40 00, including two final padding bits. We will determine each field’s value, trace all five bytes, then read how the implementation crosses its register boundary. Bytes enter internal pending storage first; delivery to the caller happens later.

Code words and arrival order

DEFLATE writes ordinary numeric fields with the least significant bit first. Huffman code words are consumed in code-word order, with the most significant bit of the word first. zlib reconciles these rules by storing a reversed canonical word in its encoding table. The bit writer can then treat both kinds of field as an integer whose low bit is the next bit to send.

For example, the fixed canonical word for literal A is 01110001. Reverse those eight positions and the integer given to send_bits is 10001110, hexadecimal 8e. Reading that integer from bit 0 upward sends 0,1,1,1,0,0,0,1: exactly the original canonical word. This is not a reversal of the stream after it has been written.

For the final fixed block, the three-bit numeric header is value 3. Its low-first order is 1,1,0: final flag 1 followed by fixed block type 01 in its numeric field order. Each writer request has a numeric value and a bit count length. This count is the encoded field width, not the number of original bytes a match will copy. The complete calls for our selected example are:

Here 10 is hexadecimal 0x10, or decimal 16. The equal numeric value for the length and distance does not make them the same field. Their widths and their roles in the format differ.

The example across register boundaries

The implementation first holds up to 16 bits in a register: bi_buf is its content and bi_valid counts meaningful bits. The pending array contains complete bytes already written. Watch both locations first; the implementation equations follow afterwards. The hexadecimal register values below put the high bit on the left; emission still takes the low byte first.

The B call has 11 existing bits and eight new bits. Only five new bits fit into the current word; the remaining three become the new register. The end code similarly crosses the boundary from 15 to 22 bits. It emits a word and leaves six zero bits that still belong to the end code. Final alignment adds two padding zeros and writes the last byte.

The resulting raw bytes are 73 74 82 40 00. Decoding this constructed stream recovers ABABABAB. That finite example checks our field accounting; it does not prove the writer for all inputs or assert the token choices of the real compressor.

A sixteen-bit staging register

The state fields are bi_buf, the register, and bi_valid, the number of meaningful low bits it contains. Pending bytes precede these held bits in the logical output. For the equations, shorten the existing valid-bit count to r = bi_valid, the new field value to v = value, and its width in bits to l = length. Thus the B append has r = 11, v = 0x4e, l = 8. The writer appends the low l bits of v after the existing r bits. The shift v << r places the new field at the first free bit, and bitwise OR joins it to the old register. The entry conditions ensure the field fits its declared width and other register bits do not interfere with that concatenation.

When r ≤ 16-l, the field fits:

bi_buf   := bi_buf OR (v << r)
bi_valid := r + l

When r > 16-l, part of the new field completes a 16-bit word. The implementation combines those low bits with the register, writes the word's low byte and then its high byte to pending storage, and retains the rest:

write low 16 bits of (bi_buf OR (v << r))
bi_buf   := v >> (16-r)
bi_valid := r + l - 16

The real C is the overflow branch of the release send_bits macro, trees.c:276–281. A trailing backslash continues the macro onto the next line. This excerpt stops within the if branch; the source link includes its else. Buf_size names the register capacity in bits and is 16. In this macro, len is the new field width, val is a local integer copy of its value, s points to the compressor state, and put_short writes a two-byte word low byte first.

if (s->bi_valid > (int)Buf_size - len) {\
  int val = (int)value;\
  s->bi_buf |= (ush)val << s->bi_valid;\
  put_short(s, s->bi_buf);\
  s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
  s->bi_valid += len - Buf_size;\

Substitute the B append line by line. The first line tests 11 > 16−8 and enters the branch. The second takes value 0x4e. The third shifts it left by 11, combines it with old register 0x0473, and retains 0x7473 in the 16-bit register. The fourth emits low byte first: 73 74. The fifth shifts right by 16−11 = 5, leaving 0x0002. The sixth sets the valid count to 11+8−16 = 3. This is the B row of the trace above.

These equations describe the bit operations; the actual C includes its stated casts and machine widths. The overflow branch uses a strict greater-than test. At exactly 16 valid bits, the fit branch leaves the full register in place. Compare the three cases:

A full register has not necessarily been emitted. The middle row becomes pending bytes only on a later overflowing append or flush.

This staging avoids a byte write for every short code or extra-bit field. It also makes the state less obvious: encoded bits may already have a definite meaning while remaining inside the register.

Flush, alignment and delivery

bi_flush writes complete bytes while retaining a partial byte. With 16 valid bits it writes two bytes and clears the register; with 8 through 15 it writes one byte and keeps the remaining bits. With fewer than eight it does nothing. The output remains ready for a later field to continue the same byte.

bi_windup instead closes the partial byte. It writes one or two bytes as needed, clears the register and records the meaningful-bit count of the last byte in bi_used. It is used where the format requires alignment, including the end of a final block. Applying it between arbitrary fields would insert padding into the encoded data.

Delivery has a separate byte account: pending counts internally buffered bytes not yet delivered, pending_out points to the first of them, next_out points to the caller's next destination, and avail_out counts writable caller bytes. total_out is the cumulative delivered-byte count. Neither register operation by itself means the application has received those bytes. flush_pending first calls _tr_flush_bits to expose complete held bytes, then copies at most min(pending, avail_out) bytes to next_out. It advances both output cursors, updates total_out, reduces avail_out and the pending count, and restores pending_out to the buffer base once all pending bytes have been delivered. Small caller buffers therefore affect delivery without changing the already encoded fields.

The next chapter places both the pending bytes and the unread symbol records into their shared allocation. That explains why a correct bit sequence and sufficient final capacity still leave an additional memory obligation.

The writer composition proof over the full public domain is unfinished. Actual call paths must establish its register and capacity conditions and carry the returned state to later emission or delivery. The bit-output component argument leads to the relevant register and capacity obligations; deflatePending exposes pending-byte and held-bit counts to callers.