Work on jump instructions.

3 files changed, 200 insertions, 59 deletions

diff --git a/asmparser.peg b/asmparser.peg
index 77f90e5..26cc318 100644
--- a/asmparser.peg
+++ b/asmparser.peg
@@ -2,10 +2,18 @@
 
 %value "Parsev"
 
-program <- line* !.
-line <- s:stmt eol { srcpos = $0s; onstmt(s); }
+line <- s:stmt eol { $$ = s; }
+      / eol { $$.kind = ASM_BLANK; }
+      / . { $$.kind = ASM_SYNTAX_ERROR; }
+      
 stmt <- i:instr { $$ = i; }
-instr <- "nop" { $$.instr = (Instr){.kind = ASM_NOP}; }
-       / "ret" { $$.instr = (Instr){.kind = ASM_RET}; }
-ws <- [ \t]*
-eol <- ws ("\n" / ! .)
+      / l:label {  $$ = l; } 
+label <- i:ident ':' { $$.label = (Label){.kind = ASM_LABEL, .value = i.ident}; }
+instr <- "nop" { $$.instr = (Instr){.kind = ASM_NOP }; }
+       / "ret" { $$.instr = (Instr){.kind = ASM_RET }; }
+       / "jmp" ws i:ident
+           { $$.instr = (Instr){.kind = ASM_JMP, .jmp.target = i.ident}; }
+ident <- <[_a-zA-Z][_a-zA-Z0-9]*> { $$.ident = xstrdup($1); } 
+
+ws <- [ \t]+
+eol <- ws? ("\n" / (! .))
diff --git a/dumbas.h b/dumbas.h
index 00f4fad..1850623 100644
--- a/dumbas.h
+++ b/dumbas.h
@@ -1,8 +1,13 @@
+#include <assert.h>
 #include <elf.h>
