opt     l+,o+,ow-
*
*   qsort.s version 7.6 - © Copyright 1990 Jaba Development
*
*   Author    : Jan van den Baard
*   Assembler : Devpac vesion 2.14
*
            incdir  'sys:devpac_inc/'
            include 'mymacros.i'

            xdef    SwapMem
            xdef    QuickSort

*
* QuickSort(base,num,size,compar)
*            a0   d0  d1   a1
*
QuickSort:  move.l  a1,-(sp)
            movem.l d0-d1,-(sp)
            move.l  a0,-(sp)
            bsr.s   QSort
            lea.l   16(sp),sp
            rts
*
* sort an array of elements.
* this routine is recursive it needs a lot of stack when sorting
* a large number of elements!
* the elements in the array may NOT be bigger than 64 KByte!
*
QSort:      movem.l d2-d5/a2-a3,-(sp)
            move.l  28(sp),a2               ; array base
            move.l  32(sp),d2               ; number of elements
            move.l  36(sp),d3               ; size of a element
            move.l  40(sp),a3               ; comparrison routine
            tst.l   d2                      ; sort if there are elements
            bne.s   SortIt
EndQS:      movem.l (sp)+,d2-d5/a2-a3
            rts
SortIt:     cldat   d4                      ; offset = 0
            moveq   #1,d5                   ; n = 1
            bra.s   ChkEnd                  ; check if all are done
CmpLoop:    move.l  a2,-(sp)                ; base[0] = x
            move.l  d3,d0
            mulu    d5,d0
            add.l   a2,d0
            move.l  d0,-(sp)
            jsr     (a3)                    ; cmp(base+(n*size),x);
            addq.w  #8,sp
            tst.l   d0
            bge.s   NoSwap                  ; if result >= 0 then dont swap
            inc.l   d4                      ; offset++
            move.l  d3,d1                   ; size
            move.l  a2,a0
            move.l  d3,d0
            mulu    d5,d0
            add.l   d0,a0                   ; base + (n*size)
            move.l  a2,a1
            move.l  d3,d0
            mulu    d4,d0
            add.l   d0,a1                   ; base + (offset*size)
            bsr.s   SwapMem                 ; SwapMem()
NoSwap:     inc.l   d5                      ; n++
ChkEnd:     cmp.l   d2,d5                   ; n < num ?
            bcs.s   CmpLoop                 ; if so.. loop
            move.l  d3,d1                   ; size
            move.l  a2,a0                   ; base
            move.l  a2,a1
            move.l  d3,d0
            mulu    d4,d0
            add.l   d0,a1                   ; base + (offset*size)
            bsr.s   SwapMem                 ; SwapMem()
            move.l  a3,-(sp)                ; cmp()
            move.l  d3,-(sp)                ; size
            move.l  d4,-(sp)                ; offset
            move.l  a2,-(sp)                ; base
            bsr.s   QSort                   ; QSort()
            addq.w  #8,sp
            move.l  d2,d0
            sub.l   d4,d0
            dec.l   d0
            move.l  d0,-(sp)                ; num - offset - 1
            move.l  d3,d0
            mulu    d4,d0
            add.l   d3,d0
            add.l   a2,d0
            move.l  d0,-(sp)                ; base + (offset*size) + size
            bsr.s   QSort                   ; QSort
            lea.l   16(sp),sp
            bra.s   EndQS

*
* SwapMem(mema,memb,size)
*          a0   a1   d1
* this routine does NOT swap memory chunks bigger than 64 Kbyte! (should be
* enough)
*
SwapMem:    bra.s   ChkDone
Swap:       move.b  (a0),d0                 ; byte = *area1
            move.b  (a1),(a0)+              ; *area1++ = *area2
            move.b  d0,(a1)+                ; *area2++ = byte
ChkDone:    dbra    d1,Swap                 ; loop until 'size' bytes done
            rts