A simple quicksort with a dynamically allocated array implemented for the MARS MIPS emulator

quicksort_mips.asm

.eqv SYS_PRINT_INT 1
.eqv SYS_READ_INT 5
.eqv SYS_MALLOC 9
.eqv SYS_EXIT 10
.eqv SYS_PRINT_CHAR 11
.eqv SYS_READ_CHAR 12


# macros that push register(s) to the stack
.macro push (%a)
	sub $sp, $sp, 4
	sw %a, ($sp)
.end_macro

.macro push (%a, %b)
	sub $sp, $sp, 8
	sw %a, 4($sp)
	sw %b, ($sp)
.end_macro

.macro push (%a, %b, %c)
	sub $sp, $sp, 12
	sw %a, 8($sp)
	sw %b, 4($sp)
	sw %c, ($sp)
.end_macro 

.macro push (%a, %b, %c, %d)
	sub $sp, $sp, 16
	sw %a, 12($sp)
	sw %b, 8($sp)
	sw %c, 4($sp)
	sw %d, ($sp)
.end_macro

.macro push (%a, %b, %c, %d, %e)
	sub $sp, $sp, 20
	sw %a, 16($sp)
	sw %b, 12($sp)
	sw %c, 8($sp)
	sw %d, 4($sp)
	sw %e, ($sp)
.end_macro 

.macro push (%a, %b, %c, %d, %e, %f)
	sub $sp, $sp, 24
	sw %a, 20($sp)
	sw %b, 16($sp)
	sw %c, 12($sp)
	sw %d, 8($sp)
	sw %e, 4($sp)
	sw %f, ($sp)
.end_macro 


.macro push (%a, %b, %c, %d, %e, %f, %g)
	sub $sp, $sp, 28
	sw %a, 24($sp)
	sw %b, 20($sp)
	sw %c, 16($sp)
	sw %d, 12($sp)
	sw %e, 8($sp)
	sw %f, 4($sp)
	sw %g, ($sp)
.end_macro

# pop macros
.macro pop (%a)
	lw %a, ($sp)
	add $sp, $sp, 4
.end_macro

.macro pop (%a, %b)
	lw %a, 4($sp)
	lw %b, ($sp)
	add $sp, $sp, 8
.end_macro

.macro pop (%a, %b, %c)
	lw %a, 8($sp)
	lw %b, 4($sp)
	lw %c, ($sp)
	add $sp, $sp, 12
.end_macro 

.macro pop (%a, %b, %c, %d)
	lw %a, 12($sp)
	lw %b, 8($sp)
	lw %c, 4($sp)
	lw %d, ($sp)
	add $sp, $sp, 16
.end_macro

.macro pop (%a, %b, %c, %d, %e)
	lw %a, 16($sp)
	lw %b, 12($sp)
	lw %c, 8($sp)
	lw %d, 4($sp)
	lw %e, ($sp)
	add $sp, $sp, 20
.end_macro 

.macro pop (%a, %b, %c, %d, %e, %f)
	lw %a, 20($sp)
	lw %b, 16($sp)
	lw %c, 12($sp)
	lw %d, 8($sp)
	lw %e, 4($sp)
	lw %f, ($sp)
	add $sp, $sp, 24
.end_macro 

.macro pop (%a, %b, %c, %d, %e, %f, %g)
	lw %a, 24($sp)
	lw %b, 20($sp)
	lw %c, 16($sp)
	lw %d, 12($sp)
	lw %e, 8($sp)
	lw %f, 4($sp)
	lw %g, ($sp)
	add $sp, $sp, 28
.end_macro 

	
# for(register = start; start < register; start++) function()
.macro for (%register, %start, %finish, %function) 
	add %register, $zero, %start
for_loop:
	bge %register, %finish, for_loop_end
	jal %function
	add %register, %register, 1
	j for_loop
for_loop_end:
.end_macro


# debugging macros:
.macro print_str (%str)	# prints a string, example usage: print_str ("string")
	.data
		print_str_label: .asciiz %str
	.text
		push ($v0, $a0)
		li $v0, 4
		la $a0, print_str_label
		syscall
		pop ($v0, $a0)
.end_macro

.macro print_reg_i (%reg) # prints the contents of a register as an int, example usage: print_reg_i ($s0)
	push ($a0, $v0, $v1)
	move $a0, %reg
	li $v0, SYS_PRINT_INT
	syscall
	pop ($a0, $v0, $v1)
.end_macro


.data
arrayptr:		# pointer to array on the heap
	.align 2
	.word 0		# NULL pointer initially

