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 }
uint64_t h2
Definition: murmur3.c:26
#define ROT(a, b)
Definition: murmur3.c:52
Memory handling functions.
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
uint64_t_TMPL AV_RL64
Definition: bytestream.h:87
void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
Initialize or reinitialize an AVMurMur3 hash context with a seed.
Definition: murmur3.c:37
Public header for MurmurHash3 hash function implementation.
#define src
Definition: vp8dsp.c:254
uint64_t h1
Definition: murmur3.c:26
int state_pos
Definition: murmur3.c:28
uint8_t
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:90
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
static const uint64_t c1
Definition: murmur3.c:49
void av_murmur3_init(AVMurMur3 *c)
Initialize or reinitialize an AVMurMur3 hash context.
Definition: murmur3.c:43
static uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:82
#define AV_WL64(p, v)
Definition: intreadwrite.h:440
static uint64_t get_k2(const uint8_t *src)
Definition: murmur3.c:63
uint8_t state[16]
Definition: murmur3.c:27
uint64_t len
Definition: murmur3.c:29
static uint64_t get_k1(const uint8_t *src)
Definition: murmur3.c:54
static unsigned int seed
Definition: videogen.c:78
static uint64_t fmix(uint64_t k)
Definition: murmur3.c:135
void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
Update hash context with new data.
Definition: murmur3.c:93
static const uint64_t c2
Definition: murmur3.c:50
static uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:72
AVMurMur3 * av_murmur3_alloc(void)
Allocate an AVMurMur3 hash context.
Definition: murmur3.c:32
void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
Finish hashing and output digest value.
Definition: murmur3.c:145