source: xtideuniversalbios/trunk/Assembly_Library/Src/Util/Sort.asm @ 602

Last change on this file since 602 was 602, checked in by krille_n_, 5 years ago

Changes:

  • SerDrive: Fixed a bug that prevented use of 3.5" 720 KB floppy disk images.
  • Also added support for Microsoft DMF (Distribution Media Format) floppy disk images.
  • XTIDECFG / Library: Minor size optimizations. Added a new macro (SKIP1B) as part of that.
  • BIOS: A small size optimization (2 bytes) to MODULE_8BIT_IDE_ADVANCED that is enabled only when USE_NEC_V is defined.
File size: 8.8 KB
Line 
1; Project name  :   Assembly Library
2; Description   :   Sorting algorithms
3
4;
5; XTIDE Universal BIOS and Associated Tools
6; Copyright (C) 2009-2010 by Tomi Tilli, 2011-2013 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/old-licenses/gpl-2.0.html
18;
19
20; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
21
22struc QSORT_PARAMS
23    .lpItems            resb    4
24    .tempAndPivotItems:
25endstruc
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
41SECTION .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;--------------------------------------------------------------------
55ALIGN JUMP_ALIGN
56Sort_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;--------------------------------------------------------------------
94ALIGN JUMP_ALIGN
95QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
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
116ALIGN 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;--------------------------------------------------------------------
137ALIGN JUMP_ALIGN
138ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
139    push    di
140    push    si
141
142    call    .GetPivotPointerToESDI
143    call    ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
144
145    pop     si
146    pop     di
147    ret
148
149ALIGN 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;--------------------------------------------------------------------
180ALIGN JUMP_ALIGN
181ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
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
198ALIGN 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
206ALIGN JUMP_ALIGN
207.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
208    call    bx
209    jle     SHORT .NoNeedToIncrementOrDecrementAnyMore
210    dec     dx
211    sub     si, cx
212    jmp     SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
213
214ALIGN 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;--------------------------------------------------------------------
232ALIGN JUMP_ALIGN
233SwapItemsFromIndexesAXandDX:
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;--------------------------------------------------------------------
266ALIGN JUMP_ALIGN
267GetPointerToTemporaryItemToESDI:
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;--------------------------------------------------------------------
286ALIGN JUMP_ALIGN
287GetItemPointerToDSSIfromIndexInDX:
288    xchg    ax, dx
289    call    GetItemPointerToDSSIfromIndexInAX
290    xchg    dx, ax
291    ret
292
293ALIGN JUMP_ALIGN
294GetItemPointerToDSSIfromIndexInAX:
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;--------------------------------------------------------------------
318ALIGN JUMP_ALIGN
319CopyItemFromDSSItoESDI:
320    call    Memory_CopyCXbytesFromDSSItoESDI
321    sub     si, cx          ; Restore SI
322    ret
Note: See TracBrowser for help on using the repository browser.