/*
 * 
 * Here is some code used to test the bit counting algorithms
 * described in "Of Integers, Fields and Bit Counting" by 
 *
 *                         Alan W. Paeth
 *                    NeuralWare Incorporated
 *                   Pittsburgh, Pennsylvania
 *
 *                       David Schilling
 *                     Software Consultant
 *                     Bellevue, Washington
 *
 * It assumes that rand() returns an integer in [0..32767].
 * If long's were returned, the code for generating random samples
 * becomes greatly simplified.
 *
 * srand() is the random seed function.  It is used to produce the
 * SAME random sample each time the test is run so that if bugs are
 * found, they can be reproduced.
 * rand() and srand() are defined in stdlib.h.
 * 
 * Feel free to modify this code for the purposes of testing the bit
 * counting algorithms on your machine, and also to determine which
 * version is the fastest on your setup.  It is highly recommended
 * that the code which is generated by a compiler for the bit-counting
 * routines be manually examined.
 *
 */

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

extern int bit32on1( unsigned long a );
extern int bit32on2( unsigned long a );
extern int bit32on3( unsigned long a );

int CorrectCount( unsigned long a )
  {
  int c;

  c = 0;
  while( a != 0 )
    {
    c++;
    // not correct: there is no negative unsigned long: a = a & ~-a;
    }
  return( c );
  }

void Error( unsigned long i, int count, char *fn )
  {
  printf( "\nError: %s( %08lx ) = %d.  Should be %d",
                fn, i, count, CorrectCount( i ) );
  }

void test( int (*count)(unsigned long), char *fn )
  {
  unsigned long i;
  unsigned int j, k;

  srand( 100 );

  printf( "Starting... [%s] \n", fn );

  for( j=0; j <= 65000; j++ )			/* first do some random testing. */
    {
    i = ((unsigned long)rand() << 21) ^		/* a random long */
        ((unsigned long)rand() << 17) ^
         (unsigned long)rand();

    k = count(i);

    if( k != CorrectCount( i ) )
      Error( i, k, fn );
    }

  for( j=0; j <= 65000; j++ )			/* test low # of bits */
    {
    i = ( ((unsigned long)rand() << 21) & ((unsigned long)rand() << 21) ) ^
        ( ((unsigned long)rand() << 17) & ((unsigned long)rand() << 17) ) ^
        (  (unsigned long)rand()        & (unsigned long)rand()         );   

    k = count(i);

    if( k != CorrectCount( i ) )
      Error( i, k, fn );
    }

  for( j=0; j <= 65000; j++ )			/* test high # of bits */
    {
    i = ( ((unsigned long)rand() << 21) | ((unsigned long)rand() << 21) ) ^
        ( ((unsigned long)rand() << 17) | ((unsigned long)rand() << 17) ) ^
        (  (unsigned long)rand()        | (unsigned long)rand()         );   

    k = count(i);

    if( k != CorrectCount( i ) )
      Error( i, k, fn );
    }



  i = 1L;					/* Now try all permutations */
  for( j =0; j < 33; j++ )			/* with only 1 bit. */
    {						/* termination includes all 0s */
    k = count(i);
    if( i != 0 )
      {
      if( k != 1 )
        Error( i, k, fn );
      }
    else
      {
      if( k != 0 )
        Error( i, k, fn );
      }
    i <<= 1;
    }

  i = 1L;					/* Finally, all permutations */
  for( j =0; j < 33; j++ )			/* with only one 0 bit. */
    {						/* termination includes all 1s */
    k = count( ~i );
    if( i != 0 )
      {
      if( k != 31 )
        Error( ~i, k, fn );
      }
    else
      {
      if( k != 32 )
        Error( ~i, k, fn );
      }
    i <<= 1;
    }

  printf( "... Done.\n" );
  }


int main( void )
  {
  test( bit32on1, "bit32on1" );
  test( bit32on2, "bit32on2" );
  test( bit32on3, "bit32on3" );
  }