iyi

Standard library, 0.18.0

std/zstd

Zstandard (RFC 8878), read and written in iyi; no libzstd is linked. It is the third Content-Encoding HTTP names (RFC 9659) beside gzip and deflate, which std/compress has.

import std/zstd to use it. Source: src/std/zstd.iyi at v0.18.0.

Reading is the whole format but dictionaries: frames one after another and skippable frames between them (§3.1), every header form, raw, RLE and compressed blocks (§3.1.1.2), literals raw, RLE or Huffman-coded in one stream or four, with the table described (weights direct or FSE-compressed) or the last block's reused (§3.1.1.3.1, §4.2), and sequences whose codes are sent with the predefined tables, one symbol, a table described in the block, or the last block's (§3.1.1.3.2, §4.1), the repeat offsets moved as §3.1.1.5 moves them. What a frame says is held to it: the content size, and the checksum - the low 32 bits of the content's XXH64, from std/digest - where the frame carries them; blocks no larger than the frame's block maximum; offsets inside the window and the frame. A frame that needs a dictionary is refused by its ID, and so is one whose window is past the caller's limit - WINDOW_LIMIT, 8 MiB, unless asked otherwise, the size §3.1.1.1.2 recommends and RFC 9659 holds HTTP to - because the window is the memory the reader keeps, and the peer chooses it.

A refusal is a ZstdError, a value: these are bytes from outside the program, not a mistake in it. What panics is the caller's own mistake: a read of no bytes, a window limit outside 1 KiB to 512 MiB.

ZstdReader reads a piece at a time: compressed bytes pulled from the block as a block needs them, a block decoded whole - its bitstreams are read from their ends - and its bytes handed out by read. What it keeps is one buffer of at most two windows and a block: the window behind the write position, which back-references reach into, and room ahead. It slides once that frees a window, so a byte decoded is moved at most once, where a buffer of one window and a block would move the whole window every block. Zstd.decompress is the same decoder over one piece, its buffer grown instead and answered whole; it refuses bytes after the last frame that begin none, as Python's zstd does, where the reader leaves them as leftover.

Zstd.compress writes one frame with the content size and a checksum: blocks of 128 KiB, a block of one byte repeated as an RLE block, the rest through a greedy matcher (a 1 MiB window, one candidate a hash of four bytes, the last offset tried first, new offsets only for six bytes or more), literals Huffman-coded and the sequence codes through tables made for each block, falling back to a raw block where that is no larger. On 4.2 MB of src/std it writes 1,275,717 bytes where Python's zstd at level 1 writes 1,285,541, zlib at level 1 1,408,756 and at level 6 1,175,988.

Measured on this machine, release builds: the 64 MiB the gate streams through ZstdReader in 41 ms, where Python's compression.zstd takes 35 ms to decompress it whole; those 4.2 MB compressed in 36 ms and read back in 15, where Python takes 10 and 5 at level 1.

Strings are the byte type here, as everywhere in src/std. The decoder loads words of the stream with one unaligned little-endian load, which every target iyi builds for is.

Zstdstruct

std/zstdiyi doc src/std/zstd.iyi
pub struct Zstd
  # One frame of *data*, with its content size and checksum, that any
  # Zstandard decoder reads with a window of 1 MiB at most.
  def self.compress(data : String) : String
  # Every frame of *data*, one after another, or the error that stopped
  # it. Bytes after the last frame that do not begin another are refused,
  # as is a stream with no frame at all.
  def self.decompress(data : String, max_window : Int32 = WINDOW_LIMIT) : String | ZstdError
  def initialize
end

ZstdErrorstruct

What ZstdReader#read and Zstd.decompress answer for a stream they cannot read: one that is corrupt, that ends early, whose checksum or content size does not match, or that asks for what this decoder does not give (a dictionary, a window past the caller's limit).

std/zstdiyi doc src/std/zstd.iyi
pub struct ZstdError
  def initialize(message : String)
  def to_s : String
end

ZstdReaderclass

A Zstandard stream read a piece at a time: the compressed bytes come from the block, the decompressed ones go out through read, and memory stays at the frame's window, twice over at most, and a block.

body = ZstdReader.new { socket_read }
while (piece = body.read(65536)!) != ""
  ...
end
std/zstdiyi doc src/std/zstd.iyi
pub class ZstdReader
  # Whether the stream has ended, its checksums checked, and every byte
  # been read: the next `read` answers "".
  def finished? : Bool
  # *source* answers the next bytes of the compressed stream, nil (or "")
  # when there are no more. *max_window* is the largest window a frame
  # may ask for; a frame that asks for more is refused rather than given
  # the memory. A limit outside 1 KiB to 512 MiB is a panic.
  def initialize(max_window : Int32 = Zstd::WINDOW_LIMIT, &source : (-> String | ::Nil))
  # Bytes the source gave beyond the last frame, for a caller that frames
  # other data after it; "" before the stream has ended.
  def leftover : String
  # Up to *max* decompressed bytes; "" once the last frame has ended and
  # been checked. A read answers what the last block decoded before it
  # decodes another, so it can answer fewer than *max* before the end, and
  # never more than a block (128 KiB).
  #
  # A corrupt stream, a bad checksum, a frame past the window limit or
  # input that ends early is a `ZstdError`, after which every read answers
  # the same error. A *max* below 1 is a panic.
  def read(max : Int32 = 65536) : String | ZstdError
end

Error for ZstdErrorimpl

std/zstdiyi doc src/std/zstd.iyi
impl Error for ZstdError
  def message : String
end