data-structures-c
Loading...
Searching...
No Matches
lib
murmurhash.h
Go to the documentation of this file.
1
/* murmurhash.h
2
*
3
* Copyright (C) 2023 abxh
4
*
5
* This library is free software; you can redistribute it and/or
6
* modify it under the terms of the GNU Lesser General Public
7
* License as published by the Free Software Foundation; either
8
* version 2.1 of the License, or (at your option) any later version.
9
* See the file LICENSE included with this distribution for more
10
* information. */
11
28
#pragma once
29
30
#include <stdint.h>
31
#include <stdlib.h>
32
#include <string.h>
33
35
static
inline
uint32_t internal_murmur_32_scramble(uint32_t k)
36
{
37
k *= 0xcc9e2d51;
38
k = (k << 15) | (k >> 17);
39
k *= 0x1b873593;
40
return
k;
41
}
43
54
static
inline
uint32_t
murmur3_32
(
const
uint8_t *key_ptr,
const
uint32_t len,
const
uint32_t seed)
55
{
56
uint32_t h = seed;
57
uint32_t k;
58
59
/* Read in groups of 4. */
60
for
(
size_t
i = len >> 2; i; i--) {
61
// Here is a source of differing results across endiannesses.
62
// A swap here has no effects on hash properties though.
63
memcpy(&k, key_ptr,
sizeof
(uint32_t));
64
key_ptr +=
sizeof
(uint32_t);
65
h ^= internal_murmur_32_scramble(k);
66
h = (h << 13) | (h >> 19);
67
h = h * 5 + 0xe6546b64;
68
}
69
70
/* Read the rest. */
71
k = 0;
72
for
(
size_t
i = len & 3; i; i--) {
73
k <<= 8;
74
k |= key_ptr[i - 1];
75
}
76
77
// A swap is *not* necessary here because the preceding loop already
78
// places the low bytes in the low places according to whatever
79
// endianness we use. Swaps only apply when the memory is copied in a
80
// chunk.
81
h ^= internal_murmur_32_scramble(k);
82
83
/* Finalize. */
84
h ^= len;
85
h ^= h >> 16;
86
h *= 0x85ebca6b;
87
h ^= h >> 13;
88
h *= 0xc2b2ae35;
89
h ^= h >> 16;
90
return
h;
91
}
92
93
// vim: ft=c
murmur3_32
static uint32_t murmur3_32(const uint8_t *key_ptr, const uint32_t len, const uint32_t seed)
Get the Murmur3 (32-bit) hash of a string of bytes.
Definition
murmurhash.h:54
Generated by
1.12.0