======Machine Language======
//Week 4 notes//
----
====Overview====
  * //Univeraslity//: 相同的**硬件**运行不同的**软件** //Turing// + //von Neumann//
  * 计算机通过机器语言（二进制指令）来实现软件层面上的不同功能
  * 机器语言提供的的三个信息：
    * Operations：指令需要计算机做什么
    * Counter：指令以及下一步指令是什么
    * Addressing：指令需要操作哪些硬件
===Compilcation===
  * 计算机只能识别机器语言
  * 人类需要通过编译器将人类友好的语言转化为机器语言
==Mnemonics==
为了更方便的讨论机器语言，人们通常将指定的代码段与相应的含义（//Mnemonic Form//）对应起来。下面的例子中，''ADD'' 就是 ''0100010'' 对应的 //Mnemonic Form//。可以观察到的是，这种替代不仅可以代表 operation，也可以代表地址。
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:mnemonics.svg?300 |}}
需要注意的是：
  * 类似 ''ADD'' 这样的形式不是真正存在的
  * 人类通过汇编语言（//assembly language//）来讲上述形式转化为机器语言
==Symbols==
Symbols 主要应用于简化内存寻址的过程。比如维护一个 ''index''，将指定的内存区域分为不同的片区，当需要对指定区域进行操作时，我们可以通过对应的 ''index'' 对其进行快速访问。这种将 symbol 与实际内存地址建立映射关系的方式，会大大增强程序的易读性和可维护性。该映射关系也是由 assmbler 来翻译的。
====Machine Languages: Elements====
  * 机器语言是硬件与软件的 Interface，其决定了硬件可以进行什么样的操作
  * 硬件与软件层面的操作通常接近，但不一定一一对应
  * 机器语言的复杂程度取决于设计。通常，设计的操作越复杂，硬件层面的实现花费就越高。
===Machine operations===
  * 算术运算：add / sub
  * 逻辑运算：and / or
  * 流程控制（flow control）
不同的机器语言之间的实现可能并不相同，取决于其复杂度。
===Addressing===
内存寻址是一项非常昂贵的操作。通常来说，有两个问题：
  * 内存越大，需要提供的地址就越长
  * 内存越大，访问指定内存的时间就越长
==Memory Hierarchy==
解决方案是提供内存的级联：将内存按速度进行划分，不同速度的内存区域对应不同的任务。需要注意的是，速度越快，对应的内存就越小。
==Registers==
寄存器是访问速度最快的内存，通常由 CPU 内置。寄存器分为几个类型：
  * Data Registers：比如 ''add r1 r2''，''r1'' 和 ''r2'' 就是该加法操作中，对应数据所在的寄存器名称。
  * Address Registers：类似于指针，作为某一片我们需要使用的内存区域的入口
==Addressing Modes==
<code bash>
# 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
</code>
==Input / Output==
外设（键盘鼠标）通常通过寄存器链接，并通过一定的协议（驱动）来使其工作。
===Flow Control===
  * 通常按顺序执行
  * 某些情况需要进行无条件跳转（unconditional jump），比如 loop
    * 通常使用寄存器来存储每次迭代的结果
    * loop 的起始点通常会使用一个名字与其地址相关联，方便跳转（比如 loop 关联到 102，则使用 Jump loop 等同于 jump 102）
  * 某些情况下需要进行带条件跳转 (condtional jump)

====The HACK Computer====
  * 16 bits computer
  * Data memory: RAM 由一系列的 16-bit 寄存器组成, ''RAM[0]''
  * Instruction memory: ROM 由一系列的 16-bits 寄存器序列组成, ''ROM[0]''
  * CPU: 执行 16 bits 的指令
  * Buses：数据 / 寻址的通道 
===Software===
整个 program 是一系列的 Hack 16bit 指令组成的序列。
==机器语言==
  * 16-bit A 类指令
  * 16-bit C 类指令
===Control===
  * 在 ROM 中会预写入指令序列
  * 使用 ''reset'' 唤起该序列，之后整个程序开始运行
===Registers===
  * D Register：16 bit, 数据类寄存器
  * A Register：16 bit，数据类 / 地址类寄存器
  * M Register: 16 bit RAM 寄存器，代表着当前地址 ''A'' 对应的寄存器
