Week 4 notes

• Univeraslity: 相同的硬件运行不同的软件 Turing + von Neumann
• 计算机通过机器语言（二进制指令）来实现软件层面上的不同功能
• 机器语言提供的的三个信息：
  • Operations：指令需要计算机做什么
  • Counter：指令以及下一步指令是什么
  • Addressing：指令需要操作哪些硬件

• 计算机只能识别机器语言
• 人类需要通过编译器将人类友好的语言转化为机器语言

为了更方便的讨论机器语言，人们通常将指定的代码段与相应的含义（Mnemonic Form）对应起来。下面的例子中，ADD 就是 0100010 对应的 Mnemonic Form。可以观察到的是，这种替代不仅可以代表 operation，也可以代表地址。

需要注意的是：

• 类似 ADD 这样的形式不是真正存在的
• 人类通过汇编语言（assembly language）来讲上述形式转化为机器语言

Symbols 主要应用于简化内存寻址的过程。比如维护一个 index，将指定的内存区域分为不同的片区，当需要对指定区域进行操作时，我们可以通过对应的 index 对其进行快速访问。这种将 symbol 与实际内存地址建立映射关系的方式，会大大增强程序的易读性和可维护性。该映射关系也是由 assmbler 来翻译的。

• 机器语言是硬件与软件的 Interface，其决定了硬件可以进行什么样的操作
• 硬件与软件层面的操作通常接近，但不一定一一对应
• 机器语言的复杂程度取决于设计。通常，设计的操作越复杂，硬件层面的实现花费就越高。

• 算术运算：add / sub
• 逻辑运算：and / or
• 流程控制（flow control）

不同的机器语言之间的实现可能并不相同，取决于其复杂度。

内存寻址是一项非常昂贵的操作。通常来说，有两个问题：

• 内存越大，需要提供的地址就越长
• 内存越大，访问指定内存的时间就越长

解决方案是提供内存的级联：将内存按速度进行划分，不同速度的内存区域对应不同的任务。需要注意的是，速度越快，对应的内存就越小。

寄存器是访问速度最快的内存，通常由 CPU 内置。寄存器分为几个类型：

• Data Registers：比如 add r1 r2，r1 和 r2 就是该加法操作中，对应数据所在的寄存器名称。
• Address Registers：类似于指针，作为某一片我们需要使用的内存区域的入口

# Register mode R2 <- R2 + R1
Add R1, R2
# Direct mode Mem[200] <- Mem[200] + R1
Add R1, M[200]
# Indirect Mem[A] <- Mem[A] + R1
Add R1, @A
# Immediate R1 <- R1 + 73
Add 73, R1

外设（键盘鼠标）通常通过寄存器链接，并通过一定的协议（驱动）来使其工作。

• 通常按顺序执行
• 某些情况需要进行无条件跳转（unconditional jump），比如 loop
  • 通常使用寄存器来存储每次迭代的结果
  • loop 的起始点通常会使用一个名字与其地址相关联，方便跳转（比如 loop 关联到 102，则使用 Jump loop 等同于 jump 102）
• 某些情况下需要进行带条件跳转 (condtional jump)

• 16 bits computer
• Data memory: RAM 由一系列的 16-bit 寄存器组成, RAM[0]
• Instruction memory: ROM 由一系列的 16-bits 寄存器序列组成, ROM[0]
• CPU: 执行 16 bits 的指令
• Buses：数据 / 寻址的通道

整个 program 是一系列的 Hack 16bit 指令组成的序列。

• 16-bit A 类指令
• 16-bit C 类指令

• 在 ROM 中会预写入指令序列
• 使用 reset 唤起该序列，之后整个程序开始运行

• D Register：16 bit, 数据类寄存器
• A Register：16 bit，数据类 / 地址类寄存器
• M Register: 16 bit RAM 寄存器，代表着当前地址 A 对应的寄存器

A指令（寻址类）的作用：存储一个值到某个 A 类寄存器中。该值将作为 RAM 的 index，自动关联到 M 寄存器。比如 @21，之后对 M 类寄存器进行访问，实际上就是访问的 RAM[21]。

