insertion-sort.asm

# BURAK ASLAN
# aslanb
# Feb 2, 2016
# Homework 3 CS 3650
# Insert Sort

.globl main
.data

#char * [] data
data:
	.align 2
	.space 64

#int size = 16
size:
	.align 4
	.word 16


#char * data[] = {"Joe", "Jenny", "Jill", "John", "Jeff", "Joyce",
#		"Jerry", "Janice", "Jake", "Jonna", "Jack", "Jocelyn",
#		"Jessie", "Jess", "Janet", "Jane"};
array:
	.align 4
	.asciiz "Joe"
	.align 4
	.asciiz "Jenny"
	.align 4
	.asciiz "Jill"
	.align 4
	.asciiz "John"
	.align 4
	.asciiz "Jeff"
	.align 4
	.asciiz "Joyce"
	.align 4
	.asciiz "Jerry"
	.align 4
	.asciiz "Janice"
	.align 4
	.asciiz "Jake"
	.align 4
	.asciiz "Jonna"
	.align 4
	.asciiz "Jack"
	.align 4
	.asciiz "Jocelyn"
	.align 4
	.asciiz "Jessie"
	.align 4
	.asciiz "Jess"
	.align 4
	.asciiz "Janet"
	.align 4
	.asciiz "Jane"
	.align 4

# "Initial array is:\n["
initialArrayString: 
	.asciiz "Initial array is:\n"
openBracket:
	.asciiz "["
closeBracket:
	.asciiz "]\n"
# Comma for between array elements
commaString:	
	.asciiz ", "
# "Insertion sort is finished!\n["
endSortString: 
	.asciiz "Insertion sort is finished!\n"
# title
authorString:
	.asciiz "Insertion Sort in Assembly - Burak Aslan - CS 3650\n"


# int main(void)
.text
main:
	# PROLOGUE

	# PRINT "Insertion Sort in Assembly - Burak Aslan - CS 3650\n"
	la $a0, authorString
	li $v0, 4
	# System call to print
	syscall

	# Clear temp values
	sw $ra, 0($sp)
	jal clearTemps
	lw $ra, 0($sp)

	# Assign the array address to $t0
	la $t0, array
	# Assign the "pointer" arrays to $t1 (char* data[])
	la $t1, data
	# assign zero to $t2, which is what we will use to iterate loop (i = 0)
	addi $t2, $zero, 0

	# Store the return address to stack pointer
	sw $ra, 0($sp)
	# Jump and link to intialize the array
	jal headInitializeArrayLoop
	# Restore the stack pointer
	lw $ra, 0($sp)   

# Function to clear temp registers
clearTemps:
	move $t0, $zero
	move $t1, $zero
	move $t2, $zero
	move $t3, $zero      
	move $t4, $zero
	move $t5, $zero
	move $t6, $zero
	move $t7, $zero
	jr $ra 

# $t0 = array
# $t1 = data
# #t2 = 0
.text
headInitializeArrayLoop:
	# Branch and end loop if we reach end of array (while(i != size){ ... }) 
	beq $t2, 16, endInitializeArrayLoop 
	# Store the word from the string array to the data array or (data[i] = &array[i])
	sw $t0, ($t1)
	# Since we are aligning with 4 bits, we have to add 16 to $t0 (array)
	addi $t0, $t0, 16
	# Since the address array is aligning 2 bits we have to ad 4 to $t1 (data)
	addi $t1, $t1, 4 
	# Iterate on the loop counter (++i)
	addi $t2, $t2, 1 #i++
	# Jump back to the top 
	j headInitializeArrayLoop	

