home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / FSORTM.ZIP / FSORTM.ASM next >
Encoding:
Assembly Source File  |  1993-01-04  |  9.5 KB  |  282 lines
  1.     Page    80,132
  2.     Title    'FSORT - Multi-key Shell/Metzner Sort of in core array'
  3. ;
  4. ;    Preparing FSORT.BIN :
  5. ;
  6. ;        MASM FSORTM;
  7. ;        LINK FSORTM;
  8. ;        EXE2BIN FSORTM
  9. ;        DEL FSORTM.EXE
  10. ;
  11. ; Original sorting code written for SORTF version 1.7 by Vern Buerg
  12. ;
  13. ; Modified to fully relocatable code suitable for use as an external
  14. ; subprogram to a Turbo Pascal program and to support multiple
  15. ; sort keys.
  16. ;                by
  17. ;                David Gwillim
  18. ;                29 July 1985
  19. ;
  20. ;                  ******************************
  21. ;
  22. ; Turbo Pascal Usage:
  23. ;
  24. ; const
  25. ;    MAXKEYS  = (however many keys you will use) ;
  26. ;
  27. ; type
  28. ;    KeyType  = array[1..MAXKEYS] of integer ;
  29. ;
  30. ; procedure Sort(RecLen  : integer ;    {Size of each array record     }
  31. ;         NumKeys : integer ;    {Number of sort keys being used}
  32. ;         var KeyPos  : KeyType ;       {Array of sort key positions   }
  33. ;         var KeyLen  : KeyType ;    {Array of sort key lengths     }
  34. ;             RecCnt  : integer ;    {Number of records to sort     }
  35. ;                Base    : integer ) ;    {Segment address of array      }
  36. ; external 'FSORTM.BIN' ;
  37. ;
  38. ; IMPORTANT NOTE:
  39. ; This version of FSORTM is designed for use with arrays created on Turbo's
  40. ; Heap using the "New" or "GetMem" procedures. It is NOT designed to be used
  41. ; with arrays that are defined in Turbo Pascal's Data Segment, or anywhere
  42. ; where the array to be sorted cannot for sure be made to start on a paragraph
  43. ; (16 byte) boundary in the 8088/8086 address space. This is a compromise that
  44. ; permits very high speed sorting.
  45. ;
  46. ; Also the size of RecLen MUST be a multiple of 16 bytes otherwise
  47. ; unpredictable happenings will occur during the sort. The sort routine
  48. ; depends for its operation on the records being adressable with the just
  49. ; 8088 segment registers. As a result the base address of the array
  50. ; must have an offset divisible by 16, i.e. the address of the array must be
  51. ; on a paragraph (16 byte) boundary in the 8088 adress space.
  52. ; This is guaranteed by the "New" procedure in Turbo Pascal if the sort
  53. ; array is the FIRST variable allocated memory space on the heap.
  54. ; Although not covered in the Turbo Pascal Reference Manual the minimum
  55. ; allocation unit that either "New" or "GetMem" uses is 8 bytes.
  56. ;
  57. ; Therefore, byte allocations on Turbo's heap go like this:
  58. ;
  59. ;    Variable Size in bytes        Allocation in bytes
  60. ;    ----------------------          -------------------
  61. ;
  62. ;         1 -  8                 8
  63. ;         9 - 16                16
  64. ;        17 - 24                24
  65. ;        25 - 32                32
  66. ;          etc.                etc.
  67. ;
  68. ; So, the current offset of the predefined variable "HeapPtr" can be
  69. ; checked to see if it zero, and if it isn't, allocate a pointer to type
  70. ; byte before allocating for the array to be sorted. This would only be needed
  71. ; if there had been a previous use of "GetMem" and/or "New" in the program.
  72. ; It can easily done like this:
  73. ;
  74. ;    var
  75. ;       BytePtr  : ^byte ;
  76. ;
  77. ;    if Ofs(HeapPtr^) <> 0 then
  78. ;       New(BytePtr) ;
  79. ;
  80. ;                    *******************************
  81. ;
  82.  
  83. Cseg    Segment
  84.     Assume    CS:Cseg,DS:Nothing,ES:Nothing
  85.  
  86. ; Equates for passed parameters from the Turbo Pascal program
  87.  
  88. RecLen    Equ    Word Ptr [BP + 20]    ;Size of each entry (mod 16 must = 0)
  89. NumKeys    Equ    Word Ptr [BP + 18]    ;Number of keys being used in the sort
  90. SKeyPos    Equ    Word Ptr [BP + 16]    ;Segment of key offset array
  91. OKeyPos    Equ    Word Ptr [BP + 14]    ;Offset of key offset array
  92. SKeyLen    Equ    Word Ptr [BP + 12]    ;Segment of key length array
  93. OKeyLen    Equ    Word Ptr [BP + 10]    ;Offset of key length array
  94. RecCnt    Equ    Word Ptr [BP + 08]    ;Number of entries
  95. Base    Equ    Word Ptr [BP + 06]    ;Seg addr of array
  96.  
  97. ; Equates for Stack addressing
  98.  
  99. DSeg    Equ    Word Ptr [BP + 04]    ;Turbo's DSeg value
  100.  
  101. WorkArea    Equ    20        ;Allocation size for local work area
  102.  
  103. ; Equates for local work area variables
  104.  
  105. Loc    Equ    Word Ptr [BP - 02]    ;Array location record number
  106. SegLen    Equ    Word Ptr [BP - 04]    ;Paras in each entry
  107. Limit    Equ    Word Ptr [BP - 06]    ;Temporary work variables for Sort
  108. Incr    Equ    Word Ptr [BP - 08]
  109. Index1    Equ    Word Ptr [BP - 10]
  110. Index2    Equ    Word Ptr [BP - 12]
  111. Ptr1    Equ    Word Ptr [BP - 14]    ;Offset to record Index1
  112. Ptr2    Equ    Word Ptr [BP - 16]    ;Offset to record Index2
  113. CurrKey    Equ    Word Ptr [BP - 18]    ;Current key being sorted on
  114. TempOfs    Equ    Word Ptr [BP - 20]    ;Offset to sort exchange area
  115.  
  116. ; The temporary storage space for record exchanges exists in a work area
  117. ; beneath TempOfs, the size of which is determined at run-time and the offset
  118. ; to it placed in TempOfs.
  119.  
  120. CR    Equ    13
  121. LF    Equ    10
  122.  
  123. Sort    Proc    Near
  124.  
  125.     Jmp    short Start
  126.  
  127. Version    db    CR
  128.     db    'FSORT - MULTIKEY '    ;^Z at end so version number can be
  129.     db    'V 1.01',CR,LF        ; can be shown by TYPE FSORTM.BIN
  130.     db    'Copyright (C) 1985 '    ; from DOS
  131.     db    'by David Gwillim',26
  132.  
  133. Start:    Cld                ;Make sure we are incrementing indexes
  134.     Push    DS            ;Save Turbo environment
  135.     Push    BP
  136.     Mov    BP,SP            ;Make parameters on stack addressable
  137.     Mov    AX,WorkArea        ;Make space on stack for sort vars
  138.     Add    AX,RecLen        ; and sort exchange variable
  139.     Sub    SP,AX
  140.     Mov    TempOfs,SP        ;Store offset to sort exchange var
  141.  
  142.     Mov    AX,RecCnt        ;Set initial value for Loc = RecCnt
  143.     Mov    Loc,AX
  144.  
  145.     Mov    AX,RecLen        ;Calculate number of 16 byte
  146.     Mov    CL,4            ; paragraphs in each record
  147.     Shr    AX,CL
  148.     Mov    SegLen,AX
  149.  
  150. Check:    Cmp    Loc,1            ;Check if Loc <= 1
  151.     Jg    Check1            ;If not continue
  152.     Jmp    Sorted            ;If so, we're done, go clean up and
  153.                     ;  return to Turbo Pascal program
  154.  
  155. Check1:    Mov    AX,Loc            ;Calculate a new value for Loc
  156.     Sar    AX,1
  157.     Or    AX,1
  158.     Mov    Loc,AX            ;New value for Loc = 2 * (Loc/4) + 1
  159.  
  160.     Mov    AX,RecCnt        ;Calculate the new value for Limit
  161.     Sub    AX,Loc
  162.     Mov    Limit,AX        ;Update value: Limit = RecCnt - Loc
  163.  
  164.     Mov    Incr,0            ;Incr=0
  165.  
  166. Again:    Mov    CurrKey,0        ;Make sure we use first key when
  167.     Jmp    short    Cont        ; first comparing arrays
  168.  
  169. Next1:    Inc    CurrKey            ;Tie on CurrKey compare so go to next
  170.     Inc    CurrKey            ; key by indexing to next array value
  171.     Mov    BX,NumKeys        ;Allow for KeyType array (2 bytes)
  172.     Shl    BX,1            ; for each KeyPos stored
  173.     Cmp    CurrKey,BX        ;Already sorted on the final key?
  174.     Jbe    Next2            ;If so, go sort on the next key
  175.     Jmp    Again            ;No more keys, leave records where-is
  176.                     ; and go compare two other records
  177.  
  178. Cont:    Inc    Incr            ;Incr=Incr+1
  179.  
  180.     Mov    AX,Incr            ;Ensure we are still in array bounds
  181.     Cmp    AX,Limit        ;If Incr > Limit then goto Check
  182.     Jg    Check
  183.  
  184.     Mul    SegLen            ;Allow for record length
  185.     Mov    Index1,AX        ;New value for Index1 = Incr * SegLen
  186.  
  187.     Mov    Index2,AX        ;Compute new value for Index2
  188.     Mov    AX,Loc            ;for next compare
  189.     Mul    SegLen            ;Allow for record length
  190.     Add    Index2,AX        ;New value for Index2
  191.                     ; = Index1 + (Loc * SegLen)
  192.  
  193. ; Compare the record keys in Array[Index1] and Array[Index2]
  194.  
  195. Comp:    Mov    AX,Index1
  196.     Sub    AX,SegLen        ;Decrement by length of one record
  197.     Add    AX,Base            ;Compute the segment address
  198.     Mov    ES,AX            ;Segment address for Index1
  199.     Mov    Ptr1,AX            ;Update stored value for Index1
  200.  
  201.     Mov    AX,Index2        ;Decrement by length of one record
  202.     Sub    AX,SegLen        ;Compute the segment address
  203.     Add    AX,Base            ;Segment address for Index2
  204.     Mov    Ptr2,AX            ;Update stored value for Index2
  205.  
  206. ; Get the offsets, within the records, of the keys currently being compared
  207.  
  208. Next2:    Mov    DS,SKeyLen        ;Get segment address of KeyLen array
  209.     Mov    SI,OKeyLen        ;Get offset address of KeyLen array
  210.     Add    SI,CurrKey        ;Use CurrKey's length
  211.     Mov    CX,DS:[SI]        ;Get KeyLen[CurrKey+1] from Turbo
  212.  
  213.     Mov    DS,SKeyPos        ;Get segment address of KeyPos array
  214.  
  215.     Mov    DI,OKeyPos        ;Point DI to offset of KeyPos array
  216.     Add    DI,CurrKey        ;Use CurrKey's offset
  217.     Mov    DI,DS:[DI]        ;Get KeyPos[CurrKey + 1] from Turbo
  218.     Dec    DI            ;Turn key position into key offset
  219.  
  220.     Mov    SI,OKeyPos        ;Point SI to offset of KeyPos array
  221.     Add    SI,CurrKey        ;Make index to CurrKey's offset value
  222.     Mov    SI,DS:[SI]        ;Get KeyPos[CurrKey+1] from Turbo
  223.     Dec    SI            ;Turn key position into key offset
  224.  
  225.     Mov    DS,AX            ;Get the segment address for Index2
  226.     Repe    Cmpsb            ;Compare the two keys
  227.  
  228.     Ja    Again            ;The compared keys are in order
  229.     Je    Next1            ;Keys are equal so check for next key
  230.  
  231. ; Fall through if Array[Index1] < Array[Index2] - keys not in order
  232.  
  233.     Mov    CurrKey,0        ;Make sure we use first key next time
  234.  
  235. ; Keys were not in order, exchange the records Array[Index1] and Array[Index2]
  236.  
  237. Swap:    Mov    AX,SS            ;Temporary storage is located in the
  238.     Mov    ES,AX            ; Stack Segment - point to it
  239.     Mov    DI,TempOfs        ;Get offset of temp storage record
  240.     Mov    CX,Reclen        ;Get number of bytes to move
  241.  
  242.     Mov    DS,Ptr1            ;Get segment address of Array[Index1]
  243.     Sub    SI,SI            ;Ensure we at beginning of the record
  244.     Rep    Movsb            ;Move Array[Index1] to temporary
  245.                     ; storage
  246.  
  247.     Mov    ES,Ptr1            ;Get segment address of Array[Index1]
  248.     Mov    DS,Ptr2            ;Get segment address of Array[Index2]
  249.     Sub    DI,DI            ;Ensure we at beginning of the records
  250.     Sub    SI,SI
  251.     Mov    CX,Reclen        ;Get number of bytes to move
  252.     Rep    Movsb            ;Move Array[Index2] into Array[Index1]
  253.  
  254.     Mov    AX,SS            ;Temp exchange record is in stack seg
  255.     Mov    DS,AX            ;Source segment = Temp exchange record
  256.     Mov    SI,TempOfs        ;Point to Temp sort exchange space
  257.     Mov    ES,Ptr2            ;Destination segment = Ptr2
  258.     Sub    DI,DI            ;Make sure we start at beginning
  259.     Mov    CX,Reclen        ;Get number of bytes to move
  260.     Rep    Movsb            ;Move Temp to Array[Index2]'s location
  261.  
  262.     Mov    AX,Index1        ;Make Index2 = Index1
  263.     Mov    Index2,AX
  264.  
  265.     Mov    AX,Loc            ;Index1=Index1-Loc
  266.     Mul    SegLen            ;Allow for record length
  267.     Sub    Index1,AX        ;Update value for Index1
  268.  
  269.     Jg    GoComp            ;Is Index1 > 0 then
  270.     Jmp    Again            ; no, then go to Again
  271. GoComp:    Jmp    Comp            ; yes, go compare keys
  272.  
  273. Sorted:    Mov    SP,BP            ;Restore Turbo environment
  274.     Pop    BP
  275.     Pop    DS
  276.     Ret    16            ;Dump the passed parameters
  277.                     ; and return to Turbo program
  278. Sort    Endp
  279.  
  280. Cseg    Ends
  281.     End    Sort
  282.