//********************************************
// PCSA.cpp
// -------------------------------------------
// Function implementations of the general
// purpose PCSA module
//
// Author: Leiwen Deng
// Date: 10/15/2005
//********************************************

#include "PCSA.h"

//************** Begin ***************
// Test1: 
// Input uniformly distributed 32-bit values to PCSA and generate the cardinality
// Hash function: no hash is performed, simply return the inputed 32-bit value

#ifdef PCSA_TEST1

int main( int argc, char * argv[] )
{
  if ( argc < 3 )
  {
    fprintf ( stderr, "Usage: PT1 <size_multiset> <m_bit>\n" );
    return 1;
  }

  int size_multiset, m_bit;
  sscanf( argv[1], "%d", &size_multiset );
  sscanf( argv[2], "%d", &m_bit );

  PCSA pcsa( m_bit, No_Hash );
  // Define the PCSA instance, set nmap_bit = 6 (64 bitmaps), use hash function "No_Hash()"
  
  uint32 value = time( 0 ) * 34141;

  for ( int i = 0; i < size_multiset; i ++ )
  {
    //************** Begin ***************
    // Generate a 32-bit random number which is uniformly distributed
    d_uniform_01( (int *)&value );
    if ( d_uniform_01() > 0.5 )
      value |= 0x80000000;
    //************** End ***************
    pcsa.InputValue( &value );
    // Input the value to PCSA
  }
  int cardinality = pcsa.GetCardinality();
  // Calculate cardinality of inputed values
  fprintf( stdout, "Test1: PCSA cardinality = %d\n", cardinality );

  return 0;
}

#endif

//*************** End ****************

//************** Begin ***************
// Test2:
// Input a sequence of size_multiset numbers and generate the cardinality
// Hash function: IP_Hash(), which calls the function "Mangler::MangleShortTable()"

#ifdef PCSA_TEST2

int main( int argc, char * argv[] )
{
  if ( argc < 3 )
  {
    fprintf ( stderr, "Usage: PT2 <size_multiset> <m_bit>\n" );
    return 1;
  }

  int size_multiset, m_bit;
  sscanf( argv[1], "%d", &size_multiset );
  sscanf( argv[2], "%d", &m_bit );

  PCSA pcsa( m_bit, IP_Hash );
  // Define the PCSA instance, set nmap_bit = 8 (256 bitmaps), use hash function "IP_Hash()"
  
  uint32 value  = (uint32)( d_uniform_01() * (double)0xFFFFFFFF );
  for ( int i = 0; i < size_multiset; i ++ )
  {
    value ++;
    pcsa.InputValue( &value );
    // Input the value to PCSA
  }

  int cardinality = pcsa.GetCardinality();
  // Calculate cardinality of inputed values
  fprintf( stdout, "Test2: PCSA cardinality = %d\n", cardinality );

  return 0;
}

#endif

//*************** End ****************

//********************************************
// PCSA( nmap_bit_in, hash_in )
// -------------------------------------------
// The constructor
//   <nmap_bit_in> specifies the "m_bit" parameter
//   <hash_in> specifies the hash function
//********************************************

PCSA::PCSA( int nmap_bit_in, HASH_FUNC hash_in )
{
  nmap_bit = nmap_bit_in;
  nmap = 1 << nmap_bit_in;
  hash = hash_in;
  InitializeBitmap();
}

//********************************************
// ~PCSA()
// -------------------------------------------
// The destructor
//********************************************

PCSA::~PCSA( void )
{
  if ( bitmap )
    delete [] bitmap;
}

//********************************************
// InitializeBitmap()
// -------------------------------------------
// Initialize the table of bitmaps
// This includes:
//   1. Allocate the space for the table
//   2. Initialize all bitmaps
//********************************************

char PCSA::InitializeBitmap( void )
{
  bitmap = new uint32[nmap];
  ResetBitmap();
  return 0;
}

//********************************************
// ResetBitmap()
// -------------------------------------------
// Initialize all bitmaps to be empty
//********************************************

char PCSA::ResetBitmap( void )
{
  int i;
  for ( i = 0; i < nmap; i ++ )
    bitmap[i] = 0;
  return 0;
}

//********************************************
// UpdateBitmap( hash_value )
// -------------------------------------------
// Update the bitmap table by inputting a hashed
// value
//********************************************

char PCSA::UpdateBitmap( uint32 hash_value )
{
  int alpha = hash_value & ( nmap - 1 );
  uint32 index = hash_value & ~( nmap - 1 );
  bitmap[alpha] |= Rou( index );
  return 0;
}

