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

Last change on this file since 244 was 54, checked in by Tomi Tilli, 14 years ago

Changes to Assembly Library:
Drive selection moved to own dialog from File Dialog.
File Dialog now displays loading text for better usability in slow systems.
Moved some functions from Memory.asm to new Registers.asm.
File size: 8.3 KB
Line 
1; File name : Sort.asm
2; Project name : Assembly Library
3; Created date : 28.9.2010
4; Last update : 24.10.2010
5; Author : Tomi Tilli
6; Description : Sorting algorithms
7
8; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
9
10struc QSORT_PARAMS
11 .lpItems resb 4
12 .tempAndPivotItems:
13endstruc
14
15;--------------------------------------------------------------------
16; Prototype for comparator callback function
17; Parameters:
18; CX: Item size in bytes
19; DS:SI: Ptr to first item to compare
20; ES:DI: Ptr to second item to compare
21; Returns:
22; FLAGS: Signed comparition between first and second item
23; Corrupts registers:
24; Nothing
25;--------------------------------------------------------------------
26
27
28; Section containing code
29SECTION .text
30
31;--------------------------------------------------------------------
32; Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX
33; Parameters:
34; CX: Item size in bytes
35; DX: Number of items to sort (signed)
36; CS:BX: Comparator function
37; DS:SI: Ptr to array of items to sort
38; Returns:
39; Nothing
40; Corrupts registers:
41; AX, CX, DX
42;--------------------------------------------------------------------
43ALIGN JUMP_ALIGN
44Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
45 push es
46 push di
47 mov di, cx
48 shl cx, 1 ; Reserve temp and pivot items
49 add cx, BYTE QSORT_PARAMS_size
50 eENTER_STRUCT cx
51 push cx
52
53 cld
54 mov cx, di ; Restore item size to CX
55 xor ax, ax ; Zero starting index
56 dec dx ; Count to index of last item
57 mov [bp+QSORT_PARAMS.lpItems], si
58 mov [bp+QSORT_PARAMS.lpItems+2], ds
59 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
60
61 lds si, [bp+QSORT_PARAMS.lpItems]
62 pop ax
63 eLEAVE_STRUCT ax
64 pop di
65 pop es
66 ret
67
68
69;--------------------------------------------------------------------
70; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
71; Parameters:
72; AX: Index of first item in range
73; BX: Comparator function
74; CX: Size of struct in bytes
75; DX: Index of last (included) item in range
76; SS:BP: Ptr to QSORT_PARAMS
77; Returns:
78; Nothing
79; Corrupts registers:
80; DS, ES
81; AX, DX (not for recursion)
82;--------------------------------------------------------------------
83ALIGN JUMP_ALIGN
84QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
85 push di
86 push si
87
88 mov si, ax ; First index to SI
89 mov di, dx ; Last index to DI
90 call ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
91
92 ; Does left partition need more sorting
93 cmp si, dx ; if (first index < Index of rightmost unsorted item)
94 jge SHORT .CheckIfRightPartitionNeedsMoreSorting
95 xchg ax, si ; AX = first index, SI = Index of leftmost unsorted item
96 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
97 xchg ax, si ; AX = Index of leftmost unsorted item
98
99.CheckIfRightPartitionNeedsMoreSorting:
100 cmp ax, di ; if (Index of leftmost unsorted item < last index)
101 jge SHORT .SortCompleted
102 mov dx, di ; DI = Index of leftmost unsorted item
103 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
104
105ALIGN JUMP_ALIGN
106.SortCompleted:
107 pop si
108 pop di
109 ret
110
111
112;--------------------------------------------------------------------
113; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
114; Parameters:
115; AX: Index of first item in range
116; BX: Comparator function
117; CX: Size of struct in bytes
118; DX: Index of last (included) item in range
119; SS:BP: Ptr to QSORT_PARAMS
120; Returns:
121; AX: Index of first unsorted item
122; DX: Index of last unsorted item
123; Corrupts registers:
124; DS, ES
125;--------------------------------------------------------------------
126ALIGN JUMP_ALIGN
127ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
128 push di
129 push si
130
131 call .GetPivotPointerToESDI
132 call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
133
134 pop si
135 pop di
136 ret
137
138ALIGN JUMP_ALIGN
139.GetPivotPointerToESDI:
140 push ax
141
142 add ax, dx
143 shr ax, 1 ; AX = Middle index in partition
144 call GetItemPointerToDSSIfromIndexInAX
145 call GetPointerToTemporaryItemToESDI
146 add di, cx ; Pivot is after temporary item
147 call CopyItemFromDSSItoESDI
148 sub di, cx ; Restore DI
149
150 pop ax
151 ret
152
153
154;--------------------------------------------------------------------
155; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
156; Parameters:
157; AX: Index of first item in range
158; BX: Comparator function
159; CX: Size of struct in bytes
160; DX: Index of last (included) item in range
161; ES:DI: Ptr to Pivot item
162; SS:BP: Ptr to QSORT_PARAMS
163; Returns:
164; AX: Index of first unsorted item
165; DX: Index of last unsorted item
166; Corrupts registers:
167; SI, DS
168;--------------------------------------------------------------------
169ALIGN JUMP_ALIGN
170ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
171 cmp ax, dx ; while (left <= right)
172 jg SHORT .BreakLoopSinceAllItemsExamined
173
174 call GetItemPointerToDSSIfromIndexInAX
175 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
176
177 call GetItemPointerToDSSIfromIndexInDX
178 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
179
180 cmp ax, dx ; If (left <= right)
181 jg SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
182 call SwapItemsFromIndexesAXandDX
183 inc ax
184 dec dx
185 jmp SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
186
187ALIGN JUMP_ALIGN
188.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
189 call bx
190 jge SHORT .NoNeedToIncrementOrDecrementAnyMore
191 inc ax ; Increment item index
192 add si, cx ; Point to next struct
193 jmp SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
194
195ALIGN JUMP_ALIGN
196.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
197 call bx
198 jle SHORT .NoNeedToIncrementOrDecrementAnyMore
199 dec dx
200 sub si, cx
201 jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
202
203ALIGN JUMP_ALIGN
204.NoNeedToIncrementOrDecrementAnyMore:
205.BreakLoopSinceAllItemsExamined:
206 ret
207
208
209;--------------------------------------------------------------------
210; SwapItemsFromIndexesAXandDX
211; Parameters:
212; AX: Index of item 1
213; CX: Size of struct in bytes
214; DX: Index of item 2
215; SS:BP: Ptr to QSORT_PARAMS
216; Returns:
217; Nothing
218; Corrupts registers:
219; SI, DS
220;--------------------------------------------------------------------
221ALIGN JUMP_ALIGN
222SwapItemsFromIndexesAXandDX:
223 push es
224 push di
225
226 ; Item AX to stack
227 call GetPointerToTemporaryItemToESDI
228 call GetItemPointerToDSSIfromIndexInAX
229 call CopyItemFromDSSItoESDI
230
231 ; Item DX to Item AX
232 call Registers_ExchangeDSSIwithESDI
233 call GetItemPointerToDSSIfromIndexInDX
234 call CopyItemFromDSSItoESDI
235
236 ; Stack to Item DX
237 call GetPointerToTemporaryItemToESDI
238 call Registers_ExchangeDSSIwithESDI
239 call CopyItemFromDSSItoESDI
240
241 pop di
242 pop es
243 ret
244
245
246;--------------------------------------------------------------------
247; GetPointerToTemporaryItemToESDI
248; Parameters:
249; SS:BP: Ptr to QSORT_PARAMS
250; Returns:
251; ES:DI: Ptr to temporary item
252; Corrupts registers:
253; Nothing
254;--------------------------------------------------------------------
255ALIGN JUMP_ALIGN
256GetPointerToTemporaryItemToESDI:
257 lea di, [bp+QSORT_PARAMS.tempAndPivotItems]
258 push ss
259 pop es
260 ret
261
262
263;--------------------------------------------------------------------
264; GetItemPointerToDSSIfromIndexInDX
265; GetItemPointerToDSSIfromIndexInAX
266; Parameters:
267; AX or DX: Item index
268; CX: Size of struct in bytes
269; SS:BP: Ptr to QSORT_PARAMS
270; Returns:
271; DS:SI: Ptr to item
272; Corrupts registers:
273; Nothing
274;--------------------------------------------------------------------
275ALIGN JUMP_ALIGN
276GetItemPointerToDSSIfromIndexInDX:
277 xchg ax, dx
278 call GetItemPointerToDSSIfromIndexInAX
279 xchg dx, ax
280 ret
281
282ALIGN JUMP_ALIGN
283GetItemPointerToDSSIfromIndexInAX:
284 push dx
285 push ax
286
287 mul cx ; DX:AX = index (AX) * size of struct (CX)
288 lds si, [bp+QSORT_PARAMS.lpItems]
289 add si, ax
290
291 pop ax
292 pop dx
293 ret
294
295
296;--------------------------------------------------------------------
297; CopyItemFromDSSItoESDI
298; Parameters:
299; CX: Item size in bytes
300; DS:SI: Ptr to source item
301; ES:DI: Ptr to destination buffer
302; Returns:
303; Nothing
304; Corrupts registers:
305; DI
306;--------------------------------------------------------------------
307ALIGN JUMP_ALIGN
308CopyItemFromDSSItoESDI:
309 call Memory_CopyCXbytesFromDSSItoESDI
310 sub si, cx ; Restore SI
311 ret
Note: See TracBrowser for help on using the repository browser.