 Introduction to the Sort Routines		   Rev.30 Jun 91
 Sort Sel. Block Initializer    - SSBINIT			|
 Main Sort Routine              - SORT			|
 Auxiliary Sort Routines/Database - General			|
 Search Array for Record        - SEARCH			|
 Delete Specified Record        - DELETE, DELETO		|
 Insert Record in Sorted Order  - INSERT, INSERTO		|
 Append Record to End of Array  - APPEND			|
 Miscellaneous Routines -- Introduction
 BDOS and BIOS Routines         - BDOS, BIOS
 Character/Nybble Conversions   - CATH, @B2HH, @B2HL
 Command Line Tail Extraction   - CLINE
 End of Code                    - CODEND, $MEMRY
 Exchange Nybbles               - EN
 Memory Fill Routines           - FILLx, HFILx
 Memory Move Routines           - MOVEx, HMOVx
 Delay Routine                  - PAUSE
 Version Number of SYSLIB       - VERSION
:Introduction to the Sort Routines

Several routines are provided which give you access to a very	|
flexible sorting system.  The main routine is called SORT, and
it provides a utility which does an in-memory sort of a set of
fixed-length records.  The sorting technique used started with	|
a Shell Sort, adapted from the book "Software Tools" by		|
Kernighan and Plaugher (Addison-Wesly, 1976, page 106), but	|
has been much improved by Joe Wright.  This sort appears to be	|
the optimum among all advanced sorts for general use.		|

This Sort can be done in two ways: with or without using
pointers.  Sorting without using pointers is typically slower
than sorting with pointers, since entire records must be moved	|
when required, rather than 2-byte pointers.  The only advantage	|
to not using pointers is the space savings from not having the
pointer table (2*number of entries).

If a sort using pointers is selected, The records may be	|
optionally reordered in sorted order with the "SNOREC" flag.	|

  The SORT routine is controlled by passing a pointer to a
Sort Specification Block (SSB).  This Sort Specification Block
is a series of 2-byte words organized as:

  Bytes 0&1: (SFIRST) Starting Address of 1st Record
  Bytes 2&3: (SNREC)  Number of Records to Sort
  Bytes 4&5: (SSIZE)  Size of Each Record (in Bytes)
  Bytes 6&7: (SCOMP)  Address of User-Supplied Compare Routine
    This routine must compare two records, one addressed by HL
    and the other by DE.  If the record pointed to by DE is less
    in sorting order than that pointed to by HL, this Routine
    must return with Carry Set (C).  If the records are equal in
    sorting order, this Routine must return with Zero Set (Z).
    HL and DE registers must be preserved by the Routine.	|
  Bytes 8&9: (SORDER) Starting Address of the Pointer Table
  Byte  10:  (SPOINT) Non-0 means use pointers, 0 means No ptrs
  Byte  11:  (SNOREC) Ignored if SPOINT = 0, If SPOINT <> 0:	|
		0 = Reorder records after sort, FF = No reorder	|

  An initialization routine, SSBINIT, must be called if a sort	|
with pointers is selected.  It looks at an area in RAM specified|
by the initial contents of an SSB and allocates space for the	|
pointer table.  Memory Checks for Transient Program Area	|
overflow are included, and if adequate space exists, SSBINIT	|
builds a table of pointers for the subsequent sort.  This table	|
includes addresses of records which will be placed or are in the|
Record Buffer at bytes 0&1 (SFIRST).  If SFIRST is Zero, then a	|
Record Buffer is assumed to start at the end of the Order Buffer|
and that address is used to seed the pointer table, as well as	|
being returned to the User in the SSB upon successful execution.|

  When the proper initialization of SSB and SSBINIT (if pointers|
are being used) is complete, records may be sorted (SORT),	|
searched for (SEARCH), inserted (INSERT) or deleted (DELETE)	|
from the array of records.					|

:SSBINIT - SSB Initializer

  ENTER: HL = Pointer to start of Scratch RAM area
	 DE = Pointer to SSB
  EXIT :  A <> 0, Zero Flag Reset (NZ) if Ok
	    A = 0, Zero Flag Set (Z) if TPA Overflow
  USES : AF

 Usage:  This routine may be used as described above before any 
records are loaded into memory for the sort, or it may be used 
after the records have already been loaded.  If SSBINIT is	|
called with an SSB with the SFIRST word equal to zero, an Order	|
table will be established at the beginning of the scratch RAM	|
area (address in HL), and the Record Buffer will be assumed to	|
start at the end of the Order Table.  SFIRST is then filled	|
with the starting address of the Record Buffer.  If SFIRST is	|
Non-Zero, The Order Table is seeded with pointers to records	|
assumed to start at the address in SFIRST.			|

