Use string hashes

1 files changed, 47 insertions, 10 deletions

diff --git a/tr8as.c b/tr8as.c
index f6628b7..cfaa80b 100644
--- a/tr8as.c
+++ b/tr8as.c
@@ -49,7 +49,7 @@ typedef struct
 
 typedef struct
 {
-    char id[MAX_ID + 1];
+    uint32_t id;
     uint16_t addr;
     Location loc;
 } Label;
@@ -63,7 +63,8 @@ typedef enum
 
 typedef struct
 {
-    char id[MAX_ID + 1];
+    uint32_t id;
+    char label[MAX_ID + 1];
     Mod mod;
     uint16_t mask;
     uint16_t addr;
@@ -72,7 +73,7 @@ typedef struct
 
 typedef struct
 {
-    char id[MAX_ID + 1];
+    uint32_t id;
     char value[MAX_ID + 1];
     Location loc;
 } Define;
@@ -137,6 +138,39 @@ static uint8_t error(const char *msg, const char *reason)
     return 0;
 }
 
+static uint32_t str_hash(char const *str)
+{
+    uint32_t m = 0x5bd1e995u;
+    uint32_t h = 0x31313137u;
+    size_t length = strlen(str);
+
+    while (length >= 4)
+    {
+        uint32_t k = *(uint32_t *)str;
+        k *= m;
+        k ^= k >> 24;
+        k *= m;
+        h *= m;
+        h ^= k;
+        str += 4;
+        length -= 4;
+    }
+    switch (length) {
+        case 3:
+            h ^= str[ 2 ] << 16;
+        case 2:
+            h ^= str[ 1 ] << 8;
+        case 1:
+            h ^= str[ 0 ];
+            h *= m;
+    }
+    h ^= h >> 13;
+    h *= m;
+    h ^= h >> 15;
+
+    return h;
+}
+
 static char * skip_whitespace(char *c)
 {
     while (*c && isspace(*c))
@@ -180,9 +214,10 @@ static uint8_t isspecial(char c)
 static char * find_define(As *as, char *word, char *found)
 {
     uint8_t i;
+    uint32_t id = str_hash(word);
 
     for (i = 0; i < as->dcnt; i++)
-        if (!strcmp(word, as->defs[i].id))
+        if (id == as->defs[i].id)
             return find_define(as, as->defs[i].value, as->defs[i].value);
 
     return found;
@@ -198,7 +233,7 @@ static uint8_t new_define(As *as, char *id, char *value)
     if (!strcmp(id, value))
         return error_l("Recursive definition", &as->loc, id);
 
-    strcpy(as->defs[as->dcnt].id, id);
+    as->defs[as->dcnt].id = str_hash(id);
     strcpy(as->defs[as->dcnt].value, value);
 
     as->defs[as->dcnt].loc.filename = as->loc.filename;
@@ -333,9 +368,10 @@ static uint8_t parse_register(char *word)
 static Label * find_label(As *as, char *word)
 {
     uint8_t i;
+    uint32_t id = str_hash(word);
 
     for (i = 0; i < as->lcnt; i++)
-        if (!strcmp(word, as->labels[i].id))
+        if (id == as->labels[i].id)
             return &as->labels[i];
 
     return NULL;
@@ -346,7 +382,7 @@ static uint8_t new_label(As *as, char *word)
     if (find_label(as, word))
         return error_l("Label redefined", &as->loc, word);
 
-    strcpy(as->labels[as->lcnt].id, word);
+    as->labels[as->lcnt].id = str_hash(word);
 
     as->labels[as->lcnt].loc.filename = as->loc.filename;
     as->labels[as->lcnt].loc.line = as->loc.line;
@@ -380,7 +416,8 @@ static uint8_t new_ref(As *as, char *word, uint16_t mask, uint16_t addr)
     if (mask == 0xff && mod == ModNone)
         return error_l("Overflow in immediate", &as->loc, word);
 
-    strcpy(as->refs[as->rcnt].id, pt);
+    as->refs[as->rcnt].id = str_hash(pt);
+    strcpy(as->refs[as->rcnt].label, pt);
     as->refs[as->rcnt].mod = mod;
     as->refs[as->rcnt].mask = mask;
     as->refs[as->rcnt].loc = as->loc;
@@ -400,9 +437,9 @@ static uint8_t resolve(As *as)
 
     for (i = 0; i < as->rcnt; i++)
     {
-        label = find_label(as, as->refs[i].id);
+        label = find_label(as, as->refs[i].label);
         if (!label)
-            return error_l("Unresolved reference", &as->refs[i].loc, as->refs[i].id);
+            return error_l("Unresolved reference", &as->refs[i].loc, as->refs[i].label);
 
         v = label->addr;
         switch (as->refs[i].mod)