git.sur5r.net Git - cc65/blob - src/common/hashfunc.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                hashfunc.c                                 */
   4 /*                                                                           */
   5 /*                              Hash functions                               */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 1998-2011, Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                D-70794 Filderstadt                                        */
  12 /* EMail:         uz@cc65.org                                                */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 /* common */
  37 #include "hashfunc.h"
  38
  39
  40
  41 /*****************************************************************************/
  42 /*                                   Code                                    */
  43 /*****************************************************************************/
  44
  45
  46
  47 unsigned HashInt (unsigned V)
  48 /* Return a hash value for the given integer. The function uses Robert
  49 ** Jenkins' 32 bit integer hash function taken from
  50 **     http://www.concentric.net/~ttwang/tech/inthash.htm
  51 ** For 16 bit integers, the function may be suboptimal.
  52 */
  53 {
  54    V = (V + 0x7ed55d16) + (V << 12);
  55    V = (V ^ 0xc761c23c) ^ (V >> 19);
  56    V = (V + 0x165667b1) + (V << 5);
  57    V = (V + 0xd3a2646c) ^ (V << 9);
  58    V = (V + 0xfd7046c5) + (V << 3);
  59    V = (V ^ 0xb55a4f09) ^ (V >> 16);
  60    return V;
  61 }
  62
  63
  64
  65 unsigned HashStr (const char* S)
  66 /* Return a hash value for the given string */
  67 {
  68     unsigned L, H;
  69
  70     /* Do the hash */
  71     H = L = 0;
  72     while (*S) {
  73         H = ((H << 3) ^ ((unsigned char) *S++)) + L++;
  74     }
  75     return H;
  76 }
  77
  78
  79
  80 unsigned HashBuf (const StrBuf* S)
  81 /* Return a hash value for the given string buffer */
  82 {
  83     unsigned I, L, H;
  84
  85     /* Do the hash */
  86     H = L = 0;
  87     for (I = 0; I < SB_GetLen (S); ++I) {
  88         H = ((H << 3) ^ ((unsigned char) SB_AtUnchecked (S, I))) + L++;
  89     }
  90     return H;
  91 }