add string literals via the data segment

1 files changed, 155 insertions, 0 deletions

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");
+    }
+}