:SORT - Sort set of fixed length records

  ENTER: DE = Pointer to Sort Specification Block (SSB)
  EXIT : None   (Records are Sorted)
  USES : None

 Usage:  This routine sorts the set of fixed length records
  according to the control information in the Sort Specifica-
  tion Block (SSB) addressed by DE.  No special action is
  required, nor possible in its operation.

NOTE:  A User-defined Sort routine may be easily added using	|
 this code to perform the majority of housekeeping tasks.	|
 Simply write the routine with the name "BSORT".  Parameters	|
 as defined in the SSB description are available, as well as	|
 two 16-bit words of general-purpose use named SJJ and SGAP.	|
 Routines "ICOMPARE" and "ISWAP" are available to perform	|
 actual comparisons and swaps of Records/Pointers as defined	|
 in the SSB values.  To add your own sort, declare needed SSB	|
 values as external, BSORT as public and link before SYSLIB.	|

:      Auxiliary Sort Routines / Database 			|

  These new functions allow us to treat a sorted array as a	|
database.  Having sorted a particular list, we can now manipu-	|
late it and search it on various keys.  We can delete a given	|
record and, if we have organized the Records and Order table	|
such that there is space, we can 'insert' a record into the	|
database. These functions are controlled by the SSB in the same	|
way the SORT is.  The following descriptions of Records,	|
Pointers and Indices require a certain attention to semantics.	|

  A Record is usually a fixed-length data structure with one or	|
or more fields which identify it and/or hold data pertaining to	|
it.  For example, the first sixteen bytes of a CP/M directory	|
entry contains four fields identifying the user number, file-	|
name, filetype and file size information.  One or more of these	|
records placed contiguously in memory is called a Record List.	|

       Auxiliary Sort Routines (Contd..) 


  Assuming we want to report this List in some order, we might	|
sort the List itself according to one or more of its fields.	|
This process requires exchanging entire records (16 bytes each)	|
and result in a Record List ordered for one particular case.	|

  A much more efficient method is to create an Order Table of	|
Pointers to each Record in the List.  We can now perform the	|
sort exchanging 2-byte Pointers with considerable time savings	|
and use the new Order Table to report the Record List.		|

  An Index is an integer from 1 to N (the number of Records)	|
to logically address a Pointer or Record.  Indices are used by	|
the sort algorithms (BSORT and others) to generalize their	|
operations on either Order Table or Record List.		|


       Auxiliary Sort Routines (Contd..) 

  Although not previously discussed, a Record may have more	|
than one key on which to search.  A symbol table, for example,	|
has two fields, value and name, which can be used as keys.	|
Given a set of unordered symbols, we can create two Order	|
Tables, one according to value and the other according to name.	|
We can now search the set (Record List) for either value or name|
depending on which Order Table (and compare routine) we select.	|

  Two routines, INSRTO and DELETO, are provided to maintain	|
the second (or third..) Order Table.  Called immediately after	|
INSERT or DELETE (which treat one Order Table), they will insert|
or delete the appropriate pointer of the next Order Table.	|

:SEARCH - Return the relative number for a record		|

  ENTER: HL = Pointer to a prototype record for key match
	 DE = Pointer to SSB for data array
  EXIT : Found:
	   AF - Zero Set (Z)
	   HL = Index (1..N) of matched record
	 Not Found:
	   AF - Zero Clear (NZ)
	   DE = Index (1..N+1) where search failed
  USES : AF,BC,DE,HL

 Usage: This routine is used to locate a record in a sorted	|
array of fixed-length records.  The search is a very fast Log N	|
binary search.  Given a list of 500 records, a linear search	|
averages 250 compares to find a record and always performs 500	|
compares if the record is not found.  The binary search		|
requires no more than Log2 * 500 (9) compares.			|

:DELETE - Delete record at specified Record Index		|
DELETO - Delete a pointer from a pointer to a record		|

  ENTER: HL = Index (1..N) of record to be deleted		|
	 DE = Pointer to SSB for data array			|
  EXIT : None.  Record and pointer (if used) are removed	|
  USES : AF,BC,DE,HL						|

 Usage:  This routine is used to remove a record from the	|
Record List (and its pointer from the Order Table).		|


:INSERT - Add a record to the array in sorted position	|
INSRTO - Add pointer to a pointer to a record			|

  ENTER: HL = Pointer to record to be inserted			|
	 DE = Pointer to SSB for data array			|
  EXIT : None.  The record and pointer (if used) are placed in	|
		proper sorted locations in the array/table	|
  USES : AF,BC,DE,HL						|

 Usage: This routine is used to place a record at the proper	|
position in the Record List (and its pointer in the Order Table)|

:APPEND  - Add a record at the end of the array		|

  ENTER: HL = Pointer to record to be added			|
	 DE = Pointer to SSB for data array			|
  EXIT : None.  The record and pointer (if used) are placed at	|
		the end of the array/pointer table		|
  USES : AF,BC,DE,HL						|

 Usage: This routine is used to add a record to an array when	|
