I am working on an implementation of the minimalist compression method. The method is based on context modeling, followed by a simple entropy coder (Golomb-Rice coder). The context model uses a single previous byte in the uncompressed symbol stream to predict the next byte. At the moment, my implementation works quite well. However, I wonder if it is possible to make it faster or more concise. Basically, any suggestions for improvement are welcome.
Prerequisites
The implementation uses the following data structure:
struct context {
size_t freq[256]; /* char -> frequency */
unsigned char sorted[256]; /* index -> char */
unsigned char order[256]; /* char -> index */
} table[256];
The functions bio_open
, bio_write_gr
, bio_read_gr
, and bio_close
implement the entropy (Golomb-Rice) coding.
Moreover, the function void update_model(unsigned char delta)
updates the entropy model according to the newly encoded byte delta
(not the subject of this review).
Code
I use several two auxiliary functions:
static void swap_symbols(struct context *context, unsigned char c, unsigned char d)
{
assert(context != NULL);
unsigned char ic = context->order[c];
unsigned char id = context->order[d];
assert(context->sorted[ic] == c);
assert(context->sorted[id] == d);
context->sorted[ic] = d;
context->sorted[id] = c;
context->order[c] = id;
context->order[d] = ic;
}
static void increment_frequency(struct context *context, unsigned char c)
{
assert(context != NULL);
unsigned char ic = context->order[c];
size_t freq_c = ++(context->freq[c]);
unsigned char *pd;
for (pd = context->sorted + ic - 1; pd >= context->sorted; --pd) {
if (freq_c <= context->freq[*pd]) {
break;
}
}
unsigned char d = *(pd + 1);
if (c != d) {
swap_symbols(context, c, d);
}
}
The main entry functions are defined as follows:
void init()
{
opt_k = 3;
for (int p = 0; p < 256; ++p) {
for (int i = 0; i < 256; ++i) {
table[p].sorted[i] = i;
table[p].freq[i] = 0;
table[p].order[i] = i;
}
}
}
void *compress(void *iptr, size_t isize, void *optr)
{
struct bio bio;
unsigned char *end = (unsigned char *)iptr + isize;
struct context *context = table + 0;
bio_open(&bio, optr, BIO_MODE_WRITE);
for (unsigned char *iptrc = iptr; iptrc < end; ++iptrc) {
unsigned char c = *iptrc;
/* get index */
unsigned char d = context->order[c];
bio_write_gr(&bio, opt_k, (uint32_t)d);
assert(c == context->sorted[d]);
/* update context model */
increment_frequency(context, c);
/* update Golomb-Rice model */
update_model(d);
context = table + c;
}
/* EOF symbol */
bio_write_gr(&bio, opt_k, 256);
bio_close(&bio, BIO_MODE_WRITE);
return bio.ptr;
}
void *decompress(void *iptr, void *optr)
{
struct bio bio;
struct context *context = table + 0;
bio_open(&bio, iptr, BIO_MODE_READ);
unsigned char *optrc = optr;
for (;; ++optrc) {
uint32_t d = bio_read_gr(&bio, opt_k);
if (d == 256) {
break;
}
assert(d < 256);
unsigned char c = context->sorted[d];
*optrc = c;
increment_frequency(context, c);
update_model(d);
context = table + c;
}
bio_close(&bio, BIO_MODE_READ);
return optrc;
}