Extended Elias Gamma Code

[Einar Saukas]

When I was designing data compressors ZX0 and ZX1, I created all kinds of variations for Elias Gamma Code. Unfortunately none of them helped to improve my compressor, so I ended up using the original Elias Gamma Code anyway (except interlaced).

I didn't think anyone else would be interested in these variants, until [mention]Joefish[/mention] posted this comment yesterday:

You could also experiment with re-proportioning the Elias-Gamma encoding so that it has more data bits to each extension bit.

This was exactly one of the variants that I coded and later discarded. Although it didn't help me, perhaps it could be useful for someone else?

In standard Elias Gamma Code, there's a 1:1 proportion between data and control bits, as represented below:

Code: Select all

Numbers      Bits  Elias Gamma Code                 Interlaced Elias Gamma Code
1              1   1                                1
2-3            3   01x                              0x1
4-7            5   001xx                            0x0x1
8-15           7   0001xxx                          0x0x0x1
16-31          9   00001xxxx                        0x0x0x0x1
32-63         11   000001xxxxx                      0x0x0x0x0x1
64-127        13   0000001xxxxxx                    0x0x0x0x0x0x1
128-255       15   00000001xxxxxxx                  0x0x0x0x0x0x0x1
256-511       17   000000001xxxxxxxx                0x0x0x0x0x0x0x0x1
512-1023      19   0000000001xxxxxxxxx              0x0x0x0x0x0x0x0x0x1
1024-2047     21   00000000001xxxxxxxxxx            0x0x0x0x0x0x0x0x0x0x1
2048-4095     23   000000000001xxxxxxxxxxx          0x0x0x0x0x0x0x0x0x0x0x1
4096-8191     25   0000000000001xxxxxxxxxxxx        0x0x0x0x0x0x0x0x0x0x0x0x1
8192-16383    27   00000000000001xxxxxxxxxxxxx      0x0x0x0x0x0x0x0x0x0x0x0x0x1
16384-32767   29   000000000000001xxxxxxxxxxxxxx    0x0x0x0x0x0x0x0x0x0x0x0x0x0x1
32768-65535   31   0000000000000001xxxxxxxxxxxxxxx  0x0x0x0x0x0x0x0x0x0x0x0x0x0x0x1

I have called "Extended Elias Gamma Code" when this proportion is different.

For instance, there's a 2:1 proportion between data and control bits in "Extended-2 Elias Gamma Code":

Code: Select all

Numbers      Bits  Extended-2 Elias Gamma Code      Interlaced Extended-2 Elias Gamma Code
1              1   1                                1
2-5            4   01xx                             0xx1
6-21           7   001xxxx                          0xx0xx1
22-85         10   0001xxxxxx                       0xx0xx0xx1
86-341        13   00001xxxxxxxx                    0xx0xx0xx0xx1
342-1365      16   000001xxxxxxxxxx                 0xx0xx0xx0xx0xx1
1366-5461     19   0000001xxxxxxxxxxxx              0xx0xx0xx0xx0xx0xx1
5462-21845    22   00000001xxxxxxxxxxxxxx           0xx0xx0xx0xx0xx0xx0xx1
21846-87381   25   000000001xxxxxxxxxxxxxxxx        0xx0xx0xx0xx0xx0xx0xx0xx1

Similarly there's a 3:1 proportion between data and control bits in "Extended-3 Elias Gamma Code":

Code: Select all

Numbers      Bits  Extended-3 Elias Gamma Code      Interlaced Extended-3 Elias Gamma Code
1              1   1                                1
2-9            5   01xxx                            0xxx1
10-73          9   001xxxxxx                        0xxx0xxx1
74-585        13   0001xxxxxxxxx                    0xxx0xxx0xxx1
586-4681      17   00001xxxxxxxxxxxx                0xxx0xxx0xxx0xxx1
4682-37449    21   000001xxxxxxxxxxxxxxx            0xxx0xxx0xxx0xxx0xxx1
37450-299593  25   0000001xxxxxxxxxxxxxxxxxx        0xxx0xxx0xxx0xxx0xxx0xxx1

The implementation is non-intuitive but quite efficient. I will provide it in my next post...

[Einar Saukas]

Here's my code to convert any positive number to Extended Elias Gamma Code:

Code: Select all

void write_interlaced_extended_elias_gamma(int value, int factor) {
    int n = 1;
    while (value > n) {
        value -= n;
        n <<= factor;
    }
    value--;
    while (n > 1) {
        write_bit(0);
        for (int i = 0; i < factor; i++) {
            n >>= 1;
            write_bit(value & n ? 1 : 0);
        }
    }
    write_bit(1);
}

