4
\$\begingroup\$

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;
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Symbolic Constants

This code could use some symbolic constants:

struct context {
    size_t freq[256];          /* char -> frequency */
    unsigned char sorted[256]; /* index -> char */
    unsigned char order[256];  /* char -> index */
} table[256];

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;
        }
    }
}

The use of symbolic constants would make this code easier to write and maintain. For example if there was a symbolic constant for 256 the size of the table and the loop controls could be changed with a single line edit.

Global Variables

In the function init() above, it is obvious that global variables are being used, table is on global variable and opt_k is another global variable.

Global variables are generally considered a bad programming practice, they make the code hard to write, debug and maintain. They also make it very easy to introduce bugs.

In the C programming language if the program consists of multiple files, it is possible that global variables can cause the program not to link if they are declared in multiple files.

Using assert() in C

If at some point the code is going to be compiled for release using the optimizing feature of the compiler, then the assert() statements will be optimized away. If the error checking provided by the asserts is required it will be better to replace the asserts with if statements.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ OP is explicitly using any unsigned char as an index. A good substitute for 256 would be size_t freq[UCHAR_MAX +1u]; \$\endgroup\$
    – chux
    Commented Feb 13, 2020 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.