Chapter 16: Compression#

Part III - Data structures. Prerequisites: Chapter 2 for the allocator a compressor is made with; Chapter 4 for the checksums. After this chapter you can compress and decompress a buffer or a stream of any length, read and write the gzip and zlib wrappers, read and write Zstandard, read Brotli, decide how much a stranger's data may expand to - and how much memory it may make you spend - before you refuse it, and say what was tested and how fast it is.

This chapter covers deflate.h, in section 7 zstd.h, and in section 8 brotli.h. All are pure computation - allocation through the allocator you give, nothing from the operating system - and are available in a freestanding build. Section 6 is the exception: it is about compressed HTTP responses, in the servers and clients of Chapters 11 and 15.

Table of contents#

1. What DEFLATE does, in one page
2. A whole buffer
3. A stream
4. Levels, windows and what they cost
5. Data from somebody else
6. Over HTTP
7. Zstandard
8. Brotli
9. What is accepted, what is not here, and how this was tested

1. What DEFLATE does, in one page#

DEFLATE (RFC 1951) is the compression inside .gz files, HTTP's Content-Encoding: gzip, PNG images, ZIP archives and WebSocket's permessage-deflate. It is thirty years old, it is not the best there is, and everything reads it.

It does two things, one after the other:

• It replaces repeats by references. Wherever the next few bytes have appeared before, within the last 32 KiB, it writes "the same as distance bytes ago, for length bytes" instead of the bytes. A log file, a web page or source code is mostly repeats.
• It writes what is left in codes of different lengths: short for what is common, long for what is rare.

So text shrinks to a third or a quarter, a table of numbers often to less, and data that is already compressed or encrypted does not shrink at all - it grows by a few bytes.

The compressed data needs something around it to be a file or a message. There are three choices, and both ends must make the same one:

The two with a checksum notice damage. Raw does not: a changed bit gives other data or an error, and nothing says which.

2. A whole buffer#

proven_size_t proven_deflate_bound(proven_deflate_format_t format, proven_size_t input_size);
proven_err_t proven_deflate_all(const proven_deflate_options_t *options, proven_mem_view_t in,
                                proven_mem_mut_t out, proven_size_t *written);
proven_err_t proven_inflate_all(proven_allocator_t alloc, proven_deflate_format_t format, proven_mem_view_t in,
                                proven_mem_mut_t out, proven_size_t *written, proven_size_t *consumed);

When the data is in memory and so is the room for the result, these two calls are all there is to it. Both write into a buffer of yours.

• Compressing needs a buffer of proven_deflate_bound bytes to be sure of fitting - the input's size plus a little, because data that does not compress grows slightly. With less, it may fail with PROVEN_ERR_OUT_OF_BOUNDS.
• Decompressing needs you to decide how large the result may be, because the compressed data does not get to. The size of out is the limit: a stream that would produce more is refused with PROVEN_ERR_OUT_OF_BOUNDS, however small it is itself. Section 5 says why there is no version of this that grows a buffer for you.

Compiled and run by the test suite:

#include <string.h>

/*
 * Compress a buffer, get it back, and refuse to be handed more than was agreed: the two
 * whole-buffer calls, and the one rule about decompressing what somebody else sent.
 */

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();

    /* Something that compresses: text repeats itself. */
    static proven_byte_t text[4000];
    static const char line[] = "GET /index.html HTTP/1.1 - 200 - text/html; charset=utf-8\n";
    for (proven_size_t i = 0; i < sizeof text; ++i) text[i] = (proven_byte_t)line[i % (sizeof line - 1)];

    /* Compressing never fails for want of room if the buffer is as large as the bound says. */
    static proven_byte_t packed[4200];
    proven_size_t packed_len = 0;
    proven_deflate_options_t options = { .alloc = heap, .format = PROVEN_DEFLATE_GZIP };
    EXAMPLE_REQUIRE(proven_deflate_bound(PROVEN_DEFLATE_GZIP, sizeof text) <= sizeof packed, "the bound for 4,000 bytes is a little more than 4,000");
    EXAMPLE_REQUIRE(proven_deflate_all(&options, (proven_mem_view_t){ text, sizeof text }, (proven_mem_mut_t){ packed, sizeof packed }, &packed_len) == PROVEN_OK,
                    "4,000 bytes of log lines compress");
    EXAMPLE_REQUIRE(packed_len < 200, "to less than 200: the same line, over and over");
    EXAMPLE_REQUIRE(packed[0] == 0x1f && packed[1] == 0x8b, "and what came out is a gzip member - a .gz file, or an HTTP body with Content-Encoding: gzip");

    /* Decompressing: the output buffer is the limit. Here it is exactly as large as the data. */
    static proven_byte_t back[4000];
    proven_size_t back_len = 0, used = 0;
    EXAMPLE_REQUIRE(proven_inflate_all(heap, PROVEN_DEFLATE_GZIP, (proven_mem_view_t){ packed, packed_len }, (proven_mem_mut_t){ back, sizeof back }, &back_len, &used) == PROVEN_OK,
                    "it decompresses");
    EXAMPLE_REQUIRE(back_len == sizeof text && memcmp(back, text, sizeof text) == 0 && used == packed_len, "to exactly what went in, using every byte of the member");

    /* The same member into a smaller buffer is refused. This is the whole defence against a
     * "decompression bomb": you say how much you are willing to receive, and that is all the
     * room there is. A few hundred bytes cannot make this program allocate a gigabyte. */
    static proven_byte_t small[1000];
    EXAMPLE_REQUIRE(proven_inflate_all(heap, PROVEN_DEFLATE_GZIP, (proven_mem_view_t){ packed, packed_len }, (proven_mem_mut_t){ small, sizeof small }, &back_len, NULL) == PROVEN_ERR_OUT_OF_BOUNDS,
                    "4,000 bytes do not fit in 1,000: PROVEN_ERR_OUT_OF_BOUNDS");

    /* Damage is noticed. gzip carries a CRC-32 of the data; one changed bit anywhere in the
     * compressed stream changes the data or breaks the format. */
    packed[packed_len / 2] ^= 0x04;
    EXAMPLE_REQUIRE(proven_inflate_all(heap, PROVEN_DEFLATE_GZIP, (proven_mem_view_t){ packed, packed_len }, (proven_mem_mut_t){ back, sizeof back }, &back_len, NULL) == PROVEN_ERR_INVALID_FORMAT,
                    "a changed bit: PROVEN_ERR_INVALID_FORMAT");
    packed[packed_len / 2] ^= 0x04;
    EXAMPLE_REQUIRE(proven_inflate_all(heap, PROVEN_DEFLATE_GZIP, (proven_mem_view_t){ packed, packed_len - 1 }, (proven_mem_mut_t){ back, sizeof back }, &back_len, NULL) == PROVEN_ERR_INVALID_FORMAT,
                    "a member cut short is not a member");

    /* The framing is a choice made at both ends. The same data as zlib is twelve bytes
     * smaller (a shorter header, a shorter checksum), and raw is smaller again - and has no
     * checksum at all, so damage to it can go unseen. */
    proven_size_t zlib_len = 0, raw_len = 0;
    static proven_byte_t other[4200];
    options.format = PROVEN_DEFLATE_ZLIB;
    EXAMPLE_REQUIRE(proven_deflate_all(&options, (proven_mem_view_t){ text, sizeof text }, (proven_mem_mut_t){ other, sizeof other }, &zlib_len) == PROVEN_OK && zlib_len == packed_len - 12,
                    "zlib framing: 12 bytes less than gzip");
    EXAMPLE_REQUIRE(proven_inflate_all(heap, PROVEN_DEFLATE_GZIP, (proven_mem_view_t){ other, zlib_len }, (proven_mem_mut_t){ back, sizeof back }, &back_len, NULL) == PROVEN_ERR_INVALID_FORMAT,
                    "and not gzip: a decompressor must be told which it is reading");
    options.format = PROVEN_DEFLATE_RAW;
    EXAMPLE_REQUIRE(proven_deflate_all(&options, (proven_mem_view_t){ text, sizeof text }, (proven_mem_mut_t){ other, sizeof other }, &raw_len) == PROVEN_OK && raw_len == zlib_len - 6,
                    "raw: no header and no checksum, 6 bytes less again");

    /* What does not compress grows a little - by the bound, at worst. */
    static proven_byte_t noise[4000], noisy[4200];
    proven_u32 x = 2463534242u;
    for (proven_size_t i = 0; i < sizeof noise; ++i) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; noise[i] = (proven_byte_t)x; }
    proven_size_t noisy_len = 0;
    options.format = PROVEN_DEFLATE_GZIP;
    EXAMPLE_REQUIRE(proven_deflate_all(&options, (proven_mem_view_t){ noise, sizeof noise }, (proven_mem_mut_t){ noisy, sizeof noisy }, &noisy_len) == PROVEN_OK &&
                    noisy_len > sizeof noise && noisy_len <= proven_deflate_bound(PROVEN_DEFLATE_GZIP, sizeof noise),
                    "random bytes come out slightly larger, and never larger than the bound");

    return EXAMPLE_OK();
}

3. A stream#

proven_err_t proven_deflate_create(const proven_deflate_options_t *options, proven_deflate_t **out);
proven_err_t proven_deflate(proven_deflate_t *z, proven_mem_view_t in, proven_size_t *consumed,
                            proven_mem_mut_t out, proven_size_t *produced, proven_deflate_flush_t flush, bool *done);
void proven_deflate_reset(proven_deflate_t *z);
void proven_deflate_destroy(proven_deflate_t *z);

proven_err_t proven_inflate_create(proven_allocator_t alloc, proven_deflate_format_t format, proven_inflate_t **out);
proven_err_t proven_inflate(proven_inflate_t *z, proven_mem_view_t in, proven_size_t *consumed,
                            proven_mem_mut_t out, proven_size_t *produced, bool *done);
void proven_inflate_reset(proven_inflate_t *z);
void proven_inflate_restart(proven_inflate_t *z);
void proven_inflate_destroy(proven_inflate_t *z);

When the data is a file larger than memory, a response still being produced, or a connection, both directions work the same way: an object that holds the state, and one step function that takes some input and fills some output.

The contract of a step is short, and worth reading once:

• It consumes as much of in as it can and produces as much into out as it can, and tells you how much of each. It never allocates and never writes past out. (Within out, the decompressor may write up to seven bytes beyond the ones it reports: pass space that is free.)
• PROVEN_OK with nothing consumed and nothing produced is not an error. It means the step needs more of one or the other: more input, or more room. Call it again when you have some. A stream that simply stops arriving looks exactly like this, which is why a caller that knows no more input is coming must treat it as a truncated stream.
• *done becomes true when the stream has ended and everything has been produced - also when the data exactly filled the room you gave. Input after the end is not consumed: *consumed tells you where the stream ended.

When compressing, flush says how urgent the output is.

A sync flush ends on a byte boundary, and the last four bytes it produces are always 00 00 ff ff. WebSocket's permessage-deflate sends each message as a sync flush with those four bytes left off, and the receiver puts them back (Chapter 12, section 9: the WebSocket drivers cut and put back those four bytes, and with context takeover keep one compressor and one decompressor for the whole connection). That is also why a raw stream need never end: the decompressor is fed piece after piece, *done never becomes true, and what it remembers of earlier pieces is what makes later ones small.

