1 /*---------------------------------------------------------------------------*
2 Project: TwlSDK - tests -
3 File: qsort.c
4
5 Copyright 2003-2008 Nintendo. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Date:: 2008-09-18#$
14 $Rev: 8573 $
15 $Author:$
16 *---------------------------------------------------------------------------*/
17
18 #include <nitro.h>
19
20 /* ------------------------------------------- *
21 * Non-recursive quicksort
22 * ------------------------------------------- */
23 /*---------------------------------------------------------------------------*
24 Name: MATH_QSort
25
26 Description: Performs a quicksort without using recursion.
27 The buffer area used for sort must be passed, and the required buffer size can be obtained with MATH_QSORT_STACK_SIZE( num ).
28
29
30 Arguments: head: Pointer to the data to sort
31 num: Number of data items to sort
32 width: Data size of one portion of data to sort
33 comp: Pointer to comparison function
34 stackBuf: Buffer to use for sorting
35
36 Returns: None.
37 *---------------------------------------------------------------------------*/
38 #include <nitro/code32.h>
MATH_QSort(register void * head,register u32 num,register u32 width,register MATHCompareFunc comp,void * stackBuf)39 asm void MATH_QSort( register void* head, register u32 num, register u32 width, register MATHCompareFunc comp, void* stackBuf )
40 {
41 #define stack r4
42 #define stackBuf_ r5
43 #define left r6
44 #define right r7
45 #define somewhere r6
46 #define somewhere_l r9
47 #define somewhere_r r10
48 #define tmp r2
49 #define tmp2 r3
50 #define comp_ r11
51 #define width_ r8
52
53 stmfd sp!, {r4-r11,lr}
54 cmp num, #1
55 ble @fin
56
57 ldr stack, [sp, #36] // stack = stackBuf;
58 mov comp_, comp // // r0-r3 and r12 are scratch registers, so they are saved before calling the comparison function
59 mov width_, width
60
61 cmp stack, #0
62 bne @00
63 clz tmp, num // // Allocate from the stack when the work buffer is NULL.
64 rsb tmp, tmp, #32
65 mov tmp, tmp, lsl #3 // // The required work size is (ILog2(num) + 1) * 4 * 2
66 sub sp, sp, tmp
67 mov stack, sp
68 str tmp, [sp, #-4]!
69
70 @00:
71 sub num, num, #1
72 mla num, num, width_, head
73
74 mov stackBuf_, stack // // PUSH the initial value. Delete because num and head are not used after this.
75 str head, [stack], #4 // PUSH(head);
76 str num, [stack], #4 // PUSH(head + (num-1) * width);
77
78 clz tmp, width_ // // Calculate ILog2(width)+1 (Use later for reference value selection)
79 rsb tmp, tmp, #32
80 str tmp, [sp, #-4]!
81
82 @01:
83 cmp stack, stackBuf_ // while ( stack != stackBuf ) {
84 beq @end
85
86 ldr right, [stack, #-4] // POP(right)
87 ldr left, [stack, #-8]! // POP(left)
88
89 sub tmp, right, left
90 cmp tmp, width_
91 bne @02 // if ( (right - left) == width ) {
92 mov r0, left
93 mov r1, right
94 blx comp_
95 cmp r0, #0 // if ( comp( left, right ) > 0 ) {
96 ble @01
97 // swap( left, right, width ); /* swap begins here */
98 mov r0, width_
99 tst r0, #3
100 beq @012
101 @011:
102 ldrb r1, [left]
103 subs r0, r0, #1
104 swpb r1, r1, [right]
105 add right, right, #1
106 strb r1, [left], #1
107 bne @011
108 b @01
109
110 @012:
111 ldr r1, [left]
112 subs r0, r0, #4
113 swp r1, r1, [right]
114 add right, right, #4
115 str r1, [left], #4
116 bne @012
117 b @01
118 // /* swap ends here */
119
120 // }
121 // continue;
122 @02: // }
123 // // Use the ILog2(width) value initially computed to select a reference value at the middle position
124 // somewhere = (((right - left) >> ILog2(width)) * width / 2) + left;
125 ldr tmp2, [sp]
126 sub tmp, right, left
127 mov tmp, tmp, lsr tmp2
128 mla tmp, tmp, width_, left
129 // swap( left, left + width * 2, width ); /* swap begins here */
130 mov r3, left
131 mov r0, width_
132 mov r2, tmp
133 tst r0, #3
134 beq @022
135 @021:
136 ldrb r1, [r2]
137 subs r0, r0, #1
138 swpb r1, r1, [r3]
139 add r3, r3, #1
140 strb r1, [r2], #1
141 bne @021
142 b @023
143
144 @022:
145 ldr r1, [r2]
146 subs r0, r0, #4
147 swp r1, r1, [r3]
148 add r3, r3, #4
149 str r1, [r2], #4
150 bne @022
151 // /* swap ends here */
152 @023:
153 mov somewhere_l, left // somewhere_l = left + width;
154 mov somewhere_r, right // somewhere_r = right;
155 add somewhere_l, somewhere_l, width_
156 @03: // do {
157 cmp somewhere_l, right
158 bge @04
159 mov r1, somewhere
160 mov r0, somewhere_l
161 blx comp_
162 cmp r0, #0 // while( somewhere_l < right && comp( somewhere_l, somewhere ) < 0 ) {
163 addlt somewhere_l, somewhere_l, width_ // somewhere_l += width;
164 blt @03 // }
165 @04:
166 mov r1, somewhere
167 mov r0, somewhere_r
168 blx comp_
169 cmp r0, #0 // while( comp( somewhere_r, somewhere ) > 0 ) {
170 subgt somewhere_r, somewhere_r, width_ // somewhere_r -= width;
171 bgt @04 // }
172
173 cmp somewhere_l, somewhere_r // if ( somewhere_l < somewhere_r ) {
174 bge @05
175
176 // swap( somewhere_l, somewhere_r, width ) /* swap begins here */;
177 mov r2, somewhere_l
178 mov r3, somewhere_r
179 mov r0, width_
180 tst r0, #3
181 beq @042
182 @041:
183 ldrb r1, [r2]
184 subs r0, r0, #1
185 swpb r1, r1, [r3]
186 add r3, r3, #1
187 strb r1, [r2], #1
188 bne @041
189 b @043
190
191 @042:
192 ldr r1, [r2]
193 subs r0, r0, #4
194 swp r1, r1, [r3]
195 add r3, r3, #4
196 str r1, [r2], #4
197 bne @042
198 // /* swap ends here */
199
200 @043:
201
202 add somewhere_l, somewhere_l, width_ // somewhere_l += width;
203 sub somewhere_r, somewhere_r, width_ // somewhere_r -= width;
204 // }
205 cmp somewhere_l, somewhere_r
206 ble @03 // } while ( somewhere_l <= smewhere_r );
207
208 @05:
209 // swap( left, somewhere_r, width ); /* swap begins here */
210 mov r2, left
211 mov r3, somewhere_r
212 mov r0, width_
213 tst r0, #3
214 beq @052
215 @051:
216 ldrb r1, [r2]
217 subs r0, r0, #1
218 swpb r1, r1, [r3]
219 add r3, r3, #1
220 strb r1, [r2], #1
221 bne @051
222 b @053
223
224 @052:
225 ldr r1, [r2]
226 subs r0, r0, #4
227 swp r1, r1, [r3]
228 add r3, r3, #4
229 str r1, [r2], #4
230 bne @052
231 // /* swap ends here */
232 @053:
233
234 sub tmp, somewhere_r, left
235 sub tmp2, right, somewhere_r // /* Sort from a small range in order to use the stack as little as possible */
236 cmp tmp, tmp2 // if ( somwehre_r - left > right - somewhere_r ) {
237 ble @06
238
239 sub tmp, somewhere_r, width_ // if ( left < somewhere_r - width ) {
240 cmp left, tmp
241
242 strlt left, [stack], #4 // PUSH(left);
243 strlt tmp, [stack], #4 // PUSH(somewhere_r - width);
244 // }
245 add tmp, somewhere_r, width_ // if ( somewhere_r + width < right ) {
246 cmp tmp, right
247 strlt tmp, [stack], #4 // PUSH( somewhere_r + width );
248 strlt right, [stack], #4 // PUSH( right );
249 // }
250 b @01
251
252 @06: // } else {
253 add tmp, somewhere_r, width_ // if ( somewhere_r + width < right ) {
254 cmp tmp, right
255 strlt tmp, [stack], #4 // PUSH( somewhere_r + width );
256 strlt right, [stack], #4 // PUSH( right );
257 // }
258 sub tmp, somewhere_r, width_ // if ( left < somewhere_r - width ) {
259 cmp left, tmp
260 strlt left, [stack], #4 // PUSH(left);
261 strlt tmp, [stack], #4 // PUSH(somewhere_r - width);
262 // }
263 b @01 // }
264 // }
265 @end:
266 add sp, sp, #4
267 sub stack, stack, #4
268 cmp stack, sp
269 ldreq r0, [sp]
270 addeq r0, r0, #4
271 addeq sp, sp, r0
272
273 @fin:
274 ldmfd sp!,{r4-r11,lr}
275 bx lr
276
277 #undef stack
278 #undef stackBuf_
279 #undef left
280 #undef right
281 #undef somewhere
282 #undef somewhere_l
283 #undef somewhere_r
284 #undef tmp
285 #undef tmp2
286 #undef comp_
287 #undef width_
288
289 }
290 #include <nitro/codereset.h>
291