variety-0.1.0.2: integer arithmetic codes
Safe HaskellSafe-Inferred
LanguageHaskell2010

Codec.Elias.Natural

Description

Elias codes are prefix codes for positive, non-zero integers with no assumption or limit to their size.

Functions of this module add 1 at encoding time and subtract 1 at decoding time to support any natural number, including zero.

Synopsis

Gamma coding

An Elias gamma code consists of the binary expansion of an integer, preceded by the unary encoding of the length of that expansion in zeros.

encodeGamma :: Integer -> BitVec Source #

Encode a number in a Elias gamma code. Throws an error if the input is negative.

decodeGamma :: BitVec -> Maybe (Integer, BitVec) Source #

Try to decode an Elias gamma code at the head of the given bit vector. If successful, returns the decoded value and the remainder of the BitVec, with the value code removed. Returns Nothing if the bit vector doesn't contain enough bits to define a number.

Delta coding

An Elias delta code is like an Elias gamma code except that the length is itself coded like a gamma code instead of simply a unary encoding.

encodeDelta :: Integer -> BitVec Source #

Encode a number in a Elias delta code. Throws an error if the input is negative.

decodeDelta :: BitVec -> Maybe (Integer, BitVec) Source #

Try to decode an Elias delta code at the head of the given bit vector. If successful, returns the decoded value and the remainder of the BitVec, with the value code removed. Returns Nothing if the bit vector doesn't contain enough bits to define a number.

Omega coding

An Elias omega code is the result of recursively encoding the length of binary expansions in the prefix until a length of 1 is reached. Since binary expansions are written without any leading zeros, a single 0 bit marks the end of the code.

encodeOmega :: Integer -> BitVec Source #

Encode a number in a Elias omega code. Throws an error if the input is negative.

decodeOmega :: BitVec -> Maybe (Integer, BitVec) Source #

Try to decode an Elias omega code at the head of the given bit vector. If successful, returns the decoded value and the remainder of the BitVec, with the value code removed. Returns Nothing if the bit vector doesn't contain enough bits to define a number.