Mind your bits, will you?

C# doesn’t provide Bit Fields like C++, and as far as I know the smallest data you can work with is a byte (8 bits). For most cases that’s fine, but sometimes you may want to micromanage every single bit of your memory, and although C# isn’t the most recommended language if you need to do that regularly, you can use bitwise operations to achieve more efficient memory usage, what can be especially useful if you plan to optimize for CPU caching which is limited to only a few KBs on L1.

In a game I’m working on I’ve recently replaced general purpose “structs” for extra object composed data with “packed bits”. In that case the usage was in a map composed of Tile structs which have a few fields like: TileType (byte), DynamicFlags (byte), and LightLevel (byte). Each Tile also contained an array of structs that I removed and used multi-purpose uints instead.

I’m using a pattern inspired by flyweight. The TileType field of each Tile struct represents an index of an array that holds classes containing block logic, and the methods in these classes use data stored in the uints of each struct. To make good use of the data stored there while still maintaining a ‘sane’ approach, I’m not storing more than a single system datum on each uint.

Let’s say you have a Tile representing water, so its TileType field contains the index of the single instance of the ‘Water : UpdatableTile’ class. When the map updating loop reach that tile, it checks if it’s updatable (bitwise flag mask) and passes the data stored in the uints to the ‘UpdateTile()’ function in the ‘Water’ class instance, and that function decides what to do with it. In the case of the water, I’m storing all the data I need in a single uint: 13 bits for the X position, 11 bits for the Y position, and 8 bits for the water level on that individual block. I’m considering using 16x+16y for the position and use another uint for the water level to keep things simpler. You can scale this pattern to unimaginable levels… for the ‘conveyor belt’ tiles for example, I’m using one uint for its position, and the other uints represent the objects on the belt (ID and position).

Especially for that approach, direct control over your bits is very useful, however, I couldn’t find a good library to pack data into bits, so I decided to code my own functions to do that:

using System;
class PackingBits
{
    static void Main(string[] args)
    {
        // say you have this data:
        byte byteA = 7;
        byte byteB = 5;
        ushort someNumber = 1500;

        // you pack that into an uint like this:
        byte[] packingFormat = {8, 8, 16};
        ushort[] dataToPack = { byteA, byteB, someNumber };
        uint packedData = PackBitFields(dataToPack, packingFormat);

        // print the value
        Console.Write("packed: ");
        foreach (ushort v in dataToPack) { Console.Write(v + ", "); }
        Console.WriteLine("into: "+packedData);

        //now you unpack the data back
        ushort[] unpackedData = GetBitFields(packedData, packingFormat);

        // print for confirmation (you may want to cast back)
        Console.Write("unpacked: ");
        foreach (ushort v in unpackedData) {Console.Write(v +  ", ");}
        Console.WriteLine();

        //#####################################
        //another example
        byte[] format2 = new byte[] {4,4,4,4,4,4,4,4};
        uint packedData2 = PackBitFields(new ushort[]{1,2,3,4,11,12,13,14}, format2);
        ushort[] unpackedData2 = GetBitFields(packedData2, format2);

        // print for confirmation - WHOAH! 8 numbers in a single UINT! (32-bit) :)
        Console.Write("unpacked: ");
        foreach (ushort v in unpackedData2) { Console.Write(v + ", "); }
        Console.WriteLine();

        //#####################################
        // here's a more useful example:
        uint packedColor = PackBitFields(new ushort[] { 31, 0, 0, 0, 63, 0 }, RGBRGB565565);
        var unpackedColor = GetBitFields(packedColor, RGBRGB565565);

        // RED AND GREEN in a uint
        Console.Write("unpacked: ");
        foreach (ushort v in unpackedColor) { Console.Write(v + ", "); }
        Console.WriteLine();

    }

    const int MaxBits = 32; // you may want to pass this and use generics to allow more or less bits
    static readonly byte[] RGBRGB565565 = { 5,6,5,5,6,5 }; // make some common formats like this

    public static uint PackBitFields(ushort[] values, byte[] bitFields)
    {
        uint retVal = values[0]; //we set the first value right away
        for (int f = 1; f < values.Length; f++)
        {
            retVal <<= bitFields[f]; //we shift the previous value
            retVal += values[f]; //and add our current value<span class="pl-c"> //on some processors | (pipe) will be faster here</span>
        }
        return retVal;
    }

    public static ushort[] GetBitFields(uint packedBits, byte[] bitFields)
    {
        int fields = bitFields.Length-1; // number of fields to unpack
        ushort[] retArr = new ushort[fields+1]; // init return array
        int curPos = 0; // current field bit position (start)
        int lastEnd; // position where last field ended
        for (int f = fields; f >= 0; f--) // loop from last
        {
            lastEnd = curPos; // we store where the last value ended
            curPos += bitFields[f]; // we get where the current value starts
            int leftShift = MaxBits - curPos; // we figure how much left shift we gotta apply for the other numbers to overflow into oblivion
            retArr[f] = (ushort)((packedBits << leftShift) >> leftShift + lastEnd); // we do magic
        }
        return retArr;
    }
}

