The Road Ahead week4 Machine language

“The great wall is made by blocks”

Hack computer and machine language

在前几章中,我们已经定义了内存以及加法器,从本章开始我们将介绍Hack computer的基本结构,并最终搭建起一个简单的CPU。我们的机器是一个16位机器,由以下几个部分组成:

  • Data memory (RAM):A sequence of 16 bit registers
  • Instruction memory (ROM):A sequence of 16 bit registers
  • Central processing unit (CPU):perform 16 bit instructions
  • Instruction bus/data bus/address bus

Hack computer Arch

而Hack的机器语言包括16位的A指令和C指令,操作3个寄存器:

  • D寄存器保存一个16位的数据
  • A寄存器保存16位地址
  • M寄存器保存A寄存器地址对应的内存寄存器

Hack计算机的汇编代码

A 指令

A指令的语法为:@value,其中,value是一个非负整数;其作用是将A寄存器设置为value,并将RAM[A]置为所选择的寄存器,例如:

1
2
3
4
5
6
# Set A = 21 and select RAM[21]
@21 # A = 21, M = RAM[21]

; to set RAM[100] to -1
@100 # A = 100
M = -1 # RAM[100] = -1

当我们需要操作内存时,总是需要A指令。

C指令

C指令的格式如下:

1
2
3
4
5
6
7
8
dest = comp ; jump    # 其中dest和jump都是可选的,comp指计算的操作,可选的computation如下:

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 = NULL, M, D, MD, A, AM, AD, AMD # M refers to RAM[A]

jump = NULL, JGT, JEQ, JGE, JLT, JNE, JLE, JMP # 如果计算结果 (>, >=, ==, <=, <, !=) 0, 则跳转至ROM[A]

C指令的功能包括:

  • 执行comp
  • 将结果保存在dest中
  • 如果计算结果与0比较成立,那么跳转

一个例子如下:

1
2
3
4
5
# if (D - 1 == 0), jump to execute instruction in ROM[56]
@56 # A = 56
D - 1; JEQ # if (D - 1 == 0) goto 56

# unconditional jump

指令集

Hack computer实现了一种非常简单的指令集,支持上述的A指令和C指令,指令集的格式分别如下:

A指令

A指令的二进制机器码格式如下:

1
0 + value   # value是一个15位的二进制数

例如,代码0000000000010101表示为将A寄存器置为21。

C指令

C指令的格式相对较为复杂 ,其二进制语法如下:

1
2
   1   |  1 1  | a c1 c2 c3 c4 c5 c6 | d1 d2 d3 | j1 j2 j3 |
opcode | unuse | comp bits | dest | jump bit |

我们先来看下comp字段,对于comp字段,对应的含义如下:

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字段为寄存器写入字段,指示待写入寄存器

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/RAM[A]/D

jump字段如下

jump j1 j2 j3 effect
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
JEQ 0 1 0 out == 0
JGE 0 1 1 out >= 0
JLT 1 0 0 out < 0
JNE 1 0 1 out != 0
JLE 1 1 0 out <= 0
JMP 1 1 1 unconditional jump

输入/输出

屏幕

我们需要接收用户的输入,并从屏幕上进行显示,对于屏幕显示的部分,我们可以将屏幕视为一个矩阵,对其进行操作,通过定期刷新映射到屏幕的内存,实现屏幕更新。我们的计算机是双字节计算机,对于一个$512\times256$大小的屏幕,所需要的内存单元数量为8192(512*256/16)个。32个内存单元能够表示一行,例如我要设置第$(row,col)$个像素,那么我要修改的内存单元为:

写为代码即:

1
word = Screen[32 * row + col / 16]

需要注意的是,屏幕映射的内存是我们整个内存的一部分,因此我们还需要知道屏幕内存的基地址,假设我们的屏幕内存位于16384,则

1
word = RAM[16384 + 32 * row + col / 16]

找到了这个双字后,我们需要将第col % 16个bit设置,然后将其写回到内存中。

键盘

我们同样对于键盘进行了映射,不过相比屏幕,键盘所需的内存很小,我们只映射16位的内存给键盘,当我们按下一个按键后,键盘中的内容会记录在这个内存中,对于Hack计算机,能够识别的字符集为ASCII的子集。在Hack中,我们将键盘映射至24567这个地址中。经过映射之后,Hack的内存布局如下:

