How can I write an interpreter for 'eq' for Hack Assembly language?

Question

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.

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.

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:

@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

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:

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.

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?

The assembly code supported for Hack Computer is as follows:

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

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

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

• 16bit Von Neumann architecture (address is 15 bits with 16 bit Word access)
• Data memory 32KW (Read/Write)
• Instruction (Program) memory 32KW (Read only)
• native 16 bit registers A,D
• general purpose 16 bit registers R0-R15 mapped to Data memory at 0x0000 - 0x000F
• these are most likely used also for: SP(R0),LCL(R1),ARG(R2),This(R3),That(R4)
• Screen is mapped to Data memory at 0x4000-0x5FFF (512x256 B/W pixels 8KW)
• Keyboard is mapped to Data memory at 0x6000 (ASCII code if last hit key?)

Answer 1

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

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

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

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

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

   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:

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:

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

     @jmptarget
     EQ ; jmp

Answer 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

• if I get it right eq a,d is something like a=(a==d)
• true is 0xFFFF and false is 0x0000

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

  1. compute a=a-d

  2. compute OR cascade of all bits of a

     • if the result is 0 return 0
     • if the result is 1 return 0xFFFF
     • this can be achieved by table or by 0-OR_Cascade(a)

  3. the OR cascade

     • I do not see any bit shift operations in your description
     • so you need to use a+a instead of a<<1
     • and if shift right is needed then you need to implement divide by 2

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

• 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)
• if you limit the operands to 15 bit then it is just the 15th bit
• for full 16 bit operands you need to compute the 16th bit of result
• for that you need to know quite a bit of logic circuits and ALU summation principles
• or divide the values to 8 bit pairs and do 2x8 bit substraction cascade
• so a=a-d will became:
• sub al,dl
• sbc ah,dh
• and the carry/sign is in the 8th bit of result which is accessible