proven_deflate_reset and proven_inflate_reset start a new stream in the same object, which is cheaper than making another. After *done, a decompressor that should read a second gzip member following the first is reset and fed from where the first ended. proven_inflate_restart starts a new stream too but keeps the last 32 KiB, so the new stream's matches may reach back into the old one: that is for permessage-deflate with context takeover, where a sender may end a message with a final block and its next message still refers to earlier ones.

Compiled and run by the test suite:

#include <string.h>

/*
 * Compression as a stream: data that arrives in pieces and leaves in pieces, through buffers
 * of whatever size you have. The same loop works for a file of any length, a response that
 * is still being produced, or a connection.
 */

/* Where the compressed bytes go. A real program writes them to a file or a socket. */
static proven_byte_t g_wire[8192];
static proven_size_t g_wire_len;

/* Give the compressor some input and take whatever output it has, 64 bytes at a time, until
 * it has taken all of the input - and, when `flush` asks for more than that, until it has
 * produced all of that too. */
static bool feed(proven_deflate_t *z, const char *text, proven_deflate_flush_t flush, bool *done) {
    proven_mem_view_t in = { (const proven_byte_t *)text, strlen(text) };
    for (;;) {
        proven_byte_t out[64];
        proven_size_t consumed = 0, produced = 0;
        if (proven_deflate(z, in, &consumed, (proven_mem_mut_t){ out, sizeof out }, &produced, flush, done) != PROVEN_OK) return false;
        if (g_wire_len + produced > sizeof g_wire) return false;
        memcpy(g_wire + g_wire_len, out, produced);
        g_wire_len += produced;
        in.ptr += consumed; in.size -= consumed;
        /* Nothing left to give, and it had less than a bufferful to say: it is up to date. */
        if (in.size == 0 && produced < sizeof out) return true;
    }
}

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();

    /* A compressor is made once. Zero in the options means the defaults: level 6, a 32 KiB
     * window. Level 1 is faster and compresses a little less; 9 is slower and a little more. */
    proven_deflate_options_t options = { .alloc = heap, .format = PROVEN_DEFLATE_ZLIB, .level = 6 };
    proven_deflate_t *z = NULL;
    EXAMPLE_REQUIRE(proven_deflate_create(&options, &z) == PROVEN_OK, "a compressor");

    /* Pieces go in as they come. With FLUSH_NONE the compressor keeps what it is given until
     * it has a block's worth - nothing may come out for a long time, and that is how it
     * compresses well. */
    bool done = false;
    EXAMPLE_REQUIRE(feed(z, "first piece of the stream; ", PROVEN_DEFLATE_FLUSH_NONE, &done), "a piece goes in");
    const proven_size_t after_first = g_wire_len;
    EXAMPLE_REQUIRE(after_first <= 2 && !done, "and nothing but the two-byte header has come out yet");

    /* A sync flush says: the other side must be able to read everything up to here, now. It
     * costs a few bytes each time - use it when somebody is waiting, not after every write. */
    EXAMPLE_REQUIRE(feed(z, "second piece of the stream; ", PROVEN_DEFLATE_FLUSH_SYNC, &done) && g_wire_len > after_first + 20 && !done,
                    "after a sync flush both pieces are on the wire");
    const proven_size_t at_flush = g_wire_len;

    /* FINISH ends the stream: the last block, and for zlib and gzip the checksum. */
    EXAMPLE_REQUIRE(feed(z, "third and last piece.", PROVEN_DEFLATE_FLUSH_FINISH, &done) && done, "the last piece, and the stream is finished");

    /* The receiving side: a decompressor, fed 10 bytes at a time into a 16-byte buffer. */
    proven_inflate_t *u = NULL;
    EXAMPLE_REQUIRE(proven_inflate_create(heap, PROVEN_DEFLATE_ZLIB, &u) == PROVEN_OK, "a decompressor");
    char text[200];
    proven_size_t text_len = 0, at = 0, seen_at_flush = 0;
    bool ended = false;
    /* First only what had been written when the sync flush returned; then the rest. */
    for (proven_size_t limit = at_flush; !ended; limit = g_wire_len) {
        for (;;) {
            proven_byte_t out[16];
            proven_size_t consumed = 0, produced = 0;
            const proven_size_t give = limit - at < 10 ? limit - at : 10;
            if (proven_inflate(u, (proven_mem_view_t){ g_wire + at, give }, &consumed, (proven_mem_mut_t){ out, sizeof out }, &produced, &ended) != PROVEN_OK) break;
            if (text_len + produced > sizeof text) break;
            memcpy(text + text_len, out, produced);
            text_len += produced;
            at += consumed;
            /* PROVEN_OK with nothing consumed and nothing produced: it has used everything
             * it was offered and wants more. That is not an error - it is how a stream waits. */
            if (ended || (consumed == 0 && produced == 0)) break;
        }
        if (limit == at_flush) seen_at_flush = text_len;
        else break;
    }
    static const char whole[] = "first piece of the stream; second piece of the stream; third and last piece.";
    EXAMPLE_REQUIRE(ended && text_len == sizeof whole - 1 && memcmp(text, whole, text_len) == 0, "the three pieces come out as one text");
    EXAMPLE_REQUIRE(at == g_wire_len, "and the stream ended exactly where the compressor stopped writing");
    EXAMPLE_REQUIRE(seen_at_flush >= 55, "at the flush point the receiver already had both of the first two pieces");

    /* Both objects are reused for the next stream rather than made again. */
    proven_deflate_reset(z);
    proven_inflate_reset(u);
    g_wire_len = 0;
    EXAMPLE_REQUIRE(feed(z, "another stream", PROVEN_DEFLATE_FLUSH_FINISH, &done) && done, "the same compressor, a new stream");
    proven_byte_t again[32];
    proven_size_t consumed = 0, produced = 0;
    EXAMPLE_REQUIRE(proven_inflate(u, (proven_mem_view_t){ g_wire, g_wire_len }, &consumed, (proven_mem_mut_t){ again, sizeof again }, &produced, &ended) == PROVEN_OK &&
                    ended && produced == 14 && memcmp(again, "another stream", 14) == 0, "and the same decompressor reads it");

    proven_deflate_destroy(z);
    proven_inflate_destroy(u);
    return EXAMPLE_OK();
}

4. Levels, windows and what they cost#

A compressor is made from a proven_deflate_options_t. Zero-initialise it, set alloc, and set what you want changed:

The level trades time for size, and the trade is lopsided. On the development machine, compressing this library's own sources and manual (3.2 MiB of text):

From 1 to 6 buys a seventh off the size for half the speed. From 6 to 9 buys almost nothing for nearly half the speed again. Decompression does not care what level was used.

zlib, the implementation everybody else uses, compresses the same data to the same sizes - within a quarter of a percent at levels 6 and 9, and it is a little larger at level 1 - and is about twice as fast at compressing, nearly three times at level 1. At decompressing the two are about the same: zlib 1.3.1, called from Python on the same data, gave between 190 and 310 MiB/s as the machine's load moved. (Before v0.42.0 this library's decompressor read a bit at a time and gave 75 to 90 MiB/s.) The compressor was written to be read; if its figures are too slow for a program, that program wants zlib.

The window is mostly a question of memory. A compressor holds twice its window and tables beside it; a decompressor always holds 32 KiB, because it cannot know what window the other side used:

A smaller window compresses less well - repeats further apart than the window are not found - and makes no difference to speed worth planning around. Use it where there are many compressors at once (one per connection) or little memory.

5. Data from somebody else#

Compressed data that arrives from outside the program is the dangerous case, for one reason:

It can be far larger than it looks. DEFLATE can say "the last byte again, 258 times" in two bytes, again and again. A hundred and seventeen bytes in this library's tests expand to 25,801; a megabyte can become a gigabyte. A program that decompresses whatever it is sent into a buffer that grows as needed has given every sender the ability to exhaust its memory.

So nothing here grows. proven_inflate writes only into the space you pass it, and when that is full it stops and says so; proven_inflate_all takes the limit as the size of its output. Decide the largest result that makes sense for what you are reading - a configuration file, a request body, a message - and refuse anything beyond it. The decompressor's own memory is fixed at about 35 KiB whatever it is fed.

And it can simply be wrong, by accident or on purpose:

After an error a decompressor returns that error from every call until it is reset. Data it produced before the error is not to be trusted as complete: with gzip and zlib the checksum is only known to match at the very end.

Two more things worth knowing.

• Compression can leak what it compresses. If a secret and text chosen by an attacker are compressed together and the attacker can see the size of the result, the size says whether the chosen text repeated part of the secret, and the secret can be guessed a character at a time. This has broken HTTPS in practice (CRIME, BREACH). The rule is the application's to keep: do not compress a secret together with anything a stranger controls.
• Raw DEFLATE has no checksum. If the bytes may have been damaged on the way and the format around them does not check, use zlib or gzip.

6. Over HTTP#

void proven_http_exchange_compress(proven_http_exchange_t *exchange);     /* the server of Chapter 11 */
void proven_http_stream_compress(proven_http_stream_t *stream);           /* the server of Chapter 15 */

bool proven_http_accepts_coding(const proven_http_header_t *headers, proven_size_t count, proven_http_coding_t coding);
unsigned proven_http_accept_weight(const proven_http_header_t *headers, proven_size_t count, proven_http_coding_t coding);
proven_http_coding_t proven_http_content_coding(const proven_http_header_t *headers, proven_size_t count);

HTTP calls this a content coding: the server compresses the body and says so in Content-Encoding, and it may only do that for a client whose Accept-Encoding allowed it. The four HTTP drivers of Chapter 11 and Chapter 15 do both halves - and do neither until you ask. A program that sets nothing sends the same bytes as before.

Unlike the rest of this chapter, this part needs sockets and is not in a freestanding build - except the three helper functions, which are plain header arithmetic in http.h.

A server compresses a response when its handler asks for that response. One call, before the response begins:

Vary is there because the response now depends on a request header, and a cache in between must not hand the gzip to a client that cannot read it.

A server compresses in Zstandard too when its configuration says compress_zstd. A response asked to be compressed then goes as zstd when the request's Accept-Encoding weighs zstd at least as high as gzip, and as gzip otherwise, as before. curl, and the browsers that take zstd, send the two at one weight - gzip, deflate, br, zstd - so they get zstd; a client that writes gzip;q=1, zstd;q=0.5 gets gzip, and one that does not name zstd gets what it got before. The tie goes to zstd because it is the cheaper of the two to make (section 7: six times the speed of gzip at level 1, at gzip 1's size or less). The level and the window are compress_zstd_level (1 to 9, zero is 1) and compress_zstd_window_log (10 to 23, zero is 17, 128 KiB); a body sent in one piece is compressed with tables sized to it whatever the window, a streamed one holds about 0.8 MiB at those defaults until it ends. Level 6 gives gzip 6's size or less at about three times its speed, for a server that wants gzip 6's size; its tables make a streamed response about 1.8 MiB. proven_http_accept_weight gives you the same weights, for a choice of your own.

