[linux-2.6-block.git] / lib / find_next_bit.c

/* find_next_bit.c: fallback find next bit implementation
 *
 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version
 * 2 of the License, or (at your option) any later version.
 */

#include <linux/bitops.h>
#include <linux/module.h>
#include <asm/types.h>
#include <asm/byteorder.h>

#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
#undef find_next_bit
#undef find_next_zero_bit

/**
 * find_next_bit - find the next set bit in a memory region
 * @addr: The address to base the search on
 * @offset: The bitnumber to start searching at
 * @size: The maximum size to search
 */
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
		unsigned long offset)
{
	const unsigned long *p = addr + BITOP_WORD(offset);
	unsigned long result = offset & ~(BITS_PER_LONG-1);
	unsigned long tmp;

	if (offset >= size)
		return size;
	size -= result;
	offset %= BITS_PER_LONG;
	if (offset) {
		tmp = *(p++);
		tmp &= (~0UL << offset);
		if (size < BITS_PER_LONG)
			goto found_first;
		if (tmp)
			goto found_middle;
		size -= BITS_PER_LONG;
		result += BITS_PER_LONG;
	}
	while (size & ~(BITS_PER_LONG-1)) {
		if ((tmp = *(p++)))
			goto found_middle;
		result += BITS_PER_LONG;
		size -= BITS_PER_LONG;
	}
	if (!size)
		return result;
	tmp = *p;

found_first:
	tmp &= (~0UL >> (BITS_PER_LONG - size));
	if (tmp == 0UL)		/* Are any bits set? */
		return result + size;	/* Nope. */
found_middle:
	return result + __ffs(tmp);
}

EXPORT_SYMBOL(find_next_bit);

/*
 * This implementation of find_{first,next}_zero_bit was stolen from
 * Linus' asm-alpha/bitops.h.
 */
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
		unsigned long offset)
{
	const unsigned long *p = addr + BITOP_WORD(offset);
	unsigned long result = offset & ~(BITS_PER_LONG-1);
	unsigned long tmp;

	if (offset >= size)
		return size;
	size -= result;
	offset %= BITS_PER_LONG;
	if (offset) {
		tmp = *(p++);
		tmp |= ~0UL >> (BITS_PER_LONG - offset);
		if (size < BITS_PER_LONG)
			goto found_first;
		if (~tmp)
			goto found_middle;
		size -= BITS_PER_LONG;
		result += BITS_PER_LONG;
	}
	while (size & ~(BITS_PER_LONG-1)) {
		if (~(tmp = *(p++)))
			goto found_middle;
		result += BITS_PER_LONG;
		size -= BITS_PER_LONG;
	}
	if (!size)
		return result;
	tmp = *p;

found_first:
	tmp |= ~0UL << size;
	if (tmp == ~0UL)	/* Are any bits zero? */
		return result + size;	/* Nope. */
found_middle:
	return result + ffz(tmp);
}

EXPORT_SYMBOL(find_next_zero_bit);

#ifdef __BIG_ENDIAN

/* include/linux/byteorder does not support "unsigned long" type */
static inline unsigned long ext2_swabp(const unsigned long * x)
{
#if BITS_PER_LONG == 64
	return (unsigned long) __swab64p((u64 *) x);
#elif BITS_PER_LONG == 32
	return (unsigned long) __swab32p((u32 *) x);
#else
#error BITS_PER_LONG not defined
#endif
}

/* include/linux/byteorder doesn't support "unsigned long" type */
static inline unsigned long ext2_swab(const unsigned long y)
{
#if BITS_PER_LONG == 64
	return (unsigned long) __swab64((u64) y);
#elif BITS_PER_LONG == 32
	return (unsigned long) __swab32((u32) y);
#else
#error BITS_PER_LONG not defined
#endif
}

unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
		long size, unsigned long offset)
{
	const unsigned long *p = addr + BITOP_WORD(offset);
	unsigned long result = offset & ~(BITS_PER_LONG - 1);
	unsigned long tmp;

	if (offset >= size)
		return size;
	size -= result;
	offset &= (BITS_PER_LONG - 1UL);
	if (offset) {
		tmp = ext2_swabp(p++);
		tmp |= (~0UL >> (BITS_PER_LONG - offset));
		if (size < BITS_PER_LONG)
			goto found_first;
		if (~tmp)
			goto found_middle;
		size -= BITS_PER_LONG;
		result += BITS_PER_LONG;
	}

	while (size & ~(BITS_PER_LONG - 1)) {
		if (~(tmp = *(p++)))
			goto found_middle_swap;
		result += BITS_PER_LONG;
		size -= BITS_PER_LONG;
	}
	if (!size)
		return result;
	tmp = ext2_swabp(p);
found_first:
	tmp |= ~0UL << size;
	if (tmp == ~0UL)	/* Are any bits zero? */
		return result + size; /* Nope. Skip ffz */
found_middle:
	return result + ffz(tmp);

found_middle_swap:
	return result + ffz(ext2_swab(tmp));
}

