BitFields and BitStrings in .NET

• Download BitString.zip - 66.7 KB

Introduction

This article will describe a .NET library that implements classes that represents a BitString and a BitField.  A BitString is a string of 1's and 0's and is represented internally as an array of 32-bit unsigned integers.  As the BitString grows, it fills each array element from the left (Most Significant Bit) to the right (Least Significant Bit) and flows into the next array element.

For example, a BitString with 33 1's is represented internally by two 32-bit unsigned integers as shown below:

BitStrings can be useful for bit manipulation.

A BitField is just a BitString with named fields/regions.  This is implemented by an internal dictionary that associates the name of the field/region with its offset and length within the BitString.  This allows us to access any field/region of the BitString by name.

Background

Recently, while converting some C++ code to C#, I encountered the use of packed structures and bit fields and was surprised that C# did not offer the same feature.  I had to translate the original C++ code's use of bit fields into non-intuitive masking and bit shifting operations in C#.

I decided to write a C# library that makes any such code conversions easier and more intuitive.  The result is a library with 2 main classes:  BitString and BitField.

A Quick Preview

Before we describe the two classes, let's take a quick preview of what you can do with the BitField class.  A use case for the BitField class is the following:

Say you need to create and read a binary file with a custom format.  Let's say this file consists of 12 records where each record consists of 5 bytes.  Hence, each record is 40 bits long.  Suppose each record has the following layout:

Layout of Binary File Record

Field Name	Offset (0-based)	Bit Length
Light1	0	1
Light2	1	1
Fan1	2	1
Fan2	3	1
ErrorCode	4	12
StatusCode	16	4
Reserved	20	9
Counter	29	11

We can define the file's record as a BitField.  The code to set up the record's layout using a BitField is given below:

            // Define a BitField structure of 40-bits (5 Bytes)
            BitField bf = new BitField();
            bf.AddField("Light1", 1);
            bf.AddField("Light2", 1);
            bf.AddField("Fan1", 1);
            bf.AddField("Fan2", 1);
            bf.AddField("ErrorCode", 12);
            bf.AddField("StatusCode", 4);
            bf.AddField("Reserved", 9);
            bf.AddField("Counter", 11);

            // After defining structure, we must initialize it.  This
            // call will initialize the 40-bit BitString to all 0's
            bf.InitBitField();

We can easily set the value of any field/region within the BitField with the following code:

            // Initialize some fields to some value.  If we don't
            // explicitly set a value, the field is all 0's from the
            // earlier call to InitBitField().  Note we can use
            // strings or integers for assignment.
            bf["Light1"] = 1;
            bf["Fan2"] = "1";
            bf["ErrorCode"] = "111100001111";
            bf["StatusCode"] = 2;

Now, we can write the records to a file by the following code:

// Create the binary file name
string fn = Path.GetTempFileName();

// Write out 12 records where each record is represented by
// a BitField
using (FileStream fs = new FileStream(fn, FileMode.Append))
{
    for (int i = 0; i < 12; i++)
    {
        // Convert the BitField into a byte array
        byte[] temp = bf.GetBytes();

        for (int j = 0; j < temp.Length; j++)
        {
            // Write out the BitField/record
            fs.WriteByte(temp[j]);
        }

        // Increment the BitField's Counter value by 1
        // using the BitString's increment operator
        ++bf["Counter"];
    }
}

We can also use the same BitField object to read the binary file back in.  To do this, we just read in a record from the file and intialize the BitField (by calling InitBitField()) with it.  We can now easily access each individual field from the record.

            // Now we want to read in the binary file that we just created!
            List<string> report = new List<string>();

            using (BinaryReader BinReader = new BinaryReader(File.Open(fn, FileMode.Open)))
            {
                for (int i = 0; i < 12; i++)
                {
                    // Read each 5-byte (40-bit) record into an array of bytes
                    byte[] buffer = BinReader.ReadBytes(5);

                    // Initialize the BitField with the record from the binary file
                    bf.InitBitField(buffer);

                    // Extract each field for display in a report
                    string temp = "BitField = " + bf.ToString() + Environment.NewLine;
                    temp = temp + "Light1 = " + bf["Light1"].ToString();
                    temp = temp + ", Light2 = " + bf["Light2"].ToString();
                    temp = temp + ", Fan1 = " + bf["Fan1"].ToString();
                    temp = temp + ", Fan2 = " + bf["Fan2"].ToString() + Environment.NewLine;
                    temp = temp + "ErrorCode = " + bf["ErrorCode"].ToString();
                    temp = temp + ", StatusCode = " + bf["StatusCode"].ToString();
                    temp = temp + ", Reserved = " + bf["Reserved"].ToString();
                    temp = temp + ", Counter = " + bf["Counter"].ToString();
                    temp = temp + Environment.NewLine + Environment.NewLine;

                    report.Add(temp);
                }
            }

