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

Last change on this file since 598 was 592, checked in by Krister Nordvall, 6 years ago

Changes:

  • The problem with NASM in the previous revision (r591) has been fixed.
  • The colors used by the boot menu and hotkey bar can now be customized by selecting one of a number of pre-defined color themes. Suggestions for additional themes are more than welcome!
  • Large builds are now 10 KB. Small builds are still 8 KB with the exception of the Tiny build which is now 4 KB. In other words, builds are now as small as possible to make it easier to combine them with other BIOSes.
  • Added code to the library to improve drive error handling. XTIDECFG can now handle "Drive Not Ready" errors.
  • Fixed a couple of potential bugs in AtaID.asm (AtaID_GetMaxPioModeToAXandMinCycleTimeToCX); 1) ATA1.bPioMode was treated as a WORD variable. 2) ATA2.bPIOSupp was assumed to be non-zero which would result in PIO mode 3 being returned if the assumption was wrong.
  • Made the same changes in the equivalent function used by BIOSDRVS (DisplayPioModeInformationUsingAtaInfoFromDSBX in AtaInfo.asm).
  • Fixed a bug from r587 in PDC20x30.asm in PDC20x30_GetMaxPioModeToALandMinPioCycleTimeToBX.
  • Fixed a bug from r523 in XTIDECFG where Auto Configure would only set the IRQ on one IDE interface on AT-builds.
  • XTIDECFG will now restore the default settings for the "Serial port virtual device" when reselecting it in the list of device types. This makes it behave consistently for all device types.
  • The eAAM macro is now used regardless if USE_UNDOC_INTEL is defined or not because it is apparently supported on all processors including the NEC V20/V30 CPUs.
  • Renamed the EXCLUDE_FROM_XTIDE_UNIVERSAL_BIOS define to EXCLUDE_FROM_XUB.
  • Added a define to exclude unused library code from BIOSDRVS (EXCLUDE_FROM_BIOSDRVS). This makes it a lot smaller than in previous revisions.
  • All unnecessary CLD-instructions are now under a new define 'CLD_NEEDED' which is only enabled for the BIOS. It is disabled for XTIDECFG and BIOSDRVS but can be enabled if needed by adding this define to the respective makefile. This change was made because these unnecessary instructions are wasteful and should never be needed. In fact, they only serve to hide bugs (in other peoples code) which I strongly believe should be avoided. I recommend people making their own BIOSes from source to not use this define as it's extremely unlikely to be needed.
  • Updated the copyright info in SerDrive and changed an URL to point to the new site.
  • Updated the copyright info and version number in BIOSDRVS.
  • Updated the copyright info in XTIDECFG.
  • Optimizations in general.
