Help Topics
Hardware Components
The Hack computer (read this first)
Instruction memory (ROM)
Data memory (RAM)
Data register (D)
Address register (A)
Program counter (PC)
Arithmetic-Logic Unit (ALU)
Screen
Keyboard
Machine/Assembly Language
Address instruction
CSJ (compute-store-jump) instruction
CSJ instruction field: compute
CSJ instruction
field: store
CSJ instruction
field: jump
Programming a Jump
Jump-control logic
ALU
ALU calculation
ALU output
ALU output path
Instruction set
Related Topics
Application
Operating system
Jack programming language
Jack compiler
virtual machine
Hardware Components
The Hack Computer:
Hack is a 16-bit computer, equipped with a 32K instruction memory, a 32K RAM, a data register, an address register, a program counter, and an ALU. The computer's I/O system consists of a memory-mapped black-and-white screen (512 rows by 256 columns) and a memory-mapped keyboard. Hack is a general-purpose
computer platform, similar to the computers that power game
machines, cellular telephones, and personal digital assistant (PDA)
machines.
Hack features a sophisticated software hierarchy. The machine and assembly languages are
typical and similar to those of other computers. The high level language, called Jack, is a simple, object-based language, modeled after Java. Jack programs are compiled by the Jack compiler into a virtual machine, modeled after Java's JVM.
Hack uses an operating system which is quite similar to early versions of DOS. The operating system is written in Jack.
The most unique feature of the Hack platform is that it can be built from scratch by anyone who cares to read our book or take our course. The hardware is constructed piece-mill using a hardware simulator, and the software is built in a step-wise fashion using an elaborate set of
API's available in the book site. The entire construction - hardware and software - can be done in one (intense) semester course at the undergraduate computer science level. More relaxed versions of this course are also possible, in which subsets of the machine are constructed by the students, and other hardware and software elements are downloaded as needed from the course site.
The entire platform - hardware and software - can be built on a personal computer, using a suite of hardware and software simulators. All the necessary software tools are available in the book site, so there is no need for anything beyond a typical PC with Windows or Linux.
Instruction memory (ROM):
An array of 32K addressable 16-bit registers, designed to hold and serve machine instructions. Typically, the instruction memory contains the code of a certain application program (e.g. text editor or computer game), as well as the operating system code required to support the application. Taken together, the application code and the O/S code comprise a long list of machine language instructions, each stored in a separate instruction memory location.
The instruction memory unit is designed to continuously output the binary value of the current instruction memory location. This 16-bit pattern codes the instruction that the computer will execute in the current clock cycle. In each cycle, a new instruction memory location is selected by the Program Counter.
In a typical personal computer environment, the computer memory is loaded with a particular application program when the user double-clicks an
icon or types a shell command. In the simulator environment, programs are loaded and executed through the simulator menus.
See also: application, operating system, instruction set, program counter.
Data memory (RAM):
An array of 32K addressable 16-bit registers, designed to hold and serve data. In particular, the data memory unit is designed to continuously output the binary value of the current memory location. The data bus architecture
routes this value to the M/A input of the ALU. The current memory location is selected by the Address Register (A).
The top 16K memory segment is designated to hold variable, array, and object values. The next 8K segment implements a memory-mapped screen. This segment holds 8*1024*16=131,072 bits, each modeling a single pixel in the computer's black-and-white screen.
The next memory register (address 24*K=24,576) is the memory-mapped keyboard segment. This 16-bit value codes the keyboard key pressed last by the user.
The rest of the memory (bottom 32K-16K-8K-1 locations) is not used.
See also: ALU, instruction set, screen, keyboard.
Data register (D):
This 16-bit register is the main "working register" of the computer.
To illustrate, suppose we want to move a value from ROM address 1000 to
ROM address 2000. This is normally done as follows. First, we use the command @1000 to select the first memory location. Next, we use D=M to load M[1000] into the data register. Next, we use @2000 to select the second memory location. Finally, we use M=D. The latter command loads the contents of D into M[2000].
The D register feeds one of the two inputs of the ALU. Hence,
every ALU operation always uses the present value of D as input, although
for many ALU commands this input is irrelevant and thus ignored.
See also: ALU, instruction set.
Address register (A):
This 16-bit register serves two purposes. First, it selects
the current Data Memory location. Specifically, the control bus architecture
feeds the output of the A register into the address input of the
Data Memory unit. As a result of this setting, the Data Memory
unit always outputs the value of the memory location that the A
register "points at".
Second, the A register is the only container in the computer into which the programmer can enter a constant value under program control. This is done by the address instruction, whose format is @constant. This instruction places the 15-bit value of constant in the A register. Subsequent commands can move this value into the D register or into the Data Memory, as needed.
See also: data memory (RAM), address instruction.
Program counter (PC):
This 16-bit counter serves two purposes. First, it selects the
current instruction, i.e. the instruction that will be executed in the current clock cycle. In the course of executing
the current instruction, the PC is updated to select the instruction
that will be executed in the next clock cycle, and so on.
The selection logic is as follows. If the current instruction is not a GOTO, the PC increments by 1. If the current instruction is "GOTO address", the PC is set to address. If the current instruction is "IF condition GOTO address" and condition happens to be true, the PC is set to address; Otherwise, the PC increments by 1. When the computer is reset, the PC is set to 0.
The control bus architecture pipes the output of the PC unit into the
address input of the Instruction Memory unit. As a result of this setting, the
Instruction Memory always outputs the value of the instruction memory location that the PC "points at."
See also: instruction memory, jump-control logic.
Arithmetic-Logic Unit (ALU):
The Hack ALU is designed to calculate 19 generic functions, as follows: f(x,y)=0, 1, -1, x, y, NOT(x), NOT(y), -x, -y, x+1, y+1, x-1, y-1, x+y, x-y, y-x, x AND y, x OR y, x NAND y.
The x input is fed from the D register. The y input is fed from either the current memory register (M) or from the address register (A).
In each clock cycle, the compute part of the current instruction specifies (i) which function the ALU will calculate, and (ii) on which inputs (M or on A -- the other ALU input is always D).
See also: ALU calculation, ALU output, ALU
destination.
Screen:
The simulated screen has 512 rows and 256 columns, featuring 131,072 black-and-white pixels. This resolution is quite sufficient for
rendering simple computer games, text editors, etc.
Programmers write to the screen by calling operating system methods. The O/S features
a typical set of graphics rendering methods like clearScreen, setColor,
drawPixel, etc., and a set of text rendering methods like
printString and println.
These O/S methods, in turn, are designed to write their output into the screen segment of the RAM. The screen itself is memory-mapped, meaning that the simulator continuously refreshes it from the RAM's screen segment.
See also: operating system, Jack programming language.
Keyboard:
The simulated keyboard is the same as the real keyboard. In particular, when the simulator's keyboard button is clicked, the simulator "takes over" and starts capturing the user's keystrokes on the real keyboard.
The keyboard is memory-mapped, meaning that the simulator places the ASCII value of the last
key that the user pressed in a designated 16-bit word in the RAM (address 24,576).
Programmers get the keyboard's input by calling operating systems methods like keyPressed(), readChar(), readLine(), etc.
These O/S methods, in turn, are designed to peek into RAM location 24,576 and return the respective value to the calling method.
See also: operating system, Jack programming language.
Machine/Assembly Language
Address instruction:
Instruction format: @x where x is a 15-bit constant.
This instruction loads the constant x into the address register A. This command
can be used to effect two different operations:
|
- Load the constant x into the computer. The only way to do so is to use @x and then a subsequent command like D=A.
- Select the memory location whose address is x. This is typically done as a preamble for a subsequent compute-store-jump operation (that operates on the current memory location).
|
See also: address register.
CSJ (Compute-Store-Jump) Instruction:
Instruction format: dest = exp; jmp
The "=exp" part of the instruction is mandatory; "dest" and "jmp" are optional.
|
- exp determines which calculation (expression) the ALU is to compute;
- dest determines where the ALU output will be stored (D, A, or M)
- jmp determines which instruction will be executed next
|
For more information, click on the field name.
CSJ instruction exp field: This part of the instruction determines which calculation the ALU will execute
and output in the current clock cycle. There are 30 possibilities:
|
0, 1, -1,
D, M, NOT(D), NOT(M), -D, -M,
D+1, M+1, D-1, M-1, D+M, D-M, M-D,
D AND M, D OR M, D NAND M.
A, NOT(A), -A,
A+1, A-1, D+A, D-A, A-D,
D AND A, D OR A, D NAND A.
|
CSJ instruction dest field: This part of the instruction specifies where the ALU result will be stored. There are eight possibilities:
|
Mnemonic (null) M D A DM AM AD ADM
|
ALU result will be stored:
nowhere
current memory register
data register
address register
data register and current memory register
address register and current memory register
address register and data register
address register, data register, and current memory register
|
CSJ instruction jump field: This part of the instruction tells the computer which instruction to execute next. There are eight possibilities:
|
Mnemonic (null) JGT JEQ JGE JLT JNE JLE JMP
|
ALU result will be stored:
PC++ (no jump, program counter increments by 1)
if ALU>0 set PC=A; else PC++
if ALU=0 set PC=A; else PC++
if ALU>=0 set PC=A; else PC++
if ALU<0 set PC=A; else PC++
if ALU<>>0 set PC=A; else PC++
if ALU<=0 set PC=A; else PC++
set PC=A
|
(ALU, A, and PC refer, respectively, to the ALU result, address register, and the program counter).
Programming a Jump: Suppose that the programmer wants to effect the following behavior: subtract 1 from the value stored in the Data Register (D); if the result is 0, jump to execute the instruction stored in address 217; otherwise, proceed to execute the next instruction. This behavior can be programmed through the following two instructions:
|
@217 =D-1;JEQ
|
// store the constant 217 in the address register
// compute D-1; if the result equals zero, jump
|
The first instruction sets the A register to the "goto address" (that may or may not come into play). The second instruction runs the rest of the show.
See also: address instruction, CSJ instruction
jump field.
Jump-control logic: This hardware unit (not shown in the
simulator) has three inputs: the jump field of the current instruction and the two output bits of the ALU. Taken together, the latter bits indicate weather the ALU result is negative, zero, or positive.
Using this information, the jump-control unit determines weather or not the PC should be
incremented, or set to the value of the address register. The
former will effect a no-jump, the latter will effect a jump.
See also: CSJ instruction jump field, ALU output.
ALU output: The ALU has three outputs: the 16-bit value of the current calculation, also referred to as the ALU result, and two bits labeled zr and ng. The first bit is 1 when the ALU result is zero and 0 otherwise; the second bit is 1 when the ALU result is negative and 0 otherwise.
ALU destination: The ALU result is fed
in parallel to three destinations: the data register D, the address register A, and the current memory location M.
Every one of these three registers is controlled by a load bit that determines weather or not the register will "open up" to accept the new input. Hence, the on/off values of these load bits determine weather or not the ALU result will be accepted by the respective registers D, A, or M.
In each clock cycle, the values of these load bits are specified by the destination part of the current instruction.
See also: CSJ instruction destination field.
The Instruction Set: The instruction format of the compute-store-jump command is dest=exp; jmp, of which exp codes the 6 control bits of the ALU. Although 64 different operations are theoretically possible, only 30 arithmetic/logical operations are actually used. The binary commands and their respective mnemonics are as follows:
|
A/M flag (4th MSB in the 16-bit instruction)=1 |
|
exp |
e |
e |
e |
e |
e |
e |
|
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
-1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
D |
0 |
0 |
1 |
1 |
0 |
0 |
|
M |
1 |
1 |
0 |
0 |
0 |
0 |
A |
Not D |
0 |
0 |
1 |
1 |
1 |
0 |
|
Not M |
1 |
1 |
0 |
0 |
1 |
0 |
Not A |
-D |
0 |
0 |
1 |
1 |
1 |
1 |
|
-M |
1 |
1 |
0 |
0 |
1 |
1 |
-A |
D+1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
M+1 |
1 |
1 |
0 |
1 |
1 |
1 |
A+1 |
D-1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
M-1 |
1 |
1 |
0 |
0 |
0 |
1 |
A-1 |
D+M |
0 |
0 |
0 |
0 |
0 |
1 |
D+A |
D-M |
0 |
1 |
0 |
0 |
1 |
1 |
D-A |
M-D |
0 |
0 |
0 |
1 |
1 |
1 |
A-D |
D and M |
0 |
0 |
0 |
0 |
0 |
0 |
D and A |
D or M |
0 |
1 |
0 |
1 |
1 |
0 |
D or A |
D nand M |
0 |
0 |
0 |
0 |
1 |
0 |
D nand A |
|
e |
e |
e |
e |
e |
e |
exp |
|
A/M flag (4th MSB in the 16-bit instruction)=0 |
|
Related Topics
Application: The term "application" has several simultaneous meanings:
|
- User view: an application is a software program that makes the computer come alive and do something useful like bounce a ball on the screen or write the text "Hello World".
The application is controlled through the keyboard.
- Programmer view: an application is a collection of classes and methods, designed to effect a certain operation like bouncing a ball on the screen or writing the text "Hello World". Applications are written in a high-level language like Java.
- Compiler view: an application is a collection of high-level classes and methods that must be translated into the computer's machine language.
- Hardware view: an application is a long list of machine language instructions stored in the instruction memory. These instructions tell the computer what to do.
|
As far as the compiler and the hardware are concerned, the operating system is yet another application.
See also: Jack programming language, operating system, compiler.
Operating System: The operating system is a collection of classes and methods, designed to interface between
the application program and the computer resources. In particular, the O/S features the following services:
|
- Graphics-oriented output (clearScreen, drawPixel, drawLine, etc.)
- Text-oriented output (moveCursor, printChar, printString, etc.)
- Keyboard handling (keyPressed, readChar, readLine, etc.)
- Memory management (peek, poke, alloc, deAlloc, etc.)
- System services (init, halt, wait, error, etc.)
- Math functions (multiply, divide, sqrt, etc.)
|
In addition, the O/S features libraries for creating and manipulating high-level objects, e.g.:
|
- Array (new, dispose, etc.)
- String (new, dispose, length, charAt, setCharAt, etc.)
|
The O/S methods are divided into four levels. Level 0 methods are needed for the compiler; Level 1 methods provide core services; Level 2 methods are needed for basic applications; Level 3 is all the rest.
The students implement various parts of the operating system in the Jack programming language. In a typical course, only level 2 methods will be written by the students. However, the students can write the entire system, as well as extend it with additional services.
See also: Jack programming language.
Jack Programming Language: In the Hack computer, application programs are normally written in a high-level language called Jack. The computer's operating system is also written in Jack.
Jack is a simple, object-based language, modeled after Java. In designing it, we sought a balance between a modern and friendly language, on the one hand, and a language for which a compiler can be easily written, on the other.
Students with object-oriented programming experience can become Jack programmers in a few hours of practice. Having acquired this skill, they can quickly proceed to develop applications and operating system services, using API's that we supply.
See also: operating system, compiler.
Jack Compiler: The Jack compiler translates Jack programs (one or more classes) into virtual machine code.
The compiler is implemented by the students from an API that we supply. The compiler can be written in any language like Java, C++, or Visual Basic.
See also: virtual machine, Jack programming language.
The Virtual Machine: Following the Java model, high-level programs are not translated directly into machine language. Rather, they are first translated by the compiler into an intermediate VM code.
The VM code consists of commands like POP and PUSH, designed to operate on an abstract stack machine.
The VM code is then translated into machine language by JcVM - a program modeled after Java's JVM. The
JacVM implementation maps the stack machine elements on the RAM, and translates each VM code command into several machine language commands that operate on the RAM.
|