Saturday, 15 March 2014

Plotting the Mandelbrot Set on the ZX Spectrum

ZX Spectrum MandelbrotZX Spectrum Mandelbrot

The Mandelbrot set is a fractal which iterates the equation zn+1 = zn² + c in the complex plane and plots which points tend to infinity. Plotting the set with Sinclair BASIC takes over 24 hours so I was curious how much faster it would be in assembly.

It turns out if we use fast 16-bit fixed-point arithmetic we can plot the Mandelbrot in about 5 minutes. To minimise multiplications each iteration is calculated as:

rn+1 = ( rn + in ) × ( rn - in ) + x

in+1 = 2 × in × rn + y

The following test is used to detect points which tend to infinity:

|in| + |rn| ≥ 2 × √ 2.
  org 60000
  ld de,255*256+191
XLOOP:
  push de
  ld hl,-180   ; x-coordinate
  ld e,d
  call SCALE
  ld (XPOS),bc
  pop de
YLOOP:
  push de
  ld hl,-96    ; y-coordinate
  call SCALE
  ld (YPOS),bc
  ld hl,0
  ld (IMAG),hl
  ld (REAL),hl
  ld b,15      ; iterations
ITER:
  push bc
  ld bc,(IMAG)
  ld hl,(REAL)
  or a
  sbc hl,bc
  ld d,h
  ld e,l
  add hl,bc
  add hl,bc
  call FIXMUL
  ld de,(XPOS)
  add hl,de
  ld de,(REAL)
  ld (REAL),hl
  ld hl,(IMAG)
  call FIXMUL
  rla
  adc hl,hl
  ld de,(YPOS)
  add hl,de
  ld (IMAG),hl
  call ABSVAL
  ex de,hl
  ld hl,(REAL)
  call ABSVAL
  add hl,de
  ld a,h
  cp 46        ; 46 ≅ 2 × √ 2 << 4
  pop bc
  jr nc,ESCAPE
  djnz ITER
  pop de
  call PLOT
  db 254       ; trick to skip next instruction
ESCAPE:
  pop de
  dec e
  jr nz,YLOOP
  dec d
  jr nz,XLOOP
  ret

FIXMUL:        ; hl = hl × de >> 24
  call MULT16BY16
  ld a,b
  ld b,4
FMSHIFT:
  rla
  adc hl,hl
  djnz FMSHIFT 
  ret

SCALE:         ; bc = (hl + e) × zoom
  ld d,0
  add hl,de
  ld de,48     ; zoom

MULT16BY16:    ; hl:bc (signed 32 bit) = hl × de
  xor a
  call ABSVAL
  ex de,hl
  call ABSVAL
  push af
  ld c,h
  ld a,l
  call MULT8BY16
  ld b,a
  ld a,c
  ld c,h
  push bc
  ld c,l
  call MULT8BY16
  pop de
  add hl,de
  adc a,b
  ld b,l
  ld l,h
  ld h,a
  pop af
  rra
  ret nc
  ex de,hl
  xor a
  ld h,a
  ld l,a
  sbc hl,bc
  ld b,h
  ld c,l
  ld h,a
  ld l,a
  sbc hl,de
  ret

MULT8BY16:     ; returns a:hl (24 bit) = a × de
  ld hl,0
  ld b,8
M816LOOP:
  add hl,hl
  rla
  jr nc,M816SKIP
  add hl,de
  adc a,0
M816SKIP:
  djnz M816LOOP
  ret

PLOT:          ; plot d = x-axis, e = y-axis
  ld a,7
  and d
  ld b,a
  inc b
  ld a,e
  rra
  scf
  rra
  or a
  rra
  ld l,a
  xor e
  and 248
  xor e
  ld h,a
  ld a,d
  xor l
  and 7
  xor d
  rrca
  rrca
  rrca
  ld l,a
  ld a,1
PLOTBIT:
  rrca
  djnz PLOTBIT
  or (hl)
  ld (hl),a
  ret

ABSVAL:        ; returns hl = |hl| and increments
  bit 7,h      ; a if the sign bit changed
  ret z
  ld b,h
  ld c,l
  ld hl,0
  or a
  sbc hl,bc
  inc a
  ret

XPOS:dw 0
YPOS:dw 0
REAL:dw 0
IMAG:dw 0

