The Most Functional Emulator: FNES (finesse)

Haskell is an interesting language. When I learnt it 2 years ago in my comparative programming language course I was amazed by what could be achieved with number in so few lines of code. Take Quicksort for example most languages take 10 lines or more, Haskell only takes 4:

quiksort [] = []
quiksort (x:xs) = smaller ++ [x] ++ larger
where smaller = quiksort [i | i <- xs, i < x]
larger = quiksort [i | i <- xs, i >= x]

Or creating an infinite list of prime numbers:

primes = sieve [2..]
where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

Haskell was awe inspiring especially with my background in mathematics I could see the elegance of its syntax with my analytical mind. Back then it was just a little nick nack I used to solve project euler problems and not much else. Why not use it for more? Afterall xMonad, a popular linux window manager, is fully programmed in it. Its uniqueness is something that makes it fun and interesting to program in. So that is something I plan on doing.

Emulators

A long time project I have always wanted to embark on has been a retro videogame console emulator, namely a NES. Sure there are plenty of NES emulators out there and this would likely not add anything interesting to the mix. This project is more about enriching my own curiousity of how emulators work and enacting practice on my problem solving ability. This also gives me a project to use as a learning tool for Haskell. In C, after obtaining the knowledge of how an emulator works it would be quite trivial to implement and I like a good challenge.

Basic Architecture

The initial problem with a functional emulator is that passing around values through each iteration of the CPU is expensive because values are immutable. This means that in order to update the values in the register of the CPU I must create a new CPU and pass that to the next iteration like so:

The problem with this is it’s slow especially for an application that is meant to be precisely timed. This might not be a problem with implementing an NES but it might prove problematic for more advanced emulation. For the purpose of this project and this blog I am going to assume that it might be a problem in the future.

A solution to this is instead using a library called Elerea. This is used for functionally reactive programming (FRP). Elerea uses a type called a Signal a which is essentially a value which changes over time, value a can represent any type. The value of the signal will be different depending on when in time the value gets unwrapped from it’s Signal type. The underlying mechanism of this is that the value is wrapped in such a way that it’s value is mutable. So instead of continuously passing new CPUs to the next stage of emulation we can have a CPU containing registers that are wrapped in Elerea Signals allowing us to have less overhead:

This can also be used in the memory model as well where our NES RAM can be viewed as a type Array Int (Signal Word8) meaning that each entry of the Array will change with time as opposed to replacing the whole array each time:

Loading INES Format File

The first step before we can truly get started is make a ROM structure and load into that from a file. For now I am going to support the bare minimum which inlcudes the loading of INES 1.0 only. This is just so I can move more swiftly through the project and implement more functionality when the need arises.

