Lab 3 Solution

1. Testing Power of Two [20 points]
Write a MIPS program that tests if a number is a power of two. Set register $t0 to some value in SPIM and use this for testing power of two. The program will generate output in console.
35 is not a power of two.
256 is a power of two.
Test the program with different values. Save your code as "Lab3_1.s" and run it in PCSpim.
Check-off Requirement: Show your solution to TA and demonstrate program execution with different values in SPIM.

2. Counting Bits [20 points]
Initialize one register to a bit value that represents a positive 32-bit integer from keyboard input. Now the program determines how many 1 bits are in the pattern. So the bit pattern: 0000 0000 1001 1000 1110 1010 0101 0011 (i.e. 0x98EA53 in hexadecimal or 10021459 in decimal format) has 12 bits for 1 and 20 bits for 0.
The program will ask a user to type one decimal value from keyboard:
Enter one value:
After counting the number of 1 bits for the given value, the program will generate output in console.
10021459 has 12 bits for 1.
Test the program with different values. Save your code as "Lab3_2.s" and run it in PCSpim.
Check-off Requirement: Show your solution to TA and demonstrate program execution with different values in SPIM.

3. Sorting Array [40 points]
Write a MIPS program that sorts elements of an array in non-decreasing order. The array (B) has 32-bit integer elements, where the array size is specified by SZ. Declare B and SZ variables in data segment.
.data
B:      .word 722               # B[0]
        .word 21                # B[1]
        .word 4                 # B[2]
        .word 89                # B[3]
        .word 16384             # B[4]
        .word 350               # B[5]
        .word 6046              # B[6]
        .word 897               # B[7]
        .word 1201              # B[8]
        .word 0                 # B[9]
        .word 904               # B[10]
        .word 897               # B[11]
        .word 4805              # B[12]
        .word 679               # B[13]
        .word 7                 # B[14]
SZ:     .word 15
Use any in-place sorting algorithm you know. The following C code shows a bubble sorting algorithm.
   int i, j, tmp;

   for (i=0; i<SZ; ++i) {
       for (j=i+1; j<SZ; ++j) {
           if (B[i] > B[j]) {
               tmp = B[i];
               B[i] = B[j];
               B[j] = tmp;
           }
       }
       
       /* Optional: Use this to display */
       printf("B[%d] = %d\n", i, B[i]);
   }
Check the result in the SPIM environment after program execution. The program does not need to print out the sorted numbers in console, but it must store the values in sorted order back to B.
Save your code as "Lab3_3.s" and run it in PCSpim.
Check-off Requirement: Show your solution to TA and demonstrate program execution in SPIM.

Control Flow Instructions in MIPS
Type
Instruction
Description
Unconditional Jump
j Label
This instruction jumps unconditionally to the instruction followed by the label Label. It is equivalent to the goto statement in C.
Conditional Branch on Equality
beq rs, rt, Label
This instruction branches to label Label, if registers rs and rt have the same values. In Register Transfer Notation (RTN), it means:
        if ( R[rs] == R[rt] )
            goto Label;
        
If the registers have different values, the processor proceeds to the next instruction.
Conditional Branch on Inequality
bne rs, rt, Label
This instruction branches to label Label, if registers rs and rt have the same values.
Set Register Based on Relation
slt rd, rs, rt
This instruction sets register rd to 1 if R[rs] < R[rt]. Otherwise it sets rd to 0. In RTN, it means:
        if ( R[rs] < R[rt] )
            R[rd] = 1;
        else
            R[rd] = 0;
        
There is an immediate version of the slt instruction in which the 3rd argument is a 16-bit signed integer. "slti rd, rs, 0x0002" sets rd to 1 if R[rs] < 0x0002.

Submission Requirement
Turn in three source files (Lab3_1.s, Lab3_2.s, and Lab3_3.s).