A body sent in one piece is compressed first and sent with its new Content-Length. A body written in pieces is compressed as it is written and sent chunked, whatever length you announced - the length is still what you must write.

A client asks and decodes when its configuration says decompress. It then sends Accept-Encoding: gzip and decodes a body that comes back as gzip or deflate, on the way to you: proven_http_client_read fills your buffer with decoded bytes, and the event-driven client's on_body receives decoded pieces of at most 16 KiB.

With decompress_zstd as well, it asks for Zstandard too - Accept-Encoding: zstd, gzip

• and decodes a zstd body in the same way, with section 7's decoder and the 8 MiB window

limit that RFC 9659 sets for HTTP. It is a separate switch because of that window: a server may make a client hold up to 8 MiB for one response, where gzip needs 35 KiB. Without decompress, decompress_zstd is PROVEN_ERR_INVALID_ARG.

With decompress_brotli, it asks for Brotli too - br joins the list, Accept-Encoding: zstd, br, gzip with both switches - and decodes a br body with section 8's decoder, which takes every window RFC 7932 allows, up to 16 MiB; no HTTP specification sets a lower one, as RFC 9659 does for Zstandard. It is a switch of its own for the same reason as Zstandard's: a server decides how much of that a response costs you. Without decompress it is PROVEN_ERR_INVALID_ARG, and in a build with PROVEN_NO_BROTLI (section 8) PROVEN_ERR_UNSUPPORTED. The servers never send br: there is no Brotli encoder here.

Example: a page compressed, an account page not#

#include <stdio.h>
#include <string.h>

/*
 * Compressed responses over HTTP: a server that compresses when its handler asks and the
 * client accepts, and a client that asks and decodes.
 *
 * Both are off until the program says otherwise. The server's part is one call in the
 * handler, per response; the client's part is one flag in its configuration.
 */

static proven_byte_t g_page[20000];        /* the page being served: text, so it compresses */

static void fill_page(void) {
    proven_size_t n = 0;
    for (unsigned k = 0; n < sizeof g_page; ++k) {
        char line[48];
        int len = snprintf(line, sizeof line, "row %u of a table that says much the same\n", k);
        for (int i = 0; i < len && n < sizeof g_page; ++i) g_page[n++] = (proven_byte_t)line[i];
    }
}

static void handle(void *ctx, proven_http_exchange_t *x) {
    proven_http_server_t **server = ctx;
    const proven_http_request_t *req = proven_http_exchange_request(x);
    proven_mem_view_t page = { g_page, sizeof g_page };

    if (proven_u8str_view_eq(req->target, PROVEN_LIT("/page"))) {
        /* One call, before the response begins. The server then does the rest: it reads the
         * request's Accept-Encoding, compresses if gzip is allowed, and writes
         * Content-Encoding, Vary and the new Content-Length. */
        proven_http_exchange_compress(x);
        proven_http_header_t type = { PROVEN_LIT("Content-Type"), PROVEN_LIT("text/plain") };
        (void)proven_http_exchange_respond(x, 200, &type, 1, page);

    } else if (proven_u8str_view_eq(req->target, PROVEN_LIT("/account"))) {
        /* Not asked for here, on purpose: this response would carry a secret next to text
         * the client chose, and the size of a compressed body gives the secret away a byte
         * at a time. Compression is asked for per response because only the handler knows. */
        (void)proven_http_exchange_respond(x, 200, NULL, 0, proven_mem_view_from_u8(PROVEN_LIT("token=... you searched for: ...\n")));

    } else if (proven_u8str_view_eq(req->target, PROVEN_LIT("/accepts"))) {
        /* The same question the server asks, for a handler that wants to choose for itself -
         * between a file and its precompressed twin, say. */
        bool gzip = proven_http_accepts_coding(req->headers, req->header_count, PROVEN_HTTP_CODING_GZIP);
        (void)proven_http_exchange_respond(x, 200, NULL, 0, proven_mem_view_from_u8(gzip ? PROVEN_LIT("gzip") : PROVEN_LIT("identity")));

    } else if (proven_u8str_view_eq(req->target, PROVEN_LIT("/log"))) {
        /* A compressed response written in pieces holds back what it is given. A flush hands
         * it over: the client reads "started" now, not when the work is done. */
        proven_http_exchange_compress(x);
        if (proven_http_exchange_begin(x, 200, NULL, 0, PROVEN_HTTP_LENGTH_UNKNOWN) == PROVEN_OK &&
            proven_http_exchange_write(x, proven_mem_view_from_u8(PROVEN_LIT("started\n"))) == PROVEN_OK &&
            proven_http_exchange_flush(x) == PROVEN_OK) {
            (void)proven_http_exchange_write(x, proven_mem_view_from_u8(PROVEN_LIT("finished\n")));
        }

    } else {
        (void)proven_http_exchange_respond(x, 200, NULL, 0, proven_mem_view_from_u8(PROVEN_LIT("bye\n")));
        proven_http_server_stop(*server);
    }
}

static void serve(void *arg) { (void)proven_http_server_run(*(proven_http_server_t **)arg); }

/* GET `path`; report the body's size as read, the Content-Length, and the coding named. */
static bool get(proven_http_client_t *client, proven_u16 port, const char *path,
                proven_size_t *read_size, proven_u64 *content_length, proven_http_coding_t *coding, proven_u8str_t *body) {
    char url[96];
    int n = snprintf(url, sizeof url, "http://127.0.0.1:%u%s", (unsigned)port, path);
    proven_http_client_response_t resp;
    bool ok = proven_http_client_get(client, (proven_u8str_view_t){ (const proven_byte_t *)url, (proven_size_t)n }, &resp) == PROVEN_OK && resp.status == 200;
    if (ok) {
        /* The headers are the server's, untouched: this is how to see what was sent. */
        *coding = proven_http_content_coding(resp.headers, resp.header_count);
        proven_u8str_view_t length = { 0 };
        *content_length = 0;
        if (proven_http_header_find(resp.headers, resp.header_count, PROVEN_LIT("Content-Length"), &length)) {
            for (proven_size_t i = 0; i < length.size; ++i) *content_length = *content_length * 10 + (proven_u64)(length.ptr[i] - '0');
        }
        /* The limit is on what arrives here - decoded bytes, when the client decodes. */
        (void)proven_u8str_reset(body);
        ok = proven_http_client_read_all(&resp, proven_heap_allocator(), body, 1024 * 1024) == PROVEN_OK;
        *read_size = proven_u8str_as_view(body).size;
    }
    proven_http_client_finish(&resp);
    return ok;
}

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();
    fill_page();

    static proven_http_server_t *server;
    proven_http_server_config_t config = { .alloc = heap, .handler = handle, .handler_ctx = &server };
    config.compress_level = 6;              /* 1 is fastest, 9 smallest; zero means this */
    EXAMPLE_REQUIRE(proven_http_server_create(&config, &server) == PROVEN_OK, "a server");
    proven_net_addr_t at;
    proven_err_t err = proven_http_server_listen(server, proven_net_addr_loopback(PROVEN_NET_FAMILY_IPV4, 0), &at);
    if (err == PROVEN_ERR_PERMISSION || err == PROVEN_ERR_UNSUPPORTED) {
        printf("no sockets in this environment; nothing to show\n");
        proven_http_server_destroy(server);
        return EXAMPLE_OK();
    }
    EXAMPLE_REQUIRE(err == PROVEN_OK, "it listens");
    proven_job_sys_t *threads = NULL;
    proven_job_group_t running;
    proven_job_group_init(&running);
    EXAMPLE_REQUIRE(proven_job_system_init(heap, 1, 4, &threads) == PROVEN_OK &&
                    proven_job_group_submit(threads, &running, serve, &server) == PROVEN_OK, "the server loop is started");

    /* Two clients: one as it always was, one that asks for compressed responses. */
    proven_http_client_config_t plain_config = { .alloc = heap, .max_idle_connections = 2 };
    proven_http_client_config_t decoding_config = { .alloc = heap, .max_idle_connections = 2, .decompress = true };
    proven_http_client_t *plain = NULL, *decoding = NULL;
    EXAMPLE_REQUIRE(proven_http_client_create(&plain_config, &plain) == PROVEN_OK &&
                    proven_http_client_create(&decoding_config, &decoding) == PROVEN_OK, "two clients");

    proven_u8str_t body = { 0 };
    proven_size_t read_size = 0;
    proven_u64 sent = 0;
    proven_http_coding_t coding = PROVEN_HTTP_CODING_IDENTITY;

    /* The client that sets nothing sends no Accept-Encoding, and nothing changes for it. */
    EXAMPLE_REQUIRE(get(plain, at.port, "/page", &read_size, &sent, &coding, &body), "the page, to a client that did not ask");
    EXAMPLE_REQUIRE(coding == PROVEN_HTTP_CODING_IDENTITY && sent == sizeof g_page && read_size == sizeof g_page, "arrives as it is");

    /* The one that asks gets the same bytes from a fraction of them. */
    EXAMPLE_REQUIRE(get(decoding, at.port, "/page", &read_size, &sent, &coding, &body), "the page, to a client that asked");
    EXAMPLE_REQUIRE(coding == PROVEN_HTTP_CODING_GZIP && read_size == sizeof g_page &&
                    memcmp(proven_u8str_as_view(&body).ptr, g_page, sizeof g_page) == 0, "was sent as gzip and read as the page");
    EXAMPLE_REQUIRE(sent < sizeof g_page / 5, "in less than a fifth of the bytes");
    printf("the page: %u bytes, sent as %u\n", (unsigned)sizeof g_page, (unsigned)sent);

    /* A response whose handler did not ask is not compressed, whoever asks for it. */
    EXAMPLE_REQUIRE(get(decoding, at.port, "/account", &read_size, &sent, &coding, &body) && coding == PROVEN_HTTP_CODING_IDENTITY, "the account page is sent as it is");

    EXAMPLE_REQUIRE(get(decoding, at.port, "/accepts", &read_size, &sent, &coding, &body) &&
                    proven_u8str_view_eq(proven_u8str_as_view(&body), PROVEN_LIT("gzip")), "the handler can see that this client accepts gzip");
    EXAMPLE_REQUIRE(get(plain, at.port, "/accepts", &read_size, &sent, &coding, &body) &&
                    proven_u8str_view_eq(proven_u8str_as_view(&body), PROVEN_LIT("identity")), "and that the other does not");

    /* A response flushed in the middle is still one gzip stream. */
    EXAMPLE_REQUIRE(get(decoding, at.port, "/log", &read_size, &sent, &coding, &body) && coding == PROVEN_HTTP_CODING_GZIP &&
                    proven_u8str_view_eq(proven_u8str_as_view(&body), PROVEN_LIT("started\nfinished\n")), "a log sent in two parts, the first flushed, reads as one");

    EXAMPLE_REQUIRE(get(plain, at.port, "/quit", &read_size, &sent, &coding, &body), "stop");
    proven_job_group_wait(threads, &running);
    proven_u8str_destroy(heap, &body);
    proven_http_client_destroy(plain);
    proven_http_client_destroy(decoding);
    proven_http_server_destroy(server);
    proven_job_system_close(threads);
    proven_job_system_destroy(threads);
    return EXAMPLE_OK();
}

