如何为Hack汇编语言编写“eq”解释器？

Question

我正在阅读和学习《计算机系统要素》，但我卡在了一个点上。可以在这里找到跳过下5条指令的示例章节。

无论如何，我正在尝试实现一个虚拟机（或字节码到汇编代码的翻译器），但我卡在了跳过下5条指令的一点上。

您可以在这里找到汇编符号。

目标是实现一个翻译器，将特定的字节码翻译成这个汇编代码。

我已经成功地为字节码做了一个例子：

push constant 5

被翻译成：

@5
D=A
@256
M=D

正如我所说的那样，Hack的汇编语言可以在我提供的链接中找到，但基本上是：

@5  // Load constant 5 to Register A
D=A // Assign the value in Reg A to Reg D
@256// Load constant 256 to Register A
M=D // Store the value found in Register D to Memory Location[A]

这很直截了当。根据定义，内存位置256是堆栈的顶部。

push constant 5
push constant 98

将被翻译为：

@5
D=A
@256
M=D
@98
D=A
@257
M=D

这一切都很好...

我还想再举一个例子：

push constant 5
push constant 98
add

被翻译成：

@5
D=A
@256
M=D
@98
D=A
@257
M=D
@257  // Here starts the translation for 'add' // Load top of stack to A
D=M   // D = M[A] 
@256  // Load top of stack to A 
A=M   // A = M[A]
D=D+A
@256
M=D

我认为这很清楚。

但是我不知道如何翻译字节码。

eq

转换为汇编语言。eq 的定义如下：

三个指令（eq，gt，lt）返回布尔值。VM将true和false分别表示为-1（负一，0xFFFF）和0（零，0x0000）。

因此，我需要弹出两个值分别到寄存器A和D中，这很容易。但是我应该如何创建一个汇编代码来检查值并在结果为真时推送1或在结果为假时推送0？

Hack计算机支持的汇编代码如下：

我可以做类似这样的事情：

push constant 5
push constant 6
sub

如果堆栈中推送的两个值相等，则其将保持值0，否则为!0，但这有什么帮助呢？我尝试使用D&A或D&M，但那也没有什么帮助。

我还可以引入条件跳转，但我怎么知道要跳转到哪个指令？Hack汇编代码没有像“跳过接下来的5条指令”之类的东西。

[由Spektre编辑]目标平台摘要，就我所见

• 16位冯·诺依曼体系结构（地址为15位，具有16位字访问）
• 数据存储器32KW（读/写）
• 指令（程序）存储器32KW（只读）
• 本地16位寄存器A、D
• 通用16位寄存器R0-R15映射到数据存储器的0x0000-0x000F
• 这些很可能也用于：SP(R0),LCL(R1),ARG(R2),This(R3),That(R4)
• 屏幕映射到数据存储器的0x4000-0x5FFF（512x256黑白像素8KW）
• 键盘映射到数据存储器的0x6000（ASCII码，如果最后按下的键？）

- Koray Tugay

---

1. 字节码转汇编？…… 汇编源代码是程序的文本表示形式（助记符），可以编译成字节码……通常是代码二进制文件。
2. 所有体系结构上的比较指令都是通过减法和设置标志Z，C来完成的，有些还包括条件分支（主要是MCU）。所以cmp a，b通常执行a-b，但会丢弃结果并留下标志。现在根据条件（无论是跳转还是其他指令）进行判断， 相等=（Z），大于=（NC），小于=（C）。

- Spektre

@Spektre 这个架构仅用于教学目的，它只有2个寄存器。没有设置标志或相对跳转。 - Koray Tugay

解释器/仿真器/模拟器模拟目标平台，您可以在一个平台上拥有源代码/可执行文件，并将其转换为另一个平台，这显然是交叉编译器。是的，如果您有标签、equ指令等内容，编译器需要预处理器...但对于原始的交叉反汇编/编译，您不需要预处理器。 - Spektre

