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

Last change on this file since 445 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.