Welcome to MSDN Blogs Sign in | Join | Help

Network compression: arithmetic encoding

Arithmetic encoding is one of those obscure tools that is rarely used, but every now and then is the only thing that can do the job. It's the oddly sized Allen-key of network data compression.

Arithmetic encoding is cool because not many people have heard of it, and at first glance it doesn't seem like it ought to work at all. A great way to impress girls at parties!

Consider this data:

    enum Species
    {
        Camel,
        Cat,
        Caterpillar,
        Cheetah,
        Chimpanzee,
        Cobra,
        Cormorant,
        Cougar,
        Coyote,
        Crab,
        Crocodile,
    }

    Species animalA;
    Species animalB;
    bool whoWon;

(yes, we're making a game that will finally answer the eternal question of young males the world over, "who would win in a fight between a cougar and a crocodile?")

There are 11 possible species, so the Species enum requires 4 bits. Along with the boolean whoWon value, this is too much to be bitpacked into a single byte.

But hang on a moment...

With 11 possible values for animalA, and 11 possible values for animalB, and 2 possible values for whoWon, that only gives 11 * 11 * 2 possible permutations, which is 242. Seems like this ought to fit into a byte, neh?

The problem with bitpacking this data is the wastefulness of using 4 bits for each species, which gives us 16 possible values when we really only needed 11. Wouldn't it be nice if we could use a fractional number of bits per field?

If we replace the bit shifting operations from my previous post with multiplication, division, and modulus calculations, we can do exactly that.

Pack the data like so:

    void ArithmeticEncode(ref int encoded, int valueRange, int value)
    {
        encoded *= valueRange;
        encoded += value;
    }

    int encoded = 0;

    ArithmeticEncode(ref encoded, 11, (int)animalA);
    ArithmeticEncode(ref encoded, 11, (int)animalB);
    ArithmeticEncode(ref encoded, 2, whoWon ? 1 : 0);

    packetWriter.Write((byte)encoded);

And to read it back:

    int ArithmeticDecode(ref int bitfield, int valueRange)
    {
        int value = bitfield % valueRange;
        bitfield /= valueRange;
        return value;
    }

    int encoded = packetReader.ReadByte();

    whoWon = ArithmeticDecode(ref encoded, 2) != 0;
    animalA = (Species)ArithmeticDecode(ref encoded, 11);
    animalB = (Species)ArithmeticDecode(ref encoded, 11);

Cool, huh?

Published Sunday, December 30, 2007 11:00 AM by ShawnHargreaves

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

Thursday, October 01, 2009 4:50 AM by Silvermax

# re: Network compression: arithmetic encoding

Is the order right? i mean, if you write AnimalA, AnimalB, bool, should it be read as Bool, AnimalB and AnimalA? Thnx

Thursday, October 01, 2009 4:53 AM by Silvermax

# re: Network compression: arithmetic encoding

The value have to be subtracted from the bitfield, isnt it?

int ArithmeticDecode(ref int bitfield, int valueRange)

       {

           int value = bitfield % valueRange;

           bitfield -= value;

           bitfield /= valueRange;

           return value;

       }

Thursday, October 01, 2009 11:42 AM by ShawnHargreaves

# re: Network compression: arithmetic encoding

You don't need a subtraction, although it won't hurt: this is effectively a no-op. The division operator takes care of removing the unwanted fractional bits. Remember that integer division rounds down...

Leave a Comment

(required) 
required 
(required) 

  
Enter Code Here: Required
 
Page view tracker