Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- .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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement