**Professor Shai
Simonson - CS304 - Computer Architecture
**

**Assignment 2
**

**Assembly Language Using MIPS
Arithmetic Bit Level Instructions and Applications
**

** **

Due Tuesday, February 23. (Total: 30 points)

Problems (10 points)

0. In the book. Chapters 2-3: 2.4, 2.19 (all parts), Note 2.19.1 has a typo 44 should be 4. 2.46 (all parts), 3.1, 3.2

1. OverflowSolve each problem below and indicate if the operation results in

overflow. (Assume that the first two have 6-bit storage capacity, and the last problem has 8-bit capacity). Check your work by converting to decimal.(a) Assume that the numbers are unsigned.

(b) Assume that the numbers are two's complement.110110 001101 00000001

+ 001011 + 011011 + 01111111

a. Show how to accomplish an SLL instruction using ROL (rotate left) pesudo-instruction and other MIPS commands.

2. Simulating Instructions

b. Same question for an SRA instruction.

**Program: (20 points) Reading
and Adding 64-bit Numbers
**

** **There
are two main parts to this program, but when you get them done,
they can be incorporated into one program (part c).

a. Write
MIPS code to add two 64-bit numbers.

Before you do the next part, you can test your program by hard-coding 0x 0000 1C31 and 0x BFFC F000 in the data section. Then add 0x 0000 1C31 BFFC F000 + 0x 0000 1C31 BFFC F000 and check the answer equals 0x 0000 3863 7FF9 E000. Note that in decimal this 64-bit addition is 31,000,000,000,000 + 31,000,000,000,000 = 62,000,000,000,000 = 14,435 × 2^{32} + 2,147,082,240, so the resulting two registers in decimal are: 14,435
and 2,147,082,240.

b. Write MIPS code that reads a string of digits (0-9), and stores the base 10 integer represented by that number in two 32-bit words. You may assume that the integer is small enough to be stored in 64 bits. This part of the program will allow you to directly type in decimal numbers, rather than converting them to hex and hard-coding the hex in the data section.

Method 1: Shift the AB combination left 3 times to get 8x and shift it once left to get 2x, and then add the two 64-bit numbers 8x and 2x using part (a). When shifting the AB combo left, be careful to add 1 to A when a 1 is shifted left from B.

Method 2: (probably the simplest) Each 64-bit product 10A and 10B can be computed using multu (not mult). Let the high and low 32-bit results for 10A be AH and AL respectively. And similarly, BH and BL for 10B. The 64-bit sum 10A*2^32 + 10B is equal to the concatenation of two 32-bit numbers: SH and SL, where SH = AL+ BH, and SL = BL. Note that AH will always be zero, because I guarantee that 10x will fit into 64-bits. When adding the 32-bit registers use "addu" in order to avoid an overflow error that "add" might generate.

Method 3 (The Lawson method -- not very efficient): Add*x*
to itself ten times using part (a) of this assignment.

c. Finally, write a program that accepts two large decimal integers as strings, stores each one in two 32-bit registers, adds them, and then prints out the 64-bit result in two separate 32-bit pieces.

Adding two
64-bit numbers cannot be done with a single instruction like
addition for 32-bit numbers. The
addition must be done in two stages - first the lower 32 bits
and then the upper 32 bits. The result of the two lower
32 bits is stored in the lower 32 bits of the result. If
this generates a carry (in class we discussed how to determine
this) then one must be added (or "or"-ed) to the upper 32-bit
addition. The result of the upper 32-bit addition
(possibly with this carry) is stored in the upper 32-bits of
the result. All these 32-bit additions adds should be
done with addu instructions, because there are no negative
numbers, and the bits should not be treated as two's
complement.

Before you do the next part, you can test your program by hard-coding 0x 0000 1C31 and 0x BFFC F000 in the data section. Then add 0x 0000 1C31 BFFC F000 + 0x 0000 1C31 BFFC F000 and check the answer equals 0x 0000 3863 7FF9 E000. Note that in decimal this 64-bit addition is 31,000,000,000,000 + 31,000,000,000,000 = 62,000,000,000,000 = 14,435 × 2

