iyi

Standard library, 0.18.0

std/xz

LZMA and LZMA2 decompression, and the two files they travel in: the .xz container (The .xz File Format, version 1.0.4, Tukaani project, 2009-08-27, which 1.2.1 restates) and the legacy .lzma file that LZMA Utils and the LZMA SDK write (liblzma calls it LZMA_Alone). Written in iyi; no liblzma is linked. The decoder follows the shape of XZ Embedded's xz_dec_lzma2.c (Lasse Collin and Igor Pavlov, public domain): the range coder, the twelve-state machine, the probability tables and their layout are that file's, and so is the rule for the input - at least 21 bytes in hand before a symbol, the most one can take, or the rest of what there is - so a symbol is never begun and then left half-read when a piece of the stream runs out.

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

XzReader reads a stream a piece at a time: the compressed bytes come from a block, the decompressed ones go out through read, as std/compress's Inflater does for DEFLATE. Xz.decompress is the same reader run over one string. A stream that is not what it says - a check, an index, a header CRC that does not match, a size the data does not have, LZMA data that is not LZMA, a stream that ends early - is an XzError, a value, the first sentence that saw it, and every read after it answers the same.

What a .xz file holds is read and checked whole. Every block header's CRC32, its flags and its padding; its compressed and uncompressed sizes when it gives them, against what the block turned out to be; the block's padding, and its check - none, CRC32, CRC64 (std/digest's CRC64) or SHA-256, the four xz writes - over what was decompressed; the index, its record count, each record against the block it names (kept as liblzma keeps them, as counts and sums and a CRC-64 of the records, so a stream of a million blocks costs nothing per block), its padding and CRC32; and the stream footer against the header and the index. Streams may follow one another, with stream padding (zero bytes, a multiple of four) between and after them, as xz reads them; the check types the format reserves (2, 3, 5 to 9, 11 to 15) are refused by name rather than read unchecked. Bytes after the last stream that are neither padding nor another stream are refused too: xz refuses them, where Python's lzma.decompress drops them.

The filters a block may name are LZMA2, which must be last, and before it the delta filter and the x86 branch-call-jump filter (BCJ, with or without its start offset), the two Python's lzma and xz --delta, --x86 write for data that wants them; the other BCJ filters (PowerPC, IA-64, ARM, ARM-Thumb, SPARC, ARM64, RISC-V) are refused by name. A .lzma file is a 13-byte header - lc, lp and pb, the dictionary size and the uncompressed size or "unknown" - and one LZMA stream, ended by its size, by the end-of-payload marker, or by the size and then a marker, which XZ Utils' own test files hold good too; bytes after it are refused. A block header's sizes are held to as the block is read: a chunk that would take it past either is refused before it is decoded.

Memory is the dictionary and what waits to be read, and the dictionary is the stream's own word for how far back it reaches: an LZMA2 filter's dictionary property, a .lzma header's size. One past the reader's dict_limit - 64 MiB unless the caller says otherwise, what xz -9 writes - is refused before anything is allocated for it, so a stream cannot ask for more memory than the caller agreed to. Under it, the ring the dictionary lives in starts at 64 KiB and doubles as the output reaches it, so a kilobyte written with xz -9e's 64 MiB dictionary allocated under 512 KiB in all (the gate measures it). The input is a buffer of 128 KiB that the pieces are copied through. Streamed 64 KiB a read, 64 MiB with an 8 MiB dictionary kept the collector under 12 MiB. Measured on one x86_64 machine, release build: 2.3 MB of prose from a 0.8 MB stream took 50 ms where liblzma through Python took 18, and 64 MiB of word-salad text 1.15 s where it took 0.47.

Left out: compression, the BCJ filters but x86, reading a multi-block file's blocks in parallel (one from xz -T is read one block after another), and random access through the index.

Strings are the byte type here, as everywhere in src/std: a compressed stream is a String whose bytes are the stream.

Xzstruct

std/xziyi doc src/std/xz.iyi
pub struct Xz
  # The bytes *data* decompresses to - every stream of a .xz file, or the
  # one of a .lzma file - or the `XzError` `XzReader` would answer.
  def self.decompress(data : String, format : XzFormat = XzFormat::Xz, dict_limit : Int64 = XzReader::DICT_LIMIT) : String | XzError
  def initialize
end

XzErrorstruct

What XzReader#read and Xz.decompress answer for a stream they cannot read: one that is corrupt, whose check or index or sizes do not match, that ends early, or whose dictionary is past the caller's limit.

std/xziyi doc src/std/xz.iyi
pub struct XzError
  def initialize(message : String)
  def to_s : String
end

XzFormatenum

The two files LZMA travels in: the .xz container, and the .lzma file of LZMA Utils and the LZMA SDK.

std/xziyi doc src/std/xz.iyi
pub enum XzFormat : Int32
  Xz = 0
  Lzma = 1
end

XzReaderclass

A .xz or .lzma 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 stream's dictionary and what is waiting to be read.

xz = XzReader.new { file.read_bytes(65536) }
while (piece = xz.read(65536)!) != ""
  ...
end
std/xziyi doc src/std/xz.iyi
pub class XzReader
  # For `Xz.decompress`.
  protected def core : XzCore
  # Whether the stream has ended, everything about it been 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. *dict_limit* is the largest dictionary a
  # stream may name, 4 KiB to 1.5 GiB; a stream that names more is an
  # `XzError` before anything is allocated for it. A .xz file is read to
  # the end of its source - streams and the padding between them - so the
  # source is asked until it says there is no more.
  def initialize(format : XzFormat = XzFormat::Xz, dict_limit : Int64 = DICT_LIMIT, &source : (-> String | ::Nil))
  # Up to *max* decompressed bytes; "" once the stream has ended and
  # everything about it been checked. A read answers as soon as it has
  # bytes and going on would call the source, so it can answer fewer than
  # *max* before the end; and never more than the dictionary at once.
  #
  # A corrupt stream, a check, index or size that does not match, input
  # that ends early, or a dictionary past the limit is an `XzError`, after
  # which every read answers the same error. A block's check is compared
  # after its last byte has been handed out, so the bytes before a bad
  # check have been read by then, as they are from a gzip stream. A *max*
  # below 1 is a panic.
  def read(max : Int32 = 65536) : String | XzError
end

Error for XzErrorimpl

std/xziyi doc src/std/xz.iyi
impl Error for XzError
  def message : String
end