Example: the same on a loop#

#include <stdio.h>
#include <string.h>

/*
 * The same on a loop: the event-driven server compressing a response that is written in
 * pieces, and the event-driven client decoding it as it arrives.
 *
 * Neither holds the body. The server compresses what it is given into its output queue, under
 * the queue's limit; the client hands on decoded pieces of at most 16 KiB.
 */

#define REPORT_BYTES ((proven_size_t)300000)

typedef struct {
    proven_loop_t *loop;
    proven_http_stream_t *stream;      /* the one response being written */
    proven_size_t written;
    proven_size_t received, pieces, largest;
    unsigned long sum_sent, sum_received;
    bool gzip, intact, done;
    proven_err_t why;
} ex_app_t;

/* The report is generated as it is written: there is no buffer holding all of it. */
static proven_byte_t report_byte(proven_size_t i) { return (proven_byte_t)("measured value \n"[i % 16]); }

// ---- the server --------------------------------------------------------------

/* Write until the server takes no more; on_writable calls this again when there is room. */
static void pump(ex_app_t *app) {
    proven_byte_t piece[4096];
    while (app->written < REPORT_BYTES) {
        proven_size_t n = REPORT_BYTES - app->written < sizeof piece ? REPORT_BYTES - app->written : sizeof piece;
        for (proven_size_t i = 0; i < n; ++i) piece[i] = report_byte(app->written + i);
        proven_result_size_t took = proven_http_stream_write(app->stream, (proven_mem_view_t){ piece, n });
        if (took.err != PROVEN_OK) return;
        for (proven_size_t i = 0; i < took.value; ++i) app->sum_sent += piece[i];
        app->written += took.value;
        /* The first piece is handed over at once: the reader sees the report begin while
         * the rest is still being made. Without this it would wait in the compressor. */
        if (app->written == sizeof piece) (void)proven_http_stream_flush(app->stream);
        if (took.value < n) return;        /* the compressed output is at its limit: wait */
    }
    (void)proven_http_stream_end(app->stream);
}

static void on_request(void *ctx, proven_http_stream_t *stream, const proven_http_request_t *head) {
    (void)head;
    ex_app_t *app = ctx;
    app->stream = stream;
    /* Before the response begins. From here on the body is written exactly as it would be
     * without it: the length given is still the length to write, though the client is sent
     * chunks of gzip. What is written may wait in the compressor until more follows. */
    proven_http_stream_compress(stream);
    if (proven_http_stream_begin(stream, 200, NULL, 0, REPORT_BYTES) == PROVEN_OK) pump(app);
}
static void on_writable(void *ctx, proven_http_stream_t *stream) { (void)stream; pump(ctx); }

// ---- the client --------------------------------------------------------------

static void on_response(void *ctx, proven_http_event_request_t *request, const proven_http_response_t *head) {
    (void)request;
    ex_app_t *app = ctx;
    app->gzip = proven_http_content_coding(head->headers, head->header_count) == PROVEN_HTTP_CODING_GZIP;
}

/* Decoded pieces. A piece is a view that is good until this function returns. */
static void on_body(void *ctx, proven_http_event_request_t *request, proven_mem_view_t piece, bool last) {
    (void)request; (void)last;
    ex_app_t *app = ctx;
    for (proven_size_t i = 0; i < piece.size; ++i) {
        if (piece.ptr[i] != report_byte(app->received + i)) app->intact = false;
        app->sum_received += piece.ptr[i];
    }
    app->received += piece.size;
    app->pieces++;
    if (piece.size > app->largest) app->largest = piece.size;
}

static void on_done(void *ctx, proven_http_event_request_t *request, proven_err_t why) {
    (void)request;
    ex_app_t *app = ctx;
    app->why = why;
    app->done = true;
    proven_loop_stop(app->loop);
}

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();
    ex_app_t app = { .intact = true };
    EXAMPLE_REQUIRE(proven_loop_create(heap, &app.loop) == PROVEN_OK, "a loop");

    /* The window sets what each compressed response holds while it is being written: about
     * 53 KiB at 12 bits, 325 KiB at the full 15. With many at once, that is the number to choose. */
    proven_http_event_server_config_t server_config = { .on = { .on_request = on_request, .on_writable = on_writable }, .ctx = &app, .compress_window_bits = 12 };
    proven_http_event_server_t *server = NULL;
    proven_net_addr_t at;
    EXAMPLE_REQUIRE(proven_http_event_server_create(app.loop, &server_config, &server) == PROVEN_OK, "a server");
    proven_err_t err = proven_http_event_server_listen(server, proven_net_addr_loopback(PROVEN_NET_FAMILY_IPV4, 0), &at);
    if (err == PROVEN_ERR_PERMISSION || err == PROVEN_ERR_UNSUPPORTED) {
        printf("no sockets in this environment; nothing to show\n");
        proven_http_event_server_destroy(server);
        proven_loop_destroy(app.loop);
        return EXAMPLE_OK();
    }
    EXAMPLE_REQUIRE(err == PROVEN_OK, "it listens");

    /* `decompress` asks for gzip and decodes it; `max_body_bytes` then also bounds the decoded
     * size, so a small body that unfolds into a huge one is cut off at the limit. */
    proven_http_event_client_config_t client_config = { .decompress = true, .max_body_bytes = 1024 * 1024 };
    proven_http_event_client_t *client = NULL;
    EXAMPLE_REQUIRE(proven_http_event_client_create(app.loop, &client_config, &client) == PROVEN_OK, "a client that decodes");

    char url[64];
    int n = snprintf(url, sizeof url, "http://127.0.0.1:%u/report", (unsigned)at.port);
    proven_http_event_request_options_t options = {
        .url = { (const proven_byte_t *)url, (proven_size_t)n },
        .on = { on_response, on_body, NULL, on_done },
        .ctx = &app,
    };
    EXAMPLE_REQUIRE(proven_http_event_client_start(client, &options, NULL) == PROVEN_OK, "the request is started");
    EXAMPLE_REQUIRE(proven_loop_run(app.loop) == PROVEN_OK && app.done, "the loop ran until it was done");

    EXAMPLE_REQUIRE(app.why == PROVEN_OK && app.gzip, "the response came as gzip");
    EXAMPLE_REQUIRE(app.received == REPORT_BYTES && app.intact && app.sum_received == app.sum_sent, "and was delivered as the report that was written");
    EXAMPLE_REQUIRE(app.largest <= 16384 && app.pieces >= REPORT_BYTES / 16384, "in pieces of at most 16 KiB");
    printf("%u bytes written, compressed, sent, decoded and received\n", (unsigned)app.received);

    proven_http_event_client_destroy(client);
    proven_http_event_server_destroy(server);
    proven_loop_destroy(app.loop);
    return EXAMPLE_OK();
}

Reference#

Cautions, and what goes wrong#

• Do not ask for a response that mixes a secret with text the client chose. This is the leak of section 5 in its best-known form (BREACH): a page that carries a session token and also echoes a search term, compressed, tells an observer of the encrypted connection - through its length alone - whether the term matched part of the token. TLS does not help; it hides bytes, not sizes. This is why the server has no "compress everything" setting: the call is per response because the judgement is.
• A streamed, compressed response does not arrive piece by piece unless you flush it. What you write may sit in the compressor until more is written or the response ends. For an event stream (Chapter 10, section 13) or anything else a client must see as it happens, call proven_http_exchange_flush or proven_http_stream_flush after each piece: what was written so far then leaves in a form the client can read at once. A flush costs a few bytes and some of the compression, so flush where a reader is waiting and not after every write - or do not compress such a response at all.
• A compressed response of a different size needs a different validator. If you send an ETag, the compressed and the plain response are two representations; give them different tags, or a cache may match one against the other. The server does not rewrite yours.
• The client's headers are the server's. With decompress, Content-Encoding: gzip is still there and Content-Length still counts the compressed bytes - not the bytes you read. Count what you read, or look at proven_http_content_coding to know which it was.
• The limit on what a server may send you is in decoded bytes. read_all's max_bytes, and the event-driven client's max_body_bytes, count what comes out of the decoder: two kilobytes that unfold into two megabytes are cut off at your limit, not at theirs. A plain proven_http_client_read is bounded by the buffer you give it, as always.
• A damaged compressed body is PROVEN_ERR_INVALID_FORMAT, never a short success: a stream that is cut off, fails its checksum, or is followed by bytes that are not another gzip member (or Zstandard frame). Several gzip members, or Zstandard frames, in a row are read as one body; a Brotli stream has nothing after it.
• deflate means two things in practice. The standard says a zlib stream; some servers send raw DEFLATE. The client looks at the first two bytes and reads whichever it is. It never asks for deflate - only gzip, zstd with decompress_zstd and br with decompress_brotli - and the servers never send it.
• Not decoded: a 206 Partial Content (a range of a compressed body is not a compressed body - and with decompress set, a request that carries Range is sent without Accept-Encoding); zstd without decompress_zstd; br without decompress_brotli; any other coding (compress); two codings applied one over the other. Such a body reaches you as it was sent, with its header.
• Memory. A response being decoded costs about 35 KiB (52 KiB in the event-driven client) while it is open - a zstd one, as much as its frame's window, up to 8 MiB, and about 400 KiB more, and a br one as much as its stream's window, up to 16 MiB, and its codes (section 8), each allocated as its output grows. A streamed response being compressed costs what section 4's table says for the window - 325 KiB by default - until it ends; one sent in one piece costs that only for the call, with a window no larger than the body. Ten thousand streamed responses at the default window are 3 GiB: lower compress_window_bits, or compress fewer. In zstd a streamed response holds about 0.8 MiB at the defaults (level 1, a 128 KiB window) - more than gzip's 325 KiB - and up to 2 MiB at level 3 with a 512 KiB window; one sent in one piece needs tables sized to the body, a few kilobytes for a short one.

7. Zstandard#

#include "proven/zstd.h"

proven_err_t proven_zstd_decoder_create(proven_allocator_t alloc, proven_u64 window_max, proven_zstd_decoder_t **out);
void proven_zstd_decoder_destroy(proven_zstd_decoder_t *z);
void proven_zstd_decoder_reset(proven_zstd_decoder_t *z);
proven_err_t proven_zstd_decode(proven_zstd_decoder_t *z, proven_mem_view_t in, proven_size_t *consumed,
                                proven_mem_mut_t out, proven_size_t *produced, bool *done);
proven_err_t proven_zstd_decode_all(proven_allocator_t alloc, proven_mem_view_t in, proven_mem_mut_t out, proven_size_t *written);

Zstandard (RFC 8878) is a newer format than DEFLATE: .zst files, HTTP's Content-Encoding: zstd (RFC 9659), and some package formats. Its compressors range from faster than gzip's fastest to smaller than gzip's smallest; whatever was used, it decodes quickly. This library reads it, and since v0.58.0 writes it - at nine levels since v0.59.0, twelve since v0.101.0 and nineteen since v0.102.0 (below, "Writing Zstandard").

The decoder is used like section 3's decompressor - a state, and a step that takes what input there is and fills what output space there is - with two differences that the format makes necessary:

