Simonson - CS304 - Computer Architecture
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
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.
+ 001011 +
011011 + 01111111
2. Simulating Instructions
a. Show how to accomplish an SLL
instruction using ROL (rotate left) pesudo-instruction and other
b. Same question for an SRA instruction.
Program: (20 points) Reading
and Adding 64-bit Numbers
are two main parts to this program, but when you get them done,
they can be incorporated into one program (part c).
MIPS code to add two 64-bit numbers.
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
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
× 232 + 2,147,082,240, so the resulting two registers in decimal are: 14,435
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.
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
+ B) = 10A*2^32 + 10B..
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
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
Method 3 (The Lawson method -- not very efficient): Add x
to itself ten times using part (a) of this assignment.
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 × 232 + 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
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 =
The two registers in
decimal are: 14435 and 2147082240.
The first example has no
carry between the 32-bit registers, but the second one
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:
64-bit numbers (15 points)
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
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
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.
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
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.