[PATCH 0/7] lib: bitmap: Simplify bitmap_shift_{left,right}

[PATCH 0/7] lib: bitmap: Simplify bitmap_shift_{left,right}

[Rasmus Villemoes]

I've previously changed the nbits parameter of most bitmap_* functions
to unsigned; now it is bitmap_shift_{left,right}'s turn. This alone
saves some .text, but while at it I found that there were a few other
things one could do. The end result of these seven patches is

$ scripts/bloat-o-meter /tmp/bitmap.o.{old,new}
add/remove: 0/0 grow/shrink: 0/2 up/down: 0/-328 (-328)
function                                     old     new   delta
__bitmap_shift_right                         384     226    -158
__bitmap_shift_left                          306     136    -170

and less importantly also a smaller stack footprint

$ stack-o-meter.pl master bitmap
file                 function                       old  new  delta
lib/bitmap.o         __bitmap_shift_right             24    8  -16
lib/bitmap.o         __bitmap_shift_left              24    0  -24

For each pair of 0 <= shift <= nbits <= 256 I've tested the end result
with a few randomly filled src buffers (including garbage beyond
nbits), in each case verifying that the shift {left,right}-most bits
of dst are zero and the remaining nbits-shift bits correspond to src,
so I'm fairly confident I didn't screw up. That hasn't stopped me from
being wrong before, though.

Rasmus Villemoes (7):
  lib: bitmap: Change bitmap_shift_right to take unsigned parameters
  lib: bitmap: Eliminate branch in __bitmap_shift_right
  lib: bitmap: Remove redundant code from __bitmap_shift_right
  lib: bitmap: Yet another simplification in __bitmap_shift_right
  lib: bitmap: Change bitmap_shift_left to take unsigned parameters
  lib: bitmap: Eliminate branch in __bitmap_shift_left
  lib: bitmap: Remove redundant code from __bitmap_shift_left

 include/linux/bitmap.h | 24 ++++++++++++------------
 lib/bitmap.c           | 47 ++++++++++++++++++++---------------------------
 2 files changed, 32 insertions(+), 39 deletions(-)

-- 
2.0.4

[PATCH 1/7] lib: bitmap: Change bitmap_shift_right to take unsigned parameters

[Rasmus Villemoes]

gcc can generate slightly better code for stuff like "nbits %
BITS_PER_LONG" when it knows nbits is not negative. Since negative
size bitmaps or shift amounts don't make sense, change these
parameters of bitmap_shift_right to unsigned.

The expressions involving "lim - 1" are still ok, since if lim is 0
the loop is never executed.

Also use "shift" and "nbits" consistently for the parameter names.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/bitmap.h | 12 ++++++------
 lib/bitmap.c           | 10 +++++-----
 2 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index e1c8d08..5494adb 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -94,8 +94,8 @@ extern int __bitmap_equal(const unsigned long *bitmap1,
 			  const unsigned long *bitmap2, unsigned int nbits);
 extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
 			unsigned int nbits);
-extern void __bitmap_shift_right(unsigned long *dst,
-                        const unsigned long *src, int shift, int bits);
+extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
+				unsigned int shift, unsigned int nbits);
 extern void __bitmap_shift_left(unsigned long *dst,
                         const unsigned long *src, int shift, int bits);
 extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
@@ -280,13 +280,13 @@ static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
 	return __bitmap_weight(src, nbits);
 }
 
