1 files changed, 168 insertions, 0 deletions
diff --git a/docs/history/10-zc/code/src/rt.zc b/docs/history/10-zc/code/src/rt.zc
new file mode 100644
index 0000000..139924b
--- /dev/null
+++ b/docs/history/10-zc/code/src/rt.zc
@@ -0,0 +1,168 @@
+// ============================================================================
+// rt.zc: the runtime half of the genome. memory map, i/o, arithmetic helpers,
+// the heap (size-class free lists) and the mark-sweep collector.
+// ============================================================================
+
+// ---- memory map (words) ----
+const MW = 0x100000;		// 1m words of memory
+const HEAP_LO = 0x40000;	// heap: 0x40000 .. 0xA0000
+const HEAP_HI = 0xA0000;
+const ZFP = 0xA0000;		// frame pointer word, used by every prologue
+const GORG = 0xC0000;		// the genome (this code) lives here
+const FBOT = 0xE0000;		// frame stack: FBOT .. FTOP, grows down
+const FTOP = 0xF0000;
+const RS0 = 0xF0000;		// return stack grows up from here
+const MARK0 = 0xF8000;		// mark stack for the collector
+const MARKN = 0x4000;
+const DSLO = 0xFC000;		// data stack: DSLO .. MW-16, grows down
+const DSHI = 0xFFFF0;
+const MAGIC = 0x2B7E1516;
+
+// ---- i/o ----
+fn putc(ch) { asm { ch @ . } return 0; }
+fn getc() { return asm { , }; }
+fn eof() { return asm { ? }; }
+fn halt() { asm { q } return 0; }
+fn puts(m s) { var i = 0; while (s[i]) { putc(s[i]); i++; } return 0; }
+fn putn(n)
+{
+	var b[12], i = 0;
+	if (n < 0) { putc('-'); n = 0 - n; }
+	if (n < 0) { puts("2147483648"); return 0; }
+	while (1) { b[i++] = '0' + n % 10; n = n / 10; if (!n) break; }
+	while (i) putc(b[--i]);
+	return 0;
+}
+fn strlen(m s) { var n = 0; while (s[n]) n++; return n; }
+fn streq(m a, m b) { var i = 0; while (a[i] && a[i] == b[i]) i++; return a[i] == b[i]; }
+fn wcopy(m dst, m src, n) { var i = 0; while (i < n) { dst[i] = src[i]; i++; } return 0; }
+fn wfill(m dst, v, n) { var i = 0; while (i < n) { dst[i] = v; i++; } return 0; }
+
+// ---- arithmetic the hardware doesn't have ----
+var pow2[32];
+var zrem;
+fn zudiv(n, d)
+{
+	var q = 0, r = 0, i = 30;
+	if (n < d) { zrem = n; return 0; }
+	while (i >= 0) {
+		r = r + r + ((n >> i) & 1);
+		q = q + q;
+		if (r >= d) { r = r - d; q++; }
+		i--;
+	}
+	zrem = r;
+	return q;
+}
+fn zdiv(a, b)
+{
+	var s = 0, q;
+	if (b == 0) { zrem = a; return 0; }
+	if (a < 0) { a = 0 - a; s = 1; }
+	if (b < 0) { b = 0 - b; s = s ^ 1; }
+	q = zudiv(a, b);
+	if (s) return 0 - q;
+	return q;
+}
+fn zmod(a, b) { var neg = a < 0; zdiv(a, b); if (neg) return 0 - zrem; return zrem; }
+fn zshl(a, b) { return a * pow2[b & 31]; }
+
+// ---- heap ----
+// every block is a power of two words with a 5 word header before the
+// pointer the program sees:
+//   p[-5] block size   p[-4] size class   p[-3] flags (1 live, 2 marked)
+//   p[-2] p ^ MAGIC    p[-1] owner (the container that owns it, or 0)
+// freed blocks keep size and class so the sweep can walk the heap linearly,
+// and go on a free list per class (the link is in p[0]).
+var hbump, freel[32], gc_runs, gc_freed, gc_auto = 1;
+
+fn heap_init()
+{
+	var i = 1;
+	pow2[0] = 1;
+	while (i < 32) { pow2[i] = pow2[i - 1] + pow2[i - 1]; i++; }
+	hbump = HEAP_LO;
+	wfill(freel, 0, 32);
+	return 0;
+}
+fn isobj(m x) { return x >= HEAP_LO + 5 && x < hbump && x[-2] == (x ^ MAGIC) && (x[-3] & 1); }
+
+fn oom() { puts("zc: out of heap memory\n"); halt(); return 0; }
+unchecked fn new(n) -> u
+{
+	var need = n + 5, k = 3, sz = 8, b = 0, p;
+	if (n < 0) need = 5;
+	while (sz < need) { sz = sz + sz; k++; }
+	if (freel[k]) { b = freel[k]; freel[k] = b[5]; }
+	else if (hbump + sz <= HEAP_HI) { b = hbump; hbump = hbump + sz; }
+	else {
+		if (gc_auto) gc();
+		if (freel[k]) { b = freel[k]; freel[k] = b[5]; }
+		else if (hbump + sz <= HEAP_HI) { b = hbump; hbump = hbump + sz; }
+		else oom();
+	}
+	p = b + 5;
+	b[0] = sz; b[1] = k; b[2] = 1; b[3] = p ^ MAGIC; b[4] = 0;
+	wfill(p, 0, sz - 5);
+	return p;
+}
+fn osize(m p) { if (!isobj(p)) return 0; return p[-5] - 5; }
+
+// frees p and, recursively, every object p owns
+fn release(p)
+{
+	var b = p - 5, n = b[0] - 5, i = 0, w;
+	b[2] = 0;
+	while (i < n) { w = p[i]; if (isobj(w) && w[-1] == p) release(w); i++; }
+	b[4] = 0;
+	b[5] = freel[b[1]];
+	freel[b[1]] = b;
+	return 0;
+}
+unchecked fn free(d p) { if (isobj(p)) release(p); return 0; }
+fn own(c, p) { if (isobj(c)) c[-1] = p; return c; }
+
+// ---- mark-sweep ----
+// conservative and non-moving. roots: the program area (globals live
+// between functions), the genome's globals, the compiler's input stack,
+// the live part of the frame stack and the whole data stack region.
+var ms_top, ms_over, gc_lo, gc_hi;
+fn mark(w)
+{
+	if (!isobj(w) || (w[-3] & 2)) return 0;
+	w[-3] = w[-3] | 2;
+	if (ms_top < MARKN) { MARK0[ms_top] = w; ms_top++; } else ms_over = 1;
+	return 0;
+}
+fn markrange(a, b) { while (a < b) { mark(*a); a++; } return 0; }
+fn drain()
+{
+	var p;
+	while (ms_top) { ms_top--; p = MARK0[ms_top]; markrange(p, p + p[-5] - 5); }
+	return 0;
+}
+fn gc_roots();
+unchecked fn gc()
+{
+	var b, sz, n = 0;
+	ms_top = 0; ms_over = 0;
+	gc_roots();
+	drain();
+	while (ms_over) {	// the mark stack overflowed: rescan marked objects
+		ms_over = 0;
+		b = HEAP_LO;
+		while (b < hbump) { if (b[2] == 3) markrange(b + 5, b + b[0]); b = b + b[0]; drain(); }
+	}
+	b = HEAP_LO;
+	while (b < hbump) {
+		sz = b[0];
+		if (b[2] == 1) { b[2] = 0; b[4] = 0; b[5] = freel[b[1]]; freel[b[1]] = b; n++; }
+		else if (b[2] == 3) b[2] = 1;
+		b = b + sz;
+	}
+	gc_runs++;
+	gc_freed = gc_freed + n;
+	return n;
+}
+// number of live objects, for tests
+fn live_objects() { var b = HEAP_LO, n = 0; while (b < hbump) { if (b[2] & 1) n++; b = b + b[0]; } return n; }