cs345
Homework 6 Solutions

1. a)  00101000
      +00110111
      ---------
       01011111

   b)  11100101
      -10011010 --> 01100101 --> 01100110
      ---------

-->    11100101
      +01100110
      ---------
       01001011

   c)  11111111
      +00000000
      ---------
       11111111

   d)  01100110
      -11111100 --> 00000011 --> 00000100
      ---------

-->    01100110
      +00000100
      ---------
       01101010

2.
#thirdCharacterRecursive.asm
#Homework 7
#cs345
#
#A program that uses a recursive function to print
#every third character of a string.
.data
str1: .asciiz "abcdefghijklmnopqrstuvwxyz\n"

newLine: .asciiz "\n"


.text
main:
la $a0, str1
li $v0, 0

jal thirdCharacterRecursive

#end program
li $v0, 10
syscall

thirdCharacterRecursive:
#allocate some stack space
sub $sp, $sp, 24

#store the return address
sw $ra, 20($sp)

#store $a0
sw $a0, 0($sp)

#if the current element of the string is zero we are finished
lb $t1, 0($a0)
beq $t1, $zero, finished

#if $a0 % 3 == 0 print the character
add $v0, $v0, 1
rem $t2, $v0, 3
move $t3, $a0
move $t4, $v0
bnez $t2, endif
  li $v0, 11
  move $a0, $t1
  syscall
endif:
move $a0, $t3
move $v0, $t4

#if we aren't finished go to the next index of the string
addi $a0, $a0, 1

jal thirdCharacterRecursive

#add one to $v0
addi $v0, $v0, 1

finished:
#load the return address
lw $ra, 20($sp)
lw $a0, 0($sp)
#deallocate stack space
addi $sp, $sp, 24
jr $ra


3. #Program: Compute Summation of Products
#This sample program uses a procedure call (function/method call)
#to compute the summation of products of a set of integers.
.data

NumIntegersToInput: .asciiz "Please enter the number of integers to read from the console: "
ReturnChar: .asciiz "\n"
IntArray: .word 0:100

.text

main:

  #Prompt for the number of integers to read from the console.
  li $v0, 4
  la $a0, NumIntegersToInput
  syscall

  #Read in the number of integers
  li $v0, 5
  syscall
  move $t1, $v0  #number of integers is stored in $t1

  #Enter each integer one by one.
  li  $t0, 0  #$t0 is the counter
  la  $t3, IntArray  #$t3 is the array location

  for: 
    li $v0, 5  # read in an integer
    syscall

    move $t2, $v0  #move the input value to another register
    sw $t2,0($t3)  #store the input value in memory

    #Store the integers in an array
    addi $t0, $t0, 1
    addi $t3, $t3, 4  #keep adding 4 to the array index counter

    #Compare 
    slt $t4, $t0, $t1
  bne $t4, $zero, for


  #Print each integer one by one.
  li  $t0, 0  #$t0 is the counter
  la  $t3, IntArray

  for2: 
    lw $a0, 0($t3) #load a value from the array into the argument register
    li $v0, 1  # print an integer
    syscall

    la $a0, ReturnChar  #print a return character
    li $v0, 4
    syscall

    addi $t0, $t0, 1  #advance the array counter
    addi $t3, $t3, 4  #keep adding 4 to the array index counter
    slt $t4, $t0, $t1
  bne $t4, $zero, for2

  #pass the address of the integer array and the number of elements
  #in the array into the sumProdProcedure
  la $a0, IntArray
  move $a1, $t1
  jal sumProdProcedure

  move $a0, $v0  #print the sum
  li $v0, 1
  syscall

  la $a0, ReturnChar  # print a return character
  li $v0, 4
  syscall

  li $v0, 10  #end program
  syscall

#Pass the array and number of integers into the Summation procedure
sumProdProcedure:
  #Compute the sum
  li $t0, 0  #loop counter
  li $t1, 0  #summation variable
  move $t2, $a0  #address counter

  sum_for:
    lw $t3, 0($t2)
    mul $t3, $t3, $t3
    add $t1, $t1, $t3  #add to the sum
    addi $t2, $t2, 4     #advance the address
    addi $t0, $t0, 1     #advance the loop counter
  bne $t0, $a1, sum_for

  #Return the sum
  move $v0, $t1
  jr $ra  #return


4. #PrintRecursive.asm
#Homework 7
#cs345
#
#A program that uses a recursive function to print
#numbers in descending order.
.data
newLine: .asciiz "\n"

.text
main:
li $a0, 10

jal printRecursive

#end program
li $v0, 10
syscall

printRecursive:
#allocate some stack space
sub $sp, $sp, 24

#store the return address
sw $ra, 20($sp)

#store $a0
sw $a0, 0($sp)

#if we aren't finished, print the current value, and decrement it by one
#$a0 is already the correct value, so we don't need to load it again
li $v0, 1
syscall

la $a0, newLine  #print a newLine character
li $v0, 4
syscall

lw $a0, 0($sp) #reload 

#if the current element of the string is less than or equal to 
#zero, we are finished.
ble $a0, 0, finished

div $a0, $a0, 2
jal printRecursive


finished:
#load the return address
lw $ra, 20($sp)
lw $a0, 0($sp)
#deallocate stack space
addi $sp, $sp, 24
jr $ra

A stack trace for printRecursive(5) is provided below:

+------------+
| $a0 = 5    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 20
+------------+

call printRecursive(2)
+------------+
| $a0 = 2    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(5)| <-- $sp + 20
+------------+
| $a0 = 5    | <-- $sp + 24
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 44
+------------+

call printRecursive(1)
+------------+
| $a0 = 1    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(2)| <-- $sp + 20
+------------+
| $a0 = 2    | <-- $sp + 24
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(5)| <-- $sp + 44
+------------+
| $a0 = 5    | <-- $sp + 48
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 68
+------------+

call printRecursive(0)
+------------+
| $a0 = 0    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(1)| <-- $sp + 20
+------------+
| $a0 = 1    | <-- $sp + 24
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(2)| <-- $sp + 44
+------------+
| $a0 = 2    | <-- $sp + 48
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(5)| <-- $sp + 68
+------------+
| $a0 = 5    | <-- $sp + 72
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 92
+------------+


return from printRecursive(0)
+------------+
| $a0 = 1    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(2)| <-- $sp + 20
+------------+
| $a0 = 2    | <-- $sp + 24
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(5)| <-- $sp + 44
+------------+
| $a0 = 5    | <-- $sp + 48
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 68
+------------+

return from printRecursive(1)
+------------+
| $a0 = 2    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
|$ra=prRec(5)| <-- $sp + 20
+------------+
| $a0 = 5    | <-- $sp + 24
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 44
+------------+

return from printRecursive(2)
+------------+
| $a0 = 5    | <-- $sp
+------------+
|   . . .    | . . .
+------------+
| $ra=main   | <-- $sp + 20
+------------+

return from printRecursive(5)
+------------+ <-- $sp