[FFmpeg-devel] [PATCH] Add 128 bit murmur3 hash function.
Michael Niedermayer
michaelni at gmx.at
Fri May 10 04:14:13 CEST 2013
On Thu, May 09, 2013 at 07:26:05PM +0200, Reimar Döffinger wrote:
> 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;
if the 32bit var is placed later this might avoid padding for
alignmentg in the struct
> +
> +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;
> +}
interleaving the operations a bit might improve performance
> +
> +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};
array too small
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
There will always be a question for which you do not know the correct answer.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20130510/1df83a01/attachment.asc>
More information about the ffmpeg-devel
mailing list