From c56d05c58ba844fc0c7b63e299c220618029a0e0 Mon Sep 17 00:00:00 2001 From: Adam Carpenter <53hornet@gmail.com> Date: Sat, 3 Dec 2016 10:44:17 -0500 Subject: Uploading Programming Assignments -- Typeset assignments will come at a later date. --- HW3/CS424_HW3_Carpenter_Adam.asm | 266 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 266 insertions(+) create mode 100644 HW3/CS424_HW3_Carpenter_Adam.asm (limited to 'HW3') 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 -- cgit v1.2.3