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
25typedef struct AVMurMur3 {
26    uint64_t h1, h2;
27    uint8_t state[16];
28    int state_pos;
29    uint64_t len;
30} AVMurMur3;
31
32AVMurMur3 *av_murmur3_alloc(void)
33{
34    return av_mallocz(sizeof(AVMurMur3));
35}
36
37void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
38{
39    memset(c, 0, sizeof(*c));
40    c->h1 = c->h2 = seed;
41}
42
43void av_murmur3_init(AVMurMur3 *c)
44{
45    // arbitrary random number as seed
46    av_murmur3_init_seeded(c, 0x725acc55daddca55);
47}
48
49static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
50static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
51
52#define ROT(a, b) ((a << b) | (a >> (64 - b)))
53
54static 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
63static 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
72static 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
82static 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
92void 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
131static 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
141void 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}
156
157#ifdef TEST
158int main(void)
159{
160    int i;
161    uint8_t hash_result[16] = {0};
162    AVMurMur3 *ctx = av_murmur3_alloc();
163#if 1
164    uint8_t in[256] = {0};
165    uint8_t *hashes = av_mallocz(256 * 16);
166    for (i = 0; i < 256; i++)
167    {
168        in[i] = i;
169        av_murmur3_init_seeded(ctx, 256 - i);
170        // Note: this actually tests hashing 0 bytes
171        av_murmur3_update(ctx, in, i);
172        av_murmur3_final(ctx, hashes + 16 * i);
173    }
174    av_murmur3_init_seeded(ctx, 0);
175    av_murmur3_update(ctx, hashes, 256 * 16);
176    av_murmur3_final(ctx, hash_result);
177    av_free(hashes);
178    av_freep(&ctx);
179    printf("result: 0x%"PRIx64" 0x%"PRIx64"\n", AV_RL64(hash_result), AV_RL64(hash_result + 8));
180    // official reference value is 32 bit
181    return AV_RL32(hash_result) != 0x6384ba69;
182#else
183    uint8_t *in = av_mallocz(512*1024);
184    av_murmur3_init(ctx);
185    for (i = 0; i < 40*1024; i++)
186        av_murmur3_update(ctx, in, 512*1024);
187    av_murmur3_final(ctx, hash_result);
188    av_free(in);
189    return hash_result[0];
190#endif
191}
192#endif
193