C Bit packing and structs

Bit packing of a struct is achieved with the ":" after the member of the struct this little item is great for working with binary images of data however it can lead to surprises. Always keep in mind the compiled result will mask and shift every thing you place in the struct.

#include <stdint.h>
#include <iostream>

using namespace std;

typedef struct {
    uint8_t a :6;
    uint8_t b :1;
    uint8_t c :1;
} Test1;

typedef struct {
    uint8_t a;
    uint8_t b;
    uint8_t c;
} Test2;

typedef union {
    struct {
 uint8_t a :6;
 uint8_t b :1;
 uint8_t c :1;
    } bits;
    uint8_t full;
} Test3;

int main()
{
    Test3 test3;
    
    cout << sizeof(Test1) << endl;
    cout << sizeof(Test2) << endl;
    cout << sizeof(Test3) << endl;
    
    test3.bits.a = 0;
    test3.bits.b = 0;
    test3.bits.c = 0;
    
    cout << "Test3 inited:" << endl 
  << (int)test3.bits.a << endl
  << (int)test3.bits.b << endl
  << (int)test3.full   << endl;
    
    test3.bits.a = 0xff;
    
    cout << "Test3.bits.a loaded with 255:" << endl 
  << (int)test3.bits.a << endl
  << (int)test3.bits.b << endl
  << (int)test3.full   << endl;
    
    test3.bits.a = 0x0;
    test3.bits.b = 0xff;
    
    cout << "Test3.bits.b loaded with 255:" << endl 
  << (int)test3.bits.a << endl
  << (int)test3.bits.b << endl
  << (int)test3.full   << endl;
}

The output looks like this (depending on machine endianness)

1
3
1
Test3 inited:
0
0
0
Test3.bits.a loaded with 255:
63
0
252
Test3.bits.b loaded with 255:
0
1
2

Bit twidding vs lookup tables

In semiconductor and RTL design using a pipeline of operations is much faster than a LUT(Look up table). However in software the result is flipped and small scale LUTs cut the complex sequence of operations to a single simplified action. In short memory lookup tables are generally much faster despite the chance of cache and memory glitches. Since im a semiconductor background the result always seems to surprise me when I revisit it.

The output is

speed of twiddling: 1482
speed of a lookup table: 874

The test code was:

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

// ********************* BIT TWIDDLER ********************* //

#define SUM_MASK1 0x55555555
#define SUM_MASK2 0x33333333
#define SUM_MASK3 0x07070707
#define SUM_MASK4 0x000f000f
#define SUM_MASK5 0x0000001f

unsigned int SumOfOnesTwiddle(unsigned int x)
{
  x = (SUM_MASK1 & (x >>  1)) + (SUM_MASK1 & x);
  x = (SUM_MASK2 & (x >>  2)) + (SUM_MASK2 & x);
  x = (SUM_MASK3 & (x >>  4)) + (SUM_MASK3 & x);
  x = (SUM_MASK4 & (x >>  8)) + (SUM_MASK4 & x);
  x = (SUM_MASK5 & (x >> 16)) + (SUM_MASK5 & x);

  return x;
}

void SumOfOnesTwiddleArray(unsigned int* in, unsigned int* out, unsigned int size)
{
  for(int i=0;i<size;i++)
    out[i] = SumOfOnesTwiddle(in[i]);
}

// ********************* LOOKUP TABLE ********************* //

#define TABLE_SIZE  256
unsigned int table[TABLE_SIZE];

void computeTable()
{
  for(int i=0; i<TABLE_SIZE; i++)
      table[i] = SumOfOnesTwiddle(i);
}

unsigned int SumOfOnesTable(unsigned int x)
{
  return  table[(x    ) & 0xff] +
          table[(x>>8 ) & 0xff] +
          table[(x>>16) & 0xff] +
          table[(x>>24) & 0xff];
}

void SumOfOnesTableArray(unsigned int* in, unsigned int* out, unsigned int size)
{
  for(int i=0;i<size;i++)
    out[i] = SumOfOnesTable(in[i]);
}

//testing

template<class itor>
void printOut(itor start, itor end)
{
  cout << hex << "0x";
  copy (start, end, ostream_iterator<int>(cout, " 0x"));
  cout << endl << endl;
}

#define SIZE 5000
int main()
{
  unsigned int indata[SIZE];
  unsigned int outdata[SIZE];
  unsigned int outdata2[SIZE];

  clock_t start_time, end_time;
  computeTable();

  srand(time(NULL));
  for(int i=0;i < SIZE; i++)
    indata[i] = rand();

  printOut(indata, indata+SIZE);
  SumOfOnesTwiddleArray(indata, outdata, SIZE);
  SumOfOnesTableArray  (indata, outdata2, SIZE);
  printOut(outdata,  outdata+SIZE);
  printOut(outdata2, outdata2+SIZE);

  for(int i=0;i < SIZE; i++)
    if(outdata[i] != outdata2[i])
       cout << "BUG!" << endl;

  start_time = clock();
  for(int i=0;i < SIZE; i++)
    SumOfOnesTwiddleArray(indata, outdata, SIZE);
  end_time = clock();

  cout << dec << "speed of bit twiddling: " << (end_time - start_time) << endl;

  start_time = clock();
  for(int i=0;i < SIZE; i++)
    SumOfOnesTableArray(indata, outdata, SIZE);
  end_time = clock();
  cout << dec << "speed of a lookup table: " << (end_time - start_time) << endl;

}

bit reversal

#if _WIN64 || __amd64__ || _M_X64
#define IS_64_BIT
#else
#define IS_32_BIT
#endif

#ifdef IS_64_BIT
uint64_t bitRevInt32(uint64_t value)
{
  value = (value & 0x00000000ffffffff) << 32 | (value & 0xffffffff00000000) >> 32;
  value = (value & 0x0000ffff0000ffff) << 16 | (value & 0xffff0000ffff0000) >> 16;
  value = (value & 0x00ff00ff00ff00ff) << 8  | (value & 0xff00ff00ff00ff00) >> 8;
  value = (value & 0x0f0f0f0f0f0f0f0f) << 4  | (value & 0xf0f0f0f0f0f0f0f0) >> 4;
  value = (value & 0x3333333333333333) << 2  | (value & 0xcccccccccccccccc) >> 2;
  value = (value & 0x5555555555555555) << 1  | (value & 0xaaaaaaaaaaaaaaaa) >> 1;
  return value;
}
#endif

uint32_t bitRevInt32(uint32_t value)
{
  value = (value & 0x0000ffff) << 16 | (value & 0xffff0000) >> 16;
  value = (value & 0x00ff00ff) << 8  | (value & 0xff00ff00) >> 8;
  value = (value & 0x0f0f0f0f) << 4  | (value & 0xf0f0f0f0) >> 4;
  value = (value & 0x33333333) << 2  | (value & 0xcccccccc) >> 2;
  value = (value & 0x55555555) << 1  | (value & 0xaaaaaaaa) >> 1;
  return value;
}

unsigned char bitRevChar(unsigned char value)
{
  value = (value & 0x0f) << 4 | (value & 0xf0) >> 4;
  value = (value & 0x33) << 2 | (value & 0xcc) >> 2;
  value = (value & 0x55) << 1 | (value & 0xaa) >> 1;
  return value;
}