The INES file format has the following structure:

  • Header: 16 bytes
  • Trainer (if present): 512 bytes
  • PRG ROM: (# of PRG Banks x 16384) bytes
  • CHR ROM: (# of CHR Banks x 8192) bytes
  • PlayChoice INST-ROM (if present): 8192 bytes
  • PlayChoice PROM (if present): 16 bytes Data, 16 bytes CounterOut, 32 bytes total

The information for how much of each memory type to load is contained in the header. The header contains the following information and mind you I am only giving the minimal in order to load the whole file (if you are interested in learning more of the specifics of the INES 1.0 or INES 2.0 go here.

Since loading the file only happens once at the beginning and the performance only needs to happen while the ROM is running we can use Haskells fancy tricks to load this file. Since this file is a binary we want to load it as one. ByteString is a Haskell module inside Data which allows us to load a ByteString it also comes with a function which allows us to convert the ByteString into a [ Word8 ]. This is convenient for two reasons; 1: since we are using Word8 as a basic type in our 8 bit emulator we won’t need further conversion and 2: since it is a list we can use pattern matching from the start of the file to the end of the file.

module Main where
import ROM (loadRom, ROM)
import qualified Data.ByteString as B (readFile, unpack)
main = do
file <- B.readFile "romName.nes"
let bytes = B.unpack file
let rom = loadRom bytes doSomething rom

Now mind you this is a simplified version of what might be required. For example we might want to accept the rom name on the command line. In this case loadRom is a function which parses the bytes of the file and stores them in a record…I will get to that but first I must describe the contents of a ROM Record.

data ROM = ROM { 
header :: Header,
trainer :: Maybe (Vector Word8),
prgRom :: Vector Word8,
chrRom :: Vector Word8,
playChoiceINST :: Maybe (Vector Word8),
playChoicePROM :: Maybe (Vector Word8)
}
data Header = Header { 
prgSize, chrSize, prgRamSize :: Int,
flag6, flag7, flag9, flag10 :: Word8
}

A ROM Record contains all the useful information that allows the game to run. This includes the ROM containing the char blocks containing sprite information and PRG ROM which contains all the program information. The player choice and trainer sometimes are in ROMs and sometimes not. I am not completely clear on their purpose but I have them specified as Maybe because most of the time they represent Nothing. The next most important piece is the header which contains information about which of these Maybes I load along with the number of CHAR and PRG banks. It also contains useful information about what features of the emulator this ROM specifically requires.

splitAtIf :: Bool -> Int -> [a] -> (Maybe [a], [a])
splitAtIf cond at list =
if cond
then let (front, rest) = splitAt at list in (Just front, rest)
else (Nothing, list)

Since we are going to be traversing the [Word8] we require spliting at specific intervals and sometimes not for our Maybe values. splitAt is a function loaded in the core library to split a list and return into a tuple the first and last parts. Above is a modified version to allow for splitting or not on a condition this will be useful as you will see below.

loadRom :: [Word8] -> ROM
loadRom (0x4E:0x45:0x53:0x1A:file1) =
ROM {
header = header,
prgRom = fromList prgRom,
trainer = fmap fromList trainer,
chrRom = fromList chrRom,
playChoicePROM = fmap fromList playChoicePROM,
playChoiceINST = fmap fromList playChoiceINST
}
where
(head, file2) = splitAt 12 file1
header = loadHeader head
trainer, file3) = splitAtIf (hasTrainer header) 512 file2
(prgRom, file4) = splitAt (prgSize header) file3
(chrRom, file5) = splitAt (chrSize header) file4
(playChoiceINST, file6) = splitAtIf (hasPC10 header) 8192 file5
(playChoicePROM, empty) = splitAtIf (hasPC10 header) 32
file6 _ = if empty == [] then [] else error "Invalid ROM File"
loadRom _ = error "Invalid ROM File"

The first part of every ROM contains 4 bytes which are “NES” followed by an MSDOS end of file character. Pattern matching on this is the first step of detecting a valid file. Below the where clause we pull off the last 12 bytes of the header, technically the first 4 bytes is a part of the header but it is entirely useless except for validation. Taking those 12 bytes and running them through the loadHeader function returns a header which can be used for the future loads and activating certain features in the emulator. The next calls involve loading the definite and optional splits. Below is a basic overview of how to load the pieces of the header.

loadHeader :: [Word8] -> Header
loadHeader (p:c:f6:f7:pr:f9:f10:0x00:0x00:0x00:0x00:0x00:[]) =
Header {
prgSize = fromIntegral p,
chrSize = fromIntegral c,
flag6 = f6,
flag7 = f7,
prgRamSize = fromIntegral pr,
flag9 = f9,
flag10 = f10
}
loadHeader _ = error "Invalid Header: only compatible with INES 1.0 ROMs"

Loading a header is super simple as it can done in just one pattern match. As for the flag numbering it is based off the beginning of the file so flag6 is byte 6 in a zero indexed position from the start of the file. Each flag contains information associated with functionality required from the emulator. The last 5 bytes are zero meaning that I will only support INES 1.0, in version 2.0 there are additional flags in the last 5 bytes of the header.

hasTrainer :: Header -> Bool
hasTrainer Header { flag6 = flag6 } =
(/=) 0 $ (.&.) flag6 $ shiftL 2 1
hasPC10 :: Header -> Bool
hasPC10 Header { flag7 = flag7 } =
(/=) 0 $ (.&.) flag7 $ shiftL 1 1

And that is the rest of my code showing how the conditions are evaluated for the conditional splits. To check if a bit is a 1 in Haskell like any language shift 1 left to the position you want to check and bitwise & comparing to 0. This code is the equivalent to (flag6 & (1 << 2)) != 0 in C.

Next

I will be moving towards getting opcodes alongside the CPU working and playing around with Helm which is what I will be using for the graphical display. Right now I am using sdl2 in my cabal file but I intend to move over. The next post might take a while and I am considering moving this over to a shorter format because writing long posts is hard while concurrently coding and working fulltime. Please leave comments since writing is new to me and any help is appreciated. Thanks for reading.


Originally published at www.adambrykajlo.ca on January 29, 2016.