1/*
2 *  linux/arch/arm/lib/div64.S
3 *
4 *  Optimized computation of 64-bit dividend / 32-bit divisor
5 *
6 *  Author:	Nicolas Pitre
7 *  Created:	Oct 5, 2003
8 *  Copyright:	Monta Vista Software, Inc.
9 *
10 *  This program is free software; you can redistribute it and/or modify
11 *  it under the terms of the GNU General Public License version 2 as
12 *  published by the Free Software Foundation.
13 */
14
15#include <linux/linkage.h>
16#include <asm/unwind.h>
17
18#ifdef __ARMEB__
19#define xh r0
20#define xl r1
21#define yh r2
22#define yl r3
23#else
24#define xl r0
25#define xh r1
26#define yl r2
27#define yh r3
28#endif
29
30/*
31 * __do_div64: perform a division with 64-bit dividend and 32-bit divisor.
32 *
33 * Note: Calling convention is totally non standard for optimal code.
34 *       This is meant to be used by do_div() from include/asm/div64.h only.
35 *
36 * Input parameters:
37 * 	xh-xl	= dividend (clobbered)
38 * 	r4	= divisor (preserved)
39 *
40 * Output values:
41 * 	yh-yl	= result
42 * 	xh	= remainder
43 *
44 * Clobbered regs: xl, ip
45 */
46
47ENTRY(__do_div64)
48UNWIND(.fnstart)
49
50	@ Test for easy paths first.
51	subs	ip, r4, #1
52	bls	9f			@ divisor is 0 or 1
53	tst	ip, r4
54	beq	8f			@ divisor is power of 2
55
56	@ See if we need to handle upper 32-bit result.
57	cmp	xh, r4
58	mov	yh, #0
59	blo	3f
60
61	@ Align divisor with upper part of dividend.
62	@ The aligned divisor is stored in yl preserving the original.
63	@ The bit position is stored in ip.
64
65#if __LINUX_ARM_ARCH__ >= 5
66
67	clz	yl, r4
68	clz	ip, xh
69	sub	yl, yl, ip
70	mov	ip, #1
71	mov	ip, ip, lsl yl
72	mov	yl, r4, lsl yl
73
74#else
75
76	mov	yl, r4
77	mov	ip, #1
781:	cmp	yl, #0x80000000
79	cmpcc	yl, xh
80	movcc	yl, yl, lsl #1
81	movcc	ip, ip, lsl #1
82	bcc	1b
83
84#endif
85
86	@ The division loop for needed upper bit positions.
87 	@ Break out early if dividend reaches 0.
882:	cmp	xh, yl
89	orrcs	yh, yh, ip
90	subcss	xh, xh, yl
91	movnes	ip, ip, lsr #1
92	mov	yl, yl, lsr #1
93	bne	2b
94
95	@ See if we need to handle lower 32-bit result.
963:	cmp	xh, #0
97	mov	yl, #0
98	cmpeq	xl, r4
99	movlo	xh, xl
100	movlo	pc, lr
101
102	@ The division loop for lower bit positions.
103	@ Here we shift remainer bits leftwards rather than moving the
104	@ divisor for comparisons, considering the carry-out bit as well.
105	mov	ip, #0x80000000
1064:	movs	xl, xl, lsl #1
107	adcs	xh, xh, xh
108	beq	6f
109	cmpcc	xh, r4
1105:	orrcs	yl, yl, ip
111	subcs	xh, xh, r4
112	movs	ip, ip, lsr #1
113	bne	4b
114	mov	pc, lr
115
116	@ The top part of remainder became zero.  If carry is set
117	@ (the 33th bit) this is a false positive so resume the loop.
118	@ Otherwise, if lower part is also null then we are done.
1196:	bcs	5b
120	cmp	xl, #0
121	moveq	pc, lr
122
123	@ We still have remainer bits in the low part.  Bring them up.
124
125#if __LINUX_ARM_ARCH__ >= 5
126
127	clz	xh, xl			@ we know xh is zero here so...
128	add	xh, xh, #1
129	mov	xl, xl, lsl xh
130	mov	ip, ip, lsr xh
131
132#else
133
1347:	movs	xl, xl, lsl #1
135	mov	ip, ip, lsr #1
136	bcc	7b
137
138#endif
139
140	@ Current remainder is now 1.  It is worthless to compare with
141	@ divisor at this point since divisor can not be smaller than 3 here.
142	@ If possible, branch for another shift in the division loop.
143	@ If no bit position left then we are done.
144	movs	ip, ip, lsr #1
145	mov	xh, #1
146	bne	4b
147	mov	pc, lr
148
1498:	@ Division by a power of 2: determine what that divisor order is
150	@ then simply shift values around
151
152#if __LINUX_ARM_ARCH__ >= 5
153
154	clz	ip, r4
155	rsb	ip, ip, #31
156
157#else
158
159	mov	yl, r4
160	cmp	r4, #(1 << 16)
161	mov	ip, #0
162	movhs	yl, yl, lsr #16
163	movhs	ip, #16
164
165	cmp	yl, #(1 << 8)
166	movhs	yl, yl, lsr #8
167	addhs	ip, ip, #8
168
169	cmp	yl, #(1 << 4)
170	movhs	yl, yl, lsr #4
171	addhs	ip, ip, #4
172
173	cmp	yl, #(1 << 2)
174	addhi	ip, ip, #3
175	addls	ip, ip, yl, lsr #1
176
177#endif
178
179	mov	yh, xh, lsr ip
180	mov	yl, xl, lsr ip
181	rsb	ip, ip, #32
182 ARM(	orr	yl, yl, xh, lsl ip	)
183 THUMB(	lsl	xh, xh, ip		)
184 THUMB(	orr	yl, yl, xh		)
185	mov	xh, xl, lsl ip
186	mov	xh, xh, lsr ip
187	mov	pc, lr
188
189	@ eq -> division by 1: obvious enough...
1909:	moveq	yl, xl
191	moveq	yh, xh
192	moveq	xh, #0
193	moveq	pc, lr
194UNWIND(.fnend)
195
196UNWIND(.fnstart)
197UNWIND(.pad #4)
198UNWIND(.save {lr})
199Ldiv0_64:
200	@ Division by 0:
201	str	lr, [sp, #-8]!
202	bl	__div0
203
204	@ as wrong as it could be...
205	mov	yl, #0
206	mov	yh, #0
207	mov	xh, #0
208	ldr	pc, [sp], #8
209
210UNWIND(.fnend)
211ENDPROC(__do_div64)
212