Lab 5

Unsigned (and Multi-Word) Arithmetic

Objectives

In this lab exercise you will work with functions which manipulate unsigned 16-bit numbers. In Part B, you would use these functions to deal with multi-word numbers..

Part A: What you will do in lab today

·         Download the file unsadd.asm. Load it into the editor, then read it over and see if you can understand how it works. Here is an explanation:

The function UNSADD adds two unsigned 16-bit numbers. That is, all 16 bits are used, so that each number can be in the range 0 to 65535; there are no negative numbers. Before you call the function, put one number into R0 and the other into R1. When the function returns, R0 will contain the 16-bit sum and R1 will indicate overflow. More specifically, if the sum does not overflow (i.e. the answer is <= 65535), the function sets R1 to zero. If the sum did overflow (i.e. the answer is >= 65536), the low-order 16 bits of the answer are in R0, and R1 is set to one.

Some thought should cause you to reach the conclusion that the unsigned addition algorithm must deal with three different cases, summarized in this table.

R0 <= 32767

R1 <= 32767

Case

What to do

Yes

Yes

Case 1

Sum in R0. No overflow can possibly occur..

No

No

Case 2

Sum in R0. Guaranteed overflow.

Yes

No

Case 3

Sum in R0. Possible overflow.

No

Yes

Case 3

 

The only complicated part is Case 3. There you must detect whether overflow has occurred, and set R1 accordingly. Remember, the LC-3 instruction set can only directly handle 16-bit signed numbers, so the algorithm must treat bit 15 as just the high-order bit, but the LC-3 instructions will treat it as the sign bit.

 

·         Now single-step through the main program. You can use the “Step Over” button to execute the function as a whole. Figure out what the answers are supposed to be for the sample, and check that the function is operating correctly. Add comments to say what the answers are supposed to be.

·         Now single-step through the function, using the “Step Into” button. Observe how the function accomplishes its tasks.

·         Now add more data to the main program, and more calls of the function. For each set of data, calculate what the answer is supposed to be, put that into comments, and confirm that the function is working properly. Do not just pick some random data; pick numbers that exercise all the paths through the function. Be sure to include “corner cases”, such as when one or both numbers, or the sum, are at or near the limits (e.g., 32767, 32768).

·         If you find any errors in the code, fix them and include a comment saying what you did and why. Hint: If I didn’t think there was an error, I wouldn’t have mentioned it.

·         You do not need to do any I/O.

·         When done, submit your unsadd.asm to web-based turnin.

Part B: Left for the Interested Student (you do not have to submit anything for this part)

In this part you will use the function from Part A, and add other functions, to handle multi-word numbers. Do the following:

 

·         Write a function to add two signed 32-bit integers. Each signed 32-bit number consists of two 16-bit words, one of which is the Most Significant Word (MSW) and the other is the Least Significant Word (LSW). Here is how a value is stored in memory or registers.

o   The left-most (i.e. highest-order) bit of the MSW is the sign bit. When it is 0, the value of the number is represented by the remaining 31 bits. So, for example, the 32-bit number x04000001 has MSW = x0400 and LSW = x0001. In other words, it has a 1 in bit 0, another 1 in bit 25, and zeroes everywhere else. Or, looked at another way, it has a 1 in bit 0 of the LSW and another 1 in bit 10 of the MSW. Its value is 1 * 226 + 1 * 21 = 67108865.

o   For negative numbers, the sign bit (bit 15 of the MSW, or bit 31 of the complete number) is 1. The number is stored in 2’s-complement notation, just like the 16-bit signed numbers. So, for example, xFFFFFFFF has the value -1.

 

OK, so how does a 32-bit add function work? First off, you need to pass in four registers. One pair holds the MSW and LSW of the first number. The other pair holds the two words of the other number. The answer has to come back in three registers: the two registers holding the two words of the answer (i.e. the sum), plus a third register to hold the overflow / underflow flag (1 or  -1).

 

Here is how it works:

o   First add the two LSWs together. Be sure to use the unsigned add function. The sum becomes the LSW of the answer.

o   Then add the two MSWs together. Since this word is signed, you should be able to use the regular ADD instruction (but see below).

o   Then add in the carry if one was generated from the unsigned add function.

o   Now comes the hard part. You need to generate the carry / borrow flag.

o   If you added two positive numbers, and the sign bit in the answer is 1, this means that the sum has overflowed. In other words, the sum is too big to fit in a signed 32-bit number. So set the overflow / underflow flag to 1.

o   If you added two negative numbers and the sign bit in the answer is zero, that means the sum has underflowed; in other bits, it is so negative that it will not fit in a siged 32-bit number. So set the overflow / underflow flag to -1 (i.e. xFFFF).

o   If neither of these cases occurred, set the flag to 0.

o   Remember that this overflow or underflow could happen either during the second addition (of the two MSWs) or the third addition (adding the carry). Something to think about: What if it happens both times?

 

Before you write the code, be sure to design it and write down your decisions. In particular:

o   Decide which registers will hold which values: On entry, at exit, and during execution of the function.

o   Figure out what all the various cases are: Two positives, with and without carry, etc.

o   Choose some test data which will thoroughly exercise all the cases, including the corner cases. For example, xFFFFFFFF + 1 should equal 0 with no overflow. But x7FFFFFFF + 1 should equal x80000000 with overflow.

 

Write the function code and test it thoroughly from your main program. In comments, be sure to say what the values are and what the expected answers are. Feel free to use a calculator (such as the one which comes with Microsoft Windows) to check your work; just remember that the calculator might not enforce a maximum number of bits.