/* Fritsch, 2.June 1999 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define BUFFER_SIZE 500000
#define REPEATER    300

/*********************************************************************/
unsigned long CountBits1(unsigned long *Buffer, unsigned long Size)
{
 unsigned long Result=0, i, Value;

 for(i=0;i<Size;i++)
 {
  Value=*Buffer++;
  for( ; Value; Value>>=1)
  {
   Result+=(Value&0x01);
  }
 }
 return Result;
}

/*********************************************************************/

unsigned long CountBits2(unsigned long *Buffer, unsigned long Size)
{
 unsigned long Result=0, i, Value;

 for(i=0;i<Size/4;i++)
 {
  Value=*Buffer++;
  for( ; Value; Value>>=1)
  {
   Result+=(Value&0x01);
  }

  Value=*Buffer++;
  for( ; Value; Value>>=1)
  {
   Result+=(Value&0x01);
  }

  Value=*Buffer++;
  for( ; Value; Value>>=1)
  {
   Result+=(Value&0x01);
  }

  Value=*Buffer++;
  for( ; Value; Value>>=1)
  {
   Result+=(Value&0x01);
  }

 }
 return Result;
}

/*********************************************************************/

unsigned long CountBits3(unsigned long *Buffer, unsigned long Size)
{
 unsigned long Result=0, i, Value;

 for(i=0;i<Size;i++)
 {
  Value=*Buffer++;
  Result+= (Value&0x00000001)!=0;
  Result+= (Value&0x00000002)!=0;
  Result+= (Value&0x00000004)!=0;
  Result+= (Value&0x00000008)!=0;
  Result+= (Value&0x00000010)!=0;
  Result+= (Value&0x00000020)!=0;
  Result+= (Value&0x00000040)!=0;
  Result+= (Value&0x00000080)!=0;
  Result+= (Value&0x00000100)!=0;
  Result+= (Value&0x00000200)!=0;
  Result+= (Value&0x00000400)!=0;
  Result+= (Value&0x00000800)!=0;
  Result+= (Value&0x00001000)!=0;
  Result+= (Value&0x00002000)!=0;
  Result+= (Value&0x00004000)!=0;
  Result+= (Value&0x00008000)!=0;
  Result+= (Value&0x00010000)!=0;
  Result+= (Value&0x00020000)!=0;
  Result+= (Value&0x00040000)!=0;
  Result+= (Value&0x00080000)!=0;
  Result+= (Value&0x00100000)!=0;
  Result+= (Value&0x00200000)!=0;
  Result+= (Value&0x00400000)!=0;
  Result+= (Value&0x00800000)!=0;
  Result+= (Value&0x01000000)!=0;
  Result+= (Value&0x02000000)!=0;
  Result+= (Value&0x04000000)!=0;
  Result+= (Value&0x08000000)!=0;
  Result+= (Value&0x10000000)!=0;
  Result+= (Value&0x20000000)!=0;
  Result+= (Value&0x40000000)!=0;
  Result+= (Value&0x80000000)!=0;
 }
 return Result;
}

/*********************************************************************/

unsigned long CountBits4(unsigned long *Buffer, unsigned long Size)
{
 unsigned long Result=0, i, Value;

 for(i=0;i<Size;i++)
 {
  Value=*Buffer++;
  if (Value&0x00000001) Result++;
  if (Value&0x00000002) Result++;
  if (Value&0x00000004) Result++;
  if (Value&0x00000008) Result++;
  if (Value&0x00000010) Result++;
  if (Value&0x00000020) Result++;
  if (Value&0x00000040) Result++;
  if (Value&0x00000080) Result++;
  if (Value&0x00000100) Result++;
  if (Value&0x00000200) Result++;
  if (Value&0x00000400) Result++;
  if (Value&0x00000800) Result++;
  if (Value&0x00001000) Result++;
  if (Value&0x00002000) Result++;
  if (Value&0x00004000) Result++;
  if (Value&0x00008000) Result++;
  if (Value&0x00010000) Result++;
  if (Value&0x00020000) Result++;
  if (Value&0x00040000) Result++;
  if (Value&0x00080000) Result++;
  if (Value&0x00100000) Result++;
  if (Value&0x00200000) Result++;
  if (Value&0x00400000) Result++;
  if (Value&0x00800000) Result++;
  if (Value&0x01000000) Result++;
  if (Value&0x02000000) Result++;
  if (Value&0x04000000) Result++;
  if (Value&0x08000000) Result++;
  if (Value&0x10000000) Result++;
  if (Value&0x20000000) Result++;
  if (Value&0x40000000) Result++;
  if (Value&0x80000000) Result++;
 }
 return Result;
}

/*********************************************************************/

unsigned char LockUpTable256[0x100];

void InitLockUpTable256(void)
{
 unsigned int i;
 unsigned char Value;
 for(i=0;i<0x100;i++)
 {
  LockUpTable256[i]=0;
  for( Value=i ; Value; Value>>=1)
  {
   LockUpTable256[i]+=(Value&0x01);
  }
 }
}

