LC-3 VM in Swift

 •  Filed under swift

I followed the Write your own Virtual Machine tutorial to write a VM. I decided to write it in Swift, because I haven't written Swift in a while and miss writing Swift programs.

Code

The complete source code for the project can be viewed here.

I have only ever written one, also toy, VM before when I was working through the Nand2Tetris book and course some years back and had long forgotten some of the specifics, which is why this exercise was a good refresher.

You will notice that the code is in no way optimized, but it works, which is good enough for now.
Both memory and the registers are represented as UInt16 arrays. I could have gone with pointers to UInt16 values directly in memory, which probably would have been faster and more elegant.

Here are some interesting things I (re)learned while implementing this project.

Sign Extend

The LC-3 VM works with unsigned 16 bit integers. However, some of the instructions, such as the ST (store) instruction depicted below, call for arithmetic operations of an unsigned 16 bit integer with a another integer with fewer than 16 bits. The ST operation works by storing the contents specified by the register SR in the memory location specified by adding the program counter offset (PCOffset) bits 0 through 8 to the current value of the program counter (PC). The PC, much like all other registers in the LC8 machine is a 16 bit value, however, while the PCOffset is 9 bits wide.
To be able to go through with the addition of the two values, the PCOffset value will have to be sign extended. If the most significant bit of the PCOffset is 0, we simply fill up PCOffset with 0s to the left until it's 16 bits long. In case of a MSB of 1, PCOffset is filled up with 1s.
Sign extension of a value basically increases the number of bits of a binary number while preserving its sign (positive/negative).

Screen-Shot-2019-02-22-at-22.46.47

Overflow addition in Swift

Unlike with the C programming language when adding two UInt16 integers in Swift (or any unsigned integers for that matter), there is no automatic overflow handling.
For instance the following code will give an EXC_BAD_INSTRUCTION error in Swift:

let n: UInt16 = UInt16(UINT16_MAX)
print(n + 5) //EXC_BAD_INSTRUCTION

In order to opt in to overflow behavior for unsigned integers, you have to use the overflow addition (or subtraction or multiplication) operator &+.

let n: UInt16 = UInt16(UINT16_MAX)
print(n &+ 5) //4

Terminal modes

A terminal's default behavior for stdin is to buffer and pre-process keyboard inputs until a new line \n is encountered and only then pass it on to the running program. This mode is called cooked or canonical mode.
To implement the checkKeyBoard() function for the VM I needed every individual key press to be passed on to my program without any buffering and waiting for a new line character to be entered.
This requires the terminal to be set to raw or non-canonical mode.
We can set a terminal's attributes by reading them out with tcgetattr() into a struct, modifying that struct and then passing that modified struct into tcsetattr().

To big endian

Writing this VM served as a welcome refresher on endianness. It reminded me that endianness refers to the ordering of individual bytes of an integer word (while endianness can refer to individual bits, this is exceedingly rare in practice).
LC-3 VM programs are big endian. Most modern CPU architectures use little endian byte ordering. In order for the VM to work correctly on little endian machines, we had to swap the endianness of every read in 16 bit word from big to little endian representation.

Memory mapped registers

I was reminded of the existence of memory mapped registers while implementing this project. These registers are, as the name implies, not available in the register table, but instead have special addresses in memory. These registers can be read from and written to by simply treating them as regular memory addresses.
In the LC-3 machine, the keyboard status register (KBSR) and the keyboard data register (KBDR) are two such memory mapped registers. The KBSR indicates whether or not a keystroke on the keyboard has been registered. The KBDR holds the value (in our case ASCII code) of the key that has been pressed. The registers are polled in every iteration of the the VM while loop to check for keystrokes.

Writing this VM has been a lot of fun and very educational. If you have the time I would definitely recommend writing one yourself to deepen your understanding of some low level hardware concepts.