lzss

README

lzss

Lempel–Ziv–Storer–Szymanski (LZSS) compression and decompression in Go - LZSS:8bit variant.
This is not the classic Okumura/Apple LZSS (ring-buffer index); backward offset from current output position, 8 flag bits per 8 slots, 12-bit offset + 4-bit length, 4096-byte window, trailing 4-byte checksum. Used in some archive and texture formats.

Install

go get github.com/woozymasta/lzss

Usage

Decompress

default: unsigned checksum, strict verification:

out, err := lzss.Decompress(compressed, expectedLen, nil)

decompress one block from []byte and get consumed bytes:

out, consumed, err := lzss.DecompressBlock(src, expectedLen, nil)

decompress one block from stream without reading to EOF:

out, consumed, err := lzss.DecompressFromReader(r, expectedLen, nil)

decompress multiple blocks from stream with known output sizes:

out, consumed, err := lzss.DecompressNFromReader(r, []int{lenA, lenB}, nil)

decompress blocks while callback returns next expected output size:

next := func() (int, bool) {
    // return next output size, true; return 0, false to stop
}
out, consumed, err := lzss.DecompressUntilEOF(r, next, nil)

Decompress with signed checksum and lenient verification (no error on checksum mismatch):

out, err := lzss.Decompress(compressed, expectedLen, lzss.SignedLenientOptions())

Compress

default search limit 2048:

out, err := lzss.Compress(data, nil)

with options (search limit, checksum mode, encodes length):

opts := &lzss.CompressOptions{
    Checksum:       lzss.ChecksumUnsigned,
    SearchLimit:    4096,
    MinMatchLength: 3,
}
out, err := lzss.Compress(data, opts)

Format details

• Flag byte: 8 bits; bit = 1 -> literal (1 byte), bit = 0 -> pointer (2 bytes).
• Pointer: 12-bit backward offset, 4-bit length -> 3..18 bytes. Stored little-endian.
• Window: 4096 bytes. When offset refers before start of output, filler byte 0x20 is used.
• Checksum: 4 bytes at end. Either unsigned (sum of bytes as uint8) or signed (sum as int8). Some formats use signed and ignore mismatch - use SignedLenientOptions() for decompress.

Peculiarities

• Back-references can overlap the write position (offset < length). The decoder must copy byte-by-byte in that case, not block-copy.
• Two checksum modes and optional strict/lenient verification; choose options to match the stream format (e.g. archives vs certain texture formats).
• Compressed block length is not stored in most containers. DecompressFromReader and DecompressBlock stop when output buffer is full, then read checksum and return consumed bytes.

Documentation

Overview

Package lzss implements LZSS:8bit compression and decompression.

Format: one flag byte per 8 slots; bit 1 = literal (1 byte), bit 0 = pointer (2 bytes). Pointer: 12-bit backward offset from current output position, 4-bit length nibble. Default (MinMatchLength 3): length = nibble+3 -> 3..18 bytes. Use MinMatch2 for nibble+2 -> 2..17. Sliding window: 4096 bytes; filler 0x20 when offset refers before start of output. Trailing 4-byte checksum: either unsigned (sum of bytes as uint8) or signed (sum as int8).

Use Decompress(src, outLen, opts) with nil for default (unsigned, strict checksum). Use DecompressBlock(src, outLen, opts) to decode from the beginning of src and get consumed bytes. Use DecompressFromReader(r, outLen, opts) to decode one block from a stream without reading to EOF. Use DecompressNFromReader(r, outLens, opts) to decode multiple blocks with known output sizes. Use DecompressUntilEOF(r, nextOutLen, opts) when output size is provided by a callback. Use SignedLenientOptions() for formats that use signed checksum and ignore mismatch. Set Options.MinMatchLength or CompressOptions.MinMatchLength to MinMatch2 for 2..17 back-ref length.

Examples

Decompress with default options (unsigned checksum, strict):

out, err := lzss.Decompress(encoded, expectedLen, nil)
if err != nil {
	return err
}

Decompress one block from a byte stream and continue from current stream position:

out, consumed, err := lzss.DecompressFromReader(r, expectedLen, nil)
if err != nil {
	return err
}
_ = consumed

Decompress multiple blocks from a stream with known output sizes:

out, consumed, err := lzss.DecompressNFromReader(r, []int{lenA, lenB}, nil)
if err != nil {
	return err
}
_ = consumed
_ = out

Round-trip compress and decompress:

enc, err := lzss.Compress(data, nil)
if err != nil {
	return err
}
dec, err := lzss.Decompress(enc, len(data), nil)
if err != nil {
	return err
}
// dec equals data

Decompress with signed checksum and skip verification (lenient):

opts := lzss.SignedLenientOptions()
out, err := lzss.Decompress(src, outLen, opts)

Compress and decompress with min match length 2 (back-ref length 2..17):

copts := &lzss.CompressOptions{SearchLimit: 2048, MinMatchLength: lzss.MinMatch2}
enc, _ := lzss.Compress(data, copts)
dopts := &lzss.Options{MinMatchLength: lzss.MinMatch2, VerifyChecksum: true}
dec, _ := lzss.Decompress(enc, len(data), dopts)

Index

