[mirror_ubuntu-artful-kernel.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>

#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)

/**
 * 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);
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>
1da177e4	15
c7f612cd AM	16	#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
	17
	18	/**
	19	* find_next_bit - find the next set bit in a memory region
	20	* @addr: The address to base the search on
	21	* @offset: The bitnumber to start searching at
	22	* @size: The maximum size to search
	23	*/
	24	unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
	25	unsigned long offset)
1da177e4	26	{
c7f612cd AM	27	const unsigned long *p = addr + BITOP_WORD(offset);
c7f612cd AM	28	unsigned long result = offset & ~(BITS_PER_LONG-1);
1da177e4 LT	29	unsigned long tmp;
1da177e4 LT	30
c7f612cd AM	31	if (offset >= size)
	32	return size;
	33	size -= result;
	34	offset %= BITS_PER_LONG;
1da177e4	35	if (offset) {
c7f612cd AM	36	tmp = *(p++);
	37	tmp &= (~0UL << offset);
	38	if (size < BITS_PER_LONG)
	39	goto found_first;
	40	if (tmp)
	41	goto found_middle;
	42	size -= BITS_PER_LONG;
	43	result += BITS_PER_LONG;
	44	}
	45	while (size & ~(BITS_PER_LONG-1)) {
	46	if ((tmp = *(p++)))
	47	goto found_middle;
	48	result += BITS_PER_LONG;
	49	size -= BITS_PER_LONG;
1da177e4	50	}
c7f612cd AM	51	if (!size)
	52	return result;
	53	tmp = *p;
1da177e4	54
c7f612cd AM	55	found_first:
	56	tmp &= (~0UL >> (BITS_PER_LONG - size));
	57	if (tmp == 0UL) /* Are any bits set? */
	58	return result + size; /* Nope. */
	59	found_middle:
	60	return result + __ffs(tmp);
	61	}
1da177e4	62
c7f612cd	63	EXPORT_SYMBOL(find_next_bit);
1da177e4	64
c7f612cd AM	65	/*
	66	* This implementation of find_{first,next}_zero_bit was stolen from
	67	* Linus' asm-alpha/bitops.h.
	68	*/
	69	unsigned 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;
1da177e4	75
c7f612cd AM	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;
1da177e4	95	}
c7f612cd AM	96	if (!size)
	97	return result;
	98	tmp = *p;
1da177e4	99
c7f612cd AM	100	found_first:
	101	tmp \|= ~0UL << size;
	102	if (tmp == ~0UL) /* Are any bits zero? */
	103	return result + size; /* Nope. */
	104	found_middle:
	105	return result + ffz(tmp);
1da177e4	106	}
40234401	107
c7f612cd	108	EXPORT_SYMBOL(find_next_zero_bit);