hashchars.cpp

TOOL (Tiny Object Oriented Language) is an easily-embedded, object-oriented, C++-like-language inter

  unsigned long lHash;
  unsigned long lTemp;

  for ( lHash = lLength, lTemp = 0; lTemp < lLength; ++lTemp )
    lHash = achTable[ lHash ^ pchKey[ lTemp ] ];  

  return( lHash );
}
/* End of function "CharHashes::PearsonHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::CRCHash

       DESCRIPTION:  Implementation of a CRC Hash Algorithm

             INPUT:  pchKey - the key to encode
                     lLength - the length of the key
                     lMask - 
                     laTable - 
            OUTPUT:  

           RETURNS:  the CRC Hash value for the given key
*/
unsigned long CharHashes::CRCHash( const unsigned char* pchKey, 
                                   unsigned long        lLength, 
                                   unsigned long        lMask )
{
  return( CRCHash( pchKey, lLength, lMask, m_CRCTable[ 0 ] ) );
}
unsigned long CharHashes::CRCHash( const unsigned char* pchKey, 
                                   unsigned long        lLength, 
                                   unsigned long        lMask,
                                   unsigned long        laTable[ 256 ] )
{
  unsigned long lHash;
  unsigned long lTemp;

  for ( lHash = lLength, lTemp = 0; lTemp < lLength; ++lTemp )    
    lHash = ( lHash << 8 ) ^ laTable[ ( lHash >> 24 ) ^ pchKey[ lTemp ] ];

  return( lHash & lMask );
}
/* End of function "CharHashes::CRCHash"
/*****************************************************************************/


/*
unsigned long get_crc( FILE *fp)   
{
  unsigned long crc;
  int char;
  crc = 0xFFFFFFFF;
  while ( ( char = getc( fp ) ) != EOF )
    crc = ( ( crc>>8 ) & 0x00FFFFFF ) ^ crc_table[ (crc^char) & 0xFF ];

  return( crc ^ 0xFFFFFFFF );
}

#define TEST(f,x)  (*(f+((x)>>4))&(1<<(((x)&15L)>>1)))
#define SET(f,x)  *(f+((x)>>4))|=1<<(((x)&15L)>>1)
void main( int argc, char *argv[])
{
  unsigned char *feld = NULL, *zzz;
  unsigned long teste = 1, max, mom, hits=1, count, alloc, s=0, e=1;

  time_t begin;

  if ( argc > 1 )
    max = atol (argv[1]) + 10000;  
  else
    max = 14010000L;

  while ( feld == NULL )
    zzz = feld = malloc ( alloc = ( ( ( max -= 10000L ) >> 4 ) +1L ) );

  for ( count = 0; count < alloc; count++ ) 
    *zzz++ = 0x00;

  printf( "Searching prime numbers to : %ld\n", max );  

  begin = time( NULL );

  while (( teste += 2 ) < max )
    if ( !TEST( feld, teste ) ) 
    {
      if ( ++hits % 2000L == 0) 
      {
        printf( " %ld. prime number\x0d", hits); 
        fflush(stdout);
      }
      for ( mom = 3L * teste; mom < max; mom += teste << 1 ) 
        SET (feld, mom);
    }

  printf(" %ld prime numbers foundn %ld secs.\n\nShow prime numbers", 
         hits, 
         time(NULL) - begin );

  while (s<e) 
  {
    printf ("\n\nStart of Area : "); 
    fflush (stdout); 
    scanf ("%ld", &s);
    printf ("End   of Area : ");
    fflush (stdout); 
    scanf ("%ld", &e);

    count = s - 2; 
    if ( s % 2 == 0 ) 
      count++;

    while ((count+=2)<e) 
      if (!TEST(feld,count)) printf ("%ld\t", count);
   }
   free (feld);
}

int main (int argc, char **argv)
{
  long unsigned ixt[sizeof(primetable)>>2],*ix,i,j,nsp,n=0,max,m;
  char sieve[1<<17],*sp;  

  if(argv[1])
  {
    max=atoi(argv[1]);
    for(nsp=0;primetable[nsp]<=(unsigned)sqrt(max);nsp++);
  }
  else
  {
    nsp=sizeof(primetable)>>2;max=0xffffffff;
  };

  printf("%u\n",2);
  for(i=0;i<nsp;i++)ixt[i]=((primetable[i]*3+1)>>1)+(1<<17);
    for(j=0;j<1<<14;j++)
    {
      memset(sieve,1,1<<17);
      for(ix=ixt+nsp-1;ix>=ixt;ix--)
        for(*ix-=1<<17;*ix<1<<17;*ix+=*(primetable+(ix-ixt)))
          sieve[*ix]=0;
      for(i=0;i<(1<<17);i++)if(sieve[i])
      {
        if((m=((j<<17)+i)<<1)>max)
          return 0;
        else 
        if(m>2)
          printf("%ld\t",m-1);
       }
    }
}

*/

/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::TypicalHash

       DESCRIPTION:  Implemenation of the Typical Hash Algorithm

             INPUT:  pchKey - the key to encode
                     lPrime - prime number
            OUTPUT:  

           RETURNS:  the Typical Hash vale for the given key 