“我怎么知道跳转到哪个指令？” 编写一个条件分支到符号标签的代码。手册中有示例，我在我的答案中编写了这样的示例。（如果您正在生成二进制代码，则知道分支指令的位置；“跳过5个指令”意味着“跳转到分支的二进制位置，+5”。） - Ira Baxter

nand2Tetris网站有一个问答部分。看起来这个问题需要非常具体的上下文，所以那可能是一个好地方去找答案。我相信这就是你在寻找的：http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Jumps-and-labels-when-you-wont-be-able-to-know-PC-line-number-td4028233.html - Noam

Answer 1

看起来有另一个章节更明确定义了Hack CPU。它说：

Hack CPU由第二章规定的ALU和三个寄存器组成，称为数据寄存器（D）、地址寄存器（A）和程序计数器（PC）。D和A是通用的16位寄存器，可以通过算术和逻辑指令进行操作，如A=D-1、D=D|A等，遵循第四章规定的Hack机器语言。虽然D寄存器仅用于存储数据值，但A寄存器的内容可以根据指令上下文以三种不同的方式进行解释：作为数据值、RAM地址或ROM地址。

因此，“M”访问似乎是由A控制的RAM位置。这就是我之前缺失的间接寻址。现在一切都清楚了。

现在我们可以更轻松地处理OP的问题了。

让我们从使用堆栈实现子程序调用开始。

     ; subroutine calling sequence
     @returnaddress   ; sets the A register
     D=A
     @subroutine
     0 ; jmp
  returnaddress:

     ...

  subroutine: ; D contains return address
  ; all parameters must be passed in memory locations, e.g, R1-R15
  ; ***** subroutine entry code *****
     @STK
     AM=M+1         ; bump stack pointer; also set A to new SP value
     M=D            ; write the return address into the stack
  ; **** subroutine entry code end ***
     <do subroutine work using any or all registers>
  ; **** subroutine exit code ****
     @STK
     AM=M-1         ; move stack pointer back
     A=M            ; fetch entry from stack
     0; jmp         ; jmp to return address
  ; **** subroutine exit code end ****

"push constant"指令可以轻松地被转换为存储在堆栈中的动态位置:

     @<constant>  ; sets A register
     D=A         ; save the constant someplace safe
     @STK
     AM=M+1         ; bump stack pointer; also set A to new SP value
     M=D            ; write the constant into the stack

如果我们想要创建一个子例程来推送常量：

   pushR2: ; value to push in R2
     @R15           ; save return address in R15
     M=D            ; we can't really use the stack,...
     @R2            ; because we are pushing on it
     D=M
     @STK
     AM=M+1         ; bump stack pointer; also set A to new SP value
     M=D            ; write the return address into the stack
     @R15
     A=M
     0 ; jmp

调用“push constant”例程的方法如下：

     @<constant>
     D=A
     @R2
     M=D
     @returnaddress   ; sets the A register
     D=A
     @pushR2
     0 ; jmp
  returnaddress:

推送变量值X：

     @X
     D=M
     @R2
     M=D
     @returnaddress   ; sets the A register
     D=A
     @pushR2
     0 ; jmp
  returnaddress:

一个从堆栈中将值弹出并存入D寄存器的子程序：

   popD:
     @R15           ; save return address in R15
     M=D            ; we can't really use the stack,...
     @STK
     AM=M-1         ; decrement stack pointer; also set A to new SP value
     D=M            ; fetch the popped value
     @R15
     A=M
     0 ; jmp

现在，要完成OP最初提出的“EQ”计算，请执行以下操作：

EQ: ; compare values on top of stack, return boolean in D
      @R15         ; save return address
      M=D
      @EQReturn1
      D=A
      @PopD
      0; jmp
@EQReturn1:
      @R2
      M=D        ; save first popped value
      @EQReturn2
      D=A
      @PopD
      0; jmp
@EQReturn2:
      ; here D has 2nd popped value, R2 has first
      @R2
      D=D-M
      @EQDone
      equal; jmp
      @AddressOfXFFFF
      D=M
EQDone: ; D contains 0 or FFFF here
      @R15
      A=M         ; fetch return address
      0; jmp

