Retro Programming

USB Stick Microcontroller Dev Boards

2011-12-29T15:16:00.000-08:00

A USB programmable microcontroller is a cheap and easy way to begin experimenting with microcontroller projects. I've recently been playing with 6 USB sticks which can be picked up for under £25 ($40) and discovered three I would recommend, the Micropendous, Minimus and eZ430. Have I missed your favourite USB stick based microcontroller?

Micropendous3

The Micropendous3 (top left) contains an ATMEL AVR AT90USB647 microcontroller with 64K flash, 2K EEPROM and 4K SRAM and allows access to the MCU's 48 I/O lines. The board also supports the AT90USB1287 with 128K flash, 4K EEPROM and 8K SRAM. Support and development software are available online.

Maximus AVR USB 1.2

Despite it's name the Maximus AVR 1.2 (top right) is based on Microchip Technology's PIC18F4550 microcontroller with 32K flash, 2K SRAM and 256 bytes EEPROM. Unfortunately the board layout doesn't allow access to the MCU pins.

Minimus AVR USB 32K

The Minimus 32K (middle left) uses ATMEL's ATMEGA32U2 with 32K flash, 1K EEPROM and 1K SRAM. The board allows access to the MCU's 22 I/O lines. Development software is available online.

eZ430-F2013

Texas Instrument's eZ430-F2013 (middle right) has a detachable target board containing a MSP430F2013 microcontroller with 2K flash and 128 bytes SRAM. The board allows access to all MCU pins. The eZ430 is supplied with development tools for Windows and support is readily available online. The instruction set is easy to learn with just 27 instructions and 4 addressing modes.

Maximus AVR USB 1.0

The Maximus AVR 1.0 (bottom left) is based on the ATMEL AT90USB162 microcontroller with 16K flash, 512 bytes EEPROM and 512 bytes SRAM. As with the later version, the layout doesn't allow access to the MCU pins.

µRlink ST7Ultralite Primer v1.1

The ST7Ultralite (bottom right) is a board based on ST's 8-bit ST7FLITEUS microcontroller with 1K flash and 128 bytes EEPROM. The slightly odd looking board features a light sensor and buzzer and is supplied with a development environment for Windows. Unfortunately the IDE refused to install and there's little information online.

A Bibliography of Programming Games

2011-11-06T11:50:00.000-08:00

The Programming Games Bibliography is an attempt to compile a complete list of articles / papers on the subject. A Programming Game is played by writing programs to compete against each other, typically by attempting to disable opponents in the memory of a virtual computer or by controlling simulated battle robots.

Please help complete the list by leaving a comment if you remember an article not listed, even if you can only recall vague details. :-)

Bibliography

Vyssotsky, Victor A. Darwin: A Game of Survival and (Hopefully) Evolution.
New Jersey: Bell Telephone Laboratories, 1961.
ℵ₀ "Computer Recreations: Darwin."
Software: Practice and Experience 2 (Jan-Mar 1972): 93-96.
Edmunds, William "Robotwar: A Wargame for All Programmers."
Computer Gaming World (Nov-Dec 1981): 13-16,33.
"Computer Gaming World's Robotwar Tournament."
Computer Gaming World (Nov-Dec 1981): 17.
Feigel, Curtis "Robotwar."
BYTE (Dec 1981): 24-34.
"Robotwar: Tournament Results."
Computer Gaming World (Mar-Apr 1983): 30-31.
Hoffman, Paul S. "Robots Maneuver Humans Into Programming."
The Rainbow (Apr 1983): 140-142.
Calle, Carlos "Robot Battle."
HOT CoCo (Sep 1983): 53-54.
"We Have a Draw! Robotwar Tournament Results."
Computer Gaming World (Apr 1984): 36.
Dewdney, A. K. "Computer Recreations: In a game called core war hostile programs engage in a battle of bits."
Scientific American (May 1984): 14–22.
"4th Annual Robotwar Tournament."
Computer Gaming World (Jan 1985): 9.
Dewdney, A. K. "Computer Recreations: A Core War bestiary of viruses, worms and other threats to computer memories."
Scientific American (Mar 1985): 14-23.
"Nobody Wins 4th Annual CGW Robotwar Tournament."
Computer Gaming World (Jun-Jul 1985): 9.
Martínez Lara, Sergio "Batcode, una auténtica batalla dentro de tu ordenador."
MICROHOBBY 70 (18-24 Mar 1986): 22-23.
Martínez Lara, Sergio "Batcode, una auténtica batalla dentro de tu ordenador (II)."
MICROHOBBY 71 (25 Mar - 1 Apr 1986): 28-30.
Martínez Lara, Sergio "Batcode (III)."
MICROHOBBY 73 (8-14 Apr 1986): 28-29.
Martínez Lara, Sergio "Batcode, una batalla dentro de tu ordenador (y IV)."
MICROHOBBY 74 (15-21 Apr 1986): 28-29.
Eliraz, Ziv "Core Wars."
Dragon User (Sep 1986): 16-21.
Dewdney, A. K. "Computer Recreations: A program called MICE nibbles its way to victory at the first Core War tournament."
Scientific American (Jan 1987): 14-20.
Edgar, Gerald A. "Darwin: A survival game for programmers."
Computer Language (Apr 1987): 79-86.
de Weger, Mark "Battle of the RAM."
The Micro User (Jan 1988): 42-43.
de Weger, Mark "The program strikes back."
The Micro User (Feb 1988): 52-54.
Dewdney, A. K. "Computer Recreations: Of worms, viruses and Core War."
Scientific American (Mar 1989): 110-113.

Darwin: Celebrating 50 Years of Programming Games

2011-07-08T01:38:00.000-07:00

Darwin was the earliest programming game, invented by Victor Vyssotsky in August 1961. The idea of the game was to write a program to out-replicate and disable all opponents.

Each program had a number of protected locations and interacted via three functions:

PROBE - return the start, end and owner of a memory block
CLAIM - reserve memory
KILL - disable a program

If a protected location was PROBEd the current program lost control. A CLAIM or KILL could only be used on a location which had previously been PROBEd.

Douglas McIlroy coded Darwin on Bell Labs' IBM 7090 and the game slowly progressed until an unbeatable program emerged, designed by Robert Morris.

Robert's program used an adaptive search. If the program PROBEd an opponent and lost control it would avoid reusing the same offset. A successful offset would be stored then used for future PROBEs and to initialise new copies of itself. Robert's program adapted to become a specialist killer.

In 1972 ℵ₀ (Aleph-Null) published the rules of Darwin in Software Practice and Experience, inspiring a number of new implementations. In 1987 Gerald Edgar published his 8080 version to accompany an article in Computer Language.

Unfortunately Darwin faced a major problem. Programs were written in machine language and could only compete against others written for the same computer. When A. K. Dewdney introduced Core War in 1984 he addressed the limitation by defining the MARS virtual computer and Redcode, a simplified assembly language.

Although Darwin has been consigned to the history book, I'll never grow tired of reading about it! Do you remember playing Darwin? If so, I'd love to hear the details.

References

ℵ₀ "Computer Recreations: Darwin"
Software: Practice and Experience 2 (Jan-Mar 1972): 93-96.
Dewdney, A. K. "In a game called core war hostile programs engage in a battle of bits" Scientific American 250 (May 1984): 14–22.
Edgar, Gerald A. "Darwin: A survival game for programmers."
Computer Language (Apr 1987): 79-86.
Levy, Steven Artificial Life: The Quest for a New Creation.
New York: Pantheon Books, 1992. 317-319.
Vyssotsky, Victor A. Darwin: A Game of Survival and (Hopefully) Evolution.
New Jersey: Bell Telephone Laboratories, 1961.

Computus: Calculating Easter Sunday

2011-04-22T04:04:00.000-07:00

