Speaker intro

• David Vázquez Púa (@davazp)
• Tijn Kersjes (@tkers)

Reaktor Amsterdam

After-hours hacking

• Founded Amsterdam Hackers

First project:

• Write an emulator?
• ...a Game Boy game?
• ...a compiler!

Initial research

Game Boy hardware

• 8-bit CPU
• 4 MHz (~1MHz CPU clock)
• 32kB ROM, 4kB RAM
• 8 + 2 registers:

Special registers ($FF00 - $FFFF)

• Video subsystem (palette, tiles, scroll, background)
• Sound subsystem (square1, square2, wave, noise)
• Input buttons
• Timers

How do we start?

• Keep reading the manual
• Start writing a compiler (somehow)
• ...wait forever until you get something on the screen

However...

• Not incremental
• Long feedback cycle

Instead ✨

• Start with working game (example)
• Reverse-engineer binary
• Try to refactor bytes
  • Add abstractions
  • Build libraries
• Write a compiler on top

Forth

• No syntax, just words
• Using stack for arguments

5 1 + .

• 5 push to stack
• 1 push to stack
• + pop 2 arguments and push sum
• . pop 1 argument and print

Forth

You can create new words

5 1 + .

can be refactored into:

: INC
  1 + ;

5 INC .

Forth

• Simplest imaginable language
• Concatenative
  • concatenation is composition
• Grow your own language

Starting the project

Machine code (ROM)

$00  $c3  $50  $01  $ce  $ed  $66  $66
$cc  $0d  $00  $0b  $03  $73  $00  $83
$00  $0c  $00  $0d  $00  $08  $11  $1f
$88  $89  $00  $0e  $dc  $cc  $6e  $e6
$dd  $dd  $d9  $99  $bb  $bb  $67  $63
$6e  $0e  $ec  $cc  $dd  $dc  $99  $9f
$bb  $b9  $33  $3e  $45  $58  $41  $4d
$50  $4c  $45  $00  $00  $00  $00  $00
$00  $00  $00  $00  $00  $00  $00  $00
$00  $00  $01  $33

Forth program that emits bytes

$00 c, $c3 c, $50 c, $01 c, $ce c, $ed c, $66 c, $66 c,
$cc c, $0d c, $00 c, $0b c, $03 c, $73 c, $00 c, $83 c,
$00 c, $0c c, $00 c, $0d c, $00 c, $08 c, $11 c, $1f c,
$88 c, $89 c, $00 c, $0e c, $dc c, $cc c, $6e c, $e6 c,
$dd c, $dd c, $d9 c, $99 c, $bb c, $bb c, $67 c, $63 c,
$6e c, $0e c, $ec c, $cc c, $dd c, $dc c, $99 c, $9f c,
$bb c, $b9 c, $33 c, $3e c, $45 c, $58 c, $41 c, $4d c,
$50 c, $4c c, $45 c, $00 c, $00 c, $00 c, $00 c, $00 c,
$00 c, $00 c, $00 c, $00 c, $00 c, $00 c, $00 c, $00 c,
$00 c, $00 c, $01 c, $33 c,

Find the patterns and meaning

$00 c, $c3 c, $50 c, $01 c, $ce c, $ed c, $66 c, $66 c,
$cc c, $0d c, $00 c, $0b c, $03 c, $73 c, $00 c, $83 c,
$00 c, $0c c, $00 c, $0d c, $00 c, $08 c, $11 c, $1f c,
$88 c, $89 c, $00 c, $0e c, $dc c, $cc c, $6e c, $e6 c,
$dd c, $dd c, $d9 c, $99 c, $bb c, $bb c, $67 c, $63 c,
$6e c, $0e c, $ec c, $cc c, $dd c, $dc c, $99 c, $9f c,
$bb c, $b9 c, $33 c, $3e c, $45 c, $58 c, $41 c, $4d c,
$50 c, $4c c, $45 c, $00 c, $00 c, $00 c, $00 c, $00 c,
$00 c, $00 c, $00 c, $00 c, $00 c, $00 c, $00 c, $00 c,
$00 c, $00 c, $01 c, $33 c,

