lib/bitmap.c

   1 /*
   2  * lib/bitmap.c
   3  * Helper functions for bitmap.h.
   4  *
   5  * This source code is licensed under the GNU General Public License,
   6  * Version 2.  See the file COPYING for more details.
   7  */
   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>
  14
  15 #define MAX_BITMAP_BITS 512U    /* for ia64 NR_CPUS maximum */
  16
  17 int bitmap_empty(const unsigned long *bitmap, int bits)
  18 {
  19         int k, lim = bits/BITS_PER_LONG;
  20         for (k = 0; k < lim; ++k)
  21                 if (bitmap[k])
  22                         return 0;
  23
  24         if (bits % BITS_PER_LONG)
  25                 if (bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
  26                         return 0;
  27
  28         return 1;
  29 }
  30 EXPORT_SYMBOL(bitmap_empty);
  31
  32 int bitmap_full(const unsigned long *bitmap, int bits)
  33 {
  34         int k, lim = bits/BITS_PER_LONG;
  35         for (k = 0; k < lim; ++k)
  36                 if (~bitmap[k])
  37                         return 0;
  38
  39         if (bits % BITS_PER_LONG)
  40                 if (~bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
  41                         return 0;
  42
  43         return 1;
  44 }
  45 EXPORT_SYMBOL(bitmap_full);
  46
  47 int bitmap_equal(const unsigned long *bitmap1,
  48                 unsigned long *bitmap2, int bits)
  49 {
  50         int k, lim = bits/BITS_PER_LONG;
  51         for (k = 0; k < lim; ++k)
  52                 if (bitmap1[k] != bitmap2[k])
  53                         return 0;
  54
  55         if (bits % BITS_PER_LONG)
  56                 if ((bitmap1[k] ^ bitmap2[k]) &
  57                                 ((1UL << (bits % BITS_PER_LONG)) - 1))
  58                         return 0;
  59
  60         return 1;
  61 }
  62 EXPORT_SYMBOL(bitmap_equal);
  63
  64 void bitmap_complement(unsigned long *bitmap, int bits)
  65 {
  66         int k;
  67         int nr = BITS_TO_LONGS(bits);
  68
  69         for (k = 0; k < nr; ++k)
  70                 bitmap[k] = ~bitmap[k];
  71 }
  72 EXPORT_SYMBOL(bitmap_complement);
  73
  74 void bitmap_shift_right(unsigned long *dst,
  75                         const unsigned long *src, int shift, int bits)
  76 {
  77         int k;
  78         DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);
  79
  80         BUG_ON(bits > MAX_BITMAP_BITS);
  81         bitmap_clear(__shr_tmp, bits);
  82         for (k = 0; k < bits - shift; ++k)
  83                 if (test_bit(k + shift, src))
  84                         set_bit(k, __shr_tmp);
  85         bitmap_copy(dst, __shr_tmp, bits);
  86 }
  87 EXPORT_SYMBOL(bitmap_shift_right);
  88
  89 void bitmap_shift_left(unsigned long *dst,
  90                         const unsigned long *src, int shift, int bits)
  91 {
  92         int k;
  93         DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);
  94
  95         BUG_ON(bits > MAX_BITMAP_BITS);
  96         bitmap_clear(__shl_tmp, bits);
  97         for (k = bits; k >= shift; --k)
  98                 if (test_bit(k - shift, src))
  99                         set_bit(k, __shl_tmp);
 100         bitmap_copy(dst, __shl_tmp, bits);
 101 }
 102 EXPORT_SYMBOL(bitmap_shift_left);
 103
 104 void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 105                                 const unsigned long *bitmap2, int bits)
 106 {
 107         int k;
 108         int nr = BITS_TO_LONGS(bits);
 109
 110         for (k = 0; k < nr; k++)
 111                 dst[k] = bitmap1[k] & bitmap2[k];
 112 }
 113 EXPORT_SYMBOL(bitmap_and);
 114
 115 void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 116                                 const unsigned long *bitmap2, int bits)
 117 {
 118         int k;
 119         int nr = BITS_TO_LONGS(bits);
 120
 121         for (k = 0; k < nr; k++)
 122                 dst[k] = bitmap1[k] | bitmap2[k];
 123 }
 124 EXPORT_SYMBOL(bitmap_or);
 125
 126 #if BITS_PER_LONG == 32
 127 int bitmap_weight(const unsigned long *bitmap, int bits)
 128 {
 129         int k, w = 0, lim = bits/BITS_PER_LONG;
 130
 131         for (k = 0; k < lim; k++)
 132                 w += hweight32(bitmap[k]);
 133
 134         if (bits % BITS_PER_LONG)
 135                 w += hweight32(bitmap[k] &
 136                                 ((1UL << (bits % BITS_PER_LONG)) - 1));
 137
 138         return w;
 139 }
 140 #else
 141 int bitmap_weight(const unsigned long *bitmap, int bits)
 142 {
 143         int k, w = 0, lim = bits/BITS_PER_LONG;
 144
 145         for (k = 0; k < lim; k++)
 146                 w += hweight64(bitmap[k]);
 147
 148         if (bits % BITS_PER_LONG)
 149                 w += hweight64(bitmap[k] &
 150                                 ((1UL << (bits % BITS_PER_LONG)) - 1));
 151
 152         return w;
 153 }
 154 #endif
 155 EXPORT_SYMBOL(bitmap_weight);
 156
 157 /*
 158  * Bitmap printing & parsing functions: first version by Bill Irwin,
 159  * second version by Paul Jackson, third by Joe Korty.
 160  */
 161
 162 #define CHUNKSZ                         32
 163 #define nbits_to_hold_value(val)        fls(val)
 164 #define roundup_power2(val,modulus)     (((val) + (modulus) - 1) & ~((modulus) - 1))
 165 #define unhex(c)                        (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
 166
 167 /**
 168  * bitmap_scnprintf - convert bitmap to an ASCII hex string.
 169  * @buf: byte buffer into which string is placed
 170  * @buflen: reserved size of @buf, in bytes
 171  * @maskp: pointer to bitmap to convert
 172  * @nmaskbits: size of bitmap, in bits
 173  *
 174  * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into
 175  * comma-separated sets of eight digits per set.
 176  */
 177 int bitmap_scnprintf(char *buf, unsigned int buflen,
 178         const unsigned long *maskp, int nmaskbits)
 179 {
 180         int i, word, bit, len = 0;
 181         unsigned long val;
 182         const char *sep = "";
 183         int chunksz;
 184         u32 chunkmask;
 185
 186         chunksz = nmaskbits & (CHUNKSZ - 1);
 187         if (chunksz == 0)
 188                 chunksz = CHUNKSZ;
 189
 190         i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
 191         for (; i >= 0; i -= CHUNKSZ) {
 192                 chunkmask = ((1ULL << chunksz) - 1);
 193                 word = i / BITS_PER_LONG;
 194                 bit = i % BITS_PER_LONG;
 195                 val = (maskp[word] >> bit) & chunkmask;
 196                 len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
 197                         (chunksz+3)/4, val);
 198                 chunksz = CHUNKSZ;
 199                 sep = ",";
 200         }
 201         return len;
 202 }
 203 EXPORT_SYMBOL(bitmap_scnprintf);
 204
 205 /**
 206  * bitmap_parse - convert an ASCII hex string into a bitmap.
 207  * @buf: pointer to buffer in user space containing string.
 208  * @buflen: buffer size in bytes.  If string is smaller than this
 209  *    then it must be terminated with a \0.
 210  * @maskp: pointer to bitmap array that will contain result.
 211  * @nmaskbits: size of bitmap, in bits.
 212  *
 213  * Commas group hex digits into chunks.  Each chunk defines exactly 32
 214  * bits of the resultant bitmask.  No chunk may specify a value larger
 215  * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
 216  * then leading 0-bits are prepended.  -EINVAL is returned for illegal
 217  * characters and for grouping errors such as "1,,5", ",44", "," and "".
 218  * Leading and trailing whitespace accepted, but not embedded whitespace.
 219  */
 220 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
 221         unsigned long *maskp, int nmaskbits)
 222 {
 223         int c, old_c, totaldigits, ndigits, nchunks, nbits;
 224         u32 chunk;
 225
 226         bitmap_clear(maskp, nmaskbits);
 227
 228         nchunks = nbits = totaldigits = c = 0;
 229         do {
 230                 chunk = ndigits = 0;
 231
 232                 /* Get the next chunk of the bitmap */
 233                 while (ubuflen) {
 234                         old_c = c;
 235                         if (get_user(c, ubuf++))
 236                                 return -EFAULT;
 237                         ubuflen--;
 238                         if (isspace(c))
 239                                 continue;
 240
 241                         /*
 242                          * If the last character was a space and the current
 243                          * character isn't '\0', we've got embedded whitespace.
 244                          * This is a no-no, so throw an error.
 245                          */
 246                         if (totaldigits && c && isspace(old_c))
 247                                 return -EINVAL;
 248
 249                         /* A '\0' or a ',' signal the end of the chunk */
 250                         if (c == '\0' || c == ',')
 251                                 break;
 252
 253                         if (!isxdigit(c))
 254                                 return -EINVAL;
 255
 256                         /*
 257                          * Make sure there are at least 4 free bits in 'chunk'.
 258                          * If not, this hexdigit will overflow 'chunk', so
 259                          * throw an error.
 260                          */
 261                         if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
 262                                 return -EOVERFLOW;
 263
 264                         chunk = (chunk << 4) | unhex(c);
 265                         ndigits++; totaldigits++;
 266                 }
 267                 if (ndigits == 0)
 268                         return -EINVAL;
 269                 if (nchunks == 0 && chunk == 0)
 270                         continue;
 271
 272                 bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
 273                 *maskp |= chunk;
 274                 nchunks++;
 275                 nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
 276                 if (nbits > nmaskbits)
 277                         return -EOVERFLOW;
 278         } while (ubuflen && c == ',');
 279
 280         return 0;
 281 }
 282 EXPORT_SYMBOL(bitmap_parse);