Hack computer Arch

Hack程序

一些基本操作

这里我们列举了Hack中一些基本的寄存器和内存的操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// D = 10
@10
D = A

// D++
D = D + 1

// RAM[17] = 0
@17
M = 0

// RAM[17] = 10
@10
D = A
@17
M = D

// RAM[5] = RAM[3]
@3
D = M
@5
M = D

下面是一个简单的计算两数相加的例子:

1
2
3
4
5
6
7
8
9
// RAM[2] = RAM[0] + RAM[1]
@0
D = M // D = RAM[0]

@1
D = D + M // D = D + RAM[1]

@2
M = D // RAM[2] = D

内嵌符号

Hack汇编包含了一些内嵌的符号,对一些值进行了常数替换,前16个RAM的字用作虚拟寄存器

1
2
3
4
5
6
7
8
symbol   value
R0 0
R1 1
... ...
R15 15

SCREEN 16384
KBD 24576

分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Program: Signum.asm
// Compute if R0 > 0 then R1 = 1; else R1 = 0

@R0
D = M

@8
D; JGT

@R1
M = 0
@10
0; JMP

@R1
M = 1

@10
0; JMP

变量

我们能够指定内存中某个寄存器,保存对应的变量,变量由变量名、地址以及值组成,下面是一个变量使用的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Program: Flip.asm
// flips the values of
// RAM[0] and RAM[1]

// temp = R1
// R1 = R0
// R0 = temp

@R1
D = M
@temp // @16
M = D
// @temp : find some available memory register, say the n'th register, use it to represent the variable temp, the @temp in program will be translated into @n

@R0
D = M
@R1
M = D

@temp // @16
D = M
@R0
M = D

(END)
@END
0; JMP

变量的使用语境如下:

  • 加入一个符号没有与之对应的标签,那么将其视为一个变量
  • 变量从内存中某个位置开始,逐渐向上递增

迭代

这里给出一个迭代的实现,计算$1+2+…+n$的值,假设$n$保存在RAM[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Computes RAM[1] = 1 + 2 + 3 + ... + n
// Put a number n in RAM[0]
// Program: Sum1toN.asm

n = R0
i = 1
sum = 0
LOOP:
if i > n goto STOP
sum = sum + i
i = i + 1
goto LOOP

STOP:
R1 = sum

此处关键的实现是迭代的逻辑,这里给出迭代的逻辑实现如下:

1
2
3
4
5
6
7
(LOOP)
@i
D = M
@n
D = D - M
@STOP
D; JGT

指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// for (i = 0; i < n; i++) {
// arr[i] = -1;
// }

// suppose that arr = 100, n = 10
@100
D = A
@arr
M = D

@10
D = A
@n
M = D

@i
M = 0

在对变量进行初始化之后,内存布局如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+------------------+  <- 0x0 
| |
+------------------+
| ... |
+------------------+ <- 0x10 (arr)
| 100 |
+------------------+ <- 0x11 (n)
| 10 |
+------------------+ <- 0x12 (i)
| 0 |
+------------------+
| ... |
+------------------+ <- 0x64
| ... |
+------------------+
| ... |
+------------------+

循环部分如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(LOOP)
// if (i - n >= 0) {Jump to END}
@i
D = M
@n
D = D - M
@END
D; JGE

// arr[i] = -1
@arr
D = M
@i
A = D + M // Pointer
M = -1

// i++
@i
M = M + 1

@LOOP
0; JMP

当我们需要使用指针对内存进行访问时,我们需要如下指令:A = M

IO操作

最后,我们给出一些简单的IO操作,让我们能够在屏幕上绘制一些基本的图形,例如从屏幕的左上角开始,绘制多行黑色的像素,对应的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//  for (i = 0; i < n; i++) {
// draw 16 hack pixels at the
// beginning of row i
// }

addr = SCREEN
n = RAM[0]
i = 0

LOOP:
if i > n goto END
RAM[addr] = -1 // 1111,1111,1111,1111
// advances to the next row
addr = addr + 32 // To next line
i = i + 1
goto LOOP

END:
goto END

参考文献

0%