it is not necessary to maintain the records in sorted order.	|
The new record will be added at the end of the Record List (and	|
its pointer to the end of the Order List).			|
NOTE: APPEND is much faster than INSERT but does NOT maintain	|
the order of the Record List or the Order Table.  After a	|
series of APPEND calls the array should be brought into order	|
with a call to SORT.						|

:	 Miscellaneous Routines -- Introduction 

  The following Routines are described in this Section:
	BDOS	    For Direct BDOS Interface
	BIOS	    For Direct BIOS Interface
	CAPS	    For Character Capitalization
	CAPSTR      For String Capitalization
	CATH	    Convert ASCII Character to Hexadecimal
	@B2HH,@B2HL Convert High and Low Nybbles of byte to Hex
	CLINE       Command Line Extraction
	CODEND      Provide End of Code/Data Area
	EN	    Exchange Nybbles in A
	FILLB       Fill Memory (up to 255 bytes)
	FILLBC      Fill Memory (up to 65,535 bytes)
	HFILB       Fill Memory (up to 255 bytes)
	HFILBC      Fill Memory (up to 65,535 bytes)
	MOVEB       Move Memory (up to 255 bytes)
	MOVEBC      Move Memory (up to 65,535 bytes)
	HMOVB       Move Memory (up to 255 bytes)
	HMOVBC      Move Memory (up to 65,535 bytes)
	PAUSE       Delay N 10th of a Second
	VERSION     Return Version Number of SYSLIB
:BDOS - Call a BDOS Function

  ENTER: DE = Arguments (if needed for function)
	  C = BDOS Function Number
  EXIT :  A = Return Status/Parameter (if returned)
	 HL = Return Parameter (if returned)
  USES : AF,HL

 Usage:  This routine provides a way of calling the BDOS while
  preserving the BC and DE registers.  This is often of benefit
  when dealing with FCB addresses in DE and/or loop counters in
  the B register.

BIOS - Call a BIOS Function directly

  ENTER:  A = Offset to BIOS Function Entry in Jump Table
	 BC = Function Parameters (if needed)
  EXIT :  A,BC - Return Parameters (if returned)
  USES : AF,BC,DE,HL

 Usage:  This routine is most often used to provide very fast
  response where BDOS overhead cannot be tolerated.  This
  routine provides you with a direct interface into the CP/M
  BIOS.  It is called with an index offset into the BIOS jump
  tale.  No registers are preserved by this routine.

  The following table summarizes the BIOS Jump Table Entries:

 Offset   Function
    0	Cold Start
    1	Warm Boot
    2	Console Status; Returns A=0FFH if char ready, A=0 if not
    3	Console Input; Returns char in A
    4	Console Output; Char passed in C

    5	List Output; Char passed in C
    6	Punch Output; Char passed in C
    7	Reader Input; Returns char in A
    8	Home Disk Head
    9	Select Disk; Disk Number (A=0, etc) passed in C
   10	Set Track Number; Track Number passed in C
   11	Set Sector Number; Sector Number passed in C
   12	Set DMA Address; DMA Address passed in BC
   13	Read Block from Disk; Returns A=0 if OK, A=1 if Error
   14	Write Block to Disk; Returns A=0 if OK, A=1 if Error
   15	List Status; Returns A=0FFH if ready, A=0 if not
   16	Sector Translation, Logical-to-Physical; Logical Sector
		Number passed in BC, Translate Table Address in
		DE; Returns Physical Sector Number in HL

:CATH - Convert ASCII to Hexadecimal

  ENTER:  A = ASCII Hex Character ("0"-"9", "A"-"F")
  EXIT :  A = Binary value represented by Char
  USES : AF
  Special Error Conditions: If invalid Hex character is passed,
	a Space (20 Hex) is returned in A.

 Uses:  This utility routine is often useful in numeric
  conversion and entry routines.  It simply converts the ASCII
  Hexadecimal character provided to its Binary representation.

@B2HH - Convert High Nybble of byte to Hex digit
 @B2HL - Convert Low Nybble of byte to Hex digit

  ENTER:  A = Data byte to convert
  EXIT :  A = Hex character (0..9,A..F) for specified nybble
  USES : AF.  All other registers not affected

 Usage:  These routines are used to perform conversions from
  binary nybbles to Hexidecimal ASCII characters.

Example:
	EXT	@B2HH,@B2HL
	...		; Enter with byte in A
	PUSH	AF	; Save the byte
	CALL	@B2HH	; Call the routine
	...		; do something with high nybble
	POP	AF	; restore original byte
	CALL	@B2HL	; Now have Hex char of low nybble
	...		; do something with it