If we print out the contents of report, it would look like:

BitField = 1001111100001111001000000000000000000000
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000000

BitField = 1001111100001111001000000000000000000001
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000001

BitField = 1001111100001111001000000000000000000010
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000010

BitField = 1001111100001111001000000000000000000011
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000011

BitField = 1001111100001111001000000000000000000100
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000100

BitField = 1001111100001111001000000000000000000101
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000101

BitField = 1001111100001111001000000000000000000110
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000110

BitField = 1001111100001111001000000000000000000111
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000000111

BitField = 1001111100001111001000000000000000001000
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000001000

BitField = 1001111100001111001000000000000000001001
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000001001

BitField = 1001111100001111001000000000000000001010
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 00000001010

BitField = 1001111100001111001000000000000000001011
Light1 = 1, Light2 = 0, Fan1 = 0, Fan2 = 1
ErrorCode = 111100001111, StatusCode = 0010, Reserved = 000000000, Counter = 0000000101

BitString Requirements

The BitString class is the workhorse of the two classes in the library.  As mentioned earlier, BitStrings are strings of 1's and 0's.  For example, the following is a BitString with 4 bits:

1011

During the design, there were specific features I wanted the BitString class to support.  I wanted the BitString class to support most of the normal operations that people would expect to be able to do with BitStrings.

I wanted to be able to concatenate two BitStrings:

0101 + 111100 = 0101111100

I wanted to be able to perform the usual bitwise operations between two BitStrings:

0101 AND 1111 = 0101

0101 OR 1111 = 1111

0101 XOR 1111 = 1010

If the BitStrings are of unequal length, then the shorter one should be padded on the right with either 1's or 0's so that the resultant BitString has the appropriate bits for the desired operation where the two BitStrings match and the remaining bits matching the longer BitString:

010 AND 101111101 = 000111101

010 OR 101111101 = 111111101

010 XOR 101111101 = 111111101

I wanted to be able to flip all the bits in a BitString:

0101 => 1010 (Flip)

I wanted to be able to reverse the bits in a BitStrings:

111001 => 100111 (Reverse)

I wanted to be able to increment/decrement BitStrings as if their bits represented unsigned integers:

0111 => 1000 (Increment)

1000 => 0111 (Decrement)

I wanted to be able to convert a BitString into its signed/unsigned integer interpretation:

1000 => 8 (Unsigned integer)

