04. Machine Language

术语

机器语言（Machine Language）一种约定的形式，用来对底层程序进行编码，从而形成一系列机器指令，应用这些指令，程序员可以命令处理器执行算数和逻辑操作，在内存中进行存取操作，让数据在寄存器之间传递，验证布尔表达式的值，等等。

内存（Memory）储存数据和指令的硬件设备。一个连续的固定宽度的单元序列，也称为字（word）或内存单元。每个内存单元都有一个唯一的地址。

CPU，中央处理器（Central Processing Unit）执行一组固定操作的设备，包括算数和逻辑操作，内存存取操作和控制操作。

寄存器（Register）可以看做处理器的一个本地高速内存，使得处理器可以快速地存取数据。

汇编语言（Assembly Language）一种低级编程语言，与机器语言一一对应，但使用助记符来表示操作和地址。

汇编编译器（Assembler）一种程序，将汇编语言代码翻译成机器语言代码。

直接寻址（Direct Addressing）一种寻址方式，指令中直接包含了操作数的地址。

立即寻址（Immediate Addressing）一种寻址方式，指令中直接包含了操作数的值。

间接寻址（Indirect Addressing）一种寻址方式，指令中包含了一个地址，这个地址指向了操作数的实际地址。

Hack

Hack 是一个基于冯诺依曼架构的 16 位计算机，由一个 CPU、两个独立的内存模块（指令内存和数据内存，16 位宽，15 位地址空间，最大地址 32K 的 16-bit word），以及两个内存映射 I/O 设备（键盘和屏幕）组成。

Hack 计算机有两个寄存器，A 寄存器和 D 寄存器。可以显式操控 A=D-1 或 D=!A。

A 既可以作为数据寄存器也可以作为地址寄存器。D仅用来存储数据值。

15 位地址 + 数据肯定大于 16 位指令，所以内存的存取指令是对隐式的内存地址 M 进行操作。规定 M 代表 A 寄存器中存储的地址所指向的内存单元。比如想要执行 D=Memory[516]-1 可以现将 A 寄存器设置为 516，然后执行 D=M-1。

任何 jump 操作都是跳转到 A 寄存器中存储的地址。如果要执行 goto 35 要先将 A 的值设置为 35，然后执行无需描述地址的 goto 命令。

A 指令

A 指令 @value 用于将 value 载入到 A 寄存器中。如果 sum 代表内存地址 17，那么 @sum 和 @17 都将具有 A <- 17 的功能。

二进制表示：0vvv vvvv vvvv vvvv，其中 v = 0 or 1。

比如 1 到 100 的连加：

asm

@i       // i 指代某个内存单元
M=1      // i=1
@sum     // sum 指代某个内存单元
M=0      // sum=0
(LOOP)
@i       // i
D=M      // D=i
@100     // 100
D=D-A    // D=i-100
@END
D;JGT    // 如果 D>0 则跳转到 END
@i
D=M      // D=i
@sum
M=D+M    // sum=sum+i
@i
M=M+1    // i=i+1
@LOOP
0;JMP    // 无条件跳转到 LOOP
(END)
@END
0;JMP    // 无限循环，结束 Hack 程序执行的标准方式

C 指令

C 指令几乎包含要做的所有事情。

dest=comp;jump 其中 dest 和 jump 是可选的，如果 dest 为空，则没有等号；如果 jump 为空，则没有分号。

二进制表示：111 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3，其中

comp 域的 a 位和 c1-c6 位指定了 ALU 的计算功能
dest 域的 d1-d3 位指定了计算后的结果要存储到哪里
jump 域的 j1-j3 位指定了跳转条件

TIP

通过最高位的 0 和 1 来区分 A 指令和 C 指令
C 指令的 a 位的 0 或 1 只用来区分是 A 还是 M 的值参与计算
d1-d3 分别代表 A、D、M 三个目的地
j1-j3 分别代表 <0、=0、>0 三种条件，具体是否跳转仍需要 ALU 的计算结果参与

a=0 助记符	c1 c2 c3 c4 c5 c6	a=1 助记符
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	1 1 0 0 0 0	M
!D	0 0 1 1 0 1
!A	1 1 0 0 0 1	!M
-D	0 0 1 1 1 1
-A	1 1 0 0 1 1	-M
D+1	0 1 1 1 1 1
A+1	1 1 0 1 1 1	M+1
D-1	0 0 1 1 1 0
A-1	1 1 0 0 1 0	M-1
D+A	0 0 0 0 1 0	D+M
D-A	0 1 0 0 1 1	D-M
A-D	0 0 0 1 1 1	M-D
D&A	0 0 0 0 0 0	D&M
D\|A	0 1 0 1 0 1	D\|M

d1 d2 d3	助记符	目的地（A D M 存储计算后的值）
0 0 0	Null	不存储
0 0 1	M	Memory[A]
0 1 0	D	D 寄存器
0 1 1	MD	D 寄存器和 Memory[A]
1 0 0	A	A 寄存器
1 0 1	AM	A 寄存器和 Memory[A]
1 1 0	AD	A 寄存器和 D 寄存器
1 1 1	AMD	A 寄存器、Memory[A] 和 D 寄存器

