include/plugin_interface/Hash.h

   1 /*
   2         SuperCollider real time audio synthesis system
   3     Copyright (c) 2002 James McCartney. All rights reserved.
   4         http://www.audiosynth.com
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  19 */
  20
  21
  22 #ifndef _Hash_
  23 #define _Hash_
  24
  25 #include "SC_Types.h"
  26 #include "SC_Endian.h"
  27
  28 // These hash functions are among the best there are in terms of both speed and quality.
  29 // A good hash function makes a lot of difference.
  30 // I have not used Bob Jenkins own hash function because the keys I use are relatively short.
  31
  32
  33 // hash function for a string
  34 inline int32 Hash(const char *inKey)
  35 {
  36     // the one-at-a-time hash.
  37     // a very good hash function. ref: a web page by Bob Jenkins.
  38     // http://www.burtleburtle.net/bob/hash/doobs.html
  39     int32 hash = 0;
  40     while (*inKey) {
  41         hash += *inKey++;
  42         hash += hash << 10;
  43         hash ^= hash >> 6;
  44     }
  45     hash += hash << 3;
  46     hash ^= hash >> 11;
  47     hash += hash << 15;
  48     return hash;
  49 }
  50
  51 // hash function for a string that also returns the length
  52 inline int32 Hash(const char *inKey, int32 *outLength)
  53 {
  54     // the one-at-a-time hash.
  55     // a very good hash function. ref: a web page by Bob Jenkins.
  56     const char *origKey = inKey;
  57     int32 hash = 0;
  58     while (*inKey) {
  59         hash += *inKey++;
  60         hash += hash << 10;
  61         hash ^= hash >> 6;
  62     }
  63     hash += hash << 3;
  64     hash ^= hash >> 11;
  65     hash += hash << 15;
  66     *outLength = inKey - origKey;
  67     return hash;
  68 }
  69
  70 // hash function for an array of char
  71 inline int32 Hash(const char *inKey, int32 inLength)
  72 {
  73     // the one-at-a-time hash.
  74     // a very good hash function. ref: a web page by Bob Jenkins.
  75     int32 hash = 0;
  76     for (int i=0; i<inLength; ++i) {
  77         hash += *inKey++;
  78         hash += hash << 10;
  79         hash ^= hash >> 6;
  80     }
  81     hash += hash << 3;
  82     hash ^= hash >> 11;
  83     hash += hash << 15;
  84     return hash;
  85 }
  86
  87 // hash function for integers
  88 inline int32 Hash(int32 inKey)
  89 {
  90     // Thomas Wang's integer hash.
  91     // http://www.concentric.net/~Ttwang/tech/inthash.htm
  92     // a faster hash for integers. also very good.
  93     uint32 hash = (uint32)inKey;
  94     hash += ~(hash << 15);
  95     hash ^=   hash >> 10;
  96     hash +=   hash << 3;
  97     hash ^=   hash >> 6;
  98     hash += ~(hash << 11);
  99     hash ^=   hash >> 16;
 100     return (int32)hash;
 101 }
 102
 103 inline int64 Hash64(int64 inKey)
 104 {
 105     // Thomas Wang's 64 bit integer hash.
 106         uint64 hash = (uint64)inKey;
 107         hash += ~(hash << 32);
 108         hash ^=  (hash >> 22);
 109         hash += ~(hash << 13);
 110         hash ^=  (hash >> 8);
 111         hash +=  (hash << 3);
 112         hash ^=  (hash >> 15);
 113         hash += ~(hash << 27);
 114         hash ^=  (hash >> 31);
 115         return (int64)hash;
 116 }
 117
 118 inline int32 Hash(const int32 *inKey, int32 inLength)
 119 {
 120     // one-at-a-time hashing of a string of int32's.
 121     // uses Thomas Wang's integer hash for the combining step.
 122     int32 hash = 0;
 123     for (int i=0; i<inLength; ++i) {
 124         hash = Hash(hash + *inKey++);
 125     }
 126     return hash;
 127 }
 128
 129 #ifndef _LASTCHAR_
 130 #define _LASTCHAR_
 131 #if BYTE_ORDER == LITTLE_ENDIAN
 132 const int32 kLASTCHAR = 0xFF000000;
 133 #else
 134 const int32 kLASTCHAR = 0x000000FF;
 135 #endif
 136 #endif
 137
 138 inline int32 Hash(const int32 *inKey)
 139 {
 140     // hashing of a string of int32's.
 141     // uses Thomas Wang's integer hash for the combining step.
 142         int32 hash = 0;
 143     int32 c;
 144         do {
 145         c = *inKey++;
 146                 hash = Hash(hash + c);
 147         } while (c & kLASTCHAR);
 148     return hash;
 149 }
 150
 151 #endif
 152