Arithmetic coding implementation. More...

#include <stdio.h>
#include <string.h>
#include "stream.h"

Classes
struct	_state_t
	Encoder/Decoder state. More...
Defines
#define	ENDL "\n"
#define	TRY(e)
#define	SAFE_FREE(e) if(e) { free(e); (e)=NULL; }
#define	B (state->b)
#define	L (state->l)
#define	C (state->cdf)
#define	SHIFT (state->shift)
#define	NSYM (state->nsym)
#define	MASK (state->mask)
#define	STREAM (&(state->d))
#define	DATA (state->d.d)
#define	OFLOW (STREAM->overflow)
#define	bitsofD (8)
#define	D (1ULL<<bitsofD)
#define	LOWL (state->lowl)
#define	DEFN_UPDATE(T)
#define	DEFN_ERENORM(T)
#define	DEFN_ESELECT(T)
#define	DEFN_ESTEP(T)
#define	DEFN_ENCODE(TOUT, TIN)
#define	DEFN_ENCODE_OUTS(TIN)
#define	DEFN_DRENORM(T)
#define	DEFN_DPRIME(T)
#define	DEFN_DSTEP(T)
#define	DEFN_DECODE(TOUT, TIN)
#define	DEFN_DECODE_OUTS(TIN)
#define	DEFN_VENCODE(T)
#define	DEFN_VDECODE(T)
Typedefs
typedef uint8_t	u8
typedef uint8_t	u16
typedef uint32_t	u32
typedef uint64_t	u64
typedef float	real
typedef struct _state_t	state_t
	Encoder/Decoder state.
Functions
static void	init_common (state_t state, u8 buf, size_t nbuf, real *cdf, size_t nsym)
	A helper function that initializes the parts of the state_t structure that do not depend on stream type.
static void	init_u1 (state_t state, u8 buf, size_t nbuf, real *cdf, size_t nsym)
	Initialize the state_t structure for `u1` streams.
static void	init_u4 (state_t state, u8 buf, size_t nbuf, real *cdf, size_t nsym)
	Initialize the state_t structure for `u4` streams.
static void	init_u8 (state_t state, u8 buf, size_t nbuf, real *cdf, size_t nsym)
	Initialize the state_t structure for `u8` streams.
static void	init_u16 (state_t state, u8 buf, size_t nbuf, real *cdf, size_t nsym)
	Initialize the state_t structure for `u16` streams.
static void	free_internal (state_t *state)
	Releases resources held by the state_t structure.
static u32	maximum (u32 *s, size_t n)
	Array maximum.
void	cdf_build (real *cdf, size_t M, u32 *s, size_t N)
	Build a cumulative distribution function (CDF) from an input u32 array.
void	carry_null (stream_t *s)
void	push_null (stream_t *s)
	DEFN_UPDATE (u1)
	DEFN_UPDATE (u4)
	DEFN_UPDATE (u8)
	DEFN_UPDATE (null)
	DEFN_ERENORM (u1)
	DEFN_ERENORM (u4)
	DEFN_ERENORM (u8)
static void	erenorm_null (state_t *state)
	DEFN_ESELECT (u1)
	DEFN_ESELECT (u4)
	DEFN_ESELECT (u8)
	DEFN_ESTEP (u1)
	DEFN_ESTEP (u4)
	DEFN_ESTEP (u8)
	DEFN_ESTEP (null)
	DEFN_ENCODE_OUTS (u8)
	DEFN_ENCODE_OUTS (u32)
	DEFN_ENCODE_OUTS (u64)
static u64	dselect (state_t state, u64 v, int *isend)
	DEFN_DRENORM (u1)
	DEFN_DRENORM (u4)
	DEFN_DRENORM (u8)
	DEFN_DPRIME (u1)
	DEFN_DPRIME (u4)
	DEFN_DPRIME (u8)
	DEFN_DSTEP (u1)
	DEFN_DSTEP (u4)
	DEFN_DSTEP (u8)
	DEFN_DECODE_OUTS (u1)
	DEFN_DECODE_OUTS (u4)
	DEFN_DECODE_OUTS (u8)
void	sync (stream_t dest, stream_t src)
void	vdecode1 (u8 *out, size_t nout, u8 in, size_t nin, real cdf, size_t nsym, real *tcdf, size_t tsym)
	DEFN_VENCODE (u8)
	DEFN_VENCODE (u32)
	DEFN_VENCODE (u64)
	DEFN_VDECODE (u8)
	DEFN_VDECODE (u32)
	DEFN_VDECODE (u64)

Detailed Description

Arithmetic coding implementation.

Introduction

Implementation after Amir Said's Algorithm 22-29[1].

Following Amir's notation,

D is the number of symbols in the output alphabet. P is the number of output symbols in the active block (see Eq 2.3 in [1]). Need 2P for multiplication.

So, have 2P*bitsof(D) = 64 (widest integer type I'll have access to)

The smallest codable probabililty is p = D/D^P = D^(1-P). Want to minimize p wrt constraint. Enumerating the possibilities:

     bitsof(D)  P                D^(1-P)
     --------   --               -------
     1          32                2^-32
     8          4    (2^8)^(-3) = 2^-24
     16         2                 2^-16
     32         1                 1

One can see there's a efficiency verses precision trade off here (higher D means less renormalizing and so better efficiency).

Notes

Need to test more!
- u1,u4,u16 encoding/decoding not tested
- random sequences etc...
- empty stream?
- streams that generte big carries

might be nice to add an interface that will encode chunks. That is, you feed it symbols one at a time and every once in a while, when bits get settled, it outputs some bytes. For streaming encoders, this would mean the intermediate buffer wouldn't have to be quite as big, although worst case that buffer is the size of the entire output message.

A check-symbol could be encoded in a manner similar to the END-OF-MESSAGE symbol. For example, code the symbol every 2^x symbols and assign it a probability of 2^-x. If the decoder doesn't recieve one of these at the expected interval, then there was some error. For short messages, it wouldn't require the insertion of such a symbol; only failure to show up after N symbols would indicate an error. It would take space on the interval, and so would have a negative impact on compression and minimum probability.

References

   [1]:  Said, A. "Introduction to Arithmetic Coding - Theory and Practice."
         Hewlett Packard Laboratories Report: 2004-2076.
         www.hpl.hp.com/techreports/2004/HPL-2004-76.pdf

Definition in file ac.c.

Define Documentation

#define ENDL "\n"

Definition at line 230 of file ac.c.

#define SAFE_FREE ( e ) if(e) { free(e); (e)=NULL; }

Definition at line 238 of file ac.c.

#define TRY ( e )

Value:

do{ if(!(e)) {\
    printf("%s(%d):"ENDL "\t%s"ENDL "\tExpression evaluated as false."ENDL, \
        __FILE__,__LINE__,#e); \
    goto Error; \
  }} while(0)

Definition at line 231 of file ac.c.

Typedef Documentation

typedef float real

Definition at line 228 of file ac.c.

typedef uint8_t u16

Definition at line 225 of file ac.c.

typedef uint32_t u32

Definition at line 226 of file ac.c.

typedef uint64_t u64

Definition at line 227 of file ac.c.

typedef uint8_t u8

Definition at line 224 of file ac.c.

Classes

Defines