home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / PROGRAM / ASM / ALIB30B / SORT24.ASM < prev    next >
Assembly Source File  |  1994-11-11  |  5KB  |  200 lines
  1. ;***************************** SORT24.ASM ***********************************
  2.  
  3. LIBSEG           segment byte public "LIB"
  4.         assume cs:LIBSEG , ds:nothing
  5. ;----------------------------------------------------------------------------
  6. .xlist
  7.     include  mac.inc
  8.     extrn    dos_mem_allocate:far
  9.     extrn    dos_mem_release:far
  10. .list
  11. comment 
  12. ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(  SORT   )
  13. ; merge_sort_arrayd - sort array of dwords.
  14. ;  inputs:  ds:0 - ptr to dword array
  15. ;              cx - number of elements in array
  16. ;
  17. ;  Output:  if no carry array is sorted in decending order
  18. ;           carry = insufficient memory
  19. ;           
  20. ;  Note:  merge_sort_arrayw uses 316 bytes for code and allocates
  21. ;         memory to hold array being sorted.
  22. ;****************************
  23. 
  24. work_seg        dw    0    ;temp index sort area
  25. sort_buffer_seg        dw    0
  26. delta            dw    0
  27. no_sort_flag        db    0    ;set =1 if no sort in merge pass
  28. sorted_flag        db    0    ;set =1 if index already sorted
  29.  
  30.     public    merge_sort_arrayd              
  31. merge_sort_arrayd    proc    far
  32.     apush    ax,bx,cx,dx,si,di,bp,ds,es
  33.     cld
  34.     cmp    cx,1
  35.     jbe    sort_exit        ;jmp if not enough data to sort
  36.     shl    cx,1
  37.     shl    cx,1
  38.     mov    bp,cx            ;bp=sort buffer length (bytes)
  39.     mov    cs:sort_buffer_seg,ds
  40.     mov    cs:sorted_flag,1    ;preload already sorted flag
  41. ;
  42. ; allocate work area
  43. ;
  44.     mov    dx,0
  45.     mov    ax,bp
  46.     call    dos_mem_allocate
  47.     jc    sort_exit3
  48.     mov    cs:work_seg,es
  49.     mov    cs:delta,4
  50.  
  51.         mov    di,cs:delta        ;setup list2 start
  52. lp1:    mov    bx,0            ;setup store ptr for 'merge' routine
  53.     mov    si,0                     ;set si at top of buffer
  54.     
  55. lp2:    call    merge
  56.     mov    cl,cs:no_sort_flag    ;get 1 if no sort occured
  57.     and    cs:sorted_flag,cl    ;keep 1 in sorted_flag if block sorted
  58.     add    si,cs:delta
  59.     add    di,cs:delta
  60.     cmp    si,bp            ;bp=sort buffer length
  61.     jb    lp2            ;jmp if more data to sort
  62. ;
  63. ; move the temp index back to origional
  64. ;    
  65. ms_4:    cmp    cs:sorted_flag,1
  66.     je    ms_done            ;jmp if no sort needed
  67.  
  68.     mov    di,cs:delta
  69.     shl    di,1
  70.     mov    cs:delta,di
  71.     cmp    di,bp            ;check if delta > buffer length
  72.     jae    ms_done
  73. ;
  74.     mov    ax,ds            ;swap
  75.     mov    cx,es            ;  buffer
  76.     mov    ds,cx            ;    pointers
  77.     mov    es,ax            ;       ds & es
  78.     jmp    lp1
  79.  
  80. ms_done:
  81.     mov    ax,ds
  82.     cmp    ax,cs:sort_buffer_seg    ;check if good data in work seg
  83.     jne    sort_exit2        ;jmp if sort data in sort_buffer
  84.         
  85.     mov    cx,bp            ;bp=sort_buffer_length
  86.     shr    cx,1            ;length
  87.     mov    di,0            ;destination
  88.     mov    si,0            ;source
  89.     mov    es,cs:sort_buffer_seg
  90.     mov    ds,cs:work_seg
  91.     rep    movsw            ;move work index -> origional index
  92. sort_exit2:    
  93.     mov    es,cs:work_seg
  94.     call    dos_mem_release    
  95. sort_exit:
  96.     clc
  97. sort_exit3:
  98.     apop    es,ds,bp,di,si,dx,cx,bx,ax
  99.     retf
  100. merge_sort_arrayd    endp
  101.  
  102. ;--------------------------------------------------------------------
  103. ; MERGE - combine two sorted lists
  104. ;   inputs:  ds:si = list1 index top
  105. ;            ds:di = list2 index top, (may be short list)
  106. ;          cs:delta = length of each list
  107. ;            es:bx = active storage pointer of work area
  108. ;               bp = sort buffer length (byte count)
  109. ;
  110. ;  output: si,di updated to end of field
  111. ;
  112. starting_list2_len    dw    0
  113.  
  114. merge:    mov    cs:no_sort_flag,0    ;preload data unsorted state
  115.     mov    cx,cs:delta        ;get list1 length
  116.     mov    dx,cx            ;set list2 length
  117. ;
  118. ; check length of list2
  119. ;    
  120.     mov    ax,dx            ;get list2 length
  121.     add    ax,di            ;compute last location
  122.     sub    ax,bp            ;ax = list2 length adjustment
  123.     jb    mer_cont2        ;jmp if length ok
  124.     sub    ax,cx
  125.     jbe    mer_cont1        ;jmp if only list2 needs adjusting
  126.     mov    dx,0            ;list2 is zero length
  127. ;
  128. ; adjust list1 length
  129. ;
  130.     sub    cx,ax
  131.     jmp    mer_cont2
  132. ;
  133. ; adjust list2 length
  134. ;
  135. mer_cont1:    
  136.     add    ax,cx
  137.     sub    dx,ax            ;adjust list2 length
  138. mer_cont2:
  139.     mov    cs:starting_list2_len,dx
  140. ;
  141. ;             bp=sort buffer length    ds:si=list1 ptr  cx=list1 length  
  142. ; ax=scratch  es:bx=store ptr          ds:di=list2 ptr  dx=list2 length
  143. ;
  144. m_lp:    cmp    cx,0
  145.     je    sort2_only        ;jmp if list1 length=0
  146.     cmp    dx,0
  147.     je    move1            ;jmp if list2 length=0
  148. ;
  149. ; both lists have valid records, do compare
  150. ;
  151.     mov    ax,word ptr ds:[si+2]
  152.     cmp    ax,word ptr ds:[di+2]
  153.     ja    move2            ;jmp if list2 data smaller
  154.     jb    move1
  155.     mov    ax,word ptr ds:[si]
  156.     cmp    ax,word ptr ds:[di]
  157.     ja    move2    
  158.     jmp    move1            ;jmp if list1 data smaller    
  159. ;
  160. ; list1 is empty, check list2
  161. ;
  162. sort2_only:
  163.     cmp    dx,0            ;check if list2 has data
  164.     je    merge_done1        ;jmp if end of both lists
  165. ;
  166. ; check if no sort was needed for list1, (everything already sorted)
  167. ;
  168.     cmp    dx,cs:starting_list2_len ;has list2 data been merged
  169.     jne    sort2_cont        ;jmp if merge occured
  170.     mov    cs:no_sort_flag,1    ;set no sort this pass flag
  171. sort2_cont:    
  172. ;
  173. ; list2 has data move it
  174. ;
  175. move2:    mov    ax,word ptr ds:[di]    ;get list2 data
  176.     mov    word ptr es:[bx],ax
  177.     mov    ax,word ptr ds:[di+2]
  178.     mov    word ptr es:[bx+2],ax
  179.     add    di,4
  180.     sub    dx,4            ;list2 length - 2
  181.     jmp    move_tail
  182. ;
  183. ; list1 has data move it
  184. ;
  185. move1:    lodsw
  186.     mov    word ptr es:[bx],ax
  187.     lodsw
  188.     mov    word ptr es:[bx+2],ax
  189.     sub    cx,4            ;list1 length - 2
  190. move_tail:
  191.     add    bx,4
  192.     jmp    m_lp
  193. ;
  194. merge_done1:
  195.     ret
  196.  
  197. ;
  198. LIBSEG    ENDS
  199.     end
  200.