[PATCH 0/4] Some minor printf improvements

[PATCH 0/4] Some minor printf improvements

[Rasmus Villemoes]

While studying the kernel's printf internals in order to write the
kernel-specific format checking for smatch, I stumbled on a few things
one could do to shave an instruction here and there. Nothing
earth-shattering.

Rasmus Villemoes (4):
  lib/vsprintf.c: Eliminate some branches
  lib/vsprintf.c: Reduce stack use in number()
  lib/vsprintf.c: Eliminate duplicate hex string array
  lib/vsprintf.c: Another small hack

 lib/vsprintf.c | 49 +++++++++++++++++--------------------------------
 1 file changed, 17 insertions(+), 32 deletions(-)

-- 
2.1.3

[PATCH 1/4] lib/vsprintf.c: Eliminate some branches

[Rasmus Villemoes]

Since FORMAT_TYPE_INT is simply 1 more than FORMAT_TYPE_UINT, and
similarly for BYTE/UBYTE, SHORT/USHORT, LONG/ULONG, we can eliminate a
few instructions by making SIGN have the value 1 instead of 2, and
then use arithmetic instead of branches for computing the right
spec->type. It's a little hacky, but certainly in the same spirit as
SMALL needing to have the value 0x20. For example for the
spec->qualifier == 'l' case, gcc now generates

     75e:       0f b6 53 01             movzbl 0x1(%rbx),%edx
     762:       83 e2 01                and    $0x1,%edx
     765:       83 c2 09                add    $0x9,%edx
     768:       88 13                   mov    %dl,(%rbx)

instead of

     763:       0f b6 53 01             movzbl 0x1(%rbx),%edx
     767:       83 e2 02                and    $0x2,%edx
     76a:       80 fa 01                cmp    $0x1,%dl
     76d:       19 d2                   sbb    %edx,%edx
     76f:       83 c2 0a                add    $0xa,%edx
     772:       88 13                   mov    %dl,(%rbx)

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/vsprintf.c | 30 +++++++++++-------------------
 1 file changed, 11 insertions(+), 19 deletions(-)

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index b235c96167d3..318d583fe862 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -340,8 +340,8 @@ int num_to_str(char *buf, int size, unsigned long long num)
 	return len;
 }
 
-#define ZEROPAD	1		/* pad with zero */
-#define SIGN	2		/* unsigned/signed long */
+#define SIGN	1		/* unsigned/signed, must be 1 */
+#define ZEROPAD	2		/* pad with zero */
 #define PLUS	4		/* show plus */
 #define SPACE	8		/* space if plus */
 #define LEFT	16		/* left justified */
