[FFmpeg-devel] [PATCH] Add 128 bit murmur3 hash function.

Reimar Döffinger Reimar.Doeffinger at gmx.de
Thu May 9 19:26:05 CEST 2013


Signed-off-by: Reimar Döffinger <Reimar.Doeffinger at gmx.de>
---
 libavutil/Makefile       |    3 +
 libavutil/murmur3.c      |  162 ++++++++++++++++++++++++++++++++++++++++++++++
 libavutil/murmur3.h      |   32 +++++++++
 tests/fate/libavutil.mak |    4 ++
 tests/ref/fate/murmur3   |    1 +
 5 files changed, 202 insertions(+)
 create mode 100644 libavutil/murmur3.c
 create mode 100644 libavutil/murmur3.h
 create mode 100644 tests/ref/fate/murmur3

diff --git a/libavutil/Makefile b/libavutil/Makefile
index 15a9e4a..f40f6fb 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -34,6 +34,7 @@ HEADERS = adler32.h                                                     \
           mathematics.h                                                 \
           md5.h                                                         \
           mem.h                                                         \
+          murmur3.h                                                     \
           dict.h                                                        \
           old_pix_fmts.h                                                \
           opt.h                                                         \
@@ -92,6 +93,7 @@ OBJS = adler32.o                                                        \
        mathematics.o                                                    \
        md5.o                                                            \
        mem.o                                                            \
+       murmur3.o                                                        \
        dict.o                                                           \
        opt.o                                                            \
        parseutils.o                                                     \
@@ -138,6 +140,7 @@ TESTPROGS = adler32                                                     \
             lfg                                                         \
             lls                                                         \
             md5                                                         \
+            murmur3                                                     \
             opt                                                         \
             pca                                                         \
             parseutils                                                  \
