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/types.h>
13#include <linux/bitops.h>
14
15#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
16
17/*
18 * Find the next set bit in a memory region.
19 */
20unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
21			    unsigned long offset)
22{
23	const unsigned long *p = addr + BITOP_WORD(offset);
24	unsigned long result = offset & ~(BITS_PER_LONG-1);
25	unsigned long tmp;
26
27	if (offset >= size)
28		return size;
29	size -= result;
30	offset %= BITS_PER_LONG;
31	if (offset) {
32		tmp = *(p++);
33		tmp &= (~0UL << offset);
34		if (size < BITS_PER_LONG)
35			goto found_first;
36		if (tmp)
37			goto found_middle;
38		size -= BITS_PER_LONG;
39		result += BITS_PER_LONG;
40	}
41	while (size & ~(BITS_PER_LONG-1)) {
42		if ((tmp = *(p++)))
43			goto found_middle;
44		result += BITS_PER_LONG;
45		size -= BITS_PER_LONG;
46	}
47	if (!size)
48		return result;
49	tmp = *p;
50
51found_first:
52	tmp &= (~0UL >> (BITS_PER_LONG - size));
53	if (tmp == 0UL)		/* Are any bits set? */
54		return result + size;	/* Nope. */
55found_middle:
56	return result + __ffs(tmp);
57}