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 #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;
28  int state_pos;
29  uint64_t len;
30 } AVMurMur3;
31 
33 {
34  return av_mallocz(sizeof(AVMurMur3));
35 }
36 
38 {
39  memset(c, 0, sizeof(*c));
40  c->h1 = c->h2 = seed;
41 }
42 
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 inline uint64_t 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 inline uint64_t 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 inline uint64_t 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 #if FF_API_CRYPTO_SIZE_T
94 #else
95 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, size_t len)
96 #endif
97 {
98  const uint8_t *end;
99  uint64_t h1 = c->h1, h2 = c->h2;
100  uint64_t k1, k2;
101  if (len <= 0) return;
102  c->len += len;
103  if (c->state_pos > 0) {
104  while (c->state_pos < 16) {
105  c->state[c->state_pos++] = *src++;
106  if (--len <= 0) return;
107  }
108  c->state_pos = 0;
109  k1 = get_k1(c->state);
110  k2 = get_k2(c->state);
111  h1 = update_h1(k1, h1, h2);
112  h2 = update_h2(k2, h1, h2);
113  }
114 
115  end = src + (len & ~15);
116  while (src < end) {
117  // These could be done sequentially instead
118  // of interleaved, but like this is over 10% faster
119  k1 = get_k1(src);
120  k2 = get_k2(src);
121  h1 = update_h1(k1, h1, h2);
122  h2 = update_h2(k2, h1, h2);
123  src += 16;
124  }
125  c->h1 = h1;
126  c->h2 = h2;
127 
128  len &= 15;
129  if (len > 0) {
130  memcpy(c->state, src, len);
131  c->state_pos = len;
132  }
133 }
134 
135 static inline uint64_t fmix(uint64_t k)
136 {
137  k ^= k >> 33;
138  k *= UINT64_C(0xff51afd7ed558ccd);
139  k ^= k >> 33;
140  k *= UINT64_C(0xc4ceb9fe1a85ec53);
141  k ^= k >> 33;
142  return k;
143 }
144 
146 {
147  uint64_t h1 = c->h1, h2 = c->h2;
148  memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
149  h1 ^= get_k1(c->state) ^ c->len;
150  h2 ^= get_k2(c->state) ^ c->len;
151  h1 += h2;
152  h2 += h1;
153  h1 = fmix(h1);
154  h2 = fmix(h2);
155  h1 += h2;
156  h2 += h1;
157  AV_WL64(dst, h1);
158  AV_WL64(dst + 8, h2);
159 }
AV_RL64
uint64_t_TMPL AV_RL64
Definition: bytestream.h:87
ROT
#define ROT(a, b)
Definition: murmur3.c:52
end
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:90
c1
static const uint64_t c1
Definition: murmur3.c:49
AVMurMur3::state
uint8_t state[16]
Definition: murmur3.c:27
AVMurMur3::state_pos
int state_pos
Definition: murmur3.c:28
get_k2
static uint64_t get_k2(const uint8_t *src)
Definition: murmur3.c:63
AVMurMur3::h2
uint64_t h2
Definition: murmur3.c:26
src
#define src
Definition: vp8dsp.c:254
intreadwrite.h
av_murmur3_alloc
AVMurMur3 * av_murmur3_alloc(void)
Allocate an AVMurMur3 hash context.
Definition: murmur3.c:32
av_murmur3_update
void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
Update hash context with new data.
Definition: murmur3.c:93
AVMurMur3::h1
uint64_t h1
Definition: murmur3.c:26
av_murmur3_final
void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
Finish hashing and output digest value.
Definition: murmur3.c:145
update_h2
static uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:82
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:135
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:54
AVMurMur3
Definition: murmur3.c:25
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:236
len
int len
Definition: vorbis_enc_data.h:452
AVMurMur3::len
uint64_t len
Definition: murmur3.c:29
c2
static const uint64_t c2
Definition: murmur3.c:50
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:37
av_murmur3_init
void av_murmur3_init(AVMurMur3 *c)
Initialize or reinitialize an AVMurMur3 hash context.
Definition: murmur3.c:43
mem.h
murmur3.h
update_h1
static uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:72