Secret Opcodes of the 8 Bit Processors

Undocumented instructions were common on early processors. A few would crash the computer (HCF - halt and catch fire) while others had strange but occasionally useful behaviour. Any self-respecting programmer would make use of these to squeeze out the last few cycles of performance.

The effect of undocumented opcodes would vary between different versions of some processors, no doubt leading to the classic excuse “it worked on my machine”. Here are a few examples I've found useful.

Secrets of the Z80

Zilog's Z80 was used in a number of popular 8 bit computers including the Sinclair Spectrum, Amstrad CPC, TRS-80 and MSX. There are a number of undocumented opcodes with the CB, DD, ED and FD prefix.

• CB30-CB37 - SLL reg shifts a register left, setting bit 0.
• DD - when used as a prefix to instructions which use H or L, either the high or low 8 bits of IX are used.
• FD - as DD, but the high or low 8 bits of IY will be used.
• ED70 - IN (C) reads from i/o port C, setting the flags and discarding the result.
• ED71 - OUT (C),0 outputs a zero to port C.

Secrets of the 8086/8088

Intel's 8088 was used in the original IBM PC and has spawned an entire family of processors.

• D6 - SALC sets the AL register to either 00 or FF depending on the carry flag. SALC was finally documented with the introduction of the Pentium Pro 27 years later.
• 0F - POP CS pops the CS register from the stack. Only works on 8086 processors.
• 0F05 - LOADALL loads all registers from memory location 0800. Only works on 80286 processors.

Which processors have you programmed and did you find any undocumented opcodes useful?

A History of Programming Games 1961-1989

In a programming game players write a program to complete a specific task, usually to wipe out all opponents. The contest takes place between either programs in the memory of a virtual computer or robots in an arena.

Darwin

In August 1961, Douglas McIlroy, Robert Morris and Victor Vyssotsky invented Darwin and the programming game genre. Programs written using IBM 7090 machine code competed to destroy all opponents and be the most prolific replicator. An Umpire provided three functions to probe memory for an opponent, to claim memory or kill an opponent.

RobotWar

RobotWar was written in the 1970s by Silas Warner for the PLATO computer system and published commercially for the Apple II by MUSE Software in 1981. Programs written in a proprietary high level language control robots which battle to eliminate all opponents in a virtual arena. In the early 1980s a society was formed and an annual tournament organised by Computer Gaming World.

Color Robot Battle

The Image Producers released Color Robot Battle in 1981 for the TRS-80 Color Computer. The game was played by writing programs in a simple hybrid of BASIC and Logo to control a battle robot. Programs faced each other in a one-on-one battle with the last robot standing being declared winner.

Core War

Alexander Dewdney described Core War in the May 1984 issue of Scientific American, introducing programming games to a wide audience for the first time. Core War became popular overnight. A society was formed, a newsletter published and regular tournaments held. Core War is played between assembly languages programs in the memory of a virtual computer. Each program attempts to eradicate all opponents. Core War can be played by email at KOTH.org or KOTH@SAL.

DROID

Inspired by RobotWar, DROID was developed at Reichhold Chemicals as a teaching aid in December 1984. Programs to control robots are written in the D-code assembly language and attempt to exterminate all adversaries in the virtual arena. DROID can be played by Telnet on the Empire HPe3000 server.

CROBOTS

Tom Poindexter published CROBOTS as shareware in December 1985 after being inspired by RobotWar. A subset of C is used to control battle robots. As usual, the aim of the game is to destroy all opponents in a virtual arena. A king of the hill tournament is organised by Maurizio Camangi.

P-Robots

In 1988 David Malmberg released P-Robots, a robot battle game based on a subset of the Pascal programming language and inspired by CROBOTS. Later versions introduced a variety of optional extras for robots, teams and obstacles.

OMEGA

OMEGA is a programming game written by Stuart Marks and published by Origin Systems in 1989. The object of the game is to program a tank to defeat a series of increasingly more powerful enemies. Each opponent defeated unlocks a higher security clearance and increased budget.