Computus is the algorithm used to calculate the date of Easter. Easter Sunday falls on the first Sunday after the full moon following the Spring equinox. For the purpose of the calculation the full moon is defined as day 14 of the lunar month and the Spring equinox as 20th March.

Unfortunately Computus defies any attempt to render it with beautiful code! This C function roughly follows the assembly language so is a little uglier than strictly necessary:

easter(year, month, date)
int year, *month, *date;
{
    int gold,cent,sa,la,epact,a18,da;
    gold = year%19;
    cent = year/100;
    sa = cent-cent/4;
    la = (8*cent+13)/25;
    epact = (19*gold-sa-la+15)%30;
    a18 = (gold+11*epact)/319;
    da = ((cent%4+year%100/4)*2+a18+32-year%4-epact)%7;
    *month = (90+epact+da-a18)/25;
    *date = (*month+19+epact+da-a18)%32;
}

The algorithm is similar to MaybeGauss1 found in J R Stockton's collection of algorithms for Easter Sunday and is valid for the Gregorian calendar well into the fourth millenium. The algorithm can be adapted to calculate a number of other dates:

Shrove Tuesday - 47 days before Easter Sunday
First Sunday in Lent - 42 days before
Palm Sunday - 7 days before
Whit Sunday - 49 days after

Finally here's the same algorithm in 8086 assembly language, length 128 bytes. On entry, AX is the year. On exit AL is the day, AH is the month:

easter:
  push cx
  push dx
  push bx
  push bp
  push si
  push di

  mov bp,ax     ; bp = year (1583:3999) 

  mov cx,100
  cwd
  div cx
  push dx
  xchg si,ax    ; si = century - 1

  mov ax,bp
  mov cl,19
  cwd           
  div cx
  mov bx,dx     ; bx = golden number - 1
  xchg ax,dx

  mul cl
  add ax,15
                ; ax in range (15:357)
  mov dx,si
  add ax,si
  shr dx,1
  shr dx,1
  sub ax,dx
  push ax
  mov ax,8
  mul si
  add ax,13
  mov cl,25
  div cx                      
  xchg dx,ax
  pop ax
  sub ax,dx
  mov cl,30
  cwd
  div cx
  mov di,dx

  mov al,11
  mul dx
  add ax,bx
  mov cl,206    ; multiply by 206 and discard the
  mul cx        ; lower 16 bits of the result.
                ; shorter than dividing by 319

  sub di,dx
  xchg ax,si
  and al,3 
  pop dx
  shr dx,1
  shr dx,1
  add ax,dx
  shl ax,1
  and bp,3
  lea bp,[bp+di-32]
  sub ax,bp
  mov cl,7
  cwd
  div cx
  xchg ax,dx
  add ax,di
  mov bp,ax
  add al,90
  mov cl,25
  div cl
  mov ah,al
  add al,19
  add ax,bp
  and al,31

  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop cx
  ret

Itsy-OS Kernel: Preemptive Switcher & Memory Manager

2011-03-30T13:04:00.000-07:00

Itsy-OS v0.1 is a small 8086 operating system kernel providing two basic services: a simple preemptive task switcher and memory management. If necessary, simple IPC and task management can be added to provide the features of a traditional microkernel.

Weighing in at about 380 bytes, Itsy should port well to tiny architectures.

Memory Control Blocks

Each block of memory is preceded by a memory control block which is 32 bytes long. The blocks of memory are arranged as a circular linked list. The first memory control block resides in segment 050h.

org 0h
; -----------------------------
; [Master Memory Control Block]
; -----------------------------

M_NEXT:dw 0             ; address of next MCB
M_LAST:dw 0             ; address of previous MCB
M_PARA:dw 0             ; size of this block in paragraphs including MCB
M_FLAG:db 0             ; flags
       db 0             ;
M_NPRO:dw 0             ; next MCB containing process, zero if not in queue
M_LPRO:dw 0             ; previous MCB containing process, or zero
M_STKP:dw 0             ; stack pointer
M_STKS:dw 0             ; stack segment

M_TIME:dw 0             ; time allocated / de-allocated
M_DATE:dw 0             ; date allocated / de-allocated
M_OWNR:dw 0             ; user number who owns this memory
M_NAME:db '          '  ; name of this memory block

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

; flag bits
F_FREE equ 01h          ; zero if this is free memory
F_ACTI equ 02h          ; zero if no task ready for CPU

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

  jmp E_INIT            ; setup kernel

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

; -------------------
; [Nucleus Data Area]
; -------------------

D_PCP:dw 0              ; segment of current process's MCB
D_SWEN:db 0             ; set to zero when switching disabled

Task Switcher

The task switcher is called by the timer interrupt. First it checks whether switching is disabled. If not:

disable switching
save the registers of the current task on the stack
save the stack pointer of the current task in it's MCB
find the next MCB with an available task
restore the new task's stack pointer and registers
enable switching and transfer control to the new task

; ---------------
; [Task Switcher]
; ---------------

E_SWITCHER:
; test if the switcher is enabled or disabled (indivisible test and set)
  pushf
  push cx
  xor cx,cx
  cs xchg cl,byte[D_SWEN]
  jcxz N_NOSWITCH

; save the registers of the current process
  push ax
  push dx
  push bx
  push bp
  push si
  push di
  push es
  push ds

; save the stack of the current process
  mov di,M_STKP
  cs mov ds,word[di+D_PCP-M_STKP]
  mov word[di],sp     ; M_STKP
  mov word[di+2],ss   ; M_STKS


E_SHORTCUT:

; select an active task to switch to
N_SELTASK:
  mov ds,word[di-4]        ; M_NPRO
  test byte[di-6],F_ACTI   ; M_FLAG
  jz N_SELTASK             ; is this task active?
  cs mov word[di+D_PCP-M_STKP],ds

; restore saved state of process being switched to
  mov sp,word[di]          ; M_STKP
  mov ss,word[di+2]        ; M_STKS
  pop ds
  pop es
  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop ax
  call E_ENABLE
N_NOSWITCH:
  pop cx
  popf
  iret

Deallocate Memory

Called with DS = MCB of memory to free. Deallocated memory is wiped with 0CCh.

Switching is disabled while the memory structure is being modified. If the memory being deallocated contains a process, it is removed from the process queue. If adjacent memory blocks are marked as free, the blocks are combined.

; -------------------
; [deallocate memory]
; -------------------

E_MEMDEALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di                   ; M_NEXT
  mov ax,word[di+M_NPRO]      ; see if there is entry in process queue
  test ax,ax
  jz N_NOPROC                 ; if there isn't, simply free the memory
  mov es,word[di+M_LPRO]      ; and if there is, remove it!
  es mov word[di+M_NPRO],ax
  mov bx,es
  mov es,ax
  es mov word[di+M_LPRO],bx

  mov ax,ds
  cs cmp ax,word[D_PCP]       ; check if process being killed is the current
  jnz N_NOPROC
  cs mov word[D_PCP],bx       ; if so, set last process as current

  call N_NOPROC               ; free the memory,
  mov di,M_STKP
  jmp short E_SHORTCUT        ; and then afterwards, switch to another task


N_NOPROC:
  mov bp,ds                   ; bp = first paragraph to clear
  mov bx,word[di+M_PARA]      ; bx = number of paragraphs to clear

  mov es,word[di]
  es test byte[di+M_FLAG],F_FREE        ; is next block free?
  jnz N_NNOTJOIN                        ; if not, can't join them

  es mov ax,word[di+M_PARA]             ; get size of next block
  add word[di+M_PARA],ax                ; add to size of this block
  es mov ax,word[di]                    ; move M_NEXT of next...
  mov word[di],ax                       ;  ...to M_NEXT of current
  inc bx                                ; an extra 2 paragraphs to clear
  inc bx
