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
av_murmur3_alloc(void)34 AVMurMur3 *av_murmur3_alloc(void)
35 {
36 return av_mallocz(sizeof(AVMurMur3));
37 }
38
av_murmur3_init_seeded(AVMurMur3 * c,uint64_t seed)39 void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
40 {
41 memset(c, 0, sizeof(*c));
42 c->h1 = c->h2 = seed;
43 }
44
av_murmur3_init(AVMurMur3 * c)45 void av_murmur3_init(AVMurMur3 *c)
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
get_k1(const uint8_t * src)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
get_k2(const uint8_t * src)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
update_h1(uint64_t k,uint64_t h1,uint64_t h2)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
update_h2(uint64_t k,uint64_t h1,uint64_t h2)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
av_murmur3_update(AVMurMur3 * c,const uint8_t * src,int len)95 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
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
fmix(uint64_t k)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
av_murmur3_final(AVMurMur3 * c,uint8_t dst[16])147 void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
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 }
162