nand2tetris
This project is from the course nand2tetris. From building logic gates to writing a high level language and an operating system in it, the resultant is a modern-day 16-bit computer which I have documented below.
Project Outcome
- Bare bones hardware - The Hack computer
- Assembly language - The Hack assembly
- Virtual machine - The Jack Virtual Machine (JVM)
- High level language - The Jack programming language
- Operating System - The Jack OS
Table of Contents
Hardware
This section aims at building the bare-bones of the computer. We first make simple logic gates and then leverage them to further make more sophisticated hardware. The logic is written in a custom Hardware Description Language (HDL) specified here.
Logic Gates
All the logic gates are created from the primitive Nand gate. Here are a list of gates that were implemented.
- Nand, Not, And, Or, Xor
- Mux, DMux
- Not16, And16, Or16, Mux16 - 16-bit wide gates
- Or8Way - Or(x0,...,x7)
- Mux4Way16, Mux8Way16, DMux4Way16, DMux8Way16 - 16-bit wide with 4/8 inputs
ALU
This ALU can compute eighteen functions using some minimal hardware design. It uses 6 control bits where each bit refers to a certain elementary operation.
| control-bit | description |
|---|---|
| zx | zero the x input? |
| nx | negate the x input? |
| zy | zero the y input? |
| ny | negate the y input? |
| f | compute x+y (if 1) or x&y (if 0) |
| no | negate the output? |
The following functions can be computed with the control bits as follows:
| # | zx | nx | zy | ny | f | no | f(x,y) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 1 | 0 | 1 | 0 | -1 |
| 4 | 0 | 0 | 1 | 1 | 0 | 0 | x |
| 5 | 1 | 1 | 0 | 0 | 0 | 0 | y |
| 6 | 0 | 0 | 1 | 1 | 0 | 1 | !x |
| 7 | 1 | 1 | 0 | 0 | 0 | 1 | !y |
| 8 | 0 | 0 | 1 | 1 | 1 | 1 | -x |
| 9 | 1 | 1 | 0 | 0 | 1 | 1 | -y |
| 10 | 0 | 1 | 1 | 1 | 1 | 1 | x+1 |
| 11 | 1 | 1 | 0 | 1 | 1 | 1 | y+1 |
| 12 | 0 | 0 | 1 | 1 | 1 | 0 | x-1 |
| 13 | 1 | 1 | 0 | 0 | 1 | 0 | y-1 |
| 14 | 0 | 0 | 0 | 0 | 1 | 0 | x+y |
| 15 | 0 | 1 | 0 | 0 | 1 | 1 | x-y |
| 16 | 0 | 0 | 0 | 1 | 1 | 1 | y-x |
| 17 | 0 | 0 | 0 | 0 | 0 | 0 | x&y |
| 18 | 0 | 1 | 0 | 1 | 0 | 1 | x|y |
The ALU also produces two status bits with the output.
| status-bit | description |
|---|---|
| zr | is the output zero? |
| ng | is the output negative? |
The following chips were implemented in this section
Future work: It will be better to replace the naive ripple carry adder in Add16 with a more efficient one like a carry-lookahead adder.
Registers, RAM and PC
Storage is realized using Data Flip-Flops (DFFs). Registers are 16-bit wide and are composed of DFFs. These registers are further stacked to create the random access memory (RAM). It allows reading/writing data from/to any address in constant time, irrespective of the physical location.
Finally, a program counter is also realized using a 16-bit register which has the following functions - reset to zero, load a particular value, and increment the current value.
List of chips implemented
Architecture
Bringing together all the circuitry, the computer is assembled in this section. The resultant device is a 16-bit von Neumann platform consisting of a CPU, two memory modules and two memory-mapped I/O devices - a screen and a keyboard.
There are two 16-bit registers A and D where D is the data register which intends at storing values, and A acts as a dual purpose register which can store both data and address. Depending on the instruction context, A's value can be interpreted as either data or a memory address. The A register allows direct memory access.
Instruction Set
The complete instruction set reference is available at this. There are two generic types of instructions available - A-instruction or address instruction, and C-instruction or compute instruction. Each instruction has a binary and symbolic representation.
The A-instruction
This is used to set the A register to a 15-bit value.
Instruction: @value
Binary: 0 v v v v v v v v v v v v v v v
A-instruction allows setting a constant value at a memory address. It also allows the C-instruction to manipulate a certain memory location or make a jump to a particular location. The left-most bit 0 is the A-instruction opcode and the following bits are the 15-bit value.
The C-instruction
C-instruction accounts for all the compute tasks on this computer.
Instruction:dest=comp;jump // Either dest/jump maybe empty and symbols are omitted accordingly.
Binary:1 x x a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
The left-most bit 1 is the C-instruction opcode and the next two bits are don't cares. The comp field is specified by the a-bit and the six c-bits. The a-bit is responsible for selecting either A-register or Memory and the c-bits are the control bits for the ALU. The dest field is given by the d-bits which allow us to select a destination. Each bit is mapped to a particular location where data is written if the bit is set.
| d-bit | location |
|---|---|
| d1 | A-register |
| d2 | D-register |
| d3 | Memory |
The last three bits are the jump bits which decide when to make the jump. Together with the two status bits from ALU, they guide the PC in deciding the next address.
| j1 | j2 | j2 | Mnemonic |
|---|---|---|---|
| 0 | 0 | 0 | null |
| 0 | 0 | 1 | JGT |
| 0 | 1 | 0 | JEQ |
| 0 | 1 | 1 | JGE |
| 1 | 0 | 0 | JLT |
| 1 | 0 | 1 | JNE |
| 1 | 1 | 0 | JLE |
| 1 | 1 | 1 | JMP |
Memory
This computer has two memory banks - instruction memory and data memory. The instruction memory is implemented using a ROM chip with 32K addressable 16-bit registers. The data memory is a RAM device consisting of 32K addressable 16-bit registers with provision for memory mapped IO.
The data memory is laid out with the RAM in the upper section, followed by IO memory buffers for the two peripheral devices - a 512 x 256 display and a keyboard. Data memory supports 15-bit addressing.
| address | component | capacity |
|---|---|---|
| 0x0000 - 0x3FFF |
RAM | 16K |
| 0x4000 - 0x5FFF |
Screen | 8K |
| 0x6000 | Keyboard | 1 |
Implementation: Memory Chip.
CPU
The CPU consists on the ALU, two registers A and D, and a program counter PC. It fetches the instruction from the instruction memory and decodes it using internal circuitry of logic. It then executes the instruction and writes back the data.
The control bits in the image above are labelled c. Different bits are routed to different parts of the CPU.
Implementation: CPU Chip.
Computer
Finally, the computer can be realized by connecting the instruction memory, CPU and the data memory. Final implementation - Computer. This marks the complete hardware which powers everything on this device. Finally, the computer can be realized by connecting the instruction memory, CPU and the data memory. Final implementation - Computer. This marks the complete hardware which powers everything on this device.
Assembler
An assembler is a piece of software that converts an assembly code into the device's machine code. This assembler is written in python and follows the instruction set as specified above. The assembler API is specified by this.
To assemble a program:
$ assembler.py /path/to/file.asm
All mnemonic lookup hashtables are defined in [convert](./Hack assembler/convert.py).
All predefined symbols and symbol hashtable are defined in [symbol_table](./Hack assembler/symbol_table.py).
Jack Virtual Machine
A virtual machine facilitates a two-tier compilation for our code. It handles intermediate logic and allows the high-level language to leverage its architecture than compile to raw assembly which is a really complex task. A VM translator is realized which translates program in the VM language to the Hack assembly. It is stack-based and supports four types of commands:
| Arithmetic | Perform arithmetic and logical operations on stack |
| Memory Access | Transfer data b/w stack and memory segments |
| Program Flow | Conditional and unconditional braching ops |
| Function Calling | Call functions and return from them |
Stack Arithmetic
Arithmetic/Logical commands
There are nine commands out of which two are unary and seven are binary. The stack uses -1 (0xFFFF) for true and 0 (0x0000) for false.
| command | action |
|---|---|
| add | pop y, pop x, push x+y |
| sub | pop y, pop x, push x-y |
| and | pop y, pop x, push x&y |
| or | pop y, pop x, push x|y |
| lt | pop y, pop x, push -1 if x<y, else 0 |
| gt | pop y, pop x, push -1 if x>y, else 0 |
| eq | pop y, pop x, push -1 if x=y, else 0 |
| neg | pop x, push -x |
| not | pop x, push !x |
Memory access commands
Memory commands can manipulate eight separate virtual memory segments. The command uses two variables which can select any memory location together.
Pointer-based addressing
| segment | location | purpose | notes |
|---|---|---|---|
| argument | *(ARG+index) | store function's arguments | private to a function |
| local | *(LCL+index) | store function's local variables | private to a function |
| this | *(THIS+index) | store field variables of current object | can be used to manipulate certain heap areas |
| that | *(THAT+index) | store array entries | " |
Absolute addressing
| segment | location | purpose | notes |
|---|---|---|---|
| pointer | THIS(0) or THAT(1) | alter base ptrs for this/that segments | - |
| temp | R5-R12 | global temporary variables | public access to everyone |
| internal | R13-R15 | internal variables used by VM | - |
| static | filename.index | store static variables of a file | all functions in the file share it |
| constant | @index | store constants 0-(2^15-1) | emulated for consistency - pseudo segment |
These two commands can essentially realize any memory operation.
push segment index
push the value at index in segment to the stack
segment can be - argument, local, static, constant, this, that, pointer or temp.
pop segment index
pop value off the stack and store at index in segment
segment can be - argument, local, static, this, that, pointer or temp.
Note, index is a non-negative integer.
Data structures
There are two implicit data structures managed by the Virtual Machine without any explicit implementation in the software. Their state is managed with carefully written pseudo commands.
- Stack - The working memory of the VM operations is a stack. All operations are facilitated using a stack.
- Heap - An area in RAM dedicated for storing objects and data structures like arrays.
Program Control
Now that we have basic some functionality in our VM, it can do math and handle memory well. However, it's still away from realizing more complex things like handling functions, go-tos and conditional statements. In this section we will implement everything that helps us controlling our program.
Branching
Labels can be declared as label c.
We have two types of branching -
| Type | Command | Usage |
|---|---|---|
| Unconditional | goto | goto c |
| Conditional | if-goto | if-goto c |
Note, conditional statement jumps to the given label if top of the stack is not equal to zero.
Algorithm :
pop x
if (x != 0)
goto c
Function Commands
JVM and Hack
Abstract notions of the VM defined above sounds good, but there should be a contract between the principles listed and the hardware it will run on, i.e. the Hack computer.
RAM Usage
The Hack data memory consists of 32k 16-bit words - refer memory. The VM implementation uses the space as follows
| Address | Usage |
|---|---|
| 0-15 | 16 virtual registers (described below) |
| 16-255 | Static variables |
| 256-2047 | Stack memory |
| 2048-16383 | Heap memory |
| 16384-24575 | Memory mapped I/O |
Hack registers
The first 16 registers can be addressed using the assembly as R0-R15. However, VM introduces some conventions for easy readibility and accessibility.
| Register(s) | Name | Usage |
|---|---|---|
| R0 | SP | Stack Pointer |
| R1 | LCL | Points to local segment |
| R2 | ARG | Points to argument segment |
| R3 | THIS | Points to this segment (in heap) |
| R4 | THAT | Points to that segment (in heap) |
| R5-R12 | - | Holds content of temp segment |
| R13-R15 | - | Can be used as general-purpose registers |
Future
Uhm, I stopped working on this because I got bored. To be continued...