N_NNOTJOIN:
  and byte[di+M_FLAG],0FFh-F_FREE-F_ACTI       ; mark as free

  mov es,word[di+M_LAST]
  es test byte[di+M_FLAG],F_FREE        ; is previous block free?
  jnz N_PNOTJOIN                        ; if not, can't join them

  mov ax,word[di+M_PARA]                ; get size of this block
  es add word[di+M_PARA],ax             ; add to size of previous block
  mov ax,word[di]                       ; move M_NEXT of current...
  es mov word[di],ax                    ;  ... to M_NEXT of previous
  jmp short N_EXTRA2P
                                        ; block already marked as free
N_PNOTJOIN:
  inc bp              ; don't clear MCB
  inc bp
  dec bx
  dec bx

N_EXTRA2P:
  cld                 ; clear memory - bp=location, bx=paragraphs
  mov ax,0CCCCh       ; code for an INT3 instruction to fill memory with
  mov dx,01000h
N_CLRGO:
  mov es,bp
  sub bx,dx
  jc N_CLRFIN
  mov cx,08000h
  rep stosw
  add bp,dx
  jmp short N_CLRGO

N_CLRFIN:
  add bx,dx
  mov cl,3
  shl bx,cl
  mov cx,bx
  rep stosw

E_ENABLE:
  cs inc byte[D_SWEN] ; enable switching
  ret

Allocate Memory

Called with AX = number of paragraphs required. Returns DS = location of memory, or DS = 0 if no memory available. Switching is disabled while the memory structure is being modified. Allocation uses a simple best fit algorithm.

; -----------------
; [allocate memory]
; -----------------

E_MEMALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di
  xor dx,dx                    ; segment of current choice
  xor cx,cx                    ; left-over memory from current choice
  inc ax
  inc ax
  mov bx,050                   ; MMCB

N_MOREMEM:
  mov ds,bx
  test byte[di+M_FLAG],F_FREE  ; is the block we are looking at empty?
  jnz N_WONTFIT                ; if it isn't, move on

  mov bx,word[di+M_PARA]
  sub bx,ax                    ; check size
  jc N_WONTFIT
  jz N_EXACT                   ; perfect fit :-)

; ** KLUDGE ***
  cmp bx,3                     ; if leftover memory block smaller than 3
  jc N_WONTFIT                 ; paragraphs, it would be too small to contain
                               ; a MCB.  Maybe handle this better later

  cmp cx,bx                    ; bx= size of potential leftover memory block
  jc N_WONTFIT                 ; have we found a better fit?
  mov cx,bx
  mov dx,ds                    ; if so, then select it!
N_WONTFIT:
  mov bx,word[di]              ; M_NEXT
  cmp bx,050                   ; are we at MMCB?
  jnz N_MOREMEM

  test dx,dx
  jne N_ALLOCIT
  mov ds,dx                   ; out of memory :-(
  jmp short N_ALEXIT
N_ALLOCIT:
  mov ds,dx
  mov es,word[di]              ; M_NEXT, es= next block

  mov bx,word[di+M_PARA]       ; bx= number of paragraphs for this block
  add bx,dx                    ; bx= end of this block
  sub bx,ax                    ; bx= location of new block's MCB        

  es mov word[di+M_LAST],bx    ; point next block to new block
  mov word[di],bx              ; M_NEXT, point this block to new block
  sub word[di+M_PARA],ax       ; resize this block
  push ds
  mov ds,bx                    ; point es to new block
  pop bx

  mov word[di+M_LAST],bx       ; initialise new block's M_LAST
  mov word[di+M_PARA],ax       ; initialise new block's M_PARA
  mov word[di],es              ; initialise new block's M_NEXT

N_EXACT:
  mov byte[di+M_FLAG],F_FREE   ; mark new block as no longer free
  mov word[di+M_NPRO],di
  mov word[di+M_LPRO],di
N_ALEXIT:
  jmp short E_ENABLE

Setup

Simply sets up the timer interrupt.

E_INT1C:
  call E_SWITCHER
  db 0EAh
D_OLDINT1C:
  dw 0,0

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

E_INIT:
  push cs
  pop es
  xor ax,ax
  mov ds,ax
  mov si,01Ch*4
  mov di,D_OLDINT1C
  cld
  push si
  movsw
  movsw
  pop di
  cli
  push ds
  pop es
  mov ax,050h
  stosw
  mov ax,E_INT1C
  stosw
  sti
; ...

Alternatives to Windows Notepad for Programmers

2011-03-17T03:37:00.000-07:00

When I upgraded to Windows 7 I was horrified to discover the text editor I've been using for years no longer works. After suffering Windows Notepad for a few days I set out on a quest to discover the perfect replacement.

My search criteria is pretty basic:

can be installed on a memory stick
works with UNIX / DOS end-of-line
supports syntax highlighting
the ability to edit multiple files
supports regular expression search
requires less than 10MB disk space

After testing a number of free programmer's editors I discovered several which meet (or almost meet) the requirements:

ConTEXT is a free programmer's text editor. It boasts a number of useful features include the ability to export code to HTML.

(The thumbnail links to a 800×560px screenshot.)

Crimson is a source code editor to replace Windows Notepad. Unfortunately the default colour scheme for syntax highlighting doesn't really distinguish between text, delimiters and constants.

gedit is the text editor from the GNOME desktop enviroment and is also available for Windows. Unfortunately the standard package lacks regex search and it's a heavyweight, weighing in at 65MB+.

jEdit is a Java programmer's text editor and has an active community of developers. Hundreds of plugins are available to add a wide range of features. jEdit is another heavyweight, consuming 25MB+ of diskspace.

Notepad++ is a replacement for Windows Notepad. Features include code folding and support for numerous plugins developed by Notepad++'s active community.

Notepad2 is a replacement for Windows Notepad that only installs two files. It features a semi-transparent mode allowing users to keep an eye on other programs while editing full screen. Unfortunately Notepad2 can only edit one file at once.

Programmer's Notepad is a programmer's editor with features including code folding, exporting code to HTML and Python scripting. Programmer's Notepad has an active user community.

PSPad is a free programmer's editor. The font selector only shows fixed width fonts which is handy, but I'd like to have the option to use a proportional font. PSPad has a feature to export code to HTML. Requires just over 14MB of disk space.

SciTE is the demo for the free Scintilla code editing component (used by several editors listed here) and is available as a single file installation. Supports code folding and exporting code to HTML. Unfortunately changing the settings requires the user to poke around in SciTE's config files.

In the end I've settled for Programmer's Notepad. Which editor are you using and what features do you consider essential? :-)

Efficiency in Forth

2011-03-13T12:10:00.000-07:00

I'm busy implementing my own Forth at the moment and it's taking a little longer than anticipated. Each Forth word is a puzzle in itself:

What's the least number of words needed to write it?
What's the most efficient implementation?

For example, take a look at Implementing MIN in Forth without Conditional Code. The smallest version of MIN is 2 words shorter than eForth's MIN.

Even words with a trivial implementation can pose an interesting problem. For example which of the following is most efficient:

Jones Forth TUCK

: TUCK DUP -ROT ;

Alternative TUCK

: TUCK SWAP OVER ;

If DUP, -ROT, SWAP and OVER are all primitive, the alternative implementation will execute two fewer instructions on an 80x86 Forth. However, -ROT is often implemented in Forth which would cause the Jones Forth TUCK to be substantially slower. Here's a typical implementation of -ROT:

: -ROT SWAP >R SWAP R> ;

If you can think of an alternative two word implementation of TUCK or four word implementation of -ROT, please let me know. :-)

The Tao of Programming

2011-02-12T03:25:00.000-08:00

The Tao of Programming by Geoffrey James is a short book of humourous computer parables inspired by an ancient Chinese text, the Tao Te Ching.

The Tao Te Ching is believed to have been written 2500 years ago by Lao Tzu and provides the basis for Taoist philosophy. The book is separated into 81 (3⁴) short chapters of parables and proverbs.