unsigned long CountBits5(unsigned long *Buffer, unsigned long Size)
{
 unsigned long Result=0, i, Value;

 for(i=0;i<Size;i++)
 {
  Value=*Buffer++;
  Result+=LockUpTable256[  Value&0x000000ff       ];
  Result+=LockUpTable256[ (Value&0x0000ff00)>> 8  ];
  Result+=LockUpTable256[ (Value&0x00ff0000)>> 16 ];
  Result+=LockUpTable256[ (Value&0xff000000)>> 24 ];
 }
 return Result;
}

/*********************************************************************/

unsigned char LockUpTable64k[0x10000];

void InitLockUpTable64k(void)
{
 unsigned long i;
 unsigned int Value;
 for(i=0;i<0x10000;i++)
 {
  LockUpTable64k[i]=0;
  for( Value=i ; Value; Value>>=1)
  {
   LockUpTable64k[i]+=(Value&0x01);
  }
 }
}

unsigned long CountBits6(unsigned long *Buffer, unsigned long Size)
{
 unsigned long Result=0, i, Value;

 for(i=0;i<Size;i++)
 {
  Value=*Buffer++;
  Result+=LockUpTable64k[  Value&0x0000ffff       ];
  Result+=LockUpTable64k[ (Value&0xffff0000)>> 16 ];
 }
 return Result;
}

/*********************************************************************/



int main(void)
{
 unsigned long *Buffer;
 unsigned int j;
 unsigned long Result;
 time_t StartTime;

 printf("Allocating buffer for %ld longs\n",BUFFER_SIZE);
 Buffer=(unsigned long*) malloc(BUFFER_SIZE*sizeof(long));
 if(Buffer)
 {
  unsigned long i;
  printf("Filling buffer with random values...\n\n");
  for(i=0;i<BUFFER_SIZE;i++)
  {
   /* init all Longs with random values */
   Buffer[i]=( rand()%0x100      ) | (( rand()%0x100) << 8 ) |
             ((rand()%0x100) <<16) | (( rand()%0x100) <<24 );
  }

  InitLockUpTable256();
  InitLockUpTable64k();

  printf("Variant 1 = Bit shifted and lowest bit added to result\n");
  printf("Variant 2 = Same as variant 1, but unrolled loop a little\n");
  printf("Variant 3 = 32 AND-Operations\n");
  printf("Variant 4 = simelar to variant 3\n");
  printf("Variant 5 = LockUp-table with 256 entries\n");
  printf("Variant 6 = LockUp-table with 64k entries\n\n\n");

  printf("Start bitcounting, I will repeat each job %ld times to increase timing accuracy.\n\n",REPEATER);


//-----------------------------------------------------------------------------
  StartTime=time(NULL);
  for(j=0;j< REPEATER;j++)
  {
   Result=CountBits1(Buffer,BUFFER_SIZE);
  }
  printf("Variant 1 Time: %4ld seconds.  ",time(NULL)-StartTime);
  printf("Found %lu Bits set to 1\n",Result);
//-----------------------------------------------------------------------------

  StartTime=time(NULL);
  for(j=0;j< REPEATER;j++)
  {
   Result=CountBits2(Buffer,BUFFER_SIZE);
  }
   printf("Variant 2 Time: %4ld seconds.  ",time(NULL)-StartTime);
   printf("Found %lu Bits set to 1\n",Result);
//-----------------------------------------------------------------------------

  StartTime=time(NULL);
  for(j=0;j< REPEATER;j++)
  {
   Result=CountBits3(Buffer,BUFFER_SIZE);
  }
  printf("Variant 3 Time: %4ld seconds.  ",time(NULL)-StartTime);
  printf("Found %lu Bits set to 1\n",Result);
//-----------------------------------------------------------------------------

  StartTime=time(NULL);
  for(j=0;j< REPEATER;j++)
  {
   Result=CountBits4(Buffer,BUFFER_SIZE);
  }
  printf("Variant 4 Time: %4ld seconds.  ",time(NULL)-StartTime);
  printf("Found %lu Bits set to 1\n",Result);
//-----------------------------------------------------------------------------

  StartTime=time(NULL);
  for(j=0;j< REPEATER;j++)
  {
   Result=CountBits5(Buffer,BUFFER_SIZE);
  }
  printf("Variant 5 Time: %4ld seconds.  ",time(NULL)-StartTime);
  printf("Found %lu Bits set to 1\n",Result);
//-----------------------------------------------------------------------------

  StartTime=time(NULL);
  for(j=0;j< REPEATER;j++)
  {
   Result=CountBits6(Buffer,BUFFER_SIZE);
  }
  printf("Variant 6 Time: %4ld seconds.  ",time(NULL)-StartTime);
  printf("Found %lu Bits set to 1\n",Result);
//-----------------------------------------------------------------------------


  free(Buffer);
 }
 else
 {
  printf("Could not allocate the buffer\n");
 }

 printf("press enter to finish\n");
 getchar();
 return 0;
}