Tape layout
===========

Imarker: [ 1 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 ]

Rules
- Each rule: [ 0 | tr1 | tr2 | tr3 | tr4 | qfrom | sread | qto | swrite | dir ]

Mmarker: [ 1 | qcurrent | t1 | t2 | t3 ]

Tape
- Each cell: [ 0 | head | tt1 | tt2 | sym ]

EXPLICITLY USED: sizeof(rule) == 2 * sizeof(cell)


Read input
==========

Write 1, move right a rule width
Go to tr1
Write 1
While nonzero:
	Subtract 1 from tr1
	Read into qfrom
	Copy to tr4 (using tr3 as scratch)
	Write 1 to tr3  ("should zero qfrom")
	Go to tr4 and add 1
	While nonzero:
		Zero tr4
		Subtract 1 from tr3
		Write 1 to rightrule.tr1

		Read into sread
		Copy to sread+1 (scratch sread+2)
		Write 1 to sread+2
		Subtract 32 from sread+1 and go to sread+1
		While nonzero:
			Subtract 1 from sread+2
			Zero sread+1 and go to sread+1
		Go to sread+2
		While nonzero:
			Zero sread
			Zero sread+2 and go to sread+2

		Read into qto

		Read into swrite
		Copy to swrite+1 (scratch swrite+2)
		Write 1 to swrite+2
		Subtract 32 from swrite+1 and go to swrite+1
		While nonzero:
			Subtract 1 from swrite+2
			Zero swrite+1 and go to swrite+1
		Go to swrite+2
		While nonzero:
			Zero swrite
			Zero swrite+2 and go to swrite+2

		Read into dir
		Subtract '=' (61) from dir

		Go to tr4

	Go to tr3
	While nonzero:
		Zero qfrom
		Zero tr3 and go to tr3

	Go to rightrule.tr1, which is 1 precisely if we didn't have EOF

Now at a zero tr1 that is one rule width too far.
So go one rule width left, at which point we are on the qcurrent of Mmarker.
Write 'S' (83), and go to Mmarker.0
Write 1
Set rightcell.head to 1
Go back to Mmarker.0


Main loop
=========

Precondition: cursor at Mmarker.0 and all temporaries are 0

Subtract 'H' from qcurrent (using t1 as scratch)
While qcurrent is nonzero:
	Add 'H' to qcurrent
	Go to Mmarker.0

	Perform execution step

	Subtract 'H' from qcurrent


Execution step
==============

Precondition: cursor at Mmarker.0 and all temporaries are 0

Find cell with head=1:
	Set t1 to 1
	While nonzero:
		Zero current cell (leftrule.tt1), then move right a cell width; now at tt1
		Set tt1 to 1
		Move head to tt1 (multiplier -1) and tt2, move tt2 back to head
		Now tt1 is not(head).
		Go to tt1
	Now at zero tt1, which means that head = 1; go to rule.0 for good measure.

Copy sym to tt1 (using tt2 as scratch)
Move tt1 over tt1's back to t1:
	Go to tt2, set to 1
	While nonzero:
		Zero current cell (tt2)
		Set leftcell.tt2 to 1
		Move leftcell.0 to leftcell.tt2 (multiplier -1) and leftcell.tt1
		Move leftcell.tt1 back to leftcell.0
		Move tt1 to leftcell.tt1
		Go to leftcell.tt2
	Now at zero t2, and t1 is sym.
[t1 = sym; tt1 = tt2 = 0 for all cells]