A simpler code, that just counts how many bits it will take:

Code: Select all

int count_interlaced_extended_elias_gamma(int value, int factor) {
    int bits = 1;
    int n = 1;
    while (value > n) {
        value -= n;
        n <<= factor;
        bits += factor+1;
    }
    return bits;
}

Luckily decoding from Extended Elias Gamma Code to a positive number is much easier:

Code: Select all

int read_interlaced_extended_elias_gamma(int factor) {
    int value = 0;
    while (!read_bit()) {
        for (int i = 0; i < factor; i++) {
            value = value << 1 | read_bit();
        }
        value++;
    }
    return value+1;
}

This is actually a generalization of the usual Elias Gamma Code implementation. You can use factor=1 for standard Elias Gamma Code, factor=2 for Extended-2 Elias Gamma Code, factor=3 for Extended-3 Elias Gamma Code, etc.

[Einar Saukas]

Finally here's a generic Z80 implementation to decode a sequence of Extended Elias Gamma Code bits to a positive number:

Code: Select all

    ld bc, 0
    call read_elias
    ...
loop:
REPT factor
    call get_bit
    rl c
    rl b
ENDR
    inc bc
read_elias:
    call get_bit
    jr nc, loop
    inc bc
    ret

[Joefish]

If your decoding is partially unwrapped then you can have different scaling factors combined in one number.

In your typical back-references (Einar), you used an exaggerated form of this - you start with 7 bits of data with an eighth 'extend' bit for convenience, as then most data fetches are for a whole byte.

What works best will depend on the distribution of lengths or back-references in the data you're compressing. At one point I had a scheme where there were 5 initial data bits, and each extension bit was worth three more data bits. It was quite efficient in some cases, but needed a very specific decoder, which is then longer.

[Einar Saukas]

If your decoding is partially unwrapped then you can have different scaling factors combined in one number.

In your typical back-references (Einar), you used an exaggerated form of this - you start with 7 bits of data with an eighth 'extend' bit for convenience, as then most data fetches are for a whole byte.

What works best will depend on the distribution of lengths or back-references in the data you're compressing. At one point I had a scheme where there were 5 initial data bits, and each extension bit was worth three more data bits. It was quite efficient in some cases, but needed a very specific decoder, which is then longer.

I think I have tried all possible combinations

These are my results for ZX0 with all offsets stored using "5 bits + Extended-3 Elias Gamma Code", all lengths stored using standard Elias Gamma Code:

Code: Select all

Calgary     107313
Canterbury   28806
Graphics    164601
Music        58414
Misc        247098

TOTAL       606232

[Einar Saukas]

I expanded this idea even further and turned into a full project, in case it may be useful to someone:

https://github.com/einar-saukas/Zeta-Xi-Code

[calatorius]

could me say me which is the advantage of using interlaced mode vs normal mode.
Thanks

[Joefish]

I assume 'interlaced' is when the data stream goes: data bit - flag bit - data bit - flag bit - data bit
Whereas normal mode is when you get all the flag bits first, then the data bits come afterwards.
It just depends which you think you can decode the fastest, depending on the way you write your unpacker.

[introspec]

There are two advantages of using the interlaced mode.

1. If you are reading all the flag variables first, you need to count them. First, this requires allocating a count register, which could have been used for something else. Second, this requires the reading the flag bits while incrementing the count register, and then reading the data bits while decrementing the count register. With interlaced code on the other hand you can read the flag and, depending on its value, grab another data bit. No time is wasted counting flag bits, effectively twice.

2. More subtly, in a compressor like ZX0 the number of bits in every compressor command is always even. This means that with interlaced code you don't need to check if your bit reservoir register is empty half-the-time. This would not apply to non-interlaced code, as the number of flag bits can be both even and odd.

[calatorius]

Very clear,
Thanks very much

[ParadigmShifter]

This seems like a good scheme for very fast compression on a data stream which arrives in real time and you need to compress and immediately resend it i.e. you cannot store the entire data stream and then compress it.

Otherwise if you can run analysis on the data before you compress it I think those methods will beat this method in nearly all cases. Even a contrived case (data stream is all 1 symbol - best case for this method) would be beaten by simple RLE. Even if you don't analyse the data a sliding window method like LZW is probably better.

Of course in a general purpose compressor you can try a bunch of methods and use the decoder which matches that.