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); it implements the BI-style variant: 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 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):

opts := &lzss.CompressOptions{
    Checksum:    lzss.ChecksumUnsigned,
    SearchLimit: 4096,
}
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).

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 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
}

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)
• 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")
	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).

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.