Lec08 HackML
Lec08 HackML
www.nand2tetris.org
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 1
Where we are at:
Assembly
Language
Assembler
Chapter 6
abstract interface
Computer
Machine Architecture
abstract interface
Language
Chapters 4 - 5
Hardware Gate Logic
abstract interface
Platform Chapters 1 - 3 Electrical
Chips & Engineering
Hardware Physics
Logic Gates
hierarchy
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 2
Machine language
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 3
Machine language
Another duality:
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 4
Machine language
◼ Binary version
◼ Symbolic version
Memory
Loose definition: state
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 5
Lecture plan
⚫ Symbolic version
⚫ Binary version
◼ Perspective
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 6
Typical machine language commands (3 types)
◼ ALU operations
◼ Memory access operations
(addressing mode: how to specify operands)
⚫ Immediate addressing, LDA R1, 67 // R1=67
⚫ Direct addressing, LD R1, 67 // R1=M[67]
⚫ Indirect addressing, LDI R1, R2 // R1=M[R2]
◼ Flow control operations
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 7
Typical machine language commands (a small sample)
ADD R1,R2,R3 // R1 R2 + R3
NOP // Do nothing
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 8
The Hack computer
A 16-bit machine consisting of the following elements:
reset Screen
Computer
Keyboard
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 9
The Hack computer
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 10
The Hack computer
A 16-bit machine consisting of the following elements:
inM
writeM
Instruction outM Data
instruction
CPU
Memory Memory
addressM
(ROM32K) (Memory)
pc
reset
Both memory chips are 16-bit wide and have 15-bit address space.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 11
The Hack computer (CPU)
A 16-bit machine consisting of the following elements:
ALU output
C C
C
D
D
C C
decode
outM
ALU
C
A
Mux
A
C
instruction A/M
Mux
M
inM
C writeM
A
addressM
C
reset
A
PC pc
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 12
The Hack computer
A 16-bit machine consisting of the following elements:
Control: The ROM is loaded with a sequence of 16-bit instructions, one per memory
location, beginning at address 0. Fetch-execute cycle: later
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 13
The A-instruction
@value // A value
Example: @21
Effect:
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 14
The A-instruction
@value // A value
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 15
The C-instruction
comp:
0, 1, -1, D, A, !D, !A, -D, -A, D+1, A+1, D-1, A-1, D+A, D-A, A-D, D&A, D|A
M, !M, -M, M+1, M-1, D+M, D-M, M-D, D&M, D|M
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 17
The C-instruction
Hack commands:
A-command: @value // set A to value
C-command: dest = comp ; jump // dest = and ;jump
// are optional
Where:
comp =
0 , 1 , -1 , D , A , !D , !A , -D , -A , D+1 , A+1 , D-1, A-1 , D+A , D-A , A-D , D&A , D|A,
M, !M , -M , M+1, M-1 , D+M, D-M, M-D, D&M, D|M
dest = M, D, A, MD, AM, AD, AMD, or null
jump = JGT , JEQ , JGE , JLT , JNE , JLE , JMP, or null
In the command dest = comp; jump, the jump materialzes if (comp
jump 0) is true. For example, in D=D+1,JLT, we jump if D+1 < 0.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 19
The Hack machine language
symbolic binary
@17 0000 0000 0001 0001
translate
D+1; JLE 1110 0111 1100 0110
execute
hardware
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 20
The A-instruction
symbolic binary
@value 0value
◼ value is a non-negative decimal ◼ value is a 15-bit binary number
number <= 215-1 or
Example
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 21
The C-instruction
symbolic binary
dest = comp ; jump 111A C1C2C3C4 C5C6 D1D2 D3J1J2J3
]
comp dest jump
not used
opcode
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 22
The C-instruction
111A C1C2C3C4 C5C6 D1D2 D3J1J2J3
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 23
The C-instruction
111A C1C2C3C4 C5C6 D1D2 D3J1J2J3
A D M
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 24
The C-instruction
111A C1C2C3C4 C5C6 D1D2 D3J1J2J3
< = >
jump j j j effect:
null 0 0 0 no jump
JGT 0 0 1 if comp > 0 jump
JEQ 0 1 0 if comp = 0 jump
JGE 0 1 1 if comp ≥ 0 jump
JLT 1 0 0 if comp < 0 jump
JNE 1 0 1 if comp ≠ 0 jump
JLE 1 1 0 if comp ≤ 0 jump
JMP 1 1 1 Unconditional jump
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 25
Hack assembly/machine language
Source code (example) Target code
// Computes 1+...+RAM[0] 0000000000010000
// And stored the sum in RAM[1] 1110111111001000
@i 0000000000010001
M=1 // i = 1 1110101010001000
@sum 0000000000010000
M=0 // sum = 0 1111110000010000
(LOOP) 0000000000000000
@i // if i>RAM[0] goto WRITE 1111010011010000
D=M 0000000000010010
@R0 1110001100000001
D=D-M 0000000000010000
@WRITE 1111110000010000
D;JGT assemble 0000000000010001
@i // sum += i 1111000010001000
D=M 0000000000010000
@sum Hack assembler 1111110111001000
M=D+M 0000000000000100
@i // i++ or CPU emulator 1110101010000111
M=M+1 0000000000010001
@LOOP // goto LOOP 1111110000010000
0;JMP 0000000000000001
(WRITE) 1110001100001000
@sum 0000000000010110
D=M 1110101010000111
@R1
M=D // RAM[1] = the sum
(END)
@END We will focus on writing the assembly code.
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 26
Working with registers and memory
◼ D: data register
◼ A: address/data register
◼ M: the currently selected memory cell, M=RAM[A]
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 27
Hack programming exercises
1. Set D to A-1
3. Set D to 19
4. D++
5. D=RAM[17]
6. Set RAM[5034] to D - 1
8. Add 1 to RAM[7],
and store the result in D.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 28
Hack programming exercises
Binary
Add.asm (example)
0000000000000000
// Computes: RAM[2] = RAM[0] + RAM[1]
1000010010001101
// D = RAM[0] 0000000000000001
@0 1010011001100001
D=M Load into the 0000000000000010 Execute
// D = D + RAM[1] CPU emulator 1110010010010011
@1
D=D+M
// RAM[2] = D
@2
M=D When loading a symbolic program
into the CPU emulator, the
emulator translates it into binary
code (using a built-in assembler)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 30
Terminate properly
00: @0
@6
01: D=M
0; JMP 02: @1
03: D=D+M
04: @2
05: M=D
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 31
Built-in symbols
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 32
Branching
// Program: branch.asm
// if R0>0
// R1=1
// else
// R1=0
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 33
Branching
// Program: branch.asm
// if R0>0
// R1=1
// else
// R1=0
@R0
D=M // D=RAM[0]
@8
D; JGT // If R0>0 goto 8
@R1
M=0 // R1=0
@10
0; JMP // go to end
@R1
M=1 // R1=1
@10
0; JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 34
Branching
// Program: branch.asm
// if R0>0
// R1=1
// else
// R1=0
@R0
D=M // D=RAM[0]
@8
D; JGT // If R0>0 goto 8
@R1
M=0 // R1=0
@10
0; JMP // go to end
@R1
M=1 // R1=1
@10
0; JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 35
Branching with labels
// Program: branch.asm 0 @0
// if R0>0
// R1=1
1 D=M
// else 2 @8
// R1=0 3 D;JGT
4 @1
@R0 5 M=0
D=M // D=RAM[0] 6 @10
@POSTIVE refer a label 7
0;JMP
D; JGT // If R0>0 goto 8 8
@1
9
@R1 10 M=1
M=0 // R1=0
11 @10
@END
0; JMP // go to end 12 0; JMP
(POSTIVE)
declare a label 13
@R1
M=1 // R1=1
14
(END) 15
@10 16
0; JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 36
IF logic – Hack style
if condition { D condition
code block 1 @IF_TRUE
} else { D;JEQ
code block 2
code block 2
}
@END
code block 3
0;JMP
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 37
Coding examples (practice)
1. goto 50
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 38
Coding examples (practice)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 39
variables
// Program: swap.asm
// temp = R1
// R1 = R0
// R0 = temp
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 40
variables
// Program: swap.asm
// temp = R1 ◼ When a symbol is encountered,
// R1 = R0 the assembler looks up a symbol
// R0 = temp
table
@R1
◼ If it is a new label, assign a
D=M
@temp number (address of the next
M=D // temp = R1 available memory cell) to it.
@R0 ◼ For this example, temp is
D=M assigned with 16.
@R1
M=D // R1 = R0 ◼ If the symbol exists, replace it
with the number recorded in
@temp
D=M the table.
@R0
M=D // R0 = temp
1. sum = 0
2. j = j + 1
3. q = sum + 12 – j
4. arr[3] = -1
5. arr[j] = 0
6. arr[j] = 17
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 42
Hack program (exercise)
Exercise: Implement the following tasks
using Hack commands:
1. @sum 4. @arr 6. @j
1. sum = 0
M=0 D=M D=M
2. j = j + 1 2. @j @3 @arr
M=M+1 A=D+A D=D+M
3. q = sum + 12 – j
3. @sum M=-1 @ptr
4. arr[3] = -1 D=M 5. @j M=D
5. arr[j] = 0
@12 D=M @17
D=D+A @arr D=A
6. arr[j] = 17
@j A=D+M @ptr
D=D-M M=0 A=M
@q M=D
M=D
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 43
WHILE logic – Hack style
❑ False is represented by 0
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 44
Complete program example
C language code:
// Adds 1+...+100.
int i = 1;
int sum = 0;
while (i <= 100){
sum += i;
i++;
}
❑ Variables: lower-case
❑ Labels: upper-case
❑ Commands: upper-case
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 45
Complete program example
Pseudo code: Hack assembly code:
i = 1; // Adds 1+...+100.
sum = 0; @i // i refers to some RAM location
M=1 // i=1
LOOP:
@sum // sum refers to some RAM location
if (i>100) goto END
M=0 // sum=0
sum += i; (LOOP)
i++; @i
goto LOOP D=M // D = i
END: @100
D=D-A // D = i - 100
Hack assembly convention: @END
D;JGT // If (i-100) > 0 goto END
❑ Variables: lower-case @i
D=M // D = i
❑ Labels: upper-case @sum
M=D+M // sum += i
❑ Commands: upper-case @i
M=M+1 // i++
@LOOP
0;JMP // Got LOOP
Demo
(END)
CPU emulator
@END
0;JMP // Infinite loop
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 46
Example
// for (i=0; i<n; i++) Pseudo code:
// arr[i] = -1;
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 47
Example
// for (i=0; i<n; i++) Pseudo code:
// arr[i] = -1;
i = 0
(LOOP)
if (i-n)>=0 goto END
arr[i] = -1
i++
goto LOOP
(END)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 48
Example
// for (i=0; i<n; i++) Pseudo code:
// arr[i] = -1;
@i i = 0
M=0
(LOOP) (LOOP)
@i if (i-n)>=0 goto END
D=M arr[i] = -1
@n i++
D=D-M goto LOOP
@END (END)
D; JGE
@arr
D=M
@i
A=D+M
M=-1
@i
M=M+1
@LOOP
0; JMP
(END)
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 49
Perspective
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 4: Machine Language slide 50