README
¶
bzip2
The encoder Go's standard library does not have — pure Go, CGO_ENABLED=0,
builds for every target Go builds for.
z := bzip2.NewWriter(f)
io.Copy(z, src)
z.Close() // the stream is complete only after this returns
compress/bzip2 decompresses and nothing more, so a Go program that can read a
.tar.bz2 cannot write one, and the usual answer is to shell out to the bzip2
binary: a C program, an external dependency, and absent on most cross-compilation
targets.
There is no decoder here on purpose. The standard library's is correct, maintained and already everywhere; a second one would be a duplicate whose only distinction is being ours.
Levels are a block size
NewWriterLevel(w, 1..9) sets the block size, 100 KiB to 900 KiB — not an effort
setting. bzip2 does the same work either way; a bigger block just gives the
transform more to find redundancy in.
How good is it
Smaller than the input, and bigger than the reference:
| 106 KB of English-like text | |
|---|---|
bzip2 -9 |
11 526 bytes |
| this | 13 123 bytes (+13.9%) |
The gap is one thing, and it is named rather than hidden. bzip2 may use up to six Huffman tables per block and spends four passes deciding which group of fifty symbols each codes best. This writer emits the two the format requires as a minimum, identical, with every selector choosing the first. Adding the iteration is the obvious next step and changes no bit of the framing around it.
Verified by other people's decoders
Every archive in the tests is read back by two decoders this project did not write:
compress/bzip2, which checks both checksums;- the reference
bzip2binary, includingbzip2 -t, which verifies rather than merely parses.
An empty stream is compared byte for byte with the reference's, at three levels: an empty bzip2 file has no block in it, so nothing is left to choose and the two outputs must be the same bytes.
Beyond that, the tests assert what no decoder can: that something was actually compressed. A writer that stored its input verbatim inside a valid frame would satisfy both judges.
Two defects worth naming
The checksum is per BLOCK, and a block can close in the middle of a Write.
Folding the whole call's bytes up front credits the next block's bytes to this
one. Every single-block test passed — with one block the two are the same bytes —
and the standard library said block checksum mismatch the moment a second block
existed.
Rotations can be equal. The prefix-doubling sort stops when no class grew,
because rotations still sharing a class are the same string and no longer prefix
separates them. Without that, h doubles past n and the shift goes out of
bounds — three identical bytes were enough.
Licence
BSD-3-Clause.
Documentation
¶
Overview ¶
Package bzip2 implements the bzip2 compressed data format in pure Go, with no cgo.
The half that was missing ¶
Go's standard library has compress/bzip2, and it only DECOMPRESSES. So a program that can read a .tar.bz2 cannot write one, and the usual answer is to shell out to the bzip2 binary — which is a C program, an external dependency, and absent on most of the targets Go cross-compiles to.
This package is the encoder. There is no decoder here on purpose: the standard library's is correct, maintained and already everywhere, and a second one would be a duplicate whose only distinction is being ours.
z := bzip2.NewWriter(f) io.Copy(z, src) z.Close() // the stream is complete only after this
What bzip2 does ¶
Four transforms, in this order, and the interesting one is the second:
- a run-length pass, replacing runs of four or more identical bytes with four of them and a count — which can GROW its input by a quarter, and is why the block size bounds this pass's output rather than the caller's bytes;
- the Burrows-Wheeler transform, which sorts every cyclic rotation of the block and keeps the last column. It compresses nothing by itself: it rearranges the block so that bytes with similar contexts end up adjacent;
- move-to-front, which turns those adjacencies into small numbers and mostly zeros, with the zero runs given their own two symbols;
- Huffman coding.
Levels ¶
A level is a block SIZE, from 100 KiB at 1 to 900 KiB at 9, not an effort setting. bzip2 does the same work either way; a larger block simply gives the transform more to find redundancy in. DefaultLevel is 9, which is what the reference implementation does when asked for nothing in particular.
How good is it ¶
Smaller than the input, and bigger than the reference: on 106 KB of English-like text, bzip2 -9 produces 11 526 bytes and this produces 13 123 — about 14% more.
The gap is one thing. bzip2 may use up to six Huffman tables per block and spends four passes deciding which group of fifty symbols each table codes best; this writer emits the two the format requires as a minimum, identical, with every selector choosing the first. Adding the iteration is the obvious next step and it changes no bit of the framing around it.
Verification ¶
Every archive in the tests is read back by two decoders written by other people: the standard library's compress/bzip2, and the reference bzip2 binary where one exists — including `bzip2 -t`, which checks both checksums rather than merely parsing. An empty stream is compared BYTE FOR BYTE with the reference's, at three levels, because an empty bzip2 file has no block in it and so nothing is left to choose.
Index ¶
Constants ¶
const DefaultLevel = 9
DefaultLevel is the block size the reference implementation uses when asked for nothing in particular: 900 KiB, its largest.
Variables ¶
var ErrClosed = errors.New("bzip2: writer is closed")
ErrClosed is returned by a Writer that has already been closed.
Functions ¶
This section is empty.
Types ¶
type Writer ¶
type Writer struct {
// contains filtered or unexported fields
}
A Writer compresses to the bzip2 format.
Write buffers a block's worth of input and compresses it when full, so the output appears in bursts; Close finishes the last block and writes the stream's trailer, and the stream is incomplete until it returns.
func NewWriterLevel ¶
NewWriterLevel returns a Writer whose blocks hold level*100 KiB, for level in 1..9.
The level is a block SIZE, not an effort setting: bzip2 does the same work either way and a larger block simply gives the transform more to find redundancy in. Nothing is faster at level 1 except the sort.
Source Files