brotli

    A streaming Brotli (RFC 7932) decoder and encoder in pure MoonBit: arbitrary input chunks, bounded output slices, memory bounded by the window.

    brotli
    compression
    decompression
    encoder
    rfc7932
    streaming
    Download zip
    Author
    Version
    0.5.0
    License
    Apache-2.0
    Last updated
    2 days ago
    Downloads
    5K

    #gaato/brotli

    A streaming Brotli (RFC 7932) decoder and encoder in pure MoonBit, for Native, JS, Wasm and Wasm GC. Both take input in chunks of any size, write output into slices of any size, and keep their memory within a window you set, so they fit an HTTP client's or server's br content coding as well as a whole file.

    #Install

    moon add gaato/brotli

    #Usage

    One shot:

    ///|
    test "decompress a whole stream" {
    let compressed = b"\x0b\x02\x80hello\x03" // brotli.compress(b"hello")
    let text = @brotli.decompress(compressed, max_output=16 * 1024 * 1024)
    assert_eq(text, b"hello")
    }

    ///|
    test "compress and decompress" {
    let text = b"hello, hello, hello, brotli"
    let compressed = @brotli.compress(text)
    assert_eq(@brotli.decompress(compressed), text)
    }

    Streaming: feed input as it arrives, take output in slices of the size you choose.

    ///|
    fn decode_all(chunks : Array[Bytes], sink : (BytesView) -> Unit) -> Unit raise {
    let decoder = @brotli.Decoder()
    let out = FixedArray::make(64 * 1024, b'\x00')
    for i, chunk in chunks {
    let mut input = chunk[:]
    for ;; {
    let status = decoder.step_into(input, out, end=i == chunks.length() - 1)
    input = input[decoder.last_consumed():]
    sink(Bytes::from_array(out[:decoder.last_produced()]))
    match status {
    Done => return
    NeedMoreInput => break
    NeedMoreOutput => ()
    }
    }
    }
    }

    ///|
    test "decode a stream chunk by chunk" {
    let decoded = Buffer()
    decode_all([b"\x0b\x02", b"\x80hel", b"lo\x03"], bytes => {
    decoded.write_bytes(bytes.to_owned())
    })
    assert_eq(decoded.to_bytes(), b"hello")
    }

    Encoding works the same way. Flush makes the output so far decode to the input so far, say to send one part of an HTTP response; Finish ends the stream. A flush ends the meta-block in progress and pads to a byte with an empty metadata block, as the reference encoder's does; a flush with nothing new since the last writes nothing, and one before any input writes the stream header and that padding, 2 bytes.

    ///|
    fn encode_parts(parts : Array[Bytes], sink : (BytesView) -> Unit) -> Unit {
    let encoder = @brotli.Encoder()
    let out = FixedArray::make(64 * 1024, b'\x00')
    for i, part in parts {
    let action : @brotli.EncodeAction = if i == parts.length() - 1 {
    Finish
    } else {
    Flush
    }
    let mut input = part[:]
    for ;; {
    let status = encoder.step_into(input, out, action~)
    input = input[encoder.last_consumed():]
    sink(Bytes::from_array(out[:encoder.last_produced()]))
    if status is (Done | NeedMoreInput) {
    break
    }
    }
    }
    }

    ///|
    test "encode a stream part by part" {
    let encoded = Buffer()
    encode_parts([b"<html>", b"<body>hello</body>", b"</html>"], bytes => {
    encoded.write_bytes(bytes.to_owned())
    })
    let decoded = @brotli.decompress(encoded.to_bytes())
    assert_eq(decoded, b"<html><body>hello</body></html>")
    }

    Decoder and Encoder implement Decode and Encode from gaato/codec_bytes, the contract the codecs of codecs.mbt share, so code written once against it drives them. Errors are gaato/codec's CodecError(kind, message), the same for every codec there; gaato/codec_bytes re-exports it, so that one import names it.

    Brotli has no framing, so an input holds one stream. A decoder made with until=EndOfMember stops right after the stream and leaves what follows unread:

    ///|
    test "stop at the end of the stream" {
    let input = b"\x0b\x02\x80hello\x03" + b"what follows"
    let decoder = @brotli.Decoder(until=EndOfMember)
    let out = FixedArray::make(64, b'\x00')
    let status = decoder.step_into(input, out, end=false)
    assert_eq(status, Done)
    assert_eq(Bytes::from_array(out[:decoder.last_produced()]), b"hello")
    assert_eq(input[decoder.last_consumed():], b"what follows")
    }

    #What it decodes

    Every RFC 7932 stream, including the static dictionary and its 121 transforms. Input comes in chunks of any size, down to one byte, and output goes into slices of any size, under the rules of gaato/codec_bytes. The rules the decoder applies to what it reads and its verdict on a prefix code's lengths are proved against RFC 7932; its decoding tables and the encoder's codes, made as libdeflate makes them, are tested, not proved; PROOFS.md lists what is proved and what is trusted.

    An LZ77 dictionary (RFC 9841 section 3.2), given to Decoder(dictionary=d) or decompress(dictionary=d) as a Dictionary of raw bytes, lets a stream copy from it, as brotli -D writes them and RFC 9842's dcb coding uses one: distances just past the window's reach address the dictionary from its end, and the static dictionary's words come after them. A copy that would run past the dictionary's end raises Corrupt, as google/brotli's decoder refuses it (RFC 9841 has it go on into the window, which a full window no longer holds).

    Not included: the rest of Shared Brotli (RFC 9841): serialized shared dictionaries, with their own words and transforms, its large window and its framing format. A large-window stream raises Corrupt.

    #Encoding

    The encoder uses greedy LZ77 (lazy by one byte) and one prefix code per meta-block: about google/brotli's quality 4, and close to gzip -6. Higher-quality encoding (context modeling, block splitting, static dictionary references) is not included. The encoder never raises.

    Encoder(dictionary=d) and compress(dictionary=d) let matches copy from an LZ77 dictionary as brotli -D writes them, for RFC 9842's dcb coding: at a distance past the window's reach, however far into the stream. A record of 314 bytes that shares words with a 50,000-byte dictionary compresses to 100 bytes with it and 201 without (brotli -q 5 -D: 95). The dictionary builds the index encoders search it with once, the first time, and every encoder given it shares that (Dictionary::memory_usage).

    #Memory

    The decoder's memory is the window (at most 16 MiB, and no more than the output so far) plus tables of at most 1.3 MiB; memory_usage() reports it, and decoder_memory_bound(max_window_bits~) gives its most before you make a decoder. Decoder(max_window_bits=n) refuses streams that need a window over 2^n - 16 bytes with LimitExceeded, saying how much the stream needs.

    The encoder's memory is its window (Encoder(window_bits=n), 22 by default: 4 MiB, growing with the input to at most twice what it has taken, and up to a quarter more before it slides) plus a 64 KiB meta-block, its output and 855 KiB of fixed tables (the hash table and the meta-block's commands); memory_usage() reports all of it, within encoder_memory_bound(window_bits~). compress_bound(n) is the most compress writes for n bytes.

    #Errors

    Every malformed stream raises CodecError(kind, message) with Truncated, Corrupt or TrailingData (bytes after the stream); decompress(max_output=n) raises LimitExceeded past n bytes. The decoder does not abort.

    A step that raises first hands out the output that comes before the error (answering NeedMoreOutput while it does not fit), and last_consumed() and last_produced() count what that step took and wrote: a corrupt stream gives the same output, then the same error, however it is split. On TrailingData, last_consumed() stops at the end of the stream.

    #When to use it

    gaato/brotli fits Brotli that arrives in pieces or comes from anyone. Decoder takes input in pieces down to one byte, writes into your slices and holds its window and at most 1.3 MiB of tables (a process decoding 256 MiB of output in 64 KiB pieces peaks at 20.1 MiB, most of it the runtime). It agreed with brotli -d on all 81 valid and 359 invalid streams of the comparison, and its decoding rules are proved against RFC 7932. It runs on Native, JS, Wasm and Wasm GC; its encoder has one quality, about google/brotli's 4.

    On Wasm, a decoder that takes the whole stream at once can be faster: hustcer/fbr's takes about 0.77 times as long as gaato/brotli on the benchmarks' text there, and 1.3 (Native), 1.6 (Wasm GC) and 1.6 (JS) times as long on the other targets. Its encoder at quality 11 writes 17 % less on that text and takes 142 to 386 times as long as ours.

    #License

    Apache-2.0. The static dictionary in src/static_data.mbt comes from google/brotli under the MIT license; see LICENSE-dictionary.

    EncodeAction

    Status and EncodeAction are gaato/codec_bytes's: a step answers Done, NeedMoreInput or NeedMoreOutput, and an encoder's step is told to Continue, Flush or Finish. Errors are gaato/codec's CodecError(kind, message).

    Status

    using @gaato/codec_bytes { type Status }

    Status and EncodeAction are gaato/codec_bytes's: a step answers Done, NeedMoreInput or NeedMoreOutput, and an encoder's step is told to Continue, Flush or Finish. Errors are gaato/codec's CodecError(kind, message).

    Decoder

    pub struct Decoder {
    // private fields
    }

    A streaming Brotli decoder (RFC 7932). Feed it input in chunks of any size with step and collect output in slices of any size; it keeps the sliding window (at most 16 MiB, and no more than the output so far) plus fixed-size tables, never the whole input or output.
    impl Decode for Decoder

    Decoder::Decoder

    fn Decoder::Decoder(max_window_bits? : Int, until? :
    Until
    , dictionary? : Dictionary) -> Decoder

    A decoder at the start of a stream. It refuses a stream whose window exceeds what max_window_bits allows: LimitExceeded with the Memory resource, where needed is the stream's window and limit the largest one allowed, both (1 << WBITS) - 16 bytes (RFC 7932 section 9.1). The default 24 accepts every RFC 7932 stream. Values are clamped to 10..24.

    Brotli has no framing: an input holds one stream. With until at its default EndOfInput, bytes after the stream raise TrailingData; with EndOfMember, step answers Done right after the stream's last meta-block and consumes nothing past it, so input[last_consumed():] is what follows the stream.

    With dictionary, the stream may copy from it as RFC 9841 section 3.2 has it, as RFC 9842's dcb coding does: distances just past the window's reach (the output so far, or the window once it is full) address the dictionary from its end, and the static dictionary's words come after them. A copy that would run past the dictionary's end raises Corrupt, as the reference decoder (google/brotli) refuses it: RFC 9841 has it go on into the window, which a full window no longer holds. The decoder keeps the dictionary by reference, so the bytes it is a view of stay alive as long as the decoder, and memory_usage does not count them.

    Decoder::is_finished

    fn Decoder::is_finished(self : Decoder) -> Bool

    Whether the stream has ended and all its output has been handed out.

    Decoder::last_consumed

    fn Decoder::last_consumed(self : Decoder) -> Int

    Input bytes the latest step accepted: all of them on NeedMoreInput. A step that raised accepted the bytes up to the error; for TrailingData, exactly up to the end of the stream, or none if the stream ended before this step's input.

    Decoder::last_produced

    fn Decoder::last_produced(self : Decoder) -> Int

    Output bytes the latest step wrote, a step that raised included: the output before the error.

    Decoder::memory_usage

    fn Decoder::memory_usage(self : Decoder) -> Int

    Bytes the decoder holds: the window and the prefix code tables of the largest meta-block so far, which grow with the stream, and what is allocated with the decoder (the context maps, the trees' offsets, the code reader's and the table builder's scratch space), 27,793 bytes. At most 1 << max_window_bits plus 1,343,596 bytes of tables plus those (see RESOURCE_BOUNDS.md). reset releases the window and keeps the tables. The static dictionary, shared by every decoder, and an LZ77 dictionary, the caller's bytes kept by reference, are not counted.

    Decoder::reset

    fn Decoder::reset(self : Decoder) -> Unit

    Starts a new stream, keeping the tables' memory. The window is released.

    Decoder::step

    fn Decoder::step(self : Decoder, input : BytesView, output : MutArrayView[Byte], end~ : Bool) ->
    Status
    raise
    CodecError

    Decodes from input into output; see last_consumed and last_produced for how much of each it used. end says whether input holds the last bytes there are: then a stream cut short raises Truncated instead of asking for more. With EndOfInput, Done comes once the stream has ended, end is true and every byte is consumed; bytes after the end of the stream raise TrailingData. With EndOfMember, Done comes once the stream has ended, and the bytes after it are left unconsumed.

    An error comes after all the output before it: when output fills first, the step answers NeedMoreOutput and a later one hands out the rest and raises. After an error the decoder raises it again, consuming and writing nothing, until reset.

    Decoder::step_into

    fn Decoder::step_into(self : Decoder, input : BytesView, output : FixedArray[Byte], end~ : Bool) ->
    Status
    raise
    CodecError

    step into a whole FixedArray, with bulk copies.

    Dictionary

    pub struct Dictionary {
    // private fields
    }

    A dictionary of raw bytes for Decoder and Encoder, held by reference (the bytes it is a view of stay alive as long as it does).

    Dictionary::Dictionary

    fn Dictionary::Dictionary(content : BytesView) -> Dictionary

    A dictionary of content, as RFC 9841 section 3.2 calls an LZ77 dictionary and brotli -D takes one.

    Dictionary::content

    fn Dictionary::content(self : Dictionary) -> BytesView

    The dictionary's bytes.

    Dictionary::length

    fn Dictionary::length(self : Dictionary) -> Int

    The dictionary's length in bytes.

    Dictionary::memory_usage

    fn Dictionary::memory_usage(self : Dictionary) -> Int

    Bytes the dictionary holds of its own: once an encoder has used it, the index encoders search it with, shared by every encoder given it: a copy of the dictionary's last 64 MiB at most (the part a distance can reach), four bytes per byte of that, and a table of at most 512 KiB. Its content is the caller's and not counted.

    Encoder

    pub struct Encoder {
    // private fields
    }

    A streaming Brotli encoder (RFC 7932): greedy LZ77 with one prefix code per category, about the ratio of gzip. Feed it input in chunks of any size with step and collect output in slices of any size. It keeps the window of past input (1 << window_bits bytes, and no more than the input so far) plus at most a meta-block (64 KiB) of input and its output, and fixed-size tables.
    impl Encode for Encoder

    Encoder::Encoder

    fn Encoder::Encoder(window_bits? : Int, dictionary? : Dictionary) -> Encoder

    An encoder at the start of a stream, with a window of 1 << window_bits bytes (clamped to 10..24). The default 22 is the reference encoder's; a decoder needs up to that much memory.

    With dictionary, a match may copy from it as RFC 9841 section 3.2 has it, as brotli -D writes and RFC 9842's dcb coding reads: at a distance past the window's reach, however far into the stream. A decoder needs the same dictionary. The dictionary keeps the index the encoder searches it with, built the first time and shared by every encoder given it (Dictionary::memory_usage).

    Encoder::is_finished

    fn Encoder::is_finished(self : Encoder) -> Bool

    Whether the stream has ended and all its output has been handed out.

    Encoder::last_consumed

    fn Encoder::last_consumed(self : Encoder) -> Int

    Input bytes the latest step took.

    Encoder::last_produced

    fn Encoder::last_produced(self : Encoder) -> Int

    Output bytes the latest step wrote.

    Encoder::memory_usage

    fn Encoder::memory_usage(self : Encoder) -> Int

    Bytes the encoder holds: the input buffer (the window and at most a meta-block not encoded yet) and the output waiting for the caller, which grow with the stream, and what is allocated with the encoder: the hash table, 16 << min(window_bits, 15) bytes (512 KiB from 15 up), and a meta-block's commands with their histograms, codes and scratch space and the distance ring, 351,628 bytes. At most (1 << window_bits) - 16, plus max(1 << (window_bits - 2), 64 KiB), plus 64 KiB, plus 131,200 bytes, plus those (see RESOURCE_BOUNDS.md). reset releases the input buffer. A dictionary's index is shared by the encoders given it and counted by Dictionary::memory_usage, not here.

    Encoder::reset

    fn Encoder::reset(self : Encoder) -> Unit

    Starts a new stream, keeping the tables' memory. The input buffer is released.

    Encoder::step

    fn Encoder::step(self : Encoder, input : BytesView, output : MutArrayView[Byte], action~ :
    EncodeAction
    ) ->
    Status

    Compresses from input into output; see last_consumed and last_produced for how much of each it used. Input that was not taken (when the output is full) must be passed again, with the same action.

    action applies once all of input is taken: Continue only takes input, Flush compresses everything buffered and pads to a byte boundary, so that the output so far decodes to the input so far, and Finish ends the stream. Both stay in effect while the step answers NeedMoreOutput. Status: NeedMoreInput once everything is taken and its output handed out (a Flush is then complete), NeedMoreOutput while output waits, Done once the stream has ended and been handed out; after that, steps take no input and answer Done.

    Encoder::step_into

    fn Encoder::step_into(self : Encoder, input : BytesView, output : FixedArray[Byte], action~ :
    EncodeAction
    ) ->
    Status

    step into a whole FixedArray, with bulk copies.

    compress

    fn compress(input : BytesView, window_bits? : Int, dictionary? : Dictionary) -> Bytes

    Compresses input into a whole Brotli stream. window_bits is as for Encoder; the window declared is no larger than input needs (and at least 64 KiB), so that decoders reserve no more memory than necessary. dictionary is as for Encoder.

    compress_bound

    fn compress_bound(n : Int64) -> Int64

    The most bytes compress writes for n bytes of input, whatever the window: the stream header, and for each meta-block of up to 64 KiB its bytes and 5 more, since a meta-block that would come out larger than its bytes is written uncompressed (4 header bytes) and the last one then needs an empty last meta-block after it. An Encoder's stream of n bytes is within it too, plus 7 bytes for each Flush (the meta-block it ends, and the empty metadata block that pads it to a byte). A negative n counts as 0; past 2^62 the result is the largest Int64.

    decoder_memory_bound

    fn decoder_memory_bound(max_window_bits? : Int) -> Int64

    The most Decoder::memory_usage reports for a decoder made with max_window_bits (clamped to 10..24, as Decoder clamps it): the window, the prefix code tables of the largest meta-block a stream may declare (1,343,596 bytes) and the 27,793 bytes allocated with the decoder. The static dictionary is shared and an LZ77 dictionary is the caller's, so neither is counted.

    decompress

    fn decompress(input : BytesView, max_output? : Int, max_window_bits? : Int, dictionary? : Dictionary) -> Bytes raise
    CodecError

    Decodes a whole Brotli stream held in memory. max_output caps the decoded size (unlimited by default) and raises LimitExceeded({ resource: Output, .. }) past it, with max_output (0 for a negative one) as the limit; max_window_bits and dictionary are as for Decoder.

    encoder_memory_bound

    fn encoder_memory_bound(window_bits? : Int) -> Int64

    The most Encoder::memory_usage reports for an encoder made with window_bits (clamped to 10..24, as Encoder clamps it): its input buffer at its largest, twice the most output that waits (the buffer doubles), and what it allocates when it is made. A dictionary's index is counted by Dictionary::memory_usage, not here.