• A step may allocate. Zstandard reads parts of each block from its end, so a block (up to 128 KiB compressed) is held whole before it is decoded, and decoded whole next to the history that later blocks refer to. These buffers grow as a frame's output grows - a frame that says it holds 300 bytes costs 300 bytes of history, not 8 MiB - and are kept for the next frame. So proven_zstd_decode can return PROVEN_ERR_NOMEM.
• Output can wait in the decoder, by up to one block, while the space you give is too small for it.

The window is the memory, and the limit is yours. Every frame says how far back it may refer - its window - and a decoder must keep that much of what it produced. A frame may claim terabytes. window_max is the most you agree to: 0 means 8 MiB, which RFC 9659 sets for HTTP. A frame that needs more is PROVEN_ERR_OUT_OF_BOUNDS before anything is allocated for it.

A stream is a sequence of frames. *done becomes true where a frame ends, and that call stops there: what it consumed is that frame. Call again with the rest and the next frame begins - no reset is needed. Skippable frames (magic numbers 0x184D2A50 to 0x184D2A5F) are read past, producing nothing. A frame that names a dictionary is decoded only by a decoder that has it ("Dictionaries" below): without it, PROVEN_ERR_UNSUPPORTED; content sent over HTTP does not use one.

Example: a buffer, two frames, and a window too large#

#include <string.h>

/*
 * Zstandard: a whole buffer, then a stream of two frames read piece by piece, and the window
 * limit that keeps a stranger's frame from deciding how much memory this program spends.
 */

/* 4,000 bytes of log lines, as libzstd wrote them at level 19 with a checksum: 77 bytes. */
static const proven_byte_t FRAME[] = {
    0x28, 0xb5, 0x2f, 0xfd, 0x64, 0xa0, 0x0e, 0xfd, 0x01, 0x00, 0x62, 0xc3,
    0x0c, 0x11, 0x90, 0x7d, 0x00, 0x04, 0x1c, 0xf9, 0xc4, 0x4b, 0x1e, 0x4d,
    0x80, 0xa0, 0x8f, 0x99, 0x3a, 0xe6, 0x0c, 0xe0, 0x84, 0xb9, 0x79, 0xda,
    0x52, 0xe7, 0x47, 0xe1, 0xa3, 0xb1, 0xbb, 0xdc, 0x1f, 0x9e, 0x10, 0xf3,
    0xe1, 0x8b, 0x28, 0xa3, 0x39, 0xc7, 0xde, 0xde, 0x4d, 0x45, 0x97, 0x11,
    0xd7, 0xf1, 0x4e, 0xad, 0x02, 0x00, 0xc6, 0xde, 0x95, 0x2f, 0x3b, 0x3b,
    0x9f, 0xe8, 0x22, 0xa1, 0x2a,
};

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();
    static const char line[] = "GET /index.html HTTP/1.1 - 200 - text/html; charset=utf-8\n";
    static proven_byte_t text[4000];
    for (proven_size_t i = 0; i < sizeof text; ++i) text[i] = (proven_byte_t)line[i % (sizeof line - 1)];

    /* A whole buffer: as with gzip, the output buffer is the limit. */
    static proven_byte_t out[8000];
    proven_size_t n = 0;
    EXAMPLE_REQUIRE(proven_zstd_decode_all(heap, (proven_mem_view_t){ FRAME, sizeof FRAME }, (proven_mem_mut_t){ out, sizeof out }, &n) == PROVEN_OK &&
                    n == sizeof text && memcmp(out, text, n) == 0, "77 bytes of Zstandard decode to the 4,000 bytes libzstd was given");
    EXAMPLE_REQUIRE(proven_zstd_decode_all(heap, (proven_mem_view_t){ FRAME, sizeof FRAME }, (proven_mem_mut_t){ out, 3999 }, &n) == PROVEN_ERR_OUT_OF_BOUNDS,
                    "and do not fit in 3,999: PROVEN_ERR_OUT_OF_BOUNDS");

    /* A stream: the same frame twice, given 10 bytes at a time with 500 bytes of room. Each
     * call takes what it can; `done` says a frame has just ended, and the next call simply
     * goes on with the frame that follows. */
    static proven_byte_t two[2 * sizeof FRAME];
    memcpy(two, FRAME, sizeof FRAME);
    memcpy(two + sizeof FRAME, FRAME, sizeof FRAME);
    proven_zstd_decoder_t *z = NULL;
    EXAMPLE_REQUIRE(proven_zstd_decoder_create(heap, 0, &z) == PROVEN_OK, "a decoder with the default window limit, 8 MiB");
    proven_size_t in_at = 0, out_at = 0;
    int frames = 0;
    while (in_at < sizeof two || out_at < sizeof out) {
        proven_size_t give = sizeof two - in_at < 10 ? sizeof two - in_at : 10, room = sizeof out - out_at < 500 ? sizeof out - out_at : 500;
        proven_size_t used = 0, made = 0;
        bool done = false;
        EXAMPLE_REQUIRE(proven_zstd_decode(z, (proven_mem_view_t){ two + in_at, give }, &used, (proven_mem_mut_t){ out + out_at, room }, &made, &done) == PROVEN_OK, "a step");
        in_at += used;
        out_at += made;
        if (done && used + made > 0) frames++;
        if (used == 0 && made == 0) break;              /* nothing more to give, or nowhere to put it */
    }
    EXAMPLE_REQUIRE(frames == 2 && out_at == 2 * sizeof text && memcmp(out + sizeof text, text, sizeof text) == 0, "two frames, one after the other, 8,000 bytes");

    /* The window limit. Every frame says how far back it may refer, and a decoder must keep
     * that much; this hand-made header asks for 1 MiB. A decoder limited to 64 KiB refuses it
     * before allocating anything for it. reset makes the decoder usable again. */
    static const proven_byte_t wide[] = { 0x28, 0xb5, 0x2f, 0xfd, 0x00, (20 - 10) << 3, 0x19, 0x00, 0x00, 'a', 'b', 'c' };
    proven_zstd_decoder_t *small = NULL;
    proven_size_t used = 0, made = 0;
    bool done = false;
    EXAMPLE_REQUIRE(proven_zstd_decoder_create(heap, 64 * 1024, &small) == PROVEN_OK, "a decoder limited to 64 KiB");
    EXAMPLE_REQUIRE(proven_zstd_decode(small, (proven_mem_view_t){ wide, sizeof wide }, &used, (proven_mem_mut_t){ out, sizeof out }, &made, &done) == PROVEN_ERR_OUT_OF_BOUNDS,
                    "a frame that needs 1 MiB of window: PROVEN_ERR_OUT_OF_BOUNDS");
    proven_zstd_decoder_reset(small);
    EXAMPLE_REQUIRE(proven_zstd_decode(small, (proven_mem_view_t){ FRAME, sizeof FRAME }, &used, (proven_mem_mut_t){ out, sizeof out }, &made, &done) == PROVEN_OK &&
                    done && made == sizeof text, "after a reset, a frame within the limit decodes");
    EXAMPLE_REQUIRE(proven_zstd_decode(z, (proven_mem_view_t){ wide, sizeof wide }, &used, (proven_mem_mut_t){ out, sizeof out }, &made, &done) == PROVEN_OK &&
                    done && made == 3, "while the default limit takes it");

    proven_zstd_decoder_destroy(small);
    proven_zstd_decoder_destroy(z);
    return EXAMPLE_OK();
}

Reference#

Cautions, and what goes wrong#

• The window, not the size of the data, decides the memory. A server - or anyone whose frames you decode - chooses it, up to your limit. A thousand responses at once, each with an 8 MiB window, are 8 GiB. Lower window_max where you can (a decoder for your own .zst files knows what window they use), and count decoders the way you count connections.
• The checksum is optional in Zstandard. A frame written without one can be damaged and still decode to wrong bytes; the decoder can only refuse what does not parse. Where it matters, check what you decoded yourself.
• Not a gzip stream. proven_zstd_decode reads Zstandard only. Over HTTP, the clients choose the decoder from Content-Encoding; for files, look at the first four bytes (28 b5 2f fd).

Nothing that libzstd refuses is accepted; some damage it reads through is refused. Where RFC 8878 leaves a case to the decoder it was settled as libzstd 1.5.7 settles it - Huffman codes up to 12 bits are read - or more strictly: every Huffman and sequence stream must be read to its first bit exactly, which libzstd's fast Huffman decoder does not check for four streams, and a compressed block of no bytes is refused, as RFC 8878 has it (libzstd's streaming decoder takes it as empty, its one-call decoder refuses it). Outside the registered tests, 80,232 truncated and changed copies of 92 streams libzstd made were given to both: none that libzstd refused was accepted here, none that both accepted came out different, and 1,985 that libzstd accepted were refused here: 1,948 for one of four Huffman streams not read exactly, 25 for bytes after the frame (which Node, the way libzstd was called, ignores), 8 for a compressed block of no bytes, and 4 for a block too short to hold its literal.

Speed. On the development machine, the C sources of this library (2.9 MiB) compressed by libzstd at levels 1, 3 and 19 decode through proven_zstd_decode_all at about 650, 650 and 750 MiB/s, and through a decoder given all of it in one call at about 590, 570 and 730 MiB/s; libzstd, in the same process, at about 1,020, 940 and 1,030 MiB/s - so this decoder runs at 0.6 to 0.7 of libzstd's speed (v0.86.0; about half before it). Before v0.86.0, 2.2 MiB of the same sources as gzip went through section 3's decompressor at about 335 MiB/s.

Writing Zstandard#

proven_err_t proven_zstd_encoder_create(const proven_zstd_encoder_options_t *options, proven_zstd_encoder_t **out);
void proven_zstd_encoder_destroy(proven_zstd_encoder_t *z);
void proven_zstd_encoder_reset(proven_zstd_encoder_t *z);
proven_err_t proven_zstd_encode(proven_zstd_encoder_t *z, proven_mem_view_t in, proven_size_t *consumed,
                                proven_mem_mut_t out, proven_size_t *produced, proven_zstd_flush_t flush, bool *done);
proven_size_t proven_zstd_encode_bound(proven_size_t input_size);
proven_err_t proven_zstd_encode_all(const proven_zstd_encoder_options_t *options, proven_mem_view_t in, proven_mem_mut_t out, proven_size_t *written);

The encoder is used like section 3's compressor: options (alloc, level, window_log, checksum), a state, and a step with a flush - PROVEN_ZSTD_FLUSH_NONE while more is coming, _BLOCK to make everything given so far decodable while the frame goes on, _FINISH to end the frame. Its frames are read by any Zstandard decoder; they are not the bytes libzstd would have written for the same input.

Levels as libzstd's. Level 1 finds matches through one hash table, levels 2 and 3 through two (libzstd's "fast" and "double fast"); levels 4 to 9 keep every position in a hash chain and look at the first 4 to 32 of it, taking the best match found (levels 4 and 5) or first looking one byte on (6) or two (7 to 9) for a better one. Every block's literals get a Huffman code and its sequences FSE tables, each chosen for the block by what it would cost. Measured on the three files of section 4, on one core of the development machine, at the release flags:

