Network compression: bitfields

Originally posted to Shawn Hargreaves Blog on MSDN, Friday, December 28, 2007

Bitfields are just like this most totally awesome old-skool way of packing data, dude! C# programmers rarely have an excuse to mess with such things, but network packet compression offers an excuse par excellence, so let us mess away.

A byte is 8 bits. An int is 32 bits. But what if our data values are not multiples of 8 or 32 bits? For instance what if we had this data to send over the network:

    bool isAlive;
bool isFiring;

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

packetWriter.Write(isAlive);
packetWriter.Write(isFiring);
packetWriter.Write((byte)species);

That is three bytes, but we shouldn't need three bytes here. Each boolean value only actually requires a single bit, and because there are only 11 possible species, that only requires 4 bits.

If we figure out the minimal number of bits needed for each field, we can use bit shifting to pack several fields into a single byte or int. In effect, we are making up our own integer types that can have whatever number of bits we like, then packing these into the fixed size 8 or 32 bit integers supported by the CPU hardware and C# language.

For instance, the three bytes shown above can be combined into a single byte (with two bits left over for other data) as follows:

    void AddToBitfield(ref int bitfield, int bitCount, int value)
{
bitfield <<= bitCount;
bitfield |= value;
}

int bitfield = 0;

AddToBitfield(ref bitfield, 1, isAlive ? 1 : 0);
AddToBitfield(ref bitfield, 1, isFiring ? 1 : 0);
AddToBitfield(ref bitfield, 4, (int)species);

packetWriter.Write((byte)bitfield);

The AddToBitfield helper does two things:

To read bitfield data, we reverse the process:

    int ReadFromBitfield(ref int bitfield, int bitCount)
{
int value = bitfield & ((1 << bitCount) - 1);
bitfield >>= bitCount;
return value;
}

int bitfield = packetReader.ReadByte();

species = (Species)ReadFromBitfield(ref bitfield, 4);
isFiring = ReadFromBitfield(ref bitfield, 1) != 0;
isAlive = ReadFromBitfield(ref bitfield, 1) != 0;

Note how the three fields (isAlive, isFiring, and species) must be read from the bitfield in the opposite order to how they were written.

The ReadFromBitfield helper does the exact opposite of AddToBitfield:

Bitfields are especially suitable for packing boolean and enum values, but they can be used with any numeric data if you quantize it into a small enough range first.

Blog index   -   Back to my homepage