DAT bombers):
org bGo
bStep equ 2223
bDrop equ 382
bDist equ 3250
bcOff equ 51
bgOff equ 17
bRun equ (bHit-bInc*bDrop)
bGate equ (bClr-bgOff)
bSpl equ (bHit-2*bInc)+1
bJmp equ (bHit-2*bInc)-1
bInc equ 3*bStep
bStart mov.i {0 , #0
bLoop mov bSpl , <bPtr
mov bJmp , *bPtr
bPtr mov bRun-bStep , @bRun+bStep+1
bHit add *bEvac , bPtr
mov >bJmp , @bPtr
jmz.a bLoop , <bJmp
bEvac jmp -bcOff , <1-bcOff-bgOff
bGo spl 1 , bWipe+5
bcDst spl 1 , bDist+4+bEvac-bcOff
mov <bGo , <bbDst
mov <bGo , <bcDst
mov <bBoot , {bBoot
mov <bBoot , {bBoot
bbDst mov.i bGo , #bDist+2+bSpl
bBoot jmp >bDist+bEvac+1 , bEvac+1
spl #bInc , <bInc+1
bClr mov bWipe , >bGate
djn.f bClr , >bGate
bWipe dat <2667 , 2-bGate
jmp bStep , {1
mov @0 , }-1
spl #2 , -bStep
The airbag technique was mentioned by M Joonas Pihlaja in once in rec.games.corewars newsgroup.
Here's what Joonas said:
So where before a self-splitting loop was good for life-expectancy, real dat bombs are turning it into a liability. The fix: Use a bombing loop that won't die if it is dat bombed, but also without self-splitting. Aka an airbag. The idea is to use a small fixed number of processes that are scheduled to execute a loop exactly like a single process, and the clever bit is that the loop is created so that the processes can detect if the loop is dat bombed, in which case they fall through to the clear. I doubt I could explain the mechanics of it as lucidly as Paulsson in his posting of his bomber Airbag, so I won't even try. Also see Janeczek's Behemot bomber for this technique.
Since it is often best to follow some code to understand an idea, let's take a look at how airbag is implemented in a warrior. The most recent, to my knowledge, is Return of Vanquisher:
sStp equ 1022
sLoo mov sSb , <sPtr ; main loop starts here
mov sJb , *sPtr
sPtr mov sStp+1 , *sStp*3+1
add sInc , sPtr
mov }sMb , @sPtr
jmz.a sLoo , {sMb ; and ends here
jmz.f clear , >clear
sInc jmz.f sStp*3 , @sStp*3+1
; some empty core
sJb jmp @sStp , sStp-1
sSb spl #1-sStp , 8
sMb mov @0 , <sSb
First, let's take a look at the main loop. We have six instructions, and it more or less looks like a standard bomber using incendiary bombs. A little big, maybe, but it delivers one spl/mov incendiary and two jmp bombs. So we have 4 (?) bombs in a six instruction loop. This means the bomber runs at 0.66c - reasonably fast.
What makes it differ from the standard bombers are the lines:
sCMb mov }sMb , @sPtr
sChk jmz.a sLoo , {sMb ; and ends here
; ...
sMb mov @0 , <sSb
If we take a look at the sMb line, which contains the mov half of the incendiary, we notice it's a-field is zero. Therefore, the instruction at sCMb copies the sMb bomb into core (via the pointer at sPtr), and then increments the a-field of sMb.
Next, the jmz.a in the sChk line, decrements the a-field of sMb, and jumps back to the beginning of the loop (unless somehow, the a-field of sMb no longer contains zero - which leads us to the next point).
As for now the idea is of no practical use. It gives no protection or anything like it. To be more precise: the bomber does a little bit of scanning, since it checks the a-field of a single cell. While fighting a paper, this cell would most likely be overwritten by the paper's code or bombs sooner or later (sooner, we presume). So the scanning line jmz.a could be used as a simple check.
More importantly: we can develop this idea to protect the main loop itself. How can this be possible? Since we have just one process in the loop, once we have been hit our process terminates and the battle ends. But why not place extra processes in our code to make it more resistant to dat bombs? If we can make them execute the loop just like a single process would... This would be perfect!
If we have more processes, a single dat bomb does not kill us so quickly. Now, we can check not only if sMb has been modified, but also if we have been hit by a dat bomb. How can we do this? A single dat bomb would not kill the warrior immediately, but would interfere with subtle timings.
Some processes would be killed. Other processes while executing the sChk line would "know" something is wrong because a previous process did not execute sCMb, and the a-field of sMb contains an unexpected value. These processes would fall through to the line after sChk to perform the end phase (in RoV this is a simple d-clear).
The main problem is to arrange processes to execute the code in the way a single process does. It is not as hard as one can expect:
org bBoo
sStp equ 1022
sLen equ 7
bOff equ (3408+sLoo) ; bomber boot distance
dOff equ -254 ; offset between bomber & bombs
bSrc mov.i {0 , #sLen
sLoo mov sSb+dOff , <sPtr
mov sJb+dOff , *sPtr
sPtr mov sStp+1 , *sStp*3+1
add sInc , sPtr
mov }sMb+dOff , @sPtr
sChk jmz.a sLoo , {sMb+dOff
sSpr jmz.f clear , >clear
sInc jmz.f sStp*3 , @sStp*3+1
;-- boot bombs and extra lines
bBoo mov sMb , bOff+19+dOff
mov sSb , bOff+18+dOff
mov sJb , bOff+17+dOff
mov sInc , bOff+sLen+2
mov sSpr , bOff+sLen+1
bDst spl 1 , bOff+sLen+1
spl 1 , }0
spl 1 , 0
;-- boot bomber
mov <bSrc , <bDst
bJmp jmp >bDst , 0
All starts at the bBoo line. First, we are moving bombs and extra lines that do not belong to the main loop. Then, thanks to John Metcalf's snippets from CW #69, we quickly generate seven (yes,seven) parallel processes. We copy all lines between bSrc and sChk.
And then the magic begins. The b-field of the bDst line points to the mov.i {0,#xx instruction in the booted bomber. The bJmp line directs the first process there. The next process, due to post-increment addressing, jumps to the next line in the booted bomber. And so on. After booting is complete, we have the following situation:
dat 0, 0
1 mov.i {0, #0 ; 1st process <- this process executes first
2 sLoo ; 2nd process <- this process executes second
3 . ; 3rd "
4 . ; 4th "
5 . ; 5th "
6 . ; 6th "
7 sChk ; 7th "
The first line simply moves the dat 0,0 that lays behind our code to the over itself. After this one process has executed we have the following situation:
1 dat 0, 0 2 sLoo ; 1st & 2nd process <- the 2nd process will execute next 3 . ; 3rd " <- then the 3rd process 4 . ; 4th " <- then the 4th process 5 . ; 5th " <- etc 6 . ; 6th " 7 sChk ; 7th "
And finally, after the 7th process has executed, it will be the turn of the first process to execute once again, and so on... You can create a "diagram of process flow" in the code. This is left as an easy exercise for the reader. :-) What you should note is processes execute the code as though it is being executed by a single process, which was our goal. Now, one hit in the lines 2 to 6 of our warrior and we jump to the clear phase, to hopefully deal with the nasty opponent.
The same goal in Behemot is achieved in other, more sophisticated way. Let's take a look at loaded code:
00000 MOV.I { 0, # 0
00001 MOV.I $ 2666, < 2
00002 MOV.I $ 2663, * 1
00003 MOV.I $ 2220, @ -1333
00004 ADD.F * 3, $ -1
00005 MOV.I > 2660, @ -2
00006 JMZ.A $ -5, < 2659
00007 JMP.B $ -51, < -67
00008 SPL.B $ 1, $ 16 (1)
00009 SPL.B $ 1, $ 3201
00010 MOV.I < -2, < 4
00011 MOV.I < -3, < -2
00012 MOV.I < 3, { 3
00013 MOV.I < 2, { 2
00014 MOV.I $ -6, # -2095
00015 JMP.B > 3243, $ -7
00016 SPL.B # -1331, < -1330
00017 MOV.I $ 2, > -17
00018 DJN.F $ -1, > -18
00019 DAT.F < 2667, $ 21
00020 JMP.B $ 2223, { 1
00021 MOV.I @ 0, } -1
00022 SPL.B # 2, $ -2223
First four cycles are spent on producing four parallel processes;
after that code looks as follows:
00008 SPL.B $ 1, $ 16
00009 SPL.B $ 1, $ 3201
00010 MOV.I < -2, < 4 (1)(2)(3)(4)
00011 MOV.I < -3, < -2
00012 MOV.I < 3, { 3
00013 MOV.I < 2, { 2
Within next 16 cycles different bits and pieces are booted into
remote part of core (lines 10-13);
00008 SPL.B $ 1, $ 8 ;<-------------------------------------- ... | 00014 MOV.I $ -6, # -2099 (1)(2)(3)(4) --- A-field points here --- 00015 JMP.B > 3235, $ -15
Process labeled (1) moves SPL 1, XXX line on line 14
itself:
00008 SPL.B $ 1, $ 8 ... 00014 SPL.B $ 1, $ 8 (2)(3)(4) ;<--- this line is executed 00015 JMP.B > 3235, $ -15 (1)Having three processes executing
SPL 1 line one receives
6 parallel process; if we now notice that process (1) fell thorugh
without spliting itself it is easy to observe that in line 15 there're
7 parallel processes:
00015 JMP.B > 3235, $ -15 (1)(2)(3)...(7)In line 15+3235=3250 one finds Behemot's main part:
03250 MOV.I { 0, # 0
03251 MOV.I $ 2666, < 2
03252 MOV.I $ 2663, * 1
03253 MOV.I $ 2220, @ -1333
03254 ADD.F * 3, $ -1
03255 MOV.I > 2660, @ -2
03256 JMZ.A $ -5, < 2659
03257 JMP.B $ -51, < -67
which processes smartly jump into, using cool trick. First, the
B-field of 3250th cell, that A-field of JMP instruction
points to is equal zero. This means that first process jumps directly
into MOV.I {0, #0 cell modyfing (via postincrement
addressing mode in 15th cell) its B-field; cell number
3250 now reads
03250 MOV.I { 0, # 1
Next process will be directed to line number 3251 and line 3250 will
loook as follows:
03250 MOV.I { 0, # 2
And so on till all processes jump into Behemot's main part; processes
are now splitted into every cell of bomber:
03250 MOV.I { 0, # 0 (1)
03251 MOV.I $ 2666, < 2 (2)
03252 MOV.I $ 2663, * 1 (3)
03253 MOV.I $ 2220, @ -1333 (4)
03254 ADD.F * 3, $ -1 (5)
03255 MOV.I > 2660, @ -2 (6)
03256 JMZ.A $ -5, < 2659 (7)
03257 JMP.B $ -51, < -67
Now, it is the same way as in airbag introduction.