[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)

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