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

Last change on this file since 61 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
RevLine 
[45]1; File name : Sort.asm
2; Project name : Assembly Library
3; Created date : 28.9.2010
[54]4; Last update : 24.10.2010
[45]5; Author : Tomi Tilli
6; Description : Sorting algorithms
7
8; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
9
10struc QSORT_PARAMS
[46]11 .lpItems resb 4
12 .tempAndPivotItems:
[45]13endstruc
14
15;--------------------------------------------------------------------
16; Prototype for comparator callback function
17; Parameters:
[46]18; CX: Item size in bytes
19; DS:SI: Ptr to first item to compare
20; ES:DI: Ptr to second item to compare
[45]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;--------------------------------------------------------------------
[46]32; Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX
[45]33; Parameters:
[46]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
[45]38; Returns:
39; Nothing
40; Corrupts registers:
41; AX, CX, DX
42;--------------------------------------------------------------------
43ALIGN JUMP_ALIGN
44Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
45 push es
46 push di
[46]47 mov di, cx
48 shl cx, 1 ; Reserve temp and pivot items
[45]49 add cx, BYTE QSORT_PARAMS_size
50 eENTER_STRUCT cx
[46]51 push cx
[45]52
53 cld
[46]54 mov cx, di ; Restore item size to CX
55 xor ax, ax ; Zero starting index
[45]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]
[46]62 pop ax
63 eLEAVE_STRUCT ax
[45]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)
[46]94 jge SHORT .CheckIfRightPartitionNeedsMoreSorting
[45]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)
[46]101 jge SHORT .SortCompleted
[45]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
[46]141
[45]142 add ax, dx
[46]143 shr ax, 1 ; AX = Middle index in partition
[45]144 call GetItemPointerToDSSIfromIndexInAX
[46]145 call GetPointerToTemporaryItemToESDI
146 add di, cx ; Pivot is after temporary item
147 call CopyItemFromDSSItoESDI
148 sub di, cx ; Restore DI
149
[45]150 pop ax
[46]151 ret
[45]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)
[46]172 jg SHORT .BreakLoopSinceAllItemsExamined
[45]173
174 call GetItemPointerToDSSIfromIndexInAX
175 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
176
177 call GetItemPointerToDSSIfromIndexInDX
178 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
179
180 cmp ax, dx ; If (left <= right)
[46]181 jg SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
[45]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
[46]227 call GetPointerToTemporaryItemToESDI
[45]228 call GetItemPointerToDSSIfromIndexInAX
[46]229 call CopyItemFromDSSItoESDI
[45]230
231 ; Item DX to Item AX
[54]232 call Registers_ExchangeDSSIwithESDI
[45]233 call GetItemPointerToDSSIfromIndexInDX
[46]234 call CopyItemFromDSSItoESDI
[45]235
236 ; Stack to Item DX
[46]237 call GetPointerToTemporaryItemToESDI
[54]238 call Registers_ExchangeDSSIwithESDI
[46]239 call CopyItemFromDSSItoESDI
[45]240
241 pop di
242 pop es
243 ret
244
[46]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;--------------------------------------------------------------------
[45]255ALIGN JUMP_ALIGN
[46]256GetPointerToTemporaryItemToESDI:
257 lea di, [bp+QSORT_PARAMS.tempAndPivotItems]
[45]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
[46]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.