C# - Writing generic method to handle bit manipulation

Question

I'm working on a tool that has to conform to a spec that has a heavy amount of packing data into bits across byte boundaries. Example: 2 bytes encode 2 fields, 10 bit value, 6 bit tolerance. Other fields may be cross 2-4 bytes and broken into many more fields.

Rather than fight with C# and try to get Structs with Bitfields (like in C++), I figured another alternative is to create generic bit packing/unpacking functions right before sending/after receiving data, and working with all data in C# using the standard types: byte, short, int, long, etc.

I'm new to C# so I'm not sure the best way of approaching this. From what I've read, using unsafe along with pointers is discouraged, but my attempts to use generic types failed miserably:

private static bool GetBitsFromByte<T,U>(T input, byte count, out U output, byte start = 0) where T:struct where U:struct
{
    if (input == default(T))
        return false;

    if( (start + count) > Marshal.SizeOf(input))
        return false;

    if(count > Marshal.SizeOf(output))
        return false;

    // I'd like to setup the correct output container based on the
    // number of bits that are needed
    if(count <= 8)
        output = new byte();
    else if (count <= 16)
        output = new UInt16();
    else if (count <= 32)
        output = new UInt32();
    else if (count <= 64)
        output = new UInt64();
    else
        return false;

    output = 0; // Init output

    // Copy bits out in order
    for (int i = start; i < count; i++)
    {
        output |= (input & (1 << i));  // This is not possible with generic types from my understanding
    }
    return true; 
}

I'd be calling the method with something like this to pull 10 bits (from LSB) out from data_in into data_out and the next 6 bits from data_in into next_data_out.

Uint32 data_in = 0xdeadbeef;
Uint16 data_out;
byte next_data_out;
if(GetBitsFromByte<Uint32,Uint16>(data_in, 10, out data_out, 0))
{
    // data_out should now = 0x2EF
    if(GetBitsFromByte<Uint32,byte>(data_in, 6, out next_data_out, data_out.Length))
    {
        // next_data_out should now = 0x2F
    }
}

I'd rather not have to write functions for all possible combinations of byte, ushort, uint, ulong, although I guess that is an alternative.

I already looked at BitConverter class but that is for byte arrays not manipulating bits. I also understand that I cannot do something like: where T : INumeric or where T : System.ValueType, so I'm open to suggestions.

Thanks!

Answer 1

If you want to get this working on any random struct, it kind of smacks of a serialization problem. See this thread for some info on that:

How to convert a structure to a byte array in C#?

Here's the above notion with a small bit of modification to make it generic:

class GenericSerializer <T>
{
    public BitArray ToBitArray(T input, int start, int len)
    {
        int structSize = Marshal.SizeOf(input);
        BitArray ret = new BitArray(len);
        int byteStart = start / 8;
        int byteEnd = (start + len) / 8 + 1;
        byte[] buffer = new byte[byteEnd - byteStart];

        IntPtr ptr = Marshal.AllocHGlobal(structSize);
        Marshal.StructureToPtr(input, ptr, false);
        Marshal.Copy(ptr, buffer, byteStart, buffer.Length);
        Marshal.FreeHGlobal(ptr);

        int destBit = 0;
        int sourceBit = start % 8;
        int sourceEnd = sourceBit + len;
        while (sourceBit < sourceEnd)
        {
            ret[destBit] = 0 != (buffer[sourceBit / 8] 
                & (1 << (sourceBit % 8)));
            ++sourceBit;
            ++destBit;
        }

        return ret;
    }

    public T FromBytes(byte[] arr)
    {
        IntPtr ptr = Marshal.AllocHGlobal(arr.Length);
        Marshal.Copy(arr, 0, ptr, arr.Length);

        T output = (T)Marshal.PtrToStructure(ptr, typeof(T));
        Marshal.FreeHGlobal(ptr);

        return output;
    }
}

Note: I only did BitArray for the read and used byte [] for the write. (A drawback here is you're fully copying the struct twice for each operation so it won't be very performant)

Using BitConverter or a set of functions to go to/from a few known types (e.g. Int32, Int16, Int64 etc) Is probably going to run a whole lot faster.

Answer 2

As you know, you can't do where T : INumeric, so whatever you write is probably going to have to have a few variations to support different numeric types.

I'd probably use a BitArray and write methods to convert to/from your other data types as necessary. You'd then need, at most, one method from and to each numeric type, not one for each combination of types. (there are 8-ish integer types in C#, so worst case is around 8+8=16, not 8*8=64)

You could probably use T4 Templates to generate the methods for the 8-ish integer types, if you don't like the idea of manual copy/pasting, and updating that when something changes.

uint data_in = 0xdeadbeef;
ushort data_out;
byte next_data_out;
// pay attention to BitConverter.IsLittleEndian here!
// you might need to write your own conversion methods,
// or do a Reverse() or find a better library
var bits = new BitArray(BitConverter.GetBytes(data_in));
if (bits.TryConvertToUInt16(out data_out, 10))
{
    Console.WriteLine(data_out.ToString("X")); // 2EF
    if (bits.TryConvertToByte(out next_data_out, 6, 10))
    {
        Console.WriteLine(next_data_out.ToString("X")); // 2F
    }
}


private static bool Validate(BitArray bits, int len, int start, int size)
{
    return len < size * 8 && bits.Count > start + len;
}
public static bool TryConvertToUInt16(this BitArray bits, out ushort output, int len, int start = 0)
{
    output = 0;
    if (!Validate(bits, len, start, sizeof(ushort)))
        return false;
    for (int i = start; i < len + start; i++)
    {
        output |= (ushort)(bits[i] ? 1 << (i - start) : 0);
    }
    return true;
}
public static bool TryConvertToByte(this BitArray bits, out byte output, int len, int start = 0)
{
    output = 0;
    if (!Validate(bits, len, start, sizeof(byte)))
        return false;
    for (int i = start; i < len + start; i++)
    {
        output |= (byte)(bits[i] ? 1 << (i - start) : 0);
    }
    return true;
}

Answer 3

There are a couple things going on here:

1. When you have an out parameter, you have to assign to it somewhere in your function. Statements like this are invalid:

   if( (start + count) > Marshal.SizeOf(input))
       return false; // no assignment to output!
   

2. Similarly, you have many assignments for output. Don't do that, you're specifying output's type in your declaration as type U

   // don't do this
   if(count <= 8)
        output = new byte();
   if (...) //etc 
   // do this
   output = new U();
   

3. Even correcting for those two, I'm still not sure how far you'll be able to get. You won't be able to infer any operations from your generic types, and I don't think you'll be able to assign values to them.

   // impossible to infer from a parameter constraint of "struct" 
   output = 0; // Init output
   

So, you may get away with versions that have hard-coded outputs (making U a hard coded type), but trying to have an out generic type seems close to impossible from my perspective.

edit: come to think of it, I'm not sure that you'll be able to perform your bitwise operation on a generic struct, either.