Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Real computer scientists like having a computer on their desk, else how could they read their mail?


computers / comp.compression / My Universal Codes Implementation

SubjectAuthor
o My Universal Codes ImplementationGerald Tamayo

1
Subject: My Universal Codes Implementation
From: Gerald Tamayo
Newsgroups: comp.compression
Date: Wed, 1 Jul 2020 11:08 UTC
X-Received: by 2002:a37:bd06:: with SMTP id n6mr7744741qkf.344.1593601715977;
Wed, 01 Jul 2020 04:08:35 -0700 (PDT)
X-Received: by 2002:ac8:41c7:: with SMTP id o7mr25139959qtm.257.1593601715813;
Wed, 01 Jul 2020 04:08:35 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!peer01.ams4!peer.am4.highwinds-media.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.compression
Date: Wed, 1 Jul 2020 04:08:35 -0700 (PDT)
Complaints-To: groups-abuse@google.com
Injection-Info: google-groups.googlegroups.com; posting-host=2001:4450:8329:3500:9574:ff11:40fa:f490;
posting-account=x4y9KQoAAAAgtc4BPWDOKB7Ls5RAV5pf
NNTP-Posting-Host: 2001:4450:8329:3500:9574:ff11:40fa:f490
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <032899de-4e2e-4f3b-969c-8b82b9ff6c03o@googlegroups.com>
Subject: My Universal Codes Implementation
From: com...@gmail.com (Gerald Tamayo)
Injection-Date: Wed, 01 Jul 2020 11:08:35 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 4130
X-Received-Body-CRC: 3132030737
View all headers
When i tried to implement universal codes again in 2009, i saw some Wikipedia descriptions pointing to a decimal number, not binary, to convert to binary. So my implementation is of course done the natural way: using binary numbers, which is more compact, i think?

[CODE]
/*
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 );

/* 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 );
int  get_vlcode( int len );

#endif
[/CODE]


I just use my put_vlcode() function for short non entropy codes. Last time i checked, this is related to Rice codes.


[CODE]
/*
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;
}
[/CODE]


1
rocksolid light 0.7.2
clearneti2ptor