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

Last change on this file since 609 was 602, checked in by Krister Nordvall, 6 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.