asm.c

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <math.h>
#include "vector.h"

typedef struct Token {
    enum {
        TOK_RIGHT,
        TOK_LEFT,
        TOK_ADD,
        TOK_SUB,
        TOK_BNZ,
        TOK_INTEGER,
        TOK_PROGRAM_SIZE,
        TOK_LABEL_REF,
        TOK_EOF,
    } type;

    char *string;
} Token;

typedef struct Label {
    int location;
    char *name;
} Label;

struct {
    Vector *tokens;
    Vector *labels; // Symbol table
    int program_size;
} lexer_ctx;

struct {
    int nxt_tok_index;
    Token *curtok;
    Token *lasttok;
} parser_ctx;

// Code gen

// Instruction opcodes
enum {
    INSTR_RIGHT = 0x0,
    INSTR_ADD   = 0x1,
    INSTR_BNZ   = 0x2,
    INSTR_NOP   = 0x3
};

void gen_instr(FILE *outfile, char opcode, uint32_t imm)
{
    uint32_t instr = (opcode << 30) | (imm & 0x3FFFFFFF);
    instr = __bswap_constant_32(instr); // Little-endian to big-endian
    fwrite(&instr, 4, 1, outfile);
}

// Parser

void next_tok()
{
    parser_ctx.lasttok = parser_ctx.curtok;
    parser_ctx.curtok = lexer_ctx.tokens->items[parser_ctx.nxt_tok_index];
    parser_ctx.nxt_tok_index++;
}

int accept_tok(int tok_type)
{
    if (parser_ctx.curtok->type == tok_type) {
        next_tok();
        return 1;
    }
    return 0;
}

void expect_tok(int tok_type)
{
    if (!accept_tok(tok_type)) {
        printf("error: unexpected token \"%s\".\n", parser_ctx.curtok->string);
        exit(1);
    }
}

int parse_integer_value()
{
    // Normal integer
    if (accept_tok(TOK_INTEGER)) {
        return strtol(parser_ctx.lasttok->string, NULL, 10);
    // Program size constant
    } else if (accept_tok(TOK_PROGRAM_SIZE)) {
        return lexer_ctx.program_size;
    } else {
        printf("error: expected an integer value instead got \"%s\".\n",
               parser_ctx.curtok->string);
        exit(1);
    }
}

void parse(FILE *outfile)
{
    int instr_addr = 0;
    parser_ctx.nxt_tok_index = 0;
    next_tok();

    while (parser_ctx.curtok->type != TOK_EOF) {
        // Right instruction
        if (accept_tok(TOK_RIGHT)) {
            gen_instr(outfile, INSTR_RIGHT, parse_integer_value());
            instr_addr += 4;
        // Left instruction
        } else if (accept_tok(TOK_LEFT)) {
            gen_instr(outfile, INSTR_RIGHT, -parse_integer_value());
            instr_addr += 4;
        // Add instruction
        } else if (accept_tok(TOK_ADD)) {
            gen_instr(outfile, INSTR_ADD, parse_integer_value());
            instr_addr += 4;
        // Subtract instruction
        } else if (accept_tok(TOK_SUB)) {
            gen_instr(outfile, INSTR_ADD, -parse_integer_value());
            instr_addr += 4;
        // Branch if not zero instruction
        } else if (accept_tok(TOK_BNZ)) {
            expect_tok(TOK_LABEL_REF);

            char *label_name = parser_ctx.lasttok->string;
            Label *label = NULL;

            // Search the label symbol table
            for (int i = 0; i < lexer_ctx.labels->length; i++) {
                Label *curlabel = lexer_ctx.labels->items[i];

                if (strcmp(curlabel->name, label_name) == 0)
                    label = curlabel;
            }

            if (label == NULL) {
                printf("error: undefined label \"%s\".\n", label_name);
                exit(1);
            }

            // Generate the instruction
            instr_addr += 4;
            gen_instr(outfile, INSTR_BNZ,
                      instr_addr < label->location ?
                          label->location - instr_addr :       // Bnz positive
                          (label->location - instr_addr)); // Bnz negative
        } else {
            printf("error: unexpected token \"%s\".\n",
                   parser_ctx.curtok->string);
            exit(1);
        }
    }
}

// Lexer

int fpeek(FILE *fp)
{
    int c = fgetc(fp);
    ungetc(c, fp);
    return c;
}

// This function may cause performance issues
char *append_char(char *str, char c)
{
    int len = strlen(str);
    str = realloc(str, sizeof(char) * (len + 2));
    str[len] = c;
    str[len + 1] = '\0';
    return str;
}

char *scan_while(FILE *fp, int (*condition)(char c))
{
    char c;
    char *token = malloc(sizeof(char));
    token[0] = '\0';

    while ((c = fgetc(fp)) != EOF && condition(c))
        token = append_char(token, c);
    ungetc(c, fp);

    return token;
}

int is_not_newline(char c)      { return c != '\n'; } // Used for comments
int is_valid_ident_char(char c) { return isalnum(c) || c == '_'; } // Identifier

