Context Navigation

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

Last change on this file since 54 was 54, checked in by aitotat, 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
10	struc QSORT_PARAMS
11	.lpItems resb 4
12	.tempAndPivotItems:
13	endstruc
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
29	SECTION .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	;--------------------------------------------------------------------
43	ALIGN JUMP_ALIGN
44	Sort_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	;--------------------------------------------------------------------
83	ALIGN JUMP_ALIGN
84	QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
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
105	ALIGN 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	;--------------------------------------------------------------------
126	ALIGN JUMP_ALIGN
127	ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
128	push di
129	push si
130
131	call .GetPivotPointerToESDI
132	call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
133
134	pop si
135	pop di
136	ret
137
138	ALIGN 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	;--------------------------------------------------------------------
169	ALIGN JUMP_ALIGN
170	ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
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
187	ALIGN 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
195	ALIGN JUMP_ALIGN
196	.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
197	call bx
198	jle SHORT .NoNeedToIncrementOrDecrementAnyMore
199	dec dx
200	sub si, cx
201	jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
202
203	ALIGN 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	;--------------------------------------------------------------------
221	ALIGN JUMP_ALIGN
222	SwapItemsFromIndexesAXandDX:
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	;--------------------------------------------------------------------
255	ALIGN JUMP_ALIGN
256	GetPointerToTemporaryItemToESDI:
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	;--------------------------------------------------------------------
275	ALIGN JUMP_ALIGN
276	GetItemPointerToDSSIfromIndexInDX:
277	xchg ax, dx
278	call GetItemPointerToDSSIfromIndexInAX
279	xchg dx, ax
280	ret
281
282	ALIGN JUMP_ALIGN
283	GetItemPointerToDSSIfromIndexInAX:
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	;--------------------------------------------------------------------
307	ALIGN JUMP_ALIGN
308	CopyItemFromDSSItoESDI:
309	call Memory_CopyCXbytesFromDSSItoESDI
310	sub si, cx ; Restore SI
311	ret

Note: See TracBrowser for help on using the repository browser.

Download in other formats: