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