Genesis Does Fibonacci

Can you think of a better way to spend a holiday than learning to write assembly language for a 26-year-old game console? I couldn’t, so I wrote a simple program for the SEGA Genesis. (Known as the Mega Drive outside North America.)

First, some tools are needed:

  • A decent text editor
  • An Assembler that produces M68000 machine code
  • A Genesis emulator with a built-in debugger

I tried to find these three tools for Mac OS X, my preferred platform. There are plenty of text editors available and the GNU assembler will run on just about anything, but I could not find a Genesis emulator for Mac OS X that has a built-in debugger. Phooey. Gotta use the right tool for the job, so it was time to dig out the old PC. Windows XP, Pentium 4. Let’s go!

A Text Editor

text_editor

You’ll need something kinda like this.

I downloaded Notepad++. There are probably better choices, but I’m using what I know. Any plain-text editor will do the job, even Notepad if you hate yourself.

An M68000 Asembler

The main processor is the M68000 (68k) from Motorola, so learning 68k assembly language is important. There are plenty of guides online, and I will link a couple at the end of this article.

The ASM68k assembler is quick to set up. It is available at Sonic Retro. To install, I copied the ASM68k.exe file into a folder pointed at by my $PATH environment variable:

C:\Windows\system32

Genesis Emulator + Debugger

Regen is the first emulator+debugger I found. Better options may be available. The link with a “D” after the version includes the debugger. Regen was crashing a lot when I tried doing more advanced things beyond what this post covers. I’m not sure if that is Regen’s fault or if my code was bad. Regardless, it is sufficient for the material in this article.

Write and Run a Program

Once the tools were gathered, I wrote and tested a simple program to make sure everything works. If you want to follow along at home, paste this into a text editor:

; ******************************************************
; ************** Sega Genesis ROM Header ***************
; ******************************************************
	dc.l	0x00FFE000		; Initial stack pointer value
	dc.l	Start		        ; Initial program counter value
	dc.l	Exception		; Bus error
	dc.l	Exception		; Address error
	dc.l	Exception		; Illegal instruction
	dc.l	Exception		; Division by zero
	dc.l	Exception		; CHK exception
	dc.l	Exception		; TRAPV exception
	dc.l	Exception		; Privilege violation
	dc.l	Exception		; TRACE exception
	dc.l	Exception		; Line-A emulator
	dc.l	Exception		; Line-F emulator
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Spurious exception
	dc.l	Exception		; IRQ level 1
	dc.l	Exception		; IRQ level 2
	dc.l	Exception		; IRQ level 3
	dc.l	HBlankInterrupt	; IRQ level 4 (horizontal retrace interrupt)
	dc.l	Exception		; IRQ level 5
	dc.l	VBlankInterrupt	; IRQ level 6 (vertical retrace interrupt)
	dc.l	Exception		; IRQ level 7
	dc.l	Exception		; TRAP #00 exception
	dc.l	Exception		; TRAP #01 exception
	dc.l	Exception		; TRAP #02 exception
	dc.l	Exception		; TRAP #03 exception
	dc.l	Exception		; TRAP #04 exception
	dc.l	Exception		; TRAP #05 exception
	dc.l	Exception		; TRAP #06 exception
	dc.l	Exception		; TRAP #07 exception
	dc.l	Exception		; TRAP #08 exception
	dc.l	Exception		; TRAP #09 exception
	dc.l	Exception		; TRAP #10 exception
	dc.l	Exception		; TRAP #11 exception
	dc.l	Exception		; TRAP #12 exception
	dc.l	Exception		; TRAP #13 exception
	dc.l	Exception		; TRAP #14 exception
	dc.l	Exception		; TRAP #15 exception
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)
	dc.l	Exception		; Unused (reserved)


; ******************************************************
; *************** Sega Genesis ROM Info ****************
; ******************************************************	
	dc.b "SEGA GENESIS    "	; Console name
	dc.b "(C)RJC- 2014.SEP"	; Copyrght holder & date
	dc.b "Fibonacci Loop                                  "	; Domestic name
	dc.b "Fibonacci Loop                                  "	; International name
	dc.b "GM XXXXXXXX-XX"	; Version number
	dc.w 0x0000		; Checksum
	dc.b "J               "	; I/O support
	dc.l 0x00000000		; Start address of ROM
	dc.l Finish	        ; End address of ROM
	dc.l 0x00FF0000		; Start address of RAM
	dc.l 0x00FFFFFF		; End address of RAM
	dc.l 0x00000000		; SRAM enabled
	dc.l 0x00000000		; Unused
	dc.l 0x00000000		; Start address of SRAM
	dc.l 0x00000000		; End address of SRAM
	dc.l 0x00000000		; Unused
	dc.l 0x00000000		; Unused
	dc.b "                                        "	; Notes (unused)
	dc.b "JUE             "	; Region codes


