CSE 410 Assignment 1

Spring 2007

Due: In class, Monday 4/9/2007

1. Add comments to the following MIPS code and describe in one sentence what it computes. Assume that $a0 is used for the input and initially contains n, a positive integer. Assume that $v0 is used for the output.

 
 begin:  addi $t0, $zero, 0 
         addi $t1, $zero, 1 
 loop:   slt  $t2, $a0, $t1 
         bne  $t2, $zero, finish 
         add  $t0, $t0, $t1 
         addi $t1, $t1, 2 
         j loop 
finish:  add  $v0, $t0, $zero

2. Here is a snippet of MIPS assembly:

   start:   beq   $s1, $s2, exit
            add   $t0, $s2, $s2
            add   $t0, $t0, $t0
            add   $t0, $t0, $s0
            lw    $t1, 0($t0)
            add   $t1, $t1, $t1
            sw    $t1, 0($t0)
            addi  $s2, $s2, 1
            j     start
   exit:
   

   Here are the contents of a portion of memory before this snippet runs:

   Address	Initial contents	First time at "j start"	Second time at "j start"	...
   400	11
   404	23
   408	63
   412	128
   416	911

   Here are the initial values of the registers before this snippet runs: (Note $t0 and $t1 are not in the list because they are used only as temporary registers, and their initial values do not matter.)

   Register	Initial contents	First time at "j start"	Second time at "j start"	...
   $s0	400
   $s1	5
   $s2	0
   $t0	N/A
   $t1	N/A

Trace through the MIPS code above. Each time you reach the "j start" line, write down the contents of addresses 400-416 and registers $s0, $s1, $s2, $t0 and $t1 by filling in the tables above (you might need to add more columns to the tables). In one sentence describe what this program does? (Note: the "addi" instruction is just like "add" except it allows you to add in a small constant directly rather than specifying a second register. For example, if $s0 contains 3, then after 'add $s2, $s0, 5' executes $s2 will contain 8.)

Extra Credit: Both a conditional branch ("beq $s1, $s2, exit") and an unconditional jump ("j start") are executed each time through the loop. Only poor compilers would produce code with this loop overhead. Rewrite the assembly code so that it uses at most one branch or jump each time through the code. How many instructions are executed before and after the optimization? (Note: You may find it necessary to put one or more instructions before the "start" label.)


In problems 4-6, resist the temptation to use a calculator that does the conversion between binary, decimal, and hexadecmial automatically.


3. For the next 2 items, convert the given decimal number to a 32-bit, binary number AND also write the resulting binary number in hexadecimal notation. (Hint: remember that converting between binary and hexadecimal is very simple).
   1. 393
   2. 4,217

4. For the next 2 items, convert the given binary numbers to both hexadecimal and decimal. (Hint: it may be less tedious to convert from hexadecimal to decimal than from binary to decimal.)
   1. 0000 0000 0100 0000 1111 1101 1100 1101
   2. 0011 1111 1001 1111 0000 1000 0011 0101

5. For the next 2 items, convert the given hexadecimal number to both binary and decimal (treat both numbers as unsigned [positive] 32-bit numbers).
   1. 0x01001001
   2. 0xDEADBEEF

6. The following program tries to copy words from the address in register $a0 to the address in register $a1, counting the number of words copied in register $v0. The program stops copying when it finds a word equal to zero. You do not have to preserve the contents of $v0, $a0, and $a1. This terminating word should be copied but not counted.

    
   loop:  lw   $v1, 0($a0)        #read next word from source
          addi $v0, $v0, 1        #increment count words copied
          sw   $v1, 0($a1)        #write to destination
          addi $a0,$a0,1          #advance ptr to next source
          addi $a1, $a1, 1        #advance ptr to next dest
          bne  $v1, $zero,loop    #loop if word copied not zero
   

   There are multiple bugs in this program; fix the bugs and turn in a bug-free version.
7. Show the MIPS instruction or instructions for the C statement:

    
     x[10] = x[11]+c;
   

   Assume that c corresponds to register $t0 and the array x has a base address of 4,000,000 (base 10). Also assume that the statement involves ordinary 4-byte integer variables and arrays.

8. Show how the following MIPS instructions are encoded in memory:

    
       add   $t1, $t2, $t3
       addi  $s0, $t1, 3
   
       sw    $t3, 32($t2)