translating eq to asm

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

translating eq to asm

amber
This post was updated on .
I an trying to translate eq to asm so that the number of asm lines will be minimal (without reference gt or lt) but I can't seem to write it in less than 11 lines:

[Source code removed by admin.]

is there a shorter way if writing it?
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

cadet1620
Administrator
Your code as posted is 10 instructions (labels don't count), but it is computing "not equal".

Put an M=-1 after the MD=D-M so that the return value is -1 if x-y==0, and change the M=-1 before (END) to M=0 so that the x-y!=0 case returns 0. This makes it 11 instructions.

My best is also 11 instructions, coded a bit differently.

The shortest code that you can write for an eq, gt, or lt command is an assembly language call to a common routine that your vm writes in the bootstrap:

    @$RIP$nnn
    D=A
    @$$EQ   // or $$GT or $$LT
    0;JMP
    ($RIP$nnn)

This is only 4 instructions per vm statement. The $$EQ function does all the work. It's a bit more than 11 instructions because it needs to save the RIP in D before the compare and jump to the RIP afterwards.

This same Assembly language subroutine is really helpful with call and return code in project 8; that code is a lot longer than the compare code!

[Please edit your post to remove the (mostly) functional code. We want students to develop their own solutions.]

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

amber

Thanks for the quick reply!
According to you're answer true is stored as -1 and false as 0. I thought it was the other way around...
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

cadet1620
Administrator
amber wrote
According to you're answer true is stored as -1 and false as 0. I thought it was the other way around...
You are not the first person to get this backwards.

Chapter 7 says, "The VM represents true and false as -1 (minus one, 0xFFFF) and 0 (zero, 0x0000), respectively."

I don't like to use the "respectively" sentence structure in documentation for just this reason; it causes confusion because the value assignments are not next to value names.  I would have written this as,

"The VM represents true as -1 (minus one, 0xFFFF), and false as 0 (zero, 0x0000)."

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

amber
thanks for the explanation!
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

linse
In reply to this post by cadet1620
Thanks for the clarification on this.

In the bottom right-hand corner of slide 14 of the lecture pdf, it states: "actually true and false are stored as 0 and -1, respectively."

Unless I'm being immeasurably dense, this (slide 14) contradicts chapter 7 as you've cited it, and the behaviour of the VM Emulator.
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

cadet1620
Administrator
No, you are not being dense...

There is definitely a problem with the slides. Chapter 7 slides 11 and 14 and Chapter 9 slide 20 all misstate the values for true and false.

Book Chapter 7 (7.2.2) and Chapter 11 (11.2.1 § Constants) define true=-1 and false=0.

You can also see that the supplied JackCompiler matches the book by compiling this program and running it in the VM Emulator.
// File: Main.jack
class Main {
    function void main() {
        var bool x;
        let x = true;
        do Output.printString("true = ");
        do Output.printInt(x);
        do Output.println();
        let x = false;
        do Output.printString("false = ");
        do Output.printInt(x);
        return;
    }
}
It outputs "true = -1 false = 0".

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

rgravina
In reply to this post by cadet1620
I had a fair bit of trouble with eq also, but this post helped thanks :)

Basically, I found using a function worked for me. Here's what I did:

At the site of the eq instruction:

1. Store arg2 - arg1 in @R13. This can be used for an eq, lt or gt comparison (later)
2. Create a label ($$RIP:n) at the end of the instruction, where n is some globally incrementing value (to ensure label is unique). Load this into @R14.
3. @SP should be pointing to the address after the top value of the stack (should already be like this)

Then, at the top of the program, create a label ($$EQ). Jump to here after doing the above. This will look at @R13 (is it zero, negative or positive?) and then set @SP - 1 to either -1 or 0. Then, you jump back to the address stored in @R14.

It might be possible to use D and A more to avoid the accesses to @R13 and @R14, but I found A was being constantly overwritten (whenever you want to access RAM or jump) and so was D for various calculations.

After implementing eq, gt and lt should be very similar.

