;
;	CPE 221 Assembly Example
;	
;	This program merges two sorted lists into one list.
;
;       #include <iostream>
;       #include <iomanip>
;       
;       using namespace std;
; 
;       int main()
;       {
;         const int size1 = 15;
;         const int size2 = 25;
;         int size3 = 40;
;         int array1[size1] = {-20000, -3000, -386, -122, -44, -11, 1, 59, 267, 999, 1111, 2929, 3333, 3333, 11111};
;         int array2[size2] {-30000, -19555, -12222, -8888, -555, -234, -88, 1, 3, 45, 88, 111, 192, 192, 212, 333, 
;                            6666, 10000, 11000, 15622, 22312, 33333, 54321, 88976, 100022};
;         int array3[40];
;         int index1 = 0;
;         int index2 = 0;
;         int index3 = 0;
;      
;         while ((index1 < size1) && (index2 < size2))
;         {
;           if (array1[index1] < array2[index2])
;             array3[index3] = array1[index1++];
;           else
;             array3[index3] = array2[index2++];
;           index3++;
;         }
;         while (index1 < size1)
;           array3[index3++] = array1[index1++];
;         while (index2 < size2)
;           array3[index3++] = array2[index2++];
;       }
    

	.org	200
size1:	.equ	15
size2:	.equ	25
size3:	.equ	40

array1:	.dc	-20000, -3000, -386, -122, -44, -11, 1, 59, 267, 999, 1111, 2929
		.dc 	3333, 3333, 11111
array2:	.dc	-30000, -19555, -12222, -8888, -555, -234, -88, 1, 3, 45, 88, 111
		.dc	192, 192, 212
		.dc	333, 6666, 10000, 11000, 15622, 22312, 33333, 54321, 88976, 100022
array3:	.dw	size3

orig:		.org	1000
		lar	r29, 2less
		lar 	r28, incindex3
		lar	r27, finish1
		lar	r26, check
		lar	r25, finish2
		lar	r24, done

		lar	r10, array1		; pointer to first element of array1
		lar	r11, array2		; pointer to first element of array2
		lar	r12, array3		; pointer to first element of array3

		la	r1, size1		; holds size of array1
		la	r2, size2		; holds size of array2
		sub	r4, r4, r4		; r4 = 0, index1 into array1
		sub	r5, r5, r5		; r5 = 0, index2 into array2
		sub	r6, r6, r6		; r6 = 0, index3 into array3
check:	sub	r9, r4, r1		; Check to see whether index1 < size1.
		brpl	r25, r9		; If not, array1 done, use array2.
		sub	r9, r5, r2		; Check to see whether index2 < size2.
		brpl	r27, r9		; If not, array2 done, use array1.

next:		shl	r13, r4, 2		; Multiply index1 by 4 to access entry 
						;in array1 by byte address.
		add	r13, r13, r10	; Add index1 to base array1 pointer.
		ld	r7, 0(r13)		; Load array1[index] into r7.
		shl	r13, r5, 2		; Multiply index2 by 4 to access entry 
						; in array2 by byte address.
		add	r13, r13, r11	; Add index2 to base array2 pointer.
		ld	r8, 0(r13)		; Load array2[index] into r8.
		shl	r13, r6, 2		; Multiply index3 by 4 to access entry 
						; in array3  by byte address.
		add	r13, r13, r12	; Add index3 to base array3 pointer.
		sub	r9, r7, r8		; Check array1[index1] < array2[index2]
		brpl	r29, r9		; If not, branch to 2less.
1less:	st	r7, 0(r13)		; Set array3[index3] = array1[index1].
		addi	r4, r4, 1		; Increment index1 next element in array1.
		br	r28			; Get ready to increment index3.
2less:	st	r8, 0(r13)		; Set array3[index3] = array2[index2].
		addi	r5, r5, 1		; Increment index2 for next element in array2.
incindex3:	addi	r6, r6, 1		; Increment index3.
		br	r26			; Look at next pair of numbers.

finish1:	sub 	r9, r4, r1		; Check to see whether index1 < size1.
		brpl	r24, r9		; If not, done with array1.
		shl	r13, r4, 2		; Multiply index1 by 4 to access entry 
						; in arrray1 by byte address.
		add	r13, r13, r10	; Add index1 to base array1 pointer.
		ld	r7, 0(r13)		; Load array1[index1] into r7.
		shl	r13, r6, 2		; Multiple index3 by 4 to access entry 
						; in array3 by byte address.
		add	r13, r13, r12	; Add index3 to base array3 pointer.
		st	r7, 0(r13)		; Set array3[index3] = array1[index1].
		addi	r4, r4, 1		; Increment index1.
		addi	r6, r6, 1		; Increment index3.
		br	r27			; Look at next entry in array1.

finish2:	sub	r9, r5, r2		; Check to see whether index2 < size2.
		brpl	r24, r9		; If not, done with array2.
		shl	r13, r5, 2		; Multiply index2 by 4 to access entry 
						; in array2 by byte address.
		add	r13, r13, r11	; Add index2 to base array2 pointer.
		ld	r8, 0(r13)		; Load array2[index2] into r8.
		shl	r13, r6, 2		; Multiply index3 by 4 to access entry 
						; in array3 by byte address.
		add	r13, r13, r12	; Add index3 to base array3 pointer.
		st	r8, 0(r13)		; Set array3[index3] = array2[index2].
		addi	r5, r5, 1		; Increment index2.
		addi	r6, r6, 1		; Increment index3.
		br	r25			; Look at next entry in array2.
done:		stop