5th August 2020, 10:42
Right, it is better to just write it as a binary number, since the range or length in bits is needed anyway.
My variable-length code is more compact i think. Only increases in bitlength (by 1) after all possible values are used up for that bitsize. This is Rice coding generalized, i think.
/*
Filename: ucodes.h (universal codes.)
Written by: Gerald Tamayo, 2009
*/
#include <stdio.h>
#include <stdlib.h>
#if !defined(_UCODES_)
#define _UCODES_
/* Unary Codes. */
#define put_unary(n) put_golomb((n),0)
#define get_unary() get_golomb(0)
/* Exponential Golomb coding */
#define put_xgolomb(n) put_vlcode((n), 0)
#define get_xgolomb() get_vlcode(0)
/* Elias-Gamma coding.
Note: don't pass a zero (0) to the encoding function: only n > 0 */
#define put_elias_gamma(n) put_xgolomb((n)-1)
#define get_elias_gamma() get_xgolomb()
/* Golomb Codes. */
void put_golomb( int n, int mfold );
int get_golomb( int mfold );
void put_vlcode( int n, int len );
int get_vlcode( int len );
#endif
I just use my put_vlcode() function for short codes. Last time i checked, this is related to Rice codes.
/*
Filename: ucodes.c (universal codes.)
Written by: Gerald Tamayo, 2009
*/
#include <stdio.h>
#include <stdlib.h>
#include "gtbitio.h"
#include "ucodes.h"
/* Golomb Codes.
We divide integer n by (1<<mfold), write the result as a
unary code, and then output the remainder as a binary number,
the bitlength of which is exactly the length of the unary_code-1.
In the implementation below, mfold is an exponent of two:
mfold = {0, 1, 2, ...} and (1<<mfold) is thus a power of two.
Each 1 bit of the unary code signifies a (1<<mfold) *part* of
integer n. In *exponential* Golomb coding, each 1 bit signifies
succeeding powers of 2. (We allow a length/mfold of 0 to encode
n as a plain unary code.)
*/
void put_golomb( int n, int mfold )
{
int i = n >> mfold;
while ( i-- ) {
put_ONE();
}
put_ZERO();
if ( mfold )
put_nbits( n%(1<<mfold), mfold );
}
int get_golomb( int mfold )
{
int n = 0;
while ( get_bit() ) n++;
n <<= mfold;
if ( mfold )
n += get_nbits(mfold);
return n;
}
/* The following variable-length encoding function can write
Elias-Gamma codes and Exponential-Golomb codes according
to the *len* parameter, which can be 0 to encode integer 0
as just 1 bit. */
void put_vlcode( int n, int len )
{
while ( n >= (1<<len) ){
put_ONE();
n -= (1<<len++);
}
put_ZERO();
if ( len ) put_nbits( n, len );
}
int get_vlcode( int len )
{
int n = 0;
while ( get_bit() ){
n += (1<<len++);
}
if ( len ) n += get_nbits(len);
return n;
}
Treat the number as a binary number (not decimal number) and transform it into a variable-length code.