xref: /unit/src/nxt_murmur_hash.c (revision 39)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * The code is based on the code by Austin Appleby,
40Sigor@sysoev.ru  * released to the public domain.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #include <nxt_main.h>
80Sigor@sysoev.ru 
90Sigor@sysoev.ru 
100Sigor@sysoev.ru uint32_t
110Sigor@sysoev.ru nxt_murmur_hash2(const void *data, size_t len)
120Sigor@sysoev.ru {
130Sigor@sysoev.ru     uint32_t        h, k;
140Sigor@sysoev.ru     const u_char    *p;
150Sigor@sysoev.ru     const uint32_t  m = 0x5bd1e995;
160Sigor@sysoev.ru 
170Sigor@sysoev.ru     p = data;
180Sigor@sysoev.ru     h = 0 ^ (uint32_t) len;
190Sigor@sysoev.ru 
200Sigor@sysoev.ru     while (len >= 4) {
210Sigor@sysoev.ru         k  = p[0];
220Sigor@sysoev.ru         k |= p[1] << 8;
230Sigor@sysoev.ru         k |= p[2] << 16;
240Sigor@sysoev.ru         k |= p[3] << 24;
250Sigor@sysoev.ru 
260Sigor@sysoev.ru         k *= m;
270Sigor@sysoev.ru         k ^= k >> 24;
280Sigor@sysoev.ru         k *= m;
290Sigor@sysoev.ru 
300Sigor@sysoev.ru         h *= m;
310Sigor@sysoev.ru         h ^= k;
320Sigor@sysoev.ru 
330Sigor@sysoev.ru         p += 4;
340Sigor@sysoev.ru         len -= 4;
350Sigor@sysoev.ru     }
360Sigor@sysoev.ru 
370Sigor@sysoev.ru     switch (len) {
380Sigor@sysoev.ru     case 3:
390Sigor@sysoev.ru         h ^= p[2] << 16;
40*39Svbart@nginx.com         /* Fall through. */
410Sigor@sysoev.ru     case 2:
420Sigor@sysoev.ru         h ^= p[1] << 8;
43*39Svbart@nginx.com         /* Fall through. */
440Sigor@sysoev.ru     case 1:
450Sigor@sysoev.ru         h ^= p[0];
460Sigor@sysoev.ru         h *= m;
470Sigor@sysoev.ru     }
480Sigor@sysoev.ru 
490Sigor@sysoev.ru     h ^= h >> 13;
500Sigor@sysoev.ru     h *= m;
510Sigor@sysoev.ru     h ^= h >> 15;
520Sigor@sysoev.ru 
530Sigor@sysoev.ru     return h;
540Sigor@sysoev.ru }
550Sigor@sysoev.ru 
560Sigor@sysoev.ru 
570Sigor@sysoev.ru /* The MurmurHash2 for fixed 4 byte length. */
580Sigor@sysoev.ru 
590Sigor@sysoev.ru uint32_t
600Sigor@sysoev.ru nxt_murmur_hash2_uint32(const void *data)
610Sigor@sysoev.ru {
620Sigor@sysoev.ru     uint32_t        h, k;
630Sigor@sysoev.ru     const u_char    *p;
640Sigor@sysoev.ru     const uint32_t  m = 0x5bd1e995;
650Sigor@sysoev.ru 
660Sigor@sysoev.ru     p = data;
670Sigor@sysoev.ru 
680Sigor@sysoev.ru     k  = p[0];
690Sigor@sysoev.ru     k |= p[1] << 8;
700Sigor@sysoev.ru     k |= p[2] << 16;
710Sigor@sysoev.ru     k |= p[3] << 24;
720Sigor@sysoev.ru 
730Sigor@sysoev.ru     k *= m;
740Sigor@sysoev.ru     k ^= k >> 24;
750Sigor@sysoev.ru     k *= m;
760Sigor@sysoev.ru 
770Sigor@sysoev.ru     h = 0 ^ 4;
780Sigor@sysoev.ru     h *= m;
790Sigor@sysoev.ru     h ^= k;
800Sigor@sysoev.ru 
810Sigor@sysoev.ru     h ^= h >> 13;
820Sigor@sysoev.ru     h *= m;
830Sigor@sysoev.ru     h ^= h >> 15;
840Sigor@sysoev.ru 
850Sigor@sysoev.ru     return h;
860Sigor@sysoev.ru }
87