find_bit.c 4.55 KB
Newer Older
1
/* bit search implementation
Linus Torvalds's avatar
Linus Torvalds committed
2 3 4 5
 *
 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 *
6 7 8 9
 * Copyright (C) 2008 IBM Corporation
 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
 * (Inspired by David Howell's find_next_bit implementation)
 *
10 11 12
 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
 * size and improve performance, 2015.
 *
Linus Torvalds's avatar
Linus Torvalds committed
13 14 15 16 17 18 19
 * 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>
20
#include <linux/bitmap.h>
21
#include <linux/export.h>
22
#include <linux/kernel.h>
Linus Torvalds's avatar
Linus Torvalds committed
23

24
#if !defined(find_next_bit) || !defined(find_next_zero_bit)
25

26
/*
27 28 29
 * This is a common helper function for find_next_bit and
 * find_next_zero_bit.  The difference is the "invert" argument, which
 * is XORed with each fetched word before searching it for one bits.
30
 */
31 32
static unsigned long _find_next_bit(const unsigned long *addr,
		unsigned long nbits, unsigned long start, unsigned long invert)
Linus Torvalds's avatar
Linus Torvalds committed
33 34 35
{
	unsigned long tmp;

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
	if (!nbits || start >= nbits)
		return nbits;

	tmp = addr[start / BITS_PER_LONG] ^ invert;

	/* Handle 1st word. */
	tmp &= BITMAP_FIRST_WORD_MASK(start);
	start = round_down(start, BITS_PER_LONG);

	while (!tmp) {
		start += BITS_PER_LONG;
		if (start >= nbits)
			return nbits;

		tmp = addr[start / BITS_PER_LONG] ^ invert;
Linus Torvalds's avatar
Linus Torvalds committed
51 52
	}

53
	return min(start + __ffs(tmp), nbits);
54
}
55
#endif
Linus Torvalds's avatar
Linus Torvalds committed
56

57
#ifndef find_next_bit
58
/*
59
 * Find the next set bit in a memory region.
60
 */
61 62 63 64 65 66 67 68 69
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
			    unsigned long offset)
{
	return _find_next_bit(addr, size, offset, 0UL);
}
EXPORT_SYMBOL(find_next_bit);
#endif

#ifndef find_next_zero_bit
70 71
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
				 unsigned long offset)
72
{
73
	return _find_next_bit(addr, size, offset, ~0UL);
Linus Torvalds's avatar
Linus Torvalds committed
74
}
75
EXPORT_SYMBOL(find_next_zero_bit);
76
#endif
77

78
#ifndef find_first_bit
79 80 81
/*
 * Find the first set bit in a memory region.
 */
82
unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
83
{
84
	unsigned long idx;
85

86 87 88
	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
		if (addr[idx])
			return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
89 90
	}

91
	return size;
92
}
93
EXPORT_SYMBOL(find_first_bit);
94
#endif
95

96
#ifndef find_first_zero_bit
97 98 99
/*
 * Find the first cleared bit in a memory region.
 */
100
unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
101
{
102
	unsigned long idx;
103

104 105 106
	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
		if (addr[idx] != ~0UL)
			return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
107 108
	}

109
	return size;
110
}
111
EXPORT_SYMBOL(find_first_zero_bit);
112
#endif
113

114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
#ifndef find_last_bit
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
	if (size) {
		unsigned long val = BITMAP_LAST_WORD_MASK(size);
		unsigned long idx = (size-1) / BITS_PER_LONG;

		do {
			val &= addr[idx];
			if (val)
				return idx * BITS_PER_LONG + __fls(val);

			val = ~0ul;
		} while (idx--);
	}
	return size;
}
EXPORT_SYMBOL(find_last_bit);
#endif

134 135 136 137 138 139 140 141 142 143 144 145 146 147
#ifdef __BIG_ENDIAN

/* include/linux/byteorder does not 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
}

148 149 150
#if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
static unsigned long _find_next_bit_le(const unsigned long *addr,
		unsigned long nbits, unsigned long start, unsigned long invert)
151 152 153
{
	unsigned long tmp;

154 155 156 157 158 159 160 161
	if (!nbits || start >= nbits)
		return nbits;

	tmp = addr[start / BITS_PER_LONG] ^ invert;

	/* Handle 1st word. */
	tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
	start = round_down(start, BITS_PER_LONG);
162

163 164 165 166 167 168
	while (!tmp) {
		start += BITS_PER_LONG;
		if (start >= nbits)
			return nbits;

		tmp = addr[start / BITS_PER_LONG] ^ invert;
169 170
	}

171 172 173 174 175 176 177 178 179
	return min(start + __ffs(ext2_swab(tmp)), nbits);
}
#endif

#ifndef find_next_zero_bit_le
unsigned long find_next_zero_bit_le(const void *addr, unsigned
		long size, unsigned long offset)
{
	return _find_next_bit_le(addr, size, offset, ~0UL);
180
}
181
EXPORT_SYMBOL(find_next_zero_bit_le);
182
#endif
183

184
#ifndef find_next_bit_le
185
unsigned long find_next_bit_le(const void *addr, unsigned
186 187
		long size, unsigned long offset)
{
188
	return _find_next_bit_le(addr, size, offset, 0UL);
189
}
190
EXPORT_SYMBOL(find_next_bit_le);
191
#endif
192

193
#endif /* __BIG_ENDIAN */