* ============================================================= *
*  Thomas C. Penick   ID# 452 80 6040              Program   5  *
*  EE319K Microprocessor Programming               due 3/27/98  *
*  Instructor: Laurence                            Section   B  *
*  MC6811 Program Source Code  PA5.asm             Roster#  32  *
*  Writing a Selection Sort subroutine for bubble.asm           *
* ============================================================= *

	org  0
Size: rmb  2
Data: rmb  100
Time: rmb  2
Addr: rmb  2            (SelSort) address of Data
Swap: rmb  2            (SelSort) holding area for comparison
Ctrs: rmb  1            (SelSort) counters j and i, if using reg D
Ctrb: rmb  1            (SelSort) counter i only
Ssze: rmb  1            (SelSort) storage for "Size"
	org  $E000
; main() { int i;
;        i -> 2,x
main:
	lds  #$00FF       load stack pointer
	ldx  #WelcomeMsg  get address of message
	jsr  OutString    display the message
	pshx              local counter \ allocate 4 bytes on stack
	pshx              local "size"  / 
	tsx               save stack pointer to X
;    for (Size=3;Size<=8;Size++) {
	ldd  #3           \
	std  Size         / Size = 3
L2:
	ldd  Size         \
	cpd  #8            > terminate the program if "Size" > 8
	bhi  L4           /
	jsr  OutDec       \
	ldaa #SPACE        > otherwise display "Size" & a space on screen
	jsr  OutCh        /
bubble.10:     ;      for(i=0;i<Size;i++) Data[i]=Size-i;  /* Reverse order */
	clra              \
	clrb               >store 0's in local counter
	std  2,x          /
L6:
	ldd  2,x          retrieve data from local counter
	cpd  Size         \ branch if counter >= "Size"
	bhs  L8           /
	ldd  #Data        \
	pshb               > load D with #Data and push to stack
	psha              /
	ldd  2,x          \ load D with local counter and multiply by 2
	lsld              /
	tsy               save stack pointer to Y
	addd 0,y          \
	puly               > add 2xCounter to address of Data and store in Y,
	xgdy              /  and deallocate 2 bytes
	ldd  Size         \
	subd 2,x           > subtract counter from size and store result in
	std  0,y          /  local size variable
L7:
	ldd  2,x          \
	addd #1            >increment the local counter
	std  2,x          /
	bra  L6           loop to L6:
L8:
bubble.11:     ;      Time=TCNT;
	ldd  4110         \ store cycle count at label "Time"
	std  Time         /
bubble.12:     ;      Bubble(Data,Size);
	ldd  Size         \ store "Size" in local size variable
	std  0,x          /
	ldd  #Data        load D with the address of "Data"

***  Call the SelSort Subroutine  *******************************
	jsr  SelSort      call the sort subroutine

bubble.13:     ;      Time=TCNT-Time-12;
	ldd  4110         load the current clock cycle into D
	subd Time         D minus previously stored clock cycle
	subd #12          D minus previously stored clock cycle minus 12
	std  Time         store the accumulated total of clock cycles in D
	jsr  OutDec       \
	ldaa #13           > display total cycles + carriage return to screen
	jsr  OutCh        /
L3:
	ldd  Size         \
	addd #1            > increment "Size"
	std  Size         /
	tsx               save the stack pointer to X
	bra  L2           loop to L2:
L4:
	pulx              \
	pulx              / deallocate 4 bytes on stack
	ldx  #DoneMsg     \
	jsr  OutString    / display message
	stop              stop the program
	jmp  main         start the program over
L1:

***  The SelSort Subroutine  **************************************
*                                                                 *
*  Inputs: size of array in 2 bytes on stack                      *
*          address of the data in register D                      *
*  Outputs: items in Data array are resorted                      *
*  Limitations: 127 elements to be sorted                         *
*  Destroyed: CCR, Registers D, X, Y                              *
*                                                                 *
*******************************************************************
SelSort:
; size is at 2,x (2 bytes)
      std  Addr         store the address of Data        [4 cycles]
	tsx               store stack pointer in X         [3 cycles]
      ldaa 3,x          \                                [4 cycles]
      deca               > store Size - 1                [2 cycles]
      staa Ssze         /                                [3 cycles]16

; for (int i = 0; i < size - 1; i++)
      ldd  #256         \ init. counters, A=1(j) B=0(i)  [3 cycles]
      std  Ctrs         /                                [4 cycles]07
Loop1:
      cmpb Ssze         compare "i" to size              [4 cycles]
      bhs  EndLoop1     we're done                       [3 cycles]07
; for (j = i + 1'; j < size; j++)
Loop2:
      cmpa Ssze         compare "j" to size              [4 cycles]
      bhi  EndLoop2                                      [3 cycles]
; if (x[i] > x[j]) Then exchange
      ldx  Addr         load the address of Data         [4 cycles]
      lsld              2x counters for 2-byte words     [3 cycles]
      abx               add counter i to address of Data [4 cycles]
                        ; now X points to x[i]
      ldy  0,x          load the value x[i] in Y         [6 cycles]
      sba               store j-i into A                 [2 cycles]
      tab               \                                [2 cycles]
      abx               / add j-i to address of x[i]     [4 cycles]
                        ; now X points to x[j]
      cpy  0,x          compare x[i] to x[j]             [7 cycles]
      bls  EndSwap      do nothing if lower or same      [3 cycles]42
BeginSwap:              ; Perform the Swap
      sty  Swap         store x[i] in "Swap"             [5 cycles]
      ldy  Addr         load the address of Data         [5 cycles]
      ldab Ctrb         load the (offset) i counter      [3 cycles]
      lslb              2x counter i for 2-byte words    [2 cycles]
      aby               add the i offset to Y            [4 cycles]
                        ; now Y points to x[i]
      ldd  0,x          load the value (x[j]) in D       [5 cycles]
      std  0,y          store x[j] in new location       [6 cycles]
      ldd  Swap         load the value x[i] in D         [4 cycles]
      std  0,x          store x[i] in new location       [5 cycles]37
EndSwap:
      ldd  Ctrs         reload counters                  [4 cycles]
      inca              increment counter j              [2 cycles]
      staa Ctrs         store updated counter j          [3 cycles]
      bra  Loop2        loop                             [3 cycles]12
EndLoop2:
      ldab Ctrb         reload counter i                 [3 cycles]
      incb              increment counter i              [2 cycles]
      tba               \  j = i + 1                     [2 cycles]
      inca              /                                [2 cycles]
      std  Ctrs         store updated counters           [4 cycles]
      bra  Loop1        loop                             [3 cycles]16
EndLoop1:
	rts
***  End SelSort Subroutine  **************************************

WelcomeMsg fcc \EE319K Selection Sort\
	fcb  CR
	fcc  \Written by Tom Penick\
	fcb  CR
	fcc  \Size  Speed in cycles\
	fcb  CR,EOT
DoneMsg fcc  \ Completed   \
	fcb  CR,EOT
	org  $FFFE
	fdb  main
