Home | History | Annotate | Line # | Download | only in cxgb 
      1 #ifndef _JHASH_H
      2 #define _JHASH_H
      3 
      4 /* jhash.h: Jenkins hash support.
      5  *
      6  * Copyright (C) 1996 Bob Jenkins (bob_jenkins (at) burtleburtle.net)
      7  *
      8  * http://burtleburtle.net/bob/hash/
      9  *
     10  * These are the credits from Bob's sources:
     11  *
     12  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
     13  * hash(), hash2(), hash3, and mix() are externally useful functions.
     14  * Routines to test the hash are included if SELF_TEST is defined.
     15  * You can use this free for any purpose.  It has no warranty.
     16  */
     17 
     18 /* NOTE: Arguments are modified. */
     19 #define __jhash_mix(a, b, c) \
     20 { \
     21   a -= b; a -= c; a ^= (c>>13); \
     22   b -= c; b -= a; b ^= (a<<8); \
     23   c -= a; c -= b; c ^= (b>>13); \
     24   a -= b; a -= c; a ^= (c>>12);  \
     25   b -= c; b -= a; b ^= (a<<16); \
     26   c -= a; c -= b; c ^= (b>>5); \
     27   a -= b; a -= c; a ^= (c>>3);  \
     28   b -= c; b -= a; b ^= (a<<10); \
     29   c -= a; c -= b; c ^= (b>>15); \
     30 }
     31 
     32 /* The golden ration: an arbitrary value */
     33 #define JHASH_GOLDEN_RATIO  0x9e3779b9
     34 
     35 /* The most generic version, hashes an arbitrary sequence
     36  * of bytes.  No alignment or length assumptions are made about
     37  * the input key.
     38  */
     39 static __inline u32 jhash(const void *key, u32 length, u32 initval)
     40 {
     41     u32 a, b, c, len;
     42     const u8 *k = key;
     43 
     44     len = length;
     45     a = b = JHASH_GOLDEN_RATIO;
     46     c = initval;
     47 
     48     while (len >= 12) {
     49         a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24));
     50         b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24));
     51         c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24));
     52 
     53         __jhash_mix(a,b,c);
     54 
     55         k += 12;
     56         len -= 12;
     57     }
     58 
     59     c += length;
     60     switch (len) {
     61     case 11: c += ((u32)k[10]<<24);
     62     case 10: c += ((u32)k[9]<<16);
     63     case 9 : c += ((u32)k[8]<<8);
     64     case 8 : b += ((u32)k[7]<<24);
     65     case 7 : b += ((u32)k[6]<<16);
     66     case 6 : b += ((u32)k[5]<<8);
     67     case 5 : b += k[4];
     68     case 4 : a += ((u32)k[3]<<24);
     69     case 3 : a += ((u32)k[2]<<16);
     70     case 2 : a += ((u32)k[1]<<8);
     71     case 1 : a += k[0];
     72     };
     73 
     74     __jhash_mix(a,b,c);
     75 
     76     return c;
     77 }
     78 
     79 /* A special optimized version that handles 1 or more of u32s.
     80  * The length parameter here is the number of u32s in the key.
     81  */
     82 static __inline u32 jhash2(u32 *k, u32 length, u32 initval)
     83 {
     84     u32 a, b, c, len;
     85 
     86     a = b = JHASH_GOLDEN_RATIO;
     87     c = initval;
     88     len = length;
     89 
     90     while (len >= 3) {
     91         a += k[0];
     92         b += k[1];
     93         c += k[2];
     94         __jhash_mix(a, b, c);
     95         k += 3; len -= 3;
     96     }
     97 
     98     c += length * 4;
     99 
    100     switch (len) {
    101     case 2 : b += k[1];
    102     case 1 : a += k[0];
    103     };
    104 
    105     __jhash_mix(a,b,c);
    106 
    107     return c;
    108 }
    109 
    110 
    111 /* A special ultra-optimized versions that knows they are hashing exactly
    112  * 3, 2 or 1 word(s).
    113  *
    114  * NOTE: In particular the "c += length; __jhash_mix(a,b,c);" normally
    115  *       done at the end is not done here.
    116  */
    117 static __inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
    118 {
    119     a += JHASH_GOLDEN_RATIO;
    120     b += JHASH_GOLDEN_RATIO;
    121     c += initval;
    122 
    123     __jhash_mix(a, b, c);
    124 
    125     return c;
    126 }
    127 
    128 static __inline u32 jhash_2words(u32 a, u32 b, u32 initval)
    129 {
    130     return jhash_3words(a, b, 0, initval);
    131 }
    132 
    133 static __inline u32 jhash_1word(u32 a, u32 initval)
    134 {
    135     return jhash_3words(a, 0, 0, initval);
    136 }
    137 
    138 #endif /* _JHASH_H */
    139