1  ; Project name : Assembly Library


2  ; Description : Sorting algorithms


3 


4  ;


5  ; XTIDE Universal BIOS and Associated Tools


6  ; Copyright (C) 20092010 by Tomi Tilli, 20112013 by XTIDE Universal BIOS Team.


7  ;


8  ; This program is free software; you can redistribute it and/or modify


9  ; it under the terms of the GNU General Public License as published by


10  ; the Free Software Foundation; either version 2 of the License, or


11  ; (at your option) any later version.


12  ;


13  ; This program is distributed in the hope that it will be useful,


14  ; but WITHOUT ANY WARRANTY; without even the implied warranty of


15  ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


16  ; GNU General Public License for more details.


17  ; Visit http://www.gnu.org/licenses/oldlicenses/gpl2.0.html


18  ;


19 


20  ; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort


21 


22  struc QSORT_PARAMS


23  .lpItems resb 4


24  .tempAndPivotItems:


25  endstruc


26 


27  ;


28  ; Prototype for comparator callback function


29  ; Parameters:


30  ; CX: Item size in bytes


31  ; DS:SI: Ptr to first item to compare


32  ; ES:DI: Ptr to second item to compare


33  ; Returns:


34  ; FLAGS: Signed comparison between first and second item


35  ; Corrupts registers:


36  ; Nothing


37  ;


38 


39 


40  ; Section containing code


41  SECTION .text


42 


43  ;


44  ; Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX


45  ; Parameters:


46  ; CX: Item size in bytes


47  ; DX: Number of items to sort (signed)


48  ; CS:BX: Comparator function


49  ; DS:SI: Ptr to array of items to sort


50  ; Returns:


51  ; Nothing


52  ; Corrupts registers:


53  ; AX, CX, DX


54  ;


55  ALIGN JUMP_ALIGN


56  Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:


57  push es


58  mov ax, cx


59  eSHL_IM ax, 1 ; Reserve temp and pivot items


60  add ax, BYTE QSORT_PARAMS_size


61  eENTER_STRUCT ax


62  push ax


63 


64  %ifdef CLD_NEEDED


65  cld


66  %endif


67  xor ax, ax ; Zero starting index


68  dec dx ; Count to index of last item


69  mov [bp+QSORT_PARAMS.lpItems], si


70  mov [bp+QSORT_PARAMS.lpItems+2], ds


71  call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP


72 


73  lds si, [bp+QSORT_PARAMS.lpItems]


74  pop ax


75  eLEAVE_STRUCT ax


76  pop es


77  ret


78 


79 


80  ;


81  ; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP


82  ; Parameters:


83  ; AX: Index of first item in range


84  ; BX: Comparator function


85  ; CX: Size of struct in bytes


86  ; DX: Index of last (included) item in range


87  ; SS:BP: Ptr to QSORT_PARAMS


88  ; Returns:


89  ; Nothing


90  ; Corrupts registers:


91  ; DS, ES


92  ; AX, DX (not for recursion)


93  ;


94  ALIGN JUMP_ALIGN


95  QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:


96  push di


97  push si


98 


99  mov si, ax ; First index to SI


100  mov di, dx ; Last index to DI


101  call ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot


102 


103  ; Does left partition need more sorting


104  cmp si, dx ; if (first index < Index of rightmost unsorted item)


105  jge SHORT .CheckIfRightPartitionNeedsMoreSorting


106  xchg ax, si ; AX = first index, SI = Index of leftmost unsorted item


107  call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP


108  xchg ax, si ; AX = Index of leftmost unsorted item


109 


110  .CheckIfRightPartitionNeedsMoreSorting:


111  cmp ax, di ; if (Index of leftmost unsorted item < last index)


112  jge SHORT .SortCompleted


113  mov dx, di ; DI = Index of leftmost unsorted item


114  call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP


115 


116  ALIGN JUMP_ALIGN


117  .SortCompleted:


118  pop si


119  pop di


120  ret


121 


122 


123  ;


124  ; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot


125  ; Parameters:


126  ; AX: Index of first item in range


127  ; BX: Comparator function


128  ; CX: Size of struct in bytes


129  ; DX: Index of last (included) item in range


130  ; SS:BP: Ptr to QSORT_PARAMS


131  ; Returns:


132  ; AX: Index of first unsorted item


133  ; DX: Index of last unsorted item


134  ; Corrupts registers:


135  ; DS, ES


136  ;


137  ALIGN JUMP_ALIGN


138  ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:


139  push di


140  push si


141 


142  call .GetPivotPointerToESDI


143  call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI


144 


145  pop si


146  pop di


147  ret


148 


149  ALIGN JUMP_ALIGN


150  .GetPivotPointerToESDI:


151  push ax


152 


153  add ax, dx


154  shr ax, 1 ; AX = Middle index in partition


155  call GetItemPointerToDSSIfromIndexInAX


156  call GetPointerToTemporaryItemToESDI


157  add di, cx ; Pivot is after temporary item


158  call CopyItemFromDSSItoESDI


159  sub di, cx ; Restore DI


160 


161  pop ax


162  ret


