FFmpeg
murmur3.c
Go to the documentation of this file.
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 
21 #include <stddef.h>
22 #include <stdint.h>
23 #include "mem.h"
24 #include "intreadwrite.h"
25 #include "murmur3.h"
26 
27 typedef struct AVMurMur3 {
28  uint64_t h1, h2;
29  uint8_t state[16];
30  int state_pos;
31  uint64_t len;
32 } AVMurMur3;
33 
35 {
36  return av_mallocz(sizeof(AVMurMur3));
37 }
38 
40 {
41  memset(c, 0, sizeof(*c));
42  c->h1 = c->h2 = seed;
43 }
44 
46 {
47  // arbitrary random number as seed
48  av_murmur3_init_seeded(c, 0x725acc55daddca55);
49 }
50 
51 static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
52 static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
53 
54 #define ROT(a, b) (((a) << (b)) | ((a) >> (64 - (b))))
55 
56 static uint64_t inline get_k1(const uint8_t *src)
57 {
58  uint64_t k = AV_RL64(src);
59  k *= c1;
60  k = ROT(k, 31);
61  k *= c2;
62  return k;
63 }
64 
65 static inline uint64_t get_k2(const uint8_t *src)
66 {
67  uint64_t k = AV_RL64(src + 8);
68  k *= c2;
69  k = ROT(k, 33);
70  k *= c1;
71  return k;
72 }
73 
74 static inline uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
75 {
76  k ^= h1;
77  k = ROT(k, 27);
78  k += h2;
79  k *= 5;
80  k += 0x52dce729;
81  return k;
82 }
83 
84 static inline uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
85 {
86  k ^= h2;
87  k = ROT(k, 31);
88  k += h1;
89  k *= 5;
90  k += 0x38495ab5;
91  return k;
92 }
93 
94 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, size_t len)
95 {
96  const uint8_t *end;
97  uint64_t h1 = c->h1, h2 = c->h2;
98  uint64_t k1, k2;
99  if (len <= 0) return;
100  c->len += len;
101  if (c->state_pos > 0) {
102  while (c->state_pos < 16) {
103  c->state[c->state_pos++] = *src++;
104  if (--len <= 0) return;
105  }
106  c->state_pos = 0;
107  k1 = get_k1(c->state);
108  k2 = get_k2(c->state);
109  h1 = update_h1(k1, h1, h2);
110  h2 = update_h2(k2, h1, h2);
111  }
112 
113  end = src + (len & ~15);
114  while (src < end) {
115  // These could be done sequentially instead
116  // of interleaved, but like this is over 10% faster
117  k1 = get_k1(src);
118  k2 = get_k2(src);
119  h1 = update_h1(k1, h1, h2);
120  h2 = update_h2(k2, h1, h2);
121  src += 16;
122  }
123  c->h1 = h1;
124  c->h2 = h2;
125 
126  len &= 15;
127  if (len > 0) {
128  memcpy(c->state, src, len);
129  c->state_pos = len;
130  }
131 }
132 
133 static inline uint64_t fmix(uint64_t k)
134 {
135  k ^= k >> 33;
136  k *= UINT64_C(0xff51afd7ed558ccd);
137  k ^= k >> 33;
138  k *= UINT64_C(0xc4ceb9fe1a85ec53);
139  k ^= k >> 33;
140  return k;
141 }
142 
143 void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
144 {
145  uint64_t h1 = c->h1, h2 = c->h2;
146  memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
147  h1 ^= get_k1(c->state) ^ c->len;
148  h2 ^= get_k2(c->state) ^ c->len;
149  h1 += h2;
150  h2 += h1;
151  h1 = fmix(h1);
152  h2 = fmix(h2);
153  h1 += h2;
154  h2 += h1;
155  AV_WL64(dst, h1);
156  AV_WL64(dst + 8, h2);
157 }
AV_RL64
uint64_t_TMPL AV_RL64
Definition: bytestream.h:91
ROT
#define ROT(a, b)
Definition: murmur3.c:54
c1
static const uint64_t c1
Definition: murmur3.c:51
AVMurMur3::state
uint8_t state[16]
Definition: murmur3.c:29
AVMurMur3::state_pos
int state_pos
Definition: murmur3.c:30
get_k2
static uint64_t get_k2(const uint8_t *src)
Definition: murmur3.c:65
AVMurMur3::h2
uint64_t h2
Definition: murmur3.c:28
intreadwrite.h
av_murmur3_alloc
AVMurMur3 * av_murmur3_alloc(void)
Allocate an AVMurMur3 hash context.
Definition: murmur3.c:34
src
#define src
Definition: vp8dsp.c:255
AVMurMur3::h1
uint64_t h1
Definition: murmur3.c:28
av_murmur3_final
void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
Finish hashing and output digest value.
Definition: murmur3.c:143
update_h2
static uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:84
seed
static unsigned int seed
Definition: videogen.c:78
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
fmix
static uint64_t fmix(uint64_t k)
Definition: murmur3.c:133
AV_WL64
#define AV_WL64(p, v)
Definition: intreadwrite.h:440
get_k1
static uint64_t get_k1(const uint8_t *src)
Definition: murmur3.c:56
AVMurMur3
Definition: murmur3.c:27
av_mallocz
void * av_mallocz(size_t size)
Allocate a memory block with alignment suitable for all memory accesses (including vectors if availab...
Definition: mem.c:263
len
int len
Definition: vorbis_enc_data.h:426
AVMurMur3::len
uint64_t len
Definition: murmur3.c:31
c2
static const uint64_t c2
Definition: murmur3.c:52
av_murmur3_init_seeded
void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
Initialize or reinitialize an AVMurMur3 hash context with a seed.
Definition: murmur3.c:39
av_murmur3_init
void av_murmur3_init(AVMurMur3 *c)
Initialize or reinitialize an AVMurMur3 hash context.
Definition: murmur3.c:45
mem.h
av_murmur3_update
void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, size_t len)
Update hash context with new data.
Definition: murmur3.c:94
murmur3.h
update_h1
static uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:74