James divides The Tao of Programming into 32 (2⁵) chapters, a mix of tales paraphrased from the Tao Te Ching and anecdotes advocating the key principles of the hacker ethic:

code should be small, elegant and easy to read
management shouldn't interfere with programming

The preface (not included in the online copy) describes how James, an amateur computer archaeologist, stumbled upon and decoded The Tao of Programming while searching through a stack of obsolete punch cards.

My favourite chapter has to be the description of well-written programs closely followed by Turing's dream:

“A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity.”

-- The Tao of Programming, Chapter 4.1

“Grand Master Turing once dreamed that he was a machine. When he awoke he exclaimed:

‘I don't know whether I am Turing dreaming that I am a machine, or a machine dreaming that I am Turing!’”

-- The Tao of Programming, Chapter 2.2

Although the book is short and you probably won't learn anything new, it's definitely worth a read if you have 30 minutes to spare.

Online copy of The Tao of Programming

Celebrating 30 Years of Color Robot Battle

2011-02-02T22:40:00.000-08:00

Color Robot Battle is one of the earliest commercial programming games, published 30 years ago for the TRS-80 Color Computer by The Image Producers.

The game is played by writing programs to control a robot's movement, sensors and weapons. Programs are written in a hybrid of the BASIC / Logo programming languages. Two robots enter an arena with the survivor being declared the winner.

I asked the designer and programmer of Color Robot Battle what inspired the game:

“Well, the Apple II program did along with the feeling I could do it better. All of these were initially inspired by Core Wars, I believe. I did want to make the language complete enough to have quite a bit of control and flexibility over the robots.”

-- Glenn Sogge

“The robot controlling programming language was based on BASIC. Prior to working on CRB, I'd written a simple BASIC interpreter for the PDP-11, so it was a natural choice.”

-- Del Ogren

Color Robot Battle is a fantastic example of compact code. The game, compiler and full screen editor are all written in 6809 assembly language and somehow manage to fit on a 4K ROM.

Although the language of CRB only takes a few minutes to learn, a whole range of strategies are possible. There are four types of command available:

movement: followed by a number. Movement commands are F(orwards), B(ackwards), L(eft), R(ight), H(alt), T(urn), D(irection).
conditional: detect what the robot is facing. =(true) or #(false) followed by R(obot), W(all), M(issile), L(aser), S(omething - any direction), ?(random).
flow control: C(all) or G(oto) a label. Labels are defined at the beginning of a line and terminated by a >.
attack: XL to fire the laser or XM to fire a missile.

The program starts at the label START>. Multiple commands on one line are separated by a colon :. If a condition fails the rest of the line is skipped.

Here's a simple example that manages to win a few battles:

*SIMPLE              ; robot name
START>               ; start here
F5                   ; move forward 5
=W:T1                ; if facing a wall, turn 45°                
=?:T1                ; randomly turn 45°
=R:XL                ; if facing a robot, fire laser
GSTART               ; repeat from start

Thanks to the simplicity of the language, CRB makes the perfect introduction to programming games. So, does anyone fancy a tournament? ;-)

Interactive Fiction: 4K Adventure

2011-01-30T00:30:00.000-08:00

I've always been a fan of text adventures - exploring a fantasy world, drawing a map and solving a few puzzles along the way. A couple of my early favourites were The Hobbit and Heroes of Khan. When I discovered shareware I spent hours puzzling over Humbug, Curses and t-zero. Even now I'm still working through The Lost Treasures of Infocom :-)

So when I needed a project to exercise my new 8086 assembly skills a text adventure seemed the natural choice. I decided to cram as much as possible into a 4K program - verb-noun parser, text decompression and a snowy forest to explore.

After 35 hours coding I'd created 4K Adventure complete with dwarves, mischievous elves and stolen magic. It managed to work despite the spaghetti code and a couple of dubious algorithms!

Impressed that I'd actually completed a project I immediately started work on a sequel and a simple operating system... I still haven't completed either. Maybe one day ;-)

4K Adventure is available to download from The Interactive Fiction Archive and runs perfectly using DOSBox.

CoreLife: Artificial Life Simulator

2011-01-27T13:17:00.000-08:00

A few years ago when using either Lycos or the WWWW (remember those?) to search for CoreLife I came across a program with the same name. The program I discovered is an artificial life simulator written by Erik de Neve.

CoreLife supports two VCPUs:

The CoreLife VCPU - supports 32 instructions that resemble 8086 assembly
The Tierra VCPU - supports the 32 instructions of Thomas Ray's software

After seeding memory with a handwritten organism the simulation begins. Each organism attempts to replicate while the simulator randomly mutates instructions or causes them to fail. Thanks to the mutation the copied organism often differs slightly from the parent.

In some cases the mutation renders the child organism less effective or too damaged to replicate. In other cases the child is smaller and faster, able to out-replicate the less efficient parent.

Watching the code evolve made me wonder if I could beat evolution. I set myself a challenge: could I create the ultimate organism to out-replicate everything else and resist mutation?

Unfortunately any attempt to resist mutation quickly died out so I settled for creating the smallest self-contained replicator, just 22 instructions:

;22 Instruction Replicator
;for the Tierra Virtual CPU
nop_1
adrb
nop_0
push ax
sub_ac
divide
mov_ab
adrf
nop_1
sub_ab
inc cx
mal
nop_1
dec cx
mov_ii
ifz
ret
inc bx
inc ax
jmpb
nop_0
pop dx

CoreLife is available on Erik de Neve's webpage and runs perfectly using DOSBox.

Recursion via Pascal

2011-01-12T14:37:00.000-08:00

Recursion via Pascal by J. S. Rohl is one of a small number of books devoted entirely to recursion in programming. Recursion is a technique where a problem is defined in terms of a simpler version of itself.

The book has over 100 examples and although the code is in Pascal it shouldn't pose too much of a problem for C / Java programmers.

Factorials are the classic example of recursion:

The factorial of a number n (written as n!) is the product of all positive integers below or equal to n.

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720.

n! can be defined recursively as:

0! = 1
n! = n × (n-1)!

Here's the code to calculate factorials in Pascal:

function factorial( n:integer ):integer;
begin
    if n = 0 then
        factorial := 1
    else
        factorial := n * factorial( n-1 )
end

Or in C:

unsigned int factorial( unsigned int n )
{
    if ( n == 0 )
        return 1;
    else
        return n * factorial( n-1 );
}

Or Forth:

: factorial
    dup 0= if
        drop 1
    else
        dup 1- recurse *
    then
;

Rohl first examines some simple examples of recusion: factorials, highest common factor and displaying numbers before moving on to more advanced topics:

two-level procedures
recursive data structures
binary recursion
recursive sorting algorithms
mutual recusion

Throughout the book Rohl compares the runtime / complexity to the equivalent iterative code and warns against any potential pitfalls. My favourite example is the code to calculate x^n from “developing the power example, a cautionary tale”:

function p(x:real; n:integer):real;
begin
  if n = 0 then
    p := 1
  else if odd(n) then
    p := p( x, n div 2 ) * p( x, n div 2 ) * x
  else
    p := p( x, n div 2 ) * p( x, n div 2 )
end

Thanks to a small oversight the order of complexity is Ο(n) instead of Ο(log n).

Recursion via Pascal was published in 1984 but remains relevant despite it's age. The text is easy to follow and I'd recommend the book to anyone curious enough to delve further into recursion :-)

#CarolsInCode - Top Five Countdown

2010-12-23T14:36:00.000-08:00

#CarolsInCode is a programming meme with a seasonal twist. Short programs are used to encode the lyrics of a Christmas carol. Some display the lyrics when the program runs while the more ingenious examples define the song with the program's control structures.

For example in JavaScript:

while ( shepherds.watch() == 'flocks' &&
  date.getHours() in night )
{
  lord.angel--;
  glory.shone_around();
}