163 


164 


165  ;


166  ; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI


167  ; Parameters:


168  ; AX: Index of first item in range


169  ; BX: Comparator function


170  ; CX: Size of struct in bytes


171  ; DX: Index of last (included) item in range


172  ; ES:DI: Ptr to Pivot item


173  ; SS:BP: Ptr to QSORT_PARAMS


174  ; Returns:


175  ; AX: Index of first unsorted item


176  ; DX: Index of last unsorted item


177  ; Corrupts registers:


178  ; SI, DS


179  ;


180  ALIGN JUMP_ALIGN


181  ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:


182  cmp ax, dx ; while (left <= right)


183  jg SHORT .BreakLoopSinceAllItemsExamined


184 


185  call GetItemPointerToDSSIfromIndexInAX


186  call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI


187 


188  call GetItemPointerToDSSIfromIndexInDX


189  call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI


190 


191  cmp ax, dx ; If (left <= right)


192  jg SHORT .BreakLoopSinceAllItemsExamined


193  call SwapItemsFromIndexesAXandDX


194  inc ax


195  dec dx


196  jmp SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI


197 


198  ALIGN JUMP_ALIGN


199  .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:


200  call bx


201  jge SHORT .NoNeedToIncrementOrDecrementAnyMore


202  inc ax ; Increment item index


203  add si, cx ; Point to next struct


204  jmp SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI


205 


206  ALIGN JUMP_ALIGN


207  .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:


208  call bx


209  jle SHORT .NoNeedToIncrementOrDecrementAnyMore


210  dec dx


211  sub si, cx


212  jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI


213 


214  ALIGN JUMP_ALIGN


215  .NoNeedToIncrementOrDecrementAnyMore:


216  .BreakLoopSinceAllItemsExamined:


217  ret


218 


219 


220  ;


221  ; SwapItemsFromIndexesAXandDX


222  ; Parameters:


223  ; AX: Index of item 1


224  ; CX: Size of struct in bytes


225  ; DX: Index of item 2


226  ; SS:BP: Ptr to QSORT_PARAMS


227  ; Returns:


228  ; Nothing


229  ; Corrupts registers:


230  ; SI, DS


231  ;


232  ALIGN JUMP_ALIGN


233  SwapItemsFromIndexesAXandDX:


234  push es


235  push di


236 


237  ; Item AX to stack


238  call GetPointerToTemporaryItemToESDI


239  call GetItemPointerToDSSIfromIndexInAX


240  call CopyItemFromDSSItoESDI


241 


242  ; Item DX to Item AX


243  call Registers_ExchangeDSSIwithESDI


244  call GetItemPointerToDSSIfromIndexInDX


245  call CopyItemFromDSSItoESDI


246 


247  ; Stack to Item DX


248  call GetPointerToTemporaryItemToESDI


249  call Registers_ExchangeDSSIwithESDI


250  call CopyItemFromDSSItoESDI


251 


252  pop di


253  pop es


254  ret


255 


256 


257  ;


258  ; GetPointerToTemporaryItemToESDI


259  ; Parameters:


260  ; SS:BP: Ptr to QSORT_PARAMS


261  ; Returns:


262  ; ES:DI: Ptr to temporary item


263  ; Corrupts registers:


264  ; Nothing


265  ;


266  ALIGN JUMP_ALIGN


267  GetPointerToTemporaryItemToESDI:


268  lea di, [bp+QSORT_PARAMS.tempAndPivotItems]


269  push ss


270  pop es


271  ret


272 


273 


274  ;


275  ; GetItemPointerToDSSIfromIndexInDX


276  ; GetItemPointerToDSSIfromIndexInAX


277  ; Parameters:


278  ; AX or DX: Item index


279  ; CX: Size of struct in bytes


280  ; SS:BP: Ptr to QSORT_PARAMS


281  ; Returns:


282  ; DS:SI: Ptr to item


283  ; Corrupts registers:


284  ; Nothing


285  ;


286  ALIGN JUMP_ALIGN


287  GetItemPointerToDSSIfromIndexInDX:


288  xchg ax, dx


289  call GetItemPointerToDSSIfromIndexInAX


290  xchg dx, ax


291  ret


292 


293  ALIGN JUMP_ALIGN


294  GetItemPointerToDSSIfromIndexInAX:


295  push dx


296  push ax


297 


298  mul cx ; DX:AX = index (AX) * size of struct (CX)


299  lds si, [bp+QSORT_PARAMS.lpItems]


300  add si, ax


301 


302  pop ax


303  pop dx


304  ret


305 


306 


307  ;


308  ; CopyItemFromDSSItoESDI


309  ; Parameters:


310  ; CX: Item size in bytes


311  ; DS:SI: Ptr to source item


312  ; ES:DI: Ptr to destination buffer


313  ; Returns:


314  ; Nothing


315  ; Corrupts registers:


316  ; DI


317  ;


318  ALIGN JUMP_ALIGN


319  CopyItemFromDSSItoESDI:


320  call Memory_CopyCXbytesFromDSSItoESDI


321  sub si, cx ; Restore SI


322  ret

