vmhash.h

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

#ifndef VM_SUPER_HASH_H_INCLUDED
#define VM_SUPER_HASH_H_INCLUDED
/*****************************************************************************/
/*                           HEADER FILE                                     */
/*****************************************************************************/
/*
       $Archive:   $

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

   Description: 

                      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.
*/
/*****************************************************************************/

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

typedef  unsigned long  int  ub4;   // unsigned 4-byte quantities 
typedef  unsigned       char ub1;   // unsigned 1-byte quantities 

#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)


/* 
mix -- mix 3 32-bit values reversibly.

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 a,b,c
is almost all zero or is uniformly distributed,

* If mix() is run forward or backward, at least 32 bits in a,b,c
  have at least 1/4 probability of changing.

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

* mix() 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.
*/

#define mix(a,b,c)              \
{                               \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8);  \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12); \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5);  \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}


class VMSuperHash
{
public:
    VMSuperHash(){;};
   ~VMSuperHash(){;};

   UINT HashKeyGenerator( const char* k, ub4 length = 0, ub4 initval = 0 );
   UINT HashString( const char* pchToHash );
};


#endif

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