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

Last change on this file since 592 was 592, checked in by krille_n_, 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.