3 * Helper functions for bitmap.h.
5 * This source code is licensed under the GNU General Public License,
6 * Version 2. See the file COPYING for more details.
8 #include <linux/module.h>
9 #include <linux/ctype.h>
10 #include <linux/errno.h>
11 #include <linux/bitmap.h>
12 #include <asm/bitops.h>
13 #include <asm/uaccess.h>
15 int bitmap_empty(const unsigned long *bitmap, int bits)
17 int k, lim = bits/BITS_PER_LONG;
18 for (k = 0; k < lim; ++k)
22 if (bits % BITS_PER_LONG)
23 if (bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
28 EXPORT_SYMBOL(bitmap_empty);
30 int bitmap_full(const unsigned long *bitmap, int bits)
32 int k, lim = bits/BITS_PER_LONG;
33 for (k = 0; k < lim; ++k)
37 if (bits % BITS_PER_LONG)
38 if (~bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
43 EXPORT_SYMBOL(bitmap_full);
45 int bitmap_equal(const unsigned long *bitmap1,
46 unsigned long *bitmap2, int bits)
48 int k, lim = bits/BITS_PER_LONG;
49 for (k = 0; k < lim; ++k)
50 if (bitmap1[k] != bitmap2[k])
53 if (bits % BITS_PER_LONG)
54 if ((bitmap1[k] ^ bitmap2[k]) &
55 ((1UL << (bits % BITS_PER_LONG)) - 1))
60 EXPORT_SYMBOL(bitmap_equal);
62 void bitmap_complement(unsigned long *bitmap, int bits)
65 int nr = BITS_TO_LONGS(bits);
67 for (k = 0; k < nr; ++k)
68 bitmap[k] = ~bitmap[k];
70 EXPORT_SYMBOL(bitmap_complement);
73 * bitmap_shift_right - logical right shift of the bits in a bitmap
74 * @dst - destination bitmap
75 * @src - source bitmap
76 * @nbits - shift by this many bits
77 * @bits - bitmap size, in bits
79 * Shifting right (dividing) means moving bits in the MS -> LS bit
80 * direction. Zeros are fed into the vacated MS positions and the
81 * LS bits shifted off the bottom are lost.
83 void bitmap_shift_right(unsigned long *dst,
84 const unsigned long *src, int shift, int bits)
86 int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
87 int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
88 unsigned long mask = (1UL << left) - 1;
89 for (k = 0; off + k < lim; ++k) {
90 unsigned long upper, lower;
93 * If shift is not word aligned, take lower rem bits of
94 * word above and make them the top rem bits of result.
96 if (!rem || off + k + 1 >= lim)
99 upper = src[off + k + 1];
100 if (off + k + 1 == lim - 1 && left)
103 lower = src[off + k];
104 if (left && off + k == lim - 1)
106 dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
107 if (left && k == lim - 1)
111 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
113 EXPORT_SYMBOL(bitmap_shift_right);
116 * bitmap_shift_left - logical left shift of the bits in a bitmap
117 * @dst - destination bitmap
118 * @src - source bitmap
119 * @nbits - shift by this many bits
120 * @bits - bitmap size, in bits
122 * Shifting left (multiplying) means moving bits in the LS -> MS
123 * direction. Zeros are fed into the vacated LS bit positions
124 * and those MS bits shifted off the top are lost.
126 void bitmap_shift_left(unsigned long *dst,
127 const unsigned long *src, int shift, int bits)
129 int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
130 int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
131 for (k = lim - off - 1; k >= 0; --k) {
132 unsigned long upper, lower;
135 * If shift is not word aligned, take upper rem bits of
136 * word below and make them the bottom rem bits of result.
143 if (left && k == lim - 1)
144 upper &= (1UL << left) - 1;
145 dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem;
146 if (left && k + off == lim - 1)
147 dst[k + off] &= (1UL << left) - 1;
150 memset(dst, 0, off*sizeof(unsigned long));
152 EXPORT_SYMBOL(bitmap_shift_left);
154 void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
155 const unsigned long *bitmap2, int bits)
158 int nr = BITS_TO_LONGS(bits);
160 for (k = 0; k < nr; k++)
161 dst[k] = bitmap1[k] & bitmap2[k];
163 EXPORT_SYMBOL(bitmap_and);
165 void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
166 const unsigned long *bitmap2, int bits)
169 int nr = BITS_TO_LONGS(bits);
171 for (k = 0; k < nr; k++)
172 dst[k] = bitmap1[k] | bitmap2[k];
174 EXPORT_SYMBOL(bitmap_or);
176 #if BITS_PER_LONG == 32
177 int bitmap_weight(const unsigned long *bitmap, int bits)
179 int k, w = 0, lim = bits/BITS_PER_LONG;
181 for (k = 0; k < lim; k++)
182 w += hweight32(bitmap[k]);
184 if (bits % BITS_PER_LONG)
185 w += hweight32(bitmap[k] &
186 ((1UL << (bits % BITS_PER_LONG)) - 1));
191 int bitmap_weight(const unsigned long *bitmap, int bits)
193 int k, w = 0, lim = bits/BITS_PER_LONG;
195 for (k = 0; k < lim; k++)
196 w += hweight64(bitmap[k]);
198 if (bits % BITS_PER_LONG)
199 w += hweight64(bitmap[k] &
200 ((1UL << (bits % BITS_PER_LONG)) - 1));
205 EXPORT_SYMBOL(bitmap_weight);
208 * Bitmap printing & parsing functions: first version by Bill Irwin,
209 * second version by Paul Jackson, third by Joe Korty.
213 #define nbits_to_hold_value(val) fls(val)
214 #define roundup_power2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
215 #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
218 * bitmap_scnprintf - convert bitmap to an ASCII hex string.
219 * @buf: byte buffer into which string is placed
220 * @buflen: reserved size of @buf, in bytes
221 * @maskp: pointer to bitmap to convert
222 * @nmaskbits: size of bitmap, in bits
224 * Exactly @nmaskbits bits are displayed. Hex digits are grouped into
225 * comma-separated sets of eight digits per set.
227 int bitmap_scnprintf(char *buf, unsigned int buflen,
228 const unsigned long *maskp, int nmaskbits)
230 int i, word, bit, len = 0;
232 const char *sep = "";
236 chunksz = nmaskbits & (CHUNKSZ - 1);
240 i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
241 for (; i >= 0; i -= CHUNKSZ) {
242 chunkmask = ((1ULL << chunksz) - 1);
243 word = i / BITS_PER_LONG;
244 bit = i % BITS_PER_LONG;
245 val = (maskp[word] >> bit) & chunkmask;
246 len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
253 EXPORT_SYMBOL(bitmap_scnprintf);
256 * bitmap_parse - convert an ASCII hex string into a bitmap.
257 * @buf: pointer to buffer in user space containing string.
258 * @buflen: buffer size in bytes. If string is smaller than this
259 * then it must be terminated with a \0.
260 * @maskp: pointer to bitmap array that will contain result.
261 * @nmaskbits: size of bitmap, in bits.
263 * Commas group hex digits into chunks. Each chunk defines exactly 32
264 * bits of the resultant bitmask. No chunk may specify a value larger
265 * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
266 * then leading 0-bits are prepended. -EINVAL is returned for illegal
267 * characters and for grouping errors such as "1,,5", ",44", "," and "".
268 * Leading and trailing whitespace accepted, but not embedded whitespace.
270 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
271 unsigned long *maskp, int nmaskbits)
273 int c, old_c, totaldigits, ndigits, nchunks, nbits;
276 bitmap_zero(maskp, nmaskbits);
278 nchunks = nbits = totaldigits = c = 0;
282 /* Get the next chunk of the bitmap */
285 if (get_user(c, ubuf++))
292 * If the last character was a space and the current
293 * character isn't '\0', we've got embedded whitespace.
294 * This is a no-no, so throw an error.
296 if (totaldigits && c && isspace(old_c))
299 /* A '\0' or a ',' signal the end of the chunk */
300 if (c == '\0' || c == ',')
307 * Make sure there are at least 4 free bits in 'chunk'.
308 * If not, this hexdigit will overflow 'chunk', so
311 if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
314 chunk = (chunk << 4) | unhex(c);
315 ndigits++; totaldigits++;
319 if (nchunks == 0 && chunk == 0)
322 bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
325 nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
326 if (nbits > nmaskbits)
328 } while (ubuflen && c == ',');
332 EXPORT_SYMBOL(bitmap_parse);