]> git.sesse.net Git - ffmpeg/blob - libavutil/murmur3.c
Merge commit '17adcc40adf1f30cba55c9727dabc1365944d32b'
[ffmpeg] / libavutil / murmur3.c
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;
27     uint8_t state[16];
28     int state_pos;
29     uint64_t len;
30 } AVMurMur3;
31
32 AVMurMur3 *av_murmur3_alloc(void)
33 {
34     return av_mallocz(sizeof(AVMurMur3));
35 }
36
37 void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
38 {
39     memset(c, 0, sizeof(*c));
40     c->h1 = c->h2 = seed;
41 }
42
43 void av_murmur3_init(AVMurMur3 *c)
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 uint64_t inline 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 uint64_t inline 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 uint64_t inline 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 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
93 {
94     const uint8_t *end;
95     uint64_t h1 = c->h1, h2 = c->h2;
96     uint64_t k1, k2;
97     if (len <= 0) return;
98     c->len += len;
99     if (c->state_pos > 0) {
100         while (c->state_pos < 16) {
101             c->state[c->state_pos++] = *src++;
102             if (--len <= 0) return;
103         }
104         c->state_pos = 0;
105         k1 = get_k1(c->state);
106         k2 = get_k2(c->state);
107         h1 = update_h1(k1, h1, h2);
108         h2 = update_h2(k2, h1, h2);
109     }
110
111     end = src + (len & ~15);
112     while (src < end) {
113         // These could be done sequentially instead
114         // of interleaved, but like this is over 10% faster
115         k1 = get_k1(src);
116         k2 = get_k2(src);
117         h1 = update_h1(k1, h1, h2);
118         h2 = update_h2(k2, h1, h2);
119         src += 16;
120     }
121     c->h1 = h1;
122     c->h2 = h2;
123
124     len &= 15;
125     if (len > 0) {
126         memcpy(c->state, src, len);
127         c->state_pos = len;
128     }
129 }
130
131 static inline uint64_t fmix(uint64_t k)
132 {
133     k ^= k >> 33;
134     k *= UINT64_C(0xff51afd7ed558ccd);
135     k ^= k >> 33;
136     k *= UINT64_C(0xc4ceb9fe1a85ec53);
137     k ^= k >> 33;
138     return k;
139 }
140
141 void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
142 {
143     uint64_t h1 = c->h1, h2 = c->h2;
144     memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
145     h1 ^= get_k1(c->state) ^ c->len;
146     h2 ^= get_k2(c->state) ^ c->len;
147     h1 += h2;
148     h2 += h1;
149     h1 = fmix(h1);
150     h2 = fmix(h2);
151     h1 += h2;
152     h2 += h1;
153     AV_WL64(dst, h1);
154     AV_WL64(dst + 8, h2);
155 }