Context Navigation

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

Last change on this file since 526 was 526, checked in by krille_n_@…, 11 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
22	struc QSORT_PARAMS
23	.lpItems resb 4
24	.tempAndPivotItems:
25	endstruc
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
41	SECTION .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	;--------------------------------------------------------------------
55	ALIGN JUMP_ALIGN
56	Sort_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	;--------------------------------------------------------------------
95	ALIGN JUMP_ALIGN
96	QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
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
117	ALIGN 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	;--------------------------------------------------------------------
138	ALIGN JUMP_ALIGN
139	ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
140	push di
141	push si
142
143	call .GetPivotPointerToESDI
144	call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
145
146	pop si
147	pop di
148	ret
149
150	ALIGN 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	;--------------------------------------------------------------------
181	ALIGN JUMP_ALIGN
182	ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
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
199	ALIGN 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
207	ALIGN JUMP_ALIGN
208	.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
209	call bx
210	jle SHORT .NoNeedToIncrementOrDecrementAnyMore
211	dec dx
212	sub si, cx
213	jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
214
215	ALIGN 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	;--------------------------------------------------------------------
233	ALIGN JUMP_ALIGN
234	SwapItemsFromIndexesAXandDX:
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	;--------------------------------------------------------------------
267	ALIGN JUMP_ALIGN
268	GetPointerToTemporaryItemToESDI:
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	;--------------------------------------------------------------------
287	ALIGN JUMP_ALIGN
288	GetItemPointerToDSSIfromIndexInDX:
289	xchg ax, dx
290	call GetItemPointerToDSSIfromIndexInAX
291	xchg dx, ax
292	ret
293
294	ALIGN JUMP_ALIGN
295	GetItemPointerToDSSIfromIndexInAX:
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	;--------------------------------------------------------------------
319	ALIGN JUMP_ALIGN
320	CopyItemFromDSSItoESDI:
321	call Memory_CopyCXbytesFromDSSItoESDI
322	sub si, cx ; Restore SI
323	ret

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

Download in other formats: