[PATCH] bitmap parsing/printing routines, version 4

From: Joe Korty <joe.korty@ccur.com>

1) the version in 2.6.1 is broken, doesn't work on 64bit big endian
   machines at all.  This needed fixing.  I thought it best to fix by
   rewriting the printer/parser with an algorithm that is naturally endian &
   sizeof(long) resistant.

2) I wanted all digits to print, eg, 0000ffff,00000004 not ffff,4.

3) I wanted exactly NR_CPUS bits to print (or whatever the bitmap size is
   in bits, and not have what is displayed rounded up to the nearest full
   byte, as the current version did.

4) The bitmap printer and parser should be part of bitmap.[ch] with syntax
   and semantics to match.  The original lib/mask.c versions did not
   recognize this commonality.

1 files changed, 146 insertions, 3 deletions

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 6462e071167b..fb09dffaa557 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1,5 +1,18 @@
-#include <linux/bitmap.h>
+/*
+ * lib/bitmap.c
+ * Helper functions for bitmap.h.
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
 #include <linux/module.h>
+#include <linux/ctype.h>
+#include <linux/errno.h>
+#include <linux/bitmap.h>
+#include <asm/bitops.h>
+#include <asm/uaccess.h>
+
+#define MAX_BITMAP_BITS	512U	/* for ia64 NR_CPUS maximum */
 
 int bitmap_empty(const unsigned long *bitmap, int bits)
 {
@@ -62,8 +75,9 @@ void bitmap_shift_right(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
 	int k;
-	DECLARE_BITMAP(__shr_tmp, bits);
+	DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);
 
+	BUG_ON(bits > MAX_BITMAP_BITS);
 	bitmap_clear(__shr_tmp, bits);
 	for (k = 0; k < bits - shift; ++k)
 		if (test_bit(k + shift, src))
@@ -76,8 +90,9 @@ void bitmap_shift_left(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
 	int k;
-	DECLARE_BITMAP(__shl_tmp, bits);
+	DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);
 
+	BUG_ON(bits > MAX_BITMAP_BITS);
 	bitmap_clear(__shl_tmp, bits);
 	for (k = bits; k >= shift; --k)
 		if (test_bit(k - shift, src))
@@ -139,3 +154,131 @@ int bitmap_weight(const unsigned long *bitmap, int bits)
 #endif
 EXPORT_SYMBOL(bitmap_weight);
 
+/*
+ * Bitmap printing & parsing functions: first version by Bill Irwin,
+ * second version by Paul Jackson, third by Joe Korty.
+ */
+
+#define CHUNKSZ				32
+#define nbits_to_hold_value(val)	fls(val)
+#define roundup_power2(val,modulus)	(((val) + (modulus) - 1) & ~((modulus) - 1))
+#define unhex(c)			(isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
+
+/**
+ * bitmap_snprintf - convert bitmap to an ASCII hex string.
+ * @buf: byte buffer into which string is placed
+ * @buflen: reserved size of @buf, in bytes
+ * @maskp: pointer to bitmap to convert
+ * @nmaskbits: size of bitmap, in bits
+ *
+ * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into
+ * comma-separated sets of eight digits per set.
+ */
+int bitmap_snprintf(char *buf, unsigned int buflen,
+	const unsigned long *maskp, int nmaskbits)
+{
+	int i, word, bit, len = 0;
+	unsigned long val;
+	const char *sep = "";
+	int chunksz;
+	u32 chunkmask;
+
+	chunksz = nmaskbits & (CHUNKSZ - 1);
+	if (chunksz == 0)
+		chunksz = CHUNKSZ;
+
+	i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
+	for (; i >= 0; i -= CHUNKSZ) {
+		chunkmask = ((1ULL << chunksz) - 1);
+		word = i / BITS_PER_LONG;
+		bit = i % BITS_PER_LONG;
+		val = (maskp[word] >> bit) & chunkmask;
+		len += snprintf(buf+len, buflen-len, "%s%0*lx", sep,
+			(chunksz+3)/4, val);
+		chunksz = CHUNKSZ;
+		sep = ",";
+	}
+	return len;
+}
+EXPORT_SYMBOL(bitmap_snprintf);
+
+/**
+ * bitmap_parse - convert an ASCII hex string into a bitmap.
+ * @buf: pointer to buffer in user space containing string.
+ * @buflen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0.
+ * @maskp: pointer to bitmap array that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Commas group hex digits into chunks.  Each chunk defines exactly 32
+ * bits of the resultant bitmask.  No chunk may specify a value larger
+ * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
+ * then leading 0-bits are prepended.  -EINVAL is returned for illegal
+ * characters and for grouping errors such as "1,,5", ",44", "," and "".
+ * Leading and trailing whitespace accepted, but not embedded whitespace.
+ */
+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+        unsigned long *maskp, int nmaskbits)
+{
+	int i, c, old_c, totaldigits, ndigits, nchunks, nbits;
+	u32 chunk;
+
+	bitmap_clear(maskp, nmaskbits);
+
+	nchunks = nbits = totaldigits = c = 0;
+	do {
+		chunk = ndigits = 0;
+
+		/* Get the next chunk of the bitmap */
+		while (ubuflen) {
+			old_c = c;
+			if (get_user(c, ubuf++))
+				return -EFAULT;
+			ubuflen--;
+			if (isspace(c))
+				continue;
+
+			/*
+			 * If the last character was a space and the current
+			 * character isn't '\0', we've got embedded whitespace.
+			 * This is a no-no, so throw an error.
+			 */
+			if (totaldigits && c && isspace(old_c))
+				return -EINVAL;
+
+			/* A '\0' or a ',' signal the end of the chunk */
+			if (c == '\0' || c == ',')
+				break;
+
+			if (!isxdigit(c))
+				return -EINVAL;
+
+			/*
+			 * Make sure there are at least 4 free bits in 'chunk'.
+			 * If not, this hexdigit will overflow 'chunk', so
+			 * throw an error.
+			 */
+			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
+				return -EOVERFLOW;
+
+			chunk = (chunk << 4) | unhex(c);
+			ndigits++; totaldigits++;
+		}
+		if (ndigits == 0)
+			return -EINVAL;
+		if (nchunks == 0 && chunk == 0)
+			continue;
+
+		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+		for (i = 0; i < CHUNKSZ; i++)
+			if (chunk & (1 << i))
+				set_bit(i, maskp);
+		nchunks++;
+		nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
+		if (nbits > nmaskbits)
+			return -EOVERFLOW;
+	} while (ubuflen && c == ',');
+
+	return 0;
+}
+EXPORT_SYMBOL(bitmap_parse);