# EPILOGUE - We call this after we initialize the array 
.text
endInitializeArrayLoop:

	# PRINT "Initial array is:\n[" (printf("Initial array is:\n["))
	la $a0, initialArrayString
	li $v0, 4
	# System call to print
	syscall

	# Clear temp values
	sw $ra, 0($sp)
	jal clearTemps
	lw $ra, 0($sp)

	# Call the print array function with the data array and the size we predetermined
	la $a0, data
	lw $a1, size
	jal headPrintArray

	# Clear temp values
	sw $ra, 0($sp)
	jal clearTemps
	lw $ra, 0($sp)
	
	# Load the data and size to the arugment values when we call insertion sort
	la $a0, data
	lw $a1, size
	sw $ra, 0($sp)
	jal headInsertionSort
	lw $ra, 0($sp)

	# Clear temp values
	sw $ra, 0($sp)
	jal clearTemps
	lw $ra, 0($sp)

	# PRINT "Insertion sort is finished!\n" (printf("Insertion sort is finished!\n"));
	la $t0, endSortString
	move $a0, $t0
	li $v0, 4
	syscall

	# Clear temp values
	sw $ra, 0($sp)
	jal clearTemps
	lw $ra, 0($sp)
	
	# Print the array again (now that it is sorted)
	la $a0, data
	lw $a1, size
	sw $ra, 0($sp)
	jal headPrintArray
	lw $ra, 0($sp)
	
	# Exit the program
	li $v0, 10
	li $a0, 0  
	syscall

# Start of the print array function
headPrintArray:
	# Store the return address into the stack pointer
	sw $ra, 0($sp)
	# $t0 = array
	move $t0, $a0
	# $t1 = 0
	move $t1, $zero
	# $t2 = size
	move $t2, $a1
	# Print open bracket
	la $a0, openBracket
	li $v0, 4
	# System call to print
	syscall
	# Call the loop function
	j loopPrintArray
	
# Main loop of the print array
loopPrintArray:
	# Loop while i != size (while (i != size))
	beq $t1, $t2, endPrintArray
	# Load the array index into the arugment to print ( print(a[i]))
	lw $a0, ($t0)
	li $v0, 4
	# System call to print
	syscall
	# Increase the index for array by 4 bits since they are aligned by 4 (i = i + 4)
	addi $t0, $t0, 4
	# Increase the index for our iterator by one (++i) 
	addi $t1, $t1, 1
	# Branch if it is the end (we need this so we do not print an extra comma at the end)
	beq $t1, $t2, endPrintArray
	# Load the comma into $a0 to print
	la $a0, commaString
	li $v0, 4
	# System call to print
	syscall
	# Jump to top
	j loopPrintArray

# End of the print, so we can print the last bracket
endPrintArray:
	# Load the bracket and new line character (printf("]\n"))
	la $a0, closeBracket
	li $v0, 4
	# System call to print
	syscall
	# Load the return address from the stack pointer
	lw $ra, 0($sp)
	# Jump out of function, continue to insertion sort
	jr $ra

headInsertionSort:

	# Allocate space in the stack 
	addi $sp, $sp, -64

	# Store word the stacks to $s registers and the save the return address
	sw $ra, 0($sp)
	sw $s0, 4($sp)
	sw $s1, 8($sp)
	sw $s2, 12($sp)
	sw $s3, 16($sp)
	sw $s4, 20($sp)
	sw $s5, 24($sp)
	sw $s6, 28($sp)

	# $s0 = array
	move $s0, $a0
	# $s1 = size
	move $s1, $a1
	#  $s2 = 1 
	li $s2, 1 
	# Start the loop for insertion sort
	j loopInsertionSort
	
loopInsertionSort:
	# Clear our temp variables
	jal clearTemps
	# Branch if the iteration variable is equal to the total size (while( i != size))
	beq $s2, $s1, endLoopInsertionSort
	# Load the array into $t0
	la $t0 ($s0)
	# Load constant 4 into $t1
	li $t1, 4
	# Multiply i by 4 because we are aligned by 4 bits in the array ( i = i * 4)
	mul $t2, $s2, $t1 
	# get the address from the data (data[i])
	add  $t3, $t0, $t2 
	# Load the value into $s3 
	lw $s3, ($t3)
	# $s4 = i - 1 
	addi $s4, $s2, -1
	# Go to the inner loop for insertion sort (check against all values in array)
	j innerLoopInsertionSort
	

# $s4 = j
	