; ******************************************************
; ******** The Meat of the Program Begins Here *********
; ******************************************************
Start:
    clr.l d0			; Clear register d0 (zero it out)
    move.l #0x1, d1		; Move 1 into register d1
FibLoop:
    move.l d1, d2		; Copy d1 into d2
    add.l d0, d1		; Add d0 into d1
    bvs Start		        ; If the overflow flag is set, go back to Start:
    move.l d2, d0		; Copy d2 (old value of d1) into d0
    jmp FibLoop        	        ; Jump back up to FibLoop:
	
	
; ******************************************************
; ********* Interrupt and Exception Handlers ***********
; ******************************************************
HBlankInterrupt:
VBlankInterrupt:
Exception:
    rte	; Just return, I don't want to figure this out today

Finish:		; Very last line, end of ROM address

Note that the code must be tabbed, but comments and labels can be on the left. Also note that different assemblers may use different syntax. I can only promise that this will work in asm68k. I saved my source file here:

C:\gen\test\test1.asm

I assembled my ROM by opening a command prompt, navigating to the directory containing the source file, and invoking the assembler like this:

cd \gen\test
asm68k /p test1.asm, test1.bin

I don’t have documentation for asm68k but running it without /p puts extra bytes at the front of the ROM which will prevent it from working. The other parameters are the input and output files. The command above created test1.bin (the ROM) from the test1.asm source code.

I opened test1.bin in the debug version of Regen. It just displays a black screen. From there I opened the M68000 debugger, clicked Reset, and was able to use the step 1 button to move through my code instruction by instruction and watch the registers change. Register d1 will count up the Fibonacci number sequence. The Fibonacci sequence is where each value is the sum of the two previous values:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Note that the register data is shown in hexadecimal (base-16) which uses digits 0-F, so 0000000D=13 and 00000015=21 which are both part of the sequence. Understanding hexadecimal numbers is vital. Go study if needed.

debugger

You can see fibonacci numbers counting up in register d1.

What Does the Code Mean?

The lines at the top that start with dc are creating a mandatory 512 byte header that all Genesis ROMs have. The dc instruction writes one or more Bytes into the ROM. The first block of the header sets up Exception and Interrupt handlers that the Genesis will call under certain circumstances, but I am not using them in my simple program. The next section contains Metadata and sets values like ROM size and Region codes. For example, JUE means the ROM will work in Japan, USA, and Europe.

After writing the 512 byte header, the program begins. This location was specified on line 5. The actual program is just this little bit:

; ******************************************************
; ******** The Meat of the Program Begins Here *********
; ******************************************************
Start:
    clr.l d0			; Clear register d0 (zero it out)
    move.l #0x1, d1		; Move 1 into register d1
FibLoop:
    move.l d1, d2		; Copy d1 into d2
    add.l d0, d1		; Add d0 into d1
    bvs Start		        ; If the overflow flag is set, go back to Start:
    move.l d2, d0		; Copy d2 (old value of d1) into d0
    jmp FibLoop        	        ; Jump back up to FibLoop:

There are three types of lines here:

  • Comments – begin with ; and are notes to anybody reading the code. Comments have no effect on the program and are not a part of the assembled ROM. Comments may also appear at the end of other lines.
  • Labels – end with : and can work as notes to anybody reading the code. More importantly, labels act as symbols for the ROM address of the next instruction.
  • Instructions – contains a mnemonic (clr, move, add, etc.) followed by parameters (d0, a1, etc). These make the processor do stuff.

A quick rundown on the processor: There are eight 32-bit data registers called d0d7 where you typically do math and comparisons. There are eight 32-bit address registers called a0a7 that are used for pointing at locations in memory. The program counter pc holds the ROM offset of the current code being run and a 16-bit status register sr holds various flags like overflow, zero, etc.

Let’s start looking at the instructions:

    clr.l d0		; Clear register d0 (zero it out)
    move.l #0x1, d1	; Move 1 into register d1

These two lines simply set registers d0 and d1 to 0 and 1 respectively. clr means clear which zeroes out a data register. The .l at the end specifies a long word (32-bit) operation. I could instead use .w for word (16-bit) or .b for byte (8-bit). In those cases, the lowest 16 or 8 bits in the register would be zeroed out and the high bits would remain unchanged. Example:

    ; d0 is currently FFFFFFFF
    clr.b d0    ; d0 now contains FFFFFF00

