Simonson - CSC304 - Computer Architecture
Assembly Language Using MIPS
Arithmetic Bit Level Instructions and Applications
Due Tuesday, February 20. (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 arbitrary
SLL instruction using ROL (rotate left) pesudo-instruction and
other MIPS commands.
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. When adding the
32-bit registers use "addu" in order to avoid an overflow
error that "add" might generate. Oveflow for addu (i.e. carry)
does not throw an exception, so you can run the program and
check for unsigned overflow without an exception being
thrown. There are no negative
numbers in this assignment, and the bits should not be
treated as two's complement.The instruction "add" throws an
exception when the sum of two positive values result in a
"negative" result, or the sum of two negative values results
in a positive result. For unsigned numbers, such
behavior would not necessarily be overflow.
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 three
natural ways to calculate 10x
+ B) = 10A*2^32 + 10B..The simplest way,
in my opinion, is Method 1 because because it requires no masks or bit ops.
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
1: 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
Method 2: 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 3: (The Lawson-Costello 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. Important: To decide when you are finished
processing a string of digits, normally you would look for a
null (0), however, the "read_string" syscall includes a linefeed
and/or carriage return ASCII value (10) at the end of the string
before the null, so looking for a non-digit (rather than null) is
the safest way to exit the loop.
Extra credit is awarded to any individual(s) who
work on the problem. It is not necessarily group work.
Write MIPS code that takes two words (64 bits) and displays a
string of digits that represents the 64-bit integer value in
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.
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.