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 */