Sunday, 9 February 2014

The Spring 2014 Core War Tournament

In May 1984 A K Dewdney introduced Core War, a game played between two or more computer programs in the memory of a virtual computer. The aim of the game is to disable all opponents and survive the longest. A variety of strategies have evolved for Core War, each with their own strengths and weaknesses.

To celebrate the 30th anniversary in May, The Spring Core War Tournament will be held at The Centre for Computing History in Cambridge UK. The Centre was established to tell the story of the Information Age and presents an interactive collection of computers and artifacts.

Entries can be up to 25 instructions and will compete in three different core sizes, 800 (tiny), 8000 (standard) and 55440 (large). A program's final score will be calculated as follows:

    final_score = 2 × standard_score + tiny_score + large_score

The program with the highest final score will be awarded the first prize, $50 and a signed copy of The Armchair Universe by A K Dewdney. The top program in each core size will be awarded a signed copy of Life As It Could Be by Thure Etzold, a technothriller which explores the possibility of programs escaping the confines of the Core War virtual computer.

Entries can be sent via email or delivered to The Centre on the day of the tournament (date tbc). Players can submit up to two entries. All entries will be published at the end of the tournament.

The provisional deadline is 01 May 2014. Updates will be posted on news:rec.games.corewar, http://corewar.eu, #corewars on irc.freenode.net and on twitter using the hashtag #corewar. Good Luck!

Technical Details:

Players may enter up to two programs. Programs face each other in a one-on-one round robin, no p-space, no self-fights, no read/write limits. Entries must be your own work. Extended ICWS'94 Draft Redcode applies with the following settings:

  • pmars -s 800 -p 800 -c 8000 -l 25 -d 25
  • pmars -s 8000 -p 8000 -c 80000 -l 25 -d 100
  • pmars -s 55440 -p 10000 -c 500000 -l 25 -d 200

Entries may use the run-time variables (CORESIZE, MAXPROCESSES, etc) to tailor the program for each core size, but the program must still behave essentially the same. Some allowed examples include:

  • tweaking the steps / constants
  • adding an extra bombing line to the core clear
  • including an extra SPL/MOV pair to a paper

Completely changing the program's behaviour or swapping / adding extra components for each core size is not allowed.

Further Details:

More information about Core War can be found at:

Software is available from:

Core War can be played online at:

For help, advice and updates see:

The Centre for Computing History has a website at:

Friday, 3 January 2014

Fast Z80 Bit Reversal

For years I've been using the following simple code to reverse the bits in the A register by rotating the bits left out of one register and right into another:

; reverse bits in A
; 8 bytes / 206 cycles

  ld b,8
  ld l,a
REVLOOP:
  rl l
  rra
  djnz REVLOOP

Recently I wondered if it's possible to save a few cycles. It turns out the bits are at most 3 rotations away from their position in the reverse:

76543210
⇐1⇐33⇒1⇒⇐1⇐33⇒1⇒
01234567

With this in mind I devised a bit-twiddling hack to reverse the bits in about a third of the time using only 6 rotates and a bit of logic to recombine the rotated bits. Here's the code, which no doubt has been done many times before:

; reverse bits in A
; 17 bytes / 66 cycles

  ld l,a    ; a = 76543210
  rlca
  rlca      ; a = 54321076
  xor l
  and 0xAA
  xor l     ; a = 56341270
  ld l,a
  rlca
  rlca
  rlca      ; a = 41270563
  rrc l     ; l = 05634127
  xor l
  and 0x66
  xor l     ; a = 01234567

Monday, 11 November 2013

The Centre for Computing History in Cambridge

The Centre for Computing History in Cambridge

The Centre for Computing History is a short walk from Cambridge city centre and is home to a sizeable collection of computers. The museum actively encourages visitors to sit down, try out a few games and even have a go at BASIC programming.

The museum's collection ranges from mechanical calculators and mainframes to home computers and games consoles. Most of the home computers and consoles are switched on and running classic games.

If you're interested in the history of computing (particularly home computing), the centre is the perfect place for a day out.

MITS Altair 8800 computer

Relaxen und watschen der Blinkenlights - the MITS Altair 8800

Commodore PET 2001

PRINT CHR$(205.5+RND(1)); - Commodore PET 2001

ZX Spectrum 48K

