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 }
 156
 157 #ifdef TEST
 158 int 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