path: root/libavutil/murmur3.c (plain)
blob: 4271e01453f77237eb71d9babb989004b0728d04

1	/*
2	* Copyright (C) 2013 Reimar Döffinger <Reimar.Doeffinger@gmx.de>
3	*
4	* This file is part of FFmpeg.
5	*
6	* FFmpeg is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU Lesser General Public
8	* License as published by the Free Software Foundation; either
9	* version 2.1 of the License, or (at your option) any later version.
10	*
11	* FFmpeg is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14	* Lesser General Public License for more details.
15	*
16	* You should have received a copy of the GNU Lesser General Public
17	* License along with FFmpeg; if not, write to the Free Software
18	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19	*/
20	#include <stdint.h>
21	#include "mem.h"
22	#include "intreadwrite.h"
23	#include "murmur3.h"
24
25	typedef struct AVMurMur3 {
26	uint64_t h1, h2;
27	uint8_t state[16];
28	int state_pos;
29	uint64_t len;
30	} AVMurMur3;
31
32	AVMurMur3 *av_murmur3_alloc(void)
33	{
34	return av_mallocz(sizeof(AVMurMur3));
35	}
36
37	void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
38	{
39	memset(c, 0, sizeof(*c));
40	c->h1 = c->h2 = seed;
41	}
42
43	void av_murmur3_init(AVMurMur3 *c)
44	{
45	// arbitrary random number as seed
46	av_murmur3_init_seeded(c, 0x725acc55daddca55);
47	}
48
49	static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
50	static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
51
52	#define ROT(a, b) (((a) << (b)) | ((a) >> (64 - (b))))
53
54	static uint64_t inline get_k1(const uint8_t *src)
55	{
56	uint64_t k = AV_RL64(src);
57	k *= c1;
58	k = ROT(k, 31);
59	k *= c2;
60	return k;
61	}
62
63	static uint64_t inline get_k2(const uint8_t *src)
64	{
65	uint64_t k = AV_RL64(src + 8);
66	k *= c2;
67	k = ROT(k, 33);
68	k *= c1;
69	return k;
70	}
71
72	static uint64_t inline update_h1(uint64_t k, uint64_t h1, uint64_t h2)
73	{
74	k ^= h1;
75	k = ROT(k, 27);
76	k += h2;
77	k *= 5;
78	k += 0x52dce729;
79	return k;
80	}
81
82	static uint64_t inline update_h2(uint64_t k, uint64_t h1, uint64_t h2)
83	{
84	k ^= h2;
85	k = ROT(k, 31);
86	k += h1;
87	k *= 5;
88	k += 0x38495ab5;
89	return k;
90	}
91
92	void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
93	{
94	const uint8_t *end;
95	uint64_t h1 = c->h1, h2 = c->h2;
96	uint64_t k1, k2;
97	if (len <= 0) return;
98	c->len += len;
99	if (c->state_pos > 0) {
100	while (c->state_pos < 16) {
101	c->state[c->state_pos++] = *src++;
102	if (--len <= 0) return;
103	}
104	c->state_pos = 0;
105	k1 = get_k1(c->state);
106	k2 = get_k2(c->state);
107	h1 = update_h1(k1, h1, h2);
108	h2 = update_h2(k2, h1, h2);
109	}
110
111	end = src + (len & ~15);
112	while (src < end) {
113	// These could be done sequentially instead
114	// of interleaved, but like this is over 10% faster
115	k1 = get_k1(src);
116	k2 = get_k2(src);
117	h1 = update_h1(k1, h1, h2);
118	h2 = update_h2(k2, h1, h2);
119	src += 16;
120	}
121	c->h1 = h1;
122	c->h2 = h2;
123
124	len &= 15;
125	if (len > 0) {
126	memcpy(c->state, src, len);
127	c->state_pos = len;
128	}
129	}
130
131	static inline uint64_t fmix(uint64_t k)
132	{
133	k ^= k >> 33;
134	k *= UINT64_C(0xff51afd7ed558ccd);
135	k ^= k >> 33;
136	k *= UINT64_C(0xc4ceb9fe1a85ec53);
137	k ^= k >> 33;
138	return k;
139	}
140
141	void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
142	{
143	uint64_t h1 = c->h1, h2 = c->h2;
144	memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
145	h1 ^= get_k1(c->state) ^ c->len;
146	h2 ^= get_k2(c->state) ^ c->len;
147	h1 += h2;
148	h2 += h1;
149	h1 = fmix(h1);
150	h2 = fmix(h2);
151	h1 += h2;
152	h2 += h1;
153	AV_WL64(dst, h1);
154	AV_WL64(dst + 8, h2);
155	}
156