===Instruction===
==A-instruction==
A指令（寻址类）的作用：存储一个值到某个 A 类寄存器中。该值将作为 RAM 的 index，自动关联到 M 寄存器。比如 ''@21''，之后对 M 类寄存器进行访问，实际上就是访问的 ''RAM[21]''。
<code bash>
# 对 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
</code>
==C-instruction: overview==
C指令（计算类）由下面的结构组成：
<code py>
# dest & jump are optional
dest:comp ; jump
</code>
其中：
  * //Dest// 代表的是计算的结果所存放的寄存器，可以是 A / D / M 类寄存器
  * //Comp// 代表的是计算表达式
  * //Jump// 代表的是带条件的跳转，当 Comp 的结果匹配某个条件时，程序会跳转到 **ROM** 中对应的指令位置
整个流程：
  - 在 COMP 中计算
  - 将计算的结果存到 dest 中
  - 如果COMP的结果 ''=='' 0，那么执行 jump。跳转的位置与之前指定的 A 值相关
==C-instruction: dest==
该部分指定计算结果应该存储到哪个寄存器。比如：
<code bash>
# 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
</code>
==C-instruction: jump==
jump 是 C 指令的一个可选操作。通常来说，当 jump 是 C 指令的一部分时，整个 C 指令实际上就是为了 jump 而准备的。比如下面的例子：
<code bash>
# if (D-1 == 0), jump to execute the instruction sotred in ROM[56]
@56
D-1;JEQ
</code>
也就是说，这个 ''A = 56'' 是一个目的性很强的操作，它的主要功能就是告诉计算机当条件成立时，我们应该执行 ''ROM[56]'' 对应的指令。换句话说，jump 的意义就是我们希望在某种条件成立的情况下，执行特定的指令（如果没有 jump，ROM 里的指令会按次序进行）。
\\ \\ 
根据条件的不同，HACK computer 中提供了多种不同条件的 jump：
^Type^explanation^
|//null//|不跳转（默认情况）|
|//JGT//|如果 comp > 0，跳转|
|//JEQ//|如果 comp == 0，跳转|
|//JGE//|如果 comp >= 0，跳转|
|//JLT//|如果 comp < 0，跳转|
|//JNE//|如果 comp ≠ 0，跳转|
|//JLE//|如果 comp <= 0，跳转|
|//JMP//|无条件跳转（always jump|
====Language Specificaion====
两种写指令的方式：
  * Symbolic：人类友好，需要 assmbler 来进行翻译
  * Binary：二进制机器码
===Comparsion in A-ins===
两种指令的对比如下：
<code bash>
# set the A register to value
# symbolic @ + value
# Binary 0 + value(in binary)
@21
0 000000000010101
</code>
===Comparsion in C-ins===
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 部分的内容

==Comp 部分的对比==
{{ :cs:comp_n_arch:courses:fnti_i:comp_symbolic_binary.jpg?400 |}}
==dest 部分的对比==
{{ :cs:comp_n_arch:courses:fnti_i:dest_symbolic_binary.jpg?400 |}}
==jump 部分的对比==
{{ :cs:comp_n_arch:courses:fnti_i:jump_symbolic_binary_1.jpg?400 |}}
====In/Output====
  * 键盘，鼠标，显示器：这些独立于计算机外部的设备通常被称为 peripheral I/O devices
  * 主要作用是于用户互动
===控制 I/O 设备===
  * High-level 方法：使用软件 / 语言的 lib
  * Low-level 方法：使用 Bits
===Output===
  * RAM 中会单独提供一部分区域用于显示器的内容的存储
  * 显示器通过对区域的内容进行持续刷新来更新输出的内容
  * 输出的内容可以通过 coding 的方式来操控
==Screen memory map==
  * 256 * 512, black / white
  * 通过一个 8k 的 16 bits 的 memory map 来作为其底层（256 * 512 == 8192 * 16），每个 bit 代表一个像素，1 / 0 代表 black / white