Level 1 is between five and six times as fast as this library's gzip at level 1, and smaller; level 6 is no larger than gzip at level 6 and between 2.6 and 3.2 times as fast. Against libzstd, levels 1 to 3 and 5 to 8 run at 0.8 to 1.0 of the speed and level 9 at about 0.8, within a third of a point of the size. Level 6 looks at 12 candidates where libzstd's looks at 8, which keeps it at or below gzip 6 on all three files (libzstd 6 is slightly larger than gzip 6 on the C source). Level 4 is not libzstd's method at that level: smaller by about a point, at about half the speed.

Since v0.103.0, proven_zstd_encode_all of more than 256 KiB gives levels 6 to 9 libzstd's larger tables for such inputs: a hash of 2^19 to 2^21 entries and a chain of 2^18 to 2^20, each cut to the window (3 MiB at level 6, 6 MiB at 7 and 8, 8 MiB at 9 with the default window, 12 MiB with the largest). A stream - the servers' - keeps the 1 MiB above. Against libzstd at the same level and the same window, on a 3.9 MB executable, 2.7 MB of C sources, 3.7 MB of JSON and 395 KB of text:

The output is about 1 % smaller on megabyte inputs, 2 % with the largest window.

Levels 10 to 12 (since v0.101.0) are lazy2 again with libzstd's larger tables for them - a hash of 2^22, 2^22 and 2^23 entries and a chain of 2^21, 2^21 and 2^22, each cut to the window - and 48, 96 and 128 candidates: for a file compressed once and sent many times. Against libzstd's same levels, on four other inputs at the largest window (window_log 23; one run each, on a loaded machine, so the speeds are rough):

Level 12 is 2 to 5 % smaller than level 9, at a fifth to a half of its speed. libzstd finds its candidates faster (it keeps them in rows) and, below 256 KiB, switches to a binary tree at level 11 - the JSON row's point. With the default window (19) the tables are 2^20 each and the C sources 2 points larger than libzstd's, which uses 4 MiB at these levels.

Levels 13 to 19 (since v0.102.0). 13 to 15 parse the same way over binary trees: every position is kept in a tree of the positions before it with the same hash, ordered by the bytes that follow, so the longest matches are found by a walk down the tree instead of along a chain (trees of 2^21 to 2^22 positions, 32, 64 and 128 nodes compared). 16 to 19 parse optimally over the same trees: every match found at a position, and the three repeat offsets, priced at what they would cost to write - their offset, their length, their sequence's literal length, each literal byte, from what the frame has written so far - and the cheapest path through each stretch of up to 4,096 bytes taken; 18 and 19 also take three-byte matches. A whole buffer of 256 KiB or less is parsed optimally from level 13, as libzstd does. The same four inputs and window:

Level 19 is 7 to 13 % smaller than level 9 on these four inputs (a quarter on numbered lines). It differs from libzstd's in one known way: libzstd's level 19 makes a first pass over the first block to learn its statistics; this one starts from the block's own bytes and the format's predefined distributions.

Long-distance matching (long_distance, since v0.103.0), as libzstd's --long: a rolling hash of the last 64 bytes picks about one position in 128; those positions are kept in buckets for the whole window (8 bytes for each 128 bytes of window: 512 KiB at window_log 23), and a match of 64 bytes or more found through them is taken, the level's own matching filling what lies between. It is for large inputs that repeat from further back than a fast level's tables reach - archives, logs, several versions of one file. It acts at levels 1 to 5: from 6 the level's own matching finds about as much, and from 9 a long match forced into the parse costs more than it saves (3 % at level 19), so there it does nothing. With the largest window, the size with it / without it, and its speed:

On the first input, level 3 with it is within 1.5 % of libzstd's level 3 with --long at the same window. Without such repeats it costs 4 to 22 % of the speed: the rolling hash reads every byte.

The table was measured before v0.89.0. Since then, on an x86 processor with BMI2 (shifts by a register without the flags), the encoder runs a second build of its block coder compiled for it - the same C, the same output, chosen when the processor is first asked: on four other inputs of 0.4 to 3.9 MB, levels 1 to 3 went from 0.76-0.88 of libzstd's speed to 0.82-0.96.

Memory. proven_zstd_encode_all compresses the caller's buffer where it is, with tables and block buffers sized to it: a few kilobytes for a short input. A stream keeps the window in its own buffer, and at most holds:

The window (window_log, 10 to 23, zero is 19) is what a decoder must hold to read the frame, so it is the reader's memory too: 23 (8 MiB) is the most RFC 9659 asks an HTTP client to accept. A whole buffer no larger than the window states its own size as the window.

Example: written whole, in a stream with a flush, and the weights of a request#

#include <string.h>

/*
 * Zstandard, written: a whole buffer, a stream that hands over what it has at a flush, and
 * the choice a server makes between zstd and gzip from a request's Accept-Encoding.
 */

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();
    static const char line[] = "GET /index.html HTTP/1.1 - 200 - text/html; charset=utf-8\n";
    static proven_byte_t text[40000];
    for (proven_size_t i = 0; i < sizeof text; ++i) text[i] = (proven_byte_t)line[i % (sizeof line - 1)];
    static proven_byte_t frame[48000], back[40000];

    /* A whole buffer. encode_bound is always enough; the frame states the input's size, so a
     * decoder needs no more window than that. */
    proven_zstd_encoder_options_t o = { .alloc = heap, .level = 1 };
    proven_size_t n = 0, got = 0;
    EXAMPLE_REQUIRE(proven_zstd_encode_bound(sizeof text) <= sizeof frame, "the bound for 40,000 bytes fits the buffer");
    EXAMPLE_REQUIRE(proven_zstd_encode_all(&o, (proven_mem_view_t){ text, sizeof text }, (proven_mem_mut_t){ frame, sizeof frame }, &n) == PROVEN_OK && n < 200,
                    "40,000 bytes of repeated log lines compress to fewer than 200");
    EXAMPLE_REQUIRE(proven_zstd_decode_all(heap, (proven_mem_view_t){ frame, n }, (proven_mem_mut_t){ back, sizeof back }, &got) == PROVEN_OK &&
                    got == sizeof text && memcmp(back, text, got) == 0, "and decode to every byte");

    /* A stream: 1,000 bytes at a time at level 6 into a 64 KiB window, with the checksum. A block flush
     * after the first 5,000 makes them decodable at once - what a server does before it
     * waits for more to send; FINISH ends the frame. */
    proven_zstd_encoder_t *z = NULL;
    o = (proven_zstd_encoder_options_t){ .alloc = heap, .level = 6, .window_log = 16, .checksum = true };
    EXAMPLE_REQUIRE(proven_zstd_encoder_create(&o, &z) == PROVEN_OK, "an encoder at level 6 - about gzip 6's size - with a 64 KiB window");
    proven_size_t in_at = 0, out_at = 0;
    bool done = false;
    while (!done) {
        const proven_size_t give = sizeof text - in_at < 1000 ? sizeof text - in_at : 1000;
        const proven_zstd_flush_t flush = in_at + give == sizeof text ? PROVEN_ZSTD_FLUSH_FINISH
                                        : in_at + give == 5000 ? PROVEN_ZSTD_FLUSH_BLOCK : PROVEN_ZSTD_FLUSH_NONE;
        proven_size_t used = 0, made = 0;
        EXAMPLE_REQUIRE(proven_zstd_encode(z, (proven_mem_view_t){ text + in_at, give }, &used, (proven_mem_mut_t){ frame + out_at, sizeof frame - out_at }, &made, flush, &done) == PROVEN_OK,
                        "a step");
        in_at += used;
        out_at += made;
        if (flush == PROVEN_ZSTD_FLUSH_BLOCK) {
            /* Everything so far, decoded from what has come out so far: the frame is not over. */
            proven_zstd_decoder_t *d = NULL;
            proven_size_t dused = 0, dmade = 0;
            bool dend = true;
            EXAMPLE_REQUIRE(proven_zstd_decoder_create(heap, 0, &d) == PROVEN_OK &&
                            proven_zstd_decode(d, (proven_mem_view_t){ frame, out_at }, &dused, (proven_mem_mut_t){ back, sizeof back }, &dmade, &dend) == PROVEN_OK &&
                            dmade == 5000 && !dend, "after the flush, a decoder gives back all 5,000 bytes and waits for the rest");
            proven_zstd_decoder_destroy(d);
        }
    }
    EXAMPLE_REQUIRE(proven_zstd_decode_all(heap, (proven_mem_view_t){ frame, out_at }, (proven_mem_mut_t){ back, sizeof back }, &got) == PROVEN_OK &&
                    got == sizeof text && memcmp(back, text, got) == 0, "the finished frame decodes to the 40,000 bytes, checksum checked");
    proven_zstd_encoder_reset(z);                         /* the same encoder, a new frame */
    proven_size_t used = 0, made = 0;
    EXAMPLE_REQUIRE(proven_zstd_encode(z, (proven_mem_view_t){ text, 300 }, &used, (proven_mem_mut_t){ frame, sizeof frame }, &made, PROVEN_ZSTD_FLUSH_FINISH, &done) == PROVEN_OK &&
                    done && used == 300, "after a reset, a second frame");
    proven_zstd_encoder_destroy(z);

    /* Which coding a request wants most: weights in thousandths. curl and browsers send zstd
     * and gzip at one weight; a server that offers zstd takes it then (compress_zstd). */
    const proven_http_header_t asks[] = { { PROVEN_LIT("Accept-Encoding"), PROVEN_LIT("gzip, deflate, br, zstd") } };
    const proven_http_header_t prefers_gzip[] = { { PROVEN_LIT("Accept-Encoding"), PROVEN_LIT("gzip;q=1.0, zstd;q=0.5") } };
    EXAMPLE_REQUIRE(proven_http_accept_weight(asks, 1, PROVEN_HTTP_CODING_ZSTD) == 1000 && proven_http_accept_weight(asks, 1, PROVEN_HTTP_CODING_GZIP) == 1000,
                    "a browser's list: zstd and gzip both 1000");
    EXAMPLE_REQUIRE(proven_http_accept_weight(prefers_gzip, 1, PROVEN_HTTP_CODING_ZSTD) == 500 && proven_http_accept_weight(prefers_gzip, 1, PROVEN_HTTP_CODING_GZIP) == 1000,
                    "a client that prefers gzip: zstd 500, gzip 1000");
    return EXAMPLE_OK();
}

Reference: the encoder#

Cautions when writing#

A stream does not state its size, so a decoder must be ready for its whole window: choose window_log for the reader, not only for the ratio. The checksum is off unless asked for: without it a damaged frame can decode to wrong bytes. A block flush costs a block header and the tables for a short block - flush where a reader is waiting, not after every write. Compressing is no more secret than gzip: section 6's caution about secrets next to text the client chose holds for zstd as it does for gzip.

Dictionaries#

Since v0.104.0. Zstandard compresses a short message poorly on its own: a record of a hundred bytes has nothing earlier to match and pays for its tables. A dictionary is a past both sides agree on before any frame is sent - typical content, given out of band - and every frame starts from it: its matches reach into the dictionary, and a formatted dictionary's entropy tables and repeat offsets are in force for the first block, which may use them without writing them. On records of a hundred bytes like the dictionary's, frames come out at a third to two fifths of their size without one.

