The Road Ahead week4 Machine language

Posted on | In ,

“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
6
7
# 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
@END
D ; JGE      # jump to END

指令集

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

A指令

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

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

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

C指令

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

1
2
3
   15    14 13  12 11 10  9  8  7  6    5  4  3    2  1  0
   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(instruction[11]) c2(10) c3(9) c4(8) c5(7) c6(6)
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(12) = 0 a = 1 - - - - - -

dest字段为寄存器写入字段，指示待写入寄存器

dest d1(instruction[5]) d2(4) d3(3) 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(2) j2(1) j3(0) effect
null 0 0 0 no jump
JGT 0 0 1 if out > 0 jump
j3 == 1 && ALUOut > 0
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    // if R0 > 0

@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    // D = 100
    @arr
    M = D    // arr = 100

    @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        // arr stores the base address
    @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%