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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
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; } } |
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:
1 2 3 4 5 6 7 8 9 10 11 |
// 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); |
3 thoughts on “Mind your bits, will you?”