FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
murmur3.c
Go to the documentation of this file.
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;
28  int state_pos;
29  uint64_t len;
30 } AVMurMur3;
31 
33 {
34  return av_mallocz(sizeof(AVMurMur3));
35 }
36 
38 {
39  memset(c, 0, sizeof(*c));
40  c->h1 = c->h2 = seed;
41 }
42 
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 
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 
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
uint64_t h2
Definition: murmur3.c:26
#define ROT(a, b)
Definition: murmur3.c:52
memory handling functions
uint64_t_TMPL AV_RL64
Definition: bytestream.h:85
AVMurMur3 * av_murmur3_alloc(void)
Definition: murmur3.c:32
uint64_t h1
Definition: murmur3.c:26
int state_pos
Definition: murmur3.c:28
uint8_t
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:67
void av_murmur3_init(AVMurMur3 *c)
Definition: murmur3.c:43
static const uint64_t c1
Definition: murmur3.c:49
static uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:82
#define AV_WL64(p, v)
Definition: intreadwrite.h:440
void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
Definition: murmur3.c:141
static uint64_t get_k2(const uint8_t *src)
Definition: murmur3.c:63
uint8_t state[16]
Definition: murmur3.c:27
void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
Definition: murmur3.c:92
uint64_t len
Definition: murmur3.c:29
static uint64_t get_k1(const uint8_t *src)
Definition: murmur3.c:54
AVS_Value src
Definition: avisynth_c.h:482
static unsigned int seed
Definition: videogen.c:78
uint8_t pi<< 24) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0f/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_U8, uint8_t,(*(constuint8_t *) pi-0x80)*(1.0/(1<< 7))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S16, int16_t,(*(constint16_t *) pi >>8)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0f/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S16, int16_t,*(constint16_t *) pi *(1.0/(1<< 15))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_S32, int32_t,(*(constint32_t *) pi >>24)+0x80) CONV_FUNC_GROUP(AV_SAMPLE_FMT_FLT, float, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0f/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_DBL, double, AV_SAMPLE_FMT_S32, int32_t,*(constint32_t *) pi *(1.0/(1U<< 31))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_FLT, float, av_clip_uint8(lrintf(*(constfloat *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_FLT, float, av_clip_int16(lrintf(*(constfloat *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_FLT, float, av_clipl_int32(llrintf(*(constfloat *) pi *(1U<< 31)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_U8, uint8_t, AV_SAMPLE_FMT_DBL, double, av_clip_uint8(lrint(*(constdouble *) pi *(1<< 7))+0x80)) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S16, int16_t, AV_SAMPLE_FMT_DBL, double, av_clip_int16(lrint(*(constdouble *) pi *(1<< 15)))) CONV_FUNC_GROUP(AV_SAMPLE_FMT_S32, int32_t, AV_SAMPLE_FMT_DBL, double, av_clipl_int32(llrint(*(constdouble *) pi *(1U<< 31))))#defineSET_CONV_FUNC_GROUP(ofmt, ifmt) staticvoidset_generic_function(AudioConvert *ac){}voidff_audio_convert_free(AudioConvert **ac){if(!*ac) return;ff_dither_free(&(*ac) ->dc);av_freep(ac);}AudioConvert *ff_audio_convert_alloc(AVAudioResampleContext *avr, enumAVSampleFormatout_fmt, enumAVSampleFormatin_fmt, intchannels, intsample_rate, intapply_map){AudioConvert *ac;intin_planar, out_planar;ac=av_mallocz(sizeof(*ac));if(!ac) returnNULL;ac->avr=avr;ac->out_fmt=out_fmt;ac->in_fmt=in_fmt;ac->channels=channels;ac->apply_map=apply_map;if(avr->dither_method!=AV_RESAMPLE_DITHER_NONE &&av_get_packed_sample_fmt(out_fmt)==AV_SAMPLE_FMT_S16 &&av_get_bytes_per_sample(in_fmt)>2){ac->dc=ff_dither_alloc(avr, out_fmt, in_fmt, channels, sample_rate, apply_map);if(!ac->dc){av_free(ac);returnNULL;}returnac;}in_planar=ff_sample_fmt_is_planar(in_fmt, channels);out_planar=ff_sample_fmt_is_planar(out_fmt, channels);if(in_planar==out_planar){ac->func_type=CONV_FUNC_TYPE_FLAT;ac->planes=in_planar?ac->channels:1;}elseif(in_planar) ac->func_type=CONV_FUNC_TYPE_INTERLEAVE;elseac->func_type=CONV_FUNC_TYPE_DEINTERLEAVE;set_generic_function(ac);if(ARCH_AARCH64) ff_audio_convert_init_aarch64(ac);if(ARCH_ARM) ff_audio_convert_init_arm(ac);if(ARCH_X86) ff_audio_convert_init_x86(ac);returnac;}intff_audio_convert(AudioConvert *ac, AudioData *out, AudioData *in){intuse_generic=1;intlen=in->nb_samples;intp;if(ac->dc){av_log(ac->avr, AV_LOG_TRACE,"%dsamples-audio_convert:%sto%s(dithered)\n", len, av_get_sample_fmt_name(ac->in_fmt), av_get_sample_fmt_name(ac->out_fmt));returnff_convert_dither(ac-> in
static uint64_t fmix(uint64_t k)
Definition: murmur3.c:131
void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
Definition: murmur3.c:37
static double c[64]
static const uint64_t c2
Definition: murmur3.c:50
#define av_free(p)
int len
#define av_freep(p)
static uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
Definition: murmur3.c:72
int main(int argc, char **argv)
Definition: main.c:22
uint64_t_TMPL AV_WL64 unsigned int_TMPL AV_RL32
Definition: bytestream.h:85
void * av_mallocz(size_t size)
Allocate a block of size bytes with alignment suitable for all memory accesses (including vectors if ...
Definition: mem.c:250