prog40q.asm

主要是8051源代码

;  PROG40q - Quick Sort
;
;  This Application Loads the Top 128 Scratchpad Registers with a Psuedo Random
;   Value and Then Sorts them Using a Quick Sort Algorithm.
;
;  Myke Predko
;  98.04.08
;
;  Hardware Notes:
;  DS80C320 is used as the Microcontroller
;   - This Program Only Runs in the UMPS Simulator

;  Constant Declarations
ArrayStart EQU 030h             ;  Start of the Array to Sort
ArrayEnd   EQU 0FFh
Random     EQU 0B5h             ;  181 is the Psuedo-Random Value

;  Variable Declarations


;  Macros


;  Mainline
 org 0                          ;  Execution Starts Here

  acall   Randomize             ;  Randomize the Memory

  mov     R0,#ArrayStart        ;  Setup the Locations the Sort
  mov     R1,#ArrayEnd

  acall   Sort                  ;  Sort the Values

Loop:                           ;  When Complete, Loop Forever
  ajmp    Loop


Randomize:                      ;  Randomize the Values using the Prime Addition

  mov     R0,#ArrayStart        ;  Use R0 as Index to the Address to be Written To
  mov     A,#Random             ;  "A" Contains the Random Seed

RandomLoop:                     ;  Loop Here Until the Memory Has been Randomized

  mov     @R0,A                 ;  Save the Current Value in "A"

  add     A,#Random             ;  Add the Random Value In

  inc     R0                    ;  Point to the Next Address and Loop Until Full
  cjne    R0,#LOW(ArrayEnd+1),RandomLoop

  ret


Sort:                           ;  Sort the Array Passed to the Routine

  mov     A,R1                  ;  If We Have Less Than 2, then Just Return
  clr     C
  subb    A,R0
  anl     A,#%11111110          ;  Any Bits Other Than 0 Set?
  jnz     DoSort

  mov     A,R0                  ;  Do we Have the Same Value?
  xrl     A,R1
  jz      SortShortEnd          ;  Yes, Just Skip

  mov     A,@R0                 ;  Is @R1 > @R0?
  clr     C
  subb    A,@R1
  jc      SortShortEnd          ;  Yes, Don't Change the Order

  mov     A,@R0
  xch     A,@R1
  mov     @R0,A

SortShortEnd:                   ;  End of the Short Ones

  ajmp    SortEnd               ;  Finished, Have Sorted Everything


DoSort:                         ;  Have Values to Sort

  mov     R3,#0                 ;  Get the Average Values
  mov     R4,#0

  push    0                     ;  Save the Start Location

SortLoop1:                      ;  Find the Mean of the Array

  mov     A,@R0                 ;  Get the First Value
  add     A,R3
  mov     R3,A                  ;  Add to the Average
  jnc     SortLoop1Skip         ;  If Carry, Increment the High Average
  inc     R4
SortLoop1Skip:

  inc     R0                    ;  Point to the Next Value
  mov     A,R0
  clr     C
  subb    A,R1
  dec     A
  jnz     SortLoop1             ;  Keep Getting the Average

  pop     0                     ;  Get the Number of Samples
  mov     A,R1
  clr     C
  subb    A,R0
  inc     A                     ;  "A" Has the Number of Samples

  mov     R5,#0                 ;  Use R5/R6 for the Dividend
  mov     R6,A

  push    0                     ;  Save Starting Address
  push    1                     ;  Save Ending Address

  mov     R0,#0                 ;  Use "R0" as the Divedend
  mov     R1,#8                 ;  Do for 8 Bits

SortDivLoop:                    ;  Loop Around Here to Divide the Values

  mov     A,R6                  ;  Shift The Divisor By 1
  clr     C
  rrc a
  mov     R6,A
  mov     A,R5
  rrc a
  mov     R5,A

  mov     A,R3                  ;  Is the Value Greater than the Current Value?
  clr     C
  subb    A,R5
  mov     R3,A
  mov     A,R4
  subb    A,R6
  mov     R4,A

  jnc     SortDivGreater        ;  No Carry, So It's Greater than/Equal to

  mov     A,R3                  ;  Add Back the Values
  add     A,R5
  mov     R3,A
  mov     A,R4
  addc    A,R6
  mov     R4,A

  mov     A,R0                  ;  Mark a "0" in the Dividend
  clr     C                     
  rlc a
  mov     R0,A

  ajmp    SortDivLoopEnd        ;  Have we done this 8x?  

SortDivGreater:                 ;  It is Greater than, Mark It

  mov     A,R0                  ;  Mark a "1" in the Dividend
  setb    C
  rlc a
  mov     R0,A

SortDivLoopEnd:                 ;  Are we at the End of the Loop?

  djnz    R1,SortDivLoop        ;  Do for 8 Bits

  mov     A,R0                  ;  Get the Average
  mov     B,A                   ;  Save the Average

  pop     1                     ;  Restore the Array Start
  pop     0                     ;   and End

  push    0                     ;  Save the Start and End Again for the Recursive Call
  push    1

SortLoop2:                      ;  Loop Here Until Everything Moved

SortLoop2Low:                   ;  Loop Here while R0 != R1 and @R0 < B

  mov     A,R0
  xrl     A,R1
  jz      SortLoop2End          ;  R0 == R1

  mov     A,@R0                 ;  Now Do we Have Something > or Equal?
  clr     C
  subb    A,B
  jnc     SortLoop2High         ;  Yes, Look For Something to Compare To

  inc     R0                    ;  No, Loop Around Again and Check the Next

  ajmp    SortLoop2Low

SortLoop2High:                  ;  Now, Come from the Top to Swap

  mov     A,R0
  xrl     A,R1
  jz      SortLoop2End          ;  R0 == R1

  mov     A,@R1                 ;  Now, Do we Have Something <?
  clr     C
  subb    A,B
  jc      SortLoop2Swap         ;  If Carry Set, then Swap Them

  dec     R1                    ;  Else, Point to the Next One

  ajmp    SortLoop2High

SortLoop2Swap:                  ;  Swap the Values at R0 and R1

  mov     A,@R0
  xch     A,@R1
  mov     @R0,A

  ajmp    SortLoop2             ;  After Swapping, Start Again

SortLoop2End:                   ;  Have Gone down to R0 == R1

  mov     A,R1                  ;  Save the Start Value
  pop     1                     ;  Restore the Original End Value
  mov     R0,A
  push    0                     ;  Save the Return Value

  acall   Sort                  ;  Now, Recursively Sort the Next Half

  pop     1                     ;  Get the Lower Half of the Sort
  pop     0

  mov     A,R0                  ;  Compare and See if we can Sort Lower
  xrl     A,R1
  jz      SortEnd               ;  If Both the Same, then no Can Do

  dec     R1                    ;  Go Down One For the Sort

  acall   Sort                  ;  Now, Call itself Recursively

SortEnd:                        ;  Finished, Return

  ret                           ;  The Passed Array Should be Sorted