Extract data into definitions

: logo
  $ce c, $ed c, $66 c, $66 c, $cc c, $0d c, $00 c, $0b c,
  $03 c, $73 c, $00 c, $83 c, $00 c, $0c c, $00 c, $0d c,
  $00 c, $08 c, $11 c, $1f c, $88 c, $89 c, $00 c, $0e c,
  $dc c, $cc c, $6e c, $e6 c, $dd c, $dd c, $d9 c, $99 c,
  $bb c, $bb c, $67 c, $63 c, $6e c, $0e c, $ec c, $cc c,
  $dd c, $dc c, $99 c, $9f c, $bb c, $b9 c, $33 c, $3e c, ;

: title
  $45 c, $58 c, $41 c, $4d c, $50 c, $4c c, $45 c, $00 c,
  $00 c, $00 c, $00 c, $00 c, $00 c, $00 c, $00 c, $00 c, ;

$00 c, $c3 c, $50 c, $01 c,
logo
title
$00 c, $00 c, $01 c, $33 c,

Decompiling machine code

• $3c is machine code for INC-A
• $04 is machine code for INC-B

Factor out operands to create full assembler

: A %00111000 ;
: B %00000000 ;

: INC,
  %00000100 or c, ;

• A INC, emits $3c

Complete assembler

• Extend language with pattern matching
  • Define ~~> and ::

Translate ROM to assembler

di,
$ffff # sp ld,

%11100100 # a ld,
a [rGBP] ld,

0 # a ld,
a [rSCX] ld,
a [rSCY] ld,

( ... )

Macros for free!

: reset-scroll
  0 # a ld,
  a [rSCX] ld,
  a [rSCY] ld, ;

di,
$ffff # sp ld,

%11100100 # a ld,
a [rGBP] ld,

reset-scroll

( ... )

Macros for free!

: reset-scroll
  0 # a ld,
  a [rSCX] ld,
  a [rSCY] ld, ;

: reset-palette
  %11100100 # a ld,
  a [rGBP] ld, ;

di,
$ffff # sp ld,

reset-palette

reset-scroll

( ... )

Next steps

Implementing Forth

Implementing Forth

The easy way:

• Use ASM macros to define Forth primitives
  • dup, swap, +...

The hard way:

• Create Intermediate Representation for definitions
  • Lazy emitting
  • Optimisations

Eventually...

• Implement code primitives (ASM)
• Adding high level libraries (Forth)
• Translating ROM to Forth

Limitations

• No run-time on Game Boy
• Division between ROM and RAM

The final test 💪

Compiling a third party Forth game...

\ sokoban - a maze game in FORTH

\ Copyright (C) 1995,1997,1998,2003,2007,2012,2013,2015
\ Free Software Foundation, Inc.

\ This file is part of Gforth.

40 Constant /maze  \ maximal maze line

Create maze  1 cells allot /maze 25 * allot  \ current maze
Variable mazes   0 mazes !  \ root pointer
Variable soko    0 soko !   \ player position
Variable >maze   0 >maze !  \ current compiled maze

: maze-field ( -- addr n )
    maze dup cell+ swap @ chars ;

: .score ( -- )
    ." Level: " level# @ 2 .r ."  Score: " score @ 4 .r
    ."  Moves: " moves @ 6 .r ."  Rocks: " rocks @ 2 .r ;

: .maze ( -- )  \ display maze
    0 0 at-xy  .score
    cr  maze-field over + swap
    DO  I /maze type cr  /maze chars  +LOOP ;

Future ideas 🚀

• ASM bug fixes
• Compiler optimisations: peephole, inlining
• GB Color support
• Memory Bank Controllers
• Automatic ROM bank switching
• Debugging tools
• Tutorial: Write a game in Forth

Contributions welcome!