Unfortunately there's very little information about some of these games online. Do you remember playing any of the above? Which is your favourite programming game and why?

#songsincode - Lyrics for Programmers

#songsincode are small pseudo-programs which display a song title or part of the lyrics. The more refined examples use conditional code and control stuctures to define the song.

The tag was first used on twitter a couple of weeks ago. After a sudden burst of popularity, #songsincode has slowed to about 20 tweets a day. Here's an example by testydonkey:

if(Door.Color == System.Color.Red)
{ Door.Color = System.Color.Black; }

This is Paint it Black by the Rolling Stones, “I see a red door and I want it painted black”.

Here's the top 25 countdown of the very finest #songsincode. Can you identify all 25? Is your favourite missing? Let me know :-)

anurse:

var s = new Submarine(Color.Yellow);
s.Residents.Add(Us); for(int i=0;i<2;i++)
{Assert.IsTrue(s.Color == Color.Yellow);}

darrennisbett:

h=new hotel(); h.name="california";
h.guest.addEvent("checkout");
h.guest.removeEvent("leave")

royvanrijn:

if(grass=="green" && girls == "pretty")
{ takeMe(paradiseCity); }

injenierobarsa:

for (int i = 1; i <= 99; i++)
{ redBalloons[i].goBy() }

3d0:

if(my.sexyness>shirt.sexyness) pain();

phikachu:

me.color = 0x0000FF;
me.text = “Da Ba Dee Da Ba Di”;

Borisson:

($horse_name == false ? $location = desert : ' ');

plaxdan:

self.vehicle = new CombineHarvester();
you.setKey(vehicle.getKey());

cargoweasel:

SubwayWalls.write(words_of_the_prophets());

Leadhyena:

I.send("...---...",world);
I.send("...---...",world);
while(!(someone.receive(bottle)&&
bottle.contains(message)){I.hope()}

antallan:

substring("the tiger",6,1)

pitsk:

void shootPeople() { shootSherif; return;
shootDeputy; }

sbruchmann:

if ($angelsDeserveToDie) { iCry(); }

royvanrijn:

while( !me.like(mondays) ) { tellWhy(me); }

Levistica:

cuts.firstElement().deepness = max;

uberTof:

final--;

plaxdan:

while (thing != that) { doForLove(thing);

numptygeek:

jumpWithDirection(left); stepWithDirection(right);

CarstenHagemann:

$jealous_sky[$sun] = $you->tell()
if ($we->walk($fields_of_gold));

numptygeek:

if(somethingStrange==true && location ==
neighborhood){ ghostbusters();
printf("I ain't afraid of no ghost");}

draconum:

//roxanne.putOnLight('#ff0000');
commented out, was not necessary

brozow:

video$ kill -9 `ps -ef | grep radio*`

rennyhernandez:

stuff={'red door','a line of cars', 'my heart'}
stuff.each do |it| it.setColor('#000000') end

codepo8:

.clowns{float:left;}.jokers{float:right};
#me_you{position:fixed;margin:0 auto;width:100%}

royvanrijn:

for(Leaf leaf:leafs)
{ leaf.setColor(new Color(139,69,19)); }
sky.setColor(Color.GRAY);

#moviesincode, #tvincode, #booksincode!

#songsincode has inspired three new tags. Can you see #moviesincode, #tvincode or #booksincode catching on? :-)

sijmen:

TypeError: Result of expression this.spoon'
[undefined] is not an object

rhizomecowboy:

trace(isNAN(prisoner));

nail7:

var i = count(MonteChristo);

My Two Greatest Programming Sins

My programming sins are too numerous to count, but there are two which keep coming back to haunt me over and over:

• version control - while developing a program I create multiple versions. Development may split into multiple paths or be backtracked. Without proper version control, confusion is inevitable.
• illegible code - I make frequent tweaks and changes, use irrelevant names for labels and functions and fail to comment code. It's unlikely I'll understand the program if I return to it a few weeks later.

Earlier this week I posted an example of ugly code. By examining the program, the magic numbers or output for sample input, three readers identified the code as an implementation of parallel bit counting. Here's how the bit counter ought to have been implemented:

: (COUNTBITS) ( u1 u2 u3 -- u4 )
( u1 = partial count )
( u2 = power )
( u3 = mask )
( u4 = new partial count )
ROT 2DUP AND >R ROT / AND R> +
;

: COUNTBITS ( u1 -- u2 ) ( parallel count )
( u2 = number of 1 bits in u1 )
2   %101010101010101 (COUNTBITS)
4   %011001100110011 (COUNTBITS)
16  %000011100000111 (COUNTBITS)
256 %000000000001111 (COUNTBITS)
;

To increase code legibility, the following changes have been made:

• function name now represents the word's behaviour
• word factored into two simpler words
• documented the word's stack activity
• represented the bit masks in binary

It's also worth considering what countbits will be used for (any suggestions?). Do we really need a fast bit twiddling algorithm? A simple iterated count or sparse ones algorithm will probably suffice:

: COUNTBITS ( u1 -- u2 )( iterated count )
( u2 = number of 1 bits in u1 )
0 SWAP
BEGIN
2 /MOD >R + R>
?DUP 0=
UNTIL
;

: COUNTBITS ( u1 -- u2 ) ( sparse ones )
( u2 = number of 1 bits in u1 )
0 SWAP
BEGIN
?DUP
WHILE
DUP 1- AND >R 1+ R>
REPEAT
;

Now I've identified a couple of faults with my coding technique, I'm hoping to correct my shortcomings while tackling my next programming project. What is your greatest coding sin and how do you plan to deal with it?

Impenetrable Code

However elegant a programming language, some fool will always find a way to write ugly code.

Here's a word I recently implemented in Forth:

: C
>R
256 15 16 1799
4 13107 2 21845
R>
4 0 DO
TUCK OVER AND -ROT
INVERT AND ROT / +
LOOP
;

Although I didn't set out to intentionally create something hideous, I'm appalled by how difficult to understand the code is. How can I make the word easier to comprehend and can you remind me what it's supposed to do?

Perverse Code: Deviant Forth

The Forth programming language has a set of functions (or words) called primitives. These are traditionally written in the language of the host machine to keep the system as simple and efficient as possible. Typically the primitives required no more than about five machine instructions each to implement.

Deviant Forth explores the possibility of using Forth to implement some of the primitives. Warning, prolonged exposure to this code may cause permanent damage to your eyes!

As a exercise, let's implement NIP in Forth:

: NIP SWAP DROP ;

Standard stuff so far. Now lets try to implement SWAP and DROP!

: DROP DUP - + ;

: SWAP OVER >R >R DROP R> R> ;

Things are beginning to look ugly. On most systems DROP can be implemented in one machine instruction and SWAP in four. It's also possible to implement DUP, + and OVER in Forth:

: DUP >R R@ R> ;

: + >R DUP DUP - R> - - ;

: OVER >R DUP DUP R@ - DUP >R - R> R> + ;

I'm no Forth purist, but I feel repelled by the abomination I've programmed. Despite this, it's interesting to discover so many Forth words can be implemented with just >R, R>, R@ and -, however unnatural it might be.

As an afront to the very nature of Forth I challenge you to implement ROT using only >R, R>, R@ and -. If you can in less than 50 words I'd love to see your solution, however unpleasant :-)

RobotWar and the Army of Clones

Back in 1981 Silas Warner created a game for MUSE Software which would go on to spawn an entire army of clones. Silas is probably better know as the author of the legendary Castle Wolfenstein. However it was RobotWar which went on to inspire a whole new genre.

Silas developed RobotWar for the PLATO computer system and later ported it to the Apple II for release by MUSE. The game is set at a time in the distant future when war has been declared hazardous to human health. Wars still rage, but the combatants are robots programmed to battle to the death.

RobotWar is played by writing the control program for one of these battle robots. The program controls the movement, radar and gun of the robot. Here's one of the example robots:

;     ROBOT  'SCANNER'
; SEND RADAR PULSE AND FIRE IF AN
; ENEMY IS SPOTTED

SCAN
AIM + 7 TO AIM

CHECK
AIM TO RADAR
IF RADAR > 0 GOTO SCAN
0 - RADAR TO SHOT
GOTO CHECK

Scanner is a simple stationary warrior. The first instruction (at scan) turns the gun 7° clockwise. The next instruction (at check) lines up the radar with the gun. The radar returns a positive number if it detects nothing, otherwise it returns minus the distance to the opponent.

The next line jumps back to scan if the radar returns positive. Otherwise a shell is fired by the penultimate instruction and the next line jumps back to check.

RobotWar earned a strong following in the early 1980's. Computer Gaming World organised annual tournaments and a group of enthusiasts formed the Postal RobotWar Club of America.

RobotWar has inspired a huge number of clones, I'll just mention a select few here:

• CROBOTS by Tom Poindexter (1985) uses a subset of C
• P-Robots by David Malmberg (1988) uses a Pascal subset
• AT-Robots by Ed T Toten (1992) uses assembly language
• Robocode by Mathew Nelson (2001) uses Java

Robocode is currently the most active. More information is available on the RoboWiki.

Please let me know if you think I've missed an important robot programming game or one of historical note. Also I'd love to hear from you if you have any memories of the above.

Five Computers I Longed to Possess in the 1980s

Back in the 1980's I owned a couple of computers, a Commodore 16 and a Spectrum +2. However, this didn't stop me wanting to own a whole range of other machines.

1. Jupiter Ace: I loved this from the moment I read about it. A Z80 based micro with a built in Forth interpreter, what more could I desire? Only about 9000 machines were manufactured and I've been waiting patiently ever since for one to come up on eBay.
2. Sam Coupé: a Sinclair Spectrum clone with 256K memory, a 6MHz Z80, optional internal disk drives and a 25MHz Z80 processor upgrade. Somewhere in the region of 12000 units were sold. A few years ago I picked up one of these at a car boot sale for a fiver! ;-)
3. NeXT Computer: from the moment I saw screenshots and read about this workstation built around Motorola's 68030 I knew I had to have one. After seeing the hefty price tag I knew I never would. Even now these sell for a small fortune on eBay.
4. Dragon 64: the Dragon's 6809 processor looked amazing compared to the 6502 used in most computers of the time. It boasted two stacks, plenty of registers and on chip multiplication. Whenever I wrote code for the 6502 I'd secretly hope to write for the 6809 one day.
5. KITT: a sentient, artificially intelligent computer built by Knight Industries and installed into a Pontiac Firebird Trans Am. Unfortunately my diecast model came without William Daniels' voice and the cool red lights. If KITT is ever on eBay I'll likely sell my house to buy it!

Let me know if you think I've missed off any cool machines :-)

Executable Compressors

An exe packer is a utility to reduce the size of executable files. It compresses a program and creates a new program with the compressed data and code to extract and run the original. Commonly used compression techniques include variants of Run Length Encoding and members of the LZ family of algorithms.

It's debatable whether there's still any real benefit to compressing exe files. Originally the reduced storage space would have been an advantage as would the slightly reduced disk (or even tape) load time. Nowadays the potential benefits are lower network bandwidth and smaller downloads.

Exe compressors present some interesting challenges for a programmer. The effectiveness of the compression has to be balanced against the size of the decompressor. The compression algorithm has to be chosen carefully for speedy decompression. If the program has a relocation table, what's the best way to optimise it? How can the additional memory requirements be minimised?

It shouldn't come as any surprise that hundreds of programmers have risen to the challenge and written an exe packer. A quick search of the net turns up at least 80 for DOS / Windows and several for other environments.

In 8086 assembly, a Run Length decoder for a DOS .COM file can be written in under 40 bytes and decoders for the simplest LZ77 derivatives in under 50 bytes. Here's an example RLE decoder:

; 8086 .COM RLE decoder

move:   ; copy unpacker and compressed
; code elsewhere in memory

mov si, unpack
mov di, freemem
mov cx, codeend-unpack
push di
rep movsb

; setup RLE paremeters

mov si, freemem+code-unpack
mov di, program
mov bx, num_of_tokens

; transfer control to unpack

ret

; unpack compressed program

unpack: push di
rle:    lodsb
cmp al, token
jne single
lodsw
mov cl,ah
db 0F3h ; rep
single: stosb
dec bx
jne rle

; transfer control to program

ret

code:   ; .....

codeend:

If you have any thoughts on the advantages / disadvantages of exe packers or any implementation ideas I'd love to hear them. Also does anyone know anything about the history of exe packers? The earliest I've found is from November 1987.

Implement MIN in Forth without Conditional Code

While lurking in the #forth channel on irc.freenode.net I was pointed to an interesting problem from the Gforth tutorial. The problem is to implement MIN in Forth without any conditionally executed code.

DO, LOOP, BEGIN, UNTIL, REPEAT, WHILE, IF, ELSE and THEN are all forbidden.  MIN removes the top two values from the data stack then puts the lower of the two back on.

Can you implement MIN under these conditions? If so I challenge you implement it in as few Forth words as possible! Let me know if your implementation is under 10 words :-)