This is While Shepherds Watched Their Flocks by Nahum Tate:

“While Shepherds watch their flocks by night,
All seated on the ground,
The angel of the Lord came down,
And glory shone around.”

Here's the top five countdown of the very best #CarolsInCode. Can you identify all five? Is your favourite missing?

GrumpyWookie:

Weather.Outside="frightful";
Fire.Delightful=true;
Lights.Luminosity=WayDownLow;
for (int i=1; i<=3; i++) { LetItSnow(); }

ShinyEmptyHead:

public Sleigh sleigh;
public void dashThroughSnow()
{
int horses = 1;
sleigh = new Sleigh(horses);
for (Field field : fields)
{
laugh();
}
}

JohnGirvin:

var wenceslas = new Person({
    rank: 'king',
    alignment: 'good'
});
$.bind(FeastOfStephen, function() {
    wenceslas.lookOut();
});

Costall:

if (DateTime.Now()=="25/12/2010")
{
for (i=0;i<3;i++) Ship[i].Visibility = Visibility.Visible;
}

GrumpyWookie:

Kiss.PersonA="Mummy";
Kiss.PersonB="Santa";
Kiss.Witness=Me;
Kiss.Location=Mistletoe.Underneath;
Kiss.Time=Date.LastNight;

More #CarolsInCode

#carolsincode - Christmas for Programmers

2010-12-17T11:29:00.000-08:00

#carolsincode are small pseudo-programs which contain a Christmas song. Some examples display the lyrics while others use the program's control structures to define the song.

Here are five examples in C, CSS and JavaScript. Can you do better? ;-)

var kings=new Array(3);
for (x in kings)
{
  kings[x].origin='orient';
  kings[x].bearingGift=true;
  kings[x].travelled='afar';
}

main() {
  int a;
  for (a=1;a<5;a++) printf("Noel, ");
  printf("Born is the King of Israel.");
}

#rudolf .nose {
  color: red;
  background: url('very_shiny.jpg');
}

while ( shepherds.watch() == 'flocks' &&
  date.getHours() in night )
{
  lord.angel--;
  glory.shone_around();
}

for ( c=1, c<=4, c++)
{
  noel()
};
king = new Object();
king.kingdom = 'Israel';

Programming Contest: Topswaps

2010-12-06T03:40:00.001-08:00

Al Zimmermann's latest programming challenge asks up to arrange a deck of n cards numbered 1 .. n to maximise the number of swaps. Each swap looks at the value x on the top card and reverses the top x cards.

For n=4 the sequence 3, 1, 4, 2 requires 4 swaps:

Al challenges us to find the best solution for the first 25 primes, n=2, 3, 5 .. 97. Even a simple program which tests random combinations can throw out some reasonable scores:

10 rem setup array
20 input z
30 dim x(z)
40 for a=1 to z
50 x(a)=a
60 next a
70 h=0

100 rem shuffle array
110 for a=1 to z
120 r=int(rnd*z+1)
130 t=x(a)
140 x(a)=x(r)
150 x(r)=t
160 next a

200 rem remember order
210 a$=""
220 for a=1 to z
230 a$=a$+","+str$(x(a))
240 next a

300 rem swap until done
310 c=0

400 q=x(1)
410 for a=1 to int(q/2)
420 t=x(a)
430 x(a)=x(q+1-a)
440 x(q+1-a)=t
450 next a

500 c=c+1
510 if x(1)>1 then goto 400

600 rem display highscore
610 if c>h then h=c:print c;" : ";a$
620 goto 100

Are you planning to take part in the contest?

URISC / OISC: One Instruction Computers

2010-10-08T12:32:00.000-07:00

URISC is an abstract computer designed to have a minimal instruction set, only one instruction. URISC is an abbreviation of Ultimate RISC, although technically the machine doesn’t meet the criteria for RISC.

Types of URISC

There are four common types of URISC – MOV, RSSB, SUBLEQ and SUBNEG.

MOV – Transport Triggered Architecture

In a MOV URISC machine there's one instruction with two operands. When the instruction executes, it copies one location in memory to another, using the operands as pointers. Jumps, arithmetic and input / output are achieve with a memory mapped program counter, arithmetic unit and input / output ports.

More information about MOV TTA:

Transport Triggered Architecture

RSSB – Reverse Subtract and Skip if Borrow

The instruction in a RSSB URISC machine is Reverse Subtract and Skip if Borrow. Each instruction has one operand which is a pointer into memory. When the instruction executes, it subtracts the accumulator from a memory location and stores the result in both. If the value in memory was lower than the accumulator, the next instruction will be skipped. The program counter, accumulator and input / output are mapped to memory.

More information about RSSB:

SUBNEG – Subtract and Branch if Negative

Also abbreviated to SBN, a SUBNEG computer uses an instruction with three operands. When executed, SUBNEG subtracts the contents of the first memory location from a second location, storing the result in the second. If the first value was higher than the second, SUBNEG jumps to where the third operand points. Input / output are memory mapped.

More information about SUBNEG:

A SBN Computer Built from 74xx Gates

SUBLEQ – Subtract and Branch if Less than or Equal

SUBLEQ is similar to a SUBNEG computer, but also branches if the contents of the two memory locations is identical.

More information about SUBLEQ:

Other Types of OISC

There have been several attempts to simplify OISC even further. Here are a couple of examples:

Core War - The King of Programming Games

2010-10-05T01:56:00.000-07:00

The aim of a programming game is to write a short program that competes towards a goal, usually destroying all opponents or capturing a flag.

There are two main types of programming game:

games inspired by RobotWar - programs control a battle robot which moves around an arena firing at opponents – RobotWar was created in the 1970s.
games inspired by Darwin - programs attempt to modify and crash the opponent's program. Darwin was first played at Bell Labs in 1961.

Both games have spawned a series of clones, the most popular being CRobots (1985) and Core War (1984).

In Core War players write programs in Redcode, the assembly language of the MARS virtual computer. The aim of the game is to survive while causing all opponents to terminate. There are three basic strategies:

paper - programs spawn off new copies in the hope at least one survives.
scissors - programs search for opponents and attempt to disable them.
stone - programs drops instructions at random hoping to hit the opponent.

A couple of years after A. K. Dewdney introduced Core War a society was formed which organised an annual tournament. The First International Core War Tournament held in the Computer Museum, Boston MA was a great success with a paper coming out on top, Mice by Chip Wendell.

Core War is now played as a King of the Hill tournament. Players submit their program to a hill containing some of the top Core War programs, receiving results a few minutes later. If the program is successful it enters the hill, knocking off the lowest warrior.

Despite being 26 years old Core War still has a community of regular players. Although the major techniques appear to have been discovered new ideas are constantly being tested, occasionally with impressive results. If you’d like to find out more about Core War here are some handy links for new players:

If you’re planning to try your hand at writing a battle program, good luck and may the core be with you!

The Vintage Computer Festival, Bletchley Park

2010-06-12T07:41:00.000-07:00

The computing highlight of June will be the Vintage Computer Festival at The National Museum of Computing, Bletchley Park. Held on 19-20 June, the event is the first of it's kind in the U.K. Tickets can be purchased for £8.50 online or £10.00 on the door.

The National Museum of Computing's website has the full list of exhibitors, lectures and events. Some of the highlights include:

The launch of the new Amiga X1000 boasting a dual-core 1.8GHz PowerISA CPU, 2GB memory and Xena 500MHz SDS co-processor
20+ exhibitors demonstrating a variety of historic computers
Lectures by a number of key figures in computing history, including Sophie Wilson, one of the designers of Acorn Computers and ARM processors
Retro gaming competition

I'll be there when the gates open at 10:30am on Saturday. Are you planning to attend?

Computer Museums in the U.K.

2010-06-05T09:34:00.000-07:00

The U.K. has a number of dedicated computer museums while a few other museums have permanent computer history collections. If you're interested in the history of computing the following are definitely worth a visit:

