9 files changed, 478 insertions, 0 deletions
diff --git a/src/Makefile b/src/Makefile
new file mode 100644
index 0000000..432b331
--- /dev/null
+++ b/src/Makefile
@@ -0,0 +1,61 @@
+ifeq ($(strip $(DEVKITPRO)),)
+$(error "Please set DEVKITPRO in your environment. export DEVKITPRO=<path to>devkitPRO")
+endif
+
+SRCS = $(sort $(wildcard $(srcdir)/*.c))
+OBJS = $(patsubst $(srcdir)/%.c,obj/%.o,$(SRCS))
+DEPS = $(patsubst $(srcdir)/%.c,obj/%.d,$(SRCS))
+
+CFLAGS =
+CPPFLAGS =
+LDFLAGS =
+
+CC = $(DEVKITPRO)/devkitARM/bin/arm-none-eabi-gcc
+
+CFLAGS_AUTO = -D__3DS__ -ffunction-sections -flto -g -march=armv6k -mtune=mpcore -mfloat-abi=hard -mtp=soft -mword-relocations -Og -std=c11 -Wall -Werror=implicit-function-declaration
+LDFLAGS_AUTO = -L$(DEVKITPRO)/libctru/lib -specs=3dsx.specs
+LDLIBS_AUTO = -lctru -lm
+
+CFLAGS_ALL = $(CPPFLAGS) $(CFLAGS_AUTO) $(CFLAGS)
+LDFLAGS_ALL = $(LDFLAGS_AUTO) $(LDFLAGS)
+LDLIBS_ALL = $(LDLIBS_AUTO) $(LDLIBS)
+
+-include config.mak
+
+ifeq ($(CONFIGURED),)
+
+all:
+	@printf >&2 'Please run mk.sh, not make.\n'
+	@exit 1
+
+else
+
+all: imb3.3dsx
+3dslink: imb3.3dsx
+	$(DEVKITPRO)/tools/bin/3dslink $<
+.PHONY: 3dslink
+
+imb3.3dsx: imb3.elf
+	3dsxtool $< $@
+
+imb3.elf: $(OBJS) obj/gc/gc.o
+	$(CC) $(CFLAGS_ALL) $(LDFLAGS_ALL) -o $@ $^ $(LDLIBS_ALL)
+imb3-debug.elf: $(OBJS) obj/gc/gc-debug.o
+	$(CC) $(CFLAGS_ALL) $(LDFLAGS_ALL) -o $@ $^ $(LDLIBS_ALL)
+
+obj/%.o: $(srcdir)/%.c
+	@mkdir -p $(dir $@)
+	$(CC) $(CFLAGS_ALL) -c -o $@ $<
+
+# https://www.gnu.org/software/make/manual/html_node/Automatic-Prerequisites.html
+obj/%.d: $(srcdir)/%.c
+	@mkdir -p obj
+	@set -e; rm -f $@; \
+	 $(CC) -M $(CPPFLAGS) $< > $@.$$$$; \
+	 sed 's,\($*\)\.o[ :]*,obj/\1.o $@ : ,g' < $@.$$$$ > $@; \
+	 rm -f $@.$$$$
+include $(DEPS)
+
+endif
+
+.PHONY: all
diff --git a/src/gc.h b/src/gc.h
new file mode 100644
index 0000000..dff3b79
--- /dev/null
+++ b/src/gc.h
@@ -0,0 +1,18 @@
+#ifndef IMB3_GC_H
+#define IMB3_GC_H
+
+#include "value.h"
+#include <stddef.h>
+
+void gc_init(void);
+void gc_collect(void);
+
+struct object;
+struct value gc_read_value_slot(struct object *, size_t);
+uintptr_t gc_read_untraced_slot(struct object *, size_t);
+uint8_t gc_read_untraced_byte(struct object *, size_t);
+void gc_write_value_slot(struct object *, size_t, struct value);
+void gc_write_untraced_slot(struct object *, size_t, uintptr_t);
+void gc_write_untraced_byte(struct object *, size_t, uint8_t);
+
+#endif // IMB3_GC_H
diff --git a/src/gc/gc-debug.c b/src/gc/gc-debug.c
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/gc/gc-debug.c
diff --git a/src/gc/gc.c b/src/gc/gc.c
new file mode 100644
index 0000000..f53fd79
--- /dev/null
+++ b/src/gc/gc.c
@@ -0,0 +1,213 @@
+#include "../util.h"
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/**
+ * These cache-size details are from
+ * https://www.copetti.org/writings/consoles/nintendo-3ds/. We call the second
+ * level of cache (only available on N3DS) L3, since this GC design only cares
+ * about L1D and L3.
+ */
+static const size_t L1D_SIZE = 16 * 1024, L3_SIZE = 2 * 1024 * 1024;
+
+/**
+ * Constants that should probably be learned.
+ */
+static const size_t NURSERY_L1D_SIZE_FACTOR = 1;
+static const size_t YOUNG_HEAP_L3_SIZE_FACTOR = 2;
+
+/**
+ * Objects each have a header, with a slightly different layout depending on
+ * which heap the object is in. Each header tracks the layout of the object
+ * itself, as well as some other properties, in a uniform way. via the
+ * `enum object_kind` and `struct object_size` types.
+ */
+
+/**
+ * Gives special properties the object might have, as well as the interpretation
+ * of its size.
+ */
+enum object_kind {
+  /**
+   * A normal object. Has up to 2¹⁶ slots for values, and up to 2¹³ slots for
+   * untraced `uintptr_t`s (which may simply be used as bytes).
+   */
+  OBJECT_NORMAL,
+
+  /**
+   * An untraced object. Has up to 2²⁹ slots for untraced `uintptr_t`s (which
+   * may simply be used as bytes).
+   */
+  OBJECT_UNTRACED,
+
+  /**
+   * A hashtable keyed by the addresses. This behaves like a normal object, but
+   * the first untraced slot gets set to the `uintptr_t` 1 whenever a collection
+   * traces the hashtable.
+   *
+   * The hashtable uses this information to rehash after each collection.
+   */
+  OBJECT_EQ_HASHTABLE,
+
+  /**
+   * A wrapper for a pointer to a code address. When this object gets collected,
+   * calls `free_code` on its first untraced slot.
+   */
+  OBJECT_COMPILED_FUNCTION,
+};
+
+/**
+ * A `size_t`-sized encoding of the object size. Also stores an extra bit used
+ * to indicate that the object has been moved in nursery collection, and that
+ * the object has been marked in old-heap collection.
+ */
+struct object_size {
+  enum object_kind kind : 2;
+  bool mark : 1;
+  size_t bits : (8 * sizeof(size_t)) - 3;
+};
+
+/**
+ * Returns the number of slots for values the object has.
+ */
+static size_t object_value_slots(struct object_size size) {
+  switch (size.kind) {
+  case OBJECT_NORMAL:
+  case OBJECT_EQ_HASHTABLE:
+  case OBJECT_COMPILED_FUNCTION:
+    return size.bits >> ((4 * sizeof(size_t)) - 3);
+  case OBJECT_UNTRACED:
+    return 0;
+  }
+}
+
+/**
+ * Returns the number of untraced slots the object has.
+ */
+static size_t object_untraced_slots(struct object_size size) {
+  switch (size.kind) {
+  case OBJECT_NORMAL:
+  case OBJECT_EQ_HASHTABLE:
+  case OBJECT_COMPILED_FUNCTION:
+    return size.bits & ((1 << ((4 * sizeof(size_t)) - 3)) - 1);
+  case OBJECT_UNTRACED:
+    return size.bits;
+  }
+}
+
+/**
+ * This struct is used as an opaque type for the fields of an object.
+ */
+struct object {
+  uintptr_t hd;
+  uintptr_t tl[];
+};
+
+/**
+ * This is the layout of an object in the nursery.
+ */
+struct nursery_object {
+  struct object_size size;
+  uintptr_t slots[];
+};
+
+/**
+ * This is the layout of an object in the young-heap. Because the young-heap is
+ * collected with mark-compact, it needs a dedicated forwarding pointer (or in
+ * our case, a forwarding offset) and can't simply overwrite the object slots
+ * with one.
+ */
+struct young_heap_object {
+  struct object_size size;
+  size_t fwd;
+  uintptr_t slots[];
+};
+
+/**
+ * This is the layout of an object in the old-heap. It matches the nursery
+ * layout at the moment.
+ */
+struct old_heap_object {
+  struct object_size size;
+  uintptr_t slots[];
+};
+
+/**
+ * The nursery and young-heap each have a layout like:
+ *
+ *     ┌──────────────┐ ←── Top
+ *     │remembered set│
+ *     ├──────────────┤ ←── Limit
+ *     │     free     │
+ *     │     space    │
+ *     ├──────────────┤ ←── Next
+ *     │              │
+ *     │              │
+ *     │    objects   │
+ *     │              │
+ *     │              │
+ *     └──────────────┘ ←── Bottom
+ *
+ * The layout of both regions are defined by the four labelled pointers, so we
+ * define them.
+ */
+uintptr_t nursery_bottom, nursery_next, nursery_limit, nursery_top;
+uintptr_t young_heap_bottom, young_heap_next, young_heap_limit, young_heap_top;
+
+/**
+ * The old-heap is composed of blocks, each of which are stored in an
+ * intrusive doubly linked list per size class. Size classes start at 8 bytes
+ * and go up to 64KiB, with a "large object" size class past that. For size
+ * classes up to and including 4KiB, blocks are 64KiB in size. Past that, blocks
+ * are sized to fit one object of the size class.
+ *
+ * Each block has a local free-list of objects of the size class.
+ */
+enum old_heap_size_class {
+  SIZE_8 = 0,
+  SIZE_16,
+  SIZE_32,
+  SIZE_64,
+  SIZE_128,
+  SIZE_256,
+  SIZE_512,
+  SIZE_1024,
+  SIZE_2048,
+  SIZE_4096,
+  SIZE_8192,
+  SIZE_16384,
+  SIZE_32768,
+  SIZE_65536,
+  SIZE_HUGE,
+
+  SIZE_CLASS_COUNT,
+};
+
+struct old_heap_block {
+  struct old_heap_block *prev, *next;
+  struct old_heap_free_object *free_list;
+};
+
+struct old_heap_free_object {
+  struct old_heap_free_object *next;
+};
+
+static struct old_heap_block old_heap_sentinels[SIZE_CLASS_COUNT];
+
+void gc_init(void) {
+  // Allocate the nursery and young-heap.
+  nursery_bottom = nursery_next =
+      (uintptr_t)malloc(L1D_SIZE * NURSERY_L1D_SIZE_FACTOR);
+  assume(nursery_bottom);
+  young_heap_bottom = young_heap_next =
+      (uintptr_t)malloc(L3_SIZE * YOUNG_HEAP_L3_SIZE_FACTOR);
+  assume(young_heap_bottom);
+
+  // Self-link the old-heap.
+  for (size_t i = 0; i < SIZE_CLASS_COUNT; i++) {
+    old_heap_sentinels[i].prev = old_heap_sentinels[i].next =
+        &old_heap_sentinels[i];
+  }
+}
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..c8a1115
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,65 @@
+#include "gc.h"
+#include "util.h"
+#include <3ds.h>
+#include <inttypes.h>
+#include <stdio.h>
+
+int main(int argc, char **argv) {
+  gfxInit(GSP_BGR8_OES, GSP_BGR8_OES, false);
+
+  // Initialize console on top screen. Using NULL as the second argument tells
+  // the console library to use the internal console structure as current one
+  consoleInit(GFX_TOP, NULL);
+
+  // Move the cursor to row 15 and column 19 and then prints "Hello World!"
+  // To move the cursor you have to print "\x1b[r;cH", where r and c are
+  // respectively the row and column where you want your cursor to move The top
+  // screen has 30 rows and 50 columns The bottom screen has 30 rows and 40
+  // columns
+  printf("\x1b[16;20HHello World!");
+
+  printf("\x1b[29;16HPress Start to exit.\n");
+
+  gc_init();
+
+  // Main loop
+  while (aptMainLoop()) {
+    // Scan all the inputs. This should be done once for each frame
+    hidScanInput();
+
+    // hidKeysDown returns information about which buttons have been just
+    // pressed (and they weren't in the previous frame)
+    u32 kDown = hidKeysDown();
+
+    if (kDown & KEY_START)
+      break; // break in order to return to hbmenu
+    if (kDown & KEY_A)
+      todo("GM");
+
+    circlePosition pos;
+    hidCircleRead(&pos);
+    printf("\x1b[0;0H\x1b[K(%" PRId16 ", %" PRId16 ")\n", pos.dx, pos.dy);
+
+    // Get the bottom screen's frame buffer
+    u16 w, h;
+    u8 *fb = gfxGetFramebuffer(GFX_BOTTOM, GFX_LEFT, &w, &h);
+
+    for (u16 j = 0; j < h; j++) {
+      for (u16 i = 0; i < w; i++) {
+        *fb++ = (u8)(((float)i / (float)w) * 255.0);
+        *fb++ = (u8)(((float)j / (float)h) * 255.0);
+        *fb++ = 0x00;
+      }
+    }
+
+    // Flush and swap framebuffers
+    gfxFlushBuffers();
+    gfxSwapBuffers();
+
+    // Wait for VBlank
+    gspWaitForVBlank();
+  }
+
+  gfxExit();
+  return 0;
+}
diff --git a/src/util.c b/src/util.c
new file mode 100644
index 0000000..c219831
--- /dev/null
+++ b/src/util.c
@@ -0,0 +1,51 @@
+#include "util.h"
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#ifdef __3DS__
+
+#include <3ds.h>
+
+static void panic_begin(void) { consoleInit(GFX_TOP, NULL); }
+
+static noreturn void panic(void) {
+  printf("\nPress Start to exit.\n");
+
+  while (aptMainLoop()) {
+    hidScanInput();
+    u32 keys = hidKeysDown();
+    if (keys & KEY_START)
+      break;
+    gfxFlushBuffers();
+    gfxSwapBuffers();
+    gspWaitForVBlank();
+  }
+
+  gfxExit();
+  exit(1);
+}
+
+#else
+
+static void panic_begin(void) {}
+
+static noreturn void panic(void) { abort(); }
+
+#endif
+
+noreturn void assume__failed(const char *file, int line, const char *expr) {
+  panic_begin();
+  fprintf(stderr, "%s:%d: assertion failed: %s\n", file, line, expr);
+  panic();
+}
+
+noreturn void todo__impl(const char *file, int line, const char *fmt, ...) {
+  panic_begin();
+  printf("%s:%d: TODO: ", file, line);
+  va_list ap;
+  va_start(ap, fmt);
+  vprintf(fmt, ap);
+  va_end(ap);
+  panic();
+}
diff --git a/src/util.h b/src/util.h
new file mode 100644
index 0000000..569054b
--- /dev/null
+++ b/src/util.h
@@ -0,0 +1,31 @@
+#ifndef IMB3_UTIL_H
+#define IMB3_UTIL_H
+
+#include <stdbool.h>
+#include <stdnoreturn.h>
+
+static inline bool likely(bool cond) { return __builtin_expect(cond, true); }
+static inline bool unlikely(bool cond) { return __builtin_expect(cond, false); }
+
+#ifndef NDEBUG
+noreturn void assume__failed(const char *file, int line, const char *expr);
+#endif // NDEBUG
+
+static inline void assume__impl(bool cond, const char *file, int line,
+                                const char *expr) {
+#ifndef NDEBUG
+  if (unlikely(!cond))
+    assume__failed(file, line, expr);
+#endif // NDEBUG
+  if (unlikely(!cond))
+    __builtin_unreachable();
+}
+
+#define assume(COND) assume__impl(COND, __FILE__, __LINE__, #COND)
+
+__attribute__((format(printf, 3, 4))) noreturn void
+todo__impl(const char *file, int line, const char *fmt, ...);
+
+#define todo(...) todo__impl(__FILE__, __LINE__, __VA_ARGS__)
+
+#endif // IMB3_UTIL_H
diff --git a/src/value.c b/src/value.c
new file mode 100644
index 0000000..66d388c
--- /dev/null
+++ b/src/value.c
@@ -0,0 +1 @@
+#include "value.h"
diff --git a/src/value.h b/src/value.h
new file mode 100644
index 0000000..a932514
--- /dev/null
+++ b/src/value.h
@@ -0,0 +1,38 @@
+#ifndef IMB3_VALUE_H
+#define IMB3_VALUE_H
+
+#include <stdint.h>
+
+struct value {
+  uintptr_t bits;
+};
+
+enum value_tag {
+  /**
+   * A big integer or the nil constant.
+   */
+  TAG_BIGINT_OR_NIL = 0b000,
+
+  /**
+   * Fixnums, i.e. integers that are stored directly in the value rather than
+   * being pointed to. This is a two-bit tag rather than a three-bit tag...
+   */
+  VALUE_FIXNUM = 0b01,
+
+  /**
+   * A builtin-object.
+   */
+  TAG_BUILTIN_OBJECT = 0b010,
+
+  /**
+   * A simple-array, i.e. an array of values without a fill-pointer.
+   */
+  TAG_SIMPLE_ARRAY = 0b100,
+
+  /**
+   * A standard-object, effectively a pair of a class and a slot array.
+   */
+  TAG_STANDARD_OBJECT = 0b110,
+};
+
+#endif // IMB3_VALUE_H