1/* find_next_bit.c: fallback find next bit implementation
2 *
3 * Copied from lib/find_next_bit.c to tools/lib/next_bit.c
4 *
5 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
6 * Written by David Howells (dhowells@redhat.com)
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version
11 * 2 of the License, or (at your option) any later version.
12 */
13
14#include <linux/bitops.h>
15#include <asm/types.h>
16#include <asm/byteorder.h>
17
18#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
19
20#ifndef find_next_bit
21/*
22 * Find the next set bit in a memory region.
23 */
24unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
25			    unsigned long offset)
26{
27	const unsigned long *p = addr + BITOP_WORD(offset);
28	unsigned long result = offset & ~(BITS_PER_LONG-1);
29	unsigned long tmp;
30
31	if (offset >= size)
32		return size;
33	size -= result;
34	offset %= BITS_PER_LONG;
35	if (offset) {
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;
50	}
51	if (!size)
52		return result;
53	tmp = *p;
54
55found_first:
56	tmp &= (~0UL >> (BITS_PER_LONG - size));
57	if (tmp == 0UL)		/* Are any bits set? */
58		return result + size;	/* Nope. */
59found_middle:
60	return result + __ffs(tmp);
61}
62#endif
63
64#ifndef find_first_bit
65/*
66 * Find the first set bit in a memory region.
67 */
68unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
69{
70	const unsigned long *p = addr;
71	unsigned long result = 0;
72	unsigned long tmp;
73
74	while (size & ~(BITS_PER_LONG-1)) {
75		if ((tmp = *(p++)))
76			goto found;
77		result += BITS_PER_LONG;
78		size -= BITS_PER_LONG;
79	}
80	if (!size)
81		return result;
82
83	tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
84	if (tmp == 0UL)		/* Are any bits set? */
85		return result + size;	/* Nope. */
86found:
87	return result + __ffs(tmp);
88}
89#endif
90