aboutsummaryrefslogtreecommitdiff
path: root/v_windows/v/old/vlib/hash/wyhash.v
blob: bd89c4216eaaa89d1fb24704202de77f1618f5b8 (plain)
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// Copyright (c) 2019-2021 Alexander Medvednikov. All rights reserved.
// Use of this source code is governed by an MIT license
// that can be found in the LICENSE file.
//
// this is an implementation of wyhash v4
// from https://github.com/wangyi-fudan/wyhash
//
// TODO: use u128 once implemented
// currently the C version performs slightly better
// because it uses 128 bit int when available and
// branch prediction hints. the C version will be
// removed once the perfomance is matched.
// you can test performance by running:
// `v run cmd/tools/bench/wyhash.v`
// try running with and without the `-prod` flag
module hash

const (
	wyp0 = u64(0xa0761d6478bd642f)
	wyp1 = u64(0xe7037ed1a0b428db)
	wyp2 = u64(0x8ebc6af09c88c6e3)
	wyp3 = u64(0x589965cc75374cc3)
	wyp4 = u64(0x1d8e4e27c47d124f)
)

[inline]
pub fn sum64_string(key string, seed u64) u64 {
	return wyhash_c(key.str, u64(key.len), seed)
}

[inline]
pub fn sum64(key []byte, seed u64) u64 {
	return wyhash_c(&byte(key.data), u64(key.len), seed)
}

[inline]
fn wyrotr(v u64, k u32) u64 {
	return (v >> k) | (v << (64 - k))
}

[inline]
pub fn wymum(a u64, b u64) u64 {
	/*
	mut r := u128(a)
	r = r*b
	return (r>>64)^r
	*/
	mask32 := u32(4294967295)
	x0 := a & mask32
	x1 := a >> 32
	y0 := b & mask32
	y1 := b >> 32
	w0 := x0 * y0
	t := x1 * y0 + (w0 >> 32)
	mut w1 := t & mask32
	w2 := t >> 32
	w1 += x0 * y1
	hi := x1 * y1 + w2 + (w1 >> 32)
	lo := a * b
	return hi ^ lo
}

[inline]
fn wyr3(p &byte, k u64) u64 {
	unsafe {
		return (u64(p[0]) << 16) | (u64(p[k >> 1]) << 8) | u64(p[k - 1])
	}
}

[inline]
fn wyr4(p &byte) u64 {
	unsafe {
		return u32(p[0]) | (u32(p[1]) << u32(8)) | (u32(p[2]) << u32(16)) | (u32(p[3]) << u32(24))
	}
}

[inline]
fn wyr8(p &byte) u64 {
	unsafe {
		return u64(p[0]) | (u64(p[1]) << 8) | (u64(p[2]) << 16) | (u64(p[3]) << 24) | (u64(p[4]) << 32) | (u64(p[5]) << 40) | (u64(p[6]) << 48) | (u64(p[7]) << 56)
	}
}