src/opr/jhash.h

   1 /*
   2  * Copyright (c) 2006 Bob Jenkins
   3  * Copyright (c) 2011 Your File System Inc.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 /* This is an OPR version of Bob Jenkins' hash routines. His original copyright
  27  * declaration reads:
  28  *
  29  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  30  *
  31  * You can use this free for any purpose.  It's in the public domain.
  32  * It has no warranty.
  33  */
  34
  35 #ifndef OPENAFS_OPR_JHASH_H
  36 #define OPENAFS_OPR_JHASH_H 1
  37
  38 #define opr_jhash_size(n) ((afs_uint32)1<<(n))
  39 #define opr_jhash_mask(n) (opr_jhash_size(n)-1)
  40 #define opr_jhash_rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
  41
  42 #define opr_jhash_mix(a,b,c) \
  43 { \
  44     a -= c;  a ^= opr_jhash_rot(c, 4);  c += b; \
  45     b -= a;  b ^= opr_jhash_rot(a, 6);  a += c; \
  46     c -= b;  c ^= opr_jhash_rot(b, 8);  b += a; \
  47     a -= c;  a ^= opr_jhash_rot(c,16);  c += b; \
  48     b -= a;  b ^= opr_jhash_rot(a,19);  a += c; \
  49     c -= b;  c ^= opr_jhash_rot(b, 4);  b += a; \
  50 }
  51
  52 #define opr_jhash_final(a,b,c) \
  53 { \
  54     c ^= b; c -= opr_jhash_rot(b,14); \
  55     a ^= c; a -= opr_jhash_rot(c,11); \
  56     b ^= a; b -= opr_jhash_rot(a,25); \
  57     c ^= b; c -= opr_jhash_rot(b,16); \
  58     a ^= c; a -= opr_jhash_rot(c,4);  \
  59     b ^= a; b -= opr_jhash_rot(a,14); \
  60     c ^= b; c -= opr_jhash_rot(b,24); \
  61 }
  62
  63 static_inline afs_uint32
  64 opr_jhash(const afs_uint32 *k, size_t length, afs_uint32 initval)
  65 {
  66     afs_uint32 a,b,c;
  67
  68     /* Set up the internal state */
  69     a = b = c = 0xdeadbeef + (((afs_uint32)length)<<2) + initval;
  70
  71     while (length > 3) {
  72         a += k[0];
  73         b += k[1];
  74         c += k[2];
  75         opr_jhash_mix(a, b, c);
  76         length -= 3;
  77         k += 3;
  78     }
  79
  80     /* All the case statements fall through */
  81     switch(length) {
  82       case 3 : c+=k[2];
  83       case 2 : b+=k[1];
  84       case 1 : a+=k[0];
  85         opr_jhash_final(a, b, c);
  86       case 0:     /* case 0: nothing left to add */
  87         break;
  88     }
  89
  90     return c;
  91 }
  92
  93 /* Simplified version of the above function to hash just one int */
  94
  95 static_inline afs_uint32
  96 opr_jhash_int(afs_uint32 a, afs_uint32 initval) {
  97    afs_uint32 b, c;
  98
  99    a += 0xdeadbeef + 4 + initval;
 100    b = c = 0xdeadbeef + 4 + initval;
 101    opr_jhash_final(a, b, c);
 102
 103    return c;
 104 }
 105
 106 /* and one to do two ints */
 107
 108 static_inline afs_uint32
 109 opr_jhash_int2(afs_uint32 a, afs_uint32 b, afs_uint32 initval)
 110 {
 111    afs_uint32 c;
 112
 113    a += 0xdeadbeef + 8 + initval;
 114    b += 0xdeadbeef + 8 + initval;
 115    c =  0xdeadbeef + 8 + initval;
 116    opr_jhash_final(a, b, c);
 117
 118    return c;
 119 }
 120
 121 static_inline afs_uint32
 122 opr_jhash_opaque(const void *val, size_t length, afs_uint32 initval)
 123 {
 124     const unsigned char *str = (const unsigned char *) val;
 125     afs_uint32 a,b,c;
 126
 127     /* Set up the internal state */
 128     a = b = c = 0xdeadbeef + ((afs_uint32)length) + initval;
 129
 130     while (length > 12) {
 131         a += (afs_uint32) str[3]<<24 |
 132             (afs_uint32) str[2]<<16 |
 133             (afs_uint32) str[1]<<8 |
 134             (afs_uint32) str[0];
 135         b += (afs_uint32) str[7]<<24 |
 136             (afs_uint32) str[6]<<16 |
 137             (afs_uint32) str[5]<<8 |
 138             (afs_uint32) str[4];
 139         c += (afs_uint32) str[11]<<24 |
 140             (afs_uint32) str[10]<<16 |
 141             (afs_uint32) str[9]<<8 |
 142             (afs_uint32) str[8];
 143         opr_jhash_mix(a, b, c);
 144         length -= 12;
 145         str += 12;
 146     }
 147
 148     /* All the case statements fall through */
 149     switch(length) {
 150       case 12 : c += (afs_uint32) str[11]<<24;
 151       case 11 : c += (afs_uint32) str[10]<<16;
 152       case 10 : c += (afs_uint32) str[9]<<8;
 153       case 9  : c += (afs_uint32) str[8];
 154       case 8  : b += (afs_uint32) str[7]<<24;
 155       case 7  : b += (afs_uint32) str[6]<<16;
 156       case 6  : b += (afs_uint32) str[5]<<8;
 157       case 5  : b += (afs_uint32) str[4];
 158       case 4  : a += (afs_uint32) str[3]<<24;
 159       case 3  : a += (afs_uint32) str[2]<<16;
 160       case 2  : a += (afs_uint32) str[1]<<8;
 161       case 1  : a += (afs_uint32) str[0];
 162         opr_jhash_final(a, b, c);
 163       case 0:     /* case 0: nothing left to add */
 164         break;
 165     }
 166
 167     return c;
 168 }
 169
 170 #endif