• Constants
• Variables
• func Compress(src []byte, opts *CompressOptions) ([]byte, error)
• func Decompress(src []byte, outLen int, opts *Options) ([]byte, error)
• func DecompressBlock(src []byte, outLen int, opts *Options) ([]byte, int, error)
• func DecompressFromReader(r io.Reader, outLen int, opts *Options) ([]byte, int64, error)
• func DecompressNFromReader(r io.Reader, outLens []int, opts *Options) ([][]byte, int64, error)
• func DecompressUntilEOF(r io.Reader, nextOutLen func() (int, bool), opts *Options) ([][]byte, int64, error)
• type ChecksumMode
• type CompressOptions
  • func DefaultCompressOptions() *CompressOptions
• type Options
  • func DefaultOptions() *Options
  • func SignedLenientOptions() *Options

Constants

const (
	// WindowSize is the sliding window size (ring buffer).
	WindowSize = 4096

	// MaxMatch is the maximum back-reference length when MinMatchLength is 3 (encoded 3..18).
	MaxMatch = 18

	// Filler is the fill byte when back-reference offset is before start of output.
	Filler = 0x20

	// FlagBits is the number of bits per flag byte (one flag byte per 8 slots: literal or pointer).
	FlagBits = 8

	// MinMatchDefault is the default minimum back-reference length (3..18). Use MinMatch2 for range 2..17.
	MinMatchDefault = 3

	// MinMatch2 is the minimum back-reference length when nibble encodes length-2, range 2..17.
	MinMatch2 = 2
)

LZSS:8bit format constants.

Variables

var (
	ErrInputTooShort     = errors.New("not enough data for checksum")
	ErrUnexpectedEOF     = errors.New("unexpected end of input while reading flags")
	ErrUnexpectedEOFBit  = errors.New("unexpected end of input inside flags block")
	ErrTrailingData      = errors.New("trailing bytes after lzss block")
	ErrNilReader         = errors.New("reader is nil")
	ErrNilOutLenProvider = errors.New("outLen provider is nil")
	ErrNegativeOutLen    = errors.New("output length must be non-negative")
	ErrEmptyInput        = errors.New("input is empty")
)

Package errors. Use errors.New for static messages, fmt.Errorf when values are needed.

Functions

func Compress

func Compress(src []byte, opts *CompressOptions) ([]byte, error)

Compress compresses src. Options nil means DefaultCompressOptions().

func Decompress

func Decompress(src []byte, outLen int, opts *Options) ([]byte, error)

Decompress decompresses src into a new buffer of length outLen. Options nil means DefaultOptions (unsigned checksum, strict verification).

func DecompressBlock

func DecompressBlock(src []byte, outLen int, opts *Options) ([]byte, int, error)

DecompressBlock decompresses one LZSS block from the beginning of src. It returns decompressed bytes and the number of consumed bytes (data + checksum). Unlike Decompress, this function ignores trailing bytes after the first block.

func DecompressFromReader

func DecompressFromReader(r io.Reader, outLen int, opts *Options) ([]byte, int64, error)

DecompressFromReader decompresses one LZSS block from r and returns consumed bytes. Decoding stops exactly after outLen output bytes and trailing 4-byte checksum are read.

func DecompressNFromReader

func DecompressNFromReader(r io.Reader, outLens []int, opts *Options) ([][]byte, int64, error)

DecompressNFromReader decompresses N LZSS blocks from r with expected output lengths. It returns decompressed blocks and total consumed byte count across all blocks.

func DecompressUntilEOF

func DecompressUntilEOF(r io.Reader, nextOutLen func() (int, bool), opts *Options) ([][]byte, int64, error)

DecompressUntilEOF decompresses blocks from r while nextOutLen returns (outLen, true). nextOutLen must provide expected unpacked size for each next block.

Types

type ChecksumMode

type ChecksumMode int

ChecksumMode defines how the 4-byte checksum is computed.

const (
	// Sum bytes as uint8 (default for archives).
	ChecksumUnsigned ChecksumMode = iota

	// Sum bytes as int8 (used by some texture formats).
	ChecksumSigned
)

Checksum mode constants.

type CompressOptions

type CompressOptions struct {
	// Checksum mode: unsigned or signed.
	Checksum ChecksumMode
	// 0 = literals only; otherwise max backward distance for match search (e.g. 64..4096).
	SearchLimit int
	// MinMatchLength: 3 (default) encodes length 3..18; 2 encodes 2..17. Zero is 3.
	MinMatchLength int
}

CompressOptions configures compression (checksum mode and search limit).

func DefaultCompressOptions

func DefaultCompressOptions() *CompressOptions

DefaultCompressOptions returns options for default compression (unsigned checksum, search limit 2048).

type Options

type Options struct {
	// Checksum sets unsigned vs signed checksum.
	Checksum ChecksumMode
	// VerifyChecksum: if true, Decompress returns an error on checksum mismatch.
	// If false, mismatch is ignored (lenient mode for formats with often-bad checksums).
	VerifyChecksum bool
	// MinMatchLength is the minimum back-reference length used when decoding the length nibble.
	//  - 3 (default): nibble + 3 -> length 3..18.
	//  - 2: nibble + 2 -> length 2..17.
	// Zero is treated as 3.
	MinMatchLength int
}

Options configures Decompress and Compress behavior.

func DefaultOptions

func DefaultOptions() *Options

DefaultOptions returns options for default behavior: unsigned checksum, strict verification.

func SignedLenientOptions

func SignedLenientOptions() *Options

SignedLenientOptions returns options: signed checksum, do not return error on mismatch.