Hope this helps and is not giving too much away! I think it would be nice if the book had a small hint, like "hint: to implement eq, gt and lt you will need to jump and have some way of knowing where to return to". At this point in the book we haven't been introduced to assembly functions, so it might be useful to introduce them (perhaps in Chapter 4? If I missed it, excuse me!). The assembly language only allows comparisons as part of a jump, so it might be possible to infer this, but myself (and I think others) were wondering if it was possible to do with instructions only.

Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

WBahn
Administrator
rgravina wrote
Hope this helps and is not giving too much away! I think it would be nice if the book had a small hint, like "hint: to implement eq, gt and lt you will need to jump and have some way of knowing where to return to". At this point in the book we haven't been introduced to assembly functions, so it might be useful to introduce them (perhaps in Chapter 4? If I missed it, excuse me!). The assembly language only allows comparisons as part of a jump, so it might be possible to infer this, but myself (and I think others) were wondering if it was possible to do with instructions only.
Although this is resurrecting an old thread, I think it is worth pointing out a clarification for those that come across this in the future.

While you DO need to do a jump in order to implement the relational VM commands, you do NOT need to have some way of knowing where to return to since the commands can be implemented with purely inline code (the jump is just needed to implement an if() structure). This is almost certainly the route that the authors expected readers to take and, in general, they tend to steer readers toward a single, workable approach and seldom go into alternatives since that tends to explode the depth of the discussion which is something they've chosen to zealously avoid given the incredible breadth of the project.

Personally, though I love to learn about alternatives and pros and cons, I think the authors are completely correct in taking this route. This book covers a meaningful portion of at least four courses and good tidbits of a couple more; those other courses are a much better place to get into that depth (which is not to say that they always do).
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

cliu
I'm still not sure I understand the best way to implement the eq, gt, lt operations.

I think I need a jump to code that sets the value to true, but if the jump condition is not met, I need to jump past that block of code, so am ending up with the following:

@TRUE
M;JEQ
M=0
// JUMP PAST TRUE BLOCK
@END
0;JMP
(TRUE)
M=-1
(END)

Is this correct? What is the comment that things can be done "inline" mean?
Also, to keep the TRUE and END labels unique, I need to append a number at the end, correct? I understand that, but was wondering if there's a reason for using $ and : symbols as in some of the comments above.

Finally, for the "bootstrap" method, does that mean having a single @TRUE and @END label to jump to that is appended to the end of every assembly code translation? However, that would still require a jump back to the main code, correct?

Thanks!
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

WBahn
Administrator
cliu wrote
I'm still not sure I understand the best way to implement the eq, gt, lt operations.

I think I need a jump to code that sets the value to true, but if the jump condition is not met, I need to jump past that block of code, so am ending up with the following:

@TRUE
M;JEQ
M=0
// JUMP PAST TRUE BLOCK
@END
0;JMP
(TRUE)
M=-1
(END)

Is this correct? What is the comment that things can be done "inline" mean?
"Inline" basically means that you make a separate copy of the needed code wherever it is used instead of calling a shared piece of code and then returning. The usual tradeoff is that inlined code is faster (since there is no need to do the jumps required to use shared code) but the size of the code grows (because you now have multiple copies of the same code).

Also, to keep the TRUE and END labels unique, I need to append a number at the end, correct? I understand that, but was wondering if there's a reason for using $ and : symbols as in some of the comments above.
It's just a naming convention that he adopted to ensure that he couldn't inadvertently end up with duplicate labels.

Finally, for the "bootstrap" method, does that mean having a single @TRUE and @END label to jump to that is appended to the end of every assembly code translation? However, that would still require a jump back to the main code, correct?
Yes. Basically what you are doing is making some little subroutines in assembly that are inserted as part of the bootstrap code. You pick a memory location to store the return address (you generally don't put it on the stack) and then the assembly code you write stores a unique program label at that memory location before jumping to the subroutine. It's important that the subroutine always be able to complete it's task and return without calling another such subroutine, otherwise chaos ensues. But since this is being used to perform a very small task that is self contained, that is usually not a problem.
Reply | Threaded
Open this post in threaded view
|

Re: translating eq to asm

cliu
Thank you!! That clarifies things for me.