move copies a value from one location to another. The parameters are source, destination. In this case, the source is a value (denoted by the # sign) and the destination is register d1. The result is that the number 0x1 is copied into register d1.

    ; d1 could contain anything right now
    move.l #0x1, d1    ; d1 now contains 00000001

I could have also used move instead of clr on the first line like this:

; d0 could contain anything right now
    move.l #0x0, d0    ; d0 now contains 00000000

I used clr instead of move on the first line because it has one parameter instead of two which results in a shorter ROM. It is also a faster operation for the CPU. The 0x before my numbers means I am using hexadecimal. Hex values can also be denoted with a dollar sign #$1. Since I’m only using zeroes and ones, I could have entered these values in binary #%1 or decimal #1. The assembler converts it all, so it comes down to preference.

FibLoop:
	move.l d1, d2		; Copy d1 into d2
	add.l d0, d1		; Add d0 into d1
	bvs Start		; If the overflow flag is set, go back to Start:
	move.l d2, d0		; Copy d2 (old value of d1) into d0
	jmp FibLoop        	; Jump back up to FibLoop:

This section begins with a label that I will explain momentarily. The next instruction is a move that copies the value from d1 to d2 because we will need that number later. add does what one would expect: it adds two numbers. In this case, it adds the value in d0 to the value in d1, overwriting the previous value in d1. (That is why I copied d1 to d2 first.)

Ignore the bvs line for now; it usually doesn’t do anything.

The final move copies the number in d2 to d0. I hope I didn’t defeat the simplicity of my example by making the program too complex, but I’ll attempt to explain why:

Before the add, d0 and d1 will contain two numbers, in order, from the Fibonacci sequence. For example, d0 could be 3 and d1 could be 5. The next number in the Fibonacci sequence will be 8 (3+5) followed by 13 (5+8). The add will destroy the 5 in d1 and leave an 8 there, but we need that 5 for the computation after that (5+8=13) so we copy it to d2 before the add and copy it to d0 after the add, so d0 and d1 will 5 and 8 which makes them ready to compute the next number in the sequence. I hope that made sense.

Finally, we have the jmp which jumps to another location in the code. In this case, we are jumping to the FibLoop: label (by changing the value in the program counter to the address represented by the FibLoob: label). This program does that forever. Computes a Fibonacci number, jumps up to FibLoop: and computes another one. Right before each jmp instruction, d1 is a new number in the Fibonacci sequence and d0 is the preceding number. Here’s a breakdown of the first few iterations:

; d0=0 | d1=1 | d2=???
FibLoop:
move.l d1, d2 ; d0=0 | d1=1 | d2=1
add.l d0, d1 ; d0=0 | d1=1 | d2=1 (d1 doesn't change because 0+1=1)
move.1 d2, d0 ; d0=1 | d1=1 | d2=1
jmp FibLoop:
move.l d1, d2 ; d0=1 | d1=1 | d2=1
add.l d0, d1 ; d0=1 | d1=2 | d2=1
move.1 d2, d0 ; d0=1 | d1=2 | d2=1
jmp FibLoop:
move.l d1, d2 ; d0=1 | d1=2 | d2=2
add.l d0, d1 ; d0=1 | d1=3 | d2=2
move.1 d2, d0 ; d0=2 | d1=3 | d2=2
jmp FibLoop:
move.l d1, d2 ; d0=2 | d1=3 | d2=3
add.l d0, d1 ; d0=2 | d1=5 | d2=3
move.1 d2, d0 ; d0=3 | d1=5 | d2=3
jmp FibLoop:
move.l d1, d2 ; d0=3 | d1=5 | d2=5
add.l d0, d1 ; d0=3 | d1=8 | d2=5
move.1 d2, d0 ; d0=5 | d1=8 | d2=5
jmp FibLoop:

Fibonacci numbers keep getting bigger, so the d1 register will eventually be maxed out and “roll” over like an old car’s odometer or the Donkey Kong high score. If that happened, this program would produce garbage values that are not part of the Fibonacci sequence. Fortunately, the computer has a way to let you know if you “rolled” your register. It sets a flag called overflow if an addition results in a sum that exceeds the maximum value.

The bvs (which stands for Branch if oVerflow is Set) instruction helps with this by checking the overflow flag and acting as a jmp if it is set. Most of the time it does nothing, but, when the register overflows, it jumps to the Start: label where the values of d0 and d1 are set to restart the Fibonacci sequence.

What’s Next?

While it’s neat to open a debugger and watch the Fibonacci sequence count up, this is hardly the kind of blast processing people expect from the Genesis. The next step will be using the Visual Display Processor (VDP) to make things appear on the screen.

I spent my day off learning something new, and I found it to be very enjoyable. If you read this, maybe you learned something too. Feel free to let me know what you think or to point out anything I did wrong.

Links

Next Article

Source Code (test1.asm)

M68000 Programmer’s Reference Manual – Straight from the processor’s manufacturer

Notepad++ – A good free text editor

Sonic Retro – Plenty of great development resources including asm68k

68k Hax – Another quick reference for 68k instructions

Regen – Sega Genesis / Mega Drive Emulator + Debugger

Finally, these two websites have been invaluable in my learning efforts. Most of my early Genesis programming articles will mix content from these two sites plus a healthy dose of trial and error.

Big Evil Corporation

Marc’s Realm

Leave a Reply

Your email address will not be published. Required fields are marked *