@@ -447,7 +447,7 @@ char *number(char *buf, char *end, unsigned long long num,
 		spec.precision = i;
 	/* leading space padding */
 	spec.field_width -= spec.precision;
-	if (!(spec.flags & (ZEROPAD+LEFT))) {
+	if (!(spec.flags & (ZEROPAD | LEFT))) {
 		while (--spec.field_width >= 0) {
 			if (buf < end)
 				*buf = ' ';
@@ -1738,29 +1738,21 @@ qualifier:
 	if (spec->qualifier == 'L')
 		spec->type = FORMAT_TYPE_LONG_LONG;
 	else if (spec->qualifier == 'l') {
-		if (spec->flags & SIGN)
-			spec->type = FORMAT_TYPE_LONG;
-		else
-			spec->type = FORMAT_TYPE_ULONG;
+		BUILD_BUG_ON(FORMAT_TYPE_ULONG + SIGN != FORMAT_TYPE_LONG);
+		spec->type = FORMAT_TYPE_ULONG + (spec->flags & SIGN);
 	} else if (_tolower(spec->qualifier) == 'z') {
 		spec->type = FORMAT_TYPE_SIZE_T;
 	} else if (spec->qualifier == 't') {
 		spec->type = FORMAT_TYPE_PTRDIFF;
 	} else if (spec->qualifier == 'H') {
-		if (spec->flags & SIGN)
-			spec->type = FORMAT_TYPE_BYTE;
-		else
-			spec->type = FORMAT_TYPE_UBYTE;
+		BUILD_BUG_ON(FORMAT_TYPE_UBYTE + SIGN != FORMAT_TYPE_BYTE);
+		spec->type = FORMAT_TYPE_UBYTE + (spec->flags & SIGN);
 	} else if (spec->qualifier == 'h') {
-		if (spec->flags & SIGN)
-			spec->type = FORMAT_TYPE_SHORT;
-		else
-			spec->type = FORMAT_TYPE_USHORT;
+		BUILD_BUG_ON(FORMAT_TYPE_USHORT + SIGN != FORMAT_TYPE_SHORT);
+		spec->type = FORMAT_TYPE_USHORT + (spec->flags & SIGN);
 	} else {
-		if (spec->flags & SIGN)
-			spec->type = FORMAT_TYPE_INT;
-		else
-			spec->type = FORMAT_TYPE_UINT;
+		BUILD_BUG_ON(FORMAT_TYPE_UINT + SIGN != FORMAT_TYPE_INT);
+		spec->type = FORMAT_TYPE_UINT + (spec->flags & SIGN);
 	}
 
 	return ++fmt - start;
-- 
2.1.3

[PATCH 2/4] lib/vsprintf.c: Reduce stack use in number()

[Rasmus Villemoes]

At least since the initial git commit, when base was passed as a
separate parameter, number() has only been called with bases 8, 10 and
16. I'm guessing that 66 was to accommodate 64 0/1, a sign and a '\0',
but the buffer is only used for the actual digits. Octal digits carry
3 bits of information, so 24 is enough. Spell that 3*sizeof(num) so
one less place needs to be changed should long long ever be 128
bits. Also remove the commented-out code that would handle an
arbitrary base.

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

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 318d583fe862..98f1ce907d3d 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -386,7 +386,7 @@ char *number(char *buf, char *end, unsigned long long num,
 	/* we are called with base 8, 10 or 16, only, thus don't need "G..."  */
 	static const char digits[16] = "0123456789ABCDEF"; /* "GHIJKLMNOPQRSTUVWXYZ"; */
 
-	char tmp[66];
+	char tmp[3 * sizeof(num)];
 	char sign;
 	char locase;
 	int need_pfx = ((spec.flags & SPECIAL) && spec.base != 10);
@@ -423,11 +423,6 @@ char *number(char *buf, char *end, unsigned long long num,
 	i = 0;
 	if (num < spec.base)
 		tmp[i++] = digits[num] | locase;
-	/* Generic code, for any base:
-	else do {
-		tmp[i++] = (digits[do_div(num,base)] | locase);
-	} while (num != 0);
-	*/
 	else if (spec.base != 10) { /* 8 or 16 */
 		int mask = spec.base - 1;
 		int shift = 3;
-- 
2.1.3

[PATCH 3/4] lib/vsprintf.c: Eliminate duplicate hex string array

[Rasmus Villemoes]

gcc doesn't merge or overlap const char[] objects with identical
contents (probably language lawyers would also insist that these
things have different addresses), but there's no reason to have the
string "0123456789ABCDEF" occur in multiple places. hex_asc_upper is
declared in kernel.h and defined in lib/hexdump.c, which is
unconditionally compiled in.

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

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 98f1ce907d3d..7a299d43987a 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -383,9 +383,6 @@ static noinline_for_stack
 char *number(char *buf, char *end, unsigned long long num,
 	     struct printf_spec spec)
 {
-	/* we are called with base 8, 10 or 16, only, thus don't need "G..."  */
-	static const char digits[16] = "0123456789ABCDEF"; /* "GHIJKLMNOPQRSTUVWXYZ"; */
-
 	char tmp[3 * sizeof(num)];
 	char sign;
 	char locase;
@@ -422,7 +419,7 @@ char *number(char *buf, char *end, unsigned long long num,
 	/* generate full string in tmp[], in reverse order */
 	i = 0;
 	if (num < spec.base)
-		tmp[i++] = digits[num] | locase;
+		tmp[i++] = hex_asc_upper[num] | locase;
 	else if (spec.base != 10) { /* 8 or 16 */
 		int mask = spec.base - 1;
 		int shift = 3;
@@ -430,7 +427,7 @@ char *number(char *buf, char *end, unsigned long long num,
 		if (spec.base == 16)
 			shift = 4;
 		do {
-			tmp[i++] = (digits[((unsigned char)num) & mask] | locase);
+			tmp[i++] = (hex_asc_upper[((unsigned char)num) & mask] | locase);
 			num >>= shift;
 		} while (num);
 	} else { /* base 10 */
-- 
2.1.3

[PATCH 4/4] lib/vsprintf.c: Another small hack

[Rasmus Villemoes]

Making ZEROPAD == '0'-' ', we can eliminate a few more instructions.

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

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 7a299d43987a..2753f9261115 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -341,10 +341,10 @@ int num_to_str(char *buf, int size, unsigned long long num)
 }
 
 #define SIGN	1		/* unsigned/signed, must be 1 */
-#define ZEROPAD	2		/* pad with zero */
+#define LEFT	2		/* left justified */
 #define PLUS	4		/* show plus */
 #define SPACE	8		/* space if plus */
-#define LEFT	16		/* left justified */
+#define ZEROPAD	16		/* pad with zero, must be 16 == '0' - ' ' */
 #define SMALL	32		/* use lowercase in hex (must be 32 == 0x20) */
 #define SPECIAL	64		/* prefix hex with "0x", octal with "0" */
 
@@ -467,7 +467,8 @@ char *number(char *buf, char *end, unsigned long long num,
 	}
 	/* zero or space padding */
 	if (!(spec.flags & LEFT)) {
-		char c = (spec.flags & ZEROPAD) ? '0' : ' ';
+		char c = ' ' + (spec.flags & ZEROPAD);
+		BUILD_BUG_ON(' ' + ZEROPAD != '0');
 		while (--spec.field_width >= 0) {
 			if (buf < end)
 				*buf = c;
-- 
2.1.3