Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl

annotate MurmurHash2.c @ 2:1218b245530c

find changesets by author, revision, files, or words in the commit message
adding MurmurHash2.c -- code for high perf hash from net
author Me
date Wed, 28 Jul 2010 13:15:28 -0700
parents
children 5b89d57e5d10
rev   line source
Me@2 1 //-----------------------------------------------------------------------------
Me@2 2 // MurmurHash2, by Austin Appleby
Me@2 3
Me@2 4 // Note - This code makes a few assumptions about how your machine behaves -
Me@2 5
Me@2 6 // 1. We can read a 4-byte value from any address without crashing
Me@2 7 // 2. sizeof(int) == 4
Me@2 8
Me@2 9 // And it has a few limitations -
Me@2 10
Me@2 11 // 1. It will not work incrementally.
Me@2 12 // 2. It will not produce the same results on little-endian and big-endian
Me@2 13 // machines.
Me@2 14
Me@2 15 unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
Me@2 16 {
Me@2 17 // 'm' and 'r' are mixing constants generated offline.
Me@2 18 // They're not really 'magic', they just happen to work well.
Me@2 19
Me@2 20 const unsigned int m = 0x5bd1e995;
Me@2 21 const int r = 24;
Me@2 22
Me@2 23 // Initialize the hash to a 'random' value
Me@2 24
Me@2 25 unsigned int h = seed ^ len;
Me@2 26
Me@2 27 // Mix 4 bytes at a time into the hash
Me@2 28
Me@2 29 const unsigned char * data = (const unsigned char *)key;
Me@2 30
Me@2 31 while(len >= 4)
Me@2 32 {
Me@2 33 unsigned int k = *(unsigned int *)data;
Me@2 34
Me@2 35 k *= m;
Me@2 36 k ^= k >> r;
Me@2 37 k *= m;
Me@2 38
Me@2 39 h *= m;
Me@2 40 h ^= k;
Me@2 41
Me@2 42 data += 4;
Me@2 43 len -= 4;
Me@2 44 }
Me@2 45
Me@2 46 // Handle the last few bytes of the input array
Me@2 47
Me@2 48 switch(len)
Me@2 49 {
Me@2 50 case 3: h ^= data[2] << 16;
Me@2 51 case 2: h ^= data[1] << 8;
Me@2 52 case 1: h ^= data[0];
Me@2 53 h *= m;
Me@2 54 };
Me@2 55
Me@2 56 // Do a few final mixes of the hash to ensure the last few
Me@2 57 // bytes are well-incorporated.
Me@2 58
Me@2 59 h ^= h >> 13;
Me@2 60 h *= m;
Me@2 61 h ^= h >> 15;
Me@2 62
Me@2 63 return h;
Me@2 64 }