PLOT 48,56:DRAW 160,0,65536 - ZX Spectrum 48K

Intel MDS 80 Microprocessor Development System

Intel MDS 80 Microprocessor Development System

HP1000 F Series minicomputer

HP1000 F Series minicomputer

Friday, 18 October 2013

Video Gaming 1979-1989 at the NCCD

Video Gaming 1979-1989 exhibition at The National Centre for Craft and Design

The National Centre for Craft & Design is hosting an event to celebrate the golden age of video games, "Revolution in the Bedroom, War in the Playground: Video Gaming 1979-1989". The exhibition runs from 19th October to 5th January in the main gallery.

The exhibition focuses on bedroom programmers, 8-bit games design and magazine cover art with classic games running on several computers. If you're in the Sleaford area, it's definitely worth a visit.

ZX Spectrum circuit schematic diagram by Simon Patterson

Detail from Simon Patterson's 15 metre chalkboard circuit diagram

artwork by Oliver Frey

Cover artwork by Oliver Frey

Video Gaming 1979-1989 exhibition

Thursday, 1 August 2013

ZX Spectrum Koch (Lévy C) Curve

ZX Spectrum Koch (Lévy C) Curve

A few years ago I submitted a couple of type-in programs (C-Curve and Curtains) to Your Sinclair and they featured in the penultimate issue (August 1993).

Encouraged by a shiny new YS badge I sent off a new batch of programs. Unfortunately it was too late. The September issue would be Your Sinclair's "Big Final Issue".

C-Curve is one of the simplest fractal curves. It starts with a straight line. To find the next iteration, each line is replaced by two lines at 90°:

C Curve fractal

Here's a later 69 byte version of the program which plots the fractal in approximately 1.52 seconds! Assemble with Pasmo (pasmo ccurve.asm ccurve.bin), load the binary to address 65467 in your favourite emulator and run using RANDOMIZE USR 65467 :-)

  org 65467
  ld de,49023 ; d = position on x axis
              ; e = position on y axis
  ld bc,3840  ; b = number of iterations
              ; c = initial direction
RECURSE:
  djnz DOWN

  ld a,6      ; check direction
  and c       ; c=0, left
  rrca        ; c=2, up
  rrca        ; c=4, right
  add a,a     ; c=6, down
  dec a
  jr nc,XMOVE

  add a,e     ; adjust y position +/-1

  ld e,a      ; calculate high byte of screen pos
  rrca
  scf
  rra
  rrca
  xor e
  and 88
  xor e
  and 95
  ld h,a
  sub h

XMOVE:
  add a,d     ; adjust x position +/-1

  ld d,a      ; calculate low byte of screen pos
  rlca
  rlca
  rlca
  xor e
  and 199
  xor e
  rlca
  rlca
  ld l,a

  ld a,7      ; calculate bit position of pixel
  and d
  ld b,a
  inc b
  ld a,1
SHIFTBIT:
  rrca
  djnz SHIFTBIT

  xor (hl)    ; plot
  ld (hl),a
  ret

DOWN:
  inc c       ; turn 45° clockwise
  call RECURSE
  inc b
  dec c       ; turn 90° anti-clockwise
  dec c
  call RECURSE
  inc b
  inc c       ; turn 45° clockwise
  ret

Finally here's a short type-in program to poke the code into a real Spectrum!

Thursday, 4 July 2013

Silicon Dreams & The Vintage Computer Festival

The Centre For Computing History at Silicon Dreams

This weekend the biggest event in the U.K.'s retro computing calendar will be hosted at the Snibston Discovery Museum in Leicestershire. The Vintage Computer Festival follows 2010's highly successful event with most of the main exhibitors returning. Some of the highlights include:

  • Raspberry Jam - a hands-on workshop for the Raspberry Pi single board computer organised by the Centre for Computing History.
  • The Amiga is well represented at the show with demonstrations of MorphOS 3.2 and the latest AmigaOne X1000.
  • 15+ exhibitors will be displaying a wide range of historic / unusual computers including RISC OS running on the Raspberry Pi.
  • Look out for the Spectranet ethernet board in action. Tweet direct from a ZX Spectrum complete with nixie tube tweetometer!

The event runs from 5th - 7th July. Tickets are £15 for the day, or £20 for the weekend. We'll be there when the gates open at 10am. Is anyone else planning to attend?