harec

commit d06c0e1b569aaf4dc2c23af1ab360d0c61ba69bc
parent 63ab73c5535a958ec4e3524a640a75a220076f5f
Author: Drew DeVault <sir@cmpwn.com>
Date:   Thu, 14 Jan 2021 09:37:04 -0500

type store: switch to FNV-1A hashing function

This hash is more suitable for an ABI specification, and we will likely
want to use it as such in the foreseeable future to obtain a unique ID
for every type.

Diffstat:
M
include/util.h
 | 
7
++++---
M
src/type_store.c
 | 
34
+++++++++++++++++-----------------
M
src/util.c
 | 
15
++++++++-------

3 files changed, 29 insertions(+), 27 deletions(-)
diff --git a/include/util.h b/include/util.h
@@ -1,11 +1,12 @@
 #ifndef HARE_UTIL_H
 #define HARE_UTIL_H
 #include <assert.h>
+#include <stdint.h>
 
-#define DJB2_INIT 5381
+#define FNV1A_INIT 14695981039346656037UL
 
-unsigned long djb2(unsigned long hash, char c);
-unsigned long djb2_s(unsigned long hash, const char *str);
+uint64_t fnv1a(uint64_t hash, char c);
+uint64_t fnv1a_s(uint64_t hash, const char *str);
 void *xcalloc(size_t n, size_t s);
 void *xrealloc(void *p, size_t s);
 
diff --git a/src/type_store.c b/src/type_store.c
@@ -291,9 +291,9 @@ builtin_type_for_storage(enum type_storage storage, bool is_const)
 static unsigned long
 type_hash(struct type_store *store, const struct type *type)
 {
-	unsigned long hash = DJB2_INIT;
-	hash = djb2(hash, type->storage);
-	hash = djb2(hash, type->flags);
+	uint64_t hash = FNV1A_INIT;
+	hash = fnv1a(hash, type->storage);
+	hash = fnv1a(hash, type->flags);
 	switch (type->storage) {
 	case TYPE_STORAGE_BOOL:
 	case TYPE_STORAGE_CHAR:
@@ -319,39 +319,39 @@ type_hash(struct type_store *store, const struct type *type)
 	case TYPE_STORAGE_ALIAS:
 		for (const struct identifier *ident = &type->alias.ident; ident;
 				ident = ident->ns) {
-			hash = djb2_s(hash, ident->name);
+			hash = fnv1a_s(hash, ident->name);
 		}
-		hash = djb2(hash, type_hash(store, type->alias.type));
+		hash = fnv1a(hash, type_hash(store, type->alias.type));
 		break;
 	case TYPE_STORAGE_ARRAY:
-		hash = djb2(hash, type_hash(store, type->array.members));
-		hash = djb2(hash, type->array.length);
+		hash = fnv1a(hash, type_hash(store, type->array.members));
+		hash = fnv1a(hash, type->array.length);
 		break;
 	case TYPE_STORAGE_FUNCTION:
-		hash = djb2(hash, type_hash(store, type->func.result));
-		hash = djb2(hash, type->func.variadism);
-		hash = djb2(hash, type->func.flags);
+		hash = fnv1a(hash, type_hash(store, type->func.result));
+		hash = fnv1a(hash, type->func.variadism);
+		hash = fnv1a(hash, type->func.flags);
 		for (struct type_func_param *param = type->func.params;
 				param; param = param->next) {
-			hash = djb2(hash, type_hash(store, param->type));
+			hash = fnv1a(hash, type_hash(store, param->type));
 		}
 		break;
 	case TYPE_STORAGE_ENUM:
 		assert(0); // TODO
 	case TYPE_STORAGE_POINTER:
-		hash = djb2(hash, type->pointer.flags);
-		hash = djb2(hash, type_hash(store, type->pointer.referent));
+		hash = fnv1a(hash, type->pointer.flags);
+		hash = fnv1a(hash, type_hash(store, type->pointer.referent));
 		break;
 	case TYPE_STORAGE_SLICE:
-		hash = djb2(hash, type_hash(store, type->array.members));
+		hash = fnv1a(hash, type_hash(store, type->array.members));
 		break;
 	case TYPE_STORAGE_STRUCT:
 	case TYPE_STORAGE_UNION:
 		for (const struct struct_field *field = type->struct_union.fields;
 				field; field = field->next) {
-			hash = djb2_s(hash, field->name);
-			hash = djb2(hash, type_hash(store, field->type));
-			hash = djb2(hash, field->offset);
+			hash = fnv1a_s(hash, field->name);
+			hash = fnv1a(hash, type_hash(store, field->type));
+			hash = fnv1a(hash, field->offset);
 		}
 		break;
 	case TYPE_STORAGE_TAGGED_UNION:
diff --git a/src/util.c b/src/util.c
@@ -1,19 +1,20 @@
 #include <stdlib.h>
+#include <stdint.h>
 // Do not include this header:
 //#include "util.h"
 
-unsigned long
-djb2(unsigned long hash, char c)
+uint64_t
+fnv1a(uint64_t hash, unsigned char c)
 {
-	return ((hash << 5) + hash) + c;
+	return (hash ^ c) * 1099511628211;
 }
 
-unsigned long
-djb2_s(unsigned long hash, const char *str)
+uint64_t
+fnv1a_s(uint64_t hash, const char *str)
 {
-	char c;
+	unsigned char c;
 	while ((c = *str++)) {
-		hash = djb2(hash, c);
+		hash = fnv1a(hash, c);
 	}
 	return hash;
 }