A raw dictionary is any bytes, at least 8 - a few typical messages, as below. A formatted one, as zstd --train makes from samples, begins with the magic number 0xEC30A437 and an ID, which each frame then names; this library uses dictionaries and does not train them. The encoder takes one in dictionary, the decoder through proven_zstd_decoder_use_dictionary, which resets it and serves every frame after: a frame that names another ID is refused, one that names none uses the one set. proven_zstd_dictionary_id says which ID a dictionary has (0 for a raw one).

The bytes stay yours on both sides, and must outlive their use. Each frame holds the content ahead of its output: the decoder up to the content's size more than without, the encoder the same in its input buffer and, for proven_zstd_encode_all, a copy of the input after the content. RFC 8878 says content sent with the zstd coding should not use a dictionary, and nothing in the HTTP drivers does: this is for a program's own messages and files.

Example: three messages as a dictionary, a fourth with it and without#

#include <string.h>

/*
 * Zstandard with a dictionary: short messages that look alike, each its own frame, both sides
 * starting from the same past. Here the dictionary is raw - a few typical messages, as is - which
 * needs no training; `zstd --train` makes formatted ones, used the same way.
 */

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();
    static const char dict[] =
        "{\"event\": \"login\", \"user\": \"alice\", \"ok\": true, \"region\": \"eu-west\"}\n"
        "{\"event\": \"logout\", \"user\": \"bob\", \"ok\": true, \"region\": \"us-east\"}\n"
        "{\"event\": \"purchase\", \"user\": \"carol\", \"ok\": false, \"region\": \"ap-south\"}\n";
    static const char msg[] = "{\"event\": \"login\", \"user\": \"dave\", \"ok\": false, \"region\": \"us-east\"}\n";
    const proven_mem_view_t dv = { (const proven_byte_t *)dict, sizeof dict - 1 };
    EXAMPLE_REQUIRE(proven_zstd_dictionary_id(dv) == 0, "a raw dictionary has no ID");

    /* One message with the dictionary, and without. */
    static proven_byte_t frame[256], plain[256], back[256];
    proven_size_t n = 0, p = 0;
    proven_zstd_encoder_options_t o = { .alloc = heap, .level = 3, .dictionary = dv };
    EXAMPLE_REQUIRE(proven_zstd_encode_all(&o, (proven_mem_view_t){ (const proven_byte_t *)msg, sizeof msg - 1 }, (proven_mem_mut_t){ frame, sizeof frame }, &n) == PROVEN_OK,
                    "a message compressed with the dictionary");
    o.dictionary = (proven_mem_view_t){ NULL, 0 };
    EXAMPLE_REQUIRE(proven_zstd_encode_all(&o, (proven_mem_view_t){ (const proven_byte_t *)msg, sizeof msg - 1 }, (proven_mem_mut_t){ plain, sizeof plain }, &p) == PROVEN_OK,
                    "and without it");
    EXAMPLE_REQUIRE(n * 2 < p, "with it, the 73 bytes take less than half of what they take without");

    /* The other side: the same dictionary, set on a decoder once, for every frame after. */
    proven_zstd_decoder_t *z = NULL;
    EXAMPLE_REQUIRE(proven_zstd_decoder_create(heap, 0, &z) == PROVEN_OK && proven_zstd_decoder_use_dictionary(z, dv) == PROVEN_OK, "a decoder with the dictionary");
    for (int round = 0; round < 2; ++round) {
        proven_size_t used = 0, made = 0;
        bool done = false;
        EXAMPLE_REQUIRE(proven_zstd_decode(z, (proven_mem_view_t){ frame, n }, &used, (proven_mem_mut_t){ back, sizeof back }, &made, &done) == PROVEN_OK && done &&
                        made == sizeof msg - 1 && memcmp(back, msg, made) == 0, "the message back - and again, from the same decoder");
    }
    /* Without the dictionary there is no way back: the frame needs the same past. */
    EXAMPLE_REQUIRE(proven_zstd_decoder_use_dictionary(z, (proven_mem_view_t){ NULL, 0 }) == PROVEN_OK, "the dictionary taken away");
    proven_size_t used = 0, made = 0;
    bool done = false;
    const proven_err_t e = proven_zstd_decode(z, (proven_mem_view_t){ frame, n }, &used, (proven_mem_mut_t){ back, sizeof back }, &made, &done);
    EXAMPLE_REQUIRE(e != PROVEN_OK || made != sizeof msg - 1 || memcmp(back, msg, made) != 0, "a raw dictionary's frame names none, so it decodes to something else, or fails");
    proven_zstd_decoder_destroy(z);
    return EXAMPLE_OK();
}

8. Brotli#

#include "proven/brotli.h"

proven_err_t proven_brotli_decoder_create(proven_allocator_t alloc, proven_u64 window_max, proven_brotli_decoder_t **out);
void proven_brotli_decoder_destroy(proven_brotli_decoder_t *b);
void proven_brotli_decoder_reset(proven_brotli_decoder_t *b);
proven_err_t proven_brotli_decode(proven_brotli_decoder_t *b, proven_mem_view_t in, proven_size_t *consumed,
                                  proven_mem_mut_t out, proven_size_t *produced, bool *done);
proven_err_t proven_brotli_decode_all(proven_allocator_t alloc, proven_mem_view_t in, proven_mem_mut_t out, proven_size_t *written);

Brotli (RFC 7932) is HTTP's Content-Encoding: br. Servers mostly use it for files they compress once in advance at its highest quality, where it comes out smaller than gzip and Zstandard; compressing at that quality is slow, and decoding is fast whatever the quality. This library reads it, since v0.60.0, and does not write it: a server here sends gzip or Zstandard.

The decoder works as section 7's does - a state, and a step that takes what input there is and fills what output space there is, stopping anywhere: between two bits of a code if that is where your input ends, in the middle of a copy if that is where your space ends. Two things are the same as there:

• A step may allocate. The history that later bytes refer to grows with the stream's output, never past the window the stream states; and each meta-block (Brotli's unit, up to 16 MiB of output) brings its own prefix codes, built into a table that grows with how many there are. Both are kept for the next stream. So proven_brotli_decode can return PROVEN_ERR_NOMEM.
• Output can wait in the decoder, in that history, while the space you give is too small.

The window is the memory, and the limit is yours. A stream's first bits say how far back it may refer: 2^WBITS - 16 bytes, for WBITS from 10 to 24, so 16 MiB at most. window_max is the most you agree to: 0 means 16 MiB, which takes every stream RFC 7932 allows. A stream that needs more is PROVEN_ERR_OUT_OF_BOUNDS before anything is allocated for it. libbrotli's "large window" variant, which is not RFC 7932, is refused as malformed.

One stream, and nothing after it. Brotli streams do not follow each other the way gzip members and Zstandard frames do. *done becomes true where the stream ends, that call stops there - what it consumed is the stream - and later calls consume nothing more; reset to read another. proven_brotli_decode_all refuses bytes after the end, as do the HTTP clients.

The static dictionary. Brotli streams may copy words from a dictionary that every decoder carries: 122,784 bytes of words in many languages, and 121 ways of changing each (a space before, a capital first letter, a suffix such as ing ). It is most of what this decoder adds to a program: with it, the library is 162,351 bytes larger (998,985 bytes of code and data against 836,634, at -O2 on x86-64). A build with -DPROVEN_NO_BROTLI leaves the decoder and the dictionary out; proven.h then does not include brotli.h, and an HTTP client asked to decode Brotli is PROVEN_ERR_UNSUPPORTED.

Example: a buffer, a stream with something after it, and a window too large#

#include <string.h>

/*
 * Brotli: a whole buffer, then the same stream read piece by piece with other bytes after it,
 * and the window limit that keeps a stranger's stream from deciding how much memory this
 * program spends.
 */

/* 4,000 bytes of log lines, as libbrotli wrote them at quality 11 with a 64 KiB window: 58 bytes. */
static const proven_byte_t STREAM[] = {
    0xe2, 0xf3, 0x01, 0xb1, 0xe3, 0x30, 0x76, 0xb3, 0x54, 0x22, 0x7f, 0x6e,
    0x31, 0x35, 0x23, 0x54, 0x7a, 0x83, 0xbc, 0xb8, 0x1c, 0x8d, 0x96, 0x8c,
    0x29, 0xa2, 0x82, 0x0d, 0x38, 0x60, 0x0f, 0x30, 0xc2, 0x45, 0x17, 0x5a,
    0x8c, 0xce, 0x18, 0x20, 0xa3, 0x8c, 0xc1, 0x41, 0x9a, 0xb7, 0x0a, 0x2d,
    0x23, 0xe3, 0x31, 0x41, 0x6b, 0xd0, 0x07, 0x39, 0x00, 0x40,
};

int main(void) {
    proven_allocator_t heap = proven_heap_allocator();
    static const char line[] = "GET /index.html HTTP/1.1 - 200 - text/html; charset=utf-8\n";
    static proven_byte_t text[4000];
    for (proven_size_t i = 0; i < sizeof text; ++i) text[i] = (proven_byte_t)line[i % (sizeof line - 1)];

    /* A whole buffer: as with gzip, the output buffer is the limit. */
    static proven_byte_t out[8000];
    proven_size_t n = 0;
    EXAMPLE_REQUIRE(proven_brotli_decode_all(heap, (proven_mem_view_t){ STREAM, sizeof STREAM }, (proven_mem_mut_t){ out, sizeof out }, &n) == PROVEN_OK &&
                    n == sizeof text && memcmp(out, text, n) == 0, "58 bytes of Brotli decode to the 4,000 bytes libbrotli was given");
    EXAMPLE_REQUIRE(proven_brotli_decode_all(heap, (proven_mem_view_t){ STREAM, sizeof STREAM }, (proven_mem_mut_t){ out, 3999 }, &n) == PROVEN_ERR_OUT_OF_BOUNDS,
                    "and do not fit in 3,999: PROVEN_ERR_OUT_OF_BOUNDS");

    /* A stream with five other bytes after it, given 7 bytes at a time with 500 bytes of room.
     * `done` comes where the stream ends, and the bytes after it are not consumed: a Brotli
     * stream has no frames to follow it, so what they are is the caller's business. */
    static proven_byte_t more[sizeof STREAM + 5];
    memcpy(more, STREAM, sizeof STREAM);
    memcpy(more + sizeof STREAM, "after", 5);
    proven_brotli_decoder_t *b = NULL;
    EXAMPLE_REQUIRE(proven_brotli_decoder_create(heap, 0, &b) == PROVEN_OK, "a decoder with the default window limit, 16 MiB");
    proven_size_t in_at = 0, out_at = 0;
    bool done = false;
    while (!done) {
        proven_size_t give = sizeof more - in_at < 7 ? sizeof more - in_at : 7, room = sizeof out - out_at < 500 ? sizeof out - out_at : 500;
        proven_size_t used = 0, made = 0;
        EXAMPLE_REQUIRE(proven_brotli_decode(b, (proven_mem_view_t){ more + in_at, give }, &used, (proven_mem_mut_t){ out + out_at, room }, &made, &done) == PROVEN_OK, "a step");
        in_at += used;
        out_at += made;
        if (used == 0 && made == 0 && !done) break;     /* nothing more to give, or nowhere to put it */
    }
    EXAMPLE_REQUIRE(done && in_at == sizeof STREAM && out_at == sizeof text && memcmp(out, text, out_at) == 0,
                    "done after the 58 bytes of the stream, with the five after it left alone");

    /* The window limit. The first bits of a stream say how far back it may refer, and a
     * decoder must keep that much: this one, made with libbrotli's largest window, asks for
     * 16 MiB. A decoder limited to 64 KiB refuses it before allocating anything for it; reset
     * makes the decoder usable again. */
    static const proven_byte_t wide[] = { 0x0f, 0x01, 0x80, 0x61, 0x62, 0x63, 0x03 };
    proven_brotli_decoder_t *small = NULL;
    proven_size_t used = 0, made = 0;
    EXAMPLE_REQUIRE(proven_brotli_decoder_create(heap, 64 * 1024, &small) == PROVEN_OK, "a decoder limited to 64 KiB");
    EXAMPLE_REQUIRE(proven_brotli_decode(small, (proven_mem_view_t){ wide, sizeof wide }, &used, (proven_mem_mut_t){ out, sizeof out }, &made, &done) == PROVEN_ERR_OUT_OF_BOUNDS,
                    "a stream with a 16 MiB window: PROVEN_ERR_OUT_OF_BOUNDS");
    proven_brotli_decoder_reset(small);
    EXAMPLE_REQUIRE(proven_brotli_decode(small, (proven_mem_view_t){ STREAM, sizeof STREAM }, &used, (proven_mem_mut_t){ out, sizeof out }, &made, &done) == PROVEN_OK &&
                    done && made == sizeof text, "after a reset, a stream within the limit decodes");
    proven_brotli_decoder_reset(b);
    EXAMPLE_REQUIRE(proven_brotli_decode(b, (proven_mem_view_t){ wide, sizeof wide }, &used, (proven_mem_mut_t){ out, sizeof out }, &made, &done) == PROVEN_OK &&
                    done && made == 3 && memcmp(out, "abc", 3) == 0, "while the default limit takes it - with a few KiB of history, not 16 MiB");

    proven_brotli_decoder_destroy(small);
    proven_brotli_decoder_destroy(b);
    return EXAMPLE_OK();
}

