/**
 * This program bubble sorts an array of 4 integers, from largest to
 * smallest. It sorts in-place, starting from memory address 0x10.
 *
 * Copyright(c) 2019-2021,2023-2024 Jason Tang <jtang@umbc.edu>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 */

/* entrypoint into program */

	/* first store into memory the values to sort */
	movi   R0, #0x10	// starting address for array
	movi   R1, #0x20
	movi   R2, #0x30
	movi   R3, #0x10
	movi   R4, #0x40
	stwi   R1, R0, #0	// data[0] = 0x20
	stwi   R2, R0, #1	// data[1] = 0x30
	stwi   R3, R0, #2	// data[2] = 0x10
	stwi   R4, R0, #3	// data[3] = 0x40

	/* set the stack pointer towards end of memory */
	movi   R6, #0
	movis  R6, #0xe0

	/* call subfunction to sort */
	bl     R7, bsort
	halt   0x01

/*
 * This function sorts an array in-place, from lowest to highest. The
 * equivalent C code is this:
 *
 *    void bsort(unsigned data[]) {
 *        int i = 0;
 *        while (i < 3) {
 *            int j = 0;
 *            while (j < (3 - i)) {
 *                unsigned a = data[j];
 *                unsigned b = data[j+1];
 *                if (a > b) {
 *                    data[j] = b;
 *                    data[j+1] = a;
 *                }
 *                j++;
 *            }
 *            i++;
 *        }
 *    }
 *
 *
 * As a reminder, ULNAv2-B uses this calling convention:
 *   R0 - holds first function parameter, and holds return value
 *   R1 - holds second function parameter
 *   R2-R5 - callee saved
 *   R6 - stack pointer
 *   R7 - link register (holds return address)
 */
bsort:
	// This function uses 6 variables. Assign them to registers like so:
	//    R0 - data (the array to be sorted)
	//    R1 - i
	//    R2 - j
	//    R3 - a
	//    R4 - b
	//    R5 - <holds temp vals>
	//  Because callees are responsible for saving registers R2
	//  through R5, first push them on to the stack
	addi.  R6, R6, #-4	// subtract 4 from the stack
	stwi   R2, R6, #3
	stwi   R3, R6, #2
	stwi   R4, R6, #1
	stwi   R5, R6, #0
	movi   R1, #0		// i = outer index = 0

	// outer loop
top_of_outer:
	cmpi.  R1, #3		// while (i < 3) {
	b.ge   end_of_func
	movi   R2, #0		//   j = inner index = 0
	// inner loop
top_of_inner:
	negi.  R5, R1, #4	//   <temp> = 3 - i
	cmp.   R2, R5		//   while (j < <temp>) {
	b.ge   end_of_inner
	ldw    R3, R0, R2	//     a = data[j]
	addi.  R5, R2, #1	//     <temp> = j + 1
	ldw    R4, R0, R5	//     b = data[<temp>]
	cmp.   R3, R4		//     if (a > b) {
	b.le   after_swap
	// swap values
	stw    R4, R0, R2	//       data[j] = b
	stw    R3, R0, R5	//       data[<temp>] = a (recall that temp
				//                         is still j+1)
				//     }
after_swap:
	addi.  R2, R2, #1	//     j++;
	b      top_of_inner	//   }
	// end of inner loop
end_of_inner:
	addi.  R1, R1, #1	//   i++
	b      top_of_outer	// }

end_of_func:
	// restore callee-saved registers
	ldwi   R5, R6, #0
	ldwi   R4, R6, #1
	ldwi   R3, R6, #2
	ldwi   R2, R6, #3
	// restore stack pointer
	addi.  R6, R6, #4
	// then jump to the return address
	br     R7