Line data    Source code

       1             : /* jhash.h: Jenkins hash support.
       2             :  *
       3             :  * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
       4             :  *
       5             :  * http://burtleburtle.net/bob/hash/
       6             :  *
       7             :  * These are the credits from Bob's sources:
       8             :  *
       9             :  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
      10             :  * hash(), hash2(), hash3, and mix() are externally useful functions.
      11             :  * Routines to test the hash are included if SELF_TEST is defined.
      12             :  * You can use this free for any purpose.  It has no warranty.
      13             :  *
      14             :  * Copyright (C) 2003 David S. Miller (davem@redhat.com)
      15             :  *
      16             :  * I've modified Bob's hash to be useful in the Linux kernel, and
      17             :  * any bugs present are surely my fault.  -DaveM
      18             :  */
      19             : 
      20             : #include "zebra.h"
      21             : #include "jhash.h"
      22             : 
      23             : /* The golden ration: an arbitrary value */
      24             : #define JHASH_GOLDEN_RATIO  0x9e3779b9
      25             : 
      26             : /* NOTE: Arguments are modified. */
      27             : #define __jhash_mix(a, b, c)                                                   \
      28             :         {                                                                      \
      29             :                 a -= b;                                                        \
      30             :                 a -= c;                                                        \
      31             :                 a ^= (c >> 13);                                                \
      32             :                 b -= c;                                                        \
      33             :                 b -= a;                                                        \
      34             :                 b ^= (a << 8);                                                 \
      35             :                 c -= a;                                                        \
      36             :                 c -= b;                                                        \
      37             :                 c ^= (b >> 13);                                                \
      38             :                 a -= b;                                                        \
      39             :                 a -= c;                                                        \
      40             :                 a ^= (c >> 12);                                                \
      41             :                 b -= c;                                                        \
      42             :                 b -= a;                                                        \
      43             :                 b ^= (a << 16);                                                \
      44             :                 c -= a;                                                        \
      45             :                 c -= b;                                                        \
      46             :                 c ^= (b >> 5);                                                 \
      47             :                 a -= b;                                                        \
      48             :                 a -= c;                                                        \
      49             :                 a ^= (c >> 3);                                                 \
      50             :                 b -= c;                                                        \
      51             :                 b -= a;                                                        \
      52             :                 b ^= (a << 10);                                                \
      53             :                 c -= a;                                                        \
      54             :                 c -= b;                                                        \
      55             :                 c ^= (b >> 15);                                                \
      56             :         }
      57             : 
      58             : /* The most generic version, hashes an arbitrary sequence
      59             :  * of bytes.  No alignment or length assumptions are made about
      60             :  * the input key.
      61             :  */
      62       13038 : uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
      63             : {
      64       13038 :         uint32_t a, b, c, len;
      65       13038 :         const uint8_t *k = key;
      66             : 
      67       13038 :         len = length;
      68       13038 :         a = b = JHASH_GOLDEN_RATIO;
      69       13038 :         c = initval;
      70             : 
      71       13376 :         while (len >= 12) {
      72         338 :                 a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
      73         338 :                       + ((uint32_t)k[3] << 24));
      74         338 :                 b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
      75         338 :                       + ((uint32_t)k[7] << 24));
      76         338 :                 c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
      77         338 :                       + ((uint32_t)k[11] << 24));
      78             : 
      79         338 :                 __jhash_mix(a, b, c);
      80             : 
      81         338 :                 k += 12;
      82         338 :                 len -= 12;
      83             :         }
      84             : 
      85       13038 :         c += length;
      86       13038 :         switch (len) {
      87          61 :         case 11:
      88          61 :                 c += ((uint32_t)k[10] << 24);
      89             :         /* fallthru */
      90          75 :         case 10:
      91          75 :                 c += ((uint32_t)k[9] << 16);
      92             :         /* fallthru */
      93         103 :         case 9:
      94         103 :                 c += ((uint32_t)k[8] << 8);
      95             :         /* fallthru */
      96       12731 :         case 8:
      97       12731 :                 b += ((uint32_t)k[7] << 24);
      98             :         /* fallthru */
      99       12739 :         case 7:
     100       12739 :                 b += ((uint32_t)k[6] << 16);
     101             :         /* fallthru */
     102       12774 :         case 6:
     103       12774 :                 b += ((uint32_t)k[5] << 8);
     104             :         /* fallthru */
     105       12784 :         case 5:
     106       12784 :                 b += k[4];
     107             :         /* fallthru */
     108       12849 :         case 4:
     109       12849 :                 a += ((uint32_t)k[3] << 24);
     110             :         /* fallthru */
     111       12883 :         case 3:
     112       12883 :                 a += ((uint32_t)k[2] << 16);
     113             :         /* fallthru */
     114       12885 :         case 2:
     115       12885 :                 a += ((uint32_t)k[1] << 8);
     116             :         /* fallthru */
     117       12893 :         case 1:
     118       12893 :                 a += k[0];
     119             :         }
     120             : 
     121       13038 :         __jhash_mix(a, b, c);
     122             : 
     123       13038 :         return c;
     124             : }
     125             : 
     126             : /* A special optimized version that handles 1 or more of uint32_ts.
     127             :  * The length parameter here is the number of uint32_ts in the key.
     128             :  */
     129          88 : uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
     130             : {
     131          88 :         uint32_t a, b, c, len;
     132             : 
     133          88 :         a = b = JHASH_GOLDEN_RATIO;
     134          88 :         c = initval;
     135          88 :         len = length;
     136             : 
     137         440 :         while (len >= 3) {
     138         352 :                 a += k[0];
     139         352 :                 b += k[1];
     140         352 :                 c += k[2];
     141         352 :                 __jhash_mix(a, b, c);
     142         352 :                 k += 3;
     143         352 :                 len -= 3;
     144             :         }
     145             : 
     146          88 :         c += length * 4;
     147             : 
     148          88 :         switch (len) {
     149           0 :         case 2:
     150           0 :                 b += k[1];
     151             :         /* fallthru */
     152           0 :         case 1:
     153           0 :                 a += k[0];
     154             :         }
     155             : 
     156          88 :         __jhash_mix(a, b, c);
     157             : 
     158          88 :         return c;
     159             : }
     160             : 
     161             : 
     162             : /* A special ultra-optimized versions that knows they are hashing exactly
     163             :  * 3, 2 or 1 word(s).
     164             :  *
     165             :  * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
     166             :  *       done at the end is not done here.
     167             :  */
     168         450 : uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
     169             : {
     170         450 :         a += JHASH_GOLDEN_RATIO;
     171         450 :         b += JHASH_GOLDEN_RATIO;
     172         450 :         c += initval;
     173             : 
     174         450 :         __jhash_mix(a, b, c);
     175             : 
     176         450 :         return c;
     177             : }
     178             : 
     179         176 : uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
     180             : {
     181         176 :         return jhash_3words(a, b, 0, initval);
     182             : }
     183             : 
     184          98 : uint32_t jhash_1word(uint32_t a, uint32_t initval)
     185             : {
     186          98 :         return jhash_3words(a, 0, 0, initval);
     187             : }