EXPORT_SYMBOL(generic_find_next_zero_le_bit);

unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
		long size, unsigned long offset)
{
	const unsigned long *p = addr + BITOP_WORD(offset);
	unsigned long result = offset & ~(BITS_PER_LONG - 1);
	unsigned long tmp;

	if (offset >= size)
		return size;
	size -= result;
	offset &= (BITS_PER_LONG - 1UL);
	if (offset) {
		tmp = ext2_swabp(p++);
		tmp &= (~0UL << offset);
		if (size < BITS_PER_LONG)
			goto found_first;
		if (tmp)
			goto found_middle;
		size -= BITS_PER_LONG;
		result += BITS_PER_LONG;
	}

	while (size & ~(BITS_PER_LONG - 1)) {
		tmp = *(p++);
		if (tmp)
			goto found_middle_swap;
		result += BITS_PER_LONG;
		size -= BITS_PER_LONG;
	}
	if (!size)
		return result;
	tmp = ext2_swabp(p);
found_first:
	tmp &= (~0UL >> (BITS_PER_LONG - size));
	if (tmp == 0UL)		/* Are any bits set? */
		return result + size; /* Nope. */
found_middle:
	return result + __ffs(tmp);

found_middle_swap:
	return result + __ffs(ext2_swab(tmp));
}
EXPORT_SYMBOL(generic_find_next_le_bit);
#endif /* __BIG_ENDIAN */
Commit	Line	Data
1da177e4 LT	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>
40234401	13	#include <linux/module.h>
c7f612cd	14	#include <asm/types.h>
930ae745	15	#include <asm/byteorder.h>
1da177e4	16
c7f612cd	17	#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
6fd92b63 AH	18	#undef find_next_bit
6fd92b63 AH	19	#undef find_next_zero_bit
c7f612cd AM	20
	21	/**
	22	* find_next_bit - find the next set bit in a memory region
	23	* @addr: The address to base the search on
	24	* @offset: The bitnumber to start searching at
	25	* @size: The maximum size to search
	26	*/
	27	unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
	28	unsigned long offset)
1da177e4	29	{
c7f612cd AM	30	const unsigned long *p = addr + BITOP_WORD(offset);
c7f612cd AM	31	unsigned long result = offset & ~(BITS_PER_LONG-1);
1da177e4 LT	32	unsigned long tmp;
1da177e4 LT	33
c7f612cd AM	34	if (offset >= size)
	35	return size;
	36	size -= result;
	37	offset %= BITS_PER_LONG;
1da177e4	38	if (offset) {
c7f612cd AM	39	tmp = *(p++);
	40	tmp &= (~0UL << offset);
	41	if (size < BITS_PER_LONG)
	42	goto found_first;
	43	if (tmp)
	44	goto found_middle;
	45	size -= BITS_PER_LONG;
	46	result += BITS_PER_LONG;
	47	}
	48	while (size & ~(BITS_PER_LONG-1)) {
	49	if ((tmp = *(p++)))
	50	goto found_middle;
	51	result += BITS_PER_LONG;
	52	size -= BITS_PER_LONG;
1da177e4	53	}
c7f612cd AM	54	if (!size)
	55	return result;
	56	tmp = *p;
1da177e4	57
c7f612cd AM	58	found_first:
	59	tmp &= (~0UL >> (BITS_PER_LONG - size));
	60	if (tmp == 0UL) /* Are any bits set? */
	61	return result + size; /* Nope. */
	62	found_middle:
	63	return result + __ffs(tmp);
	64	}
