You are here: main → corewar → book of stones → Behemot
Behemot - a Koolaid descendant - is a stun bomber that utilizes
trick called airbag to outsmart brainless frenzy killers
(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
Behemot uses a number of techniques which first have to be introduced to reader to let him have a full picture. Those techniques are airbag and incendiary bombs.
Airbag was widely covered in CW #84. This text is heavily based on that theme so you may skip this part.
The airbag technique was mentioned by M Joonas Pihlaja posted once in rec.games.corewars newsgroup.
Here's what he 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
mov sJb , *sPtr
sPtr mov sStp+1 , *sStp*3+1
add sInc , sPtr
mov }sMb , @sPtr
jmz.a sLoo , {sMb
jmz.f clear , >clear
sInc jmz.f sStp*3 , @sStp*3+1
; some empty core
sJb jmp @sStp , sStp-1
sSb spl #2-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
; ...
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 won't kill us
instantly. 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) ;
dOff equ -254 ;
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
2 sLoo ; 2nd process
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
3 . ; 3rd "
4 . ; 4th "
5 . ; 5th "
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): (note that A-field of line 14 points to line 8)
00008 SPL.B $ 1, $ 8
...
00014 MOV.I $ -6, # -2099 (1)(2)(3)(4)
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)
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, # 7 (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, we face the same situation as in airbag introduction.
Having booted Behemot and bombs, let's stop for a while, focusing on bombs Behemot uses.
Incendiary bombs are small programs a bomber wounds an enemy with. A simple incendiary bombs looks as follows:
MOV.I step, >step ... SPL.B #0 ,#-step+1
When executed, MOV.I lines moves a SPL
that is located step-cell away using an indirection. Stun bomb is
copied below MOV ; when multiprocess warrior executes
it, a SPL carpet is created.
SPL carpets stun enemy, slowing him down or
sometimes immobilizing him. We would call - for simplicity sake -
MOV/SPL part of bomb a pit.
Bombs Behemot pushes incendiaries one step further using kind of vampiric attack - a direct jump to a pit:
JMP.B step , {1
...
SPL.B #2 , step
MOV.I @0 , }-1
When thrown into a core, JMP.B points to a pit,
forming another trap for oponnent's wandering processes. The pit
itself is also more nasty for it forms a kind of SPL
clear.
Having explained incendiaries, we can step towards the attack phase of Behemot. As we shall see, the bombing loop is very sophisticated and carefully implemented.
Bombing loop looks as follows:
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
(we shan't bother about process queue, at least for a moment). Such complicated loop yields 0.6c speed and is called Tornado-like. A detailed disection will reveal its secrets:
03251 MOV.I $ 2666, < 2 -----.
03252 MOV.I $ 2663, * 1 ---. |
03253 MOV.I $ 2220, @ -1333 | |
... | |
05915 JMP.B $ 2223, { 1 <--' |
05916 MOV.I @ 0, } -1 |
05917 SPL.B # 2, $ -2223 <----'
First two lines use 3253 as a pointer for bombs. After two
cycles 3253 itself is first in the queue having both fields
properly set up. The A field points at JMP instruction
(which has been a cycle before copied by the 3252), while the other
field (neglecting indirect addressing mode) points at
SPL ; now taking @ into account, one
notices that B-field of 3253 points to an empty cell. Summing it
up: 3253 copies JMP from 5473 to a cell that B-field
of 3253-1333-1=1919 points to. This B-fiels is equal -2223, so, as
a result, JMP is copied to 1919-2223=7696.
Having laid three bombs, Behemot now shifts the attack pointer:
03206 SPL.B # -1331, < -1330 <---. ... | 03253 MOV.I $ 2220, @ -1334 | 03254 ADD.F * 3, $ -1 (*) | 03255 MOV.I > 2660, @ -2 | 03256 JMZ.A $ -5, < 2659 | 03257 JMP.B $ -51, < -67 ----'
3254 alters both A and B field of previous line:
03253 MOV.I $ 889, @ -2664
03254 ADD.F * 3, $ -1
03255 MOV.I > 2660, @ -2 (*) --.
... |
05915 JMP.B $ 2223, { 1 <-----'
05916 MOV.I @ 0, } -1
05917 SPL.B # 2, $ -2223
A-field of 3255 points to 5915 and via indirection to 5916. The postincrement addressing mode makes it point to 5917.
03255 MOV.I > 2660, @ -2
03256 JMZ.A $ -5, < 2659 (*) --.
03257 JMP.B $ -51, < -67 |
... |
05915 JMP.B $ 2223, { 2 <-----'
05916 MOV.I @ 0, } -1
05917 SPL.B # 2, $ -2223
Predecrementing mode changes B-field of 5915 to 1. Now 3256 points (taking indirection into account) at 5916. Since the A-field of this cell is 0 loop goes back to 3251
03251 MOV.I $ 2666, < 2 (*) 03252 MOV.I $ 2663, * 1 03253 MOV.I $ 889, @ -2664 03254 ADD.F * 3, $ -1 03255 MOV.I > 2660, @ -2 03256 JMZ.A $ -5, < 2659 03257 JMP.B $ -51, < -67
Now, there's a MOV part of incendiary at
3253-2664=589. 3251 moves the SPL above it (to 588)
creating a pit. The warrior countinues its run until a
JMZ loop breaks.
Behemot's loop is very suscteptible to any changes either in the loop itself or in the bomb alignment in the core. Ability of detecting hits in the loop is The Good Thing; detecting a specific type of oponnent helps us adapting by switching to another phase. This is the case in Behemot: it starts to clear the core using d-clear. Let's analyse both cases.
DAT bombs in bombing loopWe now come back to the main idea of Behemot - airbagged loop
that can detect when hit with DAT (actually with any)
bomb. As stated in previous chapter, when booted Behemot's code and
process queue has a following layout:
03250 MOV.I { 0, # 7 (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
3250 overwrites itself with an instruction above it (which
presumably is DAT.F $0, $0 ) and thus we have:
03250 DAT.F $ 0, $ 0 03251 MOV.I $ 2666, < 2 (1)(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
The loop goes on.
When hit with bomb, there're two cases one has to consider:
bombs lands either on 3251-3255 or on 3256. The latter case is
easier to examine - warrior ends its run or is disabled beyond
repair. When it is any other cell Behemot fall through
JMZ.A.
03251 MOV.I $ 2666, < 2 (1) 03252 MOV.I $ 2663, * 1 (2) 03253 DAT.F $ 0, $ 0 (3)(4*) 03254 ADD.F * 3, $ -1 (5) 03255 MOV.I > 2660, @ -2 (6) 03256 JMZ.A $ -5, < 2659 (7) 03257 JMP.B $ -51, < -67
Process 4 obviously dies but the flow goes on till it reaches the layout:
03251 MOV.I $ 2666, < 2 (6) 03252 MOV.I $ 2663, * 1 (7) 03253 DAT.F $ 0, $ 0 (1) 03254 ADD.F * 3, $ -1 (x) 03255 MOV.I > 2660, @ -2 (x) 03256 JMZ.A $ -5, < 2659 (5*) 03257 JMP.B $ -51, < -67
Since there was no process to modify B-field of 5915 the value
that is stored there is equal 1 and after predecrementing it is 0.
Thus JMZ.A checks whether the A-field of
05915 JMP.B $ 2223, { 0
is zero. It is not and Behemot falls through to 3257.
As a sidenote, one can notice that in airbagged loop of N cells one has (N-1) protected cells. Thus, airbag is more effective in bigger loops (thanks to Joonas for pointing this out).
Behemot can detect bombs that lay in remote parts of the core.
It is achieved by smart usage of JMZ.A loop. Let's a
have look at diagram below:
03256 JMZ.A $ -5, < 2659 (*) --.
03257 JMP.B $ -51, < -67 |
... |
05915 JMP.B $ 2223, { 2 <-----'
05916 MOV.I @ 0, } -1
05917 SPL.B # 2, $ -2223
Any value not equal 2 in B-field of 5915 breaks the loop and
makes Behemot fall through JMP.B instruction.
To stop its bombing run Behemot itself alters the bombs. It
simply bombs the 5916 ( MOV.I @0, }-1 ) of which
A-field is checked with JMP.B 2223, {1 making the loop
condition unsatisfied. Behemot enters its final phase.
JMZ.A line, it jumps to d-clear module:
03206 SPL.B # -1331, < -1330 < ----. 03207 MOV.I $ 2, > -17 | 03208 DJN.F $ -1, > -18 | 03209 DAT.F < 2667, $ 21 | ... | 03257 JMP.B $ -51, < -67 (*) --'
The dclear position (above the main bombing loop) is quite
important. For example, when Behemot is hit with SPL #0,
#0 bomb, the loop is burst but few processes are still
trapped in there. When the clear is started it
DAT-wipes stunned processes improving warrior's
performance.
Now, do you want to proceed to main or corewar section of grabun.com? Or maybe you still want to browse through corewar book chapters?