git.sesse.net Git - ffmpeg/blob - 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
  21 #include <stddef.h>
  22 #include <stdint.h>
  23 #include "mem.h"
  24 #include "intreadwrite.h"
  25 #include "murmur3.h"
  26
  27 typedef struct AVMurMur3 {
  28     uint64_t h1, h2;
  29     uint8_t state[16];
  30     int state_pos;
  31     uint64_t len;
  32 } AVMurMur3;
  33
  34 AVMurMur3 *av_murmur3_alloc(void)
  35 {
  36     return av_mallocz(sizeof(AVMurMur3));
  37 }
  38
  39 void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
  40 {
  41     memset(c, 0, sizeof(*c));
  42     c->h1 = c->h2 = seed;
  43 }
  44
  45 void av_murmur3_init(AVMurMur3 *c)
  46 {
  47     // arbitrary random number as seed
  48     av_murmur3_init_seeded(c, 0x725acc55daddca55);
  49 }
  50
  51 static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
  52 static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
  53
  54 #define ROT(a, b) (((a) << (b)) | ((a) >> (64 - (b))))
  55
  56 static uint64_t inline get_k1(const uint8_t *src)
  57 {
  58     uint64_t k = AV_RL64(src);
  59     k *= c1;
  60     k = ROT(k, 31);
  61     k *= c2;
  62     return k;
  63 }
  64
  65 static inline uint64_t get_k2(const uint8_t *src)
  66 {
  67     uint64_t k = AV_RL64(src + 8);
  68     k *= c2;
  69     k = ROT(k, 33);
  70     k *= c1;
  71     return k;
  72 }
  73
  74 static inline uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
  75 {
  76     k ^= h1;
  77     k = ROT(k, 27);
  78     k += h2;
  79     k *= 5;
  80     k += 0x52dce729;
  81     return k;
  82 }
  83
  84 static inline uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
  85 {
  86     k ^= h2;
  87     k = ROT(k, 31);
  88     k += h1;
  89     k *= 5;
  90     k += 0x38495ab5;
  91     return k;
  92 }
  93
  94 void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, size_t len)
  95 {
  96     const uint8_t *end;
  97     uint64_t h1 = c->h1, h2 = c->h2;
  98     uint64_t k1, k2;
  99     if (len <= 0) return;
 100     c->len += len;
 101     if (c->state_pos > 0) {
 102         while (c->state_pos < 16) {
 103             c->state[c->state_pos++] = *src++;
 104             if (--len <= 0) return;
 105         }
 106         c->state_pos = 0;
 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);
 111     }
 112
 113     end = src + (len & ~15);
 114     while (src < end) {
 115         // These could be done sequentially instead
 116         // of interleaved, but like this is over 10% faster
 117         k1 = get_k1(src);
 118         k2 = get_k2(src);
 119         h1 = update_h1(k1, h1, h2);
 120         h2 = update_h2(k2, h1, h2);
 121         src += 16;
 122     }
 123     c->h1 = h1;
 124     c->h2 = h2;
 125
 126     len &= 15;
 127     if (len > 0) {
 128         memcpy(c->state, src, len);
 129         c->state_pos = len;
 130     }
 131 }
 132
 133 static inline uint64_t fmix(uint64_t k)
 134 {
 135     k ^= k >> 33;
 136     k *= UINT64_C(0xff51afd7ed558ccd);
 137     k ^= k >> 33;
 138     k *= UINT64_C(0xc4ceb9fe1a85ec53);
 139     k ^= k >> 33;
 140     return k;
 141 }
 142
 143 void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
 144 {
 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;
 149     h1 += h2;
 150     h2 += h1;
 151     h1 = fmix(h1);
 152     h2 = fmix(h2);
 153     h1 += h2;
 154     h2 += h1;
 155     AV_WL64(dst, h1);
 156     AV_WL64(dst + 8, h2);
 157 }