/* ex: set ts=2 et: */
/* (c) 2007 Ryan "pizza" Flynn */
/* pizza \at/ parseerror /dot\ com */

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>
#include <limits.h>


#if 1
static unsigned char BitsSetTbl[65536];
#else
static const unsigned char BitsSetTbl[] = 
{
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
#endif

int bitcnt1_8tbl(uint8_t n)
{
  return BitsSetTbl[n];
}

/* count 1 bits */
int bitcnt1_8prl(uint8_t v)
{
  uint32_t c;
  v = v - ((v >> 1) & 0x55);
  v = (v & 0x33) + ((v >> 2) & 0x33);
  v = v + (v >> 4) & 0x0F;
  return v;
}

/* test correctness */
static void test_bitcnt1_8prl(void)
{
  uint8_t i = 255;
  int tbl, prl;
  do {
    tbl = bitcnt1_8tbl(i);
    prl = bitcnt1_8prl(i);
    printf("%u tbl=%d(%x) prl=%d(%x)\n", i, tbl, tbl, prl, prl);
    assert(tbl == prl);
  } while (i--);
}

int bitcnt1_32tbl(uint32_t n)
{
#if 0
  return BitsSetTbl[(n >> 24)]
       + BitsSetTbl[(n >> 16) & 0xff]
       + BitsSetTbl[(n >>  8) & 0xff]
       + BitsSetTbl[(n & 0xff)];
#else
  return BitsSetTbl[(n >> 16)]
       + BitsSetTbl[(n & 0xffff)];
#endif
}

/* count 1 bits */
int bitcnt1_32prl(uint32_t v)
{
  uint32_t c;
  v = v - ((v >> 1) & 0x55555555);                    /* reuse input as temporary */
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     /* temp */
  c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; /* count */
  return c;
}

static void speed_bitcnt1_8(void)
{
  struct timeval tv[3];
  double d[3];
  unsigned i;
  gettimeofday(tv, NULL);
  i = UINT_MAX;
  do
    bitcnt1_8tbl((uint8_t)i);
  while (i--);
  gettimeofday(tv + 1, NULL);
  i = UINT_MAX;
  do
    bitcnt1_8prl((uint8_t)i);
  while (i--);
  gettimeofday(tv + 2, NULL);
  d[0] = (tv[0].tv_sec * 1000000) + tv[0].tv_usec;
  d[1] = (tv[1].tv_sec * 1000000) + tv[1].tv_usec;
  d[2] = (tv[2].tv_sec * 1000000) + tv[2].tv_usec;
  printf("tbl: %f\n", (d[1] - d[0]) / 1000000);
  printf("prl: %f\n", (d[2] - d[1]) / 1000000);
}

static void speed_bitcnt1_32(void)
{
  struct timeval tv[3];
  double d[3];
  uint32_t i;
  i = 65535;
  do /* sneakily use the parallel method to build our table */
    BitsSetTbl[i] = bitcnt1_32prl(i);
  while (i--);
  /* done */
  gettimeofday(tv, NULL);
  i = UINT_MAX;
  do
    bitcnt1_32tbl(i);
  while (i--);
  gettimeofday(tv + 1, NULL);
  i = UINT_MAX;
  do
    bitcnt1_32prl(i);
  while (i--);
  gettimeofday(tv + 2, NULL);
  d[0] = (tv[0].tv_sec * 1000000) + tv[0].tv_usec;
  d[1] = (tv[1].tv_sec * 1000000) + tv[1].tv_usec;
  d[2] = (tv[2].tv_sec * 1000000) + tv[2].tv_usec;
  printf("tbl: %f\n", (d[1] - d[0]) / 1000000);
  printf("prl: %f\n", (d[2] - d[1]) / 1000000);
}

int main(void)
{
  //test_bitcnt1_8prl();
  //speed_bitcnt1_8(); // tbl is 50% fast
  speed_bitcnt1_32();
  return 0;
}