// Basic lexer function
void lex(FILE *src)
{
    lexer_ctx.tokens = new_vector();
    lexer_ctx.labels = new_vector();

    int instr_addr = 0;

    while (1) {
        Token *tok = malloc(sizeof(Token));
        tok->string = NULL;

        {   // Ignore whitespace
            char c;
            while ((c = fgetc(src)) != EOF && isspace(c));
            ungetc(c, src);
        }


        if (fpeek(src) == EOF) {
            tok->type = TOK_EOF;
            vector_append(lexer_ctx.tokens, tok);
            break;
        }

        // Instruction or label
        if (isalpha(fpeek(src))) {
            tok->string = scan_while(src, (int (*)(char))&is_valid_ident_char);

            // Label definition
            // Note: label definitions are not appended to lexer_ctx.tokens,
            //       instead they are appended to lexer_ctx.labels.
            if (fpeek(src) == ':') {
                fgetc(src); // Advance the file stream

                // Create label
                Label *l = malloc(sizeof(Label));
                l->name = tok->string;
                l->location = instr_addr;

                vector_append(lexer_ctx.labels, l);

                // Delete the token as it is not needed
                free(tok);
                continue;
            } else {
                // Keywords
                if (strcmp(tok->string, "right") == 0) {
                    instr_addr += 4;
                    tok->type = TOK_RIGHT;
                } else if (strcmp(tok->string, "left") == 0) {
                    instr_addr += 4;
                    tok->type = TOK_LEFT;
                } else if (strcmp(tok->string, "add") == 0) {
                    instr_addr += 4;
                    tok->type = TOK_ADD;
                } else if (strcmp(tok->string, "sub") == 0) {
                    instr_addr += 4;
                    tok->type = TOK_SUB;
                } else if (strcmp(tok->string, "bnz") == 0) {
                    instr_addr += 4;
                    tok->type = TOK_BNZ;
                // Program size constant
                } else if (strcmp(tok->string, "PROGRAM_SIZE") == 0) {
                    tok->type = TOK_PROGRAM_SIZE;
                // Label reference
                } else {
                    tok->type = TOK_LABEL_REF;
                }
            }
        // Integers
        } else if (isdigit(fpeek(src))) {
            tok->string = scan_while(src, (int (*)(char))&isdigit);
            tok->type = TOK_INTEGER;
        // Comments
        } else if (fpeek(src) == ';') {
            tok->string = scan_while(src, (int (*)(char))&is_not_newline);

            // Delete the token as it is not needed
            free(tok->string);
            free(tok);
            continue;
        // Error
        } else {
            printf("error: unexpected character \"%c\".\n", fpeek(src));
            exit(1);
        }

        vector_append(lexer_ctx.tokens, tok);
    }

    lexer_ctx.program_size = instr_addr;
}

// Main

void print_help()
{
    printf("Usage: nqoisc-asm [Options...]\n"
           "Options:\n"
           "    -h        Print this help menu and exit.\n"
           "    -i        Specify an input file.\n"
           "    -o <file> Specify an output file the default is \"a.bin\".\n");
}

int main(int argc, char *argv[])
{
    char *source_filename = NULL;
    char *out_filename = NULL;

    for (int option; (option = getopt(argc, argv, "hi:o:")) != -1;) {
        switch (option) {
        // Output file
        case 'o':
            out_filename = strdup(optarg);
            break;
        // Help menu
        case 'h':
            print_help();
            return 0;
        // Input file
        case 'i':
            source_filename = strdup(optarg);
            break;
        case '?':
            printf("Unkown option: %c\n", optopt);
            print_help();
            return 1;
            break;
        }
    }

    if (source_filename == NULL) {
        printf("error: no input source file specified.\n");
        print_help();
        return 1;
    }

    if (out_filename == NULL) {
        out_filename = malloc(sizeof("a.bin"));
        strcpy(out_filename, "a.bin");
    }

    // Lex

    FILE *source_fp = fopen(source_filename, "r");
    if (source_fp == NULL) {
        printf("error: failed to open \"%s\" for reading.\n", source_filename);
        return 1;
    }

    lex(source_fp);

    fclose(source_fp);

    // Parse

    FILE *out_fp = fopen(out_filename, "wb");
    if (out_fp == NULL) {
        printf("error: failed to open \"%s\" for writing.\n", out_filename);
        return 1;
    }

    parse(out_fp);

    fclose(out_fp);

    // Free memory

    free(source_filename);
    free(out_filename);

    // Free tokens
    for (int i = 0; i < lexer_ctx.tokens->length; i++) {
        free(((Token *)lexer_ctx.tokens->items[i])->string);
        free(lexer_ctx.tokens->items[i]);
    }
    vector_free(lexer_ctx.tokens);

    // Free labels
    for (int i = 0; i < lexer_ctx.labels->length; i++) {
        free(((Label *)lexer_ctx.labels->items[i])->name);
        free(lexer_ctx.labels->items[i]);
    }
    vector_free(lexer_ctx.labels);
}