No easy way

Here is a question… Is there a fancy or efficient way to negate a number in Y86.

Sorry, unfortunately Y86 is limited in its bit operations, so almost any operation that you can imagine will end up costing more calories than a simple subtraction from 0.

What we can do is to optimize the establishment of 0 (by using XOR) and the preservation/restoration of the interim value (by using the stack):

 # Negate a number in %ebx by subtracting it from 0
  irmovl $999, %eax    // Some random value to prove non-destructiveness
  irmovl Stack, %esp   // Set the stack
  pushl %eax           // Preserve 

  irmovl $300, %ebx
  xorl %eax, %eax
  subl %ebx,%eax
  rrmovl %eax, %ebx

  popl %eax             // Restore 

 .pos 0x0100


Another Y86 Pipeline Simulator — providing state and CPI information

Thanks to Shu Ding from Shanghai, we have access to another Y86 pipeline simulator.

This simulator does not have the break point facilities of the previously discussed simulator, but it provides information about the state of the Y86 simulator and CPIs, which is quite interesting. Additionally, it has a cool SCI-FI look.

But (and this is a biggies)… It only works on yo code, so you still need to compile the Y86 ys code somewhere else.

And, of course, this Y86 simulator does not support any of the handy-dandy extensions of our Y86 Simulator such as input, output, multiplication, conditional move, division, and modulo instructions and breakpoints and single stepping) To get support for these instructions and full Y86 ys compilation support, you want to use our super-duper Y86 simulator.

Another Y86 Simulator

Multiplication through looping… bits anyone?

Y86 does not have a multiplication instruction or bit manipulation instructions, so when we need multiplication in Y86 programs we have to construct it by – horror of horrors – looping.

There are other ways to do this, but, to keep it simple, let’s use the ADDL instruction in line with this simple example of multiplication by four:

addl %eax, %eax
addl %eax, %eax
addl %eax, %eax
addl %eax, %eax

Simple enough, right? Well, at least until you think about things like overflow and signage, which need to be handled (consider what happens if you solve Y * X by looping Y times over X when Y is negative… Boom!)

So, here is what we need to do:

  • Build a multiplication routine for positive values, accounting for overflow.
  • Figure out what sign the result should have.
  • Convert the operands to absolute values (using a negation routine.)
  • Call the multiplication routine on the absolute values.
  • Consider and handle overflow.
  • Convert the resulting amount to negative if necessary.

The rest is up to you. By the way… the maximum limit of a signed 32-bit integer value (as designated by a .LONG value) is 231-1 or 2,147,483,647.

The keen reader will have noticed that we just created a left shift bit operator by adding EAX to EAX. 00001 added to 0001, for instance, yields 0010, and, so, we performed a neat little bit shift to the left. Insert victory shuffle here!

Can you make up more constructive bit manipulations? If so, here are a couple of challenges for you:

Human speak: 
   Check if an integer, X, is odd.
Bit pseudo: 
   if (X & 1) == 0
      // even
      // odd

Human speak:
   Turn off the rightmost 1-bit in an integer, X.
Bit pseudo: 
   y = x & (x-1)

Human speak:
   Isolate the rightmost 1-bit, in an integer, X.
Bit pseudo: 
   y = x & (-x)

Human speak:
  Isolate the rightmost 0-bit in an integer, X(note that this is the opposite of the above challenge.)
Bit pseudo: 
   y = ~x & (x+1)

Human speak:
   Turn on the rightmost 0-bit in an integer, X.
Bit pseudo: 
   y = x | (x+1)


Hosed by YAS – with some help from YIS

Chul Kwon, a former student at the University of Maryland, encountered a problem when compiling his first Y86 program.

On the web site Stack Overflow, he wrote:

I’m trying to learn Y86, so I made a very simple program. It has an array of three long integers, and each block is filled by asking the user for an input through rdint

Note that RDINT is non-standard. It simply reads an integer from the user.

Here is Chul’s program:

Main:   irmovl  Array, %edx
rdint   %eax
rmmovl  %eax, 0(%edx)
rdint   %eax
rmmovl  %eax, 4(%edx)
rdint   %eax
rmmovl  %eax, 8(%edx)

irmovl  $10, %edi
Print:  irmovl  Array, %edx
    mrmovl  0(%edx), %eax
    wrch    %eax
    wrch    %edi
    mrmovl  4(%edx), %eax
    wrch    %eax
    wrch    %edi
    mrmovl  8(%edx), %eax
    wrch    %eax
    wrch    %edi


    .align 4

    .long 0
    .long 0
    .long 0

Note that WRCH is non-standard. It simply writes a character on the user’s display.

Entering 0, 1, and 2 as input, Chul expected to see 0, 1, and 2 be output, but this did not happen. Instead he got:

(three blank lines below)

Stopped in 22 steps at PC = 0x47.  Exception 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%edx:   0x00000000      0x0000004c
%edi:   0x00000000      0x0000000a

Changes to memory:
0x0004: 0x024008f2      0x00000001
0x0008: 0x00000000      0x00000002

Changes to memory: 0x0004: 0x024008f2      0x00000001 0x0008:
0x00000000      0x00000002

Boom! What is going on? Execution terminates OK, but there is no useful output, only three blank lines, and YIS reports that the top memory addresses (where the program resides) have changed.

This is a classic Y86/YAS problem. The Lack of a final new-line in the ys file, causes YAS to misbehave.

The problem originates with an error in YAS. If Chul had looked in the yo file produced by YAS he would have seen that the last .LONG 0 statement never got defined.

Moreover, he would probably see that the first line opcode in the yo file is 0x00, i.e. NOP (when YAS encounter a final instruction without an associated newline, it wraps it around, screwing up the yo file)

This means that Chul lost the first IRMOVL ARRAY, %EDX statement. In fact the statement becomes some sort of nonsense, probably 0x00000000, i.e. 4 NOPs, and so the program writes the first read character, ‘0’, to the location pointed to by EDX (i.e. 0x00000000) into the first instruction (which was now probably 4 NOPs — remember that the RDINT reads a character, but it ends up in a 4 byte register and is saved as such.)

So the program is writing 0x00000000 to an address that was already 0x00000000 (thank you YAS!,) which to YIS means that the register was not changed and therefore it is not shown in the “Changes to Memory” dump section.

Once this travesty is complete, the program repeats the nonsense with the second read character, ‘1’, writing 0x00000001 in the second memory word (neatly overwriting the instruction in that location,) and with the third read character, ‘2’, writing 0x00000002 in the third word (overwriting the instruction in that location.)

