compute.h File Reference

#include <assert.h>
#include <string.h>
#include "base/inttypes.h"

Go to the source code of this file.

Defines
#define	HASH_MIX(a, b, c)
	Hash mix found at http://burtleburtle.net/bob/hash/ Original comments from the author: -------------------------------------------------------------------- mix -- mix 3 32-bit values reversibly.
Functions
uint32_t	hash_computeU32 (const uint32_t *data, size_t length, uint32_t initval)
	Compute hash value for different data types.
uint32_t	hash_computeU16 (const uint16_t *data, size_t length, uint32_t initval)
	Hash for uint16_t[].
uint32_t	hash_computeU8 (const uint8_t *data, size_t length, uint32_t initval)
	Hash for uint8_t[].
static uint32_t	hash_computeI32 (const int32_t *data, size_t length, uint32_t initval)
	Wrapper functions for convenience.
static uint32_t	hash_computeI16 (const int16_t *data, size_t length, uint32_t initval)
static uint32_t	hash_computeI8 (const int8_t *data, size_t length, uint32_t initval)
static uint32_t	hash_computeStr (const char *str, uint32_t initval)
static uint32_t	hash_compute (uint32_t a, uint32_t b, uint32_t c)
	Compute a new hash from 3 previous hash values.

---

Define Documentation

#define HASH_MIX (  a, b, c   )

Value: { \ a -= b; a -= c; a ^= (c>>13); \ b -= c; b -= a; b ^= (a<<8); \ c -= a; c -= b; c ^= (b>>13); \ a -= b; a -= c; a ^= (c>>12); \ b -= c; b -= a; b ^= (a<<16); \ c -= a; c -= b; c ^= (b>>5); \ a -= b; a -= c; a ^= (c>>3); \ b -= c; b -= a; b ^= (a<<10); \ c -= a; c -= b; c ^= (b>>15); \ } Hash mix found at http://burtleburtle.net/bob/hash/ Original comments from the author: -------------------------------------------------------------------- mix -- mix 3 32-bit values reversibly. For every delta with one or two bit set, and the deltas of all three high bits or all three low bits, whether the original value of a,b,c is almost all zero or is uniformly distributed, * If mix() is run forward or backward, at least 32 bits in a,b,c have at least 1/4 probability of changing. * If mix() is run forward, every bit of c will change between 1/3 and 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) mix() takes 36 machine instructions, but only 18 cycles on a superscalar machine (like a Pentium or a Sparc). No faster mixer seems to work, that's the result of my brute-force search. There were about 2^^68 hashes to choose from. I only tested about a billion of those. -------------------------------------------------------------------- NOTE: the hash function based on this hash mix is much faster than MD5 hashing and gives exactly the same results.

---

Function Documentation

static uint32_t hash_compute (  uint32_t  a, uint32_t  b, uint32_t  c )  [inline, static]

Compute a new hash from 3 previous hash values. Parameters: a,b,c,:  values to combine. Returns: a mixed hashed value.

static uint32_t hash_computeI16 (  const int16_t *  data, size_t  length, uint32_t  initval )  [inline, static]

static uint32_t hash_computeI32 (  const int32_t *  data, size_t  length, uint32_t  initval )  [inline, static]

Wrapper functions for convenience. Wrap types of input data: support for int32_t => uint32_t int16_t => uint16_t int8_t => uint8_t char[] => uint8_t

static uint32_t hash_computeI8 (  const int8_t *  data, size_t  length, uint32_t  initval )  [inline, static]

static uint32_t hash_computeStr (  const char *  str, uint32_t  initval )  [inline, static]

uint32_t hash_computeU16 (  const uint16_t *  data16, size_t  length, uint32_t  initval )

Hash for uint16_t[]. Parameters: length,:  number of uint16_t initval,:  initial value to start the hash computation. Returns: the hash.

uint32_t hash_computeU32 (  const uint32_t *  data, size_t  length, uint32_t  initval )

Compute hash value for different data types. Parameters: length,:  number of uint32_t initval,:  initial value to start the hash computation. Returns: the hash.

uint32_t hash_computeU8 (  const uint8_t *  data8, size_t  length, uint32_t  initval )

Hash for uint8_t[]. Parameters: length,:  number of uint16_t initval,:  initial value to start the hash computation. Returns: the hash.

---