add string literals via the data segment

6 files changed, 222 insertions, 36 deletions

diff --git a/README.md b/README.md
index 3ded28b..52b508f 100644
--- a/README.md
+++ b/README.md
@@ -14,3 +14,4 @@ TODO soon:
 - [ ] use evaluated types to make code gen around math better
 - [ ] support for functions/function pointers as types
   - [ ] move the "expression not callable" stuff to the type checker
+- [ ] we've implemented a hash map 3 times now for different types, time to consolidate
diff --git a/codegen.c b/codegen.c
index 3d96d33..d9b2962 100644
--- a/codegen.c
+++ b/codegen.c
@@ -2,6 +2,7 @@
 #include "codegen.h"
 #include "scope.h"
 #include "register.h"
+#include "dseg.h"
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -27,6 +28,7 @@ static struct reg* MULDIV_OVERFLOW_REG = &RDX;
 #define FULL_REG_SZ 8
 #define WORD_SZ 2
 
+static struct dseg dseg;
 static struct scope* scope;
 static const struct fn_decl_node* active_fn;
 static integral_t branch_counter = 0;
@@ -95,7 +97,7 @@ static struct lval_def allocate_stack(
     const struct type* type
 ) {
     integral_t type_sz = get_effective_data_type(type)->sz;
-    fprintf(outfile, "\tsub rsp, %llu\n", type_sz);
+    fprintf(outfile, "\tsub rsp, 0x%llx\n", type_sz);
     scope->bp_offset += type_sz;
     return (struct lval_def) {
         .loc = {
@@ -156,14 +158,14 @@ static void emit_storage_loc(
             break;
         case STO_STACK:
             if (loc->bp_offset < 0)
-                fprintf(outfile, "[rbp + %lld]", -loc->bp_offset);
+                fprintf(outfile, "[rbp + 0x%llx]", -loc->bp_offset);
             else if (loc->bp_offset > 0)
-                fprintf(outfile, "[rbp - %lld]", loc->bp_offset);
+                fprintf(outfile, "[rbp - 0x%llx]", loc->bp_offset);
             else
                 fprintf(outfile, "[rbp]");
             break;
         case STO_IMM:
-            fprintf(outfile, "%llu", loc->value);
+            fprintf(outfile, "0x%llx", loc->value);
             break;
         case STO_UNRESOLVED:
             CGEN_PANIC("can't emit unresolved storage location");
@@ -346,7 +348,14 @@ static void emit_str_lit(
     const struct lval_def* dst
 ) {
     if (dst != NULL) {
-        CGEN_PANIC("string literals are not implemented");
+        const char* dseg_sym = dseg_put(&dseg, (struct dseg_entry) {
+            .type = ENT_STRING,
+            .key.string = node->val,
+        });
+        emit_mov(outfile, dst, &(struct storage_location) {
+            .type = STO_LABEL,
+            .label = dseg_sym,
+        });
     }
 }
 
@@ -370,10 +379,7 @@ static void emit_decl(
         allocate_stack(outfile, node->def_ref->type);
     node->def_ref->loc = var_dst.loc;
 
-    fprintf(outfile, "\t; %s", node->def_ref->name);
-    integral_t dst_sz = get_effective_data_type(var_dst.type)->sz;
-    emit_storage_loc(outfile, &var_dst.loc, dst_sz);
-    fprintf(outfile, "\n");
+    fprintf(outfile, "\t; %s\n", node->def_ref->name);
 
     if (node->initial_value != NULL)
         emit_expr(outfile, node->initial_value, &var_dst);
@@ -833,8 +839,8 @@ void emit_code(struct ast* ast, const char* path) {
     FILE* outfile = fopen(path, "w");
     if (outfile == NULL) CCC_PANIC;
 
+    dseg_init(&dseg);
     scope = ast->root_scope;
-    fprintf(outfile, "section .text\n");
 
     /* output all function declarations in the root scope as globals */
     const struct root_node* node = ast->root_node;
@@ -844,7 +850,8 @@ void emit_code(struct ast* ast, const char* path) {
     }
     fprintf(outfile, "\n");
 
-    /* actual code body */
+    /* text (code) segment */
+    fprintf(outfile, "section .text\n");
     node = ast->root_node;
     while (node != NULL) {
         emit_root_node(outfile, node);
@@ -852,5 +859,10 @@ void emit_code(struct ast* ast, const char* path) {
         node = node->next;
     }
 
+    /* data segment */
+    fprintf(outfile, "\n");
+    emit_dseg(outfile, &dseg);
+
+    dseg_destroy(&dseg);
     fclose(outfile);
 }
diff --git a/dseg.c b/dseg.c
new file mode 100644
index 0000000..09e18a3
--- /dev/null
+++ b/dseg.c
@@ -0,0 +1,155 @@
+#include "dseg.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#define DSEG_PANIC(msg) {fprintf(stderr, "dseg error: " msg "\n"); exit(1);}
+#define DEFAULT_SIZE 16
+#define STRING_PATTERN "str%llu"
+
+static integral_t string_counter = 0;
+
+void dseg_init(struct dseg* dseg) {
+    dseg->entries = ccc_alloc(DEFAULT_SIZE * sizeof(struct dseg_entry*));
+    dseg->cap = DEFAULT_SIZE;
+}
+
+static void dseg_entry_destroy(struct dseg_entry* entry) {
+    free(entry->symbol);
+}
+
+void dseg_destroy(struct dseg* dseg) {
+    for (integral_t i = 0; i < dseg->cap; i++) {
+        if (dseg->entries[i] == NULL) continue;
+        dseg_entry_destroy(dseg->entries[i]);
+        free(dseg->entries[i]);
+    }
+    free(dseg->entries);
+}
+
+static inline integral_t advance_hash(
+    integral_t hash,
+    integral_t val,
+    integral_t cap
+) {
+    return ((hash << 5) - hash + val) % cap;;
+}
+
+static integral_t hash_string(const char* str, integral_t cap) {
+    integral_t hash = 0, i = 0;
+    while (str[i] != 0) hash = advance_hash(hash, str[i++], cap);
+    return hash;
+}
+
+static integral_t hash_ent(const struct dseg_entry* ent, integral_t cap) {
+    switch (ent->type) {
+        case ENT_STRING:
+            return hash_string(ent->key.string, cap);
+    }
+    DSEG_PANIC("hash function not defined for entry type");
+}
+
+static bool ent_eq(const struct dseg_entry* a, const struct dseg_entry* b) {
+    if (a->type != b->type) return false;
+    switch (a->type) {
+        case ENT_STRING:
+            return strcmp(a->key.string, b->key.string) == 0;
+    }
+    DSEG_PANIC("equality function not defined for entry type");
+}
+
+static void ent_assign_key(struct dseg_entry* ent) {
+    switch (ent->type) {
+        case ENT_STRING:
+            integral_t strnum = string_counter++;
+            int req_sz = snprintf(NULL, 0, STRING_PATTERN, strnum);
+            if (req_sz < 0) CCC_PANIC;
+            req_sz += 1; // null terminator
+            ent->symbol = ccc_alloc(req_sz);
+            snprintf(ent->symbol, req_sz, STRING_PATTERN, strnum);
+            break;
+    }
+}
+
+static struct dseg_entry** dseg_cell(
+    const struct dseg* dseg,
+    const struct dseg_entry* ent
+) {
+    integral_t orig_idx = hash_ent(ent, dseg->cap);
+    integral_t idx = orig_idx;
+
+    do {
+        if (dseg->entries[idx] == NULL || ent_eq(dseg->entries[idx], ent))
+            return &dseg->entries[idx];
+    } while ((idx = (idx + 1) % dseg->cap) != orig_idx);
+    return NULL;
+}
+
+static void rehash_dseg(struct dseg* dseg) {
+    struct dseg_entry** old_ents = dseg->entries;
+    integral_t old_cap = dseg->cap;
+
+    dseg->cap = (dseg->cap + 1) << 1;
+    dseg->entries = ccc_alloc(dseg->cap * sizeof(struct dseg_entry*));
+
+    for (integral_t i = 0; i < old_cap; i++) {
+        if (old_ents[i] == NULL) continue;
+        struct dseg_entry** cell = dseg_cell(dseg, old_ents[i]);
+        if (cell == NULL) {
+            fprintf(stderr, "ccc: data segment rehash failed, likely a bug\n");
+            exit(1);
+        }
+        *cell = old_ents[i];
+    }
+
+    free(old_ents);
+}
+
+const char* dseg_put(struct dseg* dseg, struct dseg_entry entry) {
+    struct dseg_entry** cell = dseg_cell(dseg, &entry);
+    while (cell == NULL) {
+        rehash_dseg(dseg);
+        cell = dseg_cell(dseg, &entry);
+    }
+
+    if (*cell != NULL) return (*cell)->symbol;
+    struct dseg_entry* new_ent = ccc_alloc(sizeof(struct dseg_entry));
+    *cell = new_ent;
+    *new_ent = entry;
+    ent_assign_key(new_ent);
+    return new_ent->symbol;
+}
+
+static inline bool is_printable(char c) {
+    return ' ' <= c && c <= '~';
+}
+
+void emit_string(FILE* outfile, const struct dseg_entry* ent) {
+    const char* str = ent->key.string;
+    fprintf(outfile, "db ");
+    for (integral_t i = 0; str[i] != 0;) {
+        if (is_printable(str[i])) {
+            fprintf(outfile, "\"%c", str[i]);
+            while (is_printable(str[++i])) fputc(str[i], outfile);
+            fprintf(outfile, "\", ");
+        } else {
+            fprintf(outfile, "0x%x, ", str[i++]);
+        }
+    }
+    fprintf(outfile, "0x0");
+}
+
+void emit_dseg(FILE* outfile, const struct dseg* dseg) {
+    fprintf(outfile, "section .data\n");
+    for (integral_t i = 0; i < dseg->cap; i++) {
+        const struct dseg_entry* ent = dseg->entries[i];
+        if (dseg->entries[i] == NULL) continue;
+
+        fprintf(outfile, "\t%s ", ent->symbol);
+        switch (ent->type) {
+            case ENT_STRING:
+                emit_string(outfile, ent);
+                break;
+        }
+        fprintf(outfile, "\n");
+    }
+}
diff --git a/dseg.h b/dseg.h
new file mode 100644
index 0000000..4decf2f
--- /dev/null
+++ b/dseg.h
@@ -0,0 +1,28 @@
+#ifndef DSEG_H
+#define DSEG_H
+
+#include "ccc.h"
+#include <stdio.h>
+
+struct dseg_entry {
+    enum {
+        ENT_STRING,
+    } type;
+    union {
+        const char* string;
+    } key;
+    char* symbol;
+};
+
+struct dseg {
+    struct dseg_entry** entries;
+    integral_t sz;
+    integral_t cap;
+};
+
+void dseg_init(struct dseg* dseg);
+void dseg_destroy(struct dseg* dseg);
+const char* dseg_put(struct dseg* dseg, struct dseg_entry entry);
+void emit_dseg(FILE* outfile, const struct dseg* dseg);
+
+#endif
diff --git a/scope.c b/scope.c
index 3f3dc44..7077748 100644
--- a/scope.c
+++ b/scope.c
@@ -64,12 +64,9 @@ static struct type_alias** type_cell(
 static void rehash_types(struct scope* scope) {
     struct type_alias** old_types = scope->types;
     integral_t old_cap = scope->type_cap;
-    scope->type_cap *= 2;
-    scope->types = calloc(scope->type_cap, sizeof(struct type_def*));
-    if (scope->types == NULL) {
-        fprintf(stderr, "ccc: out of memory\n");
-        exit(1);
-    }
+
+    scope->type_cap = (scope->type_cap + 1) << 1;
+    scope->types = ccc_alloc(scope->type_cap * sizeof(struct type_def*));
 
     for (integral_t i = 0; i < old_cap; i++) {
         if (old_types[i] == NULL) continue;
@@ -81,6 +78,7 @@ static void rehash_types(struct scope* scope) {
         }
         *cell = old_types[i];
     }
+
     free(old_types);
 }
 
@@ -102,12 +100,9 @@ static struct var_def** var_cell(
 static void rehash_vars(struct scope* scope) {
     struct var_def** old_vars = scope->vars;
     integral_t old_cap = scope->var_cap;
-    scope->var_cap *= 2;
-    scope->vars = calloc(scope->var_cap, sizeof(struct var_def*));
-    if (scope->vars == NULL) {
-        fprintf(stderr, "ccc: out of memory\n");
-        exit(1);
-    }
+
+    scope->var_cap = (scope->var_cap + 1) << 1;
+    scope->vars = ccc_alloc(scope->var_cap * sizeof(struct var_def*));
 
     for (integral_t i = 0; i < old_cap; i++) {
         if (old_vars[i] == NULL) continue;
@@ -119,11 +114,12 @@ static void rehash_vars(struct scope* scope) {
         }
         *cell = old_vars[i];
     }
+
     free(old_vars);
 }
 
 void scope_push(struct scope** p_scope) {
-    struct scope* inner_scope = calloc(1, sizeof(struct scope));
+    struct scope* inner_scope = ccc_alloc(sizeof(struct scope));
     scope_init(inner_scope);
     inner_scope->next_out = *p_scope;
     *p_scope = inner_scope;
@@ -160,11 +156,7 @@ const struct type_alias* scope_define_type(
     /* redefinition leaks memory, so refuse */
     if (*cell != NULL) return NULL;
 
-    *cell = calloc(1, sizeof(struct type_alias));
-    if (*cell == NULL) {
-        fprintf(stderr, "ccc: out of memory\n");
-        exit(1);
-    }
+    *cell = ccc_alloc(sizeof(struct type_alias));
     **cell = type;
     return *cell;
 }
@@ -193,13 +185,7 @@ struct var_def* scope_define_var(struct scope* scope, struct var_def var) {
     /* redefinition leaks memory, so refuse */
     if (*cell != NULL) return NULL;
 
-    if (*cell == NULL) {
-        *cell = calloc(1, sizeof(struct var_def));
-        if (*cell == NULL) {
-            fprintf(stderr, "ccc: out of memory\n");
-            exit(1);
-        }
-    }
+    if (*cell == NULL) *cell = ccc_alloc(sizeof(struct var_def));
     **cell = var;
     return *cell;
 }
diff --git a/test/dseg.c b/test/dseg.c
new file mode 100644
index 0000000..fa6a249
--- /dev/null
+++ b/test/dseg.c
@@ -0,0 +1,4 @@
+int main(int argc, char** argv) {
+    char* argb = "\tluhm\\ao\nfortyfive();\n";
+    return 0;
+}