hashchars.cpp

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

/*****************************************************************************/
/*                              SOURCE FILE                                  */
/*****************************************************************************/
/*
       $Archive:   $

      $Revision:   $
          $Date:   $
        $Author:   $

    Description:   a class that has a collection of hash functions. You're 
                   sure to find one you'll like

                   NOTE: None of these hashes are crypto strength. For crypto
                   hashes refer to implementations of MD-5 or SHA-1 (or better)

                      TOOL And XML FORMS License
                      ==========================

                      Except where otherwise noted, all of the documentation 
                      and software included in the TOOL package is 
                      copyrighted by Michael Swartzendruber.

                      Copyright (C) 2005 Michael John Swartzendruber. 
                      All rights reserved.

                      Access to this code, whether intentional or accidental,
                      does NOT IMPLY any transfer of rights.

                      This software is provided "as-is," without any express 
                      or implied warranty. In no event shall the author be held
                      liable for any damages arising from the use of this software.

                      Permission is granted to anyone to use this software for 
                      any purpose, including commercial applications, and to 
                      alter and redistribute it, provided that the following 
                      conditions are met:

                      1. All redistributions of source code files must retain 
                         all copyright notices that are currently in place, 
                         and this list of conditions without modification.

                      2. The origin of this software must not be misrepresented;
                         you must not claim that you wrote the original software.

                      3. If you use this software in another product, an acknowledgment
                         in the product documentation would be appreciated but is
                         not required.

                      4. Modified versions in source or binary form must be plainly 
                         marked as such, and must not be misrepresented as being 
                         the original software.
*/
static char OBJECT_ID[] = "$Revision:   $ : $Date:   $";
/*****************************************************************************/



#include <limits.h>
#include "HashChars.h"



/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::MaxHashSize

       DESCRIPTION:  sets a clip mask

             INPUT:  ulN - sets the rotation count
            OUTPUT:  none

           RETURNS:  1 SHL by ulN