*/
unsigned long CharHashes::TypicalHash( const unsigned char* pchKey, 
                                       unsigned long        lPrime )
{
  unsigned long lHash = 0;

  for ( unsigned long iLoop = 0; iLoop < lHash; ++iLoop )  
    lHash ^= ( ( lHash << 5 ) ^ ( lHash >> 27 ) ) ^ pchKey[ iLoop ];

  return( lHash % lPrime );
}
/* End of function "CharHashes::TypicalHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::AdditiveHash

       DESCRIPTION:  Implementation the Additive Hash algorithm

             INPUT:  pchKey - the key to encode
                     lLength - the length of the key
                     lPrime - a prime number
            OUTPUT:  

           RETURNS:  the Additive Hash value for the given key
*/
unsigned long CharHashes::AdditiveHash( const unsigned char* pchKey, 
                                        unsigned long        lLength, 
                                        unsigned long        lPrime )
{  
  unsigned long lHash;
  unsigned long lTemp;

  for ( lHash = lLength, lTemp = 0; lTemp < lLength; ++lTemp )
    lHash += pchKey[ lTemp ];  

  return( lHash % lPrime );
}
/* End of function "CharHashes::AdditiveHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::RotatingHash

       DESCRIPTION:  Implementation of the Rotating Hash algorithm

             INPUT:  pchKey - the key to encode
                     lLength - the length of the key
                     lPrime - prime number
            OUTPUT:  

           RETURNS:  the Rotating Hash vale for the given key
*/
unsigned long CharHashes::RotatingHash( const unsigned char* pchKey, 
                                        unsigned long        lLength, 
                                        unsigned long        lPrime ) 
{  
  unsigned long lHash;
  unsigned long lTemp;

  for ( lHash = lLength, lTemp = 0; lTemp < lLength; ++lTemp )
    lHash = ( lHash << 5 ) ^ ( lHash >> 27 ) ^ pchKey[ lTemp ];

  return( lHash % lPrime );
}
/* End of function "CharHashes::RotatingHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::UniversalHash

       DESCRIPTION:  Implementation of the Universal Hash Algorithm

             INPUT:  pchKey - the key to encode
                     lLength - the length of the key
                     lMask - 
                     laTable - 
            OUTPUT:  

           RETURNS:  the Universal Hash value for the given key
*/
unsigned long CharHashes::UniversalHash( const unsigned char* pchKey, 
                                         unsigned long        lLength, 
                                         unsigned long        lMask )
{
  return( UniversalHash( pchKey, lLength, lMask, m_CRCTable[ 0 ] ) );
}
unsigned long CharHashes::UniversalHash( const unsigned char* pchKey, 
                                         unsigned long        lLength, 
                                         unsigned long        lMask, 
                                         unsigned long        laTable[ CHAR_BIT ] )
{
  unsigned long lHash;
  unsigned long lTemp;

  for ( lHash = lLength, lTemp = 0; lTemp < ( lLength << 3 ); lTemp += 8 )  
  {
    char aChar = pchKey[ lTemp >> 3 ];

    if ( aChar & 0x01 ) 
      lHash ^= laTable[ lTemp + 0 ];

    if ( aChar & 0x02 ) 
      lHash ^= laTable[ lTemp + 1 ];

    if ( aChar & 0x04 ) 
      lHash ^= laTable[ lTemp + 2 ];

    if ( aChar & 0x08 ) 
      lHash ^= laTable[ lTemp + 3 ];

    if ( aChar & 0x10 ) 
      lHash ^= laTable[ lTemp + 4 ];

    if ( aChar & 0x20 ) 
      lHash ^= laTable[ lTemp + 5 ];

    if ( aChar & 0x40 ) 
      lHash ^= laTable[ lTemp + 6 ];

    if ( aChar & 0x80 )
      lHash ^= laTable[ lTemp + 7 ];  
   }
   return ( lHash & lMask );
}
/* End of function "CharHashes::UniversalHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::ZobristHash

       DESCRIPTION:  Implementation of Zobrist Hash Algorithm

             INPUT:  pchKey - the key to encode
                     lLength - the length of the key
                     lMask - 
                     laTable - 
            OUTPUT:  

           RETURNS:  the Zobrist Hash value for the given key
*/
unsigned long CharHashes::ZobristHash( const unsigned char* pchKey, 
                                       unsigned long        lLength, 
                                       unsigned long        lMask )
{
  return( ZobristHash( pchKey, lLength, lMask, m_CRCTable ) );
}
unsigned long CharHashes::ZobristHash( const unsigned char* pchKey, 
                                       unsigned long        lLength, 
                                       unsigned long        lMask, 
                                       unsigned long        laTable[ CHAR_BIT ][ 256 ] )
{
  unsigned long lHash;
  unsigned long lTemp;

  for ( lHash = lLength, lTemp = 0; lTemp < lLength; ++lTemp )
    lHash ^= laTable[ lTemp ][ pchKey[ lTemp ] ];

  return( lHash & lMask );
}
/* End of function "CharHashes::ZobristHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::GenerateTable

       DESCRIPTION:  Fills the CRC table with polynomial values

             INPUT:  void
            OUTPUT:  none

           RETURNS:  void 
*/
void CharHashes::GenerateTable( void )
{
  unsigned long ulCRC;
  unsigned long ulPoly;
  int  iLoop;
  int jLoop;
    
  ulPoly = 0xEDB88320L;

  for ( iLoop = 0; iLoop < 256 * CHAR_BIT; iLoop++ )
  {
    ulCRC = iLoop;
    for ( jLoop = 8; jLoop > 0; jLoop-- )
    {
      if ( ulCRC & 1 )
        ulCRC = ( ulCRC >> 1) ^ ulPoly;
      else
        ulCRC >>= 1;
    }
    m_CRCTable[ iLoop % CHAR_BIT ][ iLoop % 256 ] = ulCRC;
  }
}
/* End of function "CharHashes::GenerateTable"
/*****************************************************************************/


/*****************************************************************************/
/* Check-in history */
/*
 *$Log:  $
*/
/*****************************************************************************/