# 对 A 类寄存器赋值
# 语法：@value
# value 值：non-negative decimal constant / symbol referring to such a constant 
# side effects: RAM[21] becomes the selected RAM register(M 寄存器)
@21

# usage
@100 # A=100
M=-1 # RAM[100] = -1

C指令（计算类）由下面的结构组成：

# dest & jump are optional
dest:comp ; jump

• Dest 代表的是计算的结果所存放的寄存器，可以是 A / D / M 类寄存器
• Comp 代表的是计算表达式
• Jump 代表的是带条件的跳转，当 Comp 的结果匹配某个条件时，程序会跳转到 ROM 中对应的指令位置

整个流程：

1. 在 COMP 中计算
2. 将计算的结果存到 dest 中
3. 如果COMP的结果 == 0，那么执行 jump。跳转的位置与之前指定的 A 值相关

该部分指定计算结果应该存储到哪个寄存器。比如：

# set the D resgister to -1
D=-1

# set the RAM[300] resgister to D - 1
# when use A register, it must be assigned a value first
@300 # A = 300
M = D - 1 # RAM[300]  = D - 1

jump 是 C 指令的一个可选操作。通常来说，当 jump 是 C 指令的一部分时，整个 C 指令实际上就是为了 jump 而准备的。比如下面的例子：

# if (D-1 == 0), jump to execute the instruction sotred in ROM[56]
@56
D-1;JEQ

两种写指令的方式：

• Symbolic：人类友好，需要 assmbler 来进行翻译
• Binary：二进制机器码

两种指令的对比如下：

# set the A register to value
# symbolic @ + value
# Binary 0 + value(in binary)
@21
0 000000000010101

C-insturction 的主要难点在于如何用二进制表示 C-instruction：

• 首先，Hack 是 16-bits 的计算机，因此指令的长度是 16 bits
• 这 16 bits 被区分为了不同区域：
  • [0]：这一部分是 op code。C 指令对应的 op code 是 1
  • [1..2]：这一部分没有用到，约定的内容是两个 1
  • [3..9]: 这一部分代表的 COMP 部分的内容
  • [10..12]: 这一部分代表的是 dest 部分的内容
  • [13..15]: 这一部分代表的是 jump 部分的内容

• 键盘，鼠标，显示器：这些独立于计算机外部的设备通常被称为 peripheral I/O devices
• 主要作用是于用户互动

• High-level 方法：使用软件 / 语言的 lib
• Low-level 方法：使用 Bits

• RAM 中会单独提供一部分区域用于显示器的内容的存储
• 显示器通过对区域的内容进行持续刷新来更新输出的内容
• 输出的内容可以通过 coding 的方式来操控

• 256 * 512, black / white
• 通过一个 8k 的 16 bits 的 memory map 来作为其底层（256 * 512 == 8192 * 16），每个 bit 代表一个像素，1 / 0 代表 black / white

• 以 32 个 字为单位作为一行(32 * 16 = 512)
• 行的范围为 [0, 255]
• 寻找坐标为(row, col) 的像素点：
  • 寻找其所在行（也就是对应的哪一个由32个寄存器组成的片区）：32 * row
  • 寻找其所在列：col / 16 （整除，也就是找出片区内对应的寄存器）
  • 最后结果 i = 32*row + col / 16
  • 再找到对应的像素点：col % 16
  • 最后将内容更新到 RAM 里，在下一个更新期就可以看到更新的内容了

需要注意的是，上述的映射是以 screen 所在的内存区域为基准的。当 screen 作为整个内存的一部分时，需要将之前的量加上，比如：

word = Screen[32*row + col/16] #without base addres
word = RAM[16384 + 32*row + col/16] #with base address

• 键盘使用 keyboard memory map 来实现（单 16bits 寄存器）
• 每个键盘按键都对应一定的值（类似 ASCII 值）
• 当按下键盘的时候，按键对应的值（比如 k 对应的 75）就会以二进制的形式写入该寄存器
• Hack 计算器中，寄存器位置：RAM[24576]。如果其值为 0，代表没有按键按下。

Hack 编程语言需要的功能有：

• Working with registers and memeory
• Branching
• Variables
• Iteration
• Pointers
• Input / Output

下面是一些基础的例子：

# D = 10
@10
D = A

