FNV-1a hashing algorithm

Signed-off-by: Mel <mel@rnrd.eu>

1 files changed, 44 insertions, 26 deletions

diff --git a/boot/common.c b/boot/common.c
index 2f9bdd0..3da5750 100644
--- a/boot/common.c
+++ b/boot/common.c
@@ -269,7 +269,8 @@ void
 _array_push(struct _Array* array, const void* element)
 {
     check(array->length < array->capacity, "array is full: %u/%u", array->length, array->capacity);
-    memcpy((ascii*)array->data + (array->length * array->element_size), element, array->element_size);
+    memcpy(
+        (ascii*)array->data + (array->length * array->element_size), element, array->element_size);
     ++array->length;
 }
 
@@ -279,7 +280,8 @@ _array_push(struct _Array* array, const void* element)
 void*
 _array_at(const struct _Array* array, uint index)
 {
-    check(index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
+    check(
+        index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
     return (ascii*)array->data + (index * array->element_size);
 }
 
@@ -289,7 +291,8 @@ _array_at(const struct _Array* array, uint index)
 void
 _array_get(const struct _Array* array, uint index, void* out_element)
 {
-    check(index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
+    check(
+        index < array->length, "array index out of bounds: %u (length: %u)", index, array->length);
     memcpy(out_element, (ascii*)array->data + (index * array->element_size), array->element_size);
 }
 
@@ -309,11 +312,7 @@ struct _Slice
 struct _Slice
 _slice_new(void* data, uint length, uint element_size)
 {
-    struct _Slice slice = {
-        .data = data,
-        .length = length,
-        .element_size = element_size
-    };
+    struct _Slice slice = { .data = data, .length = length, .element_size = element_size };
     return slice;
 }
 
@@ -330,7 +329,8 @@ slice_length(const struct _Slice* slice)
 void*
 _slice_at(const struct _Slice* slice, uint index)
 {
-    check(index < slice->length, "slice index out of bounds: %u (length: %u)", index, slice->length);
+    check(
+        index < slice->length, "slice index out of bounds: %u (length: %u)", index, slice->length);
     return (ascii*)slice->data + (index * slice->element_size);
 }
 
@@ -338,9 +338,9 @@ _slice_at(const struct _Slice* slice, uint index)
 
 // a macro for iterating over each element in an array.
 #define FOR_EACH_ARRAY(type, element_var, array_ptr, action) \
-    for (uint i = 0; i < array_length(array_ptr); ++i) { \
-        type element_var = *array_at(type, array_ptr, i); \
-        action; \
+    for (uint i = 0; i < array_length(array_ptr); ++i) {     \
+        type element_var = *array_at(type, array_ptr, i);    \
+        action;                                              \
     }
 
 // the global string region.
@@ -552,7 +552,8 @@ string_append_c_str(struct String a, const ascii* b)
     if (c_str_len == 0) return a;
 
     uint new_length = a.length + c_str_len;
-    check(region_string_cursor + new_length + 1 < REGION_SIZE, "out of string memory for append_c_str");
+    check(region_string_cursor + new_length + 1 < REGION_SIZE,
+          "out of string memory for append_c_str");
 
     ascii* at = region_string + region_string_cursor;
     region_string_cursor += new_length + 1;
@@ -580,7 +581,8 @@ string_clone(struct String s)
 struct String
 string_slice(struct String s, uint start, uint end)
 {
-    check(start <= end && end <= s.length, "invalid slice range [%u, %u) for string of length %u", start, end, s.length);
+    check(start <= end && end <= s.length, "invalid slice range [%u, %u) for string of length %u",
+          start, end, s.length);
 
     if (start == end) return string_empty();
 
@@ -596,7 +598,7 @@ string_set(struct String s, uint index, ascii c)
     check(index < s.length, "index out of bounds: %u (length: %u)", index, s.length);
 
     struct String new_s = string_clone(s);
-    new_s.data[index] = c;  // safe because we just allocated this
+    new_s.data[index] = c; // safe because we just allocated this
     return new_s;
 }
 
@@ -837,7 +839,8 @@ struct String_Buffer
 struct String_Buffer
 string_buffer_new(uint capacity)
 {
-    check(capacity + 1 < REGION_SIZE - region_string_cursor, "out of string memory for string buffer");
+    check(capacity + 1 < REGION_SIZE - region_string_cursor,
+          "out of string memory for string buffer");
 
     ascii* at = region_string + region_string_cursor;
     region_string_cursor += capacity + 1;
@@ -902,7 +905,8 @@ string_buffer_clear(struct String_Buffer* buffer)
 void
 string_buffer_push(struct String_Buffer* buffer, ascii c)
 {
-    check(buffer->length < buffer->capacity, "string buffer is full: %u/%u", buffer->length, buffer->capacity);
+    check(buffer->length < buffer->capacity, "string buffer is full: %u/%u", buffer->length,
+          buffer->capacity);
     buffer->data[buffer->length] = c;
     ++buffer->length;
     buffer->data[buffer->length] = '\0';
@@ -927,13 +931,10 @@ string_buffer_append(struct String_Buffer* buffer, struct String s)
 {
     if (string_is_empty(s)) return;
 
-    check(buffer->length + s.length <= buffer->capacity,
-          "string buffer overflow: %u + %u > %u",
+    check(buffer->length + s.length <= buffer->capacity, "string buffer overflow: %u + %u > %u",
           buffer->length, s.length, buffer->capacity);
 
-    for (uint i = 0; i < s.length; ++i) {
-        buffer->data[buffer->length + i] = s.data[i];
-    }
+    for (uint i = 0; i < s.length; ++i) { buffer->data[buffer->length + i] = s.data[i]; }
     buffer->length += s.length;
     buffer->data[buffer->length] = '\0';
 }
@@ -945,12 +946,10 @@ string_buffer_append_c_str(struct String_Buffer* buffer, const ascii* c_str)
     uint c_str_len = strlen(c_str);
     if (c_str_len == 0) return;
 
-    check(buffer->length + c_str_len <= buffer->capacity,
-          "string buffer overflow: %u + %u > %u",
+    check(buffer->length + c_str_len <= buffer->capacity, "string buffer overflow: %u + %u > %u",
           buffer->length, c_str_len, buffer->capacity);
 
-    for (uint i = 0; i < c_str_len; ++i)
-        buffer->data[buffer->length + i] = c_str[i];
+    for (uint i = 0; i < c_str_len; ++i) buffer->data[buffer->length + i] = c_str[i];
 
     buffer->length += c_str_len;
     buffer->data[buffer->length] = '\0';
@@ -1024,3 +1023,22 @@ crc32_posix(struct String str)
 
     return hash;
 }
+
+// FNV-1a hashing algorithm, 64-bit variant.
+// teeny-tiny, fast, pretty okay-ish distribution, and just about good
+// enough for content-addressing and de-duplication!
+// see: https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+uint64
+fnv1a_64(struct String str)
+{
+    const uint64 fnv_offset_basis = 0xCBF29CE484222325ULL;
+    const uint64 fnv_prime = 0x100000001B3ULL;
+
+    uint64 hash = fnv_offset_basis;
+    STRING_ITERATE(i, byte_of_data, str)
+    {
+        hash ^= (uint64)byte_of_data;
+        hash *= fnv_prime;
+    }
+    return hash;
+}