.text
start:
	jal main
	j exit


# void print_int(int)
print_int:
	li $v0, SYS_PRINT_INT
	# arg already in $a0
	syscall
	jr $ra

# int read_int(void)
read_int:
	li $v0, SYS_READ_INT
	syscall
	# result in $v0
	jr $ra
	
# void print_newline(void)
print_newline:
	li $v0, SYS_PRINT_CHAR
	li $a0, '\n'
	syscall
	jr $ra			# return

# void exit(void)
exit:
	li $v0, SYS_EXIT 
	syscall
	# no need for jr $ra

# void *malloc(int size)
malloc:
	li $v0, SYS_MALLOC
	# arg already in $a0
	syscall
	# return addr in $v0
	jr $ra

# int *malloc_int_array(int length)
malloc_int_array:
	.eqv arg_length $a0
	push ($ra)
	
	mul $a0, arg_length, 4		# length *= 4  /* 4 == sizeof(int) */
	jal malloc
	# return value already in $v0
	
	pop ($ra)
	jr $ra

# void array_create(int size)
array_create:
	.eqv arg_size $a0
	.eqv array_address $v0
	push ($ra)
	
	# arg_size already in $a0
	jal malloc_int_array		# malloc_int_array(size)
	# $v0 contains the address of our newly allocated array now
	sw $v0, arrayptr
	
	pop ($ra)
	jr $ra

# void array_set(int index, int value)
array_set:
	.eqv pointer $t0
	.eqv arg_index $a0
	.eqv arg_value $a1

	#print_str("array_set(")
	#print_reg_i($a0)
	#print_str(", ")
	#print_reg_i($a1)
	#print_str(")\n")
	
	# Equivalent to *(*arrayptr + 4 * arg_index) = arg_value;
	
	lw pointer, arrayptr			# int *pointer = *arrayptr;
	
	mul arg_index, arg_index, 4		# arg_index *= 4;   /* sizeof(int) */
	
	add pointer, pointer, arg_index		# pointer += arg_index;
	sw arg_value, (pointer)			# *pointer = arg_value
	
	jr $ra

# int array_get(int index)
array_get:
	.eqv arg_index $a0
	.eqv pointer $t0
	# return *(*arrayptr + 4 * arg_index)
	
	#print_str("array_get(")
	#print_reg_i($a0)
	#print_str(") = ")
	
	lw pointer, arrayptr		# set the pointer to the start of the array; pointer = *arrayptr;
	
	mul arg_index, arg_index, 4	# arg_index *= 4   /* sizeof int */
	
	add pointer, pointer, arg_index	# pointer += arg_index;
	lw $v0, (pointer)
	
	#print_reg_i($v0)
	#print_str("\n")
	
	jr $ra

# void array_swap(int index1, int index2)
array_swap:
	.eqv arg_index1 $a0
	.eqv arg_index2 $a1
	.eqv pointer_begin $t0
	.eqv pointer_el1 $t1
	.eqv pointer_el2 $t2
	.eqv tmp_val1 $t3
	.eqv tmp_val2 $t4
	
	#print_str ("array_swap(")
	#print_reg_i (arg_index1)
	#print_str (", ")
	#print_reg_i (arg_index2)
	#print_str (") (")

	lw pointer_begin, arrayptr		# pointer = *arrayptr;

	mul arg_index1, arg_index1, 4		# a0 *= 4 /* sizeof int */
	mul arg_index2, arg_index2, 4		# a1 *= 4 /* sizeof int */
	
	add pointer_el1, pointer_begin, arg_index1	# pointer_el1 = /*either*/ pointer_begin + arg_index1 
	add pointer_el2, pointer_begin, arg_index2	#               /*  or  */ &pointer_begin[arg_index1]

	lw tmp_val1, (pointer_el1)		# tmp_val1 = *pointer_el1
	lw tmp_val2, (pointer_el2)		# tmp_val2 = *pointer_el2
	
	sw tmp_val2, (pointer_el1)		# *pointer_el1 = tmp_val2
	sw tmp_val1, (pointer_el2)		# *pointer_el2 = tmp_val1

	#print_reg_i (tmp_val1)
	#print_str (" <-> ")
	#print_reg_i (tmp_val2)
	#print_str (")\n")

	jr $ra
		
# int choose_partition_point(int left, int right)
choose_partition_point:
	.eqv arg_left $a0
	.eqv arg_right $a1
	.eqv tmp $t0
	
	# return left - (right - left) / 2
	sub tmp, arg_right, arg_left	# tmp = right - left
	div tmp, tmp, 2			# tmp /= 2
	add $v0, arg_left, tmp		# return value = left + tmp
	
	jr $ra
	
	
