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

Last change on this file since 45 was 45, checked in by aitotat, 14 years ago

Changes to assembly library:
Changed SetCharOutputFunctionFromAXwithAttribFlagInDL to SetCharOutputFunctionFromAXwithAttribFlagInBL since DX register gets corrupted by Display_FunctionFromDI.
Implemented quicksort.
File size: 7.5 KB
Line 
1; File name     :   Sort.asm
2; Project name  :   Assembly Library
3; Created date  :   28.9.2010
4; Last update   :   29.9.2010
5; Author        :   Tomi Tilli
6; Description   :   Sorting algorithms
7
8; Algorith is from http://www.algolist.net/Algorithms/Sorting/Quicksort
9
10struc QSORT_PARAMS
11    .lpItems        resb    4
12    .tempStruct:
13endstruc
14
15;--------------------------------------------------------------------
16; Prototype for comparator callback function
17;   Parameters:
18;       DS:SI:  Offset to first item to compare
19;       ES:DI:  Offset to second item to compare
20;   Returns:
21;       FLAGS:  Signed comparition between first and second item
22;   Corrupts registers:
23;       Nothing
24;--------------------------------------------------------------------
25
26
27; Section containing code
28SECTION .text
29
30;--------------------------------------------------------------------
31; DialogFile_GetFileNameWithIoInDSSI
32;   Parameters:
33;       DS:SI:  Ptr to FILE_DIALOG_IO
34;       SS:BP:  Ptr to parent MENU
35;   Returns:
36;       Nothing
37;   Corrupts registers:
38;       AX, CX, DX
39;--------------------------------------------------------------------
40ALIGN JUMP_ALIGN
41Sort_ItemsFromDSSIwithCountInDXsizeInCXandComparatorInBX:
42    push    es
43    push    di
44    add     cx, BYTE QSORT_PARAMS_size
45    eENTER_STRUCT cx
46
47    cld
48    sub     cx, BYTE QSORT_PARAMS_size  ; Restore CX to item size
49    xor     ax, ax                      ; Zero for starting index
50    dec     dx                          ; Count to index of last item
51    mov     [bp+QSORT_PARAMS.lpItems], si
52    mov     [bp+QSORT_PARAMS.lpItems+2], ds
53    call    QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
54
55    lds     si, [bp+QSORT_PARAMS.lpItems]
56    add     cx, BYTE QSORT_PARAMS_size
57    eLEAVE_STRUCT cx
58    pop     di
59    pop     es
60    ret
61
62
63;--------------------------------------------------------------------
64; QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
65;   Parameters:
66;       AX:     Index of first item in range
67;       BX:     Comparator function
68;       CX:     Size of struct in bytes
69;       DX:     Index of last (included) item in range
70;       SS:BP:  Ptr to QSORT_PARAMS
71;   Returns:
72;       Nothing
73;   Corrupts registers:
74;       DS, ES
75;       AX, DX (not for recursion)
76;--------------------------------------------------------------------
77ALIGN JUMP_ALIGN
78QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP:
79    push    di
80    push    si
81
82    mov     si, ax          ; First index to SI
83    mov     di, dx          ; Last index to DI
84    call    ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
85
86    ; Does left partition need more sorting
87    cmp     si, dx          ; if (first index < Index of rightmost unsorted item)
88    jae     SHORT .CheckIfRightPartitionNeedsMoreSorting
89    xchg    ax, si          ; AX = first index, SI = Index of leftmost unsorted item
90    call    QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
91    xchg    ax, si          ; AX = Index of leftmost unsorted item
92
93.CheckIfRightPartitionNeedsMoreSorting:
94    cmp     ax, di          ; if (Index of leftmost unsorted item < last index)
95    jae     SHORT .SortCompleted
96    mov     dx, di          ; DI = Index of leftmost unsorted item
97    call    QuicksortItemsInRangeFromAXtoDXwithQsortParamsInSSBP
98
99ALIGN JUMP_ALIGN
100.SortCompleted:
101    pop     si
102    pop     di
103    ret
104
105
106;--------------------------------------------------------------------
107; ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot
108;   Parameters:
109;       AX:     Index of first item in range
110;       BX:     Comparator function
111;       CX:     Size of struct in bytes
112;       DX:     Index of last (included) item in range
113;       SS:BP:  Ptr to QSORT_PARAMS
114;   Returns:
115;       AX:     Index of first unsorted item
116;       DX:     Index of last unsorted item
117;   Corrupts registers:
118;       DS, ES
119;--------------------------------------------------------------------
120ALIGN JUMP_ALIGN
121ArrangeItemsInRangeAXtoDXusingMiddleItemAsPivot:
122    push    di
123    push    si
124
125    call    .GetPivotPointerToESDI
126    call    ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
127
128    pop     si
129    pop     di
130    ret
131
132ALIGN JUMP_ALIGN
133.GetPivotPointerToESDI:
134    push    ax
135    add     ax, dx
136    shr     ax, 1
137    call    GetItemPointerToDSSIfromIndexInAX
138    pop     ax
139    jmp     Memory_ExchangeDSSIwithESDI
140
141
142;--------------------------------------------------------------------
143; ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
144;   Parameters:
145;       AX:     Index of first item in range
146;       BX:     Comparator function
147;       CX:     Size of struct in bytes
148;       DX:     Index of last (included) item in range
149;       ES:DI:  Ptr to Pivot item
150;       SS:BP:  Ptr to QSORT_PARAMS
151;   Returns:
152;       AX:     Index of first unsorted item
153;       DX:     Index of last unsorted item
154;   Corrupts registers:
155;       SI, DS
156;--------------------------------------------------------------------
157ALIGN JUMP_ALIGN
158ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI:
159    cmp     ax, dx  ; while (left <= right)
160    ja      SHORT .BreakLoopSinceAllItemsExamined
161
162    call    GetItemPointerToDSSIfromIndexInAX
163    call    .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
164
165    call    GetItemPointerToDSSIfromIndexInDX
166    call    .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
167
168    cmp     ax, dx  ; If (left <= right)
169    ja      SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
170    call    SwapItemsFromIndexesAXandDX
171    inc     ax
172    dec     dx
173    jmp     SHORT ArrangeItemsInRangeAXtoDXtoBothSidesOfPivotInESDI
174
175ALIGN JUMP_ALIGN
176.GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI:
177    call    bx
178    jge     SHORT .NoNeedToIncrementOrDecrementAnyMore
179    inc     ax              ; Increment item index
180    add     si, cx          ; Point to next struct
181    jmp     SHORT .GetIndexOfLeftmostItemToAXforItemThatIsGreaterThanEqualToPivotInESDI
182
183ALIGN JUMP_ALIGN
184.GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI:
185    call    bx
186    jle     SHORT .NoNeedToIncrementOrDecrementAnyMore
187    dec     dx
188    sub     si, cx
189    jmp     SHORT .GetIndexOfRightmostItemToDXforItemThatIsGreaterThanPivotInESDI
190
191ALIGN JUMP_ALIGN
192.NoNeedToIncrementOrDecrementAnyMore:
193.BreakLoopSinceAllItemsExamined:
194    ret
195
196
197;--------------------------------------------------------------------
198; SwapItemsFromIndexesAXandDX
199;   Parameters:
200;       AX:     Index of item 1
201;       CX:     Size of struct in bytes
202;       DX:     Index of item 2
203;       SS:BP:  Ptr to QSORT_PARAMS
204;   Returns:
205;       Nothing
206;   Corrupts registers:
207;       SI, DS
208;--------------------------------------------------------------------
209ALIGN JUMP_ALIGN
210SwapItemsFromIndexesAXandDX:
211    push    es
212    push    di
213
214    ; Item AX to stack
215    call    .GetPtrToTemporaryStructToESDI
216    call    GetItemPointerToDSSIfromIndexInAX
217    call    .CopyItemFromDSSItoESDI
218
219    ; Item DX to Item AX
220    call    Memory_ExchangeDSSIwithESDI
221    call    GetItemPointerToDSSIfromIndexInDX
222    call    .CopyItemFromDSSItoESDI
223
224    ; Stack to Item DX
225    call    .GetPtrToTemporaryStructToESDI
226    call    Memory_ExchangeDSSIwithESDI
227    call    .CopyItemFromDSSItoESDI
228
229    pop     di
230    pop     es
231    ret
232
233ALIGN JUMP_ALIGN
234.GetPtrToTemporaryStructToESDI:
235    lea     di, [bp+QSORT_PARAMS.tempStruct]
236    push    ss
237    pop     es
238    ret
239
240ALIGN JUMP_ALIGN
241.CopyItemFromDSSItoESDI:
242    push    si
243    push    cx
244
245    shr     cx, 1           ; We want to copy WORDs for performance
246    jcxz    .CopyLastByte
247    rep     movsw
248.CopyLastByte:
249    jnc     SHORT .CopyComplete
250    movsb
251.CopyComplete:
252    pop     cx
253    pop     si
254    ret
255
256
257;--------------------------------------------------------------------
258; GetItemPointerToDSSIfromIndexInDX
259; GetItemPointerToDSSIfromIndexInAX
260;   Parameters:
261;       AX or DX:   Item index
262;       CX:         Size of struct in bytes
263;       SS:BP:      Ptr to QSORT_PARAMS
264;   Returns:
265;       DS:SI:      Ptr to item
266;   Corrupts registers:
267;       Nothing
268;--------------------------------------------------------------------
269ALIGN JUMP_ALIGN
270GetItemPointerToDSSIfromIndexInDX:
271    xchg    ax, dx
272    call    GetItemPointerToDSSIfromIndexInAX
273    xchg    dx, ax
274    ret
275
276ALIGN JUMP_ALIGN
277GetItemPointerToDSSIfromIndexInAX:
278    push    dx
279    push    ax
280
281    mul     cx      ; DX:AX = index (AX) * size of struct (CX)
282    lds     si, [bp+QSORT_PARAMS.lpItems]
283    add     si, ax
284
285    pop     ax
286    pop     dx
287    ret
Note: See TracBrowser for help on using the repository browser.