/*
 * Copyright 2004 Sun Microsystems, Inc. ALL RIGHTS RESERVED 
 * Use of this software is authorized pursuant to the terms of 
the 
 * license found at 
http://developers.sun.com/berkeley_license.html
 */

/*
 * By Greg Nakhimovsky, Sun MDE, March 2004.
 * Can be built under Solaris as:
 * cc popcnt.c phys_mem_avail.o -lkstat
 */

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

#define LIMIT 100000000

int phys_mem_avail(void);

int main()
{
  size_t total, i, x, *p;
  hrtime_t start, end;
  int mem_avail_kb;

  /* The obvious brute-force way to compute popcnt(x) */
  start = gethrtime();
  total = 0;
  for(i=0;i<LIMIT;i++)
  {
    x = i;
    while(x)
    {
       total += x&1;
       x >>= 1;
    }
  }
  end = gethrtime();
  printf("SUM(Obvious_popcnt) = %d\n", total);
  printf(" Time: %8.2f sec\n", (end-start)*1.e-9);
  printf("-----------------\n");

  /*
   * Check if there is enough memory to store the
   * popcnt() values for each number in (0,1,...255)
   */
  mem_avail_kb = phys_mem_avail();
  printf("Available physical memory: %d Kbytes\n", mem_avail_kb);
  printf("Memory required for storing 256 values:  %d Kbytes\n", 256*sizeof(size_t)/1024);
  if(mem_avail_kb > 256*sizeof(size_t)/1024)
  {
    start = gethrtime();
    /* precompute */
    if((p=malloc(256*sizeof(size_t))) == NULL)
      printf("Out of memory\n"), exit(1);
    for(i=0;i<256;i++)
    {
      p[i] = 0;
      x = i;
      while(x)
      {
        p[i] += x&1;
        x >>= 1;
      }
    }
    end = gethrtime();
    printf("Time to precompute 256 values: %8.2f sec\n", (end-start)*1.e-9);
    /* Now use the precomputed values */
    total = 0;
    for(i=0;i<LIMIT;i++)
    {
      total += p[i&0xff] + p[(i>>8)&0xff] + p[(i>>16)&0xff] + p[(i>>24)&0xff];
    }
    free(p);

    end = gethrtime();
    printf("SUM(using 256 precomputed values) = %d\n", total);
    printf(" Time: %8.2f sec\n", (end-start)*1.e-9);
  } else
    printf("Not enough physical memory to store 256 precomputed values\n");
  printf("-----------------\n");

  /*
   * Check if there is enough memory to store the
   * popcnt() values for each number in (0,1,...65535)
   */
  mem_avail_kb = phys_mem_avail();
  printf("Available physical memory: %d Kbytes\n", mem_avail_kb);
  printf("Memory required for storing 65536 values:  %d Kbytes\n", 65536*4/1024);
  if(mem_avail_kb > 65536*4/1024)
  {
    start = gethrtime();
    /* precompute */
    if((p=malloc(65536*sizeof(size_t))) == NULL)
      printf("Out of memory\n"), exit(1);

    for(i=0;i<65536;i++)
    {
      p[i] = 0;
      x = i;
      while(x)
      {
        p[i] += x&1;
        x >>= 1;
      }
    }
    end = gethrtime();
    printf("Time to precompute 65536 values: %8.2f sec\n", (end-start)*1.e-9);
    /* Now use the precomputed values */
    total = 0;
    for(i=0;i<LIMIT;i++)
    {
      total += p[i&0xffff] + p[(i>>16)&0xffff];
    }
    free(p);
    end = gethrtime();
    printf("SUM(using 65536 precomputed values) = %d\n", total);
    printf(" Time: %8.2f sec\n", (end-start)*1.e-9);
  } else
    printf("Not enough physical memory to store 65536 precomputed values\n");

  return 0;
}