Reputation: 36080

Read bit range from byte array

I am looking for a method that will enable me to get a range of bits. For example if I have the binary data

0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 (2 bytes)

I might need to get data from range bit 3 to 9. In other words I would be interested in:

0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1

so in short I will like to construct the method:

 byte[] Read(byte[] data, int left, int right){ 

     // implementation
 }

so that if I pass the data new byte[]{91,215}, 3, 9 I will get byte[]{122} (note byte 91 and 215 = 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 and byte 122 = 1 1 1 1 0 1 0 same binary data as the example.

It would be nice if I could use the << operator on byte arrays such as doing something like:

  byte[] myArray = new byte[] { 1, 2, 3 };
  var shift = myArray << 2;

If you are interested to know why I need this functionality:

I am creating a project on a board and often need to read and write values to the memory. The cdf, sfr, or ddf (refereed to as chip definition file) contains information about a particular chip. That file may look like:

;     Name                            Zone      Address     Bytesize  Displaybase Bitrange
;     ----                            ----      -------     --------  ----------- --------

sfr = "SPI0_CONTROL"              , "Memory", 0x40001000,        4, base=16
sfr = "SPI0_CONTROL.SPH"          , "Memory", 0x40001000,        4, base=16,    bitRange=25-25
sfr = "SPI0_CONTROL.SPO"          , "Memory", 0x40001000,        4, base=16,    bitRange=24-24
sfr = "SPI0_CONTROL.TXRXDFCOUNT"  , "Memory", 0x40001000,        4, base=16,    bitRange=8-23
sfr = "SPI0_CONTROL.INT_TXUR"     , "Memory", 0x40001000,        4, base=16,    bitRange=7-7
sfr = "SPI0_CONTROL.INT_RXOVF"    , "Memory", 0x40001000,        4, base=16,    bitRange=6-6

Since I am reading a lot of variables (sometimes 80 times per second) I will like to have an efficient algorithm. I guess my approach would be that if the bytesize is 8 then I will create a long from those 8 bytes then use the << and >> operators in order to get what I need. if the bytesize if 4 then I will create an int and use the << and >> operators but How will I do it if I need to read 16 bytes though? I guess my question should been how to implement the << and >> operators on custom struct types.

Upvotes: 8

Answers (4)

Amal K

Reputation: 4929

It's been 10 years since this question and I could not yet find a simple C# implementation that extracts a range of bits from a byte array using bitwise operations. Here's how you can do it using simple bitwise operations:

public static class ByteExtensions
{
    public const int BitsPerByte = 8;

    /// <summary>
    /// Extracts a range of bits from a byte array into a new byte array.
    /// </summary>
    /// <param name="bytes">The byte array to extract the range from.</param>
    /// <param name="start">The 0-based start index of the bit.</param>
    /// <param name="length">The number of bits to extract.</param>
    /// <returns>A new <see cref="byte"/> array with the extracted bits.</returns>
    /// <exception cref="ArgumentOutOfRangeException">Thrown if <paramref name="start"/> or <paramref name="length"/> are out of range.</exception>
    public static byte[] GetBitRange(this byte[] bytes, int start, int length)
    { 
        // Calculate the length of the input byte array in bits 
        int maxLength = bytes.Length * BitsPerByte;

        int end = start + length;

        // Range validations
        if (start >= maxLength || start < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(start), start, $"Start must non-negative and lesser than {maxLength}");
        }
        if (length < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(length), length, $"Length must be non-negative");
        }
        if (end > maxLength)
        {
            throw new ArgumentOutOfRangeException(nameof(length), length, $"Range length must be less than or equal to {maxLength}");
        }

        // Calculate the length of the new byte array and allocate
        var (byteLength, remainderLength) = Math.DivRem(length, BitsPerByte);
        byte[] result = new byte[byteLength + (remainderLength == 0 ? 0 : 1)];

        // Iterate through each byte in the new byte array
        for (int i = 0; i < result.Length; i++)
        {
            
            // Compute each of the 8 bits of the ith byte
            // Stop if start index >= end index (rest of the bits in the current byte will be 0 by default)
            for (int j = 0; j < BitsPerByte && start < end; j++)
            {
                var (byteIndex, bitIndex) = Math.DivRem(start++, BitsPerByte); // Note the increment(++) in start
                int currentBitIndex = j;
      
                result[i] |= (byte)(((bytes[byteIndex] >> bitIndex) & 1) << currentBitIndex);
            }
        }
        return result;
    }
}

Explanation

1. Allocate a new byte[] for the range

