#
# Core Wars program
#
# Walter Hofmann, March 2000
#

# We want to kill Imps by using a sequence of "move 0,A" instructions
# which will be executed by multiple threads at the same time.
# If T is the number of threads, C is the number of "move" instructions
# and S is the size of the core then S<=T*C must hold to be sure that
# we catch every Imp regardless of its starting point.
# We need  k = T + 2C + const  steps to set everything up: Creating a 
# thread is one instruction (fork) if done right, to fill memory with 
# "move" instructions we need a loop (2 instructions per cell).
# We try to minimise k under the constraint S=T*C. This gives
# T = sqrt(2*S). sqrt(S) is info(1), sqrt(2) is approximated with a 
# rational number which was calculated using a continued fraction 
# expansion of sqrt(2).
# We first fill the memory with enough "move" instructions. Then we
# need to generate the threads. Doing fork in a loop is too expensive,
# we use a fork cascade instead. This can generate a power-of-two
# number of threads. Therefore we calculate the binary representation
# of T and fork into the fork-cascade at every "one" bit in it. This is 
# done by a dynamically generated piece of code.

	title "Imp killer cascade"
        author "Walter Hofmann <walterh@gmx.de>"

CREATE:	info 6,T
	info 1,S
	mul 19601,S	# it's magic!
	div 13860,S
	less S,T
	move S,T
	info 0,S
	div T,S
	add 1,S
L1:	movei X,Y	
	loop S,L1
	move IU,[Y]

	add -1,T
L2:	add -1,P
	move 1,B
	and T,B
	div 2,T
	move IF,[P]
	equal B,0
	move IJ,[P]
	loop C,L2
	jump START

T:	data 0
B:	data 0
P:	data &END
C:	data 11
S:	data 0
X:	data &A0
Y:	data &A

IJ:	jump IU
IU:	jump IU
IF:	fork END

START:	data 0
	data 0
	data 0
	data 0
	data 0
	data 0
	data 0
	data 0
	data 0
	data 0
	data 0
END:	jump A

A10:	fork A9
A9:	fork A8
A8:	fork A7
A7:	fork A6
A6:	fork A5
A5:	fork A4
A4:	fork A3
A3:	fork A2
A2:	fork A1
A1:	fork A0
A0:	move 0,A10
A:	data 0