Reference#

Cautions, and what goes wrong#

• The window decides the memory, as in section 7: whoever wrote the stream chooses it, up to your limit. A thousand responses at once, each with a 16 MiB window and long enough to fill it, are 16 GiB. Lower window_max where you know the streams (files you made with a known window), and count decoders the way you count connections.
• There is no checksum. Damage that still forms a valid stream decodes to other bytes; the decoder can only refuse what does not parse. Where it matters, check what you decoded.
• Not recognisable by its first bytes. Brotli has no magic number: a decoder given gzip, or text, fails somewhere inside rather than at once, and very short inputs of other kinds can happen to be valid streams. Over HTTP, Content-Encoding says what a body is; for files, keep the name (.br) or a header of your own.

Nothing that libbrotli refuses is accepted. Outside the registered tests, 1,437,490 truncated and changed copies of 176 streams were given to both this decoder and libbrotli 1.1.0's one-call decoder: none that libbrotli refused was accepted here, none that both accepted came out different, and 11,242 that it accepted were refused here - each a stream that ends before the input does, with the same output, whose remaining bytes libbrotli's one-call decoder ignores and proven_brotli_decode_all (like Python's binding of libbrotli) does not.

Speed. On the development machine, the C sources of this library (2.9 MiB) compressed by libbrotli at qualities 1, 5 and 11 decode at about 195, 265 and 290 MiB/s - 0.65 to 0.73 of libbrotli's own decoder in the same process (about 270, 410 and 435 MiB/s; v0.87.0, from 0.57 to 0.65 before); an uncompressed meta-block or a long run is copied at libbrotli's speed.

9. What is accepted, what is not here, and how this was tested#

What the decompressor accepts is what zlib accepts. Where RFC 1951 leaves a corner open, each case was tried on zlib first and its verdict followed, because a real producer may emit what zlib tolerates. So: a block that uses a single code is accepted, as is a length written with the longest form of the code before the last; codes that describe more symbols than can exist, lengths and distances outside the format, a distance reaching back before the first byte, and a stream whose code tables do not add up are all refused. A gzip header may carry an extra field, a file name, a comment and its own checksum, all of which are read past (the checksum is checked); the name and the time are not reported.

What the compressor writes is valid DEFLATE that any decompressor reads. It is not, byte for byte, what zlib would have written for the same input, and it does not need to be.

Not here:

• Preset dictionaries (zlib's FDICT), in either direction.
• ZIP archives, tar files: those are containers. This is the codec inside them.
• Deflate64, and every other compression format: LZ4, bzip2, xz. Zstandard's slower levels (10 to 22 in libzstd: binary trees and optimal parsing), its dictionaries and its long-distance mode. Brotli compression; Brotli's large-window variant and shared dictionaries.
• The gzip header's fields - name, time, comment - cannot be set or read.
• Several gzip members read as one stream automatically: reset after each (section 3). (The HTTP clients of section 6 do this for a response body.)
• Over HTTP: compressed request bodies, in either direction; sending br; a call that pushes out what a streamed response has written so far; serving a precompressed file (a handler can do that itself: proven_http_accepts_coding, then its own Content-Encoding).

How this was tested. The registered test decompresses 93 streams that zlib 1.3.1 made - every level and strategy, small windows, flushes in the middle, all three formats - a byte at a time and in one call, and gets the data zlib was given; accepts ten hand-built streams that are unusual and that zlib accepts; refuses thirty hand-built streams that zlib refuses, one for each way a stream can be wrong; gives "more input, please" for every proper prefix of the short streams and an answer of some kind - never a write outside its buffer - for every single changed bit of them; and compresses eleven kinds of data at every level and three window sizes and gets it back. Outside the registered tests: zlib decompressed everything this compressor produced for a larger corpus, at every level, window and format, with flushes and in small pieces (2,856 streams); this decompressor was compared with zlib on 5,838 more; and six million randomly damaged streams were decompressed under tools that report any read or write outside a buffer, with none reported and no stream that made the decoder do work without progress.

Section 6 was tested against bodies zlib made - gzip, zlib, raw DEFLATE, two members, every optional header field, and each way of being cut short or damaged - through both clients, whole and a byte a chunk, each checked against zlib's own verdict when the test's table was generated; and with both servers compressing at seven sizes, in one piece and streamed, plain and over TLS. Outside the registered tests, curl and Python read what both servers send, and both clients read what a Python server sends.

Section 7 was tested against libzstd 1.5.7, by way of Node: the registered test decodes 91 streams libzstd made from seven kinds of data - levels 1, 3, 9 and 19, with and without the checksum and the content size, matches reaching across blocks, a frame longer than its window - in one call, a byte at a time and in odd steps, and gets the data libzstd was given; accepts thirteen hand-built frames that are unusual and that libzstd accepts (among them every kind of repeat offset), and refuses twenty, with their reasons (damage, a dictionary, a window above 8 MiB, and the empty compressed block above); refuses every proper prefix of the short streams; gives the same verdict, whole and in steps, for every single changed bit of them; and shows the window limit refusing before any allocation, the memory held, and every failed allocation answered with PROVEN_ERR_NOMEM. Outside the registered tests: 130 more streams libzstd made - up to 2.2 MiB, several frames, flushed streams - decoded byte for byte in steps from 1 byte to 70,000; and about 70,000 truncations and changed bits of seven of them, under tools that report any read or write outside a buffer, with none reported. Over HTTP, the blocking, event-driven and HTTP/2 clients decoded what Node's servers sent in zstd (levels 1, 3 and 19, whole, flushed and in several frames, up to 3 MB), refused it cut short or followed by junk, and a client that did not ask was sent gzip; curl read a handler's own Zstandard from this library's server.

Section 8 was tested against libbrotli, by way of Python's binding (1.1.0): the registered test decodes 110 streams libbrotli made from ten kinds of data - qualities 0, 1, 5, 9 and 11, windows from 1 KiB to 16 MiB, text and generic modes - in one call, a byte at a time and in odd steps, and gets the data libbrotli was given; decodes 66 hand-built streams that libbrotli decodes, with the same result - metadata, uncompressed meta-blocks, every window size, dictionary words under all 121 transforms (capitals of two- and three-byte letters among them), every context mode, context maps with runs and move-to-front, every short distance code, block switches of each kind, every way of writing a prefix code - and refuses 25 that libbrotli refuses, each wrong in a different way; refuses every proper prefix of the short streams; gives the same verdict, whole and in steps, for every single changed bit of them (72,376); and shows the window limit refusing before any allocation, the memory held, and every failed allocation answered with PROVEN_ERR_NOMEM. The dictionary and its transforms were taken from the text of RFC 7932 and checked against the CRC-32s it gives and against libbrotli's own copy. Outside the registered tests: 358 more streams from Python's libbrotli and 144 from Node's (a copy of its own, 1.2.0) - this repository's files, the Korean manual, 2.2 MB of sources - decoded byte for byte in steps from 1 byte to 70,000, under the tools that report any read or write outside a buffer; the 1,437,490 damaged copies above; and the largest code table each alphabet can make, worked out and then built. Over HTTP, the blocking, event-driven and HTTP/2 clients decoded what Node's servers sent in br - qualities 1, 5 and 11, windows of 1 KiB to 16 MiB, whole and flushed, up to 3 MB - refused it cut short, followed by junk or twice, and a client that did not ask was sent gzip.

The encoder of section 7 was tested against its decoder and against libzstd. The registered test compresses eleven kinds of data (nothing, one byte, a run, numbered lines, noise with copies from far back, random bytes, more than 128 byte values, and more) at all nineteen levels and three windows, whole and - at a level of each kind - streamed with a block flush after each piece and output a byte at a time, and decodes every frame with this library's decoder, which checks each offset against the window the frame states; it checks that a stream's blocks are byte for byte those of the same input compressed whole at every level, the frame header, the bound over 8,000 inputs, flushes, the end and a reset, literals of one byte value in a compressed block, the memory held, and failed allocations, and pins the size and CRC of thirteen frames that libzstd decoded - five of them streamed after a reset with the buffer sliding. Outside the registered tests, libzstd decoded every frame the encoder made from a corpus - this repository's files, the Korean manual, a binary, 4 MB of sources, inputs of every size to 4,096 bytes and at every block and header boundary, literals of one byte, two and four values, periods that fill a block's sequences - at every level and at windows from 1 KiB to 8 MiB, whole and streamed in pieces from one byte, under the tools that report any read or write outside a buffer: 4,105 frames, every one byte for byte. Over HTTP, Node's libzstd and curl decoded what both servers sent in zstd, whole and streamed, at levels 1, 2, 3, 6 and 9 and windows of 1 KiB to 8 MiB, and the weights chose gzip where a client preferred it.

Not done: no coverage-guided fuzzing; no comparison with a second compressor's output besides zlib's; no external review. For Zstandard: no frames from other encoders than libzstd; no browser; no decoder but libzstd and this library's for the encoder's frames. For Brotli: no streams from encoders other than libbrotli's two copies; no browser.