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

Last change on this file since 465 was 445, checked in by krille_n_@…, 12 years ago

Changes:

  • A speed optimization to the eSHL_IM macro for 386 and higher. This change breaks emulation in the sense that the macro will fail when given a memory operand as the first parameter.
  • Memory_SumCXbytesFromESSItoAL now returns with the zero flag set/cleared according to the result.
  • Unrolled all the 8 bit READ transfer loops to do 16 bytes per iteration. Added a new macro (UNROLL_SECTORS_IN_CX_TO_OWORDS) as part of it. Size wise this is expensive but I think it should be worth the ROM space. The WRITE transfer loops were left as is since writes are rare anyway (<10% of all disk I/O IIRC).
  • Minor optimizations and fixes here and there.
File size: 9.0 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;
9; XTIDE Universal BIOS and Associated Tools
10; Copyright (C) 2009-2010 by Tomi Tilli, 2011-2012 by XTIDE Universal BIOS Team.
11;
12; This program is free software; you can redistribute it and/or modify
13; it under the terms of the GNU General Public License as published by
14; the Free Software Foundation; either version 2 of the License, or
15; (at your option) any later version.
16;
17; This program is distributed in the hope that it will be useful,
18; but WITHOUT ANY WARRANTY; without even the implied warranty of
19; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20; GNU General Public License for more details.
21; Visit http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22;
23
24; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
25
26struc QSORT_PARAMS
27 .lpItems resb 4
28 .tempAndPivotItems:
29endstruc
30
31;--------------------------------------------------------------------
32; Prototype for comparator callback function
33; Parameters:
34; CX: Item size in bytes
35; DS:SI: Ptr to first item to compare
36; ES:DI: Ptr to second item to compare
37; Returns:
38; FLAGS: Signed comparition between first and second item
39; Corrupts registers:
40; Nothing
41;--------------------------------------------------------------------
42
43
44; Section containing code
45SECTION .text
46
47;--------------------------------------------------------------------
48; Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX
49; Parameters:
50; CX: Item size in bytes
51; DX: Number of items to sort (signed)
52; CS:BX: Comparator function
53; DS:SI: Ptr to array of items to sort
54; Returns:
55; Nothing
56; Corrupts registers:
57; AX, CX, DX
58;--------------------------------------------------------------------
59ALIGN JUMP_ALIGN
60Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
61 push es
62 push di
63 mov di, cx
64 eSHL_IM cx, 1 ; Reserve temp and pivot items
65 add cx, BYTE QSORT_PARAMS_size
66 eENTER_STRUCT cx
67 push cx
68
69 cld
70 mov cx, di ; Restore item size to CX
71 xor ax, ax ; Zero starting index
72 dec dx ; Count to index of last item
73 mov [bp+QSORT_PARAMS.lpItems], si
74 mov [bp+QSORT_PARAMS.lpItems+2], ds
75 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
76
77 lds si, [bp+QSORT_PARAMS.lpItems]
78 pop ax
79 eLEAVE_STRUCT ax
80 pop di
81 pop es
82 ret
83
84
85;--------------------------------------------------------------------
86; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
87; Parameters:
88; AX: Index of first item in range
89; BX: Comparator function
90; CX: Size of struct in bytes
91; DX: Index of last (included) item in range
92; SS:BP: Ptr to QSORT_PARAMS
93; Returns:
94; Nothing
95; Corrupts registers:
96; DS, ES
97; AX, DX (not for recursion)
98;--------------------------------------------------------------------
99ALIGN JUMP_ALIGN
100QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
101 push di
102 push si
103
104 mov si, ax ; First index to SI
105 mov di, dx ; Last index to DI
106 call ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
107
108 ; Does left partition need more sorting
109 cmp si, dx ; if (first index < Index of rightmost unsorted item)
110 jge SHORT .CheckIfRightPartitionNeedsMoreSorting
111 xchg ax, si ; AX = first index, SI = Index of leftmost unsorted item
112 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
113 xchg ax, si ; AX = Index of leftmost unsorted item
114
115.CheckIfRightPartitionNeedsMoreSorting:
116 cmp ax, di ; if (Index of leftmost unsorted item < last index)
117 jge SHORT .SortCompleted
118 mov dx, di ; DI = Index of leftmost unsorted item
119 call QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
120
121ALIGN JUMP_ALIGN
122.SortCompleted:
123 pop si
124 pop di
125 ret
126
127
128;--------------------------------------------------------------------
129; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
130; Parameters:
131; AX: Index of first item in range
132; BX: Comparator function
133; CX: Size of struct in bytes
134; DX: Index of last (included) item in range
135; SS:BP: Ptr to QSORT_PARAMS
136; Returns:
137; AX: Index of first unsorted item
138; DX: Index of last unsorted item
139; Corrupts registers:
140; DS, ES
141;--------------------------------------------------------------------
142ALIGN JUMP_ALIGN
143ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
144 push di
145 push si
146
147 call .GetPivotPointerToESDI
148 call ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
149
150 pop si
151 pop di
152 ret
153
154ALIGN JUMP_ALIGN
155.GetPivotPointerToESDI:
156 push ax
157
158 add ax, dx
159 shr ax, 1 ; AX = Middle index in partition
160 call GetItemPointerToDSSIfromIndexInAX
161 call GetPointerToTemporaryItemToESDI
162 add di, cx ; Pivot is after temporary item
163 call CopyItemFromDSSItoESDI
164 sub di, cx ; Restore DI
165
166 pop ax
167 ret
168
169
170;--------------------------------------------------------------------
171; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
172; Parameters:
173; AX: Index of first item in range
174; BX: Comparator function
175; CX: Size of struct in bytes
176; DX: Index of last (included) item in range
177; ES:DI: Ptr to Pivot item
178; SS:BP: Ptr to QSORT_PARAMS
179; Returns:
180; AX: Index of first unsorted item
181; DX: Index of last unsorted item
182; Corrupts registers:
183; SI, DS
184;--------------------------------------------------------------------
185ALIGN JUMP_ALIGN
186ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
187 cmp ax, dx ; while (left <= right)
188 jg SHORT .BreakLoopSinceAllItemsExamined
189
190 call GetItemPointerToDSSIfromIndexInAX
191 call .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
192
193 call GetItemPointerToDSSIfromIndexInDX
194 call .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
195
196 cmp ax, dx ; If (left <= right)
197 jg SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
198 call SwapItemsFromIndexesAXandDX
199 inc ax
200 dec dx
201 jmp SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
202
203ALIGN JUMP_ALIGN
204.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
205 call bx
206 jge SHORT .NoNeedToIncrementOrDecrementAnyMore
207 inc ax ; Increment item index
208 add si, cx ; Point to next struct
209 jmp SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
210
211ALIGN JUMP_ALIGN
212.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
213 call bx
214 jle SHORT .NoNeedToIncrementOrDecrementAnyMore
215 dec dx
216 sub si, cx
217 jmp SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
218
219ALIGN JUMP_ALIGN
220.NoNeedToIncrementOrDecrementAnyMore:
221.BreakLoopSinceAllItemsExamined:
222 ret
223
224
225;--------------------------------------------------------------------
226; SwapItemsFromIndexesAXandDX
227; Parameters:
228; AX: Index of item 1
229; CX: Size of struct in bytes
230; DX: Index of item 2
231; SS:BP: Ptr to QSORT_PARAMS
232; Returns:
233; Nothing
234; Corrupts registers:
235; SI, DS
236;--------------------------------------------------------------------
237ALIGN JUMP_ALIGN
238SwapItemsFromIndexesAXandDX:
239 push es
240 push di
241
242 ; Item AX to stack
243 call GetPointerToTemporaryItemToESDI
244 call GetItemPointerToDSSIfromIndexInAX
245 call CopyItemFromDSSItoESDI
246
247 ; Item DX to Item AX
248 call Registers_ExchangeDSSIwithESDI
249 call GetItemPointerToDSSIfromIndexInDX
250 call CopyItemFromDSSItoESDI
251
252 ; Stack to Item DX
253 call GetPointerToTemporaryItemToESDI
254 call Registers_ExchangeDSSIwithESDI
255 call CopyItemFromDSSItoESDI
256
257 pop di
258 pop es
259 ret
260
261
262;--------------------------------------------------------------------
263; GetPointerToTemporaryItemToESDI
264; Parameters:
265; SS:BP: Ptr to QSORT_PARAMS
266; Returns:
267; ES:DI: Ptr to temporary item
268; Corrupts registers:
269; Nothing
270;--------------------------------------------------------------------
271ALIGN JUMP_ALIGN
272GetPointerToTemporaryItemToESDI:
273 lea di, [bp+QSORT_PARAMS.tempAndPivotItems]
274 push ss
275 pop es
276 ret
277
278
279;--------------------------------------------------------------------
280; GetItemPointerToDSSIfromIndexInDX
281; GetItemPointerToDSSIfromIndexInAX
282; Parameters:
283; AX or DX: Item index
284; CX: Size of struct in bytes
285; SS:BP: Ptr to QSORT_PARAMS
286; Returns:
287; DS:SI: Ptr to item
288; Corrupts registers:
289; Nothing
290;--------------------------------------------------------------------
291ALIGN JUMP_ALIGN
292GetItemPointerToDSSIfromIndexInDX:
293 xchg ax, dx
294 call GetItemPointerToDSSIfromIndexInAX
295 xchg dx, ax
296 ret
297
298ALIGN JUMP_ALIGN
299GetItemPointerToDSSIfromIndexInAX:
300 push dx
301 push ax
302
303 mul cx ; DX:AX = index (AX) * size of struct (CX)
304 lds si, [bp+QSORT_PARAMS.lpItems]
305 add si, ax
306
307 pop ax
308 pop dx
309 ret
310
311
312;--------------------------------------------------------------------
313; CopyItemFromDSSItoESDI
314; Parameters:
315; CX: Item size in bytes
316; DS:SI: Ptr to source item
317; ES:DI: Ptr to destination buffer
318; Returns:
319; Nothing
320; Corrupts registers:
321; DI
322;--------------------------------------------------------------------
323ALIGN JUMP_ALIGN
324CopyItemFromDSSItoESDI:
325 call Memory_CopyCXbytesFromDSSItoESDI
326 sub si, cx ; Restore SI
327 ret
Note: See TracBrowser for help on using the repository browser.