Assignment 2
Assembly Language Using MIPS
Arithmetic Bit Level Instructions and Applications
Due Wednesday, February 21. (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.19.2 MIPS throws an error on andi $t2, $t2, -1, so if you want to run this -- you will need to change -1 to hex value 0xFFFFFFFF), 2.46 (all parts), 3.1, 3.2
1. Overflow
Solve 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
2. Simulating Instructions
a. Show how to accomplish an arbitrary SLL instruction using other MIPS commands. (Hint: The pseudo instruction ROL (rotate left) helps).
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.
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. When adding the 32-bit registers use "addu" in order to avoid an overflow error that "add" might generate. Overflow 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. (Spaces are for readability). 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 and 2,147,082,240. Another example you can test is to add 0x 0000 1111 FFFF FFFF to 0x 0000 0000 0000 0001. The result should be: 0x 0000 1112 0000 0000.
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. Note that if you read the string in with a syscall, that it will include the \n (ascii value 10, or hex 'a') at the end of the string before the zero (null) string terminator. You should make sure your loop does not process the "a". It should stop when it hits the \n (ascii 0x0000000a).
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 = 10(A*2^32 + B) = 10A*2^32 + 10B. Method 1 requires no masks or bit ops but the idea is somewhat complex. Method 2 makes extensive use of masks, shifts, ands, ors, but the idea is simpler. Method 3 is the simplest but not very efficient.
Method 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 64-bits.
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. The 64-bit shifts can be done in a way very similar to the 64-bit shifts we did in the multiplication algorithm in class.
Method 3: (The Lawson-Costello method -- not very efficient but very easy to understand): Add x to itself ten times using part (a) of this assignment.
You can test this part of the assignment with 34359738398. This should display 8 in the high register and 30 in the low register.
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. All part (c) does is a little I/O and then it invokes part (b) twice and part (a) once.
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 × 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 below.
Here is another example on which to test your program: 0x 0000 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. If you try to print these values with syscall, the lower register will print as a negative number, because the print_int syscall (code 1) treats integers as two's complement.
The first example has above 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. 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: Displaying 64-bit numbers (15 points)
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 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.
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.