-static inline void bitmap_shift_right(unsigned long *dst,
-			const unsigned long *src, int n, int nbits)
+static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
+				unsigned int shift, int nbits)
 {
 	if (small_const_nbits(nbits))
-		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> n;
+		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
 	else
-		__bitmap_shift_right(dst, src, n, nbits);
+		__bitmap_shift_right(dst, src, shift, nbits);
 }
 
 static inline void bitmap_shift_left(unsigned long *dst,
diff --git a/lib/bitmap.c b/lib/bitmap.c
index b499ab6..2332115 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -102,17 +102,17 @@ EXPORT_SYMBOL(__bitmap_complement);
  *   @dst : destination bitmap
  *   @src : source bitmap
  *   @shift : shift by this many bits
- *   @bits : bitmap size, in bits
+ *   @nbits : bitmap size, in bits
  *
  * Shifting right (dividing) means moving bits in the MS -> LS bit
  * direction.  Zeros are fed into the vacated MS positions and the
  * LS bits shifted off the bottom are lost.
  */
-void __bitmap_shift_right(unsigned long *dst,
-			const unsigned long *src, int shift, int bits)
+void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
+			unsigned shift, unsigned nbits)
 {
-	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
-	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	unsigned k, lim = BITS_TO_LONGS(nbits), left = nbits % BITS_PER_LONG;
+	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 	unsigned long mask = (1UL << left) - 1;
 	for (k = 0; off + k < lim; ++k) {
 		unsigned long upper, lower;
-- 
2.0.4

[PATCH 2/7] lib: bitmap: Eliminate branch in __bitmap_shift_right

[Rasmus Villemoes]

We can shift the bits from lower and upper into place before
assembling dst[k]; moving the shift of upper into the branch where we
already know that rem is non-zero allows us to remove a
conditional.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 2332115..9250c3f 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -127,13 +127,13 @@ void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 			upper = src[off + k + 1];
 			if (off + k + 1 == lim - 1 && left)
 				upper &= mask;
+			upper <<= (BITS_PER_LONG - rem);
 		}
 		lower = src[off + k];
 		if (left && off + k == lim - 1)
 			lower &= mask;
-		dst[k] = lower >> rem;
-		if (rem)
-			dst[k] |= upper << (BITS_PER_LONG - rem);
+		lower >>= rem;
+		dst[k] = lower | upper;
 		if (left && k == lim - 1)
 			dst[k] &= mask;
 	}
-- 
2.0.4

[PATCH 3/7] lib: bitmap: Remove redundant code from __bitmap_shift_right

[Rasmus Villemoes]

If the condition k==lim-1 is true, we must have off == 0 (otherwise, k
could never become that big). But in that case we have upper == 0 and
hence dst[k] == (src[k] & mask) >> rem. Since mask consists of a
consecutive range of bits starting from the LSB, anding dst[k] with
mask is a no-op.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 9250c3f..20bb314 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -134,8 +134,6 @@ void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 			lower &= mask;
 		lower >>= rem;
 		dst[k] = lower | upper;
-		if (left && k == lim - 1)
-			dst[k] &= mask;
 	}
 	if (off)
 		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
-- 
2.0.4

[PATCH 4/7] lib: bitmap: Yet another simplification in __bitmap_shift_right

[Rasmus Villemoes]

If left is 0, we can just let mask be ~0UL, so that anding with it is
a no-op. Conveniently, BITMAP_LAST_WORD_MASK provides precisely what
we need, and we can eliminate left.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 20bb314..0d78c96 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -111,9 +111,9 @@ EXPORT_SYMBOL(__bitmap_complement);
 void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 			unsigned shift, unsigned nbits)
 {
-	unsigned k, lim = BITS_TO_LONGS(nbits), left = nbits % BITS_PER_LONG;
+	unsigned k, lim = BITS_TO_LONGS(nbits);
 	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
-	unsigned long mask = (1UL << left) - 1;
+	unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
 	for (k = 0; off + k < lim; ++k) {
 		unsigned long upper, lower;
 
@@ -125,12 +125,12 @@ void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 			upper = 0;
 		else {
 			upper = src[off + k + 1];
-			if (off + k + 1 == lim - 1 && left)
+			if (off + k + 1 == lim - 1)
 				upper &= mask;
 			upper <<= (BITS_PER_LONG - rem);
 		}
 		lower = src[off + k];
-		if (left && off + k == lim - 1)
+		if (off + k == lim - 1)
 			lower &= mask;
 		lower >>= rem;
 		dst[k] = lower | upper;
-- 
2.0.4

[PATCH 5/7] lib: bitmap: Change bitmap_shift_left to take unsigned parameters

[Rasmus Villemoes]

gcc can generate slightly better code for stuff like "nbits %
BITS_PER_LONG" when it knows nbits is not negative. Since negative
size bitmaps or shift amounts don't make sense, change these
parameters of bitmap_shift_right to unsigned.

If off >= lim (which requires shift >= nbits), k is initialized with a
large positive value, but since I've let k continue to be signed, the
loop will never run and dst will be zeroed as expected. Inside the
loop, k is guaranteed to be non-negative, so the fact that it is
promoted to unsigned in the various expressions it appears in is
harmless.

Also use "shift" and "nbits" consistently for the parameter names.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/bitmap.h | 12 ++++++------
 lib/bitmap.c           | 11 ++++++-----
 2 files changed, 12 insertions(+), 11 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 5494adb..fc8abc7 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -96,8 +96,8 @@ extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
 			unsigned int nbits);
 extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits);
