如何为Hack Assembly语言编写'eq'解释器？

I am reading and studying The Elements of Computing Systems but I am stuck at one point. Sample chapter skip the next 5 instruction s can be found here.

我正在阅读和研究计算系统的元素,但我一度陷入困境。示例章节跳过下面的5条指令可以在这里找到。

Anyway, I am trying to implement a Virtual Machine (or a byte code to assembly translator) but I am stuck at skip the next 5 instruction one point.

无论如何,我正在尝试实现一个虚拟机(或一个字节代码到汇编转换器),但我坚持跳过下一个5指令一点。

You can find the assembly notation here.

您可以在此处找到装配符号。

The goal is to implement a translator that will translate a specific byte code to this assembly code.

目标是实现将特定字节代码转换为此汇编代码的转换器。

An example I have done successfully is for the byte code

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

push constant 5

which is translated to:

这被翻译成:

@5
D=A
@256
M=D

As I said, the assembly language for Hack is found in the link I provided but basically:

正如我所说,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]

Well this was pretty straight forward. By definition memory location 256 is the top of the stack. So

嗯这很直接。根据定义,存储器位置256是堆栈的顶部。所以

push constant 5
push constant 98

will be translated to:

将被翻译为:

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

which is all fine..

这一切都很好..

I also want to give one more example:

我还想再举一个例子:

push constant 5
push constant 98
add

is translated to:

被翻译成:

@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

I think it is pretty clear.

我认为很清楚。

However I have no idea how I can translate the byte code

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

eq

to Assembly. Definition for eq is as follows:

到大会。 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.

其中三个命令(eq,gt,lt)返回布尔值。 VM表示真和假,分别为????-1(减1,0xFFFF)和0(0,0x0000)。

So I need to pop two values to registers A and D respectively, which is quite easy. But how am I supposed to create an Assembly code that will check against the values and push 1 if the result is true or 0 if the result is false?

所以我需要分别向寄存器A和D弹出两个值,这很容易。但是我应该如何创建一个将检查值的汇编代码,如果结果为true则按1,如果结果为false则按0?

The assembly code supported for Hack Computer is as follows:

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

I can do something like:

我可以这样做:

push constant 5
push constant 6
sub

which will hold the value 0 if 2 values pushed to the stack are equal or !0 if not but how does that help? I tried using D&A or D&M but that did not help much either..

如果推送到堆栈的2个值相等,它将保持值0;如果不是,则保持为0,但这有什么帮助?我尝试使用D&A或D&M,但这也没有多大帮助..

I can also introduce a conditional jump but how am I supposed to know what instruction to jump to? Hack Assembly code does not have something like "skip the next 5 instructions" or etc..

我也可以引入一个条件跳转,但我怎么知道要跳转到什么指令? Hack汇编代码没有“跳过下5条指令”等等。

[edit by Spektre] target platform summary as I see it

[Spektre编辑]我看到的目标平台摘要

• 16bit Von Neumann architecture (address is 15 bits with 16 bit Word access)

16位冯·诺依曼架构(地址为15位,16位字访问)

• Data memory 32KW (Read/Write)

数据存储器32KW(读/写)

• Instruction (Program) memory 32KW (Read only)

指令(程序)存储器32KW(只读)

• native 16 bit registers A,D

本机16位寄存器A,D

• general purpose 16 bit registers R0-R15 mapped to Data memory at 0x0000 - 0x000F

通用16位寄存器R0-R15映射到0x0000 - 0x000F的数据存储器

• these are most likely used also for: SP(R0),LCL(R1),ARG(R2),This(R3),That(R4)

这些最有可能用于:SP(R0),LCL(R1),ARG(R2),这(R3),那(R4)

• Screen is mapped to Data memory at 0x4000-0x5FFF (512x256 B/W pixels 8KW)

屏幕映射到数据存储器0x4000-0x5FFF(512x256 B / W像素8KW)

• Keyboard is mapped to Data memory at 0x6000 (ASCII code if last hit key?)

键盘映射到0x6000的数据存储器(如果是最后一个键,则为ASCII码?)

2 个解决方案

#1

It appears there is another chapter which more definitively defines the Hack CPU. It says:

看来还有另一章更明确地定义了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