The GetBitRange(..) method above first (after validation) calculates the length of the new byte array(length in bytes) using the length parameter(length in bits) and allocates this array(result).

The outer loop iterates through each byte in result and the inner loop iterates through each of the 8 bits in the i^th byte.

2. Extracting a bit from a byte

In the inner loop, the method calculates the index of the byte in the input array bytes which contains the bit indexed by start. It is the bitIndex^th bit in the byteIndex^th byte. To extract this bit, you perform the following operations:

int nextBit = (bytes[byteIndex] >> bitIndex) & 1;

Shift the bitIndex^th bit in bytes[byteIndex] to the rightmost position so it is the least significant bit(LSB). And then perform a bitwise AND with 1. (A bitwise AND with 1 extracts only the LSB and makes the rest of the bits 0.)

3. Setting a bit in a byte

Now, nextBit is the next bit I need to add to my output byte array(result). Since, I'm currently working on the j^th bit of my i^th byte of result in my inner loop, I need to set that bit to nextBit. This is done as:

int currentBitIndex = j;
result[i] |= (byte) (nextBit << currentBitIndex);

Shift nextBit j times to the left (since I want to set the j^th bit). Now to set the bit, I perform a bitwise OR between the shifted bit and result[i]. This sets the j^th bit in result[i].

The steps 2 & 3 described above are implemented in the method as a single step:

result[i] |= (byte)(((bytes[byteIndex] >> bitIndex) & 1) << currentBitIndex);

Two important things to consider here:

Byte Endianness
Bit Numbering

Byte Endianness

The above implementation indexes into the input byte array in big endian order. So, as per the example in the question,

new byte[]{ 91 , 215 }.GetBitRange(3, 8)

does not return 122 but returns 235 instead. This is because the example in the question expects the answer in little-endian format. To use little-endian format, a simple reversal of the output array does the job. Even better is to change byteIndex in the implementation:

byteIndex = bytes.Length - 1 - byteIndex;

Bit Numbering

Bit numbering determines if the least significant bit is the first bit in the byte (LSB 0) or the most significant bit is the first bit (MSB 0).
The implementation above assumes LSB0 bit numbering.
To use MSB0, change the bit indices as follows:

currentBitIndex = BitsPerByte - 1 - currentBitIndex;
bitIndex = BitsPerByte - 1 - bitIndex;

Extending for endianness and bit numbering

Here is the full method supporting both types of endianness as well as bit numbering:

public enum Endianness
{
    BigEndian,
    LittleEndian
}

public enum BitNumbering
{
    Lsb0,
    Msb0
}

public static class ByteExtensions
{
    public const int BitsPerByte = 8;

    public static byte[] GetBitRange(
        this byte[] bytes, 
        int start, 
        int length, 
        Endianness endianness, 
        BitNumbering bitNumbering)
    { 
        // Calculate the length of the input byte array in bits 
        int maxLength = bytes.Length * BitsPerByte;

        int end = start + length;

        // Range validations
        if (start >= maxLength || start < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(start), start, $"Start must non-negative and lesser than {maxLength}");
        }
        if (length < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(length), length, $"Length must be non-negative");
        }
        if (end > maxLength)
        {
            throw new ArgumentOutOfRangeException(nameof(length), length, $"Range length must be less than or equal to {maxLength}");
        }

        // Calculate the length of the new byte array and allocate
        var (byteLength, remainderLength) = Math.DivRem(length, BitsPerByte);
        byte[] result = new byte[byteLength + (remainderLength == 0 ? 0 : 1)];

        // Iterate through each byte in the new byte array
        for (int i = 0; i < result.Length; i++)
        {

            // Compute each of the 8 bits of the ith byte
            // Stop if start index >= end index (rest of the bits in the current byte will be 0 by default)
            for (int j = 0; j < BitsPerByte && start < end; j++)
            {
                var (byteIndex, bitIndex) = Math.DivRem(start++, BitsPerByte); // Note the increment(++) in start
                int currentBitIndex = j;
                
                // Adjust for MSB 0
                if (bitNumbering is BitNumbering.Msb0)
                {
                    currentBitIndex = 7 - currentBitIndex;
                    bitIndex = 7 - bitIndex;
                }
                // Adjust for little-endian
                if (endianness is Endianness.LittleEndian)
                {
                    byteIndex = bytes.Length - 1 - byteIndex;
                }
                result[i] |= (byte)(((bytes[byteIndex] >> bitIndex) & 1) << currentBitIndex);
            }
        }
        return result;
    }
}

Upvotes: 0