1 /* $NetBSD: bitmap.h,v 1.13 2021/12/19 12:21:30 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2018 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #ifndef _LINUX_BITMAP_H_
33 #define _LINUX_BITMAP_H_
34
35 #include <sys/param.h>
36 #include <sys/types.h>
37 #include <sys/systm.h>
38
39 #include <linux/slab.h>
40
41 /*
42 * bitmap_zero(bitmap, nbits)
43 *
44 * Zero a bitmap that was allocated to have nbits bits. Yes, this
45 * zeros bits past nbits.
46 */
47 static inline void
bitmap_zero(unsigned long * bitmap,size_t nbits)48 bitmap_zero(unsigned long *bitmap, size_t nbits)
49 {
50 const size_t bpl = NBBY * sizeof(*bitmap);
51 size_t n = howmany(nbits, bpl);
52
53 memset(bitmap, 0, n * sizeof(*bitmap));
54 }
55
56 /*
57 * bitmap_empty(bitmap, nbits)
58 *
59 * Return true if all bits at 0, 1, 2, ..., nbits-2, nbits-1 are
60 * 0, or false if any of them is 1.
61 */
62 static inline bool
bitmap_empty(const unsigned long * bitmap,size_t nbits)63 bitmap_empty(const unsigned long *bitmap, size_t nbits)
64 {
65 const size_t bpl = NBBY * sizeof(*bitmap);
66
67 for (; nbits >= bpl; nbits -= bpl) {
68 if (*bitmap++)
69 return false;
70 }
71
72 if (nbits) {
73 if (*bitmap & ~(~0UL << nbits))
74 return false;
75 }
76
77 return true;
78 }
79
80 /*
81 * bitmap_weight(bitmap, nbits)
82 *
83 * Compute the number of 1 bits at 0, 1, 2, ..., nbits-2, nbits-1.
84 */
85 static inline int
bitmap_weight(const unsigned long * bitmap,size_t nbits)86 bitmap_weight(const unsigned long *bitmap, size_t nbits)
87 {
88 const size_t bpl = NBBY * sizeof(*bitmap);
89 int weight = 0;
90
91 for (; nbits >= bpl; nbits -= bpl)
92 weight += popcountl(*bitmap++);
93 if (nbits)
94 weight += popcountl(*bitmap & ~(~0UL << nbits));
95
96 return weight;
97 }
98
99 /*
100 * bitmap_set(bitmap, startbit, nbits)
101 *
102 * Set bits at startbit, startbit+1, ..., startbit+nbits-2,
103 * startbit+nbits-1 to 1.
104 */
105 static inline void
bitmap_set(unsigned long * bitmap,size_t startbit,size_t nbits)106 bitmap_set(unsigned long *bitmap, size_t startbit, size_t nbits)
107 {
108 const size_t bpl = NBBY * sizeof(*bitmap);
109 unsigned long *p = bitmap + startbit/bpl;
110 unsigned initial = startbit%bpl;
111
112 /* Handle an initial odd word if any. */
113 if (initial) {
114 /* Does the whole thing fit in a single word? */
115 if (nbits <= bpl - initial) {
116 /* Yes: just set nbits starting at initial. */
117 *p |= ~(~0ULL << nbits) << initial;
118 return;
119 }
120 /* Nope: set all bits above initial, and advance. */
121 *p++ |= ~0ULL << initial;
122 nbits -= bpl - initial;
123 }
124
125 /* Set the middle part to all bits 1. */
126 for (; nbits >= bpl; nbits -= bpl)
127 *p++ = ~0UL;
128
129 /* Handle a final odd word if any by setting its low nbits. */
130 if (nbits)
131 *p |= ~(~0ULL << nbits);
132 }
133
134 /*
135 * bitmap_clear(bitmap, startbit, nbits)
136 *
137 * Clear bits at startbit, startbit+1, ..., startbit+nbits-2,
138 * startbit+nbits-1, replacing them by 0.
139 */
140 static inline void
bitmap_clear(unsigned long * bitmap,size_t startbit,size_t nbits)141 bitmap_clear(unsigned long *bitmap, size_t startbit, size_t nbits)
142 {
143 const size_t bpl = NBBY * sizeof(*bitmap);
144 unsigned long *p = bitmap + startbit/bpl;
145 unsigned initial = startbit%bpl;
146
147 /* Handle an initial odd word if any. */
148 if (initial) {
149 /* Does the whole thing fit in a single word? */
150 if (nbits <= bpl - initial) {
151 /* Yes: just clear nbits starting at initial. */
152 *p &= ~(~(~0ULL << nbits) << initial);
153 return;
154 }
155 /* Nope: clear all bits above initial, and advance. */
156 *p++ &= ~(~0ULL << initial);
157 nbits -= bpl - initial;
158 }
159
160 /* Zero the middle part. */
161 for (; nbits >= bpl; nbits -= bpl)
162 *p++ = 0UL;
163
164 /* Handle a final odd word if any by clearing its low nbits. */
165 if (nbits)
166 *p &= ~0ULL << nbits;
167 }
168
169 /*
170 * bitmap_copy(dst, src, nbits)
171 *
172 * Copy the bitmap from src to dst. dst and src may alias (but
173 * why would you bother?).
174 */
175 static inline void
bitmap_copy(unsigned long * dst,const unsigned long * src,size_t nbits)176 bitmap_copy(unsigned long *dst, const unsigned long *src, size_t nbits)
177 {
178 const size_t bpl = NBBY * sizeof(unsigned long);
179 size_t n = howmany(nbits, bpl);
180
181 while (n --> 0)
182 *dst++ = *src++;
183 }
184
185 /*
186 * bitmap_complement(dst, src, nbits)
187 *
188 * Set dst to the the bitwise NOT of src. dst and src may alias.
189 */
190 static inline void
bitmap_complement(unsigned long * dst,const unsigned long * src,size_t nbits)191 bitmap_complement(unsigned long *dst, const unsigned long *src, size_t nbits)
192 {
193 const size_t bpl = NBBY * sizeof(unsigned long);
194 size_t n = howmany(nbits, bpl);
195
196 while (n --> 0)
197 *dst++ = ~*src++;
198 }
199
200 /*
201 * bitmap_and(dst, src1, src2, nbits)
202 *
203 * Set dst to be the bitwise AND of src1 and src2, all bitmaps
204 * allocated to have nbits bits. Yes, this modifies bits past
205 * nbits. Any pair of {dst, src1, src2} may be aliases.
206 */
207 static inline void
bitmap_and(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,size_t nbits)208 bitmap_and(unsigned long *dst, const unsigned long *src1,
209 const unsigned long *src2, size_t nbits)
210 {
211 const size_t bpl = NBBY * sizeof(unsigned long);
212 size_t n = howmany(nbits, bpl);
213
214 while (n --> 0)
215 *dst++ = *src1++ & *src2++;
216 }
217
218 /*
219 * bitmap_andnot(dst, src1, src2, nbits)
220 *
221 * Set dst to be the bitwise AND of src1 and ~src2, all bitmaps
222 * allocated to have nbits bits. Yes, this modifies bits past
223 * nbits. Any pair of {dst, src1, src2} may be aliases.
224 */
225 static inline void
bitmap_andnot(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,size_t nbits)226 bitmap_andnot(unsigned long *dst, const unsigned long *src1,
227 const unsigned long *src2, size_t nbits)
228 {
229 const size_t bpl = NBBY * sizeof(unsigned long);
230 size_t n = howmany(nbits, bpl);
231
232 while (n --> 0)
233 *dst++ = *src1++ & ~*src2++;
234 }
235
236 /*
237 * bitmap_or(dst, src1, src2, nbits)
238 *
239 * Set dst to be the bitwise inclusive-OR of src1 and src2, all
240 * bitmaps allocated to have nbits bits. Yes, this modifies bits
241 * past nbits. Any pair of {dst, src1, src2} may be aliases.
242 */
243 static inline void
bitmap_or(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,size_t nbits)244 bitmap_or(unsigned long *dst, const unsigned long *src1,
245 const unsigned long *src2, size_t nbits)
246 {
247 const size_t bpl = NBBY * sizeof(unsigned long);
248 size_t n = howmany(nbits, bpl);
249
250 while (n --> 0)
251 *dst++ = *src1++ | *src2++;
252 }
253
254 static inline unsigned long *
bitmap_zalloc(size_t nbits,gfp_t gfp)255 bitmap_zalloc(size_t nbits, gfp_t gfp)
256 {
257 const size_t bpl = NBBY * sizeof(unsigned long);
258 size_t n = howmany(nbits, bpl);
259
260 return kcalloc(n, sizeof(unsigned long), gfp);
261 }
262
263 static inline void
bitmap_free(unsigned long * bitmap)264 bitmap_free(unsigned long *bitmap)
265 {
266
267 kfree(bitmap);
268 }
269
270 #endif /* _LINUX_BITMAP_H_ */
271