BF Joust King of the Hill

BF Joust is a capture the flag programming game based on the esoteric Brainf*** programming language. Recently ais523 revised the language and enviroment, setting up a king of the hill tournament.

The game is played between two programs on a tape with a length randomly chosen between 10 and 30 cells. The cells initially contain 0 with the exception of the cells at either end which contain the flag 128.

Each program views the tape with their own flag on the left and the opponent's flag on the right. The object of the game is to find and set the opponents flag to 0 and keep it 0 for two consecutive cycles. If a program's pointer points to a location off the tape, it loses.

Here's a quick summary of the instruction set:

Op	Description
<	move the pointer to the left
>	move the pointer to the right
+	add 1 to the value stored at pointer
-	subtract 1 from the value stored at pointer
[	jump past the matching ] if the cell at pointer is 0
]	jump to instruction after matching [ unless cell at pointer is 0
.	no operation, do nothing

The interpreter also understands certain macros. Instructions inside parentheses are repeated a number of times. For example (>-)*4 expands to >->->->-.

For full details see the rules on the BF Joust Wiki page and check the current hill standings. To submit a program to the BF Joust hill, join the channel #esoteric on irc.freenode.net and send a message to egobot:

/msg egobot !bfjoust program_name program_code

It isn't possible to remove a program, but it can be replaced by submitting another with the same name.

Finally, I'll leave you with the code for shortsword the current king of the hill with 100% wins ;-)

(>++>--)*2(>)*6([-[+]]>)*20

The standings:

ID Score Pts Program
18 90.00  18 shortsword.bfjoust
19 71.12  12 stranger.bfjoust
16 69.75  11 scythe_impomatic.bfjoust
 1 59.38   9 ais523_attack5.bfjoust
 6 42.50   4 ais523_defend5.bfjoust
 2 41.50   6 ais523_attackslow.bfjoust
 7 38.00   2 asie1.bfjoust
 0 37.00   0 ais523_attack2.bfjoust
12 32.38  -1 fool1.bfjoust
 9 28.00   0 attack1.bfjoust
 4 18.25  -4 ais523_defend0_1.bfjoust
 3 16.25  -5 ais523_defend0.bfjoust
11 11.88  -9 ehirdomatic.bfjoust
10 10.50  -7 defend1.bfjoust
 5 10.50  -5 ais523_defend1.bfjoust
17  5.62  -4 shield.bfjoust
15  5.62  -9 programname.bfjoust
14  2.62 -10 nop.bfjoust
 8  2.62  -8 asie2.bfjoust
20  0.00   0 stuff.bfjoust
13  0.00   0 iwin.bfjoust

Let me know if you have any success with BF Joust.

CoreLife: Programming in 2 Dimensions!

For a while I've been promising to take a closer look at Dennis Luehring's list of programming games to select a few for further investigation. The list contains over 1500 links in 200 categories!

The first I've chosen is CoreLife, a 2D variant of Corewar by Brent Adams. CoreLife is one of the earliest 2D programming languages, predating Befunge by a few months.

Battles take place on a 100 × 100 memory grid. The outcome of a battle isn't uniquely determined by the initial conditions as there's a random element to the game.

Unfortunately, there's very little information about CoreLife strategies. There are 13 published battle programs. Most of these launch imps or bomb the grid with protected locations. Battle programs are often surrounded by a membrane or shield of protected locations. Despite this CoreLife has the potential to support more complex programs, for example replicators.

I've set myself the challenge of writing a replicator. First I'll attempt to write something linear and if that's successful, a square replicator! Has anyone experimented with CoreLife and if so, did you create a successful program or discover anything interesting?

For more information about programming games, take a look at Steven Robbins' list of programming games or Dennis Luehring's list of programming games.

The Recursive Universe by William Poundstone

In The Recursive Universe, William Poundstone uses Conway's Life as a vehicle to explore complexity theory and modern physics. Poundstone demonstrates how simple rules can produce complex results when applied recursively and suspects our own universe was created in a similar manner.

Conway's Game of Life was devised by John Conway in 1970. The Game of Life is played on a grid of square cells, each of which can be in one of two states, dead or alive. Three simple rules are applied repeatedly, first to the initial pattern, then to each new pattern in turn:

• a live cell with less than 2 neighbours dies
• a live cell with more than 3 neighbours dies
• a dead cell with 3 neighbours becomes a live cell

Each cell has eight neighbours, 2 horizontally, 2 vertically and 4 diagonally. Conway's Game of Life is also know as 23/3 Life. This indicate a live cell survives if it has 2 or 3 neighbours and a dead cell becomes live if it has 3 neighbours.

The Recursive Universe briefly explores some variations of Life, for example 34/34 Life. I'm currently experimenting with some other variations and will let you know the results shortly.

A Quick Look at a Programmer's Bookshelf

One of the best ways to get to know someone is to look at their bookshelf. -- Kathy Sierra

Here's a quick look at the programming section of the bookshelf next to my desk. It reflects my current interests pretty well:

• algorithms, Knuth and Introduction to Algorithms
• compilers, including the red and green dragon books
• operating system development
• artificial life
• assembly language, books on 68000, 8086 and 6809
• computer history, Hackers and Fire in the Valley
• web development

What's on your bookshelf?

Playing with the Arduino Microcontroller Board

Here are a couple of pictures of my latest toy, the Arduino Duemilanove microcontroller. It's equipped with 16K flash memory, 1K SRAM and 0.5K EEPROM and is currently sitting on my desk, flashing out "hello world" in Morse Code. The processor is an Atmel ATMega168 running at 16MHz.

Now I just need to learn the assembly language so I can implement something useful :-)