+#include <errno.h>
+#include <stdarg.h>
+#include <stdbool.h>
 #include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <stdio.h>
 #include <unistd.h>
 
 typedef struct {
@@ -12,43 +17,62 @@ typedef struct {
 } Section;
 
 enum AsmKind {
+  ASM_SYNTAX_ERROR,
+  ASM_BLANK,
+  ASM_LABEL,
   ASM_NOP,
-  ASM_RET
+  ASM_RET,
+  ASM_JMP
 };
 
 typedef struct {
   enum AsmKind kind;
+  union {
+    struct {
+      const char *target;
+    } jmp;
+  };
 } Instr;
 
+typedef struct {
+  enum AsmKind kind;
+  const char *value;
+} Label;
+
 typedef union {
   enum AsmKind kind;
   Instr instr;
+  Label label;
+  const char *ident;
 } Parsev;
 
-static void die(char *s) {
-  write(STDERR_FILENO, s, strlen(s));
-  exit(1);
-}
-
-static void *xcalloc(size_t nmemb, size_t n) {
-  void *p;
-  p = calloc(nmemb, n);
-  if (!p)
-    die("out of memory");
-  return p;
-}
-
-static void *xmalloc(size_t n) {
-  void *p;
-  p = malloc(n);
-  if (!p)
-    die("out of memory");
-  return p;
-}
-
-static void *xrealloc(void *p, size_t n) {
-  p = realloc(p, n);
-  if (!p)
-    die("out of memory");
-  return p;
-}
\ No newline at end of file
+typedef struct AsmLine AsmLine;
+struct AsmLine {
+  int64_t lineno;
+  int64_t wco; // Worst case offset
+  Parsev v;
+  AsmLine *next;
+};
+
+/* util.c */
+
+void fatal(const char *fmt, ...);
+
+void *xmalloc(size_t);
+void *xrealloc(void *, size_t);
+void *xreallocarray(void *, size_t, size_t);
+char *xmemdup(const char *, size_t);
+char *xstrdup(const char *s);
+
+struct hashtablekey {
+  uint64_t hash;
+  const char *str;
+  size_t len;
+};
+
+void htabkey(struct hashtablekey *, const char *, size_t);
+struct hashtable *mkhtab(size_t);
+void delhtab(struct hashtable *, void(void *));
+void **htabput(struct hashtable *, struct hashtablekey *);
+void *htabget(struct hashtable *, struct hashtablekey *);
+uint64_t murmurhash64a(const void *, size_t);
\ No newline at end of file
diff --git a/main.c b/main.c
index 0877d4a..f58200d 100644
--- a/main.c
+++ b/main.c
@@ -1,6 +1,9 @@
 #include "dumbas.h"
 
-int srcpos = 0;
+AsmLine *allasm = NULL;
+
+// Label worst case offsets
+struct hashtable *labelwco = NULL;
 
 #define MAXSECTIONS 32
 static Section sections[MAXSECTIONS];
@@ -13,7 +16,7 @@ static Section *symtab = NULL;
 static Section *bss = NULL;
 static Section *text = NULL;
 
-static void secappend(Section *s, uint8_t *bytes, size_t n) {
+static void secbytes(Section *s, uint8_t *bytes, size_t n) {
   while (s->capacity < s->hdr.sh_size + n) {
     s->capacity = s->capacity ? (s->capacity * 2) : 64;
     s->data = xrealloc(s->data, s->capacity);
@@ -22,9 +25,7 @@ static void secappend(Section *s, uint8_t *bytes, size_t n) {
   s->hdr.sh_size += n;
 }
 
-static void secbyte(Section *s, uint8_t b) {
-  secappend(s, &b, 1);
-}
+static void secbyte(Section *s, uint8_t b) { secbytes(s, &b, 1); }
 
 static Elf64_Word elfstr(Section *sec, const char *s) {
   Elf64_Word i;
@@ -33,15 +34,33 @@ static Elf64_Word elfstr(Section *sec, const char *s) {
       if (strcmp(s, (char *)&sec->data[i]) == 0)
         return i;
   }
-  secappend(sec, (uint8_t *)s, strlen(s) + 1);
+  secbytes(sec, (uint8_t *)s, strlen(s) + 1);
   return i;
 }
 
+/*
+static Elf64_sym *getsym(const char *name) {
+  const char *symname;
+  Elf64_sym newsym, *sym;
+  Elf64_Word i, nsyms;
+
+  nsyms = symtab->hdr.sh_size / sizeof(Elf64_sym);
+  for (i = 0; i < nsyms; i++) {
+    sym = (Elf64_sym*)symtab->data + i;
+    symname = (char*)strtab->data + sym->name;
+    if (strcmp(symname, name) == 0)
+      return sym;
+  }
+
+  return NULL;
+}
+*/
+
 static Section *newsection() {
   Section *s;
   s = &sections[nsections++];
   if (nsections > MAXSECTIONS)
-    die("too many sections");
+    fatal("too many sections");
   return s;
 }
 
@@ -77,11 +96,13 @@ static void initsections(void) {
   text->hdr.sh_flags = SHF_EXECINSTR | SHF_ALLOC;
   text->hdr.sh_entsize = 1;
   text->hdr.sh_addralign = 4;
+
+  cursection = text;
 }
 
 static void out(uint8_t *buf, size_t n) {
   if (write(STDOUT_FILENO, buf, n) != n)
-    die("io error");
+    fatal("io error");
 }
 
 static void outelf(void) {
@@ -121,31 +142,119 @@ static void outelf(void) {
   }
 }
 
-void onstmt(Parsev p) {
-  switch (p.kind) {
-  case ASM_NOP:
-    secbyte(cursection, 0x90);
-    break;
-  case ASM_RET:
-    secbyte(cursection, 0xc3);
-    break;
-  default:
-    die("unexpected kind");
-  }
-}
-
 #include "asmparser.c" // XXX resolve dependency cycle.
 
 void parse(void) {
-  asmparser_context_t *ctx = asmparser_create(NULL);
-  while (asmparser_parse(ctx, NULL));
+  int more;
+  uint64_t lineno;
+  Parsev v;
+  AsmLine *l, *prevl;
+  asmparser_context_t *ctx;
+
+  ctx = asmparser_create(NULL);
+  prevl = NULL;
+  lineno = 0;
+
+  do {
+    more = asmparser_parse(ctx, &v);
+    if (v.kind == ASM_SYNTAX_ERROR) {
+      fprintf(stderr, "<stdin>:%lu: syntax error\n", lineno);
+      exit(1);
+    }
+    if (v.kind == ASM_BLANK)
+      continue;
+    l = xmalloc(sizeof(AsmLine));
+    l->v = v;
+    l->lineno = lineno;
+    l->next = NULL;
+    if (prevl)
+      prevl->next = l;
+    else
+      allasm = l;
+    prevl = l;
+    lineno += 1;
+  } while (more);
+
   asmparser_destroy(ctx);
 }
 
+/* Compute worst case offsets in the text section
+   once we have worst case offsets we can compute
+   worst case jump distances. */
+static void computewco() {
+  Parsev *v;
+  AsmLine *l;
+  const char *label;
+  struct hashtablekey htk;
+  int64_t offset = 0;
+
+  for (l = allasm; l; l = l->next) {
+    l->wco = offset;
+    v = &l->v;
+    switch (v->kind) {
+    case ASM_LABEL:
+      label = v->label.value;
+      htabkey(&htk, label, strlen(label));
+      *((int64_t *)htabput(labelwco, &htk)) = offset;
+      break;
+    case ASM_NOP:
+    case ASM_RET:
+      offset += 1;
+      break;
+    case ASM_JMP:
+      offset += 5;
+      break;
+    default:
+      fatal("unexpected kind: %d", v->kind);
+    }
+  }
+}
+
+static int64_t pessimisticdistance(AsmLine *line, const char *label) {
+  struct hashtablekey htk;
+  htabkey(&htk, label, strlen(label));
+  return (int64_t)htabget(labelwco, &htk) - line->wco;
+}
+
+static void assemble() {
+  Parsev *v;
+  AsmLine *l;
+
+  for (l = allasm; l; l = l->next) {
+    v = &l->v;
+    switch (l->v.kind) {
+    case ASM_LABEL:
+      break;
+    case ASM_NOP:
+      secbyte(cursection, 0x90);
+      break;
+    case ASM_RET:
+      secbyte(cursection, 0xc3);
+      break;
+    case ASM_JMP: {
+      int64_t distance;
+      distance = pessimisticdistance(l, v->instr.jmp.target);
+      if (distance <= 128 && distance >= -127) {
+        uint8_t jbuf[2] = {0xeb, 0x00};
+        secbytes(cursection, jbuf, sizeof(jbuf));
+      } else {
+        uint8_t jbuf[5] = {0xe9, 0x00, 0x00, 0x00, 0x00};
+        secbytes(cursection, jbuf, sizeof(jbuf));
+      }
+      break;
+    }
+    default:
+      fatal("unexpected kind: %d", l->v.kind);
+    }
+  }
+}
+
 int main(void) {
+  labelwco = mkhtab(256);
   initsections();
-  cursection = text;
   parse();
+  computewco();
+  assemble();
   outelf();
   return 0;
 }
\ No newline at end of file