/* Compare times for popcount instructions */
/* Usage:  poptest K N
   - measures the time for 1000*N popcount operations on words
     with K one bits, comparing with the macro POPCOUNTMAC.
     Compile with values for WORDSIZE and POPC with POPC values:
     0 = loop, 1 = popcount, 2 = popcountl, 3 = popcountll,
                    4 = _mm_popcnt_u32, 5 = _mm_popcnt_u32 */

#define MAXN WORDSIZE

#ifndef WORDSIZE 
#define WORDSIZE 32
#endif

#ifndef POPC
#error  Need a value for POPC
#endif

#include "gtools.h"
#ifdef __INTEL_COMPILER
#include <nmmintrin.h>
#endif

#if POPC==0
#define NEWPOPC(x,c) {c = 0; while(x){++c; x &= x-1;}}
#endif
#if POPC==1
#define NEWPOPC(x,c) {c = __builtin_popcount(x);}
#endif
#if POPC==2
#define NEWPOPC(x,c) {c = __builtin_popcountl(x);}
#endif
#if POPC==3
#define NEWPOPC(x,c) {c = __builtin_popcountll(x);}
#endif
#if POPC==4
#define NEWPOPC(x,c) {c = _mm_popcnt_u32(x);}
#endif
#if POPC==5
#define NEWPOPC(x,c) {c = _mm_popcnt_u64(x);}
#endif

static setword
ransetword(int k)     /* setword with k random bits */
{
	register setword w,rb;
	register int j;

	j = 0;
	w = 0;
	for (;;)
	{
	    if (j == k) return w;

	    rb = bit[random() % WORDSIZE];
	    if ((rb & w) == 0)
	    {
		w |= rb;
		++j;
	    }
	}
}

static double
timemac(setword *x, int n, int iters, int *sump)
{
	register int c,i,j,sum;
	register setword w;
	int it;
	double t;

	sum = 0;
	for (i = 0; i < n; ++i)
	{
	    w = x[i];
	    sum += POPCOUNTMAC(w);
	}

	t = CPUTIME;

	for (it = 0; it < iters; ++it)
	{
	    for (i = 0; i < n; ++i)
            {
                w = x[i];
                sum += POPCOUNTMAC(w);
            }
	    sum ^= it;
	}	
	    
	t = CPUTIME - t;
	*sump = sum;

	return t;
}

static double
timeold(setword *x, int n, int iters, int *sump)
{
	register int c,i,j,sum;
	register setword w;
	int it;
	double t;

	sum = 0;
	for (i = 0; i < n; ++i)
	{
	    w = x[i];
	    sum += POPCOUNT(w);
	}

	t = CPUTIME;

	for (it = 0; it < iters; ++it)
	{
	    for (i = 0; i < n; ++i)
            {
                w = x[i];
                sum += POPCOUNT(w);
            }
	    sum ^= it;
	}	
	    
	t = CPUTIME - t;
	*sump = sum;

	return t;
}

static double
timenew(setword *x, int n, int iters, int *sump)
{
	register int c,i,j,sum;
	register setword w;
	int it;
	double t;

	sum = 0;
	for (i = 0; i < n; ++i)
	{
	    w = x[i];
	    NEWPOPC(w,c);
	    sum += c;
	}

	t = CPUTIME;

	for (it = 0; it < iters; ++it)
	{
	    for (i = 0; i < n; ++i)
            {
                w = x[i];
		NEWPOPC(w,c);
                sum += c;
            }
	    sum ^= it;
	}	
	    
	t = CPUTIME - t;
	*sump = sum;

	return t;
}

static double
timenull(setword *x, int n, int iters, int *sump)
{
	register int c,i,j,sum;
	register setword w;
	int it;
	double t;

	sum = 0;
	for (i = 0; i < n; ++i)
	{
	    w = x[i];
	    NEWPOPC(w,c);
	    sum += c;
	}

	t = CPUTIME;

	for (it = 0; it < iters; ++it)
	{
	    for (i = 0; i < n; ++i)
            {
                w = x[i];
		c = w;
                sum += c;
            }
	    sum ^= it;
	}	
	    
	t = CPUTIME - t;
	*sump = sum;

	return t;
}

int
main(int argc, char *argv[])
{
	int i,k,iters;
	setword x[1000];
	double tnull,told,tnew,tmac;
	int summac,sumold,sumnew,sumnull;

	printf("WORDSIZE=%d POPC=%s  ",WORDSIZE,
          POPC==0 ? "loop" :
          POPC==1 ? "popcount" : 
          POPC==2 ? "popcountl" : 
          POPC==3 ? "popcountll" : 
          POPC==4 ? "popcnt_u32" : 
          POPC==5 ? "popcnt_u64" : "undefined");
#ifdef SETWORD_INT
        printf(" setword=unsigned int ");
#endif
#ifdef SETWORD_LONG
        printf(" setword=unsigned long ");
#endif
#ifdef SETWORD_LONGLONG
        printf(" setword=unsigned long long ");
#endif
#ifdef __SSE4_2__
	printf("__SSE4_2__ ");
#endif
#ifdef __POPCNT__
	printf("__POPCNT__ ");
#endif
#ifdef __INTEL_COMPILER
	printf("__INTEL_COMPILER ");
#endif
printf("\n");

	if (argc != 3)
        {
	    fprintf(stderr,"Usage: poptest num1bits numiters\n");
	    exit(1);
        }

	k = atoi(argv[1]);
	if (k > WORDSIZE) k = WORDSIZE;
	iters = atoi(argv[2]);

	for (i = 0; i < 1000; ++i)
	    x[i] = ransetword(k);

	tnull = timenull(x,1000,iters,&sumnull);
	tmac = timemac(x,1000,iters,&summac);
	told = timeold(x,1000,iters,&sumold);
	tnew = timenew(x,1000,iters,&sumnew);

	if (summac != sumold) printf("*** sum mismatch (mac/old)\n");
	if (sumold != sumnew) printf("*** sum mismatch (old/new)\n");

	printf("macro=%3.2f compiled=%3.2f new=%3.2f\n",
		tmac-tnull,told-tnull,tnew-tnull);

	return 0;
}