1 // SPDX-License-Identifier: GPL-2.0+
2 #ifndef __LINUX_BITMAP_H
3 #define __LINUX_BITMAP_H
6 #include <linux/types.h>
7 #include <linux/bitops.h>
8 #include <linux/string.h>
10 #ifdef __LITTLE_ENDIAN
11 #define BITMAP_MEM_ALIGNMENT 8
13 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
15 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
17 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
18 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
19 #define small_const_nbits(nbits) \
20 (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
23 __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
24 const unsigned long *bitmap2, unsigned int bits)
27 unsigned int nr = BITS_TO_LONGS(bits);
29 for (k = 0; k < nr; k++)
30 dst[k] = bitmap1[k] | bitmap2[k];
34 __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
36 unsigned int k, lim = bits / BITS_PER_LONG;
39 for (k = 0; k < lim; k++)
40 w += hweight_long(bitmap[k]);
42 if (bits % BITS_PER_LONG)
43 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
49 __bitmap_set(unsigned long *map, unsigned int start, int len)
51 unsigned long *p = map + BIT_WORD(start);
52 const unsigned int size = start + len;
53 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
54 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
56 while (len - bits_to_set >= 0) {
59 bits_to_set = BITS_PER_LONG;
64 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
70 __bitmap_clear(unsigned long *map, unsigned int start, int len)
72 unsigned long *p = map + BIT_WORD(start);
73 const unsigned int size = start + len;
74 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
75 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
77 while (len - bits_to_clear >= 0) {
80 bits_to_clear = BITS_PER_LONG;
85 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
90 static inline void bitmap_zero(unsigned long *dst, int nbits)
92 if (small_const_nbits(nbits)) {
95 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
101 static inline unsigned long
102 find_next_bit(const unsigned long *addr, unsigned long size,
103 unsigned long offset)
105 const unsigned long *p = addr + BIT_WORD(offset);
106 unsigned long result = offset & ~(BITS_PER_LONG - 1);
112 offset %= BITS_PER_LONG;
115 tmp &= (~0UL << offset);
116 if (size < BITS_PER_LONG)
120 size -= BITS_PER_LONG;
121 result += BITS_PER_LONG;
123 while (size & ~(BITS_PER_LONG - 1)) {
127 result += BITS_PER_LONG;
128 size -= BITS_PER_LONG;
135 tmp &= (~0UL >> (BITS_PER_LONG - size));
136 if (tmp == 0UL) /* Are any bits set? */
137 return result + size; /* Nope. */
139 return result + __ffs(tmp);
143 * Find the first set bit in a memory region.
145 static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
149 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
151 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
157 #define for_each_set_bit(bit, addr, size) \
158 for ((bit) = find_first_bit((addr), (size)); \
160 (bit) = find_next_bit((addr), (size), (bit) + 1))
162 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
164 if (small_const_nbits(nbits)) {
167 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
169 memset(dst, 0xff, len);
173 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
174 const unsigned long *src2, unsigned int nbits)
176 if (small_const_nbits(nbits))
177 *dst = *src1 | *src2;
179 __bitmap_or(dst, src1, src2, nbits);
182 static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
184 if (small_const_nbits(nbits))
185 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
186 return __bitmap_weight(src, nbits);
189 static inline void bitmap_set(unsigned long *map, unsigned int start,
192 if (__builtin_constant_p(nbits) && nbits == 1)
193 __set_bit(start, map);
194 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
195 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
196 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
197 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
198 memset((char *)map + start / 8, 0xff, nbits / 8);
200 __bitmap_set(map, start, nbits);
203 static inline void bitmap_clear(unsigned long *map, unsigned int start,
206 if (__builtin_constant_p(nbits) && nbits == 1)
207 __clear_bit(start, map);
208 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
209 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
210 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
211 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
212 memset((char *)map + start / 8, 0, nbits / 8);
214 __bitmap_clear(map, start, nbits);
217 #endif /* __LINUX_BITMAP_H */