Behemot by Michal Janeczek

back to the home page

You are here: maincorewarbook of stones → Behemot

Table of contents

  1. Introduction
  2. How it works
    1. Airbag
      1. The concept
      2. The code
      3. Parallel execution of processes
      4. Bootstrapping
      5. Booting Behemot away
    2. Incendiary bombs
    3. The attack phase
      1. Breaking the bombing loop
      2. Detecting DAT bombs in bombing loop
      3. Detecting modification of bomb layout
    4. The clear phase

Introduction

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

^top

How it works

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.

^top

Airbag

Airbag was widely covered in CW #84. This text is heavily based on that theme so you may skip this part.

^top

The concept

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.

^top

The code

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).

^top

Parallel execution of processes

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).

^top

Bootstrapping

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.

^top

Booting Behemot away

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.

^top

Incendiary bombs

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.

^top

The attack phase

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.

^top

Breaking the bombing loop

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.

^top

Detecting DAT bombs in bombing loop

We 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).

^top

Detecting modification of bomb layout

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.

^top

The clear phase

When the loop is broken and Behemot's falls through 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.

^top

Related texts

^top

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?