1/* find_next_bit.c: fallback find next bit implementation
2 *
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 */
11
12#include <linux/bitops.h>
13#include <linux/export.h>
14#include <asm/types.h>
15#include <asm/byteorder.h>
16
17#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
18
19#ifndef find_next_bit
20/*
21 * Find the next set bit in a memory region.
22 */
23unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
24			    unsigned long offset)
25{
26	const unsigned long *p = addr + BITOP_WORD(offset);
27	unsigned long result = offset & ~(BITS_PER_LONG-1);
28	unsigned long tmp;
29
30	if (offset >= size)
31		return size;
32	size -= result;
33	offset %= BITS_PER_LONG;
34	if (offset) {
35		tmp = *(p++);
36		tmp &= (~0UL << offset);
37		if (size < BITS_PER_LONG)
38			goto found_first;
39		if (tmp)
40			goto found_middle;
41		size -= BITS_PER_LONG;
42		result += BITS_PER_LONG;
43	}
44	while (size & ~(BITS_PER_LONG-1)) {
45		if ((tmp = *(p++)))
46			goto found_middle;
47		result += BITS_PER_LONG;
48		size -= BITS_PER_LONG;
49	}
50	if (!size)
51		return result;
52	tmp = *p;
53
54found_first:
55	tmp &= (~0UL >> (BITS_PER_LONG - size));
56	if (tmp == 0UL)		/* Are any bits set? */
57		return result + size;	/* Nope. */
58found_middle:
59	return result + __ffs(tmp);
60}
61EXPORT_SYMBOL(find_next_bit);
62#endif
63
64#ifndef find_next_zero_bit
65/*
66 * This implementation of find_{first,next}_zero_bit was stolen from
67 * Linus' asm-alpha/bitops.h.
68 */
69unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
70				 unsigned long offset)
71{
72	const unsigned long *p = addr + BITOP_WORD(offset);
73	unsigned long result = offset & ~(BITS_PER_LONG-1);
74	unsigned long tmp;
75
76	if (offset >= size)
77		return size;
78	size -= result;
79	offset %= BITS_PER_LONG;
80	if (offset) {
81		tmp = *(p++);
82		tmp |= ~0UL >> (BITS_PER_LONG - offset);
83		if (size < BITS_PER_LONG)
84			goto found_first;
85		if (~tmp)
86			goto found_middle;
87		size -= BITS_PER_LONG;
88		result += BITS_PER_LONG;
89	}
90	while (size & ~(BITS_PER_LONG-1)) {
91		if (~(tmp = *(p++)))
92			goto found_middle;
93		result += BITS_PER_LONG;
94		size -= BITS_PER_LONG;
95	}
96	if (!size)
97		return result;
98	tmp = *p;
99
100found_first:
101	tmp |= ~0UL << size;
102	if (tmp == ~0UL)	/* Are any bits zero? */
103		return result + size;	/* Nope. */
104found_middle:
105	return result + ffz(tmp);
106}
107EXPORT_SYMBOL(find_next_zero_bit);
108#endif
109
110#ifndef find_first_bit
111/*
112 * Find the first set bit in a memory region.
113 */
114unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
115{
116	const unsigned long *p = addr;
117	unsigned long result = 0;
118	unsigned long tmp;
119
120	while (size & ~(BITS_PER_LONG-1)) {
121		if ((tmp = *(p++)))
122			goto found;
123		result += BITS_PER_LONG;
124		size -= BITS_PER_LONG;
125	}
126	if (!size)
127		return result;
128
129	tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
130	if (tmp == 0UL)		/* Are any bits set? */
131		return result + size;	/* Nope. */
132found:
133	return result + __ffs(tmp);
134}
135EXPORT_SYMBOL(find_first_bit);
136#endif
137
138#ifndef find_first_zero_bit
139/*
140 * Find the first cleared bit in a memory region.
141 */
142unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
143{
144	const unsigned long *p = addr;
145	unsigned long result = 0;
146	unsigned long tmp;
147
148	while (size & ~(BITS_PER_LONG-1)) {
149		if (~(tmp = *(p++)))
150			goto found;
151		result += BITS_PER_LONG;
152		size -= BITS_PER_LONG;
153	}
154	if (!size)
155		return result;
156
157	tmp = (*p) | (~0UL << size);
158	if (tmp == ~0UL)	/* Are any bits zero? */
159		return result + size;	/* Nope. */
160found:
161	return result + ffz(tmp);
162}
163EXPORT_SYMBOL(find_first_zero_bit);
164#endif
165
166#ifdef __BIG_ENDIAN
167
168/* include/linux/byteorder does not support "unsigned long" type */
169static inline unsigned long ext2_swabp(const unsigned long * x)
170{
171#if BITS_PER_LONG == 64
172	return (unsigned long) __swab64p((u64 *) x);
173#elif BITS_PER_LONG == 32
174	return (unsigned long) __swab32p((u32 *) x);
175#else
176#error BITS_PER_LONG not defined
177#endif
178}
179
180/* include/linux/byteorder doesn't support "unsigned long" type */
181static inline unsigned long ext2_swab(const unsigned long y)
182{
183#if BITS_PER_LONG == 64
184	return (unsigned long) __swab64((u64) y);
185#elif BITS_PER_LONG == 32
186	return (unsigned long) __swab32((u32) y);
187#else
188#error BITS_PER_LONG not defined
189#endif
190}
191
192#ifndef find_next_zero_bit_le
193unsigned long find_next_zero_bit_le(const void *addr, unsigned
194		long size, unsigned long offset)
195{
196	const unsigned long *p = addr;
197	unsigned long result = offset & ~(BITS_PER_LONG - 1);
198	unsigned long tmp;
199
200	if (offset >= size)
201		return size;
202	p += BITOP_WORD(offset);
203	size -= result;
204	offset &= (BITS_PER_LONG - 1UL);
205	if (offset) {
206		tmp = ext2_swabp(p++);
207		tmp |= (~0UL >> (BITS_PER_LONG - offset));
208		if (size < BITS_PER_LONG)
209			goto found_first;
210		if (~tmp)
211			goto found_middle;
212		size -= BITS_PER_LONG;
213		result += BITS_PER_LONG;
214	}
215
216	while (size & ~(BITS_PER_LONG - 1)) {
217		if (~(tmp = *(p++)))
218			goto found_middle_swap;
219		result += BITS_PER_LONG;
220		size -= BITS_PER_LONG;
221	}
222	if (!size)
223		return result;
224	tmp = ext2_swabp(p);
225found_first:
226	tmp |= ~0UL << size;
227	if (tmp == ~0UL)	/* Are any bits zero? */
228		return result + size; /* Nope. Skip ffz */
229found_middle:
230	return result + ffz(tmp);
231
232found_middle_swap:
233	return result + ffz(ext2_swab(tmp));
234}
235EXPORT_SYMBOL(find_next_zero_bit_le);
236#endif
237
238#ifndef find_next_bit_le
239unsigned long find_next_bit_le(const void *addr, unsigned
240		long size, unsigned long offset)
241{
242	const unsigned long *p = addr;
243	unsigned long result = offset & ~(BITS_PER_LONG - 1);
244	unsigned long tmp;
245
246	if (offset >= size)
247		return size;
248	p += BITOP_WORD(offset);
249	size -= result;
250	offset &= (BITS_PER_LONG - 1UL);
251	if (offset) {
252		tmp = ext2_swabp(p++);
253		tmp &= (~0UL << offset);
254		if (size < BITS_PER_LONG)
255			goto found_first;
256		if (tmp)
257			goto found_middle;
258		size -= BITS_PER_LONG;
259		result += BITS_PER_LONG;
260	}
261
262	while (size & ~(BITS_PER_LONG - 1)) {
263		tmp = *(p++);
264		if (tmp)
265			goto found_middle_swap;
266		result += BITS_PER_LONG;
267		size -= BITS_PER_LONG;
268	}
269	if (!size)
270		return result;
271	tmp = ext2_swabp(p);
272found_first:
273	tmp &= (~0UL >> (BITS_PER_LONG - size));
274	if (tmp == 0UL)		/* Are any bits set? */
275		return result + size; /* Nope. */
276found_middle:
277	return result + __ffs(tmp);
278
279found_middle_swap:
280	return result + __ffs(ext2_swab(tmp));
281}
282EXPORT_SYMBOL(find_next_bit_le);
283#endif
284
285#endif /* __BIG_ENDIAN */
286