FFmpeg coverage

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