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

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

Changes to assembly library:
Changed SetCharOutputFunctionFromAXwithAttribFlagInDL to SetCharOutputFunctionFromAXwithAttribFlagInBL since DX register gets corrupted by Display_FunctionFromDI.
Implemented quicksort.

File size: 7.5 KB
Line 
1; File name : Sort.asm
2; Project name : Assembly Library
3; Created date : 28.9.2010
4; Last update : 29.9.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 .tempStruct:
13endstruc
14
15;--------------------------------------------------------------------
16; Prototype for comparator callback function
17; Parameters:
18; DS:SI: Offset to first item to compare
19; ES:DI: Offset to second item to compare
20; Returns:
21; FLAGS: Signed comparition between first and second item
22; Corrupts registers:
23; Nothing
24;--------------------------------------------------------------------
25
26
27; Section containing code
28SECTION .text
29
30;--------------------------------------------------------------------
31; DialogFile_GetFileNameWithIoInDSSI
32; Parameters:
33; DS:SI: Ptr to FILE_DIALOG_IO
34; SS:BP: Ptr to parent MENU
35; Returns:
36; Nothing
37; Corrupts registers:
38; AX, CX, DX
39;--------------------------------------------------------------------
40ALIGN JUMP_ALIGN
41Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
42 push es
43 push di
44 add cx, BYTE QSORT_PARAMS_size
45 eENTER_STRUCT cx
46
47 cld
48 sub cx, BYTE QSORT_PARAMS_size ; Restore CX to item size
49 xor ax, ax ; Zero for starting index
50 dec dx ; Count to index of last item
51 mov [bp+QSORT_PARAMS.lpItems], si
52 mov [bp+QSORT_PARAMS.lpItems+2], ds
53 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
54
55 lds si, [bp+QSORT_PARAMS.lpItems]
56 add cx, BYTE QSORT_PARAMS_size
57 eLEAVE_STRUCT cx
58 pop di
59 pop es
60 ret
61
62
63;--------------------------------------------------------------------
64; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
65; Parameters:
66; AX: Index of first item in range
67; BX: Comparator function
68; CX: Size of struct in bytes
69; DX: Index of last (included) item in range
70; SS:BP: Ptr to QSORT_PARAMS
71; Returns:
72; Nothing
73; Corrupts registers:
74; DS, ES
75; AX, DX (not for recursion)
76;--------------------------------------------------------------------
77ALIGN JUMP_ALIGN
78QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
79 push di
80 push si
81
82 mov si, ax ; First index to SI
83 mov di, dx ; Last index to DI
84 call ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
85
86 ; Does left partition need more sorting
87 cmp si, dx ; if (first index < Index of rightmost unsorted item)
88 jae SHORT .CheckIfRightPartitionNeedsMoreSorting
89 xchg ax, si ; AX = first index, SI = Index of leftmost unsorted item
90 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
91 xchg ax, si ; AX = Index of leftmost unsorted item
92
93.CheckIfRightPartitionNeedsMoreSorting:
94 cmp ax, di ; if (Index of leftmost unsorted item < last index)
95 jae SHORT .SortCompleted
96 mov dx, di ; DI = Index of leftmost unsorted item
97 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
98
99ALIGN JUMP_ALIGN
100.SortCompleted:
101 pop si
102 pop di
103 ret
104
105
106;--------------------------------------------------------------------
107; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
108; Parameters:
109; AX: Index of first item in range
110; BX: Comparator function
111; CX: Size of struct in bytes
112; DX: Index of last (included) item in range
113; SS:BP: Ptr to QSORT_PARAMS
114; Returns:
115; AX: Index of first unsorted item
116; DX: Index of last unsorted item
117; Corrupts registers:
118; DS, ES
119;--------------------------------------------------------------------
120ALIGN JUMP_ALIGN
121ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
122 push di
123 push si
124
125 call .GetPivotPointerToESDI
126 call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
127
128 pop si
129 pop di
130 ret
131
132ALIGN JUMP_ALIGN
133.GetPivotPointerToESDI:
134 push ax
135 add ax, dx
136 shr ax, 1
137 call GetItemPointerToDSSIfromIndexInAX
138 pop ax
139 jmp Memory_ExchangeDSSIwithESDI
140
141
142;--------------------------------------------------------------------
143; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
144; Parameters:
145; AX: Index of first item in range
146; BX: Comparator function
147; CX: Size of struct in bytes
148; DX: Index of last (included) item in range
149; ES:DI: Ptr to Pivot item
150; SS:BP: Ptr to QSORT_PARAMS
151; Returns:
152; AX: Index of first unsorted item
153; DX: Index of last unsorted item
154; Corrupts registers:
155; SI, DS
156;--------------------------------------------------------------------
157ALIGN JUMP_ALIGN
158ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
159 cmp ax, dx ; while (left <= right)
160 ja SHORT .BreakLoopSinceAllItemsExamined
161
162 call GetItemPointerToDSSIfromIndexInAX
163 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
164
165 call GetItemPointerToDSSIfromIndexInDX
166 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
167
168 cmp ax, dx ; If (left <= right)
169 ja SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
170 call SwapItemsFromIndexesAXandDX
171 inc ax
172 dec dx
173 jmp SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
174
175ALIGN JUMP_ALIGN
176.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
177 call bx
178 jge SHORT .NoNeedToIncrementOrDecrementAnyMore
179 inc ax ; Increment item index
180 add si, cx ; Point to next struct
181 jmp SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
182
183ALIGN JUMP_ALIGN
184.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
185 call bx
186 jle SHORT .NoNeedToIncrementOrDecrementAnyMore
187 dec dx
188 sub si, cx
189 jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
190
191ALIGN JUMP_ALIGN
192.NoNeedToIncrementOrDecrementAnyMore:
193.BreakLoopSinceAllItemsExamined:
194 ret
195
196
197;--------------------------------------------------------------------
198; SwapItemsFromIndexesAXandDX
199; Parameters:
200; AX: Index of item 1
201; CX: Size of struct in bytes
202; DX: Index of item 2
203; SS:BP: Ptr to QSORT_PARAMS
204; Returns:
205; Nothing
206; Corrupts registers:
207; SI, DS
208;--------------------------------------------------------------------
209ALIGN JUMP_ALIGN
210SwapItemsFromIndexesAXandDX:
211 push es
212 push di
213
214 ; Item AX to stack
215 call .GetPtrToTemporaryStructToESDI
216 call GetItemPointerToDSSIfromIndexInAX
217 call .CopyItemFromDSSItoESDI
218
219 ; Item DX to Item AX
220 call Memory_ExchangeDSSIwithESDI
221 call GetItemPointerToDSSIfromIndexInDX
222 call .CopyItemFromDSSItoESDI
223
224 ; Stack to Item DX
225 call .GetPtrToTemporaryStructToESDI
226 call Memory_ExchangeDSSIwithESDI
227 call .CopyItemFromDSSItoESDI
228
229 pop di
230 pop es
231 ret
232
233ALIGN JUMP_ALIGN
234.GetPtrToTemporaryStructToESDI:
235 lea di, [bp+QSORT_PARAMS.tempStruct]
236 push ss
237 pop es
238 ret
239
240ALIGN JUMP_ALIGN
241.CopyItemFromDSSItoESDI:
242 push si
243 push cx
244
245 shr cx, 1 ; We want to copy WORDs for performance
246 jcxz .CopyLastByte
247 rep movsw
248.CopyLastByte:
249 jnc SHORT .CopyComplete
250 movsb
251.CopyComplete:
252 pop cx
253 pop si
254 ret
255
256
257;--------------------------------------------------------------------
258; GetItemPointerToDSSIfromIndexInDX
259; GetItemPointerToDSSIfromIndexInAX
260; Parameters:
261; AX or DX: Item index
262; CX: Size of struct in bytes
263; SS:BP: Ptr to QSORT_PARAMS
264; Returns:
265; DS:SI: Ptr to item
266; Corrupts registers:
267; Nothing
268;--------------------------------------------------------------------
269ALIGN JUMP_ALIGN
270GetItemPointerToDSSIfromIndexInDX:
271 xchg ax, dx
272 call GetItemPointerToDSSIfromIndexInAX
273 xchg dx, ax
274 ret
275
276ALIGN JUMP_ALIGN
277GetItemPointerToDSSIfromIndexInAX:
278 push dx
279 push ax
280
281 mul cx ; DX:AX = index (AX) * size of struct (CX)
282 lds si, [bp+QSORT_PARAMS.lpItems]
283 add si, ax
284
285 pop ax
286 pop dx
287 ret
Note: See TracBrowser for help on using the repository browser.