==map 的映射==
  * 以 32 个 字为单位作为一**行**(32 * 16 = 512)
  * 行的范围为 [0, 255]
  * 寻找坐标为(row, col) 的像素点：
    * 寻找其所在行（也就是对应的哪一个由32个寄存器组成的片区）：32 * row
    * 寻找其所在列：col / 16 （整除，也就是找出片区内对应的寄存器）
    * 最后结果 i = 32*row + col / 16
    * 再找到对应的像素点：col % 16
    * 最后将内容更新到 RAM 里，在下一个更新期就可以看到更新的内容了
需要注意的是，上述的映射是以 screen 所在的内存区域为基准的。当 screen 作为整个内存的一部分时，需要将之前的量加上，比如：
<code bash>
word = Screen[32*row + col/16] #without base addres
word = RAM[16384 + 32*row + col/16] #with base address
</code>
当得到具体寄存器所在地址后，如果我们要改变该寄存器中任意一个像素点，可以使用 ''col % 16'' 来找到该像素点并赋值
===Input===
  * 键盘使用 keyboard memory map 来实现（单 16bits 寄存器）
  * 每个键盘按键都对应一定的值（类似 ASCII 值）
  * 当按下键盘的时候，按键对应的值（比如 ''k'' 对应的 75）就会以二进制的形式写入该寄存器
  * Hack 计算器中，寄存器位置：''RAM[24576]''。如果其值为 ''0''，代表没有按键按下。
====Hack Proramming====
<WRAP center round tip 100%>
可以使用课程提供的 assambler 或者 cpu emulator 来进行 symbolic 语言到机器语言的转化。
</WRAP>
Hack 编程语言需要的功能有：
  * Working with registers and memeory
  * Branching
  * Variables
  * Iteration
  * Pointers
  * Input / Output
===Registers & Memory===
下面是一些基础的例子：
<code bash>
# 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
</code>
==实例：两数相加==
<WRAP center round info 100%>
指令在转换过程中会忽略所有的 white space。
</WRAP>

<code bash>
# 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
</code>

需要特别注意的是，**计算机并不会自动终结程序**。一种终止程序的解决方案是，在指令序列的末尾添加一个无限循环，让整个程序不会再继续执行下去：
<code bash>
@6
0;JMP
</code>
==Built-in symbols==
  * R0 to R15：对应的数据为 0 到 15 
这些 symbols 主要作为虚拟寄存器（//Virutal register//），来提高可读性。考虑下面的程序：
<code bash>
@15
D=A 
@5 
M=D
</code>
这段程序中，A 既充当了数据寄存器，又充当了地址寄存器。如果单看带 ''@'' 这一段，我们根本不知道 A 到底使用的哪个寄存器。R0-R15 代表着我们指定了将要使用的寄存器是 0-15 号寄存器，而不是别的：
<code bash>
@R5 # case sensitive! no r5
M=D
</code>
  * SCREEN 16384
  * KBD 24576

===Branching===
机器语言（汇编语言）中，只存在着一种 branching 的方式：//goto//：
<code bash>
# 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
</code>
==使用 label 提高可读性==
我们可以使用一些 label 代替具体的位置，来提高可读性：
<code bash>
# jump to POSITIVE branch
@POSITIVE
D; JGT

(POSITIVE)
    @R1
    M = 1

# infinite loop
# Jump to the @end
(END)
    @END
    0;JMP
</code>
括号中的内容可以被视作注释，不会被转写；但引用（''@END''）这个将在转写中被替代为对应的 ROM 入口。
===Variables===
Hack 中使用 16bits 的寄存器作为 variable 的唯一标识方式。在Hack 语言中，我们可以通过 ''@varName'' 的方式来定义一个变量。这个变量存储于 RAM 中，其起始位置为 ''RAM[16]''（0-15 被 R0-R15 占了）。下面是一个具体的例子：
<code bash>
# 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
</code>
需要注意的是，变量被识别的前提是在程序中无法找到与其对应的 label 注释。这个是与 branch 的根本不同：
  * Branch label 是 ''@name + (name)'' 的形式，分配位置与具体 label 所在位置有关
  * 变量是 ''@name'' 的形式，分配位置从 ''RAM[16]'' 开始
===Iteration===
在 Hack 中写循环一般要确定两个入点：
  * STOP：入口放置于整个程序的末尾，跳转点放置于循环条件的后方
  * LOOP：入口放置于循环体的起始点，跳转点放置于循环体的末尾
