SHARE
TWEET

Untitled

a guest May 19th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. .eqv SYS_PRINT_INT 1
  2. .eqv SYS_READ_INT 5
  3. .eqv SYS_MALLOC 9
  4. .eqv SYS_EXIT 10
  5. .eqv SYS_PRINT_CHAR 11
  6. .eqv SYS_READ_CHAR 12
  7.  
  8.  
  9. # macros that push register(s) to the stack
  10. .macro push (%a)
  11.     sub $sp, $sp, 4
  12.     sw %a, ($sp)
  13. .end_macro
  14.  
  15. .macro push (%a, %b)
  16.     sub $sp, $sp, 8
  17.     sw %a, 4($sp)
  18.     sw %b, ($sp)
  19. .end_macro
  20.  
  21. .macro push (%a, %b, %c)
  22.     sub $sp, $sp, 12
  23.     sw %a, 8($sp)
  24.     sw %b, 4($sp)
  25.     sw %c, ($sp)
  26. .end_macro
  27.  
  28. .macro push (%a, %b, %c, %d)
  29.     sub $sp, $sp, 16
  30.     sw %a, 12($sp)
  31.     sw %b, 8($sp)
  32.     sw %c, 4($sp)
  33.     sw %d, ($sp)
  34. .end_macro
  35.  
  36. .macro push (%a, %b, %c, %d, %e)
  37.     sub $sp, $sp, 20
  38.     sw %a, 16($sp)
  39.     sw %b, 12($sp)
  40.     sw %c, 8($sp)
  41.     sw %d, 4($sp)
  42.     sw %e, ($sp)
  43. .end_macro
  44.  
  45. .macro push (%a, %b, %c, %d, %e, %f)
  46.     sub $sp, $sp, 24
  47.     sw %a, 20($sp)
  48.     sw %b, 16($sp)
  49.     sw %c, 12($sp)
  50.     sw %d, 8($sp)
  51.     sw %e, 4($sp)
  52.     sw %f, ($sp)
  53. .end_macro
  54.  
  55.  
  56. .macro push (%a, %b, %c, %d, %e, %f, %g)
  57.     sub $sp, $sp, 28
  58.     sw %a, 24($sp)
  59.     sw %b, 20($sp)
  60.     sw %c, 16($sp)
  61.     sw %d, 12($sp)
  62.     sw %e, 8($sp)
  63.     sw %f, 4($sp)
  64.     sw %g, ($sp)
  65. .end_macro
  66.  
  67. # pop macros
  68. .macro pop (%a)
  69.     lw %a, ($sp)
  70.     add $sp, $sp, 4
  71. .end_macro
  72.  
  73. .macro pop (%a, %b)
  74.     lw %a, 4($sp)
  75.     lw %b, ($sp)
  76.     add $sp, $sp, 8
  77. .end_macro
  78.  
  79. .macro pop (%a, %b, %c)
  80.     lw %a, 8($sp)
  81.     lw %b, 4($sp)
  82.     lw %c, ($sp)
  83.     add $sp, $sp, 12
  84. .end_macro
  85.  
  86. .macro pop (%a, %b, %c, %d)
  87.     lw %a, 12($sp)
  88.     lw %b, 8($sp)
  89.     lw %c, 4($sp)
  90.     lw %d, ($sp)
  91.     add $sp, $sp, 16
  92. .end_macro
  93.  
  94. .macro pop (%a, %b, %c, %d, %e)
  95.     lw %a, 16($sp)
  96.     lw %b, 12($sp)
  97.     lw %c, 8($sp)
  98.     lw %d, 4($sp)
  99.     lw %e, ($sp)
  100.     add $sp, $sp, 20
  101. .end_macro
  102.  
  103. .macro pop (%a, %b, %c, %d, %e, %f)
  104.     lw %a, 20($sp)
  105.     lw %b, 16($sp)
  106.     lw %c, 12($sp)
  107.     lw %d, 8($sp)
  108.     lw %e, 4($sp)
  109.     lw %f, ($sp)
  110.     add $sp, $sp, 24
  111. .end_macro
  112.  
  113. .macro pop (%a, %b, %c, %d, %e, %f, %g)
  114.     lw %a, 24($sp)
  115.     lw %b, 20($sp)
  116.     lw %c, 16($sp)
  117.     lw %d, 12($sp)
  118.     lw %e, 8($sp)
  119.     lw %f, 4($sp)
  120.     lw %g, ($sp)
  121.     add $sp, $sp, 28
  122. .end_macro
  123.  
  124.    
  125. # for(register = start; start < register; start++) function()
  126. .macro for (%register, %start, %finish, %function)
  127.     add %register, $zero, %start
  128. for_loop:
  129.     bge %register, %finish, for_loop_end
  130.     jal %function
  131.     add %register, %register, 1
  132.     j for_loop
  133. for_loop_end:
  134. .end_macro
  135.  
  136.  
  137. # debugging macros:
  138. .macro print_str (%str) # prints a string, example usage: print_str ("string")
  139.     .data
  140.         print_str_label: .asciiz %str
  141.     .text
  142.         push ($v0, $a0)
  143.         li $v0, 4
  144.         la $a0, print_str_label
  145.         syscall
  146.         pop ($v0, $a0)
  147. .end_macro
  148.  
  149. .macro print_reg_i (%reg) # prints the contents of a register as an int, example usage: print_reg_i ($s0)
  150.     push ($a0, $v0, $v1)
  151.     move $a0, %reg
  152.     li $v0, SYS_PRINT_INT
  153.     syscall
  154.     pop ($a0, $v0, $v1)
  155. .end_macro
  156.  
  157.  
  158. .data
  159. arrayptr:       # pointer to array on the heap
  160.     .align 2
  161.     .word 0     # NULL pointer initially
  162.  
  163. .text
  164. start:
  165.     jal main
  166.     j exit
  167.  
  168.  
  169. # void print_int(int)
  170. print_int:
  171.     li $v0, SYS_PRINT_INT
  172.     # arg already in $a0
  173.     syscall
  174.     jr $ra
  175.  
  176. # int read_int(void)
  177. read_int:
  178.     li $v0, SYS_READ_INT
  179.     syscall
  180.     # result in $v0
  181.     jr $ra
  182.    
  183. # void print_newline(void)
  184. print_newline:
  185.     li $v0, SYS_PRINT_CHAR
  186.     li $a0, '\n'
  187.     syscall
  188.     jr $ra          # return
  189.  
  190. # void exit(void)
  191. exit:
  192.     li $v0, SYS_EXIT
  193.     syscall
  194.     # no need for jr $ra
  195.  
  196. # void *malloc(int size)
  197. malloc:
  198.     li $v0, SYS_MALLOC
  199.     # arg already in $a0
  200.     syscall
  201.     # return addr in $v0
  202.     jr $ra
  203.  
  204. # int *malloc_int_array(int length)
  205. malloc_int_array:
  206.     .eqv arg_length $a0
  207.     push ($ra)
  208.    
  209.     mul $a0, arg_length, 4      # length *= 4  /* 4 == sizeof(int) */
  210.     jal malloc
  211.     # return value already in $v0
  212.    
  213.     pop ($ra)
  214.     jr $ra
  215.  
  216. # void array_create(int size)
  217. array_create:
  218.     .eqv arg_size $a0
  219.     .eqv array_address $v0
  220.     push ($ra)
  221.    
  222.     # arg_size already in $a0
  223.     jal malloc_int_array        # malloc_int_array(size)
  224.     # $v0 contains the address of our newly allocated array now
  225.     sw $v0, arrayptr
  226.    
  227.     pop ($ra)
  228.     jr $ra
  229.  
  230. # void array_set(int index, int value)
  231. array_set:
  232.     .eqv pointer $t0
  233.     .eqv arg_index $a0
  234.     .eqv arg_value $a1
  235.  
  236.     #print_str("array_set(")
  237.     #print_reg_i($a0)
  238.     #print_str(", ")
  239.     #print_reg_i($a1)
  240.     #print_str(")\n")
  241.    
  242.     # Equivalent to *(*arrayptr + 4 * arg_index) = arg_value;
  243.    
  244.     lw pointer, arrayptr            # int *pointer = *arrayptr;
  245.    
  246.     mul arg_index, arg_index, 4     # arg_index *= 4;   /* sizeof(int) */
  247.    
  248.     add pointer, pointer, arg_index     # pointer += arg_index;
  249.     sw arg_value, (pointer)         # *pointer = arg_value
  250.    
  251.     jr $ra
  252.  
  253. # int array_get(int index)
  254. array_get:
  255.     .eqv arg_index $a0
  256.     .eqv pointer $t0
  257.     # return *(*arrayptr + 4 * arg_index)
  258.    
  259.     #print_str("array_get(")
  260.     #print_reg_i($a0)
  261.     #print_str(") = ")
  262.    
  263.     lw pointer, arrayptr        # set the pointer to the start of the array; pointer = *arrayptr;
  264.    
  265.     mul arg_index, arg_index, 4 # arg_index *= 4   /* sizeof int */
  266.    
  267.     add pointer, pointer, arg_index # pointer += arg_index;
  268.     lw $v0, (pointer)
  269.    
  270.     #print_reg_i($v0)
  271.     #print_str("\n")
  272.    
  273.     jr $ra
  274.  
  275. # void array_swap(int index1, int index2)
  276. array_swap:
  277.     .eqv arg_index1 $a0
  278.     .eqv arg_index2 $a1
  279.     .eqv pointer_begin $t0
  280.     .eqv pointer_el1 $t1
  281.     .eqv pointer_el2 $t2
  282.     .eqv tmp_val1 $t3
  283.     .eqv tmp_val2 $t4
  284.    
  285.     #print_str ("array_swap(")
  286.     #print_reg_i (arg_index1)
  287.     #print_str (", ")
  288.     #print_reg_i (arg_index2)
  289.     #print_str (") (")
  290.  
  291.     lw pointer_begin, arrayptr      # pointer = *arrayptr;
  292.  
  293.     mul arg_index1, arg_index1, 4       # a0 *= 4 /* sizeof int */
  294.     mul arg_index2, arg_index2, 4       # a1 *= 4 /* sizeof int */
  295.    
  296.     add pointer_el1, pointer_begin, arg_index1  # pointer_el1 = /*either*/ pointer_begin + arg_index1
  297.     add pointer_el2, pointer_begin, arg_index2  #               /*  or  */ &pointer_begin[arg_index1]
  298.  
  299.     lw tmp_val1, (pointer_el1)      # tmp_val1 = *pointer_el1
  300.     lw tmp_val2, (pointer_el2)      # tmp_val2 = *pointer_el2
  301.    
  302.     sw tmp_val2, (pointer_el1)      # *pointer_el1 = tmp_val2
  303.     sw tmp_val1, (pointer_el2)      # *pointer_el2 = tmp_val1
  304.  
  305.     #print_reg_i (tmp_val1)
  306.     #print_str (" <-> ")
  307.     #print_reg_i (tmp_val2)
  308.     #print_str (")\n")
  309.  
  310.     jr $ra
  311.        
  312. # int choose_partition_point(int left, int right)
  313. choose_partition_point:
  314.     .eqv arg_left $a0
  315.     .eqv arg_right $a1
  316.     .eqv tmp $t0
  317.    
  318.     # return left - (right - left) / 2
  319.     sub tmp, arg_right, arg_left    # tmp = right - left
  320.     div tmp, tmp, 2         # tmp /= 2
  321.     add $v0, arg_left, tmp      # return value = left + tmp
  322.    
  323.     jr $ra
  324.    
  325.    
  326. # int partition_array(int left, int right)
  327. partition_array:
  328.     .eqv partition_index $s0
  329.     .eqv partition_value $s1
  330.     .eqv partition_current_position $s2
  331.     .eqv partition_i $s3
  332.     .eqv partition_arg_left $s4
  333.     .eqv partition_arg_right $s5
  334.    
  335.     push ($ra, $s0, $s1, $s2, $s3, $s4, $s5)
  336.    
  337.     move partition_arg_left, $a0
  338.     move partition_arg_right, $a1
  339.    
  340.     # same arguments ($a0, $a1)
  341.     jal choose_partition_point
  342.     move partition_index, $v0           # partition_index = choose_partition_point(left, right)
  343.    
  344.     move $a0, partition_index
  345.     jal array_get
  346.     move partition_value, $v0           # partition_value = array[partition_index]
  347.    
  348.     # move the partitioning value to the end of the array
  349.     move $a0, partition_index
  350.     move $a1, partition_arg_right
  351.     jal array_swap                  # array_swap(partition_index, partition_arg_right)
  352.    
  353.     # start from left
  354.     move partition_current_position, partition_arg_left
  355.    
  356.     # loop from left to right-1
  357.     for (partition_i, partition_arg_left, partition_arg_right, partition_array_inside_loop)
  358.    
  359.     # bring the partitioning value back
  360.     move $a0, partition_current_position
  361.     move $a1, partition_arg_right
  362.     jal array_swap                  # array_swap(partition_current_position, partition_arg_right)
  363.    
  364.     move $v0, partition_current_position        # return partition_current_position
  365.    
  366.     pop ($ra, $s0, $s1, $s2, $s3, $s4, $s5)
  367.    
  368.     jr $ra
  369.    
  370.     # loop contents
  371.     partition_array_inside_loop:
  372.         push ($ra)
  373.        
  374.         # if(array_get(partition_i) >= partition_value) return;
  375.         move $a0, partition_i
  376.         jal array_get       # v0 = array_get(partition_i)
  377.         bge $v0, partition_value, partition_array_inside_loop_end
  378.        
  379.         move $a0, partition_i
  380.         move $a1, partition_current_position
  381.         jal array_swap
  382.        
  383.         add partition_current_position, partition_current_position, 1
  384.        
  385.         partition_array_inside_loop_end:
  386.         pop ($ra)
  387.         jr $ra
  388.  
  389.  
  390. # void quicksort(int left, int right)
  391. quicksort:
  392.     .eqv arg_left $a0
  393.     .eqv arg_right $a1
  394.     .eqv left $s0
  395.     .eqv right $s1
  396.     .eqv pivot $s2
  397.     #print_str ("quicksort(")
  398.     #print_reg_i (arg_left)
  399.     #print_str (", ")
  400.     #print_reg_i (arg_right)
  401.     #print_str (")\n")
  402.    
  403.     bge arg_left, arg_right, quicksort_end # don't need to do anything if left >= right
  404.    
  405.     push ($ra, $s0, $s1, $s2)
  406.    
  407.    
  408.     move left, arg_left
  409.     move right, arg_right
  410.    
  411.     # arguments ($a0 and $a1) are already (left, right)
  412.     jal partition_array # pivot = partition_array(left, right)
  413.     move pivot, $v0
  414.    
  415.     #print_str ("left quicksort:\n")
  416.     move $a0, left
  417.     sub $a1, pivot, 1
  418.     jal quicksort   # quicksort(left, pivot - 1)
  419.    
  420.     #print_str ("right quicksort:\n")
  421.     add $a0, pivot, 1
  422.     move $a1, right
  423.     jal quicksort   # quicksort(pivot + 1, right)
  424.    
  425.    
  426.     pop ($ra, $s0, $s1, $s2)
  427.    
  428.     quicksort_end:
  429.     jr $ra
  430.  
  431.  
  432. # void main(void)
  433. main:
  434.     .eqv read_loop_i $s0
  435.     .eqv print_loop_i $s0 # reusing the same register as for read_loop_i
  436.     .eqv array_length $s1
  437.     push($ra)
  438.    
  439.     print_str ("\ninput length: ")
  440.  
  441.     jal read_int
  442.     move array_length, $v0      # array_length = read_int()
  443.  
  444.     move $a0, array_length
  445.     jal array_create        # array_create(array_length)
  446.  
  447.     print_str ("\ninput contents:\n")
  448.  
  449.     for (read_loop_i, 0, array_length, main_read_loop)
  450.     jal print_newline
  451.    
  452.     li $a0, 0
  453.     sub $a1, array_length, 1
  454.     jal quicksort           # quicksort(0, array_length - 1)
  455.    
  456.     for (print_loop_i, 0, array_length, main_print_loop)
  457.    
  458.     pop ($ra)
  459.     jr $ra
  460.  
  461. # body of the read for loop from main
  462. main_read_loop:
  463.     push ($ra) # don't push read_loop_i ($s0) because we are using the value from the loop in main
  464.  
  465.     move $a0, read_loop_i
  466.     jal read_int
  467.     move $a1, $v0
  468.     jal array_set   # array_set(read_loop_i, read_int())
  469.    
  470.     pop ($ra)
  471.     jr $ra
  472.  
  473. # body of the print for loop from main
  474. main_print_loop:
  475.     push ($ra) # don't push print_loop_i ($s0) because we are using the value from the loop in main
  476.  
  477.     move $a0, print_loop_i
  478.     jal array_get
  479.     move $a0, $v0   # move the return value to the argument
  480.     jal print_int   # print_int(array_get(print_loop_i))
  481.  
  482.     jal print_newline
  483.  
  484.     pop ($ra)
  485.     jr $ra
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top