The National Museum of Computing

During World War II Bletchley Park was home to Britain's secret codebreaking activities. The National Museum of Computing is based at Bletchley and has a collection which includes an Elliot 803, ICL 2966 and the Colossus. The museum is open Thursday and Saturday afternoons, admission £8.50.

Museum of Computing

The Museum of Computing is close to Swindon's town centre and specialises in home computers and games consoles. The museum is open on Monday and Saturday, admission £3.50.

The Science Museum

London's Science Museum has a collection dedicated to the history of computing. The museum is home to a variety of notable systems including a Cray 1, Ferranti Pegasus and Charles Babbage's Difference Engine. Entry is free.

The Centre for Computing History

The Centre for Computing History is based at Haverhill in Suffolk. The museum has an extensive collection of home computers, manuals and magazines. Admission is free but by appointment only.

The Museum of Science and Industry

The calculating and computing exhibition at Manchester's Museum of Science and Industry includes a rebuilt Baby, the world's first stored program computer. Entry to the museum is free.

My Latest Gadget: Altera MAX II

2010-05-07T13:07:00.000-07:00

Here's my latest gadget, a SLS ELT II development board with Altera MAX II picked up for £1.20 on eBay :-) It provides 240 programmable logic elements and 8 kilobits of flash memory. I haven't got anything planned for it yet apart from a crazy idea about evolving a logic array to solve a problem. Have you got any great ideas for a project?

10 Alternative Monospace Fonts for Programmers

2010-05-03T01:11:00.000-07:00

Recently I started to look for an alternative programming font after spending far too many hours staring at Courier New. I needed to find a free fixed-width font that's easy on the eye and clearly distinguishes between similar characters, e.g. O01Il.

Here's a quick round up of the best alternatives I found. Which programming font are you using? Did I miss your favourite?

Default Monospace Fonts

First let's take a look at the default fonts. The examples show the font at 12 point with subpixel rendering switched off:

Consolas

Consolas is a monospace programming font created for Microsoft by Lucas de Groot and ships with Windows Vista / Windows 7. Has a slashed zero and designed to look best with ClearType enabled.

Courier New

Courier New is perhaps the most familiar monospace font having been introduced in 1992 with Windows 3.1. Courier New is a serifed font designed by Adrian Frutiger and lacks a slashed zero.

Lucida Console

Lucida Console designed by Charles Bigelow and Kris Holmes is the default font for Windows Notepad and also lacks a slashed zero.

Monaco

Monaco is a sans-serif monospace font designed by Susan Kare and Kris Holmes and ships with Mac OS X. Includes a slashed zero.

Alternative Monospace Fonts

While some of the default fonts aren't too bad, we can do much better. Here are some great alternatives mostly designed with programmers in mind:

Anonymous Pro

Anonymous Pro is a programming font designed by Mark Simonson. The serifed font was influenced by Susan Lesch and David Lamkins' Anonymous 9. Very clear with plenty of white space and a slashed zero.

Bitstream Vera Sans Mono

Bitstream Vera Sans Mono is a sans-serif coding font designed by Jim Lyles from Bitstream. The zero is dotted and the bottom of the lower case l curls to the right.

DejaVu Sans Mono

DejaVu Sans Mono is extended from Bitstream Vera Sans Mono and supports a wider selection of characters. The clean sans-serif font ships with a number of Linux distributions.

Dina

Dina is a sans-serif programming font created by Jørgen Ibsen and is available in 8, 9 or 10 point. Has a slashed zero.

Droid Sans Mono

Droid Sans Mono was designed by Steve Matteson of Ascender Corporation. The sans-serif font is clear but lacking a slashed or dotted zero.

Envy Code R

Envy Code R is a clean sans-serif programming font designed by Damien Guard and includes a slashed zero.

Inconsolata

Inconsolata is a monospace programming font created by Raph Levien and inspired in part by Consolas. Has a slashed zero.

Monofur

Monofur is a quirky monospace font created by Tobias Benjamin Köhler. Includes a dotted zero and a curl on the lower case l.

Proggy Clean

Proggy Clean was designed by Tristan Grimmer and is available with either a dotted or slashed zero. Several variants of the Proggy font are available.

Triskweline

Triskweline is a clear monospace font created by Henning Koch. Lacks a slashed zero and only available in 10 point.

Classic Home Computer Fonts

2010-04-04T12:25:00.000-07:00

Anyone who owned a home computer in the 80's would have been intimately familiar with the character set. Although it was possible to redefine the font, it had to be loaded from cassette and was restricted to an 8×8 pixel grid. Love it or hate it, you were stuck with it.

Fortunately for anyone who misses their 8-bit computer a selection of classic fonts are available online. Here are a few of my favourites:

Amstrad CPC font

Atari font

Commodore font

ZX Spectrum font

Which home computers did you own and what did you love / hate about the font? :-)

Threaded Interpretive Languages by R. G. Loeliger

2010-03-20T02:14:00.000-07:00

In Threaded Interpretive Languages, Loeliger explores the design and implementation of TILs in an individual quirky style. Programs in a threaded language typically compiles to a list of subroutine calls or addresses. Loeliger focuses on Forth-like threaded languages and provides examples in Z80 assembly language.

After the standard introductory chapter the book gets straight down to the implementation details, first dealing with the design of the dictionary format, inner and outer interpreters. This is followed by example code for the interpreters and assembly language definitions for 170 of the most common subroutines.

Later chapters investigate some common extensions to TILs including virtual memory and floating point numbers. A section is devoted to assemblers and includes code for a structured Z80 assembler.

Threaded Interpretive Languages contains the most in-depth examination of Forth internals I've seen. However the age of the books shows in the dialect of Forth used and the systems described. Despite this, I'd still recommend Threaded Interpretive Languages to anyone planning to implement a minimal Forth.

Emulating the Manchester SSEM

2010-02-28T09:24:00.000-08:00

The Manchester Small-Scale Experimental Machine was the first computer to store programs in memory and was built at the University of Manchester in 1948 by Williams, Kilburn and Toothill.

The machine had 32 words of 32 bit memory, one register and supported 7 instructions:

000	JMP	s, C	Jump
100	JRP	c+s, C	Relative Jump
010	LDN	-s, A	Load and Negate
110	STO	a, S	Store
001	SUB	a-s, A	Subtract
011	CMP	Test	Skip if Negative
111	STOP	Stop	Halt Machine

With only 7 instructions the SSEM makes an ideal system for an emulation project. A basic simulator can be written in under 40 Intel x86 instructions. If you're tempted to write your own, the SSEM Reference Manual will come in handy. :-)

8 Bit Home Computer Benchmarks

2010-01-09T11:10:00.000-08:00

Over the years I've collected quite a few 8 bit home computers. Out of curiosity I decided to write a simple prime sieve benchmark to compare their implementations of BASIC.

10 LET W=500:DIM F(W):LET P=1:LET A=3
20 LET F(P)=A:LET P=P+1:IF P>W THEN STOP
30 LET A=A+2:LET X=1
40 LET S=A/F(X):IF S=INT(S) THEN 30
50 LET X=X+1:IF X<P AND F(X)*F(X)<=A THEN 40
60 GOTO 20

Here are the results from a few of the machines I have to hand:

System	CPU	Time
Acorn Electron	2.0MHz 6502	138
Amstrad CPC464	4.0MHz Z80A	140
Commodore C64	1.0MHz 6510	254
Commodore Plus/4	1.0 MHz 8501	267
Tandy 64K CoCo 2	0.895MHz 6809E	271
Atari 800XL	1.8MHz 6502	316
Sinclair Spectrum +3	3.55MHz Z80A	388

Let me know how long it takes to run on your favourite classic computer. :-)

Secret Opcodes of the 8 Bit Processors

2009-11-08T09:33:00.000-08:00

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

