~rycwo/forge

ref: HEAD forge/src/murmur_hash.c -rw-r--r-- 1.4 KiB
d7ee94d6Ryan Chan Fix missing cd in .build.yml 14 days ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// This file is part of Forge, the foundation library for Forge tools.
//
// Copyright (C) 2021 Ryan Chan <rycwo@posteo.net>
// SPDX-License-Identifier: GPL-3.0-only
//
// This Source Code Form is subject to the terms of the GNU General Public
// License v3.0 only. You should have received a copy of the license along with
// this program. If not, see <https://www.gnu.org/licenses/>.

#include "forge/compiler_attribute.h"
#include "forge/murmur_hash.h"

uint64_t
fg_murmur_hash_64(void const* key, int len, uint64_t seed) {
	// https://github.com/aappleby/smhasher
	uint64_t const m = 0xc6a4a7935bd1e995LLU;
	int const r = 47;

	uint64_t h = seed ^ (len * m);

	uint64_t const* data = (uint64_t const*)key;
	uint64_t const* end = data + (len / 8);

	while (data != end) {
		// Assuming little-endian
		uint64_t k = *data++;

		k *= m;
		k ^= k >> r;
		k *= m;

		h ^= k;
		h *= m;
	}

	unsigned char const* data2 = (unsigned char const*)data;
	switch (len & 7) {
	case 7: h ^= ((uint64_t)data2[6]) << 48; fallthrough;
	case 6: h ^= ((uint64_t)data2[5]) << 40; fallthrough;
	case 5: h ^= ((uint64_t)data2[4]) << 32; fallthrough;
	case 4: h ^= ((uint64_t)data2[3]) << 24; fallthrough;
	case 3: h ^= ((uint64_t)data2[2]) << 16; fallthrough;
	case 2: h ^= ((uint64_t)data2[1]) << 8;  fallthrough;
	case 1: h ^= ((uint64_t)data2[0]);
			h *= m;
	}

	h ^= h >> r;
	h *= m;
	h ^= h >> r;

	return h;
}