Tuesday 16 December 2008

What can you Write in 128 Bytes?

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 pastime to code an impressive 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.

OKOOKO by Ind. The coloured rings sway gently. Good use of colour.
InterferenceInterference by New Generation Crew. A fast moving interference pattern between two sets of rings. Supplied with source code.
CtvereckyCtverecky by RRRola. A chaotic, spiralling pattern. Only 93 bytes long. Supplied with source code.
CorkscrewedCorkscrewed by lord Kelvin - a smooth, gentle swirl slowly draws you in. Great use of colour. Supplied with source code.
Color DreamColor Dream by Digimind - a chaotic looking swarm of spheres. Impressive in motion.
Plasma WavePlasma 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.

Monday 17 November 2008

Core War - Hostile Programming

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:
What are your experiences with Core War, have you ever had any success?

Sunday 26 October 2008

Programming in Strange Places!

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.

Victoria Cave, near SettleKoch Curve on the Sinclair Spectrum

Sunday 21 September 2008

Optimising Assembly Like an 80's Hacker

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!

Friday 12 September 2008

Al Zimmermann's Programming Contests

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

Tuesday 2 September 2008

Five Programming Books I Couldn't Survive Without

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.
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Wednesday 20 August 2008

Programming Quotes


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

Sunday 29 June 2008

Infinite Loop

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.

Thursday 12 June 2008

Privacy Policy

Privacy

I respect your privacy.  The following policy explains how information is collected on Retro Programming.  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 Programming.  This information is not linked to personally identifiable information.

Cookies

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

Contact

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