-extern void __bitmap_shift_left(unsigned long *dst,
-                        const unsigned long *src, int shift, int bits);
+extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
+				unsigned int shift, unsigned int nbits);
 extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 			const unsigned long *bitmap2, unsigned int nbits);
 extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
@@ -289,13 +289,13 @@ static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *s
 		__bitmap_shift_right(dst, src, shift, nbits);
 }
 
-static inline void bitmap_shift_left(unsigned long *dst,
-			const unsigned long *src, int n, int nbits)
+static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
+				unsigned int shift, unsigned int nbits)
 {
 	if (small_const_nbits(nbits))
-		*dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
+		*dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
 	else
-		__bitmap_shift_left(dst, src, n, nbits);
+		__bitmap_shift_left(dst, src, shift, nbits);
 }
 
 static inline int bitmap_parse(const char *buf, unsigned int buflen,
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 0d78c96..5edd71b 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -146,18 +146,19 @@ EXPORT_SYMBOL(__bitmap_shift_right);
  *   @dst : destination bitmap
  *   @src : source bitmap
  *   @shift : shift by this many bits
- *   @bits : bitmap size, in bits
+ *   @nbits : bitmap size, in bits
  *
  * Shifting left (multiplying) means moving bits in the LS -> MS
  * direction.  Zeros are fed into the vacated LS bit positions
  * and those MS bits shifted off the top are lost.
  */
 
-void __bitmap_shift_left(unsigned long *dst,
-			const unsigned long *src, int shift, int bits)
+void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
+			unsigned int shift, unsigned int nbits)
 {
-	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
-	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	int k;
+	unsigned int lim = BITS_TO_LONGS(nbits), left = nbits % BITS_PER_LONG;
+	unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 	for (k = lim - off - 1; k >= 0; --k) {
 		unsigned long upper, lower;
 
-- 
2.0.4

[PATCH 6/7] lib: bitmap: Eliminate branch in __bitmap_shift_left

[Rasmus Villemoes]

We can shift the bits from lower and upper into place before
assembling dst[k + off]; moving the shift of lower into the branch
where we already know that rem is non-zero allows us to remove a
conditional.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 5edd71b..2362601 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -167,15 +167,14 @@ void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 		 * word below and make them the bottom rem bits of result.
 		 */
 		if (rem && k > 0)
-			lower = src[k - 1];
+			lower = src[k - 1] >> (BITS_PER_LONG - rem);
 		else
 			lower = 0;
 		upper = src[k];
 		if (left && k == lim - 1)
 			upper &= (1UL << left) - 1;
-		dst[k + off] = upper << rem;
-		if (rem)
-			dst[k + off] |= lower >> (BITS_PER_LONG - rem);
+		upper <<= rem;
+		dst[k + off] = lower | upper;
 		if (left && k + off == lim - 1)
 			dst[k + off] &= (1UL << left) - 1;
 	}
-- 
2.0.4

[PATCH 7/7] lib: bitmap: Remove redundant code from __bitmap_shift_left

[Rasmus Villemoes]

The first of these conditionals is completely redundant: If k ==
lim-1, we must have off==0, so the second conditional will also
trigger and then it wouldn't matter if upper had some high bits
set. But the second conditional is in fact also redundant, since it
only serves to clear out some high-order "don't care" bits of dst,
about which no guarantee is made.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/bitmap.c | 9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 2362601..acea8ae 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -157,7 +157,7 @@ void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 			unsigned int shift, unsigned int nbits)
 {
 	int k;
-	unsigned int lim = BITS_TO_LONGS(nbits), left = nbits % BITS_PER_LONG;
+	unsigned int lim = BITS_TO_LONGS(nbits);
 	unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 	for (k = lim - off - 1; k >= 0; --k) {
 		unsigned long upper, lower;
@@ -170,13 +170,8 @@ void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 			lower = src[k - 1] >> (BITS_PER_LONG - rem);
 		else
 			lower = 0;
-		upper = src[k];
-		if (left && k == lim - 1)
-			upper &= (1UL << left) - 1;
-		upper <<= rem;
+		upper = src[k] << rem;
 		dst[k + off] = lower | upper;
-		if (left && k + off == lim - 1)
-			dst[k + off] &= (1UL << left) - 1;
 	}
 	if (off)
 		memset(dst, 0, off*sizeof(unsigned long));
-- 
2.0.4