*/
unsigned long CharHashes::MaxHashSize( unsigned long ulN )
{
  return( 1 << ulN );
}
/* End of function "CharHashes::MaxHashSize"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::MakeMask

       DESCRIPTION:  makes a mask ulN bits wide

             INPUT:  ulN - the number of bits to include in the mask
            OUTPUT:  none

           RETURNS:  a mask that will pass 'ulN' bits through it
*/
unsigned long CharHashes::MakeMask( unsigned long ulN )
{
  return( MaxHashSize( ulN ) - 1 );
}
/* End of function "CharHashes::MakeMask"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::MixBits

       DESCRIPTION:  Reversably mixes 3 32-bit values

                     For every delta with one or two bits set, and the deltas 
                     of all three high bits or all three low bits, whether the 
                     original value of rulA, rulB, rulC is almost all zero or 
                     is uniformly distributed,

                     If MixBits() is run forward or backward, at least 32 bits 
                     in rulA, rulB, rulC have at least 1/4 probability of 
                     changing.

                     If MixBits() is run forward, every bit of rulC will change 
                     between 1/3 and 2/3 of the time. (Well, 22/100 and 78/100 
                     for some 2-bit deltas.)

                     MixBits() takes 36 machine instructions, but only 18 
                     cycles on a superscalar machine (like a Pentium or a Sparc).
                     No faster mixer seems to work, that's the result of my 
                     brute-force search.  There were about 2^68 hashes to choose from.
                     I only tested about a billion of those

             INPUT:  rulA - reference to a long to mix up
                     rulB - reference to a long to mix up
                     rulC - reference to a long to mix up
            OUTPUT:  contents of all parameters is changed

           RETURNS:  void  
*/
void CharHashes::MixBits( unsigned long& rulA, unsigned long& rulB, unsigned long& rulC )
{                                 
  rulA -= rulB; 
  rulA -= rulC; 
  rulA ^= ( rulC >> 13 );

  rulB -= rulC; 
  rulB -= rulA; 
  rulB ^= ( rulA << 8 );   

  rulC -= rulA; 
  rulC -= rulB; 
  rulC ^= ( rulB >> 13 );

  rulA -= rulB; 
  rulA -= rulC; 
  rulA ^= ( rulC >> 12 );  

  rulB -= rulC; 
  rulB -= rulA; 
  rulB ^= ( rulA << 16 );

  rulC -= rulA; 
  rulC -= rulB; 
  rulC ^= ( rulB >> 5 );   

  rulA -= rulB; 
  rulA -= rulC; 
  rulA ^= ( rulC >> 3 ); 

  rulB -= rulC; 
  rulB -= rulA; 
  rulB ^= ( rulA << 10 );  

  rulC -= rulA; 
  rulC -= rulB; 
  rulC ^= ( rulB >> 15 );
}
/* End of function "CharHashes::MixBits"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::JenkinsHash

       DESCRIPTION:  Implementation of the Jenkins Hash Algorithm

                     NOTES FROM ORIGINAL AUTHOR:

                     Returns a 32-bit value. Every bit of the key affects every 
                     bit of the return value. Every 1-bit and 2-bit delta achieves 
                     avalanche. About 6 * len + 35 instructions.

                     The best hash table sizes are powers of 2. There is no need 
                     to do mod a prime (mod is sooo slow!). If you need less than 
                     32 bits, use a bitmask.  For example, if you need only 10 bits, 
                     do h = ( h & MakeMask( 10 ) );

                     In which case, the hash table should have hashsize(10) 
                     elements. If you are hashing n strings (ub1**)k, do it like 
                     this:

                     for (i = 0,h = 0; i < n; ++i ) 
                       h = hash( k[ i ], len[ i ], h );

                     By Bob Jenkins, 1996. [e-mail]. You may use 
                     this code any way you wish, private, educational, or commercial.
                     It's free. See 
                     http://ourworld.compuserve.com/homepages/bob_jenkins/evahash.htm

                     Use for hash table lookup, or anything where one collision 
                     in 2^^32 is acceptable. 

                     Do NOT use for cryptographic purposes.

             INPUT:  pchKey - the key to encode
                     lLength - the length of the key
                     lSeed - can be any 4-byte value
            OUTPUT:  

           RETURNS:  The Jenkins Hash value for the given key
*/
unsigned long CharHashes::JenkinsHash( const unsigned char* pchKey, 
                                       unsigned long        lLength, 
                                       unsigned long        lSeed )
{
  unsigned long ulA;
  unsigned long ulB;
  unsigned long ulC;

  unsigned long lInternalLength;  // Set up the internal state 

  lInternalLength = lLength;
  ulA = ulB = 0x9e3779b9;        // the golden ratio; an arbitrary value 
  ulC = lSeed;                   // the previous hash value 
   
  // handle most of the key
  //
  while ( lInternalLength >= 12 )   
  {
    ulA += ( pchKey[ 0 ] 
       + ( (unsigned long)pchKey[ 1 ] << 8 ) 
       + ( (unsigned long)pchKey[ 2 ] << 16 ) 
       + ( (unsigned long)pchKey[ 3 ] << 24 ) );

    ulB += ( pchKey[ 4 ] 
       + ( (unsigned long)pchKey[ 5 ] << 8 ) 
       + ( (unsigned long)pchKey[ 6 ] << 16 ) 
       + ( (unsigned long) pchKey[ 7 ] << 24 ) );

    ulC += ( pchKey[ 8 ] 
       + ( (unsigned long) pchKey[ 9 ] << 8 ) 
       + ( (unsigned long) pchKey[ 10 ] << 16 )
       + ( (unsigned long) pchKey[ 11 ] << 24 ) );

    MixBits( ulA, ulB, ulC );
    pchKey += 12; 
    lInternalLength -= 12;
  }

  // handle the last 11 bytes
  //
  ulC += lLength;
  switch( lInternalLength ) 
  {
    // NOTE: all the case statements fall through
    //
    case 11: 
      ulC += ( (unsigned long)pchKey[ 10 ] << 24 );   
    case 10: 
      ulC += ( (unsigned long)pchKey[ 9 ] << 16 );
    case 9: 
      ulC += ( (unsigned long)pchKey[ 8 ] << 8 );
    //
    // the first byte of ulC is reserved for the lLength
    //
    case 8: 
      ulB += ( (unsigned long)pchKey[ 7 ] << 24 );   
    case 7: 
      ulB += ( (unsigned long)pchKey[ 6 ] << 16 );
    case 6: 
      ulB += ( (unsigned long)pchKey[ 5 ] << 8 );   
    case 5: 
      ulB += pchKey[ 4 ];
    //
    //
    case 4: 
      ulA += ( (unsigned long)pchKey[ 3 ] << 24 );   
    case 3: 
      ulA += ( (unsigned long)pchKey[ 2 ] << 16 );
    case 2: 
      ulA += ( (unsigned long)pchKey[ 1 ] << 8 );   
    case 1: 
      ulA += pchKey[0];
    //
    // case 0: nothing left to add 
    //
  }   
  MixBits( ulA, ulB, ulC );
  //
  // report the result
  //
  return( ulC );
}
/* End of function "CharHashes::JenkinsHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::WeinbergerHash

       DESCRIPTION:  Implementation of the Weinberger Hash Algorithm based on
                     Allen Holub's version

             INPUT:  pchKey - the key to encode
            OUTPUT:  none

           RETURNS:  the Weinberger Hash value for the given key
*/
unsigned long CharHashes::WeinbergerHash( const unsigned char* pchKey )
{
  unsigned long ulHash;
  unsigned long ulTemp;

  for ( ulHash = 0; *pchKey; ++pchKey )
  {
    ulHash = ( ulHash << ONE_EIGHTH ) + *pchKey;

    if ( ( ulTemp = ulHash & HIGH_BITS ) != 0 )
      ulHash = ( ulHash ^ ( ulTemp >> THREE_QUARTERS ) ) & ~HIGH_BITS;
  }
  return ( ulHash );
}
/* End of function "CharHashes::WeinbergerHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::ElfHash

       DESCRIPTION:  Implementation of the Elf Hash Algorithm

             INPUT:  pchKey - the key to encode
            OUTPUT:  none

           RETURNS:  the Elf Hash value for the given key
*/
unsigned long CharHashes::ElfHash( const unsigned char* pchKey )
{
  unsigned long ulHash = 0;
  unsigned long ulTemp;

  while ( *pchKey )
  {
    ulHash = ( ulHash << 4 ) + *pchKey++;

    if ( ulTemp = ulHash & 0xF0000000 )
      ulHash ^= ulTemp >> 24;

    ulHash &= ~ulTemp;
  }
  return( ulHash );
}
/* End of function "CharHashes::ElfHash"
/*****************************************************************************/


/*****************************************************************************/
/*
     FUNCTION NAME:  CharHashes::PearsonHash

       DESCRIPTION:  Implementation of the Pearson Hash Algorithm

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

           RETURNS:  the Pearson Hash vale for the given key
*/
unsigned long CharHashes::PearsonHash( const unsigned char* pchKey, 
                                       unsigned long        lLength )
{
  return( PearsonHash( pchKey, lLength, m_CRCTable[ 0 ] ) );
} 
unsigned long CharHashes::PearsonHash( const unsigned char* pchKey, 
                                       unsigned long        lLength, 
                                       const unsigned long  achTable[ 256 ] ) 
{