Hostile Programming on the BF Joust Hill

For the past couple of days I've been playing on the BF Joust Hill. BF (or Brainf***) is a simple programming language with 8 instructions as follows:

Op	Description
<	move pointer to the left
>	move pointer to the right
+	increment the value stored at pointer
-	decrement the value stored at pointer
[	jump past the matching ] if the cell at pointer is 0
]	jump to the matching [
,	character input (not used by BF Joust)
.	character output (not used by BF Joust)

The object of the game is to capture the flag. The size of memory is chosen at random in the range 135 - 167. Memory is initialise to 0. Both flags are set to 128. Your flag is at the far left end of memory, the opponent's flag is to the right.

The object is to set the opponent's flag to 0. If your flag is set to 0, or your pointer runs off either end of memory, you lose.

A simple strategy would be to keep moving right, setting any non-zero memory to 0:

[>[-]-]

Against the last 15 warriors on BF Joust, this scores 76. The maximum score is 300.

What would happen if we build a decoy to slow down the opponent? We could set a few non-zero memory cells next to the flag:

>+>->+>->+>->+>->+>-[>[-]-]

The new score is 103. Some memory cells are incremented to 1, others are decremented to -1 (255). It doesn't matter whether the opponent is using [-] or [+] to set memory to zero, it will be delayed for hundreds of cycles.

How can we avoid wasting time if the opponent has a similar decoy? One technique is to increment the memory cell just before entering the decrement loop:

>+>->+>->+>->+>->+>-[>+[-]-]

If there's a -1 decoy, it's changed to 0 and the [-] loop is never executed. The new code scores 140.

We can prevent the opponent from benefiting from a similar technique as follows:

>+++>--->+++>--->+++>--->+++>--->+++>---[>+[-]-]

This scores 181 :-)

