FFmpeg  4.4
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 }
uint8_t
#define AV_RL64
Definition: intreadwrite.h:173
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
AVMurMur3 * av_murmur3_alloc(void)
Allocate an AVMurMur3 hash context.
Definition: murmur3.c:34
void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
Update hash context with new data.
Definition: murmur3.c:95
void av_murmur3_init(AVMurMur3 *c)
Initialize or reinitialize an AVMurMur3 hash context.
Definition: murmur3.c:45
void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
Initialize or reinitialize an AVMurMur3 hash context with a seed.
Definition: murmur3.c:39
void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
Finish hashing and output digest value.
Definition: murmur3.c:147
#define AV_WL64(p, v)
Definition: intreadwrite.h:440
Memory handling functions.
static const uint64_t c2
Definition: murmur3.c:52
#define ROT(a, b)
Definition: murmur3.c:54
static uint64_t get_k2(const uint8_t *src)
Definition: murmur3.c:65
static const uint64_t c1
Definition: murmur3.c:51
static uint64_t get_k1(const uint8_t *src)
Definition: murmur3.c:56
static uint64_t fmix(uint64_t k)
Definition: murmur3.c:137
static uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:74
static uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:84
Public header for MurmurHash3 hash function implementation.
uint64_t h1
Definition: murmur3.c:28
uint64_t len
Definition: murmur3.c:31
uint8_t state[16]
Definition: murmur3.c:29
int state_pos
Definition: murmur3.c:30
uint64_t h2
Definition: murmur3.c:28
#define src
Definition: vp8dsp.c:255
static unsigned int seed
Definition: videogen.c:78
int len
static double c[64]