algorithm - 如何为 Hack 汇编语言编写 'eq' 的解释器？

Question

我正在读书学习The Elements of Computing Systems但我被困在某一时刻。示例章节跳过下5条指令可查here .

无论如何，我正在尝试实现一个虚拟机(或一个字节码到汇编翻译器)，但我被困在跳过接下来的 5 条指令。

你可以找到汇编符号here .

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

我成功完成的一个例子是字节码

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

到 assembly 。 eq的定义如下:

Three of the commands (eq, gt, lt) return Boolean values. The VM represents true and false as 􏰁-1 (minus one, 0xFFFF) and 0 (zero, 0x0000), respectively.

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

Hack Computer支持的汇编代码如下:

我可以这样做:

push constant 5
push constant 6
sub

如果压入堆栈的 2 个值相等，它将保存值 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 代码是否是最后一次按下的键？)

Answer 1

似乎还有另一章更明确地定义了 Hack CPU。它说:

The Hack CPU consists of the ALU specified in chapter 2 and three registers called data register (D), address register (A), and program counter (PC). D and A are general-purpose 16-bit registers that can be manipulated by arithmetic and logical instructions like A=D-1 , D=D|A , and so on, following the Hack machine language specified in chapter 4. While the D-register is used solely to store data values, the contents of the A-register can be interpreted in three different ways, depending on the instruction’s context: as a data value, as a RAM address, or as a ROM address

显然，“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