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

Last change on this file since 576 was 526, checked in by krille_n_@…, 12 years ago

Changes:

  • Update of the copyright notices to include the year 2013.
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 cld
66 mov cx, di ; Restore item size to CX
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 di
77 pop es
78 ret
79
80
81;--------------------------------------------------------------------
82; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
83; Parameters:
84; AX: Index of first item in range
85; BX: Comparator function
86; CX: Size of struct in bytes
87; DX: Index of last (included) item in range
88; SS:BP: Ptr to QSORT_PARAMS
89; Returns:
90; Nothing
91; Corrupts registers:
92; DS, ES
93; AX, DX (not for recursion)
94;--------------------------------------------------------------------
95ALIGN JUMP_ALIGN
96QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
97 push di
98 push si
99
100 mov si, ax ; First index to SI
101 mov di, dx ; Last index to DI
102 call ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
103
104 ; Does left partition need more sorting
105 cmp si, dx ; if (first index < Index of rightmost unsorted item)
106 jge SHORT .CheckIfRightPartitionNeedsMoreSorting
107 xchg ax, si ; AX = first index, SI = Index of leftmost unsorted item
108 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
109 xchg ax, si ; AX = Index of leftmost unsorted item
110
111.CheckIfRightPartitionNeedsMoreSorting:
112 cmp ax, di ; if (Index of leftmost unsorted item < last index)
113 jge SHORT .SortCompleted
114 mov dx, di ; DI = Index of leftmost unsorted item
115 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
116
117ALIGN JUMP_ALIGN
118.SortCompleted:
119 pop si
120 pop di
121 ret
122
123
124;--------------------------------------------------------------------
125; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
126; Parameters:
127; AX: Index of first item in range
128; BX: Comparator function
129; CX: Size of struct in bytes
130; DX: Index of last (included) item in range
131; SS:BP: Ptr to QSORT_PARAMS
132; Returns:
133; AX: Index of first unsorted item
134; DX: Index of last unsorted item
135; Corrupts registers:
136; DS, ES
137;--------------------------------------------------------------------
138ALIGN JUMP_ALIGN
139ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
140 push di
141 push si
142
143 call .GetPivotPointerToESDI
144 call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
145
146 pop si
147 pop di
148 ret
149
150ALIGN JUMP_ALIGN
151.GetPivotPointerToESDI:
152 push ax
153
154 add ax, dx
155 shr ax, 1 ; AX = Middle index in partition
156 call GetItemPointerToDSSIfromIndexInAX
157 call GetPointerToTemporaryItemToESDI
158 add di, cx ; Pivot is after temporary item
159 call CopyItemFromDSSItoESDI
160 sub di, cx ; Restore DI
161
162 pop ax
163 ret
164
165
166;--------------------------------------------------------------------
167; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
168; Parameters:
169; AX: Index of first item in range
170; BX: Comparator function
171; CX: Size of struct in bytes
172; DX: Index of last (included) item in range
173; ES:DI: Ptr to Pivot item
174; SS:BP: Ptr to QSORT_PARAMS
175; Returns:
176; AX: Index of first unsorted item
177; DX: Index of last unsorted item
178; Corrupts registers:
179; SI, DS
180;--------------------------------------------------------------------
181ALIGN JUMP_ALIGN
182ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
183 cmp ax, dx ; while (left <= right)
184 jg SHORT .BreakLoopSinceAllItemsExamined
185
186 call GetItemPointerToDSSIfromIndexInAX
187 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
188
189 call GetItemPointerToDSSIfromIndexInDX
190 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
191
192 cmp ax, dx ; If (left <= right)
193 jg SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
194 call SwapItemsFromIndexesAXandDX
195 inc ax
196 dec dx
197 jmp SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
198
199ALIGN JUMP_ALIGN
200.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
201 call bx
202 jge SHORT .NoNeedToIncrementOrDecrementAnyMore
203 inc ax ; Increment item index
204 add si, cx ; Point to next struct
205 jmp SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
206
207ALIGN JUMP_ALIGN
208.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
209 call bx
210 jle SHORT .NoNeedToIncrementOrDecrementAnyMore
211 dec dx
212 sub si, cx
213 jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
214
215ALIGN JUMP_ALIGN
216.NoNeedToIncrementOrDecrementAnyMore:
217.BreakLoopSinceAllItemsExamined:
218 ret
219
220
221;--------------------------------------------------------------------
222; SwapItemsFromIndexesAXandDX
223; Parameters:
224; AX: Index of item 1
225; CX: Size of struct in bytes
226; DX: Index of item 2
227; SS:BP: Ptr to QSORT_PARAMS
228; Returns:
229; Nothing
230; Corrupts registers:
231; SI, DS
232;--------------------------------------------------------------------
233ALIGN JUMP_ALIGN
234SwapItemsFromIndexesAXandDX:
235 push es
236 push di
237
238 ; Item AX to stack
239 call GetPointerToTemporaryItemToESDI
240 call GetItemPointerToDSSIfromIndexInAX
241 call CopyItemFromDSSItoESDI
242
243 ; Item DX to Item AX
244 call Registers_ExchangeDSSIwithESDI
245 call GetItemPointerToDSSIfromIndexInDX
246 call CopyItemFromDSSItoESDI
247
248 ; Stack to Item DX
249 call GetPointerToTemporaryItemToESDI
250 call Registers_ExchangeDSSIwithESDI
251 call CopyItemFromDSSItoESDI
252
253 pop di
254 pop es
255 ret
256
257
258;--------------------------------------------------------------------
259; GetPointerToTemporaryItemToESDI
260; Parameters:
261; SS:BP: Ptr to QSORT_PARAMS
262; Returns:
263; ES:DI: Ptr to temporary item
264; Corrupts registers:
265; Nothing
266;--------------------------------------------------------------------
267ALIGN JUMP_ALIGN
268GetPointerToTemporaryItemToESDI:
269 lea di, [bp+QSORT_PARAMS.tempAndPivotItems]
270 push ss
271 pop es
272 ret
273
274
275;--------------------------------------------------------------------
276; GetItemPointerToDSSIfromIndexInDX
277; GetItemPointerToDSSIfromIndexInAX
278; Parameters:
279; AX or DX: Item index
280; CX: Size of struct in bytes
281; SS:BP: Ptr to QSORT_PARAMS
282; Returns:
283; DS:SI: Ptr to item
284; Corrupts registers:
285; Nothing
286;--------------------------------------------------------------------
287ALIGN JUMP_ALIGN
288GetItemPointerToDSSIfromIndexInDX:
289 xchg ax, dx
290 call GetItemPointerToDSSIfromIndexInAX
291 xchg dx, ax
292 ret
293
294ALIGN JUMP_ALIGN
295GetItemPointerToDSSIfromIndexInAX:
296 push dx
297 push ax
298
299 mul cx ; DX:AX = index (AX) * size of struct (CX)
300 lds si, [bp+QSORT_PARAMS.lpItems]
301 add si, ax
302
303 pop ax
304 pop dx
305 ret
306
307
308;--------------------------------------------------------------------
309; CopyItemFromDSSItoESDI
310; Parameters:
311; CX: Item size in bytes
312; DS:SI: Ptr to source item
313; ES:DI: Ptr to destination buffer
314; Returns:
315; Nothing
316; Corrupts registers:
317; DI
318;--------------------------------------------------------------------
319ALIGN JUMP_ALIGN
320CopyItemFromDSSItoESDI:
321 call Memory_CopyCXbytesFromDSSItoESDI
322 sub si, cx ; Restore SI
323 ret
Note: See TracBrowser for help on using the repository browser.