j1 j2 j3	助记符	作用（< = >）
0 0 0	Null	不跳转
0 0 1	JGT	if out > 0 jump
0 1 0	JEQ	if out = 0 jump
0 1 1	JGE	if out >= 0 jump
1 0 0	JLT	if out < 0 jump
1 0 1	JNE	if out != 0 jump
1 1 0	JLE	if out <= 0 jump
1 1 1	JMP	无条件跳转

符号

符号 R0 到 R15 来代表 0 到 15 号 RAM 地址。

同时，符号 SP、LCL、ARG、THIS 和 THAT 来代表 0 到 4 号 RAM 地址。

符号 SCREEN 和 KBD 来代表 16384（0x4000）和 24576（0x6000）号 RAM 地址，分别是屏幕和键盘的内存映像的基地址。

标签符号 (Xxx) 用户自定义的符号，用于标记 goto 命令跳转的目的地址，甚至在定义之前就可以使用。

变量符号，如果不是上述符号，那么就会被看做是变量，汇编程序会赋予其独立的内存地址（从 RAM 地址 16，即 0x0010 开始）。

屏幕

Hack 计算机有一个 256 行 × 512 列像素的黑白屏幕，每行用 32 个 16-位字来表示屏幕的内容由 RAM 基地址 16384（0x4000）的 8K 内存映射来表示，所以具体地址范围是 0x4000-0x5FFF。

asm

// 在屏幕左上角画一个黑点
@SCREEN
M=1

键盘

Hack 计算机与物理键盘之间通过 RAM 基地址 24576（0x6000）的单字内存映射来进行交互。

敲击键盘上的一个键会在 RAM[24576] 中留下一个对应的 16 位 ASCII 码值。

ASCII Table

还有下面表格中的特殊键：

按键	编码
newline	128
backspace	129
left arrow	130
up arrow	131
right arrow	132
down arrow	133
home	134
end	135
page up	136
page down	137
insert	138
delete	139
esc	140
f1-f12	141-152

asm

@KBD
D=M      // D=RAM[24576]，即键盘输入的 ASCII

语法规约

二进制文件，如 Prog.hack，包含了 Hack 机器语言指令的二进制表示，每行一个指令。每条指令都是 16 位宽的二进制数，使用 ASCII 字符 '0' 和 '1' 来表示。

汇编语言文件，如 Prog.asm，每行代表一个指令或者一个符号定义。

常数和符号：常数必须是非负且十进制的整数；用户自定义符号可以由任意字母、数字、下划线、点、美元符号、冒号构成，但不能以数字开头
注释：以 // 开头的文本被视为注释，直到行尾结束
空格：空格字符以及空行被忽略
大小写：所有的汇编助记符必须大写；用户自定义标签和变量则区分大小写，一般标签大写，变量小写

Project 04

Mult.asmMultSwap.asmFill.asm

asm

// Multiplies R0 and R1 and stores the result in R2.
// (R0, R1, R2 refer to RAM[0], RAM[1], and RAM[2], respectively.)
// The algorithm is based on repetitive addition.
@i
M=0     // i=0
@R2
M=0     // R2=0

(LOOP)
@R0
D=M     // D=R0
@i
D=D-M   // D=R0-i
@END
D;JEQ   // if R0-i=0, goto END

@R1
D=M     // D=R1
@R2
M=D+M   // R2+=R1

@i
M=M+1   // i++
@LOOP
0;JMP   // goto LOOP

(END)
@END
0;JMP   // infinite loop to end the program

asm

// 比较大小，较小的数作为 count，较大的数作为 addend，可以减少循环次数
@R2
M=0

@R0
D=M
@R1
D=D-M   // D=R0-R1
@SWAP
D;JLE   // if R0<=R1, no swap

// R0>R1: count=R1, addend=R0
@R1
D=M
@count
M=D
@R0
D=M
@addend
M=D
@LOOP
0;JMP

(SWAP)
// R0<=R1: count=R0, addend=R1
@R0
D=M
@count
M=D
@R1
D=M
@addend
M=D

(LOOP)
@count
D=M
@END
D;JEQ   // done when count==0

@addend
D=M
@R2
M=D+M   // R2+=addend

@count
M=M-1   // count--
@LOOP
0;JMP

(END)
@END
0;JMP   // infinite loop to end the program

asm

// Runs an infinite loop that listens to the keyboard input.
// When a key is pressed (any key), the program blackens the screen,
// i.e. writes "black" in every pixel. When no key is pressed,
// the screen should be cleared.
(LOOP)
@KBD
D=M
@BLACK
D;JNE
@WHITE
0;JMP

(BLACK)
@color
M=-1
@INIT
0;JMP

(WHITE)
@color
M=0

(INIT)
@SCREEN
D=A
@addr
M=D         // screen base address
@8192
D=A
@count
M=D         // count=8192=32*256, number of screen words

(FILL)
@count
D=M
@LOOP
D;JEQ       // done filling, go check keyboard again

@color
D=M
@addr
A=M
M=D         // RAM[addr]=color

@addr
M=M+1       // addr++
@count
M=M-1       // count--

@FILL
0;JMP

04. Machine Language ​

术语 ​

Hack ​

A 指令 ​

C 指令 ​

符号 ​

屏幕 ​

键盘 ​

语法规约 ​

Project 04 ​