+/EE460N

computer architecture

git clone https://git.julia.blue/+/EE460N

Joseph RyanLab 2 first pass (no testing done whatsoever)458988b

master
12.5 KiB405 linesraw
1/*
2        Name 1: Joseph Ryan
3        Name 2: Rahul Butani
4        UTEID 1: jbr2558
5        UTEID 2: rhb834
6*/
7#include <ctype.h>
8#include <stdarg.h>
9#include <stdbool.h>
10#include <stdint.h>
11#include <stdio.h>
12#include <stdlib.h>
13#include <string.h>
14
15#define MAX_LABEL_LEN 20
16#define MAX_SYMBOLS 255
17#define MAX_LINE_LEN 255
18#define NUM_RESERVED 32
19
20FILE* in_file;
21FILE* out_file;
22char buf[MAX_LINE_LEN + 1];
23size_t line_len;
24char pretty_buf[MAX_LINE_LEN + 1];
25char* current = NULL;
26
27const char* reserved[NUM_RESERVED] = {
28    "add",  "and",  "ldb",   "ldw",   "lea",  "stb",  "stw",  "xor",
29    "not",  "lshf", "rshfl", "rshfa", "nop",  "jmp",  "ret",  "jsr",
30    "jsrr", "rti",  "trap",  "getc",  "out",  "puts", "in",   "halt",
31    "br",   "brn",  "brz",   "brp",   "brnz", "brzp", "brnp", "brnzp"};
32
33typedef struct Symbol {
34    uint16_t addr;
35    uint16_t line;
36    char name[MAX_LABEL_LEN + 1];
37} Symbol;
38
39Symbol SymbolTable[MAX_SYMBOLS];
40size_t num_symbols;
41
42uint16_t line_num = 0;
43
44// Prints an error message and the current line, then exits
45void errmsg(int exit_code, const char* fmt, ...) {
46    va_list args;
47    va_start(args, fmt);
48    printf("ERROR at line %d:\n", line_num);
49    printf("\n%s\n\n", pretty_buf);
50    vprintf(fmt, args);
51    va_end(args);
52    printf("\n");
53    exit(exit_code);
54}
55
56// Checks if a string is a reserved word
57_Bool is_reserved(char* s) {
58    for (int i = 0; i < NUM_RESERVED; ++i) {
59        if (!strcmp(s, reserved[i])) {
60            return true;
61        }
62    }
63    return false;
64}
65
66// Converts a string to lowercase in place and returns the same string
67char* lower(char* s) {
68    for (int i = 0; s[i]; ++i) { s[i] = tolower(s[i]); }
69    return s;
70}
71
72// Returns either a pointer to the symbol with the given name,
73// or NULL if it isn't found
74Symbol* get_symbol(char* s) {
75    for (size_t i = 0; i < num_symbols; ++i) {
76        if (!strncmp(SymbolTable[i].name, s, MAX_LABEL_LEN)) {
77            return &SymbolTable[i];
78        }
79    }
80    return NULL;
81}
82
83// Adds a symbol with the given string at the given address
84void add_symbol(char* s, uint16_t addr) {
85    if (isdigit(*s) || *s == 'x') {
86        errmsg(4, "Labels cannot start with 'x' or a number");
87    }
88    for (char* c = s; *c; ++c) {
89        if (!isalnum(*c)) {
90            errmsg(4, "Invalid character in label: %c", *c);
91        }
92    }
93    if (num_symbols == MAX_SYMBOLS) {
94        errmsg(4, "Exceeded translation limit, too many labels");
95    }
96    Symbol* old = get_symbol(s);
97    if (old) {
98        errmsg(4, "Symbol '%s' is already defined on line %d", s, old->line);
99    }
100    SymbolTable[num_symbols] = (Symbol){.addr = addr, .line = line_num};
101    strncpy(SymbolTable[num_symbols++].name, s, MAX_LABEL_LEN + 1);
102}
103
104// Reads from in_file up to the next token and returns it
105char* next_tok() {
106    if (current) {
107        current = strtok(NULL, " ,\t\n");
108    }
109    while (!current) {
110        ++line_num;
111        if (!(current = fgets(buf, MAX_LINE_LEN, in_file))) {
112            errmsg(4, "Reached end of file");
113        }
114        // If we've got a ';', kill:
115        char* pos = strchr(buf, ';');
116        if (pos) {
117            *pos = '\0';
118        }
119        line_len = strlen(buf);
120        strncpy(pretty_buf, buf, MAX_LINE_LEN + 1);
121        current = strtok(buf, " ,\t\n");
122    }
123    return lower(current);
124}
125
126// Reads the next token, but makes sure that it is from the same line
127char* next_arg() {
128    uint16_t temp = line_num;
129    char* tok = next_tok();
130    if (line_num != temp) {
131        errmsg(4, "Incomplete instruction on previous line");
132    }
133    return tok;
134}
135
136// Reads the next argument and returns the corresponding numeric constant
137// Also checks that the result falls within the representable range with the
138// given number of bits and signedness
139int32_t next_num(uint8_t bits, _Bool is_signed) {
140    char* tok = next_arg();
141    size_t len = strlen(tok);
142    if (len == 1) {
143        errmsg(4, "'%s' is an invalid constant", tok);
144    }
145    int base;
146    if (*tok == 'x') {
147        base = 16;
148    } else if (*tok == '#') {
149        base = 10;
150    } else {
151        errmsg(4, "'%s' is an invalid constant", tok);
152    }
153    _Bool neg = (*++tok == '-');
154    if (!is_signed && neg) {
155        errmsg(3, "Negative constant not allowed: '%s'", tok - 2);
156    }
157    char* c = tok + neg;
158    if (!*c--) {
159        errmsg(3, "No constant specified");
160    }
161    while (*++c) {
162        if ((base == 10 && !isdigit(*c)) || (base == 16 && !isxdigit(*c))) {
163            errmsg(4, "'%s' is an invalid base-%d constant", tok, base);
164        }
165    }
166    int32_t num = strtol(tok, NULL, base);
167    if (bits == 17) {
168        if (!(num < 65536 && num >= -32768)) {
169            errmsg(3, "%s is outside the representable range (%d bits)", tok,
170                   bits);
171        }
172        return ((1 << bits) - 1) & num;
173    }
174    if ((is_signed && (num >= 1 << (bits - 1) || num < -1 << (bits - 1))) ||
175        (!is_signed && num >= 1 << bits)) {
176        errmsg(3, "%s is outside the representable range (%d bits)", tok, bits);
177    }
178    return ((1 << bits) - 1) & num;
179}
180
181// Reads the next argument and returns the corresponding register number
182uint8_t next_reg() {
183    char* tok = next_arg();
184    size_t len = strlen(tok);
185    if (len != 2 || !(tok[0] == 'r' && tok[1] >= '0' && tok[1] < '8')) {
186        errmsg(4, "'%s' is an invalid register", tok);
187    }
188    return tok[1] - '0';
189}
190
191// Checks if the next argument is a register without reading from in_file
192_Bool peek_reg() {
193    char* temp = current;
194    // Advance to end of current token
195    while (*temp++) {}
196    // If we're at the end of buf and don't have another token:
197    if ((size_t)(temp - buf) == line_len) {
198        return false;
199    }
200    // Advance to beginning of next token
201    while (*temp && isspace(*temp)) { ++temp; }
202    // Check if it looks like a register constant
203    return *temp && (*temp == 'r' || *temp == 'R');
204}
205
206char* next_string() {
207    // TODO: add support for .stringz
208    return "This assembler doesn't support strings yet\n";
209}
210
211// Reads the next argument and returns the corresponding label's
212// offset from the given address
213// Also checks that said offset is representable by a given number of bits
214int16_t next_label(uint8_t bits, int32_t addr) {
215    char* tok = next_arg();
216    if (isdigit(*tok) || *tok == 'x') {
217        errmsg(4, "Cannot use numeric constant as operand");
218    }
219    Symbol* s = get_symbol(tok);
220    if (!s) {
221        errmsg(1, "Undefined label '%s'", tok);
222    }
223    int16_t offset = (s->addr - (addr + 2)) / 2;
224    if (offset >= 1 << (bits - 1) || offset < -1 << (bits - 1)) {
225        errmsg(4, "Label '%s' is too far away", tok);
226    }
227    return ((1 << bits) - 1) & offset;
228}
229
230// Reads through in_file, ignoring instructions and adding symbols to the table
231void build_table() {
232    char* tok = next_tok();
233    if (strcmp(tok, ".orig")) {
234        errmsg(4, "Expected '.ORIG', found: '%s'", tok);
235    }
236    int addr = next_num(16, false);
237    if (addr % 2) {
238        errmsg(3, ".ORIG address must be byte aligned");
239    }
240    tok = next_tok();
241    while (strcmp(tok, ".end")) {
242        if (!strcmp(tok, ".blkw")) {
243            addr += next_num(16, false); // * 2?
244        } else if (!strcmp(tok, ".stringz")) {
245            addr += strlen(next_string()) + 1;
246        } else {
247            if (!is_reserved(tok) && tok[0] != '.') {
248                uint16_t temp = line_num;
249                next_tok();
250                if (line_num != temp) {
251                    errmsg(2, "Invalid opcode");
252                }
253                add_symbol(tok, addr);
254            }
255            current = NULL;
256            addr += 2;
257        }
258        tok = next_tok();
259    }
260}
261
262// Parses the arguments for the 'add', 'and', and 'xor' instructions
263uint16_t gen_arithmetic() {
264    uint16_t temp = next_reg() << 9 | next_reg() << 6;
265    return temp | (peek_reg() ? next_reg() : (1 << 5 | next_num(5, true)));
266}
267
268// Reads through the file, generating machine code for each instruction and
269// writing it as hex to out_file
270// TODO: Add support for push/pop macros
271void codegen() {
272    // Skip the .orig
273    next_tok();
274    uint16_t addr = next_num(16, false);
275    // First line is the starting address
276    fprintf(out_file, "0x%.4X\n", addr);
277    char* tok = next_tok();
278    while (strcmp(tok, ".end")) {
279        uint16_t inst = 0;
280        if (get_symbol(tok)) {
281            tok = next_arg();
282        }
283        if (!strcmp(tok, "add")) {
284            inst = 0x1000 | gen_arithmetic();
285        } else if (!strcmp(tok, "and")) {
286            inst = 0x5000 | gen_arithmetic();
287        } else if (!strcmp(tok, "xor")) {
288            inst = 0x9000 | gen_arithmetic();
289        } else if (!strcmp(tok, "not")) {
290            inst = 0x903F | next_reg() << 9;
291            inst |= next_reg() << 6;
292        } else if (!strcmp(tok, "lshf")) {
293            inst = 0xD000 | next_reg() << 9;
294            inst |= next_reg() << 6;
295            inst |= next_num(4, false);
296        } else if (!strcmp(tok, "rshfl")) {
297            inst = 0xD010 | next_reg() << 9;
298            inst |= next_reg() << 6;
299            inst |= next_num(4, false);
300        } else if (!strcmp(tok, "rshfa")) {
301            inst = 0xD030 | next_reg() << 9;
302            inst |= next_reg() << 6;
303            inst |= next_num(4, false);
304        } else if (!strcmp(tok, "ldb")) {
305            inst = 0x2000 | next_reg() << 9;
306            inst |= next_reg() << 6;
307            inst |= next_num(6, true);
308        } else if (!strcmp(tok, "ldw")) {
309            inst = 0x6000 | next_reg() << 9;
310            inst |= next_reg() << 6;
311            inst |= next_num(6, true);
312        } else if (!strcmp(tok, "stb")) {
313            inst = 0x3000 | next_reg() << 9;
314            inst |= next_reg() << 6;
315            inst |= next_num(6, true);
316        } else if (!strcmp(tok, "stw")) {
317            inst = 0x7000 | next_reg() << 9;
318            inst |= next_reg() << 6;
319            inst |= next_num(6, true);
320        } else if (!strcmp(tok, "lea")) {
321            inst = 0xE000 | next_reg() << 9;
322            inst |= next_label(9, addr);
323        } else if (!strcmp(tok, "jmp")) {
324            inst = 0xC000 | next_reg() << 6;
325        } else if (!strcmp(tok, "ret")) {
326            inst = 0xC1C0;
327        } else if (!strcmp(tok, "rti")) {
328            inst = 0x8000;
329        } else if (!strcmp(tok, "trap")) {
330            // This should only take hex but it accepts decimal
331            inst = 0xF000 | next_num(8, false);
332        } else if (!strcmp(tok, "getc")) {
333            inst = 0xF020;
334        } else if (!strcmp(tok, "out")) {
335            inst = 0xF021;
336        } else if (!strcmp(tok, "puts")) {
337            inst = 0xF022;
338        } else if (!strcmp(tok, "in")) {
339            inst = 0xF023;
340        } else if (!strcmp(tok, "halt")) {
341            inst = 0xF025;
342        } else if (!strcmp(tok, "jsrr")) {
343            inst = 0x4000 | next_reg() << 6;
344        } else if (!strcmp(tok, "jsr")) {
345            inst = 0x4800 | next_label(11, addr);
346        } else if (!strcmp(tok, "nop")) {
347            inst = 0x0000;
348        } else if (!strcmp(tok, ".fill")) {
349            inst = next_num(17, true);
350        } else if (!strcmp(tok, ".blkw")) {
351            // TODO
352        } else {
353            size_t len = strlen(tok);
354            if (len >= 2 && tok[0] == 'b' && tok[1] == 'r') {
355                char* temp = tok + 1;
356                uint8_t nzp = 0;
357                if (len == 2) {
358                    nzp = 7;
359                } else {
360                    while (*++temp) {
361                        switch (*temp) {
362                        case 'n': nzp |= 4; break;
363                        case 'z': nzp |= 2; break;
364                        case 'p': nzp |= 1; break;
365                        }
366                    }
367                }
368                inst = 0x0000 | nzp << 9 | next_label(9, addr);
369            } else {
370                errmsg(2, "Invalid opcode '%s'", tok);
371            }
372        }
373        uint16_t temp = line_num;
374        tok = next_tok();
375        if (temp == line_num) {
376            errmsg(4, "Extra token after instruction: %s", tok);
377        }
378        addr += 2;
379        fprintf(out_file, "0x%.4X\n", inst);
380    }
381}
382
383int main(int argc, char* argv[]) {
384    if (argc != 3) { // TODO: if no output file is provided use input + ext
385        printf("Usage: %s [INFILE] [OUTFILE]\n", argv[0]);
386        exit(4);
387    }
388    if (!(in_file = fopen(argv[1], "r"))) {
389        printf("ERROR: cannot open '%s'", argv[1]);
390        exit(4);
391    }
392    build_table();
393    if (!(out_file = fopen(argv[2], "w"))) {
394        printf("ERROR: cannot open '%s'", argv[2]);
395        exit(4);
396    }
397    // Reset in_file after the first pass
398    rewind(in_file);
399    current = NULL;
400    line_num = 0;
401
402    codegen();
403    fclose(in_file);
404    fclose(out_file);
405}