File size: 8.9 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 comparition 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 push di
59 mov di, cx
60 eSHL_IM cx, 1 ; Reserve temp and pivot items
61 add cx, BYTE QSORT_PARAMS_size
62 eENTER_STRUCT cx
63 push cx
64
65%ifdef CLD_NEEDED
66 cld
67%endif
68 mov cx, di ; Restore item size to CX
69 xor ax, ax ; Zero starting index
70 dec dx ; Count to index of last item
71 mov [bp+QSORT_PARAMS.lpItems], si
72 mov [bp+QSORT_PARAMS.lpItems+2], ds
73 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
74
75 lds si, [bp+QSORT_PARAMS.lpItems]
76 pop ax
77 eLEAVE_STRUCT ax
78 pop di
79 pop es
80 ret
81
82
83;--------------------------------------------------------------------
84; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
85; Parameters:
86; AX: Index of first item in range
87; BX: Comparator function
88; CX: Size of struct in bytes
89; DX: Index of last (included) item in range
90; SS:BP: Ptr to QSORT_PARAMS
91; Returns:
92; Nothing
93; Corrupts registers:
94; DS, ES
95; AX, DX (not for recursion)
96;--------------------------------------------------------------------
97ALIGN JUMP_ALIGN
98QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
99 push di
100 push si
101
102 mov si, ax ; First index to SI
103 mov di, dx ; Last index to DI
104 call ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
105
106 ; Does left partition need more sorting
107 cmp si, dx ; if (first index < Index of rightmost unsorted item)
108 jge SHORT .CheckIfRightPartitionNeedsMoreSorting
109 xchg ax, si ; AX = first index, SI = Index of leftmost unsorted item
110 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
111 xchg ax, si ; AX = Index of leftmost unsorted item
112
113.CheckIfRightPartitionNeedsMoreSorting:
114 cmp ax, di ; if (Index of leftmost unsorted item < last index)
115 jge SHORT .SortCompleted
116 mov dx, di ; DI = Index of leftmost unsorted item
117 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
118
119ALIGN JUMP_ALIGN
120.SortCompleted:
121 pop si
122 pop di
123 ret
124
125
126;--------------------------------------------------------------------
127; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
128; Parameters:
129; AX: Index of first item in range
130; BX: Comparator function
131; CX: Size of struct in bytes
132; DX: Index of last (included) item in range
133; SS:BP: Ptr to QSORT_PARAMS
134; Returns:
135; AX: Index of first unsorted item
136; DX: Index of last unsorted item
137; Corrupts registers:
138; DS, ES
139;--------------------------------------------------------------------
140ALIGN JUMP_ALIGN
141ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
142 push di
143 push si
144
145 call .GetPivotPointerToESDI
146 call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
147
148 pop si
149 pop di
150 ret
151
152ALIGN JUMP_ALIGN
153.GetPivotPointerToESDI:
154 push ax
155
156 add ax, dx
157 shr ax, 1 ; AX = Middle index in partition
158 call GetItemPointerToDSSIfromIndexInAX
159 call GetPointerToTemporaryItemToESDI
160 add di, cx ; Pivot is after temporary item
161 call CopyItemFromDSSItoESDI
162 sub di, cx ; Restore DI
163
164 pop ax
165 ret
166
167
168;--------------------------------------------------------------------
169; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
170; Parameters:
171; AX: Index of first item in range
172; BX: Comparator function
173; CX: Size of struct in bytes
174; DX: Index of last (included) item in range
175; ES:DI: Ptr to Pivot item
176; SS:BP: Ptr to QSORT_PARAMS
177; Returns:
178; AX: Index of first unsorted item
179; DX: Index of last unsorted item
180; Corrupts registers:
181; SI, DS
182;--------------------------------------------------------------------
183ALIGN JUMP_ALIGN
184ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
185 cmp ax, dx ; while (left <= right)
186 jg SHORT .BreakLoopSinceAllItemsExamined
187
188 call GetItemPointerToDSSIfromIndexInAX
189 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
190
191 call GetItemPointerToDSSIfromIndexInDX
192 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
193
194 cmp ax, dx ; If (left <= right)
195 jg SHORT .BreakLoopSinceAllItemsExamined
196 call SwapItemsFromIndexesAXandDX
197 inc ax
198 dec dx
199 jmp SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
200
201ALIGN JUMP_ALIGN
202.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
203 call bx
204 jge SHORT .NoNeedToIncrementOrDecrementAnyMore
205 inc ax ; Increment item index
206 add si, cx ; Point to next struct
207 jmp SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
208
209ALIGN JUMP_ALIGN
210.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
211 call bx
212 jle SHORT .NoNeedToIncrementOrDecrementAnyMore
213 dec dx
214 sub si, cx
215 jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
216
217ALIGN JUMP_ALIGN
218.NoNeedToIncrementOrDecrementAnyMore:
219.BreakLoopSinceAllItemsExamined:
220 ret
221
222
223;--------------------------------------------------------------------
224; SwapItemsFromIndexesAXandDX
225; Parameters:
226; AX: Index of item 1
227; CX: Size of struct in bytes
228; DX: Index of item 2
229; SS:BP: Ptr to QSORT_PARAMS
230; Returns:
231; Nothing
232; Corrupts registers:
233; SI, DS
234;--------------------------------------------------------------------
235ALIGN JUMP_ALIGN
236SwapItemsFromIndexesAXandDX:
237 push es
238 push di
239
240 ; Item AX to stack
241 call GetPointerToTemporaryItemToESDI
242 call GetItemPointerToDSSIfromIndexInAX
243 call CopyItemFromDSSItoESDI
244
245 ; Item DX to Item AX
246 call Registers_ExchangeDSSIwithESDI
247 call GetItemPointerToDSSIfromIndexInDX
248 call CopyItemFromDSSItoESDI
249
250 ; Stack to Item DX
251 call GetPointerToTemporaryItemToESDI
252 call Registers_ExchangeDSSIwithESDI
253 call CopyItemFromDSSItoESDI
254
255 pop di
256 pop es
257 ret
258
259
260;--------------------------------------------------------------------
261; GetPointerToTemporaryItemToESDI
262; Parameters:
263; SS:BP: Ptr to QSORT_PARAMS
264; Returns:
265; ES:DI: Ptr to temporary item
266; Corrupts registers:
267; Nothing
268;--------------------------------------------------------------------
269ALIGN JUMP_ALIGN
270GetPointerToTemporaryItemToESDI:
271 lea di, [bp+QSORT_PARAMS.tempAndPivotItems]
272 push ss
273 pop es
274 ret
275
276
277;--------------------------------------------------------------------
278; GetItemPointerToDSSIfromIndexInDX
279; GetItemPointerToDSSIfromIndexInAX
280; Parameters:
281; AX or DX: Item index
282; CX: Size of struct in bytes
283; SS:BP: Ptr to QSORT_PARAMS
284; Returns:
285; DS:SI: Ptr to item
286; Corrupts registers:
287; Nothing
288;--------------------------------------------------------------------
289ALIGN JUMP_ALIGN
290GetItemPointerToDSSIfromIndexInDX:
291 xchg ax, dx
292 call GetItemPointerToDSSIfromIndexInAX
293 xchg dx, ax
294 ret
295
296ALIGN JUMP_ALIGN
297GetItemPointerToDSSIfromIndexInAX:
298 push dx
299 push ax
300
301 mul cx ; DX:AX = index (AX) * size of struct (CX)
302 lds si, [bp+QSORT_PARAMS.lpItems]
303 add si, ax
304
305 pop ax
306 pop dx
307 ret
308
309
310;--------------------------------------------------------------------
311; CopyItemFromDSSItoESDI
312; Parameters:
313; CX: Item size in bytes
314; DS:SI: Ptr to source item
315; ES:DI: Ptr to destination buffer
316; Returns:
317; Nothing
318; Corrupts registers:
319; DI
320;--------------------------------------------------------------------
321ALIGN JUMP_ALIGN
322CopyItemFromDSSItoESDI:
323 call Memory_CopyCXbytesFromDSSItoESDI
324 sub si, cx ; Restore SI
325 ret
Note: See TracBrowser for help on using the repository browser.