2009-09-20T13:45:00.000-07:00

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

2009-09-10T02:09:00.001-07:00

#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

2009-08-29T14:45:00.000-07:00

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

2009-08-25T15:39:00.000-07:00

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

2009-07-25T12:11:00.000-07:00

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

2009-07-09T12:07:00.000-07:00

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

2009-07-02T01:49:00.000-07:00

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.

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

2009-06-30T08:38:00.000-07:00

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

2009-06-01T13:14:00.000-07:00

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

2009-05-22T23:33:00.000-07:00

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!

2009-05-09T00:21:00.001-07:00

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

2009-04-27T01:02:00.001-07:00

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

2009-03-25T10:57:00.000-07:00

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

2009-03-11T06:51:00.001-07:00

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

2009-02-06T01:17:00.000-08:00

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

2009-01-18T09:25:00.000-08:00

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:

accumulator
always contains 0
character input
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

2009-01-15T03:18:00.000-08:00

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

What can you Write in 128 Bytes?

2008-12-16T14:29:00.000-08:00

In contrast to the ever increasing memory available, a number of programmers are choosing to demonstrate their coding prowess by squeezing as much as possible into an incredibly tiny program. It has become a popular passtime to code an impessive graphical display in either 128 or 256 bytes.

Before zooming off to try this for yourself, why not check out some of the competition? Five of the best are listed below, and also my own contribution.

OKO by Ind. The coloured rings sway gently. Good use of colour.

Interference by New Generation Crew. A fast moving interference pattern between two sets of rings. Supplied with source code.

Ctverecky by RRRola. A chaotic, spiralling pattern. Only 93 bytes long. Supplied with source code.

Corkscrewed by lord Kelvin - a smooth, gentle swirl slowly draws you in. Great use of colour. Supplied with source code.

Color Dream by Digimind - a chaotic looking swarm of spheres. Impressive in motion.

Plasma Wave by John Metcalf - my own contribution. A display of flowing plasma. Supplied with source code.

If there's a program you think I should have included, or you want to show off your own demo, please leave a comment below.

Core War - Hostile Programming

2008-11-17T00:02:00.000-08:00

Core War is a game from the 80's, played between computer programs written in Redcode, a language similar to assembly. The programmers design their battle programs to remove opponents from the memory of the MARS virtual computer by any means possible.

Some of the simpler techniques include blindly overwriting memory, searching for the opponent or spawning off new processes. These are commonly known as stone, scissors, paper after the popular playground game. Stone usually wins against scissors, scissors normally defeat paper, and paper mostly beats stone.

Here's an example of a typical Core War program:

org   wipe

step  equ 5
first equ bomb-10

bomb:mov.i #1,       -1

ptr: sub   #step,    #first
wipe:jmz.f ptr,      @ptr

