1  /*
  2   hash_fnv.c     - FNV hash functions
  3  
  4   Copyright (C)
  5     2010, 2011,                  Christian Thaeter <ct@pipapo.org>
  6  
  7   This program is free software; you can redistribute it and/or modify
  8   it under the terms of the GNU General Public License as published by
  9   the Free Software Foundation; either version 2 of the License, or
 10   (at your option) any later version.
 11  
 12   This program is distributed in the hope that it will be useful,
 13   but WITHOUT ANY WARRANTY; without even the implied warranty of
 14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 15   GNU General Public License for more details.
 16  
 17   You should have received a copy of the GNU General Public License
 18   along with this program; if not, contact Christian Thaeter <ct@pipapo.org>.
 19  
 20  The actual fnv functions are taken from Landon Curt Noll's original code, no copyright applies:
 21   ***
 22   *
 23   * Please do not copyright this code.  This code is in the public domain.
 24   *
 25   * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 26   * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
 27   * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 28   * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
 29   * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 30   * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 31   * PERFORMANCE OF THIS SOFTWARE.
 32   *
 33   * By:
 34   *	chongo <Landon Curt Noll> /\oo/\
 35   *      http://www.isthe.com/chongo/
 36   *
 37   * Share and Enjoy!	:-)
 38  */
 39  
 40  /**
 41   * @file
 42   * Fowler / Noll / Vo (FNV) Hashes
 43   */
 44  
 45  
 46  #ifndef HASH_FNV_H
 47  #define HASH_FNV_H
 48  
 49  #include <stdlib.h>  /* for size_t */
 50  #include <inttypes.h>
 51  
 52  #define HASH_FNV64_BASE ((uint64_t)14695981039346656037ULL)
 53  #define HASH_FNV32_BASE ((uint32_t)2166136261UL)
 54  
 55  #define HASH_FNV64_PRIME ((uint64_t)1099511628211ULL)
 56  #define HASH_FNV32_PRIME ((uint32_t)16777619UL)
 57  
 58  
 59  /**
 60   * FNV-1a 64 bit hash over a buffer.
 61   * @param buf start of the buffer
 62   * @param len size of the buffer
 63   * @param hval previous hash value when incremental hashing or HASH_FNV64_BASE when starting a new hash
 64   * @return new hash value
 65   */
 66  uint64_t
 67  hash_fnv64a_buf (const void *buf, size_t len, uint64_t hval);
 68  
 69  /**
 70   * FNV-1a 64 bit hash over a zero terminated string.
 71   * @param buf start of the buffer
 72   * @param len maximum size to be processed
 73   * @param hval previous hash value when incremental hashing or HASH_FNV64_BASE when starting a new hash
 74   * @return new hash value
 75   */
 76  uint64_t
 77  hash_fnv64a_strn (const char* str, size_t len, uint64_t hval);
 78  
 79  
 80  /**
 81   * FNV-1a 32 bit hash over a buffer.
 82   * @param buf start of the buffer
 83   * @param len size of the buffer
 84   * @param hval previous hash value when incremental hashing or HASH_FNV32_BASE when starting a new hash
 85   * @return new hash value
 86   */
 87  uint32_t
 88  hash_fnv32a_buf (const void *buf, size_t len, uint32_t hval);
 89  
 90  
 91  /**
 92   * FNV-1a 32 bit hash over a zero terminated string.
 93   * @param buf start of the buffer
 94   * @param len maximum size to be processed
 95   * @param hval previous hash value when incremental hashing or HASH_FNV32_BASE when starting a new hash
 96   * @return new hash value
 97   */
 98  uint32_t
 99  hash_fnv32a_strn (const char* str, size_t len, uint32_t hval);
100  
101  
102  
103  /**
104   * reduce a hash value to n bits.
105   * Uses the xor folding method to stash a hash value together, this preserves unbiased hash distribution
106   * @param hash result from one of the 64 bit hash functions above
107   * @param bits number of significat bits for the result
108   * @result hashvalue with no more than 'bits' significant bits
109   */
110  uint64_t
111  hash_fnv64_xorfold (uint64_t hash, int bits);
112  
113  
114  /**
115   * reduce a hash value to n bits.
116   * Uses the xor folding method to stash a hash value together, this preserves unbiased hash distribution
117   * @param hash result from one of the 32 bit hash functions above
118   * @param bits number of significat bits for the result
119   * @result hashvalue with no more than 'bits' significant bits
120   */
121  uint32_t
122  hash_fnv32_xorfold (uint32_t hash, int bits);
123  
124  
125  /**
126   * reduce hash to be within 0 to limit-1.
127   * Uses the retry method to limit a hash value, this preserves unbiased hash distribution.
128   * @param hash result from one of the 64 bit hash functions above
129   * @param limit upper limit plus one for the result
130   * @result hashvalue in the range from 0 to limit-1
131   */
132  uint64_t
133  hash_fnv64_retry (uint64_t hash, uint64_t limit);
134  
135  
136  /**
137   * reduce hash to be within 0 to limit-1.
138   * Uses the retry method to limit a hash value, this preserves unbiased hash distribution.
139   * @param hash result from one of the 32 bit hash functions above
140   * @param limit upper limit plus one for the result
141   * @result hashvalue in the range from 0 to limit-1
142   */
143  uint32_t
144  hash_fnv32_retry (uint64_t hash, uint32_t limit);
145  
146  
147  
148  /*
149  PLANNED? 128 bit and 256bit hashes
150  128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371
151  
152  256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211
153  
154  128 bit offset_basis = 144066263297769815596495629667062367629
155  
156  256 bit offset_basis =
157  100029257958052580907070968620625704837092796014241193945225284501741471925557
158  
159  */
160  
161  
162  
163  #endif
164  
165  /*
166  //      Local Variables:
167  //      mode: C
168  //      c-file-style: "gnu"
169  //      indent-tabs-mode: nil
170  //      End:
171  */