Copy qcurrent to tr1 of last rule (using t2 as scratch)
Move t1 (=sym) to tr2 of last rule
Go to t2 (same offset as tr3), set to 1
While nonzero:
	Zero current cell (rightrule.tr3), then move left a rule width; now at tr3
	Zero tr3
	[tr1 = qcurrent, tr2 = sym]
	Copy qfrom to tr4 (using tr3 as scratch)
	Copy tr1 to tr3 (using rule.0 as scratch)
	[tr1 = qcurrent, tr2 = sym, tr3 = qcurrent, tr4 = qfrom]
	Set tr3 to (qcurrent != qfrom): to(tr3) [- to(tr4) - to(tr3)] to(tr4) [to(tr3) + to(tr4) [-]]
	Move tr3 to left-rule.tr3 (or T3 if leftmost rule)

	[tr1 = qcurrent, tr2 = sym]
	Copy sread to tr4 (using tr3 as scratch)
	Copy tr2 to tr3 (using rule.0 as scratch)
	[tr1 = qcurrent, tr2 = sym, tr3 = sym, tr4 = sread]
	Set tr3 to (sym != sread): to(tr3) [- to(tr4) - to(tr3)] to(tr4) [to(tr3) + to(tr4) [-]]
	Move tr3 to left-rule.tr4 (or T4 if leftmost rule)

	[tr1 = qcurrent, tr2 = sym, prev.tr3 = q!=q, prev.tr4 = s!=s]
	Move leftrule.tr3 to tr4 and leftrule.tr4 also to tr4
	If tr4 is nonzero: zero tr4 and set tr3 to 1

	[tr1 = qcurrent, tr2 = sym, tr3 = q!=q || s!=s]
	Copy tr3 to leftrule.tr3 (using rule.0 as scratch)

	[tr1 = qcurrent, tr2 = sym, tr3 = q!=q || s!=s, leftrule.tr3 = q!=q || s!=s]
	While leftrule.0 is nonzero:
		Zero tr3 and set tr4 to 1
		Zero leftrule.0
	Move tr4 to leftrule.0

	[tr1 = qcurrent, tr2 = sym, tr3 = (q!=q || s!=s) && not_leftmost_rule, leftrule.tr3 = q!=q || s!=s]

	Move tr1 to leftrule.tr1 and tr2 to leftrule.tr2 (or T1 and T2 if leftmost rule)
	Go to tr3

Now at a tr3 that is zero. So either this is the last rule, or this rule matches.
Note that leftrule.tr3 is q!=q || s!=s, or in other words, 0 if the current rule matches and 1 otherwise.
While leftrule.tr3:
	Apparently no rule matched, so crash().

Apparently leftrule.tr3 is zero, so the current rule matches.
Zero leftrule.tr1 and leftrule.tr2
Copy qto to tr2 (using tr1 as scratch)
Copy swrite to tr3 (using tr1 as scratch)
Copy dir to tr4 (using tr1 as scratch)

Go to rightrule.tr2, set to 1
While nonzero:
	Now current cell (tr2) is 1
	Move rule.0 to tr2 (multiplier -1) and tr3
	Move tr3 back to rule.0
	Move tr2 to rightrule.tr2
	Move leftrule.tr2 to tr2, leftrule.tr3 to tr3, leftrule.tr4 to tr4
	Go to rightrule.tr2 (or tt1 of second cell! Here we use that sizeof(rule) == 2 * sizeof(cell))

Now: [t1 = qto, t2 = swrite, t3 = dir] and cursor is at tt1 of second cell.

Zero qcurrent
Move t1 to qcurrent
Move t2 to t1 and t3 to t2

[t1 = swrite, t2 = dir]

Go to rightcell.tt1, set to 1
While nonzero:
	Now current cell (tt1) is 1
	Move head to tt1 (multiplier -1) and tt2
	Move tt2 back to head
	Move tt1 to rightcell.tt1
	Move leftcell.tt1 to tt1 and leftcell.tt2 to tt2
	Go to rightcell.tt1

Move left a cell width; then at tt1 of the cell where head=1 and [tt1 = swrite, tt2 = dir].

Zero sym
Move tt1 to sym

Move tt2 to cell.0 and tt1
Move cell.0 back to tt2
[tt1 = dir, tt2 = dir]

Go to tt1
While nonzero:
	Subtract 1
	While nonzero:
		Apparently, dir was -1
		Set cell.0 to 1 and go back to tt1
		Zero tt1

[cell.0 = (dir == -1), tt1 = 0, tt2 = dir]
Go to tt2
While nonzero:
	Add 1
	While nonzero:
		Apparently, dir was 1
		Set tt1 to 1 and go back to tt2
		Zero tt2

[cell.0 = (dir == -1), tt1 = (dir == 1), tt2 = 0]

Go to cell.0
While nonzero:
	While leftcell.0:
		Apparently we moved the head beyond the left end of the tape, so crash().

	Move head to leftcell.head
	Go back to cell.0 and zero cell.0

Go to tt1
While nonzero:
	Move head to rightcell.head
	Go back to tt1 and zero tt1

[cell.0 = 0, tt1 = 0, tt2 = 0] and head is in the correct spot.

Now go back to Mmarker:
	Go to tt1 and set to 1
	While nonzero:
		Zero current cell (tt1)
		Set leftcell.tt1 to 1
		Move leftcell.0 to leftcell.tt1 (multiplier -1) and leftcell.tt2
		Move leftcell.tt2 back to leftcell.0
		Go to leftcell.tt1
	
	Now at t1, so go to Mmarker.0