# int partition_array(int left, int right)
partition_array:
	.eqv partition_index $s0
	.eqv partition_value $s1
	.eqv partition_current_position $s2
	.eqv partition_i $s3
	.eqv partition_arg_left $s4
	.eqv partition_arg_right $s5
	
	push ($ra, $s0, $s1, $s2, $s3, $s4, $s5)
	
	move partition_arg_left, $a0
	move partition_arg_right, $a1
	
	# same arguments ($a0, $a1)
	jal choose_partition_point
	move partition_index, $v0			# partition_index = choose_partition_point(left, right)
	
	move $a0, partition_index
	jal array_get
	move partition_value, $v0			# partition_value = array[partition_index]
	
	# move the partitioning value to the end of the array
	move $a0, partition_index
	move $a1, partition_arg_right
	jal array_swap					# array_swap(partition_index, partition_arg_right)
	
	# start from left
	move partition_current_position, partition_arg_left
	
	# loop from left to right-1
	for (partition_i, partition_arg_left, partition_arg_right, partition_array_inside_loop)
	
	# bring the partitioning value back
	move $a0, partition_current_position
	move $a1, partition_arg_right
	jal array_swap					# array_swap(partition_current_position, partition_arg_right)
	
	move $v0, partition_current_position		# return partition_current_position
	
	pop ($ra, $s0, $s1, $s2, $s3, $s4, $s5)
	
	jr $ra
	
	# loop contents
	partition_array_inside_loop:
		push ($ra)
		
		# if(array_get(partition_i) >= partition_value) return;
		move $a0, partition_i
		jal array_get		# v0 = array_get(partition_i)
		bge $v0, partition_value, partition_array_inside_loop_end
		
		move $a0, partition_i
		move $a1, partition_current_position
		jal array_swap
		
		add partition_current_position, partition_current_position, 1
		
		partition_array_inside_loop_end:
		pop ($ra)
		jr $ra


# void quicksort(int left, int right)
quicksort:
	.eqv arg_left $a0
	.eqv arg_right $a1
	.eqv left $s0
	.eqv right $s1
	.eqv pivot $s2
	#print_str ("quicksort(")
	#print_reg_i (arg_left)
	#print_str (", ")
	#print_reg_i (arg_right)
	#print_str (")\n")
	
	bge arg_left, arg_right, quicksort_end # don't need to do anything if left >= right
	
	push ($ra, $s0, $s1, $s2)
	
	
	move left, arg_left
	move right, arg_right
	
	# arguments ($a0 and $a1) are already (left, right)
	jal partition_array # pivot = partition_array(left, right)
	move pivot, $v0
	
	#print_str ("left quicksort:\n")
	move $a0, left
	sub $a1, pivot, 1
	jal quicksort	# quicksort(left, pivot - 1)
	
	#print_str ("right quicksort:\n")
	add $a0, pivot, 1
	move $a1, right
	jal quicksort	# quicksort(pivot + 1, right)
	
	
	pop ($ra, $s0, $s1, $s2)
	
	quicksort_end:
	jr $ra


# void main(void)
main:
	.eqv read_loop_i $s0
	.eqv print_loop_i $s0 # reusing the same register as for read_loop_i
	.eqv array_length $s1
	push($ra)
	
	print_str ("\ninput length: ")

	jal read_int
	move array_length, $v0		# array_length = read_int()

	move $a0, array_length
	jal array_create		# array_create(array_length)

	print_str ("\ninput contents:\n")

	for (read_loop_i, 0, array_length, main_read_loop)
	jal print_newline
	
	li $a0, 0
	sub $a1, array_length, 1
	jal quicksort			# quicksort(0, array_length - 1)
	
	for (print_loop_i, 0, array_length, main_print_loop)
	
	pop ($ra)
	jr $ra

# body of the read for loop from main
main_read_loop:
	push ($ra) # don't push read_loop_i ($s0) because we are using the value from the loop in main

	move $a0, read_loop_i
	jal read_int
	move $a1, $v0
	jal array_set	# array_set(read_loop_i, read_int())
	
	pop ($ra)
	jr $ra

# body of the print for loop from main
main_print_loop:
	push ($ra) # don't push print_loop_i ($s0) because we are using the value from the loop in main

	move $a0, print_loop_i
	jal array_get
	move $a0, $v0	# move the return value to the argument
	jal print_int	# print_int(array_get(print_loop_i))

	jal print_newline

	pop ($ra)
	jr $ra