CSCE-312 Day 1 Introduction
L19 – Assembler Basic Concepts
The Big Picture
abstraction
VM translator
human
thought
VM code
compiler
abstraction
OS
write a program
abstraction
high-level
language
computer architecture
abstraction
CPU, RAM,
chipset
abstraction
elementary logic gates
abstraction
Nand
comb. and
seq. Logic
combinational logic
digital design
assembler
machine language
software hierarchy
hardware platform
p1
p2
p3
p4
p5
p6
Credit: www.nand2tetris.org
2
Program Translation Process
3
Machine Language
Courtesy: nand2tetris.org
if ((x+width)>511) {
let x=511-width;
}
High Level Language code
Compiler
3
Assembly process
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
…
Machine Language
assembler
@i
M=1 // i = 1
@sum
M=0 // sum = 0
(LOOP)
@i // if i>RAM[0]
D=M // GOTP WRITE
@R0
D=D-M
@WRITE
D;JGT
… // Etc.
Assembly Language
assemble
mario.asm
into
mario.bin
run
4
Credit: www.nand2tetris.org
Why care about assemblers?
Assemblers are the first rung up the software hierarchy ladder
An assembler is a translator of a simple language
Writing an assembler = low-impact practice for writing compilers.
Credit: www.nand2tetris.org
5
5
Assembler: lecture plan
The assembly process
The Hack assembly language
The assembly process: instructions
The assembly process: symbols
Developing an assembler
Project 6 overview
6
Credit: www.nand2tetris.org
The translator’s challenge (overview)
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
…
Assembler
Hack assembly code
(source language)
What are the rules of the game?
Hack binary code
(source language)
// Computes RAM[1]=1+…+RAM[0]
@i
M=1 // i = 1
@sum
M=0 // sum = 0
(LOOP)
@i // if i>RAM[0] goto STOP
D=M
@R0
D=D-M
@STOP
D;JGT
@i // sum += i
D=M
@sum
M=D+M
@i // i++
M=M+1
@LOOP // goto LOOP
0;JMP
…
Credit: www.nand2tetris.org
7
7
The translator’s challenge (overview)
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
…
Hack assembly code
(source language)
Hack binary code
(source language)
Based on the syntax rules of:
The source language
The target language
// Computes RAM[1]=1+…+RAM[0]
@i
M=1 // i = 1
@sum
M=0 // sum = 0
(LOOP)
@i // if i>RAM[0] goto STOP
D=M
@R0
D=D-M
@STOP
D;JGT
@i // sum += i
D=M
@sum
M=D+M
@i // i++
M=M+1
@LOOP // goto LOOP
0;JMP
…
Assembler
Credit: www.nand2tetris.org
8
8
Assembly example
Assembler = simple translator
Translates each assembly command into binary machine instructions
Handles symbols (e.g. i, sum, LOOP, …)
Handles Whitespace and Comments
Credit: www.nand2tetris.org
@ sum
D = M
@ foo
M = D
9
In the example shown in green box, an assembler will extract the program semantics starting with the first line @sum which will bring the variable sum location (address) into A register. The instruction is syntactically correct and has a semantic meaning as aforementioned. However, the next statement D=55 (even though it appears semantically correct i.e. assign 55 to Register D is not syntactically correct since HACK assembly language requires any non0, non-+1 number to be indirectly coming from register A.
Basic Assembler Logic
Repeat
Read the next assembly language command
Break it into its different fields
Lookup the binary code for every field
Combine these codes into a single machine language command
Output the machine language command
Until EOF reached
Credit: www.nand2tetris.org
@4
D = 0
M = D
000 0000000 000 100
111 0101010 010 000
111 1001100 001 000
A: @
C: dest = comp ; jump
10
Hack language specification: A-instruction
Example:
0000000000010101
Binary syntax:
0valueInBinary
Where value is either
a non-negative decimal constant or
a symbol referring to such a constant
@21
Examples:
@value
Symbolic syntax:
@foo
Credit: www.nand2tetris.org
11
11
Hack language specification: C-instruction
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
dest = comp ; jump
Credit: www.nand2tetris.org
12
Hack language specification: C-instruction
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
dest = comp ; jump
Credit: www.nand2tetris.org
13
Hack language specification: symbols
symbol value symbol value
R0 0 SP 0
R1 1 LCL 1
R2 2 ARG 2
... ... THIS 3
R15 15 THAT 4
SCREEN 16384
KBD 24576
Label declaration: (label)
Pre-defined symbols:
Variable declaration: @variableName
Credit: www.nand2tetris.org
14
The Hack language: a translator’s perspective
Assembly program elements:
White space
Empty lines / indentation
Line comments
In-line comments
Instructions
A-instructions
C-instructions
Symbols
References
Label declarations
// Computes RAM[1] = 1 + ... + RAM[0]
@i
M=1 // i = 1
@sum
M=0 // sum = 0
(LOOP)
@i // if i>RAM[0] goto STOP
D=M
@R0
D=D-M
@STOP
D;JGT
@i // sum += i
D=M
@sum
M=D+M
@i // i++
M=M+1
@LOOP // goto LOOP
0;JMP
(STOP)
@sum
D=M
@R1
M=D // RAM[1] = the sum
(END)
@END
0;JMP
Assembly program
Credit: www.nand2tetris.org
15
15
The Hack language: a translator’s perspective
Challenges:
Handling…
White space
Instructions
Symbols
// Computes RAM[1] = 1 + … + RAM[0]
@i
M=1 // i = 1
@sum
M=0 // sum = 0
(LOOP)
@i // if i>RAM[0] goto STOP
D=M
@R0
D=D-M
@STOP
D;JGT
@i // sum += i
D=M
@sum
M=D+M
@i // i++
M=M+1
@LOOP // goto LOOP
0;JMP
(STOP)
@sum
D=M
@R1
M=D // RAM[1] = the sum
(END)
@END
0;JMP
Assembly program
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
Assembler
Credit: www.nand2tetris.org
16
16
Symbols
// Computes RAM[1] = 1 + … + RAM[0]
@i
M=1 // i = 1
@sum
M=0 // sum = 0
(LOOP)
@i // if i>RAM[0] goto STOP
D=M
@R0
D=D-M
@STOP
D;JGT
@i // sum += i
D=M
@sum
M=D+M
@i // i++
M=M+1
@LOOP // goto LOOP
0;JMP
(STOP)
@sum
D=M
@R1
M=D // RAM[1] = the sum
(END)
@END
0;JMP
Program with symbols
Simplifying assumption:
Let’s deal with symbols later.
Challenges:
Handling…
White space
Instructions
Symbols
Credit: www.nand2tetris.org
17
17
Handling programs without symbols
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
// Computes RAM[1] = 1 + … + RAM[0]
@16
M=1 // i = 1
@17
M=0 // sum = 0
@16 // if i>RAM[0] goto STOP
D=M
@0
D=D-M
@18
D;JGT
@16 // sum += i
D=M
@17
M=D+M
@16 // i++
M=M+1
@4 // goto LOOP
0;JMP
@17
D=M
@1
M=D // RAM[1] = the sum
@22
0;JMP
Assembly program (without symbols)
Assembler
for symbol-less Hack programs
Challenges:
Handling…
White space
Instructions
Credit: www.nand2tetris.org
18
18
Handling white space
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
// Computes RAM[1] = 1 + … + RAM[0]
@16
M=1 // i = 1
@17
M=0 // sum = 0
@16 // if i>RAM[0] goto STOP
D=M
@0
D=D-M
@18
D;JGT
@16 // sum += i
D=M
@17
M=D+M
@16 // i++
M=M+1
@4 // goto LOOP
0;JMP
@17
D=M
@1
M=D // RAM[1] = the sum
@22
0;JMP
Assembly program (without symbols)
Challenges:
Handling…
White space
Instructions
Assembler
for symbol-less Hack programs
Credit: www.nand2tetris.org
19
19
Handling white space
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
// Computes RAM[1] = 1 + … + RAM[0]
@16
M=1 // i = 1
@17
M=0 // sum = 0
@16 // if i>RAM[0] goto STOP
D=M
@0
D=D-M
@18
D;JGT
@16 // sum += i
D=M
@17
M=D+M
@16 // i++
M=M+1
@4 // goto LOOP
0;JMP
@17
D=M
@1
M=D // RAM[1] = the sum
@22
0;JMP
Assembly program (without symbols)
Challenges:
Handling…
White space
Instructions
Assembler
for symbol-less Hack programs
Handling white space:
Ignore it!
Credit: www.nand2tetris.org
20
20
Handling instructions
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
Assembly program (without symbols)
@16
M=1
@17
M=0
@16
D=M
@0
D=D-M
@18
D;JGT
@16
D=M
@17
M=D+M
@16
M=M+1
@4
0;JMP
@17
D=M
@1
M=D
@22
0;JMP
Challenges:
Handling…
White space
Instructions
Assembler
for symbol-less Hack programs
Credit: www.nand2tetris.org
21
21
Translating A-instructions
Example:
0000000000010101
Binary syntax:
0valueInBinary
Translation to binary:
If value is a decimal constant, generate the equivalent binary constant
If value is a symbol, later.
Where value is either
a non-negative decimal constant or
a symbol referring to such a constant (later)
@21
Examples:
@value
Symbolic syntax:
@foo
Credit: www.nand2tetris.org
22
22
Translating C-instructions
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
Example:
MD=D+1
Symbolic:
Binary:
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
dest = comp ; jump
Credit: www.nand2tetris.org
23
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
dest = comp ; jump
Translating C-instructions
Example:
MD=D+1
Symbolic:
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
Credit: www.nand2tetris.org
24
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
dest = comp ; jump
Translating C-instructions
Example:
MD=D+1
Symbolic:
111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
Credit: www.nand2tetris.org
25
Translating C-instructions
Example:
MD=D+1
Symbolic:
111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
26
Translating C-instructions
Example:
MD=D+1
Symbolic:
111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
27
Translating C-instructions
Example:
MD=D+1
Symbolic:
111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
28
Translating C-instructions
Example:
MD=D+1
Symbolic:
1110011111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
29
Translating C-instructions
1110011111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
Example:
MD=D+1
Symbolic:
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
30
Example:
MD=D+1
Symbolic:
Translating C-instructions
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
1110011111
Binary:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
31
Translating C-instructions
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
Example:
MD=D+1
Symbolic:
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
1110011111
Binary:
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
32
Example:
MD=D+1
Symbolic:
Translating C-instructions
1110011111011
Binary:
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
33
Translating C-instructions
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
Example:
MD=D+1
Symbolic:
1110011111011
Binary:
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
34
Example:
MD=D+1
Symbolic:
Translating C-instructions
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
1110011111011
Binary:
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
35
Example:
MD=D+1
Symbolic:
Translating C-instructions
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
1110011111011
Binary:
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
36
Example:
MD=D+1
Symbolic:
Translating C-instructions
1110011111011000
Binary:
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
37
Translating C-instructions
1110011111011000
Binary:
dest d1 d2 d3 effect: the value is stored in:
null 0 0 0 The value is not stored
M 0 0 1 RAM[A]
D 0 1 0 D register
MD 0 1 1 RAM[A] and D register
A 1 0 0 A register
AM 1 0 1 A register and RAM[A]
AD 1 1 0 A register and D register
AMD 1 1 1 A register, RAM[A], and D register
jump j1 j2 j3 effect:
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out ≥ 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out ≠ 0 jump
JLE 1 1 0 if out ≤ 0 jump
JMP 1 1 1 Unconditional jump
comp c1 c2 c3 c4 c5 c6
0 1 0 1 0 1 0
1 1 1 1 1 1 1
-1 1 1 1 0 1 0
D 0 0 1 1 0 0
A M 1 1 0 0 0 0
!D 0 0 1 1 0 1
!A !M 1 1 0 0 0 1
-D 0 0 1 1 1 1
-A -M 1 1 0 0 1 1
D+1 0 1 1 1 1 1
A+1 M+1 1 1 0 1 1 1
D-1 0 0 1 1 1 0
A-1 M-1 1 1 0 0 1 0
D+A D+M 0 0 0 0 1 0
D-A D-M 0 1 0 0 1 1
A-D M-D 0 0 0 1 1 1
D&A D&M 0 0 0 0 0 0
D|A D|M 0 1 0 1 0 1
a=0 a=1
Example:
MD=D+1
Symbolic:
dest = comp ; jump
Symbolic syntax:
1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
Binary syntax:
Credit: www.nand2tetris.org
38
The overall assembly logic
For each instruction
Parse the instruction:
break it into its underlying fields
A-instruction:
translate the decimal value into a binary value
C-instruction:
for each field in the instruction, generate the corresponding binary code;
Assemble the translated binary codes into a complete 16-bit machine instruction
Write the 16-bit instruction to the output file.
@16
M=1
@17
M=0
@16
D=M
@0
D=D-M
@18
D;JGT
@16
D=M
@17
M=D+M
@16
M=M+1
@4
0;JMP
@17
D=M
@1
M=D
@22
0;JMP
Assembly program
39
Credit: www.nand2tetris.org
The overall assembly logic
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
Resulting code:
@16
M=1
@17
M=0
@16
D=M
@0
D=D-M
@18
D;JGT
@16
D=M
@17
M=D+M
@16
M=M+1
@4
0;JMP
@17
D=M
@1
M=D
@22
0;JMP
Assembly program
Credit: www.nand2tetris.org
40
40
The overall assembly logic
0000000000010000
1110111111001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000000000000
1111010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111
0000000000010001
1111110000010000
0000000000000001
1110001100001000
0000000000010110
1110101010000111
Hack machine code
@16
M=1
@17
M=0
@16
D=M
@0
D=D-M
@18
D;JGT
@16
D=M
@17
M=D+M
@16
M=M+1
@4
0;JMP
@17
D=M
@1
M=D
@22
0;JMP
Assembly program
Disclaimer
The source code contains no symbols
Resulting code:
Credit: www.nand2tetris.org
41
41
Assembler: lecture plan
Assembler logic (basic)
The Hack assembly language
The assembly process: instructions
The assembly process: symbols
Developing an assembler
Project 6 overview
42
Credit: www.nand2tetris.org
Remaining Discussion in L20
...
push x
push width
add
push 511
gt
if-goto L1
goto L2
L1:
push 511
push width
sub
pop x
L2:
...
// push 511
@511
D=A // D=511
@SP
A=M
M=D // *SP=D
@SP
M=M+1 // SP++
Virtual machine program
Assembly program
0000000000000000
1110110010001000
Executable
VM
translator
Assembler
push 511
@SP
M=M+1 // SP++
/docProps/thumbnail.jpeg