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;
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 #if FF_API_CRYPTO_SIZE_T
96 #else
97 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, size_t len)
98 #endif
99 {
100  const uint8_t *end;
101  uint64_t h1 = c->h1, h2 = c->h2;
102  uint64_t k1, k2;
103  if (len <= 0) return;
104  c->len += len;
105  if (c->state_pos > 0) {
106  while (c->state_pos < 16) {
107  c->state[c->state_pos++] = *src++;
108  if (--len <= 0) return;
109  }
110  c->state_pos = 0;
111  k1 = get_k1(c->state);
112  k2 = get_k2(c->state);
113  h1 = update_h1(k1, h1, h2);
114  h2 = update_h2(k2, h1, h2);
115  }
116 
117  end = src + (len & ~15);
118  while (src < end) {
119  // These could be done sequentially instead
120  // of interleaved, but like this is over 10% faster
121  k1 = get_k1(src);
122  k2 = get_k2(src);
123  h1 = update_h1(k1, h1, h2);
124  h2 = update_h2(k2, h1, h2);
125  src += 16;
126  }
127  c->h1 = h1;
128  c->h2 = h2;
129 
130  len &= 15;
131  if (len > 0) {
132  memcpy(c->state, src, len);
133  c->state_pos = len;
134  }
135 }
136 
137 static inline uint64_t fmix(uint64_t k)
138 {
139  k ^= k >> 33;
140  k *= UINT64_C(0xff51afd7ed558ccd);
141  k ^= k >> 33;
142  k *= UINT64_C(0xc4ceb9fe1a85ec53);
143  k ^= k >> 33;
144  return k;
145 }
146 
148 {
149  uint64_t h1 = c->h1, h2 = c->h2;
150  memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
151  h1 ^= get_k1(c->state) ^ c->len;
152  h2 ^= get_k2(c->state) ^ c->len;
153  h1 += h2;
154  h2 += h1;
155  h1 = fmix(h1);
156  h2 = fmix(h2);
157  h1 += h2;
158  h2 += h1;
159  AV_WL64(dst, h1);
160  AV_WL64(dst + 8, h2);
161 }
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
av_murmur3_update
void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
Update hash context with new data.
Definition: murmur3.c:95
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:147
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:137
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
uint8_t
uint8_t
Definition: audio_convert.c:194
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:237
len
int len
Definition: vorbis_enc_data.h:452
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
murmur3.h
update_h1
static uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:74