b. Write MIPS code that reads a string of digits (0-9), and stores the base 10 integer represented by that number in two 32-bit words. You may assume that the integer is small enough to be stored in 64 bits. This part of the program will allow you to directly type in decimal numbers, rather than converting them to hex and hard-coding the hex in the data section.

Briefly, the
algorithm works like this: You process the string from
left to right, and with each new digit you multiply the
previous result by 10 and add the numerical value of the
digit. Note that this addition is to a 64-bit number, so you
will need to use part (a) of this assignment. Also you need to
convert ascii codes of '0' through '9' to integer values 0
through 9, and perform multiplication by 10 on a 64-bit
number stored in *two* 32-bit words.

Let the upper 32 bits be A and the lower 32 bits be B, so that the 64-bit number x = A*2^32+B. There are a number of natural ways to calculate 10x = 10(A*2^32 + B) = 10A*2^32 + 10B..

Let the upper 32 bits be A and the lower 32 bits be B, so that the 64-bit number x = A*2^32+B. There are a number of natural ways to calculate 10x = 10(A*2^32 + B) = 10A*2^32 + 10B..

Method 1: Shift the AB combination left 3 times to get 8x and shift it once left to get 2x, and then add the two 64-bit numbers 8x and 2x using part (a). When shifting the AB combo left, be careful to add 1 to A when a 1 is shifted left from B.

Method 2: (probably the simplest) Each 64-bit product 10A and 10B can be computed using multu (not mult). Let the high and low 32-bit results for 10A be AH and AL respectively. And similarly, BH and BL for 10B. The 64-bit sum 10A*2^32 + 10B is equal to the concatenation of two 32-bit numbers: SH and SL, where SH = AL+ BH, and SL = BL. Note that AH will always be zero, because I guarantee that 10x will fit into 64-bits. When adding the 32-bit registers use "addu" in order to avoid an overflow error that "add" might generate.

Method 3 (The Lawson method -- not very efficient): Add

c. Finally, write a program that accepts two large decimal integers as strings, stores each one in two 32-bit registers, adds them, and then prints out the 64-bit result in two separate 32-bit pieces.

For
example: 0x 0000 1A2B 3C4D 5E6F + 0x 0000 1A2B 3C4D 5E6F = 28,772,997,619,311 + 28,772,997,619,311 = 0x 0000
3456 789A BCDE = 57,545,995,238,622. You can look in the
registers to see if this looks right. Note that when you
print the two registers in decimal you will get 13,398 and
2,023,406,814. The actual number 57,545,995,238,622 is 13,398 × 2^{32} + 2,023,406,814. If you wanted to display the
64-bit number in one long decimal value 57,545,995,238,622,
you would need to implement subtraction and division. A
detailed extra credit assignment to do this is outlined
below.

Here is another example on which to test your program: 0x 000 1C31 BFFC F000 + 0x 0000 1C31 BFFC F000 = 31,000,000,000,000 + 31,000,000,000,000 = 0x 0000 3863 7FF9 E000 =
62,000,000,000,000.
The two registers in
decimal are: 14435 and 2147082240.

The first example has no carry between the 32-bit registers, but the second one does.

The first example has no carry between the 32-bit registers, but the second one does.

Hints for the program:

1. It is really useful to use
memory locations (RAM) to store items that you expect to use
later. Registers are fine for computing values, but if you
use them for longer term storage, you will soon run out of
registers. To store a value from register $8 to a place
called "value". You should initialize a location called
value in the data section like this:

.data

value: .word 0

Then to store the value in register $8 you use sw $3, value. Then register $8 is free for other computations. To restore the value you saved, use lw $8, value.

2. You may feel a need to use functions or procedures in this program, and that is natural, but unless you look ahead you won't know how to do that. So, don't bother! To "simulate" procedures (functions, or methods) I suggest simply designing a code segment with certain registers marked for input and certain ones for output. Then simply copy and paste the code everywhere you need it. When using the code, make sure you provide the appropriate values in the correct registers. This ad-hoc style will prepare you for how procedures really work in MIPS, and help you appreciate it better.

