1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
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");
}
}
|