using System;

class PackingBits

{

static void Main(string[] args)

{

// say you have this data:

byte byteA = 7;

byte byteB = 5;

ushort someNumber = 1500;

// you pack that into an uint like this:

byte[] packingFormat = {8, 8, 16};

ushort[] dataToPack = { byteA, byteB, someNumber };

uint packedData = PackBitFields(dataToPack, packingFormat);

// print the value

Console.Write("packed: ");

foreach (ushort v in dataToPack) { Console.Write(v + ", "); }

Console.WriteLine("into: "+packedData);

//now you unpack the data back

ushort[] unpackedData = GetBitFields(packedData, packingFormat);

// print for confirmation (you may want to cast back)

Console.Write("unpacked: ");

foreach (ushort v in unpackedData) {Console.Write(v + ", ");}

Console.WriteLine();

//#####################################

//another example

byte[] format2 = new byte[] {4,4,4,4,4,4,4,4};

uint packedData2 = PackBitFields(new ushort[]{1,2,3,4,11,12,13,14}, format2);

ushort[] unpackedData2 = GetBitFields(packedData2, format2);

// print for confirmation - WHOAH! 8 numbers in a single UINT! (32-bit) :)

Console.Write("unpacked: ");

foreach (ushort v in unpackedData2) { Console.Write(v + ", "); }

Console.WriteLine();

//#####################################

// here's a more useful example:

uint packedColor = PackBitFields(new ushort[] { 31, 0, 0, 0, 63, 0 }, RGBRGB565565);

var unpackedColor = GetBitFields(packedColor, RGBRGB565565);

// RED AND GREEN in a uint

Console.Write("unpacked: ");

foreach (ushort v in unpackedColor) { Console.Write(v + ", "); }

Console.WriteLine();

}

const int MaxBits = 32; // you may want to pass this and use generics to allow more or less bits

static readonly byte[] RGBRGB565565 = { 5,6,5,5,6,5 }; // make some common formats like this

public static uint PackBitFields(ushort[] values, byte[] bitFields)

{

uint retVal = values[0]; //we set the first value right away

for (int f = 1; f < values.Length; f++)

{

retVal <<= bitFields[f]; //we shift the previous value

retVal += values[f]; //and add our current value<span class="pl-c"> //on some processors | (pipe) will be faster here</span>

}

return retVal;

}

public static ushort[] GetBitFields(uint packedBits, byte[] bitFields)

{

int fields = bitFields.Length-1; // number of fields to unpack

ushort[] retArr = new ushort[fields+1]; // init return array

int curPos = 0; // current field bit position (start)

int lastEnd; // position where last field ended

for (int f = fields; f >= 0; f--) // loop from last

{

lastEnd = curPos; // we store where the last value ended

curPos += bitFields[f]; // we get where the current value starts

int leftShift = MaxBits - curPos; // we figure how much left shift we gotta apply for the other numbers to overflow into oblivion

retArr[f] = (ushort)((packedBits << leftShift) >> leftShift + lastEnd); // we do magic

}

return retArr;

}

Gist Link

As you can see usage is very simple, and I guess you can’t go much more efficient than that. One element of the packing format isn’t used, so it’s useless data flowing around what’s not good for micro optimization, but it keeps things easier to understand and it’s pretty much negligible. Please note that there’s no checking whatsoever, so if the data you’re storing overflows the max number your bit count would allow, it will affect the adjacent numbers. A quick fix to that is using a mask, but that’s less efficient and not necessary if you know your sizes.

On a future article I’m going to show how I’m using bitwise to efficiently perform flag operations, like determining if an object contains multiple flags in a single bitwise operation, basically like this:

// object flags 1 = 1010101010101010 //each bit is a flag
ushort f1 = 43690;

// object flags 2 = 0001111111111100
ushort f2 = 8188;

// flags to check = 0000011110000000
ushort mask = 1920;

Console.WriteLine((f1 & mask) == mask);
Console.WriteLine((f2 & mask) == mask);

// object flags 1 = 1010101010101010 //each bit is a flag

ushort f1 = 43690;

// object flags 2 = 0001111111111100

ushort f2 = 8188;

// flags to check = 0000011110000000

ushort mask = 1920;

Console.WriteLine((f1 & mask) == mask);

Console.WriteLine((f2 & mask) == mask);

Related

3 thoughts on “Mind your bits, will you?”

Leave a Reply Cancel reply