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

Last change on this file since 600 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
RevLine 
[45]1; Project name : Assembly Library
2; Description : Sorting algorithms
3
[376]4;
[445]5; XTIDE Universal BIOS and Associated Tools
[526]6; Copyright (C) 2009-2010 by Tomi Tilli, 2011-2013 by XTIDE Universal BIOS Team.
[376]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.
[445]12;
[376]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
[445]16; GNU General Public License for more details.
[376]17; Visit http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
[445]18;
[376]19
[45]20; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
21
22struc QSORT_PARAMS
[46]23 .lpItems resb 4
24 .tempAndPivotItems:
[45]25endstruc
26
27;--------------------------------------------------------------------
28; Prototype for comparator callback function
29; Parameters:
[46]30; CX: Item size in bytes
31; DS:SI: Ptr to first item to compare
32; ES:DI: Ptr to second item to compare
[45]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;--------------------------------------------------------------------
[46]44; Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX
[45]45; Parameters:
[46]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
[45]50; Returns:
51; Nothing
52; Corrupts registers:
53; AX, CX, DX
54;--------------------------------------------------------------------
55ALIGN JUMP_ALIGN
56Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
57 push es
58 push di
[46]59 mov di, cx
[445]60 eSHL_IM cx, 1 ; Reserve temp and pivot items
[45]61 add cx, BYTE QSORT_PARAMS_size
62 eENTER_STRUCT cx
[46]63 push cx
[45]64
[592]65%ifdef CLD_NEEDED
[45]66 cld
[592]67%endif
[46]68 mov cx, di ; Restore item size to CX
69 xor ax, ax ; Zero starting index
[45]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]
[46]76 pop ax
77 eLEAVE_STRUCT ax
[45]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)
[46]108 jge SHORT .CheckIfRightPartitionNeedsMoreSorting
[45]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)
[46]115 jge SHORT .SortCompleted
[45]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
[46]155
[45]156 add ax, dx
[46]157 shr ax, 1 ; AX = Middle index in partition
[45]158 call GetItemPointerToDSSIfromIndexInAX
[46]159 call GetPointerToTemporaryItemToESDI
160 add di, cx ; Pivot is after temporary item
161 call CopyItemFromDSSItoESDI
162 sub di, cx ; Restore DI
163
[45]164 pop ax
[46]165 ret
[45]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)
[46]186 jg SHORT .BreakLoopSinceAllItemsExamined
[45]187
188 call GetItemPointerToDSSIfromIndexInAX
189 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
190
191 call GetItemPointerToDSSIfromIndexInDX
192 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
193
194 cmp ax, dx ; If (left <= right)
[592]195 jg SHORT .BreakLoopSinceAllItemsExamined
[45]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
[46]241 call GetPointerToTemporaryItemToESDI
[45]242 call GetItemPointerToDSSIfromIndexInAX
[46]243 call CopyItemFromDSSItoESDI
[45]244
245 ; Item DX to Item AX
[54]246 call Registers_ExchangeDSSIwithESDI
[45]247 call GetItemPointerToDSSIfromIndexInDX
[46]248 call CopyItemFromDSSItoESDI
[45]249
250 ; Stack to Item DX
[46]251 call GetPointerToTemporaryItemToESDI
[54]252 call Registers_ExchangeDSSIwithESDI
[46]253 call CopyItemFromDSSItoESDI
[45]254
255 pop di
256 pop es
257 ret
258
[46]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;--------------------------------------------------------------------
[45]269ALIGN JUMP_ALIGN
[46]270GetPointerToTemporaryItemToESDI:
271 lea di, [bp+QSORT_PARAMS.tempAndPivotItems]
[45]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
[46]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.