add random non-overlapping ranges in core

3 files changed, 144 insertions, 6 deletions

diff --git a/src/vm/core.js b/src/vm/core.js
index 4fdd0a0..184be00 100644
--- a/src/vm/core.js
+++ b/src/vm/core.js
@@ -3,6 +3,46 @@
 const { Op, AddrMode} = require('./enum.js');
 
 
+function mod(a, N) {
+	const A = a % N;
+	if (A < 0) {
+		return A + N;
+	} else {
+		return A;
+	}
+}
+
+
+class Range {
+	constructor(start, end, coresize) {
+		this.start = start;
+		this.end = end;
+		this.coresize = coresize;
+	}
+
+	
+	// thanks to https://fgiesen.wordpress.com/2015/09/24/intervals-in-modular-arithmetic/
+	// c:
+	contains(n) {
+		return mod(n - this.start, this.coresize) <= mod(this.end - this.start, this.coresize);
+	}
+
+	overlaps(other) {
+		return (
+			this.contains(other.start) ||
+			other.contains(this.start)
+		);
+	}
+}
+
+
+function randomRange(coresize, length) {
+	const start = Math.floor(Math.random() * coresize);
+	const end = mod(start + length - 1, coresize);
+	return new Range(start, end, coresize);
+}
+
+
 class Core {
 	constructor(size) {
 		this.data = new Array(size);
@@ -18,13 +58,31 @@ class Core {
 	}
 
 
-	normalize(pc, value) {
-		const v = (pc + value) % this.data.length;
-		if (v < 0) {
-			return v + this.data.length;
-		} else {
-			return v;
+	getRanges(lengths, ranges) {
+		if (ranges === undefined) {
+			ranges = [];
+		}
+
+		if (lengths.length === 0) {
+			return ranges;
 		}
+
+		const length = lengths[0];
+		let range;
+		do {
+			range = randomRange(this.data.length, length);
+		} while (
+			ranges
+				.map(r => r.overlaps(range))
+				.reduce((acc, overlap) => acc || overlap, false)
+		);
+
+		return this.getRanges(lengths.slice(1), [...ranges, range]);
+	}
+
+
+	normalize(pc, value) {
+		return mod((pc + value), this.data.length);
 	}
 
 
@@ -57,4 +115,6 @@ class Core {
 }
 
 
+exports.mod = mod;
+exports.Range = Range;
 exports.Core = Core;
diff --git a/src/vm/core.test.js b/src/vm/core.test.js
new file mode 100644
index 0000000..84aab6f
--- /dev/null
+++ b/src/vm/core.test.js
@@ -0,0 +1,42 @@
+'use strict';
+
+const { mod, Range, Core } = require('./core.js');
+
+test('ranges overlap correctly', () => {
+	const a = new Range(7, 1, 8);
+	const b = new Range(0, 2, 8);
+	const c = new Range(3, 5, 8);
+
+	expect(a.overlaps(a)).toBe(true);
+	expect(b.overlaps(b)).toBe(true);
+	expect(c.overlaps(c)).toBe(true);
+
+	expect(a.overlaps(b)).toBe(true);
+	expect(b.overlaps(a)).toBe(true);
+	expect(a.overlaps(c)).toBe(false);
+	expect(b.overlaps(c)).toBe(false);
+	expect(c.overlaps(a)).toBe(false);
+	expect(c.overlaps(b)).toBe(false);
+});
+
+test('get non-overlapping ranges in a core', () => {
+	const CORESIZE = 8000;
+	const core = new Core(CORESIZE);
+
+	for (let loop=0; loop<500; loop++) {
+		const ranges = core.getRanges([20, 10, 5, 5]);
+	
+		expect(ranges.length).toBe(4);
+		expect(mod(ranges[0].end - ranges[0].start + 1, CORESIZE)).toBe(20);
+		expect(mod(ranges[1].end - ranges[1].start + 1, CORESIZE)).toBe(10);
+		expect(mod(ranges[2].end - ranges[2].start + 1, CORESIZE)).toBe(5);
+		expect(mod(ranges[3].end - ranges[3].start + 1, CORESIZE)).toBe(5);
+	
+		for (let i=0; i<ranges.length; i++) {
+			for (let j=0; j<ranges.length; j++) {
+				if (i === j) continue;
+				expect(ranges[i].overlaps(ranges[j])).toBe(false);
+			}
+		}
+	}
+});
diff --git a/src/vm/vm.js b/src/vm/vm.js
new file mode 100644
index 0000000..1ec890b
--- /dev/null
+++ b/src/vm/vm.js
@@ -0,0 +1,36 @@
+'use strict';
+
+
+const { Core } = require('./core.js');
+const {
+	DAT,
+	MOV, ADD, SUB, CMP, SLT,
+	JMP, JMZ, JMN, DJN, SPL,
+} = require('./instruction.js');
+
+
+class Warrior {
+	constructor(start) {
+		this.queue = [start];
+	}
+
+	isDead() { return (this.queue.length === 0); }
+
+	append(heads) {
+		this.queue.push(...heads);
+	}
+
+	next() {
+		const pc = this.queue[0];
+		this.queue = this.queue.slice(1);
+		return next;
+	}
+};
+
+
+class RedcodeVm {
+	constructor(coresize, warriors) {
+		this.core = new Core(coresize);
+		
+	}
+};