;redcode-94
;name FastSpawnGeneratorV3
;author Skybuck Flying
;version 3
;history version 1,2,3 created on 7 december 2007
;assert 1
; version 3:
MUL.AB #2 ,$1
SLT.AB #99 ,#1
JMP.B $-2 ,$0
DIV.AB #2 ,$-2
MOV.X $-3 ,$1
DIV.AB #0 ,#0
JMZ.B $3 ,$-1
MOV.I $9 ,>11
JMP.B $2 ,$0
MOV.I $8 ,>9
MOV.X $-9 ,$1
MOD.AB #0 ,#0
DIV.AB #2 ,$-11
MOV.BA $-2 ,$-12
JMN.B $-10 ,$-13
JMP.B $4 ,$0
SPL.B $1 ,$0
MOV.I $-1 ,$0
DAT.F $0 ,#1
for 0
;
; 26 instructions needed in core. At least my code size is now smaller than John's :) John's was 31
;
; Tested with 100 and working ok :)
;
; 191 cycles needed. another 10% improvement compared to version 2.
;
; Let's try further optimization by working directly with values in the slt's etc try to alter them directly etc.
;
; version 2:
;
; Tested with 100 and working ok :)
;
; 214 cycles needed. 8% improvement ;) probably more optimization can be done ;)
;
; Let's write an optimized spawn generator to try and beat at least John's spawn generator lol.
;
; I think I can optimize it by using dual counters so that the mov instructions can move twice as many data into the comparators etc.
;
; version 1:
; Tested with 100 and working ok :)
; 235 cycles needed to generate 100 threads.
; Code/comments still a bit messy but it's working ! =D
;
; Let's write a faster spawn creator.
;
; Hello,
;
; Listen if you want to spawn a number of threads then do the following:
;
; First substract 1 from the number of threads.
;
; Then determine where it lies on the binary scale for example
; 1-2-4-8-16-32-64-128-256-512-1024
;
;For example (101-1) = 100 threads to be created to get 101 threads lies
;between 64 and 128.
;
;Simple idea, start with 1, multiply it by 2, keep multiplieing it by 2 until
;it's greater than the number of threads.
;
;Now divide it once and you have something which you can use to find the
;binary number for 100.
;
;Call it the divisor. For example for 100 the divisor starts with 64.
;
;Here's the rest of algo:
;
;Divide Number of Threads (100) by the divisor (64).
;
;If it can divide it gives 1 if not it gives a 0.
;
;Now comes the interesting part.
;
;For a 1, the number of threads need to dubbel.
;For a 0, the number of threads need to dubbel-1.
;
;Depending on the outcome, dubbel or dubbel-1 the threads.
;
;To dubbel use spl 1
;To dubbel-1 use mov spawn, 0 (spawn is spl 1)
;
;Then make all threads jump to generated instruction as described in the two
;lines above.
;
;So for a 1:
;
;spl 1 should be executed.
;
;So for a zero
;
;mov spawn, 0 will be executed for the first thread.
;all other threads will execute
;spl 1, 0
;
;This has the effect that one less thread will be created which is exactly
;what it should.
;
;Now divide the divisor by 2 and repeat the loop, until the divisor is zero.
;
;Here is an example:
;
;100 div 64 = 1, remainder 35
;36 div 32 = 1, remainder 4
;4 div 16 = 0, remainder 4
;4 div 8 = 0, remainder 4
;4 div 4 = 1, remainder 0
;0 div 2 = 0, remainder 0
;0 div 1 = 0, remainder 0
;0 div 0 = death of thread. you could try to avoid it or use it to your
;adventage to kill off any calculating thread or so.
;
;binary 1100100 = 100
;
;Now you have an algorithm to extract the binary one's and zero's from the
;number 100.
;
;And thus you can create a nice spawning program which will execute fast.
;
;The spawning program should look something like:
;spl 1
;spl 1
;mov -1, 0
;mov -1, 0
;spl 1
;mov -1, 0
;mov -1, 0
;jmp 0
;
;An alternative method (untested but will probably work just as well):
;
;spl 1
;spl 1
;mov SplInstruction, 0
;mov SplInstruction, 0
;spl 1
;mov SplInstruction, 0
;mov SplInstruction, 0
;jmp 0
;SplInstruction spl 1
;After this code has been executed there will be 100 threads created plus the
;main thread so 101 threads ! nice eh ! ;)
;
;Now the only thing to do is for example write some nice redcode code which
;implements the algorithm with div's, mod's and such.
; modified in v2
; mov.a #99, NumberOfThreadsToSpawn ; number of threads to spawn
; Algorithm:
;
; Step 1: start with 1 and keep multiplieing it until it's greater then the number of threads to spawn
; the multiplieing result will ultimately be used as a divisor so the variable will be called "Divisor"
; multiplies divisor by 2 in comparison.b
Multiplier mul #2, Comparison
; A = NumberOfThreadsToSpawn, B = Divisor
Comparison slt #99, #1
jmp Multiplier
; now we need to divide the divisor once
div #2, Comparison
;
; Step 2: Divide the NumberOfThreadsToSpawn by the divisor, the outcome indicates a 1 for spl 1 or mov spl 1, 0 for a zero.
; then calculate the remainder for number of threads to spawn
; then divide the divisor by 2, repeat until divisor is zero
Step2
; move values from comparison to divider, swapped.
mov.x Comparison, Divider
Divider div #0, #0
; look at result, generate instruction etc
; look at the result,
; if it's a 1 we need to add instruction: spl 1, to the spawn program
; if it's a 0 we need to add instruction: mov doubleinstruction, 0 to the spawn program
jmz.b StepDoubleMinusOne, Divider
StepDouble:
mov DoubleInstruction, >SpawnProgramPointer
jmp Skip
StepDoubleMinusOne:
mov DoubleMinusOneInstruction, >SpawnProgramPointer
Skip
; calculate the remainder for the number of threads to spawn
; move values from comparison to modder
mov.x Comparison, Modder
; A= Divisor, B = Number of Threads To Spawn, result in B = remainder
Modder mod #0, #0
; divide the divisor by 2
div #2, Comparison
; move the result of the modder back to the comparison.a/number of threads to spawn
mov.ba Modder, Comparison
; repeat
jmn Step2, Comparison
; add a spinner to the spawn program to keep the threads spinning to demonstrate how many there are ;)
; could be handy for final programs as well. probably would have to alter jump instruction to compensate for generated program length
; ignored for now... just jump to end of program for now ;)
; mov SpinnerInstruction, >SpawnProgramPointer
; jump to spawn program to execute it
; jmp @SpawnProgramPointer ; wrong offset ignored for now, might not even matter as long as one knows where to jump to at begin of the algo
jmp EndOfProgram
DoubleInstruction spl $1, 0
DoubleMinusOneInstruction mov DoubleInstruction, 0
; SpinnerInstruction jmp $0, $0
; NumberOfThreadsToSpawn dat $0, #0
; Divisor dat $0, #0
; replaced with dual data storage:
SpawnProgramPointer dat $0, #EndOfProgram
EndOfProgram
rof