1000 => -8 (2's Complement Signed integer)

I wanted to be able to subset a BitString:

111010000 => 010 (Subset a BitString from location 3 to location 5)

I wanted to be able to set/clear individual bits in a BitString.

111000 => 101000 (Clear bit 1)

111000 => 111010 (Set bit 4)

Finally, I wanted to be able to handle BitStrings of almost any length.  For this requirement, I wanted a BitString to be represented internally by an array of unsigned 32-bit integers so the BitString 101011110101 would be stored internally as

uint[0] = 10101111010100000000000000000000

I wanted the BitString to be filled left justified into each array element and as the BitString grows, it should overflow into the next array element.  So, a BitString with 33 bits of all 1's would be stored as

uint[0] = 11111111111111111111111111111111

uint[1] = 10000000000000000000000000000000

I wanted to be able to get the byte array representation of the internal buffer so the array of uints above will be returned as the following array of bytes

byte[0] = 11111111

byte[1] = 11111111

byte[2] = 11111111

byte[3] = 11111111

byte[4] = 10000000

The byte array representation would allow us to easily write the raw bits of the BitString to a stream.

BitField Requirements

A BitField is just a BitString with named fields/regions.  This means I wanted to be able to associate a group of contiguous bits in a BitString with a name.  The requirements for a BitField are simple.

• I wanted a way to give a group of contiguous bits in a BitString a unique name.
• I wanted to be able to refer to any such group by its unique name.

Class Design

The class diagram of the library is shown above.  The two main classes in this library are the BitString and BitField class.  Most of the work is done by the BitString class.  The BitField class contains a BitString object (m_BitString) and a dictionary (m_Fields) that maps the name of a field/region with the location and length of that region within the BitString.  The dictionary gives the ability to access any named field/region within the BitString.

Using the code

To use the library in your code, just add a reference to the library (BitString.dll) in your project and add a using statement for the namespace "GCore".  You should now be able to use the BitString and BitField class in your project.

The following is a simple program that shows how to use the BitString class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using GCore;

namespace DemoConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            // Instantiating a BitString using a regular string of 1's and 0's
            String bits1 = "101010";
            BitString bs1 = new BitString(bits1);

            // bs1 = 101010
            Console.WriteLine("bs1 = " + bs1.ToString());

            // You can also just use assignment with a string value to set the BitString
            bs1 = "11110000";
            Console.WriteLine("bs1 = " + bs1.ToString());

            // Instantiating a BitString using another BitString
            BitString bs2 = new BitString(bs1);

            // bs2 = 11110000
            Console.WriteLine("bs2 = " + bs2.ToString());

            // We can flip all the bits
            bs2.Flip();

            // bs2 = 00001111
            Console.WriteLine("bs2 (flipped) = " + bs2.ToString());

            // You can bitwise XOR two BitStrings
            BitString temp = bs1 ^ bs2;

            // bs1 ^ bs2 = 11111111
            Console.WriteLine("bs1 ^ bs2 = " + temp.ToString());

            // You can concatenate two BitStrings
            BitString bs3 = bs1 + bs2;

            // bs3 (bs1 + bs2) = 1111000000001111
            Console.WriteLine("bs3 (bs1 + bs2) = " + bs3.ToString());

            // Instantiating a BitString using an array of bytes
            byte[] seed = new byte[2];
            seed[0] = 0xFF;
            seed[1] = 0xAA;
            bs3 = new BitString(seed);

            // bs3 = 1111111110101010
            Console.WriteLine("bs3 = " + bs3.ToString());

            // You can reverse a BitString
            bs3.Reverse();

            // bs3 = 0101010111111111
            Console.WriteLine("bs3 (reverse) = " + bs3.ToString());

            // Setting a BitString's value by using a integer
            BitString bs4 = 4;

            // bs4 = 0000000000000000000000000100
            Console.WriteLine("bs4 = " + bs4.ToString());

            // You can subset a BitString
            BitString bs5 = bs4[29, 3];

            // bs5 = 100
            Console.WriteLine("bs5 = " + bs5.ToString());

            // You can increment a BitString
            ++bs5;

            // bs5 = 101
            Console.WriteLine("++bs5 = " + bs5.ToString());

            // Pause and wait for key stroke to end
            Console.ReadKey();
        }
    }
}

Visual Studio Solution

I've included the Visual Studio 2015 Solution of the library in this article.  The solutions consists of 4 projects:

1. BitString Project (this project is the BitString/BitField library)
2. BitString Test Project (this project contains unit tests for the library)
3. Demo Project (this project contains a little demo that allows you to interact with BitStrings and see its internal properties)
4. DemoConsole Project (this project contains the simple console program for the BitString shown earlier)

The Demo project presents a GUI that allows you to play around with BitStrings and see their internal representation.  The button labeled "Binary File Test" runs the program that was shown in the Quick Preview section.  The button labeled "Benchmark" uses the subset operator to insert a 6-bit BitString at a roaming location along a 64-bit BitString 10,000,000 times.  On my machine (AMD Phenom II X6 1035T), it takes about 1 minute and 30 seconds to finish.

I hope this library is useful for someone out there.  It can handle BitStrings/BitFields of very large length and the BitStrings are not constrained by byte/word boundaries.  It probably is not fast enough to do real-time bit manipulation but I hope it makes writing .NET code that needs to perform bit manipulation easier and more intuititive.

Thanks for reading!

History

• 10/19/2016 - Updated BitString library with optimization suggestions from readers (irneb).  This improved the speed of some operations by 25%.  Added Randomize() method to randomize bits in a BitString.
• 10/08/2016 - Initial Release.