1/*
2 *  linux/arch/arm/lib/findbit.S
3 *
4 *  Copyright (C) 1995-2000 Russell King
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 as
8 * published by the Free Software Foundation.
9 *
10 * 16th March 2001 - John Ripley <jripley@sonicblue.com>
11 *   Fixed so that "size" is an exclusive not an inclusive quantity.
12 *   All users of these functions expect exclusive sizes, and may
13 *   also call with zero size.
14 * Reworked by rmk.
15 */
16#include <linux/linkage.h>
17#include <asm/assembler.h>
18                .text
19
20/*
21 * Purpose  : Find a 'zero' bit
22 * Prototype: int find_first_zero_bit(void *addr, unsigned int maxbit);
23 */
24ENTRY(_find_first_zero_bit_le)
25		teq	r1, #0
26		beq	3f
27		mov	r2, #0
281:
29 ARM(		ldrb	r3, [r0, r2, lsr #3]	)
30 THUMB(		lsr	r3, r2, #3		)
31 THUMB(		ldrb	r3, [r0, r3]		)
32		eors	r3, r3, #0xff		@ invert bits
33		bne	.L_found		@ any now set - found zero bit
34		add	r2, r2, #8		@ next bit pointer
352:		cmp	r2, r1			@ any more?
36		blo	1b
373:		mov	r0, r1			@ no free bits
38		ret	lr
39ENDPROC(_find_first_zero_bit_le)
40
41/*
42 * Purpose  : Find next 'zero' bit
43 * Prototype: int find_next_zero_bit(void *addr, unsigned int maxbit, int offset)
44 */
45ENTRY(_find_next_zero_bit_le)
46		teq	r1, #0
47		beq	3b
48		ands	ip, r2, #7
49		beq	1b			@ If new byte, goto old routine
50 ARM(		ldrb	r3, [r0, r2, lsr #3]	)
51 THUMB(		lsr	r3, r2, #3		)
52 THUMB(		ldrb	r3, [r0, r3]		)
53		eor	r3, r3, #0xff		@ now looking for a 1 bit
54		movs	r3, r3, lsr ip		@ shift off unused bits
55		bne	.L_found
56		orr	r2, r2, #7		@ if zero, then no bits here
57		add	r2, r2, #1		@ align bit pointer
58		b	2b			@ loop for next bit
59ENDPROC(_find_next_zero_bit_le)
60
61/*
62 * Purpose  : Find a 'one' bit
63 * Prototype: int find_first_bit(const unsigned long *addr, unsigned int maxbit);
64 */
65ENTRY(_find_first_bit_le)
66		teq	r1, #0
67		beq	3f
68		mov	r2, #0
691:
70 ARM(		ldrb	r3, [r0, r2, lsr #3]	)
71 THUMB(		lsr	r3, r2, #3		)
72 THUMB(		ldrb	r3, [r0, r3]		)
73		movs	r3, r3
74		bne	.L_found		@ any now set - found zero bit
75		add	r2, r2, #8		@ next bit pointer
762:		cmp	r2, r1			@ any more?
77		blo	1b
783:		mov	r0, r1			@ no free bits
79		ret	lr
80ENDPROC(_find_first_bit_le)
81
82/*
83 * Purpose  : Find next 'one' bit
84 * Prototype: int find_next_zero_bit(void *addr, unsigned int maxbit, int offset)
85 */
86ENTRY(_find_next_bit_le)
87		teq	r1, #0
88		beq	3b
89		ands	ip, r2, #7
90		beq	1b			@ If new byte, goto old routine
91 ARM(		ldrb	r3, [r0, r2, lsr #3]	)
92 THUMB(		lsr	r3, r2, #3		)
93 THUMB(		ldrb	r3, [r0, r3]		)
94		movs	r3, r3, lsr ip		@ shift off unused bits
95		bne	.L_found
96		orr	r2, r2, #7		@ if zero, then no bits here
97		add	r2, r2, #1		@ align bit pointer
98		b	2b			@ loop for next bit
99ENDPROC(_find_next_bit_le)
100
101#ifdef __ARMEB__
102
103ENTRY(_find_first_zero_bit_be)
104		teq	r1, #0
105		beq	3f
106		mov	r2, #0
1071:		eor	r3, r2, #0x18		@ big endian byte ordering
108 ARM(		ldrb	r3, [r0, r3, lsr #3]	)
109 THUMB(		lsr	r3, #3			)
110 THUMB(		ldrb	r3, [r0, r3]		)
111		eors	r3, r3, #0xff		@ invert bits
112		bne	.L_found		@ any now set - found zero bit
113		add	r2, r2, #8		@ next bit pointer
1142:		cmp	r2, r1			@ any more?
115		blo	1b
1163:		mov	r0, r1			@ no free bits
117		ret	lr
118ENDPROC(_find_first_zero_bit_be)
119
120ENTRY(_find_next_zero_bit_be)
121		teq	r1, #0
122		beq	3b
123		ands	ip, r2, #7
124		beq	1b			@ If new byte, goto old routine
125		eor	r3, r2, #0x18		@ big endian byte ordering
126 ARM(		ldrb	r3, [r0, r3, lsr #3]	)
127 THUMB(		lsr	r3, #3			)
128 THUMB(		ldrb	r3, [r0, r3]		)
129		eor	r3, r3, #0xff		@ now looking for a 1 bit
130		movs	r3, r3, lsr ip		@ shift off unused bits
131		bne	.L_found
132		orr	r2, r2, #7		@ if zero, then no bits here
133		add	r2, r2, #1		@ align bit pointer
134		b	2b			@ loop for next bit
135ENDPROC(_find_next_zero_bit_be)
136
137ENTRY(_find_first_bit_be)
138		teq	r1, #0
139		beq	3f
140		mov	r2, #0
1411:		eor	r3, r2, #0x18		@ big endian byte ordering
142 ARM(		ldrb	r3, [r0, r3, lsr #3]	)
143 THUMB(		lsr	r3, #3			)
144 THUMB(		ldrb	r3, [r0, r3]		)
145		movs	r3, r3
146		bne	.L_found		@ any now set - found zero bit
147		add	r2, r2, #8		@ next bit pointer
1482:		cmp	r2, r1			@ any more?
149		blo	1b
1503:		mov	r0, r1			@ no free bits
151		ret	lr
152ENDPROC(_find_first_bit_be)
153
154ENTRY(_find_next_bit_be)
155		teq	r1, #0
156		beq	3b
157		ands	ip, r2, #7
158		beq	1b			@ If new byte, goto old routine
159		eor	r3, r2, #0x18		@ big endian byte ordering
160 ARM(		ldrb	r3, [r0, r3, lsr #3]	)
161 THUMB(		lsr	r3, #3			)
162 THUMB(		ldrb	r3, [r0, r3]		)
163		movs	r3, r3, lsr ip		@ shift off unused bits
164		bne	.L_found
165		orr	r2, r2, #7		@ if zero, then no bits here
166		add	r2, r2, #1		@ align bit pointer
167		b	2b			@ loop for next bit
168ENDPROC(_find_next_bit_be)
169
170#endif
171
172/*
173 * One or more bits in the LSB of r3 are assumed to be set.
174 */
175.L_found:
176#if __LINUX_ARM_ARCH__ >= 5
177		rsb	r0, r3, #0
178		and	r3, r3, r0
179		clz	r3, r3
180		rsb	r3, r3, #31
181		add	r0, r2, r3
182#else
183		tst	r3, #0x0f
184		addeq	r2, r2, #4
185		movne	r3, r3, lsl #4
186		tst	r3, #0x30
187		addeq	r2, r2, #2
188		movne	r3, r3, lsl #2
189		tst	r3, #0x40
190		addeq	r2, r2, #1
191		mov	r0, r2
192#endif
193		cmp	r1, r0			@ Clamp to maxbit
194		movlo	r0, r1
195		ret	lr
196
197