# D++
D = D + 1

# D = RAM[17]
@17
D = M

# RAM[17] = 0 
# 注意这里的 0 是表达式！而不是常量，HACK 里常量是不能直接写入 M 的
@17
M = 0

# RAM[17] = 10
# 注意，Hack 的指令集并不能支持将常量写入 M 的操作
# 所有的操作都必须放到寄存器里去过一遍
@10 # 将常量 10 写入到 A
D = A # 之后 A 需要复用（写入 17，关联 M），因此这里将当前 A 代表的常量写入到 D
@17 # 使用 A 取地址，准备关联 M
M = D # 关联 M 到 RAM[17]，并写入 D 中的常量 10

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

# adds up two numbers
# 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

需要特别注意的是，计算机并不会自动终结程序。一种终止程序的解决方案是，在指令序列的末尾添加一个无限循环，让整个程序不会再继续执行下去：

@6
0;JMP

• R0 to R15：对应的数据为 0 到 15

这些 symbols 主要作为虚拟寄存器（Virutal register），来提高可读性。考虑下面的程序：

@15
D=A 
@5 
M=D

@R5 # case sensitive! no r5
M=D

• SCREEN 16384
• KBD 24576

机器语言（汇编语言）中，只存在着一种 branching 的方式：goto：

# sinnum.asm
# Computes: if R0>0, R1 = 1, else R1 = 0
@R0
D = M

# ROM[8] 会针对另外一个条件做处理
# 如果 D > 0， 则跳转到 ROM[8]
@8
D;JGT

# 否则做另外一个分支
# 两个分支都会使用 R1 寄存器
@R1
M = 0

# 无限循环，结束程序（在分支 R0 <= 0 上）
# 入口是 ROM[6]，但会跳转到 ROM[10]，无限循环最终会稳定在 ROM[10]
@10
0;JMP

# ROM[8], D > 0 分支
@R1
D = M

# 做 D > 0 分支的结束
@10
0;JMP

我们可以使用一些 label 代替具体的位置，来提高可读性：

# jump to POSITIVE branch
@POSITIVE
D; JGT

(POSITIVE)
    @R1
    M = 1

# infinite loop
# Jump to the @end
(END)
    @END
    0;JMP

Hack 中使用 16bits 的寄存器作为 variable 的唯一标识方式。在Hack 语言中，我们可以通过 @varName 的方式来定义一个变量。这个变量存储于 RAM 中，其起始位置为 RAM[16]（0-15 被 R0-R15 占了）。下面是一个具体的例子：

# exhange two values
# temp = R1, R1 = R0, R0 = temp

@R1
D = M
@temp #此时 M 对应的是变量所关联的寄存器
M = D

@R2
D = M 
@R1
M = D # R1 = R0

@temp
D = M # 再次关联 temp 的值到 M，并存储到 D 中
@R0 # 最后将该值存放到 R0 中，交换完毕
M = D

(END)
    @END
    0;JMP

• Branch label 是 @name + (name) 的形式，分配位置与具体 label 所在位置有关
• 变量是 @name 的形式，分配位置从 RAM[16] 开始

在 Hack 中写循环一般要确定两个入点：

• STOP：入口放置于整个程序的末尾，跳转点放置于循环条件的后方
• LOOP：入口放置于循环体的起始点，跳转点放置于循环体的末尾

下面是一个循环累加的例子：

# compute RAM[1] + RAM[2] ... + RAM[n]
# 初始化
@R0 
D=M
@n
M=D # 将 R0 的值用于 n 的初始化
@i
M = 1 # i = 1
@sum
M = 0 # sum = 0

(LOOP)
    @i 
    D = M # 获取当前 i 值
    @n
    D = D - M # 获取 n 值，计算 i-n 的结果

    @STOP
    D;JGT # 如果 i-n > 0，则循环超过上限，停止

    @sum 
    D = M 
    @i 
    D = D+M # 否则，sum += i
    @sum # 覆写 sum
    M = D

    @i 
    M = M + 1 # ++i

    @LOOP # 再次循环
    0;JMP

(STOP)
    @sum 
    D = M
    @R1 # 将 sum 值存储到 R1 中
    M = D

(END)
    @END
    0;JMP