Performance improvement for mirroring bit matrix around the diagonal

Question

I have some code that manages data received from an array of sensors. The PIC that controls the sensors uses 8 SAR-ADCs in parallel to read 4096 data bytes. It means it reads the most significant bit for the first 8 bytes; then it reads their second bit and so on until the eighth (least significant bit).

Basically, for each 8 bytes it reads, it creates (and sends forth to the computer) 8 bytes as follows:

// rxData[0] = MSB[7] MSB[6] MSB[5] MSB[4] MSB[3] MSB[2] MSB[1] MSB[0]
// rxData[1] =  B6[7]  B6[6]  B6[5]  B6[4]  B6[3]  B6[2]  B6[1]  B6[0]
// rxData[2] =  B5[7]  B5[6]  B5[5]  B5[4]  B5[3]  B5[2]  B5[1]  B5[0]
// rxData[3] =  B4[7]  B4[6]  B4[5]  B4[4]  B4[3]  B4[2]  B4[1]  B4[0]
// rxData[4] =  B3[7]  B3[6]  B3[5]  B3[4]  B3[3]  B3[2]  B3[1]  B3[0]
// rxData[5] =  B2[7]  B2[6]  B2[5]  B2[4]  B2[3]  B2[2]  B2[1]  B2[0]
// rxData[6] =  B1[7]  B1[6]  B1[5]  B1[4]  B1[3]  B1[2]  B1[1]  B1[0]
// rxData[7] = LSB[7] LSB[6] LSB[5] LSB[4] LSB[3] LSB[2] LSB[1] LSB[0]

This pattern is repeated for all the 4096 bytes the system reads and I process.

Imagine that each 8 bytes read are taken separately, we can then see them as an 8-by-8 array of bits. I need to mirror this array around the diagonal going from its bottom-left (LSB[7]) to its top-right (MSB[0]). Once this is done, the resulting 8-by-8 array of bits contains in its rows the correct data bytes read from the sensors. I used to perform this operation on the PIC controller, using left shifts and so on, but that slowed down the system quite a lot. Thus, this operation is now performed on the computer where we process the data, using the following code:

BitArray ba = new BitArray(rxData);
BitArray ba2 = new BitArray(ba.Count);
for (int i = 0; i < ba.Count; i++)
{
    ba2[i] = ba[(((int)(i / 64)) + 1) * 64 - 1 - (i % 8) * 8 - (int)(i / 8) + ((int)(i / 64)) * 8];
}
byte[] data = new byte[rxData.Length];
ba2.CopyTo(data, 0);

Note that THIS CODE WORKS.

rxData is the received byte array.

The formula I use for the index of ba[] in the loop codes for the mirroring of the arrays I described above. The size of the array is checked elsewhere to make sure it always contains the correct number (4096) of bytes.

So far this was the background for my problem.

In each processing loop of my system I need to perform that mirroring twice, because my data processing is on the difference between two arrays acquired consecutively. Speed is important for my system (possibly the main constraint on the processing), and the mirroring accounts for between 10% and 30% of the execution time of my processing.

I would like to know if there are alternative solutions I might compare to my mirroring code and that might allow me to improve performances. Using the BitArrays is the only way I found to address the different bits in the received bytes.

Answer 1

Operating on separate bits is very slow, and creating 2 bit arrays and copy data back and forth creates further overheads

The simplest obvious solution is just extracting the bits and combining them again. You can do it with a loop but since it uses both left and right shift at the same time, you need a function to handle negative shift amount. As a result here I unrolled it for easier understanding and more speed

out[0] = (byte)(((rxData[0] & 0x80) >> 0) | ((rxData[1] & 0x80) >> 1) | ((rxData[2] & 0x80) >> 2) | ((rxData[3] & 0x80) >> 3) |
                ((rxData[4] & 0x80) >> 4) | ((rxData[5] & 0x80) >> 5) | ((rxData[6] & 0x80) >> 6) | ((rxData[7] & 0x80) >> 7));
            
out[1] = (byte)(((rxData[0] & 0x40) << 1) | ((rxData[1] & 0x40) >> 0) | ((rxData[2] & 0x40) >> 1) | ((rxData[3] & 0x40) >> 2) |
                ((rxData[4] & 0x40) >> 3) | ((rxData[5] & 0x40) >> 4) | ((rxData[6] & 0x40) >> 5) | ((rxData[7] & 0x40) >> 6));
            
out[2] = (byte)(((rxData[0] & 0x20) << 2) | ((rxData[1] & 0x20) << 1) | ((rxData[2] & 0x20) >> 0) | ((rxData[3] & 0x20) >> 1) |
                ((rxData[4] & 0x20) >> 2) | ((rxData[5] & 0x20) >> 3) | ((rxData[6] & 0x20) >> 4) | ((rxData[7] & 0x20) >> 5));
            
out[3] = (byte)(((rxData[0] & 0x10) << 3) | ((rxData[1] & 0x10) << 2) | ((rxData[2] & 0x10) << 1) | ((rxData[3] & 0x10) >> 0) |
                ((rxData[4] & 0x10) >> 1) | ((rxData[5] & 0x10) >> 2) | ((rxData[6] & 0x10) >> 3) | ((rxData[7] & 0x10) >> 4));
            
out[4] = (byte)(((rxData[0] & 0x08) << 4) | ((rxData[1] & 0x08) << 3) | ((rxData[2] & 0x08) << 2) | ((rxData[3] & 0x08) << 1) |
                ((rxData[4] & 0x08) >> 0) | ((rxData[5] & 0x08) >> 1) | ((rxData[6] & 0x08) >> 2) | ((rxData[7] & 0x08) >> 3));
            
out[5] = (byte)(((rxData[0] & 0x04) << 5) | ((rxData[1] & 0x04) << 4) | ((rxData[2] & 0x04) << 3) | ((rxData[3] & 0x04) << 2) |
                ((rxData[4] & 0x04) << 1) | ((rxData[5] & 0x04) >> 0) | ((rxData[6] & 0x04) >> 1) | ((rxData[7] & 0x04) >> 2));
            
out[6] = (byte)(((rxData[0] & 0x02) << 6) | ((rxData[1] & 0x02) << 5) | ((rxData[2] & 0x02) << 4) | ((rxData[3] & 0x02) << 3) |
                ((rxData[4] & 0x02) << 2) | ((rxData[5] & 0x02) << 1) | ((rxData[6] & 0x02) >> 0) | ((rxData[7] & 0x02) >> 1));

out[7] = (byte)(((rxData[0] & 0x01) << 7) | ((rxData[1] & 0x01) << 6) | ((rxData[2] & 0x01) << 5) | ((rxData[3] & 0x01) << 4) |
                ((rxData[4] & 0x01) << 3) | ((rxData[5] & 0x01) << 2) | ((rxData[6] & 0x01) << 1) | ((rxData[7] & 0x01) >> 0));

Obviously this is still very slow because it operates byte-by-byte. An optimal solution would operate on multiple bytes at once, for example with SIMD and/or multithreading. Especially since you're doing that for lots of data, .NET SIMD intrinsics would be extremely useful