innerLoopInsertionSort:
	# j + 1 > 0 == j >= 0
	addi $t0, $s4, 1
	# if j is 0 then end the inner loop
	beq $t0, $zero, endInnerLoopInsertionSort
	# move data[i] into the arugment value 
	move $a0, $s3

	# START STRING COMPARE
	# Here we use str_lt to compare the strings
	# Load the constant 4 and also j from the stack (because it can change from frame to frame)
	la $t0, ($s0)
	# Load 4 into $t1
	li $t1, 4
	# $t2 = 4 * j
	mul $t2, $s4, $t1
	# $t3 = data[j + (bit index)]
	add $t3, $t0, $t2 
	# load the value of the array at j into argument register (a[j])
	lw $a1, ($t3) 
	# Jump to the string compare (****todo finish the str_lt function****)
	jal str_lt
	# Get the 1 or 0 value from the string compare function and see if it is 0
	beq $v0, $zero, endInnerLoopInsertionSort
	# Add 1 to j and assign to $t1
	addi $t1, $s4, 1
	# Branch if j + 1 == 0
	beq $t1, $zero, endInnerLoopInsertionSort 

	# Clear temp registers
	jal clearTemps
	j innerLoop2InsertionSort

innerLoop2InsertionSort:
	# for (j = i-1; j >= 0 && str_lt(value, a[j]); j--) {
	# Load the address of the return address 
	la $t0, ($s0)
	# Load the const 4 into $t1
	li $t1, 4
	# $t2 = j * 4 (becuase 4 bit alignment)
	mul $t2, $s4, $t1 
	# get the new address of word in the array
	add $t3, $t0, $t2 
	# Save the new word value into $t4
	lw $t4, ($t3)
	# Create constant 4 into $t1
	li $t1, 4
	# $t2 = j + 1
	addi $t2, $s4, 1
	# $t3 = (j + 1) * 4
	mul $t3, $t2, $t1
	# Get the new address for next word from data 
	add $t1, $t3, $s0
	# j = j - 1
	addi $s4, $s4, -1 
	# a[j+1] = value;
	# Store the new word into $t4 (a[j + 1] = a[j])
	sw $t4, ($t1) 
	# Jump back to top
	j innerLoopInsertionSort 
	
endInnerLoopInsertionSort:
	# a[j+1] = a[j];
	# Increament i (i++)
	addi $s2, $s2, 1
	# Load constant so we can multiply 
	li $t1, 4
	# $t2 = j + 1
	addi $t2, $s4, 1
	# $t4 = (j + 1) * 4
	mul $t4, $t2, $t1
	# $t1 = (j + 1) * 4 + next address
	add $t1, $t4, $s0
	# Store next value ($s3 = a[j + 1])
	sw $s3, ($t1)
	# Jump back to main loop
	j loopInsertionSort
	
endLoopInsertionSort:
	# EPILOGUE
	# Deallocate memory and load the return address back 
	lw $ra, 0($sp)
	addi $sp, $sp, 64
	# Return to address
	jr $ra

	
# STR_LT ###############################################################
# PROLOGUE
str_lt:
	# Allocate stack memory of 4 bits
	addi $sp, $sp, -16
	# Store the return address 
	sw $ra, 0($sp)
	# Clear all temps
	jal clearTemps
	# Restore return address
	lw $ra, 0($sp)
	# Pointer to x
	move $t0, $a0
	# Pointer to y
	move $t1, $a1
	# Jump to the loop
	j loopStr_lt
	
# $t0 = x
# $t1 = y 
loopStr_lt:
	# First we want to load the BIT values of the chars in each string
	lb $t2, ($t0) # Load the first char 
	lb $t3, ($t1) # Load the second char
	# Now we can do bitwise operator on it (AND) and save it to $t4 
	and $t4, $t2, $t3
	# if ( *x == 0 )
	beq $t2, 0, returnTrue
	# if ( *y == '\0' ) return 0;
	beq $t4, 0, returnFalse
	# if ( *x < *y ) return 1;
	blt $t2, $t3, returnTrue
	# if ( *y < *x ) return 0;
	bgt $t2, $t3, returnFalse
	# x = x + 1
	addi $t0, $t0, 1
	# y = y + 1
	addi $t1, $t1, 1
	# Jump back to the top
	j loopStr_lt

# EPILOGUE
returnTrue: 
	# Return true or 1 
	li $v0, 1
	# deallocate stack pointer
	j deallocateAndJump
	
returnFalse:
	# Return false or 0
	li $v0, 0
	# deallocate stack pointer
	j deallocateAndJump
	
deallocateAndJump:
	# Restore return address
	lw $ra, 0($sp)
	addi $sp, $sp, 16
	jr $ra