sys/sys/fnv_hash.h

   1 /*
   2  * Fowler / Noll / Vo Hash (FNV Hash)
   3  * http://www.isthe.com/chongo/tech/comp/fnv/
   4  *
   5  * This is an implementation of the algorithms posted above.
   6  * This file is placed in the public domain by Peter Wemm.
   7  *
   8  * $FreeBSD: src/sys/sys/fnv_hash.h,v 1.2.2.1 2001/03/21 10:50:59 peter Exp $
   9  * $DragonFly: src/sys/sys/fnv_hash.h,v 1.2 2003/06/17 04:28:58 dillon Exp $
  10  */
  11
  12 typedef u_int32_t Fnv32_t;
  13 typedef u_int64_t Fnv64_t;
  14
  15 #define FNV1_32_INIT ((Fnv32_t) 33554467UL)
  16 #define FNV1_64_INIT ((Fnv64_t) 0xcbf29ce484222325ULL)
  17
  18 #define FNV_32_PRIME ((Fnv32_t) 0x01000193UL)
  19 #define FNV_64_PRIME ((Fnv64_t) 0x100000001b3ULL)
  20
  21 static __inline Fnv32_t
  22 fnv_32_buf(const void *buf, size_t len, Fnv32_t hval)
  23 {
  24         const u_int8_t *s = (const u_int8_t *)buf;
  25
  26         while (len-- != 0) {
  27                 hval *= FNV_32_PRIME;
  28                 hval ^= *s++;
  29         }
  30         return hval;
  31 }
  32
  33 static __inline Fnv32_t
  34 fnv_32_str(const char *str, Fnv32_t hval)
  35 {
  36         const u_int8_t *s = (const u_int8_t *)str;
  37         Fnv32_t c;
  38
  39         while ((c = *s++) != 0) {
  40                 hval *= FNV_32_PRIME;
  41                 hval ^= c;
  42         }
  43         return hval;
  44 }
  45
  46 static __inline Fnv64_t
  47 fnv_64_buf(const void *buf, size_t len, Fnv64_t hval)
  48 {
  49         const u_int8_t *s = (const u_int8_t *)buf;
  50
  51         while (len-- != 0) {
  52                 hval *= FNV_64_PRIME;
  53                 hval ^= *s++;
  54         }
  55         return hval;
  56 }
  57
  58 static __inline Fnv64_t
  59 fnv_64_str(const char *str, Fnv64_t hval)
  60 {
  61         const u_int8_t *s = (const u_int8_t *)str;
  62         u_register_t c;          /* 32 bit on i386, 64 bit on alpha,ia64 */
  63
  64         while ((c = *s++) != 0) {
  65                 hval *= FNV_64_PRIME;
  66                 hval ^= c;
  67         }
  68         return hval;
  69 }