[linux.git] / arch / arm / lib / div64.S

/*
 *  linux/arch/arm/lib/div64.S
 *
 *  Optimized computation of 64-bit dividend / 32-bit divisor
 *
 *  Author:	Nicolas Pitre
 *  Created:	Oct 5, 2003
 *  Copyright:	Monta Vista Software, Inc.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 */

#include <linux/linkage.h>
#include <asm/unwind.h>

#ifdef __ARMEB__
#define xh r0
#define xl r1
#define yh r2
#define yl r3
#else
#define xl r0
#define xh r1
#define yl r2
#define yh r3
#endif

/*
 * __do_div64: perform a division with 64-bit dividend and 32-bit divisor.
 *
 * Note: Calling convention is totally non standard for optimal code.
 *       This is meant to be used by do_div() from include/asm/div64.h only.
 *
 * Input parameters:
 * 	xh-xl	= dividend (clobbered)
 * 	r4	= divisor (preserved)
 *
 * Output values:
 * 	yh-yl	= result
 * 	xh	= remainder
 *
 * Clobbered regs: xl, ip
 */

ENTRY(__do_div64)
UNWIND(.fnstart)

	@ Test for easy paths first.
	subs	ip, r4, #1
	bls	9f			@ divisor is 0 or 1
	tst	ip, r4
	beq	8f			@ divisor is power of 2

	@ See if we need to handle upper 32-bit result.
	cmp	xh, r4
	mov	yh, #0
	blo	3f

	@ Align divisor with upper part of dividend.
	@ The aligned divisor is stored in yl preserving the original.
	@ The bit position is stored in ip.

#if __LINUX_ARM_ARCH__ >= 5

	clz	yl, r4
	clz	ip, xh
	sub	yl, yl, ip
	mov	ip, #1
	mov	ip, ip, lsl yl
	mov	yl, r4, lsl yl

#else

	mov	yl, r4
	mov	ip, #1
1:	cmp	yl, #0x80000000
	cmpcc	yl, xh
	movcc	yl, yl, lsl #1
	movcc	ip, ip, lsl #1
	bcc	1b

#endif

	@ The division loop for needed upper bit positions.
 	@ Break out early if dividend reaches 0.
2:	cmp	xh, yl
	orrcs	yh, yh, ip
	subcss	xh, xh, yl
	movnes	ip, ip, lsr #1
	mov	yl, yl, lsr #1
	bne	2b

	@ See if we need to handle lower 32-bit result.
3:	cmp	xh, #0
	mov	yl, #0
	cmpeq	xl, r4
	movlo	xh, xl
	movlo	pc, lr

	@ The division loop for lower bit positions.
	@ Here we shift remainer bits leftwards rather than moving the
	@ divisor for comparisons, considering the carry-out bit as well.
	mov	ip, #0x80000000
4:	movs	xl, xl, lsl #1
	adcs	xh, xh, xh
	beq	6f
	cmpcc	xh, r4
5:	orrcs	yl, yl, ip
	subcs	xh, xh, r4
	movs	ip, ip, lsr #1
	bne	4b
	mov	pc, lr

	@ The top part of remainder became zero.  If carry is set
	@ (the 33th bit) this is a false positive so resume the loop.
	@ Otherwise, if lower part is also null then we are done.
6:	bcs	5b
	cmp	xl, #0
	moveq	pc, lr

	@ We still have remainer bits in the low part.  Bring them up.

#if __LINUX_ARM_ARCH__ >= 5

	clz	xh, xl			@ we know xh is zero here so...
	add	xh, xh, #1
	mov	xl, xl, lsl xh
	mov	ip, ip, lsr xh

#else

7:	movs	xl, xl, lsl #1
	mov	ip, ip, lsr #1
	bcc	7b

#endif

	@ Current remainder is now 1.  It is worthless to compare with
	@ divisor at this point since divisor can not be smaller than 3 here.
	@ If possible, branch for another shift in the division loop.
	@ If no bit position left then we are done.
	movs	ip, ip, lsr #1
	mov	xh, #1
	bne	4b
	mov	pc, lr

8:	@ Division by a power of 2: determine what that divisor order is
	@ then simply shift values around

#if __LINUX_ARM_ARCH__ >= 5

	clz	ip, r4
	rsb	ip, ip, #31

#else

	mov	yl, r4
	cmp	r4, #(1 << 16)
	mov	ip, #0
	movhs	yl, yl, lsr #16
	movhs	ip, #16

	cmp	yl, #(1 << 8)
	movhs	yl, yl, lsr #8
	addhs	ip, ip, #8

	cmp	yl, #(1 << 4)
	movhs	yl, yl, lsr #4
	addhs	ip, ip, #4

	cmp	yl, #(1 << 2)
	addhi	ip, ip, #3
	addls	ip, ip, yl, lsr #1

#endif

	mov	yh, xh, lsr ip
	mov	yl, xl, lsr ip
	rsb	ip, ip, #32
 ARM(	orr	yl, yl, xh, lsl ip	)
 THUMB(	lsl	xh, xh, ip		)
 THUMB(	orr	yl, yl, xh		)
	mov	xh, xl, lsl ip
	mov	xh, xh, lsr ip
	mov	pc, lr

	@ eq -> division by 1: obvious enough...
9:	moveq	yl, xl
	moveq	yh, xh
	moveq	xh, #0
	moveq	pc, lr
UNWIND(.fnend)

UNWIND(.fnstart)
UNWIND(.pad #4)
UNWIND(.save {lr})
Ldiv0_64:
	@ Division by 0:
	str	lr, [sp, #-8]!
	bl	__div0

	@ as wrong as it could be...
	mov	yl, #0
	mov	yh, #0
	mov	xh, #0
	ldr	pc, [sp], #8

UNWIND(.fnend)
ENDPROC(__do_div64)
Commit	Line	Data
1da177e4 LT	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>
01885bc5	16	#include <asm/unwind.h>
1da177e4 LT	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
	47	ENTRY(__do_div64)
01885bc5	48	UNWIND(.fnstart)
1da177e4 LT	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
	78	1: 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.
	88	2: 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.
	96	3: 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
	106	4: movs xl, xl, lsl #1
	107	adcs xh, xh, xh
	108	beq 6f
	109	cmpcc xh, r4
	110	5: 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.
119	6: 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
134	7: 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
149	8: @ 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
8b592783 CM	182	ARM( orr yl, yl, xh, lsl ip )
	183	THUMB( lsl xh, xh, ip )
	184	THUMB( orr yl, yl, xh )
1da177e4 LT	185	mov xh, xl, lsl ip
	186	mov xh, xh, lsr ip
	187	mov pc, lr
	188
	189	@ eq -> division by 1: obvious enough...
	190	9: moveq yl, xl
	191	moveq yh, xh
	192	moveq xh, #0
	193	moveq pc, lr
01885bc5	194	UNWIND(.fnend)
1da177e4	195
01885bc5 LA	196	UNWIND(.fnstart)
	197	UNWIND(.pad #4)
	198	UNWIND(.save {lr})
	199	Ldiv0_64:
1da177e4	200	@ Division by 0:
1d6760a3	201	str lr, [sp, #-8]!
1da177e4 LT	202	bl __div0
	203
	204	@ as wrong as it could be...
	205	mov yl, #0
	206	mov yh, #0
	207	mov xh, #0
1d6760a3	208	ldr pc, [sp], #8
1da177e4	209
01885bc5	210	UNWIND(.fnend)
93ed3970	211	ENDPROC(__do_div64)