3. To decide when you are finished processing a string of digits, look for a null or else just look for the first non-digit. The "read_string" syscall may include a linefeed and/or carriage return ASCII value at the end of the string before the null, so looking for a non-digit is the safest way.

Extra
Credit: .data

value: .word 0

Then to store the value in register $8 you use sw $3, value. Then register $8 is free for other computations. To restore the value you saved, use lw $8, value.

2. You may feel a need to use functions or procedures in this program, and that is natural, but unless you look ahead you won't know how to do that. So, don't bother! To "simulate" procedures (functions, or methods) I suggest simply designing a code segment with certain registers marked for input and certain ones for output. Then simply copy and paste the code everywhere you need it. When using the code, make sure you provide the appropriate values in the correct registers. This ad-hoc style will prepare you for how procedures really work in MIPS, and help you appreciate it better.

3. To decide when you are finished processing a string of digits, look for a null or else just look for the first non-digit. The "read_string" syscall may include a linefeed and/or carriage return ASCII value at the end of the string before the null, so looking for a non-digit is the safest way.

Write MIPS code that takes two words (64 bits) and
displays a string of digits that represents the 64-bit integer
value in base 10. The algorithm is similar to
reading but in reverse. You should generate the string from
right to left, each time dividing the 2-word number by 10,
calculating the remainder and quotient. The remainder is
converted to the next character and stored in a string for
printing later. The quotient is rewritten into the two words
and used in the next iteration. The hard step is dividing a
64-bit (2-word) number by 10 to get the quotient and
remainder.

There are two ways to divide a 64-bit number by 10.

Method 1 (preferred): Let A (64 bits) be composed of B and C, where B contains the high end 32 bits and C the low end 32 bits. That is, A = B(2^32) + C. Use divu and remu instructions on B and C to determine the overall quotient and remainder for the 64-bit number A divided by 10.

Method 2: Use the long division method you learned in grade school. Your text has the binary version of the algorithm. If you use this method, you will need to use the 64-bit subtracter described below.

Using all these segments of code, write a program to read in two strings representing two large decimal numbers, convert them to binary, add them, and display their sum.

There are two ways to divide a 64-bit number by 10.

Method 1 (preferred): Let A (64 bits) be composed of B and C, where B contains the high end 32 bits and C the low end 32 bits. That is, A = B(2^32) + C. Use divu and remu instructions on B and C to determine the overall quotient and remainder for the 64-bit number A divided by 10.

You need to compute the quotient
(2^32)/10 and the remainder (2^32) %10. You can ask me for
hints.

Method 2: Use the long division method you learned in grade school. Your text has the binary version of the algorithm. If you use this method, you will need to use the 64-bit subtracter described below.

Subtracting
64-bit numbers is very similar to
adding 64-bit numbers, except we use add (not addu)
instructions because the numbers can be negative numbers and
we consider them in two's complement. Note, you don't need to explicitly do the two's
complement yourself since it is done implicitly through the
subtraction command. The
lower 32 bits are subtracted first, and the carry calculated
and stored. Then the upper 32 bits are
subtracted. Finally, if there is no carry from the
result of the two lower 32 bits, then subtract one from the
subtraction of the upper 32 bits.

The reason for
processing carry's this way is because the upper 32 bits being
subtracted will have an extra
1 added to the right end that should NOT be there. If
there was a carry from the lower 32 bit subtraction then we
are all even and nothing needs to be done, but if there was no
carry from the lower 32 bit subtraction, then we have an extra
one in the upper 32 bit subtraction and we must subtract 1 to
even it out. Figuring out whether or not there is a
carry requires looking at the leftmost bit of each
number. To find the leftmost bit of the number you are
subtracting, you must explicitly find its two's complemented
number, since you are effectively adding the two's complement
number. To find the two's complement of a number, you
can subtract 1 and toggle the leftmost bit. This is
equivalent to, but easier, than toggling the bits and adding
one.

Using all these segments of code, write a program to read in two strings representing two large decimal numbers, convert them to binary, add them, and display their sum.

http://www.stonehill.edu/compsci/shai.htm