Extended qscan using only sne/seq pairs. Part I

A general form of q4ish scan can be constructed like this:

tA dat 0 ,qA
tB dat 0 ,qB
tC dat 0 ,qC

sne qPtr+qM*qA ,qPtr+qM*qA+Dist
seq <tA ,qPtr+qM*(qA-1)+Dist
jmp decode ,{tB
sne qPtr+qM*qB ,qPtr+qM*qB+Dist
seq <tB ,qPtr+qM*(qB-1)+Dist
jmp decode ,0
sne qPtr+qM*qC ,qPtr+qM*qC+Dist
seq <tC ,qPtr+qM*(qC-1)+Dist
jmp decode ,}tB

decode mul.b *tB ,qPtr
sne null ,@qPtr
add.ab #Dist ,qPtr
mov bomb ,@qPtr
qPtr mov bomb ,@qM
add.ab #Incr ,qPtr
djn -3 ,#10

Only a little math is needed to make things come out right. After the
seq decrements tA we see that:

tA+(qA-1) = qPtr+qM*(qA-1)
(qA-1)*(1-qM) = qPtr-tA ; gather (qA-1) terms on left
(qA-1)*(qM-1) = tA-qPtr ; multiply both sides by -1
(qA-1)*(qM-1)*qMod = (tA-qPtr)*qMod ; multiply both sides by new
value qMod
(qM-1)*qMod = 1 mod 8000 ; define qMod
qA-1 = (tA-qPtr)*qMod ; remove (qM-1)*qMod = 1
qA = (tA-qPtr)*qMod + 1 ;

qB & qC are derived the same way.

With tB = tA+1 and tC = tA+2, the parameters determining qA qB & qC
are:
tA = location of tA in the compiled program
qPtr = location of qPtr in the compiled program
qMod = some value where (qM-1)*qMod = 1 mod 8000

If tA can be put anywhere from 0 to 97 and qPtr anywhere from 4 to 96,
that is roughly 10000 combinations. And there are 3201 pairs of
numbers satisfying (qM-1)*qMod = 1 mod 8000, including (2,1) (4,2667)
(8,1143). This is the set of imp numbers, each incremented by 1.
That gives roughly 3 million parameter combinations, each generating
12 search values. Wowsers!

Corewars' space is indeed vast! So vast that we can add additional
constraints and still have abundant choices. Moore took advantage of
this to bury pointers to tA tB & tC in the decoder:

decode mul.b *2 ,qPtr
decide sne {table1 ,@qPtr
add.b table2 ,qPtr
mov table3 ,@qPtr
qPtr mov bomb ,@factor
add.ab #Incr ,qPtr
djn -3 ,#10

This allows the qA qB & qC values to be distributed into other program
code. At the same time, he collapsed Dist into the tables which only
complicates the math a little. With extensions, these q4/q4.5 qscans
have proliferated across the hills.

Some characteristics of q4/q4.5 are a bit undesirable:
1. only six sne/seq pairs possible
2. can only be extended with seq scans, like q3
3. at least one pair of values will be < 100 apart

A sne/seq pair is dense. 4 values scanned in only 3 lines. An seq
scan is 2 values in 2 lines, so it is less dense. Density is an
advantage, the more dense your code is, the less likely it is to be
discovered by an opposing qscan. Ideally, all your scans will be sne/
seq pairs, and all of your opponents would be seq scans, giving you a
25% scanning advantage. This is why q3 disappeared from all the hills
and won't be back. q4 scans are significantly denser.

The usual code includes six sne/seq pairs for 24 search values. This
is often extended using seq scans, plus a jmz scan for a total of 33
values. It has not been previously reported, but sne/seq pairs can
also be extended with another seq:

seq qPtr+qM*(qA+1) ,qPtr+qM*(qA+1)+Dist
jmp 3 ,>tA
sne qPtr+qM*qA ,qPtr+qM*qA+Dist
seq <tA ,qPtr+qM*(qA-1)+Dist
jmp decode ,{tB

Now you can have up to 45 scan values using 6 sne/seq quads, 10 seq
pairs, and 1 jmz. Unfortunately we are looking more like a q3 scan
than a q4. Instead, what if we could scan using only sne/seq pairs?

Coming up in Part II - 40 scans using only sne/seq pairs!

P. Kline