ARI - Arithmetic Coding Library

A compact C library implementing arithmetic coding for lossless data compression.

Overview

Arithmetic coding is an entropy encoding technique that can approach the theoretical compression limit for a given probability model. This library provides a simple API for encoding and decoding bit streams using adaptive arithmetic coding with 32-bit precision.

Features

• Efficient encoding/decoding: 32-bit precision arithmetic coding implementation
• Probability-based compression: Each bit can be encoded with its own probability distribution
• Custom memory allocators: Configurable allocation functions for embedded systems
• Self-contained format: Encoded data includes magic number and metadata
• Clean API: Simple encoder/decoder interface

Building

Compile the library and test:

gcc -o test_ari test_ari.c ari.c -O2
./test_ari

API Reference

Encoder

// Create a new encoder
ari_Encoder *ari_new_encoder(void);

// Encode a bit with probability p0 for bit 0
// Returns 1 on success, -1 on error
int ari_encode(ari_Encoder *enc, int bit, float p0);

// Finalize encoding and get packed data
// Caller must free the returned pointer using ari_free()
void *ari_get_packed(ari_Encoder *enc);

// Free encoder resources
void ari_free_encoder(ari_Encoder *enc);

Decoder

// Create decoder from packed data
ari_Decoder *ari_new_decoder(void *packed);

// Decode next bit using probability p0 for bit 0
int ari_decode_bit(ari_Decoder *dec, float p0);

// Free decoder resources
void ari_free_decoder(ari_Decoder *dec);

Custom Memory Allocation

// Override default malloc/free
extern void *(*ari_alloc)(size_t);
extern void (*ari_free)(void *);

Usage Example

#include "ari.h"

// Encode
ari_Encoder *enc = ari_new_encoder();
ari_encode(enc, 0, 0.7);  // Encode 0 with p(0) = 0.7
ari_encode(enc, 1, 0.3);  // Encode 1 with p(0) = 0.3
void *packed = ari_get_packed(enc);
ari_free_encoder(enc);

// Decode
ari_Decoder *dec = ari_new_decoder(packed);
int bit1 = ari_decode_bit(dec, 0.7);  // Returns 0
int bit2 = ari_decode_bit(dec, 0.3);  // Returns 1
ari_free_decoder(dec);
ari_free(packed);

File Format

The packed data format includes:

• Bytes 0-7: Total packed size (uint64_t)
• Bytes 8-15: Magic number ("ari\x1a" + 4 zero bytes)
• Bytes 16-23: Original bit count (uint64_t)
• Bytes 24+: Encoded bit stream

Performance

The included test program encodes 8 million bits using a 4-context probability model, demonstrating compression efficiency with various probability distributions.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Author

Andrea Griffini