diff --git a/libavutil/murmur3.c b/libavutil/murmur3.c
new file mode 100644
index 0000000..c456438
--- /dev/null
+++ b/libavutil/murmur3.c
@@ -0,0 +1,162 @@
+/*
+ * Copyright (C) 2013 Reimar Döffinger <Reimar.Doeffinger at gmx.de>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+#include <stdint.h>
+#include "mem.h"
+#include "intreadwrite.h"
+#include "murmur3.h"
+
+typedef struct AVMurMur3 {
+    uint64_t h1, h2;
+    uint8_t state[16];
+    int state_pos;
+    uint64_t len;
+} AVMurMur3;
+
+AVMurMur3 *av_murmur3_alloc(void)
+{
+    return av_mallocz(sizeof(AVMurMur3));
+}
+
+void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
+{
+    memset(c, 0, sizeof(*c));
+    c->h1 = c->h2 = seed;
+}
+
+void av_murmur3_init(AVMurMur3 *c)
+{
+    // arbitrary random number as seed
+    av_murmur3_init_seeded(c, 0x725acc55daddca55);
+}
+
+static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
+static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
+
+#define ROT(a, b) ((a << b) | (a >> (64 - b)))
+
+static uint64_t inline get_k1(const uint8_t *src)
+{
+    uint64_t k = AV_RL64(src);
+    k *= c1;
+    k = ROT(k, 31);
+    k *= c2;
+    return k;
+}
+
+static uint64_t inline get_k2(const uint8_t *src)
+{
+    uint64_t k = AV_RL64(src + 8);
+    k *= c2;
+    k = ROT(k, 33);
+    k *= c1;
+    return k;
+}
+
+static void inline update_128bit(AVMurMur3 *c, const uint8_t *src)
+{
+    uint64_t k = get_k1(src);
+    k ^= c->h1;
+    k = ROT(k, 27);
+    k += c->h2;
+    k *= 5;
+    k += 0x52dce729;
+    c->h1 = k;
+
+    k = get_k2(src);
+    k ^= c->h2;
+    k = ROT(k, 31);
+    k += c->h1;
+    k *= 5;
+    k += 0x38495ab5;
+    c->h2 = k;
+}
+
+void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
+{
+    if (len <= 0) return;
+    c->len += len;
+    if (c->state_pos > 0) {
+        while (c->state_pos < 16) {
+            c->state[c->state_pos++] = *src++;
+            if (--len <= 0) return;
+        }
+        c->state_pos = 0;
+        update_128bit(c, c->state);
+    }
+    while (len >= 16) {
+        update_128bit(c, src);
+        src += 16;
+        len -= 16;
+    }
+    if (len > 0) {
+        memcpy(c->state, src, len);
+        c->state_pos = len;
+    }
+}
+
+static inline uint64_t fmix(uint64_t k)
+{
+    k ^= k >> 33;
+    k *= UINT64_C(0xff51afd7ed558ccd);
+    k ^= k >> 33;
+    k *= UINT64_C(0xc4ceb9fe1a85ec53);
+    k ^= k >> 33;
+    return k;
+}
+
+void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
+{
+    memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
+    c->h1 ^= get_k1(c->state) ^ c->len;
+    c->h2 ^= get_k2(c->state) ^ c->len;
+    c->h1 += c->h2;
+    c->h2 += c->h1;
+    c->h1 = fmix(c->h1);
+    c->h2 = fmix(c->h2);
+    c->h1 += c->h2;
+    c->h2 += c->h1;
+    AV_WL64(dst, c->h1);
+    AV_WL64(dst + 8, c->h2);
+}
+
+#ifdef TEST
+int main(void)
+{
+    int i;
+    uint8_t in[256] = {0};
+    uint8_t *hashes = av_mallocz(256 * 16);
+    uint8_t hash_result[8] = {0};
+    AVMurMur3 *ctx = av_murmur3_alloc();
+    for (i = 0; i < 256; i++)
+    {
+        in[i] = i;
+        av_murmur3_init_seeded(ctx, 256 - i);
+        // Note: this actually tests hashing 0 bytes
+        av_murmur3_update(ctx, in, i);
+        av_murmur3_final(ctx, hashes + 16 * i);
+    }
+    av_murmur3_init_seeded(ctx, 0);
+    av_murmur3_update(ctx, hashes, 256 * 16);
+    av_murmur3_final(ctx, hash_result);
+    printf("result: 0x%"PRIx64" 0x%"PRIx64"\n", AV_RL64(hash_result), AV_RL64(hash_result + 8));
+    // official reference value is 32 bit
+    return AV_RL32(hash_result) != 0x6384ba69;
+}
+#endif
diff --git a/libavutil/murmur3.h b/libavutil/murmur3.h
new file mode 100644
index 0000000..f29ed97
--- /dev/null
+++ b/libavutil/murmur3.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2013 Reimar Döffinger <Reimar.Doeffinger at gmx.de>
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_MURMUR3_H
+#define AVUTIL_MURMUR3_H
+
+#include <stdint.h>
+
+struct AVMurMur3 *av_murmur3_alloc(void);
+void av_murmur3_init_seeded(struct AVMurMur3 *c, uint64_t seed);
+void av_murmur3_init(struct AVMurMur3 *c);
+void av_murmur3_update(struct AVMurMur3 *c, const uint8_t *src, int len);
+void av_murmur3_final(struct AVMurMur3 *c, uint8_t dst[16]);
+
+#endif /* AVUTIL_MURMUR3_H */
diff --git a/tests/fate/libavutil.mak b/tests/fate/libavutil.mak
index 2508ba0..d086a66 100644
--- a/tests/fate/libavutil.mak
+++ b/tests/fate/libavutil.mak
@@ -54,6 +54,10 @@ FATE_LIBAVUTIL += fate-md5
 fate-md5: libavutil/md5-test$(EXESUF)
 fate-md5: CMD = run libavutil/md5-test
 
+FATE_LIBAVUTIL += fate-murmur3
+fate-murmur3: libavutil/murmur3-test$(EXESUF)
+fate-murmur3: CMD = run libavutil/murmur3-test
+
 FATE_LIBAVUTIL += fate-parseutils
 fate-parseutils: libavutil/parseutils-test$(EXESUF)
 fate-parseutils: CMD = run libavutil/parseutils-test
diff --git a/tests/ref/fate/murmur3 b/tests/ref/fate/murmur3
new file mode 100644
index 0000000..cd5c0e8
--- /dev/null
+++ b/tests/ref/fate/murmur3
@@ -0,0 +1 @@
+result: 0x63f3de036384ba69 0x7192878ce684ed2d
-- 
1.7.10.4



More information about the ffmpeg-devel mailing list