deflate(Z_FINISH) returns Z_OK (not the doc-guaranteed Z_STREAM_END) when raw-deflate output exactly fills a deflateBound()-sized buffer

[JasonGross]

zlib/zlib.h

Lines 334 to 339 in 51b7f2a

	Z_FINISH can be used in the first deflate call after deflateInit if all the
	compression is to be done in a single step. In order to complete in one
	call, avail_out must be at least the value returned by deflateBound (see
	below). Then deflate is guaranteed to return Z_STREAM_END. If not enough
	output space is provided, deflate will not return Z_STREAM_END, and it must
	be called again as described above.

This guarantee does not hold in the raw deflate case where deflate has exactly filled the output buffer and deflateBound is exact. I'm not sure if this is a docs bug or a code bug.

An excessively long report from Fable

Summary

zlib.h documents that a first deflate() call given all the input, an output buffer of deflateBound() bytes, and Z_FINISH "is guaranteed to return Z_STREAM_END". I have an input family for which, with raw deflate at level 1, the compressed output is exactly deflateBound() bytes — and that first call then returns Z_OK, not Z_STREAM_END, with avail_out == 0 and the complete, valid deflate stream already in the buffer. A second call (no new input, any nonzero avail_out) writes zero additional bytes and returns Z_STREAM_END; alternatively, giving the first call deflateBound() + 1 bytes yields Z_STREAM_END in one call with the same output.

So the bound itself is never exceeded — this is purely the return-code protocol at exact fill. I'm reporting it anyway because (a) the documented guarantee, as written, is violated; and (b) the failure mode invites misdiagnosis: a caller that allocates deflateBound() bytes and treats rc != Z_STREAM_END as "output exceeded the bound" (a natural reading of the guarantee) will report a bound overflow that never happened. That is in fact how I found it: a test harness I was formally verifying aborted with "deflate did not fit inside deflateBound()" on an input whose output fits the bound exactly.

Environment

Reproduced identically, by execution, on:

• zlib 1.3.1 built from release source (./configure --static), gcc 12, x86-64 Linux
• zlib 1.2.13 (Debian bookworm system library)
• develop head e3dc0a8 (1.3.2.1-motley), built the same way

The documented guarantee

zlib.h at v1.3.1, deflateBound doc comment, lines 768–771:

If that first deflate() call is provided the sourceLen input bytes, an output buffer allocated to the size returned by deflateBound(), and the flush value Z_FINISH, then deflate() is guaranteed to return Z_STREAM_END.

Same promise in the deflate() documentation, zlib.h lines 334–339:

Z_FINISH can be used in the first deflate call after deflateInit if all the
compression is to be done in a single step. In order to complete in one call,
avail_out must be at least the value returned by deflateBound (see below).
Then deflate is guaranteed to return Z_STREAM_END.

Both passages are unchanged on develop (zlib.h L775–L778 at e3dc0a8).

Reproduction

Input: 999423 bytes (= 16384·61 − 1), constructed so that level-1 deflate emits 62 stored blocks and nothing else (construction below; the reproducer generates it deterministically in code). Invocation:

deflateInit2(&s, 1, Z_DEFLATED, -15, 8, Z_DEFAULT_STRATEGY);
bound = deflateBound(&s, 999423);      /* = 999733 */
s.next_in  = input; s.avail_in  = 999423;
s.next_out = out;   s.avail_out = bound;
rc = deflate(&s, Z_FINISH);

step	expected per zlib.h	observed
first deflate(Z_FINISH), avail_out = bound (999733)	Z_STREAM_END	Z_OK
total_out after first call	≤ 999733	999733 (= bound exactly, avail_out = 0)
output buffer content after first call	—	complete raw deflate stream (inflates alone, round-trips)
second deflate(Z_FINISH), 1 more byte of room, no input	—	Z_STREAM_END, 0 extra bytes
fresh stream, first call with avail_out = bound + 1	—	Z_STREAM_END, same 999733-byte output

Why the output hits the bound exactly

For raw deflate with default windowBits/memLevel and sourceLen < 2^25, the tight bound (deflate.c L893–L896 at v1.3.1) is sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 7. At sourceLen = 16384k − 1 that is sourceLen + 5k + 5 with zero slack, and an input that deflate encodes as all stored blocks costs exactly sourceLen + 5·(k + 1): at memLevel 8 the symbol buffer flushes a block every 16383 symbols, so a match-free input of this length makes k full 16383-byte stored blocks plus a (k−1)-byte final block, at 5 bytes overhead each. Equality.