mov   bomb,     >ptr
djn.f wipe,     {ptr-5

end

This simple example of scissors once held a 20 point lead over it's rivals. The first instruction is never executed, it's the bomb used to overwrite opponents. The next two instructions form a loop which look through memory for an opponent, and the final two instructions actually overwrite it.

Core War is still going strong, and celebrates it's 25th anniversary in 2009. If you'd like to discover more about Core War, here are the top resources:

The Beginner's Guide to Redcode will teach you the language of Core War
pMARS is a portable implementation of the Core War virtual machine
Core War Tutorials exist on virtually every aspect of the game
Koenigstuhl is an archive of thousands of published Core War programs
SAL organises a number of on-going king of the hill tournaments
sfghoul and impomatic report the latest Core War news on their blogs
#corewars is the official Core War discussion channel, hosted by irc.freenode.net

What are your experiences with Core War, have you ever had any success?

Programming in Strange Places!

2008-10-26T02:44:00.000-07:00

Earlier this month I spent a week in Cornwall without access to a computer. In the true spirit of recreational programmers everywhere, this didn't curtail my programming activity. I managed to discover a number of solutions to the Semaphore Problem in Redcode while watching the waves!

However, programming on the beach, public transport, restaurants and even a theme park appear pretty normal alongside the place where I wrote Koch Curve for the Sinclair Spectrum.

One October night 14 years ago I took shelter from the wind and rain in Victoria Cave. After setting up for the night and studying the map, I eventually tried to code an idea I'd had a few days earlier.

Working by candlelight on scraps of paper I programmed, optimized and hand assembled Koch Curve for the Speccy's Z80. Perhaps the surroundings explain the strange names I used for labels!

What's the strangest place you've written a program? I'd love to know.

Optimising Assembly Like an 80's Hacker

2008-09-21T00:01:00.000-07:00

Forget about fancy algorithms and data structures. If you want respect as an 80's hacker, follow these simple tips.

Never get caught setting a register to zero without using xor:

Z80 Code

ld a,0           ; bad, 2 bytes / 7 cycles

xor a            ; good, 1 byte / 4 cycles

8088 Code

mov ax,0         ; bad, 3 bytes / 4 cycles

xor ax,ax        ; good, 2 bytes / 3 cycles

Never set two 8 bit register independently. Code readability is not required:

Z80 Code

ld b,10          ; bad, 4 bytes / 14 cycles
ld c,32

ld bc,10*256+32  ; good, 3 bytes / 11 cycles

8088 Code

mov ch,10        ; bad, 4 bytes / 8 cycles
mov cl,32

mov cx,10*256+32 ; good, 3 bytes / 4 cycles

Never compare to zero:

Z80 Code

cp 0             ; bad, 2 bytes / 7 cycles

or a             ; good, 1 byte / 4 cycles

8088 Code

cmp ax,0         ; bad, 3 bytes / 4 cycles

test ax,ax       ; good, 2 bytes / 3 cycles

Remember, you don't need to worry about code alignment, order of instructions or processor penalties. Follow these simple tips and your super-optimised bubble sort will demand the utmost respect!

Al Zimmermann's Programming Contests

2008-09-12T07:22:00.000-07:00

Normally I don't participate in programming challenges, but something about the latest of Al Zimmermann's Programming Contests caught my attention.

The idea is to submit sets of numbers so their combination by addition and subtraction generates the most distinct primes. There are 12 problems, for sets of 3 to 14 numbers.

A pen and paper should be sufficient to find the optimal solution for 3 numbers. Don't be fooled however, the solutions for 4+ require a program to search through the possibilities.

4 yields easily to a computer search with at least three optimal solutions waiting to be discovered. Despite writing a program which tests 280,000 potential solutions per second, I haven't found the top solution for 5.

Currently I'm restricting the search space to one odd number, one multiple of 6 and the remaining numbers all multiples of 30. Maybe this is too restrictive?

Here's the program I'm using. Any suggestions how I can improve the speed?

n1 equ 1
n2 equ 6
n3 equ 30
n4 equ 90
n5 equ 270

i1 equ 600
i2 equ 600

vprime equ 7000

numb equ 5

; *** generate list of primes

mov si,prime+4
mov bx,5
nextpr:
mov di,prime+2
try:
mov ax,bx
xor dx,dx
div word[di]
or dx,dx
jz notpr
scasw
ja try
mov word[si],bx
cmpsw
notpr:
inc bx
inc bx
cmp si,prime+vprime
jne nextpr

; *** fill prime table with zero

xchg ax,bx
mov di,tabl
xchg ax,cx
xor ax,ax
rep stosb

; *** update values to test

testnew:
add word[xa],2
cmp word[xa],n1+i1+10
jc gogo
mov word[xa],n1

add word[xb],6
cmp word[xb],n2+i2+10
jc gogo
mov word[xb],n2

add word[xc],30
mov ax,word[xc]
cmp ax,word[xd]
jc gogo
mov word[xc],n3

add word[xd],30
mov ax,word[xd]
cmp ax,word[xe]
jc gogo
mov word[xd],n4

add word[xe],30

; *** mark primes in table

gogo:
mov ax,word[xa]
add ax,word[xe]
add ax,word[xd]
add ax,word[xc]
add ax,word[xb]
xchg dx,ax
mov si,prime
ptab:
lodsw
cmp dx,ax
jc fini
add ax,tabl
xchg bx,ax
mov byte[bx],1
cmp si,prime+vprime
jne ptab
fini:

; *** test

xor bp,bp
mov ax,word[xa]
mov bx,word[xe]
mov cx,word[xd]
mov dx,word[xc]
mov di,word[xb]

call x2

; *** if there's a new top score...

xchg ax,bp
cmp ax,word[xhigh]
jl next

; *** ... display the winning numbers

mov word[xhigh],ax
call printdec

mov dl,' '
call printchar
mov dl,'-'
call printchar

mov cx,numb
lea si,word[xa]
disp:
mov dl,' '
call printchar
lodsw
call printdec
loop disp

mov dl,0D
call printchar
mov dl,0A
call printchar

; *** and repeat

next:
mov ah,1
int 016h
jz redo
int 020h
redo:
jmp testnew


x2:
push ax
add ax,bx
call x3
pop ax
push ax
sub ax,bx
call x3
pop ax

x3:
push ax
add ax,cx
call x4
pop ax
push ax
sub ax,cx
call x4
pop ax

x4:
push ax
add ax,dx
call x5
pop ax
push ax
sub ax,dx
call x5
pop ax

x5:
push ax
add ax,di
call x6
pop ax
push ax
sub ax,di
call x6
pop ax

x6:
xabs:
neg ax
js xabs
add ax,tabl
xchg ax,si
cmp byte[si],0
je notprx
inc bp
mov byte[si],0
notprx:
xchg ax,si
ret

; *** print number in ax

printdec:
push ax
push cx
push dx
mov cx,10
xor dx,dx
div cx
test ax,ax
je pdbye
call printdec
pdbye:
add dl,'0'
call printchar
pop dx
pop cx
pop ax
ret

printchar:
mov ah,2
int 021
ret

xhigh:dw 0

xa:dw n1-2
xb:dw n2
xc:dw n3
xd:dw n4
xe:dw n5

prime:
dw 2
dw 3

tabl equ prime+vprime+10

Five Programming Books I Couldn't Survive Without

2008-09-02T07:24:00.000-07:00

There's roughly 400 programming books on my bookshelf. If I had to reduce it to just five, here are the books I just couldn't live without.

Introduction to Algorithms - Cormen, Leiserson, Rivest & Stein. This programming book provides in depth yet accessible coverage of many algorithms. If I want to get the job done as quickly and painfree as possible, I reach for Introduction to Algorithms before Knuth's The Art of Computer Programming every time.
Compilers: Principles, Techniques and Tools - Aho, Sethi & Ullman. "The Dragon Book" provides an excellent introduction to compiling before getting stuck into the inner workings of analysis, translation, code generation and optimisation.
The New Turing Omnibus - Dewdney. Sitting atop the fun programming books category, Dewdney's book offers 66 articles covering a variety of computer science topics and recreational computing problems.
Fundamentals of Operating Systems - Lister. The way the structure of this book mirrors the structure of an operating system makes it an easier point of reference than books such as Krakowiak's Principles of Operating Systems.
Advanced Spectrum FORTH - Thomasson. Depite being written for a sadly obsolete platform, Advanced Spectrum FORTH remains one of the best FORTH programming books. The source code for the dictionary provides a valuable resource.

Disagree? Think I've missed out a classic programming book? Drop me a comment below.

Programming Quotes

2008-08-20T23:00:00.000-07:00

Beware of bugs in the above code; I have only proved it correct, not tried it.

Donald Knuth, 1977

It is practically impossible to teach good programming style to students that have had prior exposure to Basic; as potential programmers they are mentally mutilated beyond hope of regeneration.

Edsger W. Dijkstra, 1982

Measuring programming progress by lines of code is like measuring aircraft building progress by weight.

Bill Gates

Anyone who considers arithmetical methods of producing random numbers is, of course, in a state of sin.

John von Neumann, 1951

Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

Stan Kelly-Bootle

Infinite Loop

2008-06-29T03:02:00.000-07:00

More often than not, infinite loops are created by programming errors and are quickly dealt with. In sympathy for this highly persecuted group of programs, a safe haven has been created on retro code. The two infinite loops below are highly optimized examples. In fact, the actual loops are only 1 byte long!

Z80 Infinite Loop

  ld hl, HERE
HERE:jp (hl)

8080 Infinite Loop

  lxi h, HERE
HERE:pchl

Corewar Infinite Loop

  jmp #0, <-5

In Corewar, the infinite loop finds its niche destroying small mobile programs called imps!

If you know any infinite loops in need of shelter, please post them in the comments below.

Privacy Policy

2008-06-12T00:08:00.000-07:00

Privacy

I respect your privacy. The following policy explains how information is collected on Retro Code. Your personal information will never be sold or disclosed to a third party, except where required by law.

Statistics

I use Google Analytics to track aggregate statistics about visitors to Retro Code. This information is not linked to personally identifiable information.

Cookies are small data files stored by a website on a user's computer. Retro Code does not uses cookies. However, some of my advertising partners use cookies. I have no access to cookies set by advertisers.

Advertisers

I use advertising partners to display ads on Retro Code. These partners may use cookies. I work with Google Adsense and Amazon. Please check the advertising partners' websites for their privacy policies.

Contact Information

If you have any questions please contact John Metcalf at digital.wilderness@googlemail.com.

Retro Programming

USB Stick Microcontroller Dev Boards

Micropendous3

Maximus AVR USB 1.2

Minimus AVR USB 32K

eZ430-F2013

Maximus AVR USB 1.0

µRlink ST7Ultralite Primer v1.1

A Bibliography of Programming Games

Bibliography

Darwin: Celebrating 50 Years of Programming Games

References

See Also

Computus: Calculating Easter Sunday

Itsy-OS Kernel: Preemptive Switcher & Memory Manager

Memory Control Blocks

Task Switcher

Deallocate Memory

Allocate Memory

Setup

Alternatives to Windows Notepad for Programmers

Efficiency in Forth

Jones Forth TUCK

Alternative TUCK

The Tao of Programming

Celebrating 30 Years of Color Robot Battle

Interactive Fiction: 4K Adventure

CoreLife: Artificial Life Simulator

Recursion via Pascal

#CarolsInCode - Top Five Countdown

More #CarolsInCode

#carolsincode - Christmas for Programmers

Programming Contest: Topswaps

URISC / OISC: One Instruction Computers

Types of URISC

MOV – Transport Triggered Architecture

RSSB – Reverse Subtract and Skip if Borrow

SUBNEG – Subtract and Branch if Negative

SUBLEQ – Subtract and Branch if Less than or Equal

Other Types of OISC

Core War - The King of Programming Games

The Vintage Computer Festival, Bletchley Park

Computer Museums in the U.K.

The National Museum of Computing

Museum of Computing

The Science Museum

The Centre for Computing History

The Museum of Science and Industry

My Latest Gadget: Altera MAX II

10 Alternative Monospace Fonts for Programmers

Default Monospace Fonts

Consolas

Courier New

Lucida Console

Monaco

Alternative Monospace Fonts

Anonymous Pro

Bitstream Vera Sans Mono

DejaVu Sans Mono

Dina

Droid Sans Mono

Envy Code R

Inconsolata

Monofur

Proggy Clean

Triskweline

Classic Home Computer Fonts

Threaded Interpretive Languages by R. G. Loeliger

Emulating the Manchester SSEM

8 Bit Home Computer Benchmarks

Secret Opcodes of the 8 Bit Processors

Secrets of the Z80

Secrets of the 8086/8088

A History of Programming Games 1961-1989

Darwin

RobotWar

Color Robot Battle

Core War

DROID

CROBOTS