; Data reverser.asm
; This SimpSim assembly language program sorts data from smallest to largest.
; Input:   2,77,3,66,4,55,5,44,6,33,7,22,8,11,9
; Output:  2,3,4,5,6,7,8,9,11,22,33,44,55,66,77

  ;; 1.  Load the Lo and Hi pointers with the start and end of the data
  load R1,Data      ; Lo Pointer (initially the start of the data)
  load R2,EndOfData ; Hi Pointer (initially the end of the data)
  load R3,1         ; needed to increment Lo pointer
  load R4,-1        ; needed to decrement Hi pointer  
  addi R2,R2,R4     ; Decrement Hi pointer to last data element
OuterLoop:
  ;; 2.  Check if we are done (if Hi <= Lo)
  move R0,R1        ; Copy Lo Pointer (R1) into R0
  jmpLE R2<=R0,Done ; If (Hi <= Lo) jump to Done
  ;; 3.  Set lowestRemainingPointer (R5) to current Lo pointer (R1)
  move R5,R1
  ;; 4.  Set lowestRemaining (R6) to M[current Lo Pointer]
  load R6,[R1]
  ;; 5.  Set nextCheckPointer (R7) to Lo Pointer + 1
  move R7,R1     ;; R7 <- R1 (Lo Pointer)
  addi R7,R7,R3  ;; R7 <- R7 + 1 (Lo Pointer  + 1)
InnerLoop:
  ;; 6.  If HiPointer < nextCheckPointer, goto FinishInnerLoop
  move R0,R7                     ;; R0 <- R7 (nextCheckPointer)
  addi R0,R0,R4                  ;; R0 <- nextCheckPointer - 1
  jmpLE R2<=R0,ContinueOuterLoop ;; note R2 is HiPointer
  ;; 7.  If the value in M[nextCheckPointer] <= M[lowestRemainingPointer]
  ;;     then set lowestRemainingPointer and lowestRemaining to nextCheck
  move R0,R6              ;; R0 <- lowestRemaining (= M[lowestRemainingPointer])
  load R8,[R7]            ;; R8 <- M(nextCheckPointer)
  jmpLE R8<=R0,FoundLower ;; Found a lower one, so store it
  jmp ContinueInnerLoop   ;; If we didn't find one, skip the storing part
FoundLower:
  move R5,R7        ;; lowestRemainingPointer <- nextCheckPointer;
  move R6,R8        ;; lowestRemaining <- M[nextCheckPointer];
ContinueInnerLoop:
  ;; 8.  increase nextCheckPointer and continue with InnerLoop
  addi R7,R7,R3     ;; nextCheckPointer <- nextCheckPointer + 1;
  jmp InnerLoop
ContinueOuterLoop:
  ;; 9. We found the lowestRemaining number and its pointer
  ;;    So swap M[Lo Pointer] with M[lowestRemainingPointer]
  load R9,[R1]     ;; R9 <- M[Lo Pointer]
  store R6,[R1]    ;; M[Lo Pointer] = M[lowestRemainingPointer]
  store R9,[R5]    ;; M[lowestRemainingPointer] = old M[Lo Pointer]
  ;; 10. increase Lo Pointer and continue with OuterLoop
  addi R1,R1,R3    ;; LoPointer = LoPointer + 1;
  jmp OuterLoop
Done:
  ;; 11. Halt -- we're done!
  halt

org 0xF0 ; start our data segment at memory location 20h
Data:      db      2h,77h,3h,66h,4h,55h,5h,44h,6h,33h
           db      7h,22h,8h,11h,9h
EndOfData: db      0   ; Data terminator