summaryrefslogtreecommitdiff
path: root/HW3
diff options
context:
space:
mode:
authorAdam Carpenter <53hornet@gmail.com>2016-12-03 10:44:17 -0500
committerAdam Carpenter <53hornet@gmail.com>2016-12-03 10:44:17 -0500
commitc56d05c58ba844fc0c7b63e299c220618029a0e0 (patch)
tree7e8c66253c08f9ebca3da6ca9c1c519a1e10f0a0 /HW3
downloadcsci424-master.tar.xz
csci424-master.zip
Uploading Programming Assignments -- Typeset assignments will come at a later date.HEADmaster
Diffstat (limited to 'HW3')
-rw-r--r--HW3/CS424_HW3_Carpenter_Adam.asm266
1 files changed, 266 insertions, 0 deletions
diff --git a/HW3/CS424_HW3_Carpenter_Adam.asm b/HW3/CS424_HW3_Carpenter_Adam.asm
new file mode 100644
index 0000000..7e0c15b
--- /dev/null
+++ b/HW3/CS424_HW3_Carpenter_Adam.asm
@@ -0,0 +1,266 @@
+# CSCI 424, Homework 3
+# Adam Carpenter - username acarpent - acarpenter@email.wm.edu
+ .text
+ .globl main
+main:
+ la $s0, array1 # create array
+ la $t0, ($s0) # create pointer
+ add $s1, $zero, $zero # represents n-1 of array
+ la $a0, startMsg
+ jal Print_string # print message
+InputLoop: # Take in only positive integers and store them in array until user enters -1
+ la $a0, prompt
+ jal Print_string # Print prompt
+ jal Read_integer # read integer
+ beq $v0, -1, isArrayEmpty # Exit if user enters -1
+ sw $v0, ($t0) # Store integer
+ add $t0, $t0, 4 # increment pointer
+ add $s1, $s1, 1 # increment counter
+ j InputLoop
+isArrayEmpty: # If the user only enters -1, there is nothing to sort
+ bne $t0, $s0, arrayNotEmpty
+ la $a0, emptyMsg
+ jal Print_string
+ jal Exit
+arrayNotEmpty: # The array isn't empty, continue execution
+ add $t0, $s0, $zero
+ add $t1, $zero, $zero
+ la $a0, unsortedMsg
+ jal Print_string
+printLoopUnsorted:
+ lw $a0, ($t0)
+ jal Print_integer
+ la $a0, separator
+ jal Print_string
+ add $t0, $t0, 4
+ add $t1, $t1, 1
+ bne $s1, $t1, printLoopUnsorted
+
+ # Call MergeSort for first time
+ sub $s1, $s1, 1 # set s1 to length-1
+ add $a0, $zero, $zero # low stored in $a0
+ add $a1, $zero, $zero # mid stored in $a1
+ add $a2, $zero, $s1 # high stored in $a2
+ jal MergeSort
+
+ # Finish execution in main by printing sorted array
+ add $t0, $s0, $zero
+ add $t1, $zero, $zero
+ la $a0, sortedMsg
+ jal Print_string
+ addi $s1, $s1, 1 # set s1 to length
+printLoopSorted:
+ lw $a0, ($t0)
+ jal Print_integer
+ la $a0, separator
+ jal Print_string
+ add $t0, $t0, 4
+ add $t1, $t1, 1
+ bne $s1, $t1, printLoopSorted
+ jal Exit # End the program
+# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+# How it works: This mergesort algorithm does not follow the algorithm listed in the
+# homework prompt. I believe it is simpler. Mergesort() takes in low and high arguments
+# (the array is globally saved and accessed) and then makes recursive calls to
+# mergesort(low, mid) and then mergesort(mid+1, high) and then calls merge(low, mid, high).
+# Merge() creates L1 and L2 to look at the elements of the array. It creates a second
+# array (b) of the required size and places elements from a into b based on the
+# divide and conquer conditions passed. Once the merge is done, control is returned
+# to Mergesort which continues the algorithm. For more information, visit
+# https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_program_in_c.htm
+
+# --- MergeSort Procedure ---
+MergeSort:
+ addi $sp, $sp, -16 # adjust stack, push return address
+ sw $ra, 12($sp)
+
+ bge $a0, $a2, MergeSortEnd # if low >= high, end procedure
+ add $a1, $zero, $zero # reset mid
+ add $t0, $a0, $a2 # temp = low + high
+ div $a1, $t0, 2 # mid = temp / 2
+
+ # push arguments onto stack
+ sw $a0, 0($sp)
+ sw $a1, 4($sp)
+ sw $a2, 8($sp)
+
+ add $a2, $a1, $zero # Call MergeSort(low, mid)
+ jal MergeSort
+
+ # load arguments back
+ lw $a0, 0($sp)
+ lw $a1, 4($sp)
+ lw $a2, 8($sp)
+ # lw $ra, 12($sp)
+
+ addi $a0, $a1, 1 # Call MergeSort(mid+1, high)
+ jal MergeSort
+
+ # load arguments back
+ lw $a0, 0($sp)
+ lw $a1, 4($sp)
+ lw $a2, 8($sp)
+ lw $ra, 12($sp)
+
+ jal Merge # Call Merge
+MergeSortEnd:
+ lw $ra, 12($sp) # Load return address
+ addi $sp, $sp, 16 # Readjust stack pointer
+ jr $ra # Return
+# ---------------------------
+
+# --- Merge Procedure ---
+Merge:
+ add $s2, $zero, $zero # initialize
+ add $t3, $zero, $zero
+ add $t9, $zero, $zero
+ add $t0, $a0, $zero # i = low
+ add $t1, $a0, $zero # L1 = low
+ addi $t2, $a1, 1 # L2 = mid + 1
+
+ add $s2, $a0, $zero # Protect a0 from being overwritten permanently
+ add $a0, $a2, $zero # create array b for merging
+ li $v0, 9
+ syscall
+
+ add $t3, $v0, $zero # tmp3 points to arrayb
+ add $a0, $s2, $zero
+ add $s2, $t3, $zero # s2 points to arrayb as backup
+
+While1:
+ mul $t9, $t1, 4 # tmp9 is the array index converter (turn i into address increment)
+ add $t5, $t9, $s0 # tmp5 = &a[L1]
+ lw $t5, ($t5) # tmp5 = *a[L1]
+ mul $t9, $t2, 4
+ add $t6, $t9, $s0 # tmp6 = &a[L2]
+ lw $t6, ($t6) # tmp6 = *a[L2]
+ add $t3, $s2, $zero # tmp3 = &b[0]
+ mul $t9, $t0, 4
+ add $t3, $t3, $t9 # tmp3 = &b[i]
+
+ bgt $t5, $t6, Else1 # if *a[L1] <= *a[L2] then
+ sw $t5, ($t3) # *b[i] = *a[L1]
+ addi $t1, $t1, 1 # L1 = L1 + 1
+ j Final1
+Else1: # else
+ sw $t6, ($t3) # *b[i] = *a[L2]
+ addi $t2, $t2, 1 # L2 = L2 + 1
+Final1:
+ addi $t0, $t0, 1 # i = i + 1
+ bgt $t1, $a1, End1 # loop only if L1 <= mid
+ bgt $t2, $a2, End1 # loop only if L2 <= high
+ # addi $t0, $t0, 1 # i = i + 1
+ j While1
+End1:
+ bgt $t1, $a1, End2 # loop only if L1 <= mid
+
+While2:
+ mul $t9, $t1, 4
+ add $t5, $t9, $s0 # tmp5 = &a[L1]
+ lw $t5, ($t5) # tmp5 = *a[L1]
+ add $t3, $s2, $zero # tmp3 = &b[0]
+ mul $t9, $t0, 4
+ add $t3, $t3, $t9 # tmp3 = &b[i]
+ sw $t5, ($t3) # *b[i] = *a[L1]
+ addi $t1, $t1, 1 # L1 = L1 + 1
+ addi $t0, $t0, 1 # i = i + 1
+ bgt $t1, $a1, End2 # loop only if L1 <= mid
+ j While2
+End2:
+ bgt $t2, $a2, End3 # loop only if L2 <= high
+
+While3:
+ mul $t9, $t2, 4
+ add $t6, $t9, $s0 # tmp6 = &a[L2]
+ lw $t6, ($t6) # tmp6 = *a[L2]
+ add $t3, $s2, $zero # tmp3 = &b[0]
+ mul $t9, $t0, 4
+ add $t3, $t3, $t9 # tmp3 = &b[i]
+ sw $t6, ($t3) # *b[i] = *a[L2]
+ addi $t2, $t2, 1 # L2 = L2 + 1
+ addi $t0, $t0, 1 # i = i + 1
+ bgt $t2, $a2, End3 # loop only if L2 <= high
+ j While3
+
+End3:
+ add $t0, $a0, $zero # i = low
+ add $t7, $s0, $zero # tmp7 = &a[0]
+
+While4:
+ add $t3, $s2, $zero # tmp3 = &b[0]
+ mul $t9, $t0, 4
+ add $t3, $t3, $t9 # tmp3 = &b[i]
+ lw $t3, ($t3) # tmp3 = *b[i]
+ add $t7, $s0, $zero # tmp7 = &a[0]
+ add $t7, $t7, $t9 # tmp7 = &a[i]
+ sw $t3, ($t7) # *a[i] = *b[i]
+ addi $t0, $t0, 1 # i = i + 1
+ bgt $t0, $a2, MergeEnd # loop only if i <= high
+ j While4
+
+MergeEnd:
+ jr $ra # Return
+# ---------------------------
+
+# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ .data
+startMsg:
+ .asciiz "\nPlease enter positive integers. When you are finished enter -1.\n"
+prompt:
+ .asciiz "Enter integer: "
+emptyMsg:
+ .asciiz "Nothing to sort -- the array is empty!\n"
+unsortedMsg:
+ .asciiz "\nUnsorted array: "
+sortedMsg:
+ .asciiz "\nSorted array: "
+separator:
+ .asciiz " "
+
+ .align 4
+array1:
+ .space 60 # 60 bytes for max 15 integers
+
+ .align 4
+arrayL:
+ .space 32 # 32 bytes for max 8 integers
+
+ .align 4
+arrayR:
+ .space 32 # 32 bytes for max 8 integers
+
+# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+# Wrapper functions around some of the system calls
+# From P&H COD, Fig. A.9.1
+ .text
+
+ .globl Read_integer
+Read_integer: # input an integer to be stored in v0
+ addi $v0, $zero, 5
+ syscall
+ jr $ra
+
+ .globl Print_integer
+Print_integer: # print the integer in register a0
+ addi $v0, $zero, 1
+ syscall
+ jr $ra
+
+ .globl Print_string
+Print_string: # print the string whose starting address is in register a0
+ addi $v0, $zero, 4
+ syscall
+ jr $ra
+
+ .globl Exit
+Exit: # end the program, no explicit return status
+ addi $v0, $zero, 10
+ syscall
+ jr $ra
+
+ .globl Exit2
+Exit2: # end the program, with return status from register a0
+ addi $v0, $zero, 17
+ syscall
+ jr $ra