:CLINE - Command Line Tail Extraction

  ENTER: HL = Address of Command Line Buffer (Char Count)
  EXIT : HL = Address of Command Line String (1st Char)
	  A <> 0, Zero Flag Clear (NZ) if Buffer OK
	    A = 0, Zero Flag Set (Z) if Buffer Truncated
  USES : AF,HL

 Usage:  This routine is used to free the default buffer at 80H
  by copying the contents to a local buffer.  The preserved
  copy may then be parsed or evaluated at a later time.  The
  line may be up to 255 characters long and will be truncated
  if longer.  The string will be terminated by a <NULL> as per 
  the SYSLIB concept of strings.

:CODEND - End of Code

  ENTER: None
  EXIT : HL = Address of Page above last byte used in Program
  USES : HL

 Usage:  This routine is most often used to determine the base
  address of free memory for use in Sorting, Directory Listing
  and other programs.  Scratch memory extends from the value
  returned by CODEND to the base of the CCP or BDOS.


     Buffer Name:  $MEMRY

$MEMRY contains the address of the next available byte of
memory after the last module loaded and resolved by MicroSoft's 
LINK-80 linker, SLR Systems' SLRNK or Mitek's ZLINK.  This
reserved global variable should be accessed as:

	...
	EXT	$MEMRY
	...
	LD	HL,($MEMRY)	; get value
	...

    Contents:  Address of next available byte

:EN - Exchange Nybbles

  ENTER:  A = Byte to manipulate
  EXIT :  A = Manipulated Byte
  USES : AF

 Usage:  This routine simply exchanges the Nybbles in the A
  Register; High-order four bits are exchanged with Low-order
  four bits.

:FILLB, FILLBC, HFILB, HFILBC - Memory Fill Routines

  ENTER: HL = Pointer to first byte of Memory area to fill
	 BC (FILLBC and HFILBC) = Number of Bytes to fill
	  B (FILLB and HFILB)   = Number of Bytes to fill
	  A = Value to store in Buffer
  EXIT : HL (HFILB and HFILBC only) = Pter to byte after last
  USES : HL (HFILB and HFILBC only)

 Usage:  These routines are used to fill an area of memory with
  a constant byte value.  FILLB can fill up to a 256-byte
  buffer, and FILLBC can fill up to a 65,536-byte (within
  reason) buffer.

  FILLB and FILLBC have no effects on any registers.  HFILB and
  HFILBC both affect the HL register pair, and they return with
  HL pointing to the byte after the last byte filled.  HFILB
  and HFILBC are useful when further processing from the last
  point filled is desired.

:MOVEB, MOVEBC, HMOVB, HMOVBC - Memory Move Routines

  ENTER: HL = Pointer to first byte of Source Buffer
	 DE = Pointer to first byte of Destination Buffer
	 BC (MOVEBC & HMOVBC) = Number of Bytes to move
	  B (MOVEB & HMOVB)   = Number of Bytes to move
  EXIT : HL (HMOVB & HMOVBC) = Ptr to byte after last Source
	 DE (HMOVB & HMOVBC) = Ptr to byte after last Dest.
  USES : HL,DE (HMOVB & HMOVBC only)

 Usage:  These routines are used to move the block of memory
  specified by the Source address to the specified destination
  memory location.  MOVEB can move up to a 256-byte buffer, and
  MOVEBC can move up to a 65,536-byte buffer.

  MOVEB and MOVEBC have no effects on any registers.  HMOVB and
  HMOVBC both affect the HL register pair, and they return with
  HL and DE pointing to the byte after the last byte moved.
  HMOVB and  HMOVBC are useful when further processing from the
  last point filled is desired.

:PAUSE - Delay Routine

  ENTER: HL = Number of 10ths of a Second Delay desired
	  B = Processor Speed in MHz (1,2,3,...)
  EXIT : None
  USES : None

 Usage:  This routine is simply used to delay from one to 65,536
  tenths of a second.  Calculations are approximate and depend
  on accuracy on clock specification and number of clock cycles
  per opcode in the delay code. (i.e. the Z180/64180 execute in
  fewer clock cycles than the Z80)

:VERSION - Version Number of SYSLIB0				|
 VERS1   - Version Number of SYSLIB1				|

  ENTER: None
  EXIT : HL = Version (H=Major, L=Minor.  H=4, L=3 for 4.3)
  USES : HL

 Usage:  This routine simply returns the library version, and
  Identification text string.  The Text ID string, containing	|
  any bug-fixing revision (e.g. 4.3c) may be found by getting	|
  the address of the null-terminated string starting four bytes	|
  after the label address.  The following code fragment will	|
  print the ID string contained in SYSLIB1:			|

	LD	HL,VERS1	; Get the label address		|
	LD	DE,4		; .offset to string start	|
	ADD	HL,DE		; HL now pts to string start	|
	CALL	PSTR		; Send it to the Console	|
