1/*
2 * linux/arch/arm/lib/lib1funcs.S: Optimized ARM division routines
3 *
4 * Author: Nicolas Pitre <nico@fluxnic.net>
5 *   - contributed to gcc-3.4 on Sep 30, 2003
6 *   - adapted for the Linux kernel on Oct 2, 2003
7 */
8
9/* Copyright 1995, 1996, 1998, 1999, 2000, 2003 Free Software Foundation, Inc.
10
11This file is free software; you can redistribute it and/or modify it
12under the terms of the GNU General Public License as published by the
13Free Software Foundation; either version 2, or (at your option) any
14later version.
15
16In addition to the permissions in the GNU General Public License, the
17Free Software Foundation gives you unlimited permission to link the
18compiled version of this file into combinations with other programs,
19and to distribute those combinations without any restriction coming
20from the use of this file.  (The General Public License restrictions
21do apply in other respects; for example, they cover modification of
22the file, and distribution when not linked into a combine
23executable.)
24
25This file is distributed in the hope that it will be useful, but
26WITHOUT ANY WARRANTY; without even the implied warranty of
27MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
28General Public License for more details.
29
30You should have received a copy of the GNU General Public License
31along with this program; see the file COPYING.  If not, write to
32the Free Software Foundation, 59 Temple Place - Suite 330,
33Boston, MA 02111-1307, USA.  */
34
35
36#include <linux/linkage.h>
37#include <asm/assembler.h>
38
39
40.macro ARM_DIV_BODY dividend, divisor, result, curbit
41
42#if __LINUX_ARM_ARCH__ >= 5
43
44	clz	\curbit, \divisor
45	clz	\result, \dividend
46	sub	\result, \curbit, \result
47	mov	\curbit, #1
48	mov	\divisor, \divisor, lsl \result
49	mov	\curbit, \curbit, lsl \result
50	mov	\result, #0
51
52#else
53
54	@ Initially shift the divisor left 3 bits if possible,
55	@ set curbit accordingly.  This allows for curbit to be located
56	@ at the left end of each 4 bit nibbles in the division loop
57	@ to save one loop in most cases.
58	tst	\divisor, #0xe0000000
59	moveq	\divisor, \divisor, lsl #3
60	moveq	\curbit, #8
61	movne	\curbit, #1
62
63	@ Unless the divisor is very big, shift it up in multiples of
64	@ four bits, since this is the amount of unwinding in the main
65	@ division loop.  Continue shifting until the divisor is
66	@ larger than the dividend.
671:	cmp	\divisor, #0x10000000
68	cmplo	\divisor, \dividend
69	movlo	\divisor, \divisor, lsl #4
70	movlo	\curbit, \curbit, lsl #4
71	blo	1b
72
73	@ For very big divisors, we must shift it a bit at a time, or
74	@ we will be in danger of overflowing.
751:	cmp	\divisor, #0x80000000
76	cmplo	\divisor, \dividend
77	movlo	\divisor, \divisor, lsl #1
78	movlo	\curbit, \curbit, lsl #1
79	blo	1b
80
81	mov	\result, #0
82
83#endif
84
85	@ Division loop
861:	cmp	\dividend, \divisor
87	subhs	\dividend, \dividend, \divisor
88	orrhs	\result,   \result,   \curbit
89	cmp	\dividend, \divisor,  lsr #1
90	subhs	\dividend, \dividend, \divisor, lsr #1
91	orrhs	\result,   \result,   \curbit,  lsr #1
92	cmp	\dividend, \divisor,  lsr #2
93	subhs	\dividend, \dividend, \divisor, lsr #2
94	orrhs	\result,   \result,   \curbit,  lsr #2
95	cmp	\dividend, \divisor,  lsr #3
96	subhs	\dividend, \dividend, \divisor, lsr #3
97	orrhs	\result,   \result,   \curbit,  lsr #3
98	cmp	\dividend, #0			@ Early termination?
99	movnes	\curbit,   \curbit,  lsr #4	@ No, any more bits to do?
100	movne	\divisor,  \divisor, lsr #4
101	bne	1b
102
103.endm
104
105
106.macro ARM_DIV2_ORDER divisor, order
107
108#if __LINUX_ARM_ARCH__ >= 5
109
110	clz	\order, \divisor
111	rsb	\order, \order, #31
112
113#else
114
115	cmp	\divisor, #(1 << 16)
116	movhs	\divisor, \divisor, lsr #16
117	movhs	\order, #16
118	movlo	\order, #0
119
120	cmp	\divisor, #(1 << 8)
121	movhs	\divisor, \divisor, lsr #8
122	addhs	\order, \order, #8
123
124	cmp	\divisor, #(1 << 4)
125	movhs	\divisor, \divisor, lsr #4
126	addhs	\order, \order, #4
127
128	cmp	\divisor, #(1 << 2)
129	addhi	\order, \order, #3
130	addls	\order, \order, \divisor, lsr #1
131
132#endif
133
134.endm
135
136
137.macro ARM_MOD_BODY dividend, divisor, order, spare
138
139#if __LINUX_ARM_ARCH__ >= 5
140
141	clz	\order, \divisor
142	clz	\spare, \dividend
143	sub	\order, \order, \spare
144	mov	\divisor, \divisor, lsl \order
145
146#else
147
148	mov	\order, #0
149
150	@ Unless the divisor is very big, shift it up in multiples of
151	@ four bits, since this is the amount of unwinding in the main
152	@ division loop.  Continue shifting until the divisor is
153	@ larger than the dividend.
1541:	cmp	\divisor, #0x10000000
155	cmplo	\divisor, \dividend
156	movlo	\divisor, \divisor, lsl #4
157	addlo	\order, \order, #4
158	blo	1b
159
160	@ For very big divisors, we must shift it a bit at a time, or
161	@ we will be in danger of overflowing.
1621:	cmp	\divisor, #0x80000000
163	cmplo	\divisor, \dividend
164	movlo	\divisor, \divisor, lsl #1
165	addlo	\order, \order, #1
166	blo	1b
167
168#endif
169
170	@ Perform all needed substractions to keep only the reminder.
171	@ Do comparisons in batch of 4 first.
172	subs	\order, \order, #3		@ yes, 3 is intended here
173	blt	2f
174
1751:	cmp	\dividend, \divisor
176	subhs	\dividend, \dividend, \divisor
177	cmp	\dividend, \divisor,  lsr #1
178	subhs	\dividend, \dividend, \divisor, lsr #1
179	cmp	\dividend, \divisor,  lsr #2
180	subhs	\dividend, \dividend, \divisor, lsr #2
181	cmp	\dividend, \divisor,  lsr #3
182	subhs	\dividend, \dividend, \divisor, lsr #3
183	cmp	\dividend, #1
184	mov	\divisor, \divisor, lsr #4
185	subges	\order, \order, #4
186	bge	1b
187
188	tst	\order, #3
189	teqne	\dividend, #0
190	beq	5f
191
192	@ Either 1, 2 or 3 comparison/substractions are left.
1932:	cmn	\order, #2
194	blt	4f
195	beq	3f
196	cmp	\dividend, \divisor
197	subhs	\dividend, \dividend, \divisor
198	mov	\divisor,  \divisor,  lsr #1
1993:	cmp	\dividend, \divisor
200	subhs	\dividend, \dividend, \divisor
201	mov	\divisor,  \divisor,  lsr #1
2024:	cmp	\dividend, \divisor
203	subhs	\dividend, \dividend, \divisor
2045:
205.endm
206
207
208ENTRY(__udivsi3)
209ENTRY(__aeabi_uidiv)
210
211	subs	r2, r1, #1
212	moveq	pc, lr
213	bcc	Ldiv0
214	cmp	r0, r1
215	bls	11f
216	tst	r1, r2
217	beq	12f
218
219	ARM_DIV_BODY r0, r1, r2, r3
220
221	mov	r0, r2
222	mov	pc, lr
223
22411:	moveq	r0, #1
225	movne	r0, #0
226	mov	pc, lr
227
22812:	ARM_DIV2_ORDER r1, r2
229
230	mov	r0, r0, lsr r2
231	mov	pc, lr
232
233ENDPROC(__udivsi3)
234ENDPROC(__aeabi_uidiv)
235
236ENTRY(__umodsi3)
237
238	subs	r2, r1, #1			@ compare divisor with 1
239	bcc	Ldiv0
240	cmpne	r0, r1				@ compare dividend with divisor
241	moveq   r0, #0
242	tsthi	r1, r2				@ see if divisor is power of 2
243	andeq	r0, r0, r2
244	movls	pc, lr
245
246	ARM_MOD_BODY r0, r1, r2, r3
247
248	mov	pc, lr
249
250ENDPROC(__umodsi3)
251
252ENTRY(__divsi3)
253ENTRY(__aeabi_idiv)
254
255	cmp	r1, #0
256	eor	ip, r0, r1			@ save the sign of the result.
257	beq	Ldiv0
258	rsbmi	r1, r1, #0			@ loops below use unsigned.
259	subs	r2, r1, #1			@ division by 1 or -1 ?
260	beq	10f
261	movs	r3, r0
262	rsbmi	r3, r0, #0			@ positive dividend value
263	cmp	r3, r1
264	bls	11f
265	tst	r1, r2				@ divisor is power of 2 ?
266	beq	12f
267
268	ARM_DIV_BODY r3, r1, r0, r2
269
270	cmp	ip, #0
271	rsbmi	r0, r0, #0
272	mov	pc, lr
273
27410:	teq	ip, r0				@ same sign ?
275	rsbmi	r0, r0, #0
276	mov	pc, lr
277
27811:	movlo	r0, #0
279	moveq	r0, ip, asr #31
280	orreq	r0, r0, #1
281	mov	pc, lr
282
28312:	ARM_DIV2_ORDER r1, r2
284
285	cmp	ip, #0
286	mov	r0, r3, lsr r2
287	rsbmi	r0, r0, #0
288	mov	pc, lr
289
290ENDPROC(__divsi3)
291ENDPROC(__aeabi_idiv)
292
293ENTRY(__modsi3)
294
295	cmp	r1, #0
296	beq	Ldiv0
297	rsbmi	r1, r1, #0			@ loops below use unsigned.
298	movs	ip, r0				@ preserve sign of dividend
299	rsbmi	r0, r0, #0			@ if negative make positive
300	subs	r2, r1, #1			@ compare divisor with 1
301	cmpne	r0, r1				@ compare dividend with divisor
302	moveq	r0, #0
303	tsthi	r1, r2				@ see if divisor is power of 2
304	andeq	r0, r0, r2
305	bls	10f
306
307	ARM_MOD_BODY r0, r1, r2, r3
308
30910:	cmp	ip, #0
310	rsbmi	r0, r0, #0
311	mov	pc, lr
312
313ENDPROC(__modsi3)
314
315#ifdef CONFIG_AEABI
316
317ENTRY(__aeabi_uidivmod)
318
319	stmfd	sp!, {r0, r1, ip, lr}
320	bl	__aeabi_uidiv
321	ldmfd	sp!, {r1, r2, ip, lr}
322	mul	r3, r0, r2
323	sub	r1, r1, r3
324	mov	pc, lr
325
326ENDPROC(__aeabi_uidivmod)
327
328ENTRY(__aeabi_idivmod)
329
330	stmfd	sp!, {r0, r1, ip, lr}
331	bl	__aeabi_idiv
332	ldmfd	sp!, {r1, r2, ip, lr}
333	mul	r3, r0, r2
334	sub	r1, r1, r3
335	mov	pc, lr
336
337ENDPROC(__aeabi_idivmod)
338
339#endif
340
341Ldiv0:
342
343	str	lr, [sp, #-8]!
344	bl	__div0
345	mov	r0, #0			@ About as wrong as it could be.
346	ldr	pc, [sp], #8
347
348
349