iyi

Standard library, 0.18.0

std/bzip2

bzip2 (Julian Seward's format, as libbzip2 1.0.8 writes and reads it), both ways, written in iyi; no libbzip2 is linked. There is no RFC: the format is what bzip2's own compress.c, decompress.c and blocksort.c do, written down in Joe Tsai's "BZip2 format specification" (2016), which this follows.

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

A stream is "BZh" and a block-size digit 1 to 9 (blocks of up to 100,000 to 900,000 bytes), then blocks, each opened by the 48 bits of pi's BCD digits 0x314159265359 and carrying its own CRC, then the 48 bits of sqrt(pi) 0x177245385090 and the stream's combined CRC, then zeros to a byte. Every field is read most significant bit first. A block undoes five transforms, outermost first: Huffman coding (two to six tables, which one codes each run of 50 symbols named by a selector, the selectors themselves move-to-front coded), the zero-run code of RUNA and RUNB (bijective base 2) over a move-to-front of the bytes the block uses, the Burrows-Wheeler transform (its origin pointer naming the row that is the block), and the first run-length code (four equal bytes and a count of 0 to 251 more). The CRC is the MSB-first CRC-32 (polynomial 0x04c11db7) of what the block gives; the combined CRC is each block's folded in by rotating left one bit and XORing. Both are checked, and a mismatch is an error, not a warning.

Bzip2Reader reads a stream a piece at a time, the shape of std/compress's Inflater: the compressed bytes come from a block when the decoder needs them, the decompressed ones go out through read. A block has to be read whole before the first of its bytes is known - the BWT is over the block - so memory is one block's: the 32-bit links of the inverse BWT (four bytes a byte, 3.6 MB for a 900k block), and a 64 KiB buffer read answers from. Nothing of the output is kept: the inverse BWT and the run-length code are undone as read asks, a step through the links a byte. A file that is several streams one after another, as cat a.bz2 b.bz2 and pbzip2 make, is read as what they hold one after another, as bzip2(1) and Python's bz2 read it. Bytes after a stream that do not start another ("BZh" and a digit) end the input and are leftover; bzip2(1) ignores trailing garbage the same way, where Python's bz2.decompress refuses it.

What a stream that is not one gets is a Bzip2Error, a value, whose sentence names what is wrong: the magic, a block header, a randomised block (which bzip2 stopped writing at 0.9.5, when its fallback sort replaced randomising; refused as Go refuses it), a mapping that uses no byte, a table count outside 2 to 6, no selectors or one past the tables, a code length outside 1 to 20, an over-subscribed table, a bit pattern no code has, more symbols than the selectors cover, a block past its declared size, an origin pointer outside the block, either CRC, and a stream that ends early. The bounds are libbzip2's (decompress.c); what it reads and this does not is the randomised block and the over-subscribed table, which it builds without looking and no bzip2 writes.

Bzip2.compress(data, level) writes a stream libbzip2 reads: the first run-length code, the BWT, the move-to-front and zero-run code, and bzip2's own table choice - two to six tables by how many symbols the block has, seeded by splitting the symbol frequencies and refined four times by giving each 50-symbol group to the table that codes it in the fewest bits, then code lengths up to 17 bits. The output is valid, not libbzip2's byte for byte: the BWT is a different sort and ties between equal frequencies break differently.

The BWT is the order of the block's rotations, which comparison sorts find slowly on repetitive data: two rotations of "abab..." agree for the whole block, so a quicksort compares a block's length a pair, and libbzip2 falls back from its quicksort to a slower sort when its budget runs out. This sorts by prefix doubling instead (Manber and Myers, 1990; Karp, Miller and Rosenberg's ranks): rank the rotations by their first byte, then by their first 2, 4, 8... bytes from the ranks of the halves with two counting sorts a round, stopping once every rank is distinct or the prefix covers the block. That is O(n log n) whatever the input: at most twenty rounds for a 900k block, and on noise the ranks are distinct after a few. Measured on this machine, built with --release, against Python's bz2 (libbzip2 1.0.8) on the same bytes: 1 MiB of one byte compresses in 5 ms (libbzip2 4), 1 MiB of "ab" in 43 ms (76), 1 MiB of random bytes in 79 ms (56); Python's 64 MiB stream reads back through Bzip2Reader in 252 ms (bz2.decompress 240), the collector keeping 3.5 MB past what it held before.

Strings are the byte type here, as everywhere in src/std. Left out: randomised blocks (refused by name), and a streaming compressor.

Bzip2struct

std/bzip2iyi doc src/std/bzip2.iyi
pub struct Bzip2
  # *data* as one bzip2 stream with blocks of *level* * 100,000 bytes,
  # 1 to 9 (bzip2's -1 to -9); any other level is a panic.
  def self.compress(data : String, level : Int32 = 9) : String
  # Every byte *data*'s streams hold, or the error the first wrong thing in
  # them is. Bytes after the last stream that do not start another are
  # ignored, as bzip2(1) ignores them.
  def self.decompress(data : String) : String | Bzip2Error
  def initialize
end

Bzip2Errorstruct

What Bzip2Reader#read and Bzip2.decompress answer for a stream they cannot read: one that is corrupt, whose CRC does not match, or that ends early.

std/bzip2iyi doc src/std/bzip2.iyi
pub struct Bzip2Error
  def initialize(message : String)
  def to_s : String
end

Bzip2Readerclass

A bzip2 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 one block's links and a 64 KiB buffer.

body = Bzip2Reader.new { file.read_bytes(65536) }
while (piece = body.read(65536)!) != ""
  ...
end
std/bzip2iyi doc src/std/bzip2.iyi
pub class Bzip2Reader
  # Whether every stream has ended, its CRCs 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. It is called only when the decoder has no
  # bytes in hand for what it must read next, so it is never asked for
  # anything past a stream's end - except that the input ends only where
  # no stream follows, which takes a look at the next four bytes.
  def initialize(&source : (-> String | ::Nil))
  # Bytes the source gave beyond the last stream, for a caller that frames
  # other data after it; "" before the input has ended.
  def leftover : String
  # Up to *max* decompressed bytes, 64 KiB at most; "" once every stream
  # has ended and its CRCs been checked. A read that has bytes when a
  # block ends answers them rather than reading the next block, so it can
  # answer fewer than *max* before the end.
  #
  # A corrupt stream, a CRC that does not match, or input that ends early
  # is a `Bzip2Error`, after which every read answers the same error. A
  # block's bytes are given out before its CRC is known, as the CRC is
  # over them; the read that gives its last byte checks it, and answers
  # the error instead of those bytes. A *max* below 1 is a panic.
  def read(max : Int32 = 65536) : String | Bzip2Error
end

Error for Bzip2Errorimpl

std/bzip2iyi doc src/std/bzip2.iyi
impl Error for Bzip2Error
  def message : String
end