把所有东西都放在一起：

     @5           ; push constant 5
     D=A
     @R2
     M=D
     @returnaddress1
     D=A
     @pushR2
     0 ; jmp
  returnaddress1:

     @X                ; now push X
     D=M
     @R2
     M=D
     @returnaddress2 
     D=A
     @pushR2
     0 ; jmp
  returnaddress2:

     @returnaddress3   ; pop and compare the values
     D=A
     @EQ
     0 ; jmp
  returnaddress3:

此时，OP可以生成代码将D推入堆栈：

     @R2                ; push D onto stack
     M=D
     @returnaddress4 
     D=A
     @pushR2
     0 ; jmp
  returnaddress4:

或者他可以生成代码来根据D的值进行分支：

     @jmptarget
     EQ ; jmp

- Ira Baxter

---

这也是我的第一个想法，但我想象中可能漏掉了什么。感谢您的绝佳答案。但还有一个问题：我在哪里声明没有间接寻址？ - Koray Tugay

@KorayTugay：你并没有。你提供了文档的副本；我查看了原件，那就是我最初拥有的全部数据。你唯一的“罪过”是指向一个似乎是关于指令集唯一信息的文档。重新阅读一下你的问题评论，看看思路是如何演变的。我给书的作者发了一条消息，说将指令集文档分开不是个好主意。顺便说一句：我实际上查看了由Jack生成的代码，以确信自己理解了它在做什么。 - Ira Baxter

谢谢您。虽然我最终使用了一个更原始、没有子程序的 eq 实现，但我发现您的子程序实现非常有启发性。在运行这门课程时，我从未想过在汇编级别实现子程序。 - Rudi Kershaw

这将导致执行速度极慢。调用推送子程序的代码比编写原始推送要长，一个5行操作变成了一个18行的混乱。此外，栈指针应按照惯例始终指向下一个可用插槽，因此请注意，这种推送方法需要在每个其他操作中进行范式转换。 - Matheus Leão

@MatheusLeão：人们通过构建解释器，有意放弃性能以缩短实现时间来驯服丑陋的指令集。 - Ira Baxter

@IraBaxter 没关系，但是Hack架构本身的ROM容量非常有限。仅凭这种方法可能无法安装操作系统。 - Matheus Leão

Answer 2

正如我在上一条评论中所写的那样，有一种无分支的方法，因此你需要直接从操作数计算返回值。

让我们先来看看像“eq”这样简单的操作。

• 如果我理解正确，eq a,d就像是a=(a==d)
• true是0xFFFF，false是0x0000

• 所以如果a==d，那么a-d==0，这可以直接使用

  1. 计算a=a-d

  2. 计算a的所有位的OR级联

     • 如果结果为0，则返回0
     • 如果结果为1，则返回0xFFFF
     • 这可以通过表格或0-OR_Cascade(a)来实现

  3. OR级联

     • 我在你的描述中没有看到任何位移操作
     • 所以你需要使用a+a代替a<<1
     • 如果需要进行右移操作，则需要实现除以2

因此，当我总结这个eq a,d时，可能会像这样：

• a=a-d;
• a=(a|(a>>1)|(a>>2)|...|(a>>15))&1
• a=0-a;
• 您只需要将其编码到您的汇编程序中
• 由于您没有直接支持除法或移位，因此可能更好
• a=a-d;
• a=(a|(a<<1)|(a<<2)|...|(a<<15))&0x8000
• a=0-(a>>15);

较小和较大的比较要复杂得多

• 你需要计算减法的进位标志
• 或使用结果的符号（结果的最高有效位）
• 如果将操作数限制为15位，则只需计算第15位
• 对于完整的16位操作数，您需要计算结果的第16位
• 为此，您需要了解相当多的逻辑电路和ALU求和原理
• 或将值分成8位对，并进行2x8位减法级联
• 因此，a=a-d 将变成：
• sub al,dl
• sbc ah,dh
• 进位/符号在结果的第8位中，可以访问该位

- Spektre

---

我觉得你会发现实现右移或除以二相当困难。 - Ira Baxter