//********************************************
// mask_code = Rou( value )
// -------------------------------------------
// Calculates a 32-bit mask code of an input
// value.
// The mask code indicates the position of the
// first 1-bit in the value, rank starting at 0,
// for example: 
//   "1000 0000 0000 ..." indicates rank 0,
//   "0100 0000 0000 ..." indicates rank 1,
//   "0000 0100 0000 ..." indicates rank 5.
// Return the mask code calculated.
//********************************************

uint32 PCSA::Rou( uint32 value ) const
{
  int nbit = 32 - nmap_bit;
  uint32 mask_code = 0x80000000;
  int i;
  for ( i = 0; i < nbit; i ++ )
  {
    if ( value & mask_code )
      break;
    mask_code >>= 1;
  }
  if ( i >= nbit )
    mask_code = 0;
  return mask_code;
}

double d_uniform_01( int * seed )
//******************************************************************************
//
//  Purpose:
//
//    D_UNIFORM_01 is a portable pseudorandom number generator.
//
//  Discussion:
//
//    This routine implements the recursion
//
//      seed = 16807 * seed mod ( 2**31 - 1 )
//      unif = seed / ( 2**31 - 1 )
//
//    The integer arithmetic never requires more than 32 bits,
//    including a sign bit.
//
//  Modified:
//
//    11 August 2004
//
//  Author:
//
//    John Burkardt
//
//  Reference:
//
//    Paul Bratley, Bennett Fox, L E Schrage,
//    A Guide to Simulation,
//    Springer Verlag, pages 201-202, 1983.
//
//    Bennett Fox,
//    Algorithm 647:
//    Implementation and Relative Efficiency of Quasirandom
//    Sequence Generators,
//    ACM Transactions on Mathematical Software,
//    Volume 12, Number 4, pages 362-376, 1986.
//
//  Parameters:
//
//    Input/output, int *SEED, the "seed" value.  Normally, this
//    value should not be 0.  On output, SEED has been updated.
//
//    Output, double D_UNIFORM_01, a new pseudorandom variate, strictly between
//    0 and 1.
//
{
  int k;
  double r;

  k = *seed / 127773;

  *seed = 16807 * ( *seed - k * 127773 ) - k * 2836;

  if ( *seed < 0 )
  {
    *seed = *seed + 2147483647;
  }
//
//  Although SEED can be represented exactly as a 32 bit integer,
//  it generally cannot be represented exactly as a 32 bit real number!
//
  r = ( double ) ( *seed ) * 4.656612875E-10;

  return r;
}

// The compact version of above d_uniform_01
double d_uniform_01( void )
{
  static int seed = (int)time( 0 ) * 8888;
  return d_uniform_01( &seed );
}


//********************************************
// InputValue( value )
// -------------------------------------------
// Input an element of the multiset to the
// counting system
//   <value> specifies the value of the input
//   element
//********************************************

char PCSA::InputValue( const void * value )
{
  UpdateBitmap( hash( value ) );
  return 0;
}

//********************************************
// cardinality = GetCardinality()
// -------------------------------------------
// Calculate the PCSA cardinality of the
// inputted multiset.
// Return the cardinality calculated.
//********************************************

#define PHY 0.77351

int PCSA::GetCardinality( void ) const
{
  int nbit = 32 - nmap_bit;
  int S = 0;
  for ( int i = 0; i < nmap; i ++ )
  {
    int R;
    int cur_bitmap = bitmap[i];
    for ( R = 0; R < nbit; R ++ )
    {
      if ( ( cur_bitmap & 0x80000000 ) == 0 )
        break;
      cur_bitmap <<= 1;
    }
    S += R;
    // fprintf( stdout, "bitmap[%02d]: %08X, R = %d\n", i, bitmap[i], R );
  }
  int cardinality = (int)( (double)nmap / ( PHY * ( 1 + 0.31 / (double)nmap ) ) * pow( 2.0, (double)S / (double)nmap ) );
  return cardinality;
}

//********************************************
// hashed_value = IP_Hash( key )
// -------------------------------------------
// A hash function used for mangling the 32-bit
// IPv4 address
//********************************************

uint32 IP_Hash( const void * key )
{
#ifdef WINXP
  return *(uint32 *)key;
#else
  static Mangler mangler; // The Mangler instance
  return mangler.MangleShortTable( * (uint32 *)key);
#endif
}

//********************************************
// hashed_value = No_Hash( key )
// -------------------------------------------
// A fake hash function for 32-bit integers.
// It directly returns the inputted integer as
// the hashed value.
//********************************************

uint32 No_Hash( const void * key )
{
  return *(uint32 *)key;
}