Network compression: bitfields

Network compression: bitfields

Rate This
  • Comments 3

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:

  • Shuffles existing bits to the left (using the << operator) to make room for new ones
  • Merges new bits into the existing value (using the | operator)

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:

  • Extracts a set of bits from the bottom of the bitfield (using the & operator)
  • Shuffles remaining bits to the right (using the >> operator) to fill the gap

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.

  • The best so far in the series. It has my five!

  • wow man :-) this is mad crazy yo

  • This shows one of the few drawbacks of C#.

    In C and C++ you can use bitfields in structs something like:

    [code]

    struct Animal

    {

     bool isAlive: 1;    

     bool isFiring: 1;    

     char Species: 4;

    };

    [/code]

    But in C# to get similar functionality you would have to create a class that handles things behind the scenes.  Probably a safer way to go.

Page 1 of 1 (3 items)
Leave a Comment
  • Please add 5 and 1 and type the answer here:
  • Post