Basic Compression Library
Manual
API version 1.2
July 22, 2006
c
2003-2006 Marcus Geelnard
Summary
This document describes the algorithms used in the Basic Compression Library, and how to use the
library interface functions.
i
Contents
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The library philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 The Compression Algorithms 3
2.1 RLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Shannon-Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Rice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Lempel-Ziv (LZ77) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Compiling 11
4 Library API Reference 12
4.1 RLE_Compress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 RLE_Uncompress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 SF_Compress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.4 SF_Uncompress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.5 Huffman_Compress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.6 Huffman_Uncompress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.7 Rice_Compress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.8 Rice_Uncompress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.9 LZ_Compress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
ii
Basic Compression Library Manual API version 1.2 Page 1/16
Chapter 1
Introduction
1.1 Background
The Basic Compression Library is a set of open source implementations of several well known lossless
compression algorithms, such as Huffman and RLE, written in portable ANSI C.
The library itself is not intended to serve as a competitor to advanced general purpose compression
tools, but rather as a reference or a set of building blocks for custom compression algorithms.
An example of a field where customized compression algorithms can be be useful is the compression of
digitized media (such as images or audio), for which you usually have lots of apriori information, and
can tailor an efficient method based on entropy reduction (e.g. differentiation) followed by simple
entropy coding (e.g. Huffman coding).
In many cases entropy reduction results in data that is NOT easily compressed with advanced dictionary
based general purpose entropy coders, such as gzip or bzip2, since data often becomes very noisy after
entropy reduction. Even a simple Huffman coder can give better compression results than the most
advanced dictionary based coders under these circumstances.
1.2 The library philosophy
All compression algorithms are represented by a coder and a decoder (a compressor and a
decompressor), often referred to as a CODEC.
All coders and decoders work on preallocated memory buffers, and do not rely on any internal memory
allocation or file I/O. In addition, all library functions are 100% reentrant.
No data integrity checking is performed within the library (e.g. there are no CRCs stored in the
compressed data streams, nor any information about the size of the uncompressed data). This kind of
functionality is left to the user of the library.
