include(macro_defs.m)

		define(SIZE,40)
		define(i_r,l0)
		define(j_r,l1)
		define(tmp_r,l2)

		local_var
		var(i_s,4)
		var(j_s,4)
		var(tmp_s,4)
		var(v_s,4,4*SIZE)
		var(SIZE_s,4)

fma:	.asciz "v[%d] = %d\n"
		.align 4
fmb:	.asciz "Random Array\n"
		.align 4
fmc:	.asciz "\nSorted Array\n"
		.align 4

		begin_main

		mov 	0,		%i_r					!i = 0
		st 		%i_r,	[%fp+i_s]				!store i on stack

		mov 	SIZE,	%l3
		st 		%l3, 	[%fp+SIZE_s]			!store size of array on the stack

		set		fmb,	%o0						!print "Random Array"
		call	printf
		nop

fill_array:
		ld 		[%fp+i_s],	%i_r				!load i from stack
		ld 		[%fp+SIZE_s],	%l3				!load size from stack into %l3

		cmp 	%i_r,	%l3						!compare i and size
		bge 	next							!branch to next if i>=size
		nop

		call	rand							!random number generator
		nop
		and		%o0, 	0xff, 	%l7				!0-256. Random number stored in %l7

		sll		%i_r,	2, 		%l6				!the traversing thing from tutorial
		add		%fp,	%l6,	%l6
		st 		%l7, 	[%l6+v_s]				!store random number in stack

		set 	fma,	%o0						!prepare to print
		mov 	%i_r, 	%o1						!move i
		mov 	%l7, 	%o2 					!move value if j[i]
		call 	printf							!print
		nop

		ld 		[%fp+i_s], 	%i_r				!load i
		add 	%i_r,  		1,		%i_r		!increment i
		st 		%i_r,		[%fp+i_s] 			!store i in stack
		ba 		fill_array						!branch to fill_array
		nop

next:
		mov 	1,		%i_r 					!set i = 1
		st 		%i_r, 	[%fp+i_s]				!store i on the stack
		mov 	%i_r,		%j_r				!set j = i
		st 		%j_r,	[%fp+j_s]				!store j on the stack

outer_loop:

		ld 		[%fp+SIZE_s],	%l3				!load SIZE into %l3
		ld 		[%fp+i_s],	%i_r				!load i from stack
		cmp 	%i_r,	%l3						!check if i < SIZE
		bge 	print 							!branch to printing the array if i >= SIZE
		nop

		sll		%i_r,	2,		%l6				!traverse thing from tutorial
		add		%fp,	%l6,	%l6
		ld 		[%l6+v_s],		%tmp_r			!set tmp = v[i]
		st 		%tmp_r,			[%fp+tmp_s]		!store tmp on the stack

 inner_loop:
		ld 		[%fp+j_s],	%j_r				!load j from the stack

		cmp 	%j_r,		0 					!check if j > 0

		ble		outer_end						!if j <= 0, skip to the end of the outer loop
		nop
		sub		%j_r,	1,		%l5				!get j-1

		sll		%l5,	2,		%l6				!traverse thing from tutorial
		add		%fp,	%l6,	%l6
		ld 		[%l6+v_s],	%l4					!%l4 = v[j-1]

		ld 		[%fp+tmp_s],	%tmp_r			!load tmp from the stack
		cmp 	%tmp_r,			%l4				!check if tmp < v[j-1]
		bge 	outer_end						!go to end of outer loop if tmp >= v[j-1]
		nop

		sll		%j_r,	2,		%l6				!traverse thing from tutorial
		add		%fp,	%l6,	%l6
		st		%l4,	[%l6+v_s]				!v[j] = v[j-1]

		sub		%j_r,	1,		%j_r			!decrement j
		st		%j_r,	[%fp+j_s]				!store j on the stack
		ba 		inner_loop
		nop

outer_end:

		ld 		[%fp+tmp_s],	%tmp_r			!load tmp from stack

		sll		%j_r,	2,		%l6				!traverse thing from tutorial
		add		%fp,	%l6,	%l6
		st 		%tmp_r,	[%l6+v_s]				!v[j] = tmp

		add		%i_r,	1,		%i_r			!increase i by 1
		st 		%i_r,	[%fp +i_s]				!store i on the stack
		mov 	%i_r,	%j_r					!set j=i
		st 		%j_r,	[%fp+j_s]				!store j on the stack
		ba 		outer_loop
		nop


print:
		mov 	0,		%i_r 					!i = 0
		set		fmc,	%o0 					!set the string
		call	printf							!print out the label "Sorted Array"


		st 		%i_r,	[%fp+i_s]				!store i on the stack

print_sorted:
		ld 		[%fp+i_s],		%i_r			!load i from the stack
		ld 		[%fp+SIZE_s],	%l3				!load SIZE into %l3
		cmp 	%i_r, 			%l3				!check if i < SIZE
		bge		end 							!branch to end if i >=size
		nop

		sll		%i_r,	2,		%l7				!%g2 = i * 4 (first loop instruction)
		add		%fp,	%l7,	%l7				!%g2 = %fp + (i * 4)
		ld 		[%l7+v_s],		%g2				!load v[i] into %g1

		set 	fma,			%o0				!set the correct string format
		ld 		[%fp+i_s],	%i_r			!load i from the stack
		mov 	%i_r,			%o1				!move i to %o1 for printing
		mov 	%g2,			%o2				!move v[i] to %o2 for printing
		call	printf							!print v[i]
		nop

		inc 	%i_r 							!i++
		st 		%i_r,			[%fp+i_s]		!store i on the stack
		ba 		print_sorted
		nop
end:
		end_main								!end program