1da177e4	65
c7f612cd	66	EXPORT_SYMBOL(find_next_bit);
1da177e4	67
c7f612cd AM	68	/*
	69	* This implementation of find_{first,next}_zero_bit was stolen from
	70	* Linus' asm-alpha/bitops.h.
	71	*/
	72	unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
	73	unsigned long offset)
	74	{
	75	const unsigned long *p = addr + BITOP_WORD(offset);
	76	unsigned long result = offset & ~(BITS_PER_LONG-1);
	77	unsigned long tmp;
1da177e4	78
c7f612cd AM	79	if (offset >= size)
	80	return size;
	81	size -= result;
	82	offset %= BITS_PER_LONG;
	83	if (offset) {
	84	tmp = *(p++);
	85	tmp \|= ~0UL >> (BITS_PER_LONG - offset);
	86	if (size < BITS_PER_LONG)
	87	goto found_first;
	88	if (~tmp)
	89	goto found_middle;
	90	size -= BITS_PER_LONG;
	91	result += BITS_PER_LONG;
	92	}
	93	while (size & ~(BITS_PER_LONG-1)) {
	94	if (~(tmp = *(p++)))
	95	goto found_middle;
	96	result += BITS_PER_LONG;
	97	size -= BITS_PER_LONG;
1da177e4	98	}
c7f612cd AM	99	if (!size)
	100	return result;
	101	tmp = *p;
1da177e4	102
c7f612cd AM	103	found_first:
	104	tmp \|= ~0UL << size;
	105	if (tmp == ~0UL) /* Are any bits zero? */
	106	return result + size; /* Nope. */
	107	found_middle:
	108	return result + ffz(tmp);
1da177e4	109	}
40234401	110
c7f612cd	111	EXPORT_SYMBOL(find_next_zero_bit);
930ae745 AM	112
	113	#ifdef __BIG_ENDIAN
	114
	115	/* include/linux/byteorder does not support "unsigned long" type */
	116	static inline unsigned long ext2_swabp(const unsigned long * x)
	117	{
	118	#if BITS_PER_LONG == 64
	119	return (unsigned long) __swab64p((u64 *) x);
	120	#elif BITS_PER_LONG == 32
	121	return (unsigned long) __swab32p((u32 *) x);
	122	#else
	123	#error BITS_PER_LONG not defined
	124	#endif
	125	}
	126
	127	/* include/linux/byteorder doesn't support "unsigned long" type */
	128	static inline unsigned long ext2_swab(const unsigned long y)
	129	{
	130	#if BITS_PER_LONG == 64
	131	return (unsigned long) __swab64((u64) y);
	132	#elif BITS_PER_LONG == 32
	133	return (unsigned long) __swab32((u32) y);
	134	#else
	135	#error BITS_PER_LONG not defined
	136	#endif
	137	}
	138
	139	unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
	140	long size, unsigned long offset)
	141	{
	142	const unsigned long *p = addr + BITOP_WORD(offset);
	143	unsigned long result = offset & ~(BITS_PER_LONG - 1);
	144	unsigned long tmp;
	145
	146	if (offset >= size)
	147	return size;
	148	size -= result;
	149	offset &= (BITS_PER_LONG - 1UL);
	150	if (offset) {
	151	tmp = ext2_swabp(p++);
	152	tmp \|= (~0UL >> (BITS_PER_LONG - offset));
	153	if (size < BITS_PER_LONG)
	154	goto found_first;
	155	if (~tmp)
	156	goto found_middle;
	157	size -= BITS_PER_LONG;
	158	result += BITS_PER_LONG;
	159	}
	160
	161	while (size & ~(BITS_PER_LONG - 1)) {
	162	if (~(tmp = *(p++)))
	163	goto found_middle_swap;
	164	result += BITS_PER_LONG;
	165	size -= BITS_PER_LONG;
	166	}
	167	if (!size)
	168	return result;
	169	tmp = ext2_swabp(p);
	170	found_first:
	171	tmp \|= ~0UL << size;
	172	if (tmp == ~0UL) /* Are any bits zero? */
	173	return result + size; /* Nope. Skip ffz */
	174	found_middle:
	175	return result + ffz(tmp);
176
177	found_middle_swap:
178	return result + ffz(ext2_swab(tmp));
179	}
180
181	EXPORT_SYMBOL(generic_find_next_zero_le_bit);
182
aa02ad67 AK	183	unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
	184	long size, unsigned long offset)
	185	{
	186	const unsigned long *p = addr + BITOP_WORD(offset);
	187	unsigned long result = offset & ~(BITS_PER_LONG - 1);
	188	unsigned long tmp;
	189
	190	if (offset >= size)
	191	return size;
	192	size -= result;
	193	offset &= (BITS_PER_LONG - 1UL);
	194	if (offset) {
	195	tmp = ext2_swabp(p++);
	196	tmp &= (~0UL << offset);
	197	if (size < BITS_PER_LONG)
	198	goto found_first;
	199	if (tmp)
	200	goto found_middle;
	201	size -= BITS_PER_LONG;
	202	result += BITS_PER_LONG;
	203	}
	204
	205	while (size & ~(BITS_PER_LONG - 1)) {
	206	tmp = *(p++);
	207	if (tmp)
	208	goto found_middle_swap;
	209	result += BITS_PER_LONG;
	210	size -= BITS_PER_LONG;
	211	}
	212	if (!size)
	213	return result;
	214	tmp = ext2_swabp(p);
	215	found_first:
	216	tmp &= (~0UL >> (BITS_PER_LONG - size));
	217	if (tmp == 0UL) /* Are any bits set? */
	218	return result + size; /* Nope. */
	219	found_middle:
	220	return result + __ffs(tmp);
	221
	222	found_middle_swap:
	223	return result + __ffs(ext2_swab(tmp));
	224	}
	225	EXPORT_SYMBOL(generic_find_next_le_bit);
930ae745	226	#endif /* __BIG_ENDIAN */