Now, of course, Chul was completely hosed! In the print section, his program reset the pointer to the array (using EDX,) and attempted to print the content, but ARRAY(0), ARRAY(4), and ARRAY(8) contains 0x00000000, because that is what it was defined as (using the .LONG 4 statements for ARRAY(0) and for ARRAY(4), and, automatically for, ARRAY(8) since the default set-up for undefined memory in Y86 is 0x00000000.

And so, the program printed x’00’ three times (because it prints one character from a 4 byte word,) which, of course, is junk, resulting in 3 empty lines.

The keen reader will note that this fits with the dump from YIS: (1) EAX does not show as it is unchanged from 0x00000000, its initial value; (2) EDX and EDI look A-OK, with EDI pointing to ARRAY(8); and (3) the only memory that has changed is the second and third word of the program (which have been overwritten with 0x00000001 and 0x00000002, respectively)

So, in summary:

  • YAS makes an initial mistake. Chul must overcome this problem by adding a new-line after the last .LONG 0 statement.
  • YIS adds to the misery by misleading Chul because, critically!, it does not throw exceptions when Y86 overwrites code with data (which, of course, also means that you can create self-modifying code in Y86, but that is another story.)

Easy Y86

y86SimulatorYAS/YIS/SIMM are great tools — except when they aren’t. So what about an alternative Y86 simulator? Perhaps a web based one that is interactive and nice looking, too?

We have added a link to a web-based Y86 simulator that even supports single stepping and conditional breakpoints.

Note, however, that this simulator has a number of problems and it does not support any of the handy-dandy extension instructions of our Y86 Simulator (input/output/multiplication/conditional move/modulo/division.) To get support for these instructions and full Y86 ys compilation support, you want to use our super-duper Y86 simulator.

Read more about it here.

Spot the problem

This is a classic beginner problem in Y86 classes:

Write a program that creates a sum of all inclusive integers between X and Y, with the sum, SUM, and X and Y being global variables.

Solving this problem requires a loop, and the point of the problem is to learn loop management.

The problem is fairly trivial, but things can go wrong. Below is an example of how it went wrong for one student. Can you find the problem? If not, scroll past the program to see the answer.

   .pos 0
   init:   irmovl Stack, %esp  // Set up stack pointer
   irmovl Stack, %ebp          // Set up base pointer
   call main                   // Call main program
   halt                        // Terminate program

   main:   pushl %ebp          // Setup
   rrmovl %esp, %ebp

   pushl %ebx                  // Declare x local register
   irmovl x, %ebx      
   pushl %esi                  // Declare y local register
   irmovl y, %esi      
   pushl %eax                  // Declare sum
   irmovl sum, %eax
   pushl %edi                 //  Set a constant 1
   irmovl $1, %edi            // get the loop started

   subl %ebx, %esi            // %esi = y-x
   jl L3                      // Ends function if x greater than y

   irmovl y, %esi             // %esi = y
   addl %ebx, %eax            // sum += x
   addl %edi, %ebx            // x++
   jmp L2                     // Go to beginning of loop

   rmmovl %eax, (%eax)        // Assign value to sum 

   rrmovl %ebp, %esp          // Finished.  Perform house cleaning
   popl %ebx       
   popl %esi
   popl %edi
   popl %eax
   popl %ebp

   ret                         // Back where we belong!

   .align 4                    // Get on the boundary
   x: .long 1                  // Set X to 1
   y: .long 4                  // Set Y to 4
   sum: .long 0

   .pos 0x200
   Stack: .long 0

Do you see the problem? No? Here is a clue. Focus on IRMOVL. See it?

Ok, here it is… the program assigns the addresses of X and Y to registers instead of the appropriate values.

Let’s run the program and stop after the assignment of X.

After X

As you see (if you click on the image to zoom in,) the EBX register has been assigned x’60 as a value instead of 1.  And guess what?  x’60 is precisely the location of X.  

Let’s run the program again, this time stopping after the assignment of Y.

After Y

As you see, the ESI register has been assigned x’64 as a value instead of 4.  And guess what?  x’64 is precisely the location of Y.

Know how to fix it? No? Try using MRMOVL instead.

Now look at the assignment of SUM. Anything you would want to change here?

This is a classic mistake. The clue could be found in the X and Y values.

Translating from IA-32 to Y86.. What the heck!

IA-32 is great… Almost as great as Y86.

Recently, students at a university were challenged to translate an IA-32 program to Y86. To their horror, they discovered that Y86 has no CMP instructions, which was a problem since the IA-32 program contained:

   cmpl %ebx, %ecx

The IA-32 CMPL instruction compares two values (operand1 and operand2) by subtracting operand1 from operand2, but! critically does not store the result, only changes the flags. CMPL is typically executed in conjunction with conditional jumps based on the condition code (cc.)

Y86 does not have a CMPL instruction. However, it does have has SUBL, PUSHL and POPL instructions.

So cmpl %ebx, %ecx can be converted to the following Y86 code:

   pushl %ecx
   subl  %ebx, %ecx
   popl  %ecx

AI-32’s CMPL instructionis exactly the same as Y86’s SUBL instruction, with the difference that CMPL does not store the result, it only updates the flags. So CMPL can always be replaced with the PUSHL, SUBL, POPL combination shown above, which preserves the register.

P.S. As always, make sure that there is enough space in the stack!