*************************************
*                                   *
* BitSort.asm                       *
*                                   *
* Written by Nico François          *
* Public Domain                     *
*************************************

	SECTION "bitsort",CODE

*
* This function will sort a table or array of longwords from low to high.
*
* It is very fast (6 times faster than the SAS/C quicksort function!) and
* very easy to use.
* This function is recursive, but will never use more than 800 bytes of
* stackspace!!
*
*
* C example:
*
* ULONG nums[20];
*
* main()
* {
*    ...
*    /* fill 'nums' array with numbers */
*    ...
*    /* Sort the array */
*    BitSortLongs (nums, 20);
*    ...
* }
*
*
* Assembly example:
*
*    SECTION "sort",CODE
*
* start:
*    ...                       ; fill array with numbers
*    lea    nums,a0
*    moveq  #20,d0
*    jsr    BitSortLongs(PC)   ; sort the array
*    ...
*
*    SECTION "array",DATA
*
* nums:
*    ds.l   20
*

	XDEF _BitSortLongs
	XDEF @BitSortLongs

* void BitSortLongs (ULONG *table, ULONG num);
*                    A0            D0
_BitSortLongs:             ; normal C entry point
   move.l   4(a7),a0
   move.l   8(a7),d0
@BitSortLongs:             ; __regargs entry point
BitSortLongs:              ; assembly entry point
   move.l   d2,-(a7)
   move.l   d0,d1
   move.l   a0,a1

   moveq    #0,d2
   subq.w   #1,d0
looplongest:
   cmp.l    (a0)+,d2
   bcc.b    nonewlargest
   move.l   -4(a0),d2
nonewlargest:
   dbra     d0,looplongest
   tst.l    d2
   beq.s    allsorted

   moveq    #32,d0
loopfindbit:
   subq.l   #1,d0
   btst     d0,d2
   beq.s    loopfindbit

   lsl.l    #2,d1
   move.l   a1,a0
   add.l    d1,a0
   move.l   d0,-(a7)
   move.l   a0,-(a7)
   move.l   a1,-(a7)
   bsr.b    sortbits
   lea      12(a7),a7

allsorted:
   move.l   (a7)+,d2
   rts


sortbits:
   movem.l  a0/d2,-(a7)
   move.l   12(a7),a0      ; table
   move.l   16(a7),a1      ; pointer after end of table
   move.l   20(a7),d2      ; bit number to test
   move.l   a1,d0
   subq.l   #4,d0
   cmp.l    d0,a0
   bcc.b    tablesorted
   bra.b    startfind1bit

find1bit:
   addq.l   #4,a0
startfind1bit:
   cmp.l    a1,a0
   bcc.b    allpassed
   move.l   (a0),d0
   btst     d2,d0
   beq.b    find1bit

bitis1:
   move.l   -(a1),d0
   btst     d2,d0
   beq.b    bitis0
   cmp.l    a1,a0
   bcc.b    allpassed
   bra.b    bitis1
bitis0:
   move.l   (a0),(a1)
   move.l   d0,(a0)
   bra.b    find1bit

allpassed:
   subq.l   #1,d2
   bcs.b    tablesorted

   move.l   d2,-(a7)      ; push bit number
   move.l   a0,-(a7)
   move.l   8+12(a7),-(a7)
   bsr.b    sortbits
   lea      12(a7),a7
   move.l   d2,-(a7)      ; push bit number
   move.l   4+16(a7),-(a7)
   move.l   a0,-(a7)
   bsr.b    sortbits
   lea      12(a7),a7

tablesorted:
   movem.l  (a7)+,a0/d2
   rts

   END