Hack CPU由第2章中指定的ALU和称为数据寄存器(D),地址寄存器(A)和程序计数器(PC)的三个寄存器组成。 D和A是通用的16位寄存器,可以通过算法和逻辑指令操作,如A = D-1,D = D | A等,遵循第4章中规定的Hack机器语言。 -register仅用于存储数据值,A寄存器的内容可以用三种不同的方式解释,具体取决于指令的上下文:作为数据值,作为RAM地址或作为ROM地址

So apparently "M" accesses are to RAM locations controlled by A. There's the indirect addressing I was missing. Now everything clicks.

显然“M”访问是由A控制的RAM位置。我缺少间接寻址。现在一切都点击了

With that confusion cleared up, now we can handle OP's question (a lot more easily).

随着这种混乱被清除,现在我们可以处理OP的问题(更容易)。

Let's start with implementing subroutine calls with the stack.

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

     ; 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 ****

The "push constant" instruction can easily be translated to store into a dynamic location in the stack:

“推送常量”指令可以轻松转换为存储到堆栈中的动态位置:

     @<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

If we wanted to make a subroutine to push constants:

如果我们想要一个子程序来推动常量:

   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

And to call the "push constant" routine:

并称为“推动常量”例程:

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

To push a variable value X:

要推送变量值X:

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

A subroutine to pop a value from the stack into the D register:

一个子程序,用于将值从堆栈弹出到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

Now, to do the "EQ" computation that was OP's original request:

现在,要执行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

Putting it all together:

把它们放在一起:

     @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:

At this point, OP can generate code to push D onto the stack:

此时,OP可以生成将D推入堆栈的代码:

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

or he can generate code to branch on the value of D:

或者他可以生成代码来分支D的值:

     @jmptarget
     EQ ; jmp

#2

As I wrote in last comment there is a branch less way so you need to compute the return value from operands directly

正如我在上一篇评论中写的那样,有一个分支更少的方式,所以你需要直接从操作数计算返回值

Lets take the easy operation like eq for now

让我们像eq一样轻松操作

• if I get it right eq a,d is something like a=(a==d)

如果我把它做对了eq a,d就像a =(a == d)

• true is 0xFFFF and false is 0x0000

true为0xFFFF,false为0x0000

• So this if a==d then a-d==0 this can be used directly

  所以这个如果a == d然后a-d == 0这可以直接使用

  1. compute a=a-d

  2. compute OR cascade of all bits of a

     计算a的所有位的OR级联

     • if the result is 0 return 0

     如果结果为0则返回0

     • if the result is 1 return 0xFFFF

     如果结果为1则返回0xFFFF

     • this can be achieved by table or by 0-OR_Cascade(a)

     这可以通过表格或0-OR_Cascade(a)来实现

  3. the OR cascade

     OR级联

     • I do not see any bit shift operations in your description

     我没有在您的描述中看到任何位移操作

     • so you need to use a+a instead of a<<1

     所以你需要使用+ a而不是<< 1

     • and if shift right is needed then you need to implement divide by 2

     如果需要右移,那么你需要实现除以2

So when I summarize this eq a,d could look like this:

因此,当我总结这个方程式时,d看起来像这样:

• a=a-d;
• a=(a|(a>>1)|(a>>2)|...|(a>>15))&1
• a=0-a;
• you just need to encode this into your assembly

你只需要将它编码到你的程序集中

• as you do not have division or shift directly supported may be this may be better

因为你没有直接支持分裂或转移可能这可能会更好

• a=a-d;
• a=(a|(a<<1)|(a<<2)|...|(a<<15))&0x8000
• a=0-(a>>15);

the lower and greater comparison are much more complicated

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

• you need to compute the carry flag of the substraction

你需要计算减法的进位标志

• or use sign of the result (MSB of result)

或使用结果的符号(结果的MSB)

• if you limit the operands to 15 bit then it is just the 15th bit

如果将操作数限制为15位,那么它只是第15位

• for full 16 bit operands you need to compute the 16th bit of result

对于完整的16位操作数,您需要计算结果的第16位

• for that you need to know quite a bit of logic circuits and ALU summation principles

为此你需要了解相当多的逻辑电路和ALU求和原理

• or divide the values to 8 bit pairs and do 2x8 bit substraction cascade

或将值除以8位对并进行2x8位减法级联

• so a=a-d will became:

所以a = a-d将成为:

• sub al,dl
• sbc ah,dh
• and the carry/sign is in the 8th bit of result which is accessible

并且进位/符号位于可访问的结果的第8位