From-Nand-Gates-To-Operating-System

This project's goal is to build a full computer from scratch by using only a Nand gate abstraction to go from implementing the CPU , RAM all the way till the Assembler , Compiler and finally a basic Operating System.

Computer Layers

This project was done in 9 subprojects, each in their respective folder. Since this project is focused on Computer Science, the computer was built on my own PC, using a software-based hardware simulator without any need for physical materials.

1 - Logic Gates

Creating elementary logic gates which will be the foundation of the Hack computer (this project's computer architecture). The Hardware Description Language (HDL) was used to create the following 15 elementary logic gates:

• Not.hdl - Inverts the input bit.
• And.hdl - Outputs 1 if both inputs are 1.
• Or.hdl - Outputs 1 if either input is 1.
• Xor.hdl - Outputs 1 if only one input is 1.
• Mux.hdl - Has two inputs, one selector bit and one output. The selector bit chooses which input to output.
• DMux.hdl - Has one input, one selector bit and two outputs. The selector bit chooses which output the input will go through. In case it chooses the a output, the b output will be 0.
• Not16.hdl - Not gate for 16-bit integer.
• And16.hdl - And gate for 16-bit integer.
• Or16.hdl - Or gate for 16-bit integer.
• Mux16.hdl - Mux gate for 16-bit integer.
• Or8Way.hdl - Or gate for 8-bit integer.
• Mux4Way16.hdl - Mux gate for 16-bit integer with 4 inputs instead of 2.
• Mux8Way16.hdl - Mux gate for 16-bit integer with 8 inputs instead of 2.
• DMux4Way.hdl - DMux gate with 4 outputs instead of 2.
• DMux8Way.hdl - DMux gate with 8 outputs instead of 2.

All of these gates were built either from the primitive Nand gate or from previously built gates.

2 - Arithmetic Gates And ALU

Creating arithmetic gates to implement the computer's Arithmetic Logic Unit (ALU):

• HalfAdder.hdl - Sums two input bits and outputs the sum and the carry bit.
• FullAdder.hdl - Sums two input bits and one carry bit and outputs the sum and the carry bit.
• Add16.hdl - Adds two 16-bit integers in Two's complement.
• Inc16.hdl - Adds 1 to 16-bit integers.
• ALU.hdl - Arithmetic Logic Unit, used to compute various operations, according to the following table:

3 - Memory Chips

Creating the memory chips of the Hack computer using the abstraction of the Data Flip-Flop gate (DFF):

• Bit.hdl - 1-bit Register.
• Register.hdl - 16-bit Register.
• RAM8.hdl - 16-bit RAM with 8 register of memory.
• RAM64.hdl - 16-bit RAM with 64 register of memory.
• RAM512.hdl - 16-bit RAM with 512 register of memory.
• RAM4K.hdl - 16-bit RAM with 4096 register of memory.
• RAM16K.hdl - 16-bit RAM with 16384 register of memory.
• PC.hdl - 16-bit program counter.

4 - Machine Language Programs

In this part, i wrote some assembly programs in order to start learning the Hack Assembly language that will eventually run on the Hack computer:

• Fill.asm - Runs an infinite loop that listens to the keyboard input. When a key is pressed (any key), the program blackens the screen and should remain fully black as long as the key is pressed. When no key is pressed, the program clears the screen. The screen should remain fully clear as long as no key is pressed.
• Mult.asm - Multiplies RAM[0] and RAM[1] and stores the result in RAM[2].
• add.asm - Sums RAM[0] and RAM[1] and stores the result in RAM[2].
• max.asm - Gets the maximum of RAM[0] and RAM[1] and stores the result in RAM[2].
• sum1toN.asm - Sums from 1 to RAM[0] and stores the result in RAM[1]: R1<-1+2+3+..+R0
• sumArray.asm - Stores the summation of all array elements in variable 'sum'

5 - Computer Architecture

Creating CPU and RAM of the Hack computer and applying the Harvard Architecture where the CPU has separate buses and memory for data and instructions, this is applied through the following chips:

• Memory.hdl - Entire RAM address space for the computer (RAM16K, Keyboard and Screen).
• CPU.hdl - The Hack CPU.
• Computer.hdl - The Hack computer platform.

Harvard Architecture :

Memory Design :

CPU Design :

6 - Hack Assembler

Building a Hack Assembler in C++ that translates .asm files into .hack binary files. It initializes predefined symbols and computation tables, then performs two passes: the first pass records label addresses, and the second pass assigns variables and generates the final 16-bit binary instructions.

All .hack instructions are a single 16-bit integer that can be translated either to A-instructions that is used for addressing or C-intructions used for calculation.

7 - Virtual Machine Translator

Since the compiler i built for this computer is a 2-tier architecture, a virtual machine layer was needed to translate the intermediate code into executable code. This stack-based virtual machine will serve as the backend module of the 2-tier compiler.

Creating a C++ file of VM translator to be operated in a CLI like:

g++ VMTranslator.cpp -o VMTranslator && ./VMTranslator StackTest\StackTest.vm.

The vm code in .vm files are translated into hack assembly in .asm files and placed in the same directory.

The VM translator is able to:

• Handle a total of 9 arithmetic and logic operations(add-sub-neg-eq-or-gt-lt-and-not).
• Translate push and pop commands to the VM Stack and to 8 distinct memory segments(local-argument-this-that-temp-static-pointer-constant).
• Translate complex branching scenario using goto and if-goto commands.
• Translate more complex functions and recursion scenarios using function , return and function calling using call command.
• Handle multi-file directory translation: g++ VMTranslator.cpp NestedCall, all .vm files in the directory will be translated into one .asm file.
• Translate bootstrap code in case there is a Sys.vm file in the directory (Resets Stack top and calls Sys.init).

The mapping for the VM translator is:

8 - Jack Analyzer And Compiler

For completing the front-end of the two-tier compiler architecture, a jack compiler was built to parse, analyze, and compile the jack high-level programs into intermediate VM code, which is then translated into Hack assembly by the previously built VM Translator.

The Jack Compiler consists of two main components:

1. Jack Analyzer

• The Jack Analyzer translates Jack code into a XML parse tree.
• It performs tokenization, identifying keywords, symbols, identifiers, integer constants, and string constants, and then constructs an xml parse tree that reflects the grammatical structure of the program.

Here are grammar rules for the Jack language:

2. Jack Compiler (Code Generation)

• The Jack Compiler extends the analyzer to directly generate VM code that can be executed by the virtual machine.
• It was implemented by modifying the JackAnalyzer.cpp program, enabling .jack files to compile directly into .vm code.

Key challenges addressed in this project included:

• Handling the construction and manipulation of arrays and objects
• Implementing code generation techniques for expressions and statements
• Designing a recursive compilation engine for nested structures
• Managing symbol tables for class-level and subroutine-level variables
• Implementing memory management for variable allocation and deallocation

Here’s the architecture of the full compiler pipeline:

9 - Jack Operating System

The OS layer is the final component that brings the Hack computer to life, providing high-level abstractions for the hardware modules built in previous stages.

Here are 8 classes that make up the Jack Operating System, implemented entirely in the Jack language that I built earlier:

• Memory→ Provides access to RAM and manages memory allocation for objects.
• Array → Provides a representation for arrays and memory indexing.
• Math → Implements mathematical operations such as multiplication, division, and square root.
• String → Supports string creation, manipulation, and conversion.
• Keyboard → Handles user input from the keyboard.
• Output → Enables writing text to the screen.
• Sys → Implements system-level services, including program initialization and termination.

Challenges for this OS project include:

• Running-time analysis and optimization.
• Resource allocation and deallocation.
• Heap management and garbage control.
• Input handling and textual outputs.
• String processing and overall OS integration.