The input family that forces all-stored (verified by execution for k = 16…61, 80, 100; the smallest exact fill is k = 16, i.e. 262143 = 2^18 − 1 bytes: the final short block is emitted stored iff at least 15 of its bytes lie in [144,255] — the 9-bit static-code class, a criterion derived from trees.c's stored-vs-static comparison and independent of the tail length — so a tail of ≥ 15 such bytes is needed and hence k ≥ 16; the reproducer below uses a scattered-tail construction whose own floor is k = 20; for k ≥ 2048 the >> 25 term adds slack again):

• match-free: no 3-byte substring repeats within the 32 KB window, so the level-1 fast path emits only literals;
• per-block-uniform: the body is a concatenation of random 256-byte permutations, so every block's byte histogram is uniform to ±1 and neither static nor dynamic Huffman can beat 8 bits/literal — every full block is emitted stored;
• scattered tail: the final k−1 bytes are distinct values 136, 138, … (mostly ≥ 144, i.e. 9-bit static codes, and expensive to describe dynamically), so the short last block is stored too.

Mechanism

1. deflate_fast consumes the last input byte and invokes FLUSH_BLOCK(s, 1) (deflate.c L1896).

2. _tr_flush_block emits the final stored block and flush_pending drains it, exactly filling the output buffer. avail_out is now 0, so FLUSH_BLOCK takes its early return (deflate.c L1601–L1604):

   if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \

   finish_started is documented as "finish started, need only more output at next deflate" (deflate.c L66) — but here there is no more output; the pending buffer is empty.

3. deflate() maps finish_started to Z_OK (deflate.c L1190–L1195).

4. The next call has nothing to do (FINISH_STATE, no input, no lookahead, nothing pending) and immediately reaches if (s->wrap <= 0) return Z_STREAM_END; (deflate.c L1229), writing nothing.

Raw deflate only. With a zlib or gzip wrapper the same input also fills the bound exactly (wraplen is budgeted), but the stream's last bytes are trailer bytes emitted through the end-of-deflate() path whose return is s->pending != 0 ? Z_OK : Z_STREAM_END (deflate.c L1254), which reports completion correctly even at avail_out == 0. Verified: the identical run with windowBits = 15 (bound 999739) returns Z_STREAM_END in one call at exact fill. Only a stream that ends inside FLUSH_BLOCK — i.e. raw — has no way to signal completion when the flush lands on avail_out == 0.

Reproducer

Self-contained, deterministic (no data file; builds the input in ~0.1 s; allocates a 64 MB table while generating):

cc -O2 repro_deflatebound_exactfill.c -lz && ./a.out

Exact output against 1.3.1:

zlib 1.3.1, input len = 999423 (= 16384*61 - 1)
deflateBound(len) = 999733
call 1 (avail_out = bound):   rc = Z_OK         total_out = 999733, avail_out = 0
call 2 (1 more byte of room): rc = Z_STREAM_END extra bytes written = 0
call-1 output alone inflates: rc = Z_STREAM_END round-trip matches input
fresh, avail_out = bound + 1: rc = Z_STREAM_END total_out = 999733
=> documented guarantee violated: Z_OK (not Z_STREAM_END) at avail_out = deflateBound()

(1.2.13 and develop e3dc0a8 print the same numbers, different version string.)

/* repro_deflatebound_exactfill.c
 *
 * zlib.h (deflateBound) documents: "If that first deflate() call is provided
 * the sourceLen input bytes, an output buffer allocated to the size returned
 * by deflateBound(), and the flush value Z_FINISH, then deflate() is
 * guaranteed to return Z_STREAM_END."
 *
 * This program deterministically builds a 999423-byte input for which, at
 * level 1 raw deflate (deflateInit2(.., 1, Z_DEFLATED, -15, 8,
 * Z_DEFAULT_STRATEGY)), the compressed output is EXACTLY deflateBound()
 * bytes (62 stored blocks).  The first deflate(Z_FINISH) call with
 * avail_out == deflateBound() then returns Z_OK, not Z_STREAM_END, even
 * though the complete stream is already in the buffer: a second call writes
 * 0 additional bytes and returns Z_STREAM_END, and the call-1 output alone
 * inflates back to the input.  With avail_out == deflateBound()+1 the first
 * call returns Z_STREAM_END.  The bound itself is never exceeded.
 *
 * Build:  cc -O2 repro_deflatebound_exactfill.c -lz && ./a.out
 * (The generator allocates a 64 MB trigram table.)
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "zlib.h"

#define K 61
#define LEN (16384UL * K - 1)          /* 999423 */
#define TAIL 60                        /* LEN - 61*16383 */
#define BODY (LEN - TAIL)              /* 61 * 16383 = 999363 */

/* deterministic xorshift64 PRNG; avoids libc rand() portability issues */
static unsigned long long rngstate = 88172645463325252ULL;
static unsigned rnd(unsigned n) {
    rngstate ^= rngstate << 13;
    rngstate ^= rngstate >> 7;
    rngstate ^= rngstate << 17;
    return (unsigned)((rngstate >> 24) % n);
}

/* trigram -> position of its most recent occurrence (index of last byte) */
static int *seen;
#define TIDX(a, b, c) (((a) << 16) | ((b) << 8) | (c))
#define NEVER (-0x40000000)

/* Input with (a) no 3-byte repeat within deflate's 32506-byte match window,
 * so the level-1 fast path emits only literals and flushes a block every
 * 16383 symbols; (b) per-block byte histogram uniform to +-1 (whole 256-byte
 * random permutations), so no Huffman block type beats 8 bits/literal and
 * every full block is emitted stored; (c) a 60-byte tail of scattered
 * distinct values 136,138,..,254 (mostly 9-bit static codes; expensive
 * dynamic code description), so the final short block is stored too.  Total
 * compressed size: 61*(16383+5) + (60+5) = LEN + 5*62 = deflateBound(LEN). */
static unsigned char *gen_witness(void) {
    unsigned char *data = malloc(BODY + 256 + TAIL), perm[256], vals[TAIL];
    unsigned long n = 0;
    int i, j, tries, ok = 0;
    seen = malloc((1UL << 24) * sizeof(int));
    if (!data || !seen) { fprintf(stderr, "oom\n"); exit(2); }
    for (i = 0; i < (1 << 24); i++) seen[i] = NEVER;
    for (i = 0; i < 256; i++) perm[i] = (unsigned char)i;
    while (n < BODY) {                     /* body: 256-byte permutations */
        for (tries = 0; tries < 10000; tries++) {
            for (i = 255; i > 0; i--) {    /* Fisher-Yates shuffle */
                unsigned char t = perm[i];
                j = (int)rnd((unsigned)i + 1);
                perm[i] = perm[j]; perm[j] = t;
            }
            ok = 1;                        /* no trigram within 32770 bytes */
            for (j = 0; j < 256 && ok; j++)
                if (n + j >= 2) {
                    int a = j >= 2 ? perm[j-2] : data[n+j-2];
                    int b = j >= 1 ? perm[j-1] : data[n+j-1];
                    if ((long)(n + j) - seen[TIDX(a, b, perm[j])] <= 32770)
                        ok = 0;
                }
            if (ok) break;
        }
        if (!ok) { fprintf(stderr, "generator stuck (body)\n"); exit(2); }
        for (j = 0; j < 256; j++) {
            if (n + j >= 2) {
                int a = j >= 2 ? perm[j-2] : data[n+j-2];
                int b = j >= 1 ? perm[j-1] : data[n+j-1];
                seen[TIDX(a, b, perm[j])] = (int)(n + j);
            }
            data[n + j] = perm[j];
        }
        n += 256;
    }
    n = BODY;                              /* truncate to 61 whole blocks */
    for (i = 0; i < TAIL; i++) vals[i] = (unsigned char)(136 + 2 * i);
    for (tries = 0; tries < 10000; tries++) {
        for (i = TAIL - 1; i > 0; i--) {
            unsigned char t = vals[i];
            j = (int)rnd((unsigned)i + 1);
            vals[i] = vals[j]; vals[j] = t;
        }
        ok = 1;
        for (i = 0; i < TAIL && ok; i++) {
            int a = i >= 2 ? vals[i-2] : data[n+i-2];
            int b = i >= 1 ? vals[i-1] : data[n+i-1];
            if ((long)(n + i) - seen[TIDX(a, b, vals[i])] <= 32770) ok = 0;
        }
        if (ok) break;
    }
    if (!ok) { fprintf(stderr, "generator stuck (tail)\n"); exit(2); }
    memcpy(data + n, vals, TAIL);
    free(seen);
    return data;
}

static const char *rcname(int rc) {
    return rc == Z_STREAM_END ? "Z_STREAM_END" : rc == Z_OK ? "Z_OK" :
           rc == Z_BUF_ERROR ? "Z_BUF_ERROR" : "other";
}

static void init_raw_level1(z_stream *s) {
    memset(s, 0, sizeof(*s));
    if (deflateInit2(s, 1, Z_DEFLATED, -15, 8, Z_DEFAULT_STRATEGY) != Z_OK) {
        fprintf(stderr, "deflateInit2 failed\n"); exit(2);
    }
}

int main(void) {
    unsigned char *in = gen_witness(), *out, *rt;
    z_stream s, z;
    uLong bound;
    int rc, violated;

    printf("zlib %s, input len = %lu (= 16384*%d - 1)\n", zlibVersion(), LEN, K);
    init_raw_level1(&s);
    bound = deflateBound(&s, LEN);
    printf("deflateBound(len) = %lu\n", bound);
    out = malloc(bound + 1);
    if (!out) { fprintf(stderr, "oom\n"); exit(2); }

    /* single-call deflate as documented: all input, avail_out = bound */
    s.next_in = in;   s.avail_in = (uInt)LEN;
    s.next_out = out; s.avail_out = (uInt)bound;
    rc = deflate(&s, Z_FINISH);
    printf("call 1 (avail_out = bound):   rc = %-12s total_out = %lu, avail_out = %u\n",
           rcname(rc), s.total_out, s.avail_out);
    violated = (rc == Z_OK && s.total_out == bound && s.avail_out == 0);

    /* (a) second call, 1 more byte of room, no new input: 0 extra bytes */
    s.next_out = out + s.total_out; s.avail_out = 1;
    rc = deflate(&s, Z_FINISH);
    printf("call 2 (1 more byte of room): rc = %-12s extra bytes written = %lu\n",
           rcname(rc), s.total_out - bound);
    deflateEnd(&s);

    /* the call-1 output was already the complete stream: it inflates alone */
    rt = malloc(LEN);
    memset(&z, 0, sizeof(z));
    if (!rt || inflateInit2(&z, -15) != Z_OK) { fprintf(stderr, "inflate init\n"); exit(2); }
    z.next_in = out; z.avail_in = (uInt)bound;
    z.next_out = rt; z.avail_out = (uInt)LEN;
    rc = inflate(&z, Z_FINISH);
    printf("call-1 output alone inflates: rc = %-12s round-trip %s\n", rcname(rc),
           z.total_out == LEN && !memcmp(rt, in, LEN) ? "matches input" : "MISMATCH");
    inflateEnd(&z);

    /* (b) fresh stream, avail_out = bound + 1: Z_STREAM_END in one call */
    init_raw_level1(&s);
    s.next_in = in;   s.avail_in = (uInt)LEN;
    s.next_out = out; s.avail_out = (uInt)(bound + 1);
    rc = deflate(&s, Z_FINISH);
    printf("fresh, avail_out = bound + 1: rc = %-12s total_out = %lu\n",
           rcname(rc), s.total_out);
    deflateEnd(&s);

    printf(violated
           ? "=> documented guarantee violated: Z_OK (not Z_STREAM_END) at avail_out = deflateBound()\n"
           : "=> guarantee held on this build\n");
    free(in); free(out); free(rt);
    return violated ? 0 : 1;
}

Possible resolutions

Any of these would close the gap; I don't have a strong preference:

1. Code: let the final flush report completion even at avail_out == 0 when nothing is left pending — e.g. have FLUSH_BLOCK's early return distinguish s->pending == 0 on the last branch (returning finish_done rather than finish_started), so a raw single-call Z_FINISH at exact fill returns Z_STREAM_END as documented. The wrapped paths already behave this way via the s->pending != 0 ? Z_OK : Z_STREAM_END trailer return.
2. Docs: qualify the guarantee — either recommend deflateBound() + 1 bytes for the single-call idiom, or note that when the output exactly fills the buffer, deflate() may return Z_OK with the stream already complete, requiring one more call (or a deflatePending() check) to observe Z_STREAM_END.
3. Bound: add 1 to the tight branch for raw streams (wraplen == 0), so the documented protocol always has the one byte of headroom the current return-code logic needs. (For wrapped streams equality is also achievable but harmless, since the trailer path signals completion correctly.)

Related reports (none covers this)

I searched the open and closed issues here (and what mailing-list/StackOverflow material I could find) and did not find this reported:

• #149 is the closest: an exact-size buffer with Z_FULL_FLUSH, where the next call emits a spurious flush marker. It was closed as not-a-bug, correctly, because the docs explicitly disclaim flushes other than Z_FINISH/Z_NO_FLUSH. This report is the Z_FINISH case — the one case the docs do guarantee.
• #758 (fixed in 1.3) and #944 (fixed after 1.3.1) were cases of deflateBound() returning a value genuinely below the output size (level-0/memLevel-9 selector; post-completion gzip wrapper accounting). Here the bound is never exceeded — the output fits it exactly.
• #822 concerns whether the tight bound extends to memLevel 9 ("No. In fact it can be larger."). That is about the bound's magnitude, not the return-code protocol at exact fill.
• zlib_how.html acknowledges the generic ambiguity for the chunked-output loop: "suppose that deflate() has no more output, but just so happened to exactly fill the output buffer! avail_out is zero, and we can't tell that deflate() has done all it can." The deflateBound guarantee is the one place the documentation promises one-call completion regardless — and this input family lands the promise exactly on that ambiguous state.