You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
94 lines
2.6 KiB
C
94 lines
2.6 KiB
C
#include <assert.h>
|
|
#include <stdbool.h>
|
|
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
/*
|
|
* FNV-1 hash implementation (32-bit aka FNV32_1).
|
|
*
|
|
* See http://isthe.com/chongo/tech/comp/fnv/
|
|
*/
|
|
uint32_t fnv32_1(uint8_t * data, size_t data_len) {
|
|
uint32_t hash;
|
|
|
|
/* Constants, for 32-bit only. */
|
|
uint32_t offset_basis = (uint32_t) 2166136261UL;
|
|
uint32_t FNV_prime = (uint32_t) 16777619UL;
|
|
|
|
hash = offset_basis;
|
|
for (size_t i = 0; i < data_len; i++) {
|
|
hash = hash * FNV_prime; /* implictly modulo 2^32 */
|
|
hash = hash ^ data[i]; /* implictly only on lower octet. */
|
|
}
|
|
return hash;
|
|
}
|
|
|
|
/* Compute FNV-1 hash for the given string (without NUL byte). */
|
|
uint32_t fnv32_1_str(char *string) {
|
|
return fnv32_1((uint8_t *) string, strlen(string));
|
|
}
|
|
|
|
/* Test FNV32_1 */
|
|
void test_fnv32_1() {
|
|
assert(fnv32_1_str("03SB[") == 0x00000000UL);
|
|
assert(fnv32_1_str("") == 0x811c9dc5UL);
|
|
assert(fnv32_1_str("a") == 0x050c5d7eUL);
|
|
assert(fnv32_1_str("b") == 0x050c5d7dUL);
|
|
assert(fnv32_1_str("c") == 0x050c5d7cUL);
|
|
assert(fnv32_1_str("d") == 0x050c5d7bUL);
|
|
assert(fnv32_1_str("e") == 0x050c5d7aUL);
|
|
assert(fnv32_1_str("f") == 0x050c5d79UL);
|
|
assert(fnv32_1_str("fo") == 0x6b772514UL);
|
|
assert(fnv32_1_str("foo") == 0x408f5e13UL);
|
|
assert(fnv32_1_str("foob") == 0xb4b1178bUL);
|
|
assert(fnv32_1_str("fooba") == 0xfdc80fb0UL);
|
|
assert(fnv32_1_str("foobar") == 0x31f0b262UL);
|
|
}
|
|
|
|
|
|
/* Bloom filter data structure */
|
|
const size_t bloom_bits = 64;
|
|
typedef uint64_t bloom_filter_type;
|
|
bloom_filter_type bloom_filter[1] = { 0 }; // XXX should calculate the size here
|
|
|
|
/* Returns the bit in the bloom filter to set/check. */
|
|
size_t bloom_bit(char *string) {
|
|
/* Note: a real bloom filter would use multiple bits and multiple hash fns. */
|
|
return fnv32_1_str(string) % bloom_bits;
|
|
}
|
|
|
|
/* Add a value to the bloom filter. */
|
|
void bloom_add(char *string) {
|
|
size_t i = bloom_bit(string) / sizeof(bloom_filter_type);
|
|
size_t j = bloom_bit(string) % sizeof(bloom_filter_type);
|
|
|
|
bloom_filter[i] |= (1 << j);
|
|
}
|
|
|
|
/* Check if a value might have been seen before. */
|
|
bool bloom_check(char *string) {
|
|
size_t i = bloom_bit(string) / sizeof(bloom_filter_type);
|
|
size_t j = bloom_bit(string) % sizeof(bloom_filter_type);
|
|
|
|
return (bloom_filter[i] & (1 << j)) != 0;
|
|
}
|
|
|
|
/* Test filter */
|
|
void test_bloom_filter() {
|
|
assert(bloom_check("foo") == false);
|
|
bloom_add("foo");
|
|
assert(bloom_check("foo") == true);
|
|
|
|
assert(bloom_check("bar") == false); /* assuming foo's hash values != bar's */
|
|
bloom_add("bar");
|
|
assert(bloom_check("bar") == true);
|
|
}
|
|
|
|
|
|
int main(void) {
|
|
test_fnv32_1();
|
|
test_bloom_filter();
|
|
}
|