diff options
author | Garima Singh <garima.singh@microsoft.com> | 2020-03-30 00:31:24 +0000 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2020-03-30 09:59:53 -0700 |
commit | f52207a45ca9e7cfbe431f4ffff79b3fdbcf3a37 (patch) | |
tree | f0cec587c23bece10b7daf2fe2ea9a0a3e8596f0 /bloom.h | |
parent | commit-graph: define and use MAX_NUM_CHUNKS (diff) | |
download | tgif-f52207a45ca9e7cfbe431f4ffff79b3fdbcf3a37.tar.xz |
bloom.c: add the murmur3 hash implementation
In preparation for computing changed paths Bloom filters,
implement the Murmur3 hash algorithm as described in [1].
It hashes the given data using the given seed and produces
a uniformly distributed hash value.
[1] https://en.wikipedia.org/wiki/MurmurHash#Algorithm
Helped-by: Derrick Stolee <dstolee@microsoft.com>
Helped-by: Szeder Gábor <szeder.dev@gmail.com>
Reviewed-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'bloom.h')
-rw-r--r-- | bloom.h | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/bloom.h b/bloom.h new file mode 100644 index 0000000000..d0fcc5f0aa --- /dev/null +++ b/bloom.h @@ -0,0 +1,13 @@ +#ifndef BLOOM_H +#define BLOOM_H + +/* + * Calculate the murmur3 32-bit hash value for the given data + * using the given seed. + * Produces a uniformly distributed hash value. + * Not considered to be cryptographically secure. + * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm + */ +uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len); + +#endif
\ No newline at end of file |