Archasg2

Hints for 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 loacation called value in the data section like this:
.data
value: .word 0
Then to store the value in rgeister $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 an ascii value of 10 (carriage return), or else just look for the first non-digit.

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.

(c) One way to check for overflow in 2’s complement addition is to check if the two numbers are positive but give a negative answer (i.e. the most significant bit in the result is 1), or the two numbers are negative but give a positive answer. Design overflow circuitry to detect overflow using this scheme. (It will appear later as the overflow “black box” of a ripple adder.)

a. Show how to accomplish an SLL instruction using ROL (rotate left) pesudo-instruction and other logical MIPS commands (and, or, nor).
b. Same question for an SRA instruction.

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. 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. This is tricky because besides the need to convert ascii codes of 0-9 to values 0-9, you also need to do multiplication and addition on a number stored in two words. The multiplication by 10 can be done with shifts and addition (add 8x + 2x). Hence, the only hard part is the addition of two 64-bit numbers.

Write MIPS code to add two 64-bit numbers. Adding two 64-bit numbers cannot be done with one ADD instruction because ADD instructions work only on 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 then one must be added to the upper 32 bit addtion. The result of the upper 32-bit addition (possibly with this carry) is stored in the upper 32-bits of the result. All these adds are done with ADDU instructions, because there are no negative numbers.

Test your code by writing 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: 28,772,997,619,311 + 28,772,997,619,311 = 0x 0000 3456 789A BCDE. 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 is 13,398 × 2³² + 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 assigment to do this is outlined below.

Write MIPS code to subtract two 64-bit numbers. This is very similar to the last problem, but now we are using negative numbers and two's complement arithmetic. The lower 32 bits are subtracted first, and the carry calculated and stored. Then the upper 32 bits can be subtracted. You don't need to explicitly do the two's complement yourself since it is done implicitly through the subtraction command. Finally, if there is no carry from the result of the two upper 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 two's complemented number, you can subtract 1 from the (32-bit) number and then toggle the leftmost bit. (This is equivalent to but easier than toggling the bits and then adding one).

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 re-written 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. This is somewhat like the long division you learned in grade school. You will need to use the 64-bit subtracter from part c. Details may be discussed in class.

Using 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. Don't do the program directly from the strings. Make sure to use the segments you wrote above.