Subversion Repositories Kolibri OS

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
7143 serge 1 
/* bit search implementation
2 
 *
3 
 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 
 * Written by David Howells (dhowells@redhat.com)
5 
 *
6 
 * Copyright (C) 2008 IBM Corporation
7 
 * 'find_last_bit' is written by Rusty Russell
8 
 * (Inspired by David Howell's find_next_bit implementation)
9 
 *
10 
 * Rewritten by Yury Norov  to decrease
11 
 * size and improve performance, 2015.
12 
 *
13 
 * This program is free software; you can redistribute it and/or
14 
 * modify it under the terms of the GNU General Public License
15 
 * as published by the Free Software Foundation; either version
16 
 * 2 of the License, or (at your option) any later version.
17 
 */
18 
 
19 
#include
20 
#include
21 
#include
22 
#include
23 
 
24 
#if !defined(find_next_bit) || !defined(find_next_zero_bit)
25 
 
26 
/*
27 
 * This is a common helper function for find_next_bit and
28 
 * find_next_zero_bit.  The difference is the "invert" argument, which
29 
 * is XORed with each fetched word before searching it for one bits.
30 
 */
31 
static unsigned long _find_next_bit(const unsigned long *addr,
32 
		unsigned long nbits, unsigned long start, unsigned long invert)
33 
{
34 
	unsigned long tmp;
35 
 
36 
	if (!nbits || start >= nbits)
37 
		return nbits;
38 
 
39 
	tmp = addr[start / BITS_PER_LONG] ^ invert;
40 
 
41 
	/* Handle 1st word. */
42 
	tmp &= BITMAP_FIRST_WORD_MASK(start);
43 
	start = round_down(start, BITS_PER_LONG);
44 
 
45 
	while (!tmp) {
46 
		start += BITS_PER_LONG;
47 
		if (start >= nbits)
48 
			return nbits;
49 
 
50 
		tmp = addr[start / BITS_PER_LONG] ^ invert;
51 
	}
52 
 
53 
	return min(start + __ffs(tmp), nbits);
54 
}
55 
#endif
56 
 
57 
#ifndef find_next_bit
58 
/*
59 
 * Find the next set bit in a memory region.
60 
 */
61 
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
62 
			    unsigned long offset)
63 
{
64 
	return _find_next_bit(addr, size, offset, 0UL);
65 
}
66 
EXPORT_SYMBOL(find_next_bit);
67 
#endif
68 
 
69 
#ifndef find_next_zero_bit
70 
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71 
				 unsigned long offset)
72 
{
73 
	return _find_next_bit(addr, size, offset, ~0UL);
74 
}
75 
EXPORT_SYMBOL(find_next_zero_bit);
76 
#endif
77 
 
78 
#ifndef find_first_bit
79 
/*
80 
 * Find the first set bit in a memory region.
81 
 */
82 
unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
83 
{
84 
	unsigned long idx;
85 
 
86 
	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
87 
		if (addr[idx])
88 
			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 
 * Find the first cleared bit in a memory region.
99 
 */
100 
unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
101 
{
102 
	unsigned long idx;
103 
 
104 
	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
105 
		if (addr[idx] != ~0UL)
106 
			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 
#ifndef find_last_bit
115 
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
116 
{
117 
	if (size) {
118 
		unsigned long val = BITMAP_LAST_WORD_MASK(size);
119 
		unsigned long idx = (size-1) / BITS_PER_LONG;
120 
 
121 
		do {
122 
			val &= addr[idx];
123 
			if (val)
124 
				return idx * BITS_PER_LONG + __fls(val);
125 
 
126 
			val = ~0ul;
127 
		} while (idx--);
128 
	}
129 
	return size;
130 
}
131 
EXPORT_SYMBOL(find_last_bit);
132 
#endif
133 
 
134 
#ifdef __BIG_ENDIAN
135 
 
136 
/* include/linux/byteorder does not support "unsigned long" type */
137 
static inline unsigned long ext2_swab(const unsigned long y)
138 
{
139 
#if BITS_PER_LONG == 64
140 
	return (unsigned long) __swab64((u64) y);
141 
#elif BITS_PER_LONG == 32
142 
	return (unsigned long) __swab32((u32) y);
143 
#else
144 
#error BITS_PER_LONG not defined
145 
#endif
146 
}
147 
 
148 
#if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
149 
static unsigned long _find_next_bit_le(const unsigned long *addr,
150 
		unsigned long nbits, unsigned long start, unsigned long invert)
151 
{
152 
	unsigned long tmp;
153 
 
154 
	if (!nbits || start >= nbits)
155 
		return nbits;
156 
 
157 
	tmp = addr[start / BITS_PER_LONG] ^ invert;
158 
 
159 
	/* Handle 1st word. */
160 
	tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
161 
	start = round_down(start, BITS_PER_LONG);
162 
 
163 
	while (!tmp) {
164 
		start += BITS_PER_LONG;
165 
		if (start >= nbits)
166 
			return nbits;
167 
 
168 
		tmp = addr[start / BITS_PER_LONG] ^ invert;
169 
	}
170 
 
171 
	return min(start + __ffs(ext2_swab(tmp)), nbits);
172 
}
173 
#endif
174 
 
175 
#ifndef find_next_zero_bit_le
176 
unsigned long find_next_zero_bit_le(const void *addr, unsigned
177 
		long size, unsigned long offset)
178 
{
179 
	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 
		long size, unsigned long offset)
187 
{
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 */