Finally, we know the enemy's flag is in the memory range 135-167. We can quickly skip ahead to location 135:

>+++>--->+++>--->+++>--->+++>--->+++>---
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>
+[>+[-]-]

Scoring 209!

Rank             Program  TOT
-----------------------------
  1      woggle_050109_2  246
  2              joust12  240
  3      woggle_050109_1  228
  4      woggle_060109_3  213
* 5           Challenger  209
  6      wooble_231208_2  188
  7       ehird_060109_1  143
  8    BPilgrim_271208_1  132
  9      wooble_191208_1  130
 10      ais523_201208_1  121
 11       ehird_201208_4  103
 12    BPilgrim_271208_2   77
 13       ehird_191208_3   55
 14       comex_241208_1   46
 15       comex_241208_3   16
 16       comex_241208_2   16
-----------------------------

Let me know if you've discovered a better technique, or if you can beat 209.

Hello World for the RSSB Virtual Computer

The RSSB virtual computer has a single instruction, reverse subtract and skip if borrow. Each instruction has one operand, a pointer into memory. RSSB subtracts the accumulator from the contents of memory and the result is stored in both. If the accumulator was greater than the number in memory, the next instruction is skipped.

Jumps can be implemented by manipulating the instruction pointer at memory location 0, which normally requires 4 instructions. A conditional jump requires 6 instructions. Other special locations are as follows:

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

