2 * Copyright (C) 2013 Reimar Döffinger <Reimar.Doeffinger@gmx.de>
4 * This file is part of FFmpeg.
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.
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.
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
24 #include "intreadwrite.h"
27 typedef struct AVMurMur3 {
34 AVMurMur3 *av_murmur3_alloc(void)
36 return av_mallocz(sizeof(AVMurMur3));
39 void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
41 memset(c, 0, sizeof(*c));
45 void av_murmur3_init(AVMurMur3 *c)
47 // arbitrary random number as seed
48 av_murmur3_init_seeded(c, 0x725acc55daddca55);
51 static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
52 static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
54 #define ROT(a, b) (((a) << (b)) | ((a) >> (64 - (b))))
56 static uint64_t inline get_k1(const uint8_t *src)
58 uint64_t k = AV_RL64(src);
65 static inline uint64_t get_k2(const uint8_t *src)
67 uint64_t k = AV_RL64(src + 8);
74 static inline uint64_t update_h1(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)
94 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, size_t len)
97 uint64_t h1 = c->h1, h2 = c->h2;
101 if (c->state_pos > 0) {
102 while (c->state_pos < 16) {
103 c->state[c->state_pos++] = *src++;
104 if (--len <= 0) return;
107 k1 = get_k1(c->state);
108 k2 = get_k2(c->state);
109 h1 = update_h1(k1, h1, h2);
110 h2 = update_h2(k2, h1, h2);
113 end = src + (len & ~15);
115 // These could be done sequentially instead
116 // of interleaved, but like this is over 10% faster
119 h1 = update_h1(k1, h1, h2);
120 h2 = update_h2(k2, h1, h2);
128 memcpy(c->state, src, len);
133 static inline uint64_t fmix(uint64_t k)
136 k *= UINT64_C(0xff51afd7ed558ccd);
138 k *= UINT64_C(0xc4ceb9fe1a85ec53);
143 void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
145 uint64_t h1 = c->h1, h2 = c->h2;
146 memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
147 h1 ^= get_k1(c->state) ^ c->len;
148 h2 ^= get_k2(c->state) ^ c->len;
156 AV_WL64(dst + 8, h2);