xref: /openbmc/qemu/include/qemu/bitmap.h (revision 5e9efe31)
1 /*
2  * Bitmap Module
3  *
4  * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
5  *
6  * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
7  *
8  * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
9  * See the COPYING.LIB file in the top-level directory.
10  */
11 
12 #ifndef BITMAP_H
13 #define BITMAP_H
14 
15 
16 #include "qemu/bitops.h"
17 
18 /*
19  * The available bitmap operations and their rough meaning in the
20  * case that the bitmap is a single unsigned long are thus:
21  *
22  * Note that nbits should be always a compile time evaluable constant.
23  * Otherwise many inlines will generate horrible code.
24  *
25  * bitmap_zero(dst, nbits)                      *dst = 0UL
26  * bitmap_fill(dst, nbits)                      *dst = ~0UL
27  * bitmap_copy(dst, src, nbits)                 *dst = *src
28  * bitmap_and(dst, src1, src2, nbits)           *dst = *src1 & *src2
29  * bitmap_or(dst, src1, src2, nbits)            *dst = *src1 | *src2
30  * bitmap_xor(dst, src1, src2, nbits)           *dst = *src1 ^ *src2
31  * bitmap_andnot(dst, src1, src2, nbits)        *dst = *src1 & ~(*src2)
32  * bitmap_complement(dst, src, nbits)           *dst = ~(*src)
33  * bitmap_equal(src1, src2, nbits)              Are *src1 and *src2 equal?
34  * bitmap_intersects(src1, src2, nbits)         Do *src1 and *src2 overlap?
35  * bitmap_empty(src, nbits)                     Are all bits zero in *src?
36  * bitmap_full(src, nbits)                      Are all bits set in *src?
37  * bitmap_set(dst, pos, nbits)                  Set specified bit area
38  * bitmap_set_atomic(dst, pos, nbits)           Set specified bit area with atomic ops
39  * bitmap_clear(dst, pos, nbits)                Clear specified bit area
40  * bitmap_test_and_clear_atomic(dst, pos, nbits)    Test and clear area
41  * bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
42  * bitmap_to_le(dst, src, nbits)      Convert bitmap to little endian
43  * bitmap_from_le(dst, src, nbits)    Convert bitmap from little endian
44  * bitmap_copy_with_src_offset(dst, src, offset, nbits)
45  *                                    *dst = *src (with an offset into src)
46  * bitmap_copy_with_dst_offset(dst, src, offset, nbits)
47  *                                    *dst = *src (with an offset into dst)
48  */
49 
50 /*
51  * Also the following operations apply to bitmaps.
52  *
53  * set_bit(bit, addr)               *addr |= bit
54  * clear_bit(bit, addr)             *addr &= ~bit
55  * change_bit(bit, addr)            *addr ^= bit
56  * test_bit(bit, addr)              Is bit set in *addr?
57  * test_and_set_bit(bit, addr)      Set bit and return old value
58  * test_and_clear_bit(bit, addr)    Clear bit and return old value
59  * test_and_change_bit(bit, addr)   Change bit and return old value
60  * find_first_zero_bit(addr, nbits) Position first zero bit in *addr
61  * find_first_bit(addr, nbits)      Position first set bit in *addr
62  * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
63  * find_next_bit(addr, nbits, bit)  Position next set bit in *addr >= bit
64  */
65 
66 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
67 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
68 
69 #define DECLARE_BITMAP(name,bits)                  \
70         unsigned long name[BITS_TO_LONGS(bits)]
71 
72 #define small_nbits(nbits)                      \
73         ((nbits) <= BITS_PER_LONG)
74 
75 int slow_bitmap_empty(const unsigned long *bitmap, long bits);
76 int slow_bitmap_full(const unsigned long *bitmap, long bits);
77 int slow_bitmap_equal(const unsigned long *bitmap1,
78                       const unsigned long *bitmap2, long bits);
79 void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
80                             long bits);
81 int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
82                     const unsigned long *bitmap2, long bits);
83 void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
84                     const unsigned long *bitmap2, long bits);
85 void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
86                      const unsigned long *bitmap2, long bits);
87 int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
88                        const unsigned long *bitmap2, long bits);
89 int slow_bitmap_intersects(const unsigned long *bitmap1,
90                            const unsigned long *bitmap2, long bits);
91 long slow_bitmap_count_one(const unsigned long *bitmap, long nbits);
92 
bitmap_try_new(long nbits)93 static inline unsigned long *bitmap_try_new(long nbits)
94 {
95     long nelem = BITS_TO_LONGS(nbits);
96     return g_try_new0(unsigned long, nelem);
97 }
98 
bitmap_new(long nbits)99 static inline unsigned long *bitmap_new(long nbits)
100 {
101     long nelem = BITS_TO_LONGS(nbits);
102     return g_new0(unsigned long, nelem);
103 }
104 
bitmap_zero(unsigned long * dst,long nbits)105 static inline void bitmap_zero(unsigned long *dst, long nbits)
106 {
107     if (small_nbits(nbits)) {
108         *dst = 0UL;
109     } else {
110         long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
111         memset(dst, 0, len);
112     }
113 }
114 
bitmap_fill(unsigned long * dst,long nbits)115 static inline void bitmap_fill(unsigned long *dst, long nbits)
116 {
117     size_t nlongs = BITS_TO_LONGS(nbits);
118     if (!small_nbits(nbits)) {
119         long len = (nlongs - 1) * sizeof(unsigned long);
120         memset(dst, 0xff,  len);
121     }
122     dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
123 }
124 
bitmap_copy(unsigned long * dst,const unsigned long * src,long nbits)125 static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
126                                long nbits)
127 {
128     if (small_nbits(nbits)) {
129         *dst = *src;
130     } else {
131         long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
132         memcpy(dst, src, len);
133     }
134 }
135 
bitmap_and(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,long nbits)136 static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
137                              const unsigned long *src2, long nbits)
138 {
139     if (small_nbits(nbits)) {
140         return (*dst = *src1 & *src2) != 0;
141     }
142     return slow_bitmap_and(dst, src1, src2, nbits);
143 }
144 
bitmap_or(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,long nbits)145 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
146                              const unsigned long *src2, long nbits)
147 {
148     if (small_nbits(nbits)) {
149         *dst = *src1 | *src2;
150     } else {
151         slow_bitmap_or(dst, src1, src2, nbits);
152     }
153 }
154 
bitmap_xor(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,long nbits)155 static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
156                               const unsigned long *src2, long nbits)
157 {
158     if (small_nbits(nbits)) {
159         *dst = *src1 ^ *src2;
160     } else {
161         slow_bitmap_xor(dst, src1, src2, nbits);
162     }
163 }
164 
bitmap_andnot(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,long nbits)165 static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
166                                 const unsigned long *src2, long nbits)
167 {
168     if (small_nbits(nbits)) {
169         return (*dst = *src1 & ~(*src2)) != 0;
170     }
171     return slow_bitmap_andnot(dst, src1, src2, nbits);
172 }
173 
bitmap_complement(unsigned long * dst,const unsigned long * src,long nbits)174 static inline void bitmap_complement(unsigned long *dst,
175                                      const unsigned long *src,
176                                      long nbits)
177 {
178     if (small_nbits(nbits)) {
179         *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
180     } else {
181         slow_bitmap_complement(dst, src, nbits);
182     }
183 }
184 
bitmap_equal(const unsigned long * src1,const unsigned long * src2,long nbits)185 static inline int bitmap_equal(const unsigned long *src1,
186                                const unsigned long *src2, long nbits)
187 {
188     if (small_nbits(nbits)) {
189         return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
190     } else {
191         return slow_bitmap_equal(src1, src2, nbits);
192     }
193 }
194 
bitmap_empty(const unsigned long * src,long nbits)195 static inline int bitmap_empty(const unsigned long *src, long nbits)
196 {
197     if (small_nbits(nbits)) {
198         return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
199     } else {
200         return slow_bitmap_empty(src, nbits);
201     }
202 }
203 
bitmap_full(const unsigned long * src,long nbits)204 static inline int bitmap_full(const unsigned long *src, long nbits)
205 {
206     if (small_nbits(nbits)) {
207         return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
208     } else {
209         return slow_bitmap_full(src, nbits);
210     }
211 }
212 
bitmap_intersects(const unsigned long * src1,const unsigned long * src2,long nbits)213 static inline int bitmap_intersects(const unsigned long *src1,
214                                     const unsigned long *src2, long nbits)
215 {
216     if (small_nbits(nbits)) {
217         return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
218     } else {
219         return slow_bitmap_intersects(src1, src2, nbits);
220     }
221 }
222 
bitmap_count_one(const unsigned long * bitmap,long nbits)223 static inline long bitmap_count_one(const unsigned long *bitmap, long nbits)
224 {
225     if (unlikely(!nbits)) {
226         return 0;
227     }
228 
229     if (small_nbits(nbits)) {
230         return ctpopl(*bitmap & BITMAP_LAST_WORD_MASK(nbits));
231     } else {
232         return slow_bitmap_count_one(bitmap, nbits);
233     }
234 }
235 
bitmap_count_one_with_offset(const unsigned long * bitmap,long offset,long nbits)236 static inline long bitmap_count_one_with_offset(const unsigned long *bitmap,
237                                                 long offset, long nbits)
238 {
239     long aligned_offset = QEMU_ALIGN_DOWN(offset, BITS_PER_LONG);
240     long redundant_bits = offset - aligned_offset;
241     long bits_to_count = nbits + redundant_bits;
242     const unsigned long *bitmap_start = bitmap +
243                                         aligned_offset / BITS_PER_LONG;
244 
245     return bitmap_count_one(bitmap_start, bits_to_count) -
246            bitmap_count_one(bitmap_start, redundant_bits);
247 }
248 
249 void bitmap_set(unsigned long *map, long i, long len);
250 void bitmap_set_atomic(unsigned long *map, long i, long len);
251 void bitmap_clear(unsigned long *map, long start, long nr);
252 bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr);
253 bool bitmap_test_and_clear(unsigned long *map, long start, long nr);
254 void bitmap_copy_and_clear_atomic(unsigned long *dst, unsigned long *src,
255                                   long nr);
256 unsigned long bitmap_find_next_zero_area(unsigned long *map,
257                                          unsigned long size,
258                                          unsigned long start,
259                                          unsigned long nr,
260                                          unsigned long align_mask);
261 
bitmap_zero_extend(unsigned long * old,long old_nbits,long new_nbits)262 static inline unsigned long *bitmap_zero_extend(unsigned long *old,
263                                                 long old_nbits, long new_nbits)
264 {
265     long new_nelem = BITS_TO_LONGS(new_nbits);
266     unsigned long *ptr = g_renew(unsigned long, old, new_nelem);
267     bitmap_clear(ptr, old_nbits, new_nbits - old_nbits);
268     return ptr;
269 }
270 
271 void bitmap_to_le(unsigned long *dst, const unsigned long *src,
272                   long nbits);
273 void bitmap_from_le(unsigned long *dst, const unsigned long *src,
274                     long nbits);
275 
276 void bitmap_copy_with_src_offset(unsigned long *dst, const unsigned long *src,
277                                  unsigned long offset, unsigned long nbits);
278 void bitmap_copy_with_dst_offset(unsigned long *dst, const unsigned long *src,
279                                  unsigned long shift, unsigned long nbits);
280 
281 #endif /* BITMAP_H */
282