下面是一个循环累加的例子：
<code bash>
# 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
</code>
<WRAP center round box 100%>
  * 推荐先写伪代码，再翻译为 HACK program
  * 测试推荐使用 track table：跟踪每个迭代中每个值的变化，看是否符合预期
</WRAP>
===Pointers===
array 的形式在机器语言中是不存在的。取而代之的是，array 是以起始地址 + 偏移量的形式来进行访问的。我们将这种通过地址进行访问的形式称为指针（//Pointer//)。
实现上，我们会通过更新 A 来得到其对应的 M，再对 M进行更新操作。下面是一个例子：
<code cpp>
// 需要模拟的代码
n = 10;
for (i = 0; i < n; ++i)
{
    arr[i] = -1;
}
</code>
<code bash>
# 初始化
# 假设 array arr 的起始地址为 100

# 初始化 arr
@100
D = A
@arr
M = D # 将 arr 的初始值设为 100

# 初始化 n
@10
D = A 
@n
M = D # 将 n 的初始值设为 10

# 初始化 i
@i
M = 0 # 将 i 的初始值设为 0

# 开始进入循环
(LOOP)
    # 如果 i == n，循环结束
    @i
    D = M
    @n
    D = D - M # D 是判断条件，存储 i - n 的结果
    
    @END
    D;JEQ # i == n 则跳转至 END
    
    # 如果不相等，则循环继续
    
    # 获取 arr 的起始地址
    @arr
    D=M
    @i
    A = D+M # 计算偏移量，也就是指针的地址 arr + i
    # 更新对应的地址
    # 注意此时的 M 已经变化了，不再是 i 对应的寄存器，而是 A 对应的寄存器
    # A 更新后访问 M 的 side effect: M 会与 RAM[A] 关联
    M = -1 # RAM[arr+i] = -1
    
    @i
    M = M + 1 # ++i
    
    @LOOP # 循环结束
    0;JMP

(END)
    @END
    0;JMP
</code>
===Input & Output===
这部分主要实现的是：
  * Screen
  * Keyboard
{{ :cs:comp_n_arch:courses:fnti_i:hack_memory_distribution.svg?150 |}}
==实例：drawing an rectangle==
  * 题目的要求是：画一个自定义 row(''n'') 的，宽度（列）为 16 bits 的矩形。
首先从高级语言考虑一下这个代码的循环：
<code cpp>
for (i=0; i < n; ++i)
{
    // print first black pixels at he beginning of row i
}
</code>
接下来以更机器语言的方式思考该伪代码：
<code bash>
# init
addr = SCREEN # 写入的首地址是 SCREEN 对应的内存起始点
n = RAM[0] # 从 R0 中获取 n 的初始值
i = 0 

# Looping
LOOP:
    if i > n goto END # 循环结束条件是 i > n
    # draw pixels
    RAM[addr] = -1 # -1的二进制表示是 1111111111111111
    # update status
    addr += 32 # 换行，由于屏幕宽度是 512，每一行需要 32 个寄存器才可以完全表示，因此换行是直接去第 33 个寄存器
    i += 1 # 更新循环条件
    goto LOOP
    
END:
    goto END
</code>
实现如下：
<code bash>
@SCREEN 
D = A
@addr # 使用 SCREEN 地址初始化 addr, 16384 号寄存器
M = D
@R0
D = M
@n
M = D # 使用 R0 内容初始化 n
@i
M = 0 # 初始化 i 为 0

(LOOP)
    @i
    D = M
    @n
    D = D - M
    @END
    D;JGT # 如果 i > n, 结束循环

    @addr
    A = M 
    M = -1 # RAM[addr] = 1111 1111 1111 1111

    # 更新循环状态
    @i 
    M = M + 1

    @32
    D = A # 注意，所有的常量都需要用 A 类寄存器获取
    @addr 
    M = M + D
    
    @LOOP
    0;JMP

(END)
    @END
    0;JMP
</code>
==keyboard==
  - 读取 RAM[24576] 内的内容
  - 如果内容为 ''0'' ，那么没有键被按下
  - 否则，搜寻对应值的 key 值