Line data    Source code

       1             : /*
       2             :  * vr_hash.h
       3             :  *
       4             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       5             :  * Copyright Contributors to the OpenSDN project
       6             :  */
       7             : 
       8             : #ifndef _VR_HASH_H
       9             : #define _VR_HASH_H
      10             : 
      11             : #include "vr_os.h"
      12             : 
      13             : /* vr_hash.h: Jenkins hash support.
      14             :  *
      15             :  * License: Public Domain
      16             :  * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net)
      17             :  *
      18             :  * http://burtleburtle.net/bob/hash/
      19             :  *
      20             :  * These are the credits from Bob's sources:
      21             :  *
      22             :  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
      23             :  *
      24             :  * These are functions for producing 32-bit hashes for hash table lookup.
      25             :  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
      26             :  * are externally useful functions.  Routines to test the hash are included
      27             :  * if SELF_TEST is defined.  You can use this free for any purpose.  It's in
      28             :  * the public domain.  It has no warranty.
      29             :  *
      30             :  * Copyright (C) 2009-2010 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu)
      31             :  *
      32             :  * I've modified Bob's hash to be useful in the Linux kernel, and
      33             :  * any bugs present are my fault.
      34             :  * Jozsef
      35             :  */
      36             : 
      37             : /* Best hash sizes are of power of two */
      38             : #define vr_hash_size(n)   ((uint32_t)1<<(n))
      39             : /* Mask the hash value, i.e (value & vr_hash_mask(n)) instead of (value % n) */
      40             : #define vr_hash_mask(n)   (vr_hash_size(n)-1)
      41             : 
      42             : #define rolword(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
      43             : 
      44             : /* __vr_hash_mix -- mix 3 32-bit values reversibly. */
      45             : #define __vr_hash_mix(a, b, c)              \
      46             : {                                           \
      47             :     a -= c;  a ^= rolword(c, 4);  c += b;   \
      48             :     b -= a;  b ^= rolword(a, 6);  a += c;   \
      49             :     c -= b;  c ^= rolword(b, 8);  b += a;   \
      50             :     a -= c;  a ^= rolword(c, 16); c += b;   \
      51             :     b -= a;  b ^= rolword(a, 19); a += c;   \
      52             :     c -= b;  c ^= rolword(b, 4);  b += a;   \
      53             : }
      54             : 
      55             : /* __vr_hash_final - final mixing of 3 32-bit values (a,b,c) into c */
      56             : #define __vr_hash_final(a, b, c)            \
      57             : {                                           \
      58             :     c ^= b; c -= rolword(b, 14);            \
      59             :     a ^= c; a -= rolword(c, 11);            \
      60             :     b ^= a; b -= rolword(a, 25);            \
      61             :     c ^= b; c -= rolword(b, 16);            \
      62             :     a ^= c; a -= rolword(c, 4);             \
      63             :     b ^= a; b -= rolword(a, 14);            \
      64             :     c ^= b; c -= rolword(b, 24);            \
      65             : }
      66             : 
      67             : /* An arbitrary initial parameter */
      68             : #define VR_HASH_INITVAL     0xdeadbeef
      69             : 
      70             : __attribute__packed__open__
      71             : struct __unaligned_u32 {
      72             :     uint32_t x;
      73             : } __attribute__packed__close__;
      74             : 
      75        2487 : static inline uint32_t __get_unaligned_word(const void *p)
      76             : {
      77             :     union {
      78             :         uint8_t bytes[sizeof(uint32_t)];
      79             :         struct __unaligned_u32 u32;
      80             :     } word;
      81             : 
      82             :     size_t i;
      83       12435 :     for (i = 0; i < sizeof(struct __unaligned_u32); i++) {
      84        9948 :         word.bytes[i] = ((uint8_t *) p)[i];
      85             :     }
      86        2487 :     return word.u32.x;
      87             : }
      88             : 
      89             : 
      90             : /* vr_hash - hash an arbitrary key
      91             :  * @k: sequence of bytes as key
      92             :  * @length: the length of the key
      93             :  * @initval: the previous hash, or an arbitray value
      94             :  *
      95             :  * The generic version, hashes an arbitrary sequence of bytes.
      96             :  * No alignment or length assumptions are made about the input key.
      97             :  *
      98             :  * Returns the hash value of the key. The result depends on endianness.
      99             :  */
     100         984 : static inline uint32_t vr_hash(const void *key, uint32_t length, uint32_t initval)
     101             : {
     102             :     uint32_t a, b, c;
     103         984 :     const uint8_t *k = key;
     104             : 
     105             :     /* Set up the internal state */
     106         984 :     a = b = c = VR_HASH_INITVAL + length + initval;
     107             : 
     108             :     /* All but the last block: affect some 32 bits of (a,b,c) */
     109        1813 :     while (length > 12) {
     110         829 :         a += __get_unaligned_word(k);
     111         829 :         b += __get_unaligned_word(k + 4);
     112         829 :         c += __get_unaligned_word(k + 8);
     113         829 :         __vr_hash_mix(a, b, c);
     114         829 :         length -= 12;
     115         829 :         k += 12;
     116             :     }
     117             :     /* Last block: affect all 32 bits of (c) */
     118         984 :     if (length == 12) c += (uint32_t)k[11]<<24;
     119         984 :     if (length >= 11) c += (uint32_t)k[10]<<16;
     120         984 :     if (length >= 10) c += (uint32_t)k[9]<<8;
     121         984 :     if (length >= 9) c += k[8];
     122         984 :     if (length >= 8) b += (uint32_t)k[7]<<24;
     123         984 :     if (length >= 7) b += (uint32_t)k[6]<<16;
     124         984 :     if (length >= 6) b += (uint32_t)k[5]<<8;
     125         984 :     if (length >= 5) b += k[4];
     126         984 :     if (length >= 4) a += (uint32_t)k[3]<<24;
     127         984 :     if (length >= 3) a += (uint32_t)k[2]<<16;
     128         984 :     if (length >= 2) a += (uint32_t)k[1]<<8;
     129         984 :     if (length >= 1) {
     130         984 :         a += k[0];
     131         984 :         __vr_hash_final(a, b, c);
     132             :     }
     133             : 
     134         984 :     return c;
     135             : }
     136             : 
     137             : /* vr_hash2 - hash an array of u32's
     138             :  * @k: the key which must be an array of u32's
     139             :  * @length: the number of u32's in the key
     140             :  * @initval: the previous hash, or an arbitray value
     141             :  *
     142             :  * Returns the hash value of the key.
     143             :  */
     144             : static inline uint32_t vr_hash2(const uint32_t *k, uint32_t length, uint32_t initval)
     145             : {
     146             :     uint32_t a, b, c;
     147             : 
     148             :     /* Set up the internal state */
     149             :     a = b = c = VR_HASH_INITVAL + (length<<2) + initval;
     150             : 
     151             :     /* Handle most of the key */
     152             :     while (length > 3) {
     153             :         a += k[0];
     154             :         b += k[1];
     155             :         c += k[2];
     156             :         __vr_hash_mix(a, b, c);
     157             :         length -= 3;
     158             :         k += 3;
     159             :     }
     160             : 
     161             :     /* Handle the last 3 u32's: all the case statements fall through */
     162             :     switch (length) {
     163             :     case 3: c += k[2];
     164             :     case 2: b += k[1];
     165             :     case 1: a += k[0];
     166             :         __vr_hash_final(a, b, c);
     167             :     case 0:    /* Nothing left to add */
     168             :         break;
     169             :     }
     170             : 
     171             :     return c;
     172             : }
     173             : 
     174             : 
     175             : /* vr_hash_3words - hash exactly 3, 2 or 1 word(s) */
     176           2 : static inline uint32_t vr_hash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
     177             : {
     178           2 :     a += VR_HASH_INITVAL;
     179           2 :     b += VR_HASH_INITVAL;
     180           2 :     c += initval;
     181             : 
     182           2 :     __vr_hash_final(a, b, c);
     183             : 
     184           2 :     return c;
     185             : }
     186             : 
     187           2 : static inline uint32_t vr_hash_2words(uint32_t a, uint32_t b, uint32_t initval)
     188             : {
     189           2 :     return vr_hash_3words(a, b, 0, initval);
     190             : }
     191             : 
     192             : static inline uint32_t vr_hash_1word(uint32_t a, uint32_t initval)
     193             : {
     194             :     return vr_hash_3words(a, 0, 0, initval);
     195             : }
     196             : 
     197             : #endif /* _VR_HASH_H */