Brainf*** Interpreter in Redcode

Brainf*** is an esoteric programming language developed by Urban Müller. There are 8 instructions in brainf***:

Ins	Macro	Description
<	lt	move pointer left
>	gt	move pointer right
+	inc	increment memory cell at pointer
-	dec	decrement memory cell at pointer
.	out	output a character from the cell at pointer
,	in	input a character and store in cell at pointer
[	op	jump past matching ] if cell at pointer is 0
]	cl	jump to matching [ if cell at pointer not 0

Brainf*** operates on an array of memory cells and has a pointer into the array. Each instruction translates directly into Redcode. Before executing the brainf*** program, the interpreter calculates and stores the offset for [ and ] to avoid repeated searching.

Here's the code:

        lt equ sub #1, ptr
        gt equ add #1, ptr
        inc equ add #1, @ptr
        dec equ sub #1, @ptr
        out equ sts @ptr, 0
        in equ lds @ptr, 0
        op equ jmz 0, @ptr
        cl equ jmn 2, @ptr

        org    seek

ptr     mov.ba #0,        #prog

find    sne.a  #2,        *ptr
        sub    #1,        count
        sne.a  #0,        }ptr
        jmp    find,      >count
count   jmn    find,      #0

        mov.a  ptr,       @ptr
        sub.ba ptr,       >ptr
        mov.ba ptr,       {ptr
        sub.a  ptr,       *ptr

seek    jmn.a  seek,      >ptr
        jmn    ptr,       <ptr

prog

Redcode Interpreter for the RSSB Single Instruction Computer

The RSSB single instruction computer is a minimal, Turing complete virtual machine. The instruction used is Reverse Subtract and Skip if Borrow. RSSB subtracts the accumulator from the contents of a memory location and stores the result in both. The next instruction will be skipped if the accumulator was greater than the value in memory.

Jumps can be implemented by manipulating the instruction pointer at memory location 0. Other special locations are as follows:

1. accumulator
2. always contains 0
3. input
4. output

Here's the code for the interpreter. I've included a Hello World program written in RSSB. If you think you can reduce the size of Hello World, please let me know how.

        org    rssbint

rssbint mov.ba >ip,       ip    ; load next instruction

        mov    #0,        zero  ; set zero

        sne.a  #3,        ip    ; handle input
        lds    in,        0

        sne.a  #4,        ip    ; handle output
        sts    acc,       0
        mov    acc,       out
        add    out,       out

        slt    *ip,       acc   ; set flag for skip
        mov    #2,        skip

        sub.b  acc,       *ip   ; acc, *ip = *ip - acc
        mov.b  *ip,       acc

skip    djn    noskip,    #1    ; skip if required
        nop    >ip,       >skip

noskip  slt    #7900,     @ip   ; protect interpreter

        jmn    rssbint,   ip    ; loop until ip = 0

; --------------------------------------

ip      dat    5      ; instruction pointer
acc     dat    0      ; accumulator
zero    dat    0      ; always 0
in      dat    0      ; character input
out     dat    0      ; character output

; --------------------------------------

loop    dat    -ip+   acc       ; acc = character from ptr
ptr     dat    -ip+   hello        

        dat    -ip+   out       ; display character

        dat    -ip+   zero      ; acc = -acc

        dat    -ip+   zero      ; always skipped

        dat    -ip+   sum       ; subtract acc from sum

        dat    -ip+   ip        ; skipped if sum is negative,
                                ; otherwise jump to 0

one     dat    -ip+   acc       ; subtract 1 from ptr
        dat    -ip+   one
        dat    -ip+   ptr

        dat    -ip+   acc       ; jump to loop
        dat    -ip+   loopoff
        dat    -ip+   ip
loopoff dat    -loop

sum     dat    -1116

        dat    33         ; '!'
        dat    100        ; 'd'
        dat    108        ; 'l'
        dat    114        ; 'r'
        dat    111        ; 'o'
        dat    87         ; 'W'
        dat    32         ; ' '
        dat    44         ; ','
        dat    111        ; 'o'
        dat    108        ; 'l'
        dat    108        ; 'l'
        dat    101        ; 'e'
hello   dat    72         ; 'H'

        end

The Corewar DynaHill

Christian Schmidt has announced the opening of a new Corewar hill with a ranking system similar to Japanese Sumo. The Corewar DynaHill is of unlimited size. New warriors enter at the bottom and at certain time intervals each warrior fights 15 neighbours.

Depending on the number of wins / losses, each warrior moves either up or down a number of positions. Eventually, the warrior will be unable to climb higher, possibly becoming King of the DynaHill!

'94draft and limited process warriors co-exist on the hill. If a '94draft warrior battles against a limited process warrior, a random number of processes is chosen between 40 and 120.

The use of PIN and MAXPROCESSES is forbidden. The maximum length is 200.

For more information, take a look at The Corewar DynaHill FAQ.

Call / Return Macros in Redcode, a Possible Solution

Here's one solution to the call / ret problem in Redcode. Unfortunately the offsets in multi-line-equates can be slightly out. In this solution, the offsets are adjusted the first time the call is executed.  Here's how it works:

call routine compiles as follows:

        mov    #2-return, <stack ; save return address
        jmp    callsub,   1+routine ; jump to callsub which adjusts the address
                                    ; b-field pointer is either correct or out by 1

callsub then adjusts the pointer if necessary and moves it to the a-field of the jmp:

         mov    #2-return, <stack ; save return address
         jmp    routine,   1+routine ; jump to routine, a-field is correct

The jmp now contains the correct offset and jumps directly to routine in future.

Here's the code:

stack   dat    0

call    equ    mov    #2-return, <stack
        equ    jmp    callsub,   1+

ret     equ    jmp    return

return  mov.b  >stack,    #0
        jmp    @return

callsub mov.b  @stack,    #0
        add    #return-callsub, callsub
        mov.ba <callsub,  @callsub
        slt.b  @callsub,  #CORESIZE/2
        jmp    @callsub
        djn.a  @callsub,  @callsub

Call / Return Macros in Redcode

For a while I've been trying to implement call / ret macros in Redcode so I can call subroutines. The obvious solution is as follows and doesn't work correctly:

; this code is buggy

stack   dat    0

call    equ    mov    #2-return, <stack
        equ    jmp

ret     equ    jmp    return

return  mov.b  >stack,    #0
        jmp    @return

Unfortunately, this only works for forward calls. The address offset is out by 1 for reverse calls and I can't find a simple fix. I've tried the following solutions, but I'm not particularly happy with any of them:

• adding a nop to the top of all subroutines (extra code)
• using a macro to automatically adjust the address, e.g. call subroutine adjust (ugly)
• adjusting the address the first time it is executed (extra code, slower)

Can you suggest a better solution?