identon2 check

gistfile1.cpp

// file: identon2.cpp
//
// gcc -xc++ -lstdc++ identon2.cpp 
// CL /TP /EHsc identon2.cpp 


#include <limits.h>
#include <sstream>
#include <iostream>

const size_t byte_size__ = 8;

void identon2_test ( int max, int prime );
void flags_test ();

int identon2 ( int index, int max, int prime );

void set_flag( char* flags, int index );
bool get_flag( char* flags, int index );
void dump_flags( char* flags, size_t flags_bytes );
std::string char2bits( char bits );


int main ( int argc, char** argv )
{
  int max   = INT_MAX;
  int prime = 3;

  //identon2_test ( max, prime );
  flags_test ();

}


void identon2_test ( int max, int prime )
{
  int flags_bytes = (max / byte_size__ ) + 1;
  char* flags = new char[ flags_bytes ];

  bool is_ok = true;
  for( int i = 0; i < max; ++i )
    {
      int val = identon2( i, max, prime );

      //      std::cout << i << ":" << val << std::endl;

      if( get_flag ( flags, val ) )
	{
	  is_ok = false;
	  break;
	}
      else
	{
	  set_flag ( flags, val );
	}
    }

  delete [] flags;


  if( is_ok )
    std::cout << "ok!!" << std::endl;
  else
    std::cout << "ng.." << std::endl;

}


void flags_test ()
{
  int max = 64;

  int flags_bytes = (max / byte_size__ ) + 1;
  char* flags = new char[ flags_bytes ];

  dump_flags( flags, flags_bytes );


  set_flag( flags, 0 );  std::cout << "set:0" << std::endl;
  set_flag( flags, 15 ); std::cout << "set:15" << std::endl;
  set_flag( flags, 16 ); std::cout << "set:16" << std::endl;
  set_flag( flags, 37 ); std::cout << "set:37" << std::endl;
  set_flag( flags, 38 ); std::cout << "set:38" << std::endl;
  set_flag( flags, 39 ); std::cout << "set:39" << std::endl;
  set_flag( flags, 40 ); std::cout << "set:40" << std::endl;
  set_flag( flags, 62 ); std::cout << "set:62" << std::endl;
  set_flag( flags, 63 ); std::cout << "set:63" << std::endl;
  set_flag( flags, 64 ); std::cout << "set:64" << std::endl;

  dump_flags( flags, flags_bytes );


  for( size_t i = 0; i <= max; ++i )
    {
      std::cout << i << ":" << get_flag( flags, i ) << std::endl;
    }


  delete [] flags;
  
}



int identon2 ( int index, int max, int prime )
{
  long long l_index = index;
  long long l_max   = max;
  long long l_prime = prime;

  return ( l_index * l_prime ) % l_max;
}

void set_flag( char* flags, int index )
{
  size_t byte_pos = index / byte_size__;
  size_t bit_pos  = index % byte_size__;

  char bit = 1 << bit_pos; 

  flags[byte_pos] = flags[byte_pos] | bit;
}


bool get_flag( char* flags, int index )
{
  size_t byte_pos = index / byte_size__;
  size_t bit_pos  = index % byte_size__;

  char bit = 1 << bit_pos; 

  return ( flags[byte_pos] & bit );
}


void dump_flags( char* flags, size_t flags_bytes )
{

  for ( size_t i = 0; i < flags_bytes; ++i )
    {
      std::cout << char2bits( flags[i] ) << ":";
      if( i % 8 == 7 )  std::cout << std::endl;
    }
  std::cout << std::endl;
}


std::string char2bits( char bits )
{

  char buff[] = "00000000";

  char bit = 1;
  for ( size_t i = 0; i < byte_size__; ++i )
    {
      if ( bits & bit )
	{
	  buff[i] = '1';
	}
      else
	{
	  buff[i] = '0';
	}
      bit <<= 1;
    }

  std::ostringstream out;
  out << buff;

  return out.str();
 
}