The four lines of code below demonstrate the shortest jump:

        rssb   acc       ; set acc to 0
        rssb   $+2       ; set acc to loop offset
        rssb   ip        ; subtract acc from ip
        rssb   $-loop    ; the loop offset

The code below implements hello world for the RSSB virtual computer. The sum deserves an explanation. Each character is subtracted from sum until sum passes zero, indicating all character have been printed. The final value of sum is the offset required by the conditional jump!

loop    rssb   acc       ; acc = character from ptr
ptr     rssb   hello        

        rssb   out       ; display character

        rssb   zero      ; acc = -acc

        rssb   zero      ; always skipped

        rssb   sum       ; subtract acc from sum

        rssb   ip        ; skipped if sum is <0
                         ; otherwise jump to 0

one     rssb   acc       ; subtract 1 from ptr
        rssb   one
        rssb   ptr

        rssb   acc       ; jump to loop
        rssb   loopoff
        rssb   ip
loopoff rssb   $-loop

sum     rssb   -1116

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

If you can improve the code above, or you've seen any other programs inplemented with RSSB, please leave a message below.

The Ultimate RISC, One Instruction Set Computers

A One Instruction Set Computer is a virtual computer designed to use only one instruction. There are two common methods to implement a OISC:

Reverse Subtract and Skip if Borrow

The instruction has one operand which points to a memory location. The program counter is stored at location 0 and the accumulator at location 1. Location 2 always contains zero, location 3 is used for input and location 4 for output.

RSSB subtracts the accumulator from the contents of a memory location, storing the result in both.  If the accumulator was greater than the memory location, the next instruction will be skipped. Jumps can be implemented by manipulating location 0.

Subtract and Branch if Negative

SBN requires three operands, a, b and c.  The contents of memory location a is subtracted from the contents of b and the result is stored in b. If the value originally stored in a was greater than the value in b, SBN will jump to c. A variation on the theme is Subtract and Branch unless Positive.

I'll publish my implementation in Redcode shortly. In the meantime, why not take a look at projects listed below. If you're aware of any other implementations, please leave a comment with the details.

• Luke Valenty built a SBN machine using 7400 series logic gates
  
• Clive Gifford has written a SUBLEQ self-interpreter
• Oleg Mazonka implemented a SUBLEQ interpreter in C++
• Safalra has designed a variation called MISC