[RFC PATCH] lib/vsprintf.c: Simplify uuid_string()

[RFC PATCH] lib/vsprintf.c: Simplify uuid_string()

[George Spelvin]

I didn't see your decimal print changes before they went in, but great
work!  That's a real "why didn't I think of that?" change.


Anyway, merging some local patches I have with that prompted me to look
over that file and I came up with the following two patches which might
be interesting.  RFC until I build a test harness and made sure there
aren't any stupid bugs, but the ideas are simple enough.

They're so small I'm breaking protocol and including them both in the same
e-mail.


>From 065a49efdf601acdf8f9c2689259a4210a527da0 Mon Sep 17 00:00:00 2001
From: George Spelvin <linux@horizon.com>
Date: Mon, 11 May 2015 08:09:39 -0400
Subject: [PATCH 1/2] lib/vsprintf.c: Simplify uuid_string()

Rather than have a second pass to upcase the buffer, just make the
hex lookup table variable.

I suspect it's a speedup, but since this is not hot code, the important
part is that it shrinks the function from 332 to 256 bytes.

Signed-off-by: George Spelvin <linux@horizon.com>
---
 lib/vsprintf.c | 17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 452e4a16..de7f5bde 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1270,21 +1270,23 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 	static const u8 be[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
 	static const u8 le[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
 	const u8 *index = be;
-	bool uc = false;
+	const char *hex = hex_asc;
 
 	switch (*(++fmt)) {
 	case 'L':
-		uc = true;		/* fall-through */
+		hex = hex_asc_upper;		/* fall-through */
 	case 'l':
 		index = le;
 		break;
 	case 'B':
-		uc = true;
+		hex = hex_asc_upper;
 		break;
 	}
 
 	for (i = 0; i < 16; i++) {
-		p = hex_byte_pack(p, addr[index[i]]);
+		u8 byte = addr[index[i]];
+		*p++ = hex[x >> 4];
+		*p++ = hex[x & 0x0f];
 		switch (i) {
 		case 3:
 		case 5:
@@ -1297,13 +1299,6 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 
 	*p = 0;
 
-	if (uc) {
-		p = uuid;
-		do {
-			*p = toupper(*p);
-		} while (*(++p));
-	}
-
 	return string(buf, end, uuid, spec);
 }
 
-- 
2.1.4


>From 744056f73bb5625d52de61605b31300ba3d3fbc6 Mon Sep 17 00:00:00 2001
From: George Spelvin <linux@horizon.com>
Date: Mon, 11 May 2015 10:46:52 -0400
Subject: [PATCH 2/2] lib/vsprintf.c: Further simplify uuid_string().

Make the endianness permutation table do double duty by having it
list not source offsets, but destination offsets.  Thus, it both puts
the bytes in the right order and skips the hyphens.

This further shrinks the code from 256 to 214 bytes.  Eliminating
erratic branches probably helps speed, too.

Signed-off-by: George Spelvin <linux@horizon.com>
---
 lib/vsprintf.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index de7f5bde..38c1d87e 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1265,10 +1265,9 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 		  struct printf_spec spec, const char *fmt)
 {
 	char uuid[sizeof("xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx")];
-	char *p = uuid;
 	int i;
-	static const u8 be[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
-	static const u8 le[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
+	static const u8 be[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
+	static const u8 le[16] = {6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34};
 	const u8 *index = be;
 	const char *hex = hex_asc;
 
@@ -1284,20 +1283,14 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 	}
 
 	for (i = 0; i < 16; i++) {
-		u8 byte = addr[index[i]];
-		*p++ = hex[x >> 4];
-		*p++ = hex[x & 0x0f];
-		switch (i) {
-		case 3:
-		case 5:
-		case 7:
-		case 9:
-			*p++ = '-';
-			break;
-		}
-	}
+		u8 byte = addr[i];
+		char *p = uuid + index[i];
 
-	*p = 0;
+		p[0] = hex[byte >> 4];
+		p[1] = hex[byte & 0x0f];
+	}
+	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
+	uuid[36] = 0;
 
 	return string(buf, end, uuid, spec);
 }
-- 
2.1.4

Re: [RFC PATCH] lib/vsprintf.c: Simplify uuid_string()

[Joe Perches]

On Mon, 2015-05-11 at 12:32 -0400, George Spelvin wrote:
> I suspect it's a speedup, but since this is not hot code, the important
> part is that it shrinks the function from 332 to 256 bytes.

shrinking code in vsprintf is always good

> diff --git a/lib/vsprintf.c b/lib/vsprintf.c
[]
>  	for (i = 0; i < 16; i++) {
> -		p = hex_byte_pack(p, addr[index[i]]);
> +		u8 byte = addr[index[i]];
> +		*p++ = hex[x >> 4];
> +		*p++ = hex[x & 0x0f];

?
		*p++ = hex[byte >> 4];
		*p++ = hex[byte & 0x0f];

Re: [RFC PATCH] lib/vsprintf.c: Simplify uuid_string()

[George Spelvin]

>From joe@perches.com Mon May 11 16:49:27 2015
X-Session-Marker: 6A6F6540706572636865732E636F6D
X-Spam-Summary: 2,0,0,,d41d8cd98f00b204,joe@perches.com,:::::,RULES_HIT:41:355:379:541:599:960:973:988:989:1260:1277:1311:1313:1314:1345:1359:1373:1437:1515:1516:1518:1534:1538:1593:1594:1711:1714:1730:1747:1777:1792:2393:2559:2562:2828:3138:3139:3140:3141:3142:3351:3622:3865:3867:3870:3871:3872:3874:4321:4560:5007:6120:6261:10004:10400:10848:11026:11232:11658:11914:12517:12519:12740:13069:13311:13357:21080,0,RBL:none,CacheIP:none,Bayesian:0.5,0.5,0.5,Netcheck:none,DomainCache:0,MSF:not bulk,SPF:fn,MSBL:0,DNSBL:none,Custom_rules:0:0:0
X-HE-Tag: word26_8c684ad08ef5e
X-Filterd-Recvd-Size: 1292
Subject: Re: [RFC PATCH] lib/vsprintf.c: Simplify uuid_string()
From: Joe Perches <joe@perches.com>
To: George Spelvin <linux@horizon.com>
Cc: linux@rasmusvillemoes.dk, linux-kernel@vger.kernel.org
Date: Mon, 11 May 2015 09:49:23 -0700
In-Reply-To: <20150511163230.14333.qmail@ns.horizon.com>
References: <20150511163230.14333.qmail@ns.horizon.com>
Content-Type: text/plain; charset="ISO-8859-1"
X-Mailer: Evolution 3.12.11-0ubuntu3 
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit

On Mon, 2015-05-11 at 12:32 -0400, George Spelvin wrote:
> I suspect it's a speedup, but since this is not hot code, the important
> part is that it shrinks the function from 332 to 256 bytes.

Joe Perches <joe@perches.com> wrote:
> shrinking code in vsprintf is always good
> ?
>		*p++ = hex[byte >> 4];
>		*p++ = hex[byte & 0x0f];

Arrgh!

Yes, I ran into that compile problem already.  I'd already made
that change (I'm not quite Linus; I do *compile* my untested patches
before posting them), but didn't commit it properly, and when I ran
format-patch... :-(

Since this seems to be a positive reaction, I'll put together a test
harmess and make a proper submission.

[PATCH 1/2] lib/vsprintf.c: Simplify uuid_string()

[George Spelvin]

>From a53aa64b7b508d1f7cddbad556fb94f2c9c0191f Mon Sep 17 00:00:00 2001
From: George Spelvin <linux@horizon.com>
Date: Mon, 11 May 2015 13:05:55 -0400
Subject: [PATCH 1/2] lib/vsprintf.c: Simplify uuid_string()

Rather than have a second pass to upcase the buffer, just make the
hex lookup table variable.

I suspect it's a speedup, but since this is not hot code, the important
part is that it shrinks the function from 332 to 256 bytes.

Signed-off-by: George Spelvin <linux@horizon.com>
---
With apologies for the un-compilable intermediate state of the draft.

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

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 452e4a16..4c4f9055 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1270,21 +1270,23 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 	static const u8 be[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
 	static const u8 le[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
 	const u8 *index = be;
-	bool uc = false;
+	const char *hex = hex_asc;
 
 	switch (*(++fmt)) {
 	case 'L':
-		uc = true;		/* fall-through */
+		hex = hex_asc_upper;	/* fall-through */
 	case 'l':
 		index = le;
 		break;
 	case 'B':
-		uc = true;
+		hex = hex_asc_upper;
 		break;
 	}
 
 	for (i = 0; i < 16; i++) {
-		p = hex_byte_pack(p, addr[index[i]]);
+		u8 byte = addr[index[i]];
+		*p++ = hex[byte >> 4];
+		*p++ = hex[byte & 0x0f];
 		switch (i) {
 		case 3:
 		case 5:
@@ -1297,13 +1299,6 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 
 	*p = 0;
 
-	if (uc) {
-		p = uuid;
-		do {
-			*p = toupper(*p);
-		} while (*(++p));
-	}
-
 	return string(buf, end, uuid, spec);
 }
 
-- 
2.1.4

[PATCH 2/2] lib/vsprintf.c: Further simplify uuid_string()

[George Spelvin]

Make the endianness permutation table do double duty by having it
list not source offsets, but destination offsets.  Thus, it both puts
the bytes in the right order and skips the hyphens.

This further shrinks the code from 256 to 214 bytes.  Eliminating
erratic branches probably helps speed, too.

This has been verified to produce the same output as the older code using
a user-space test harness.

Signed-off-by: George Spelvin <linux@horizon.com>
---
 lib/vsprintf.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 4c4f9055..38c1d87e 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1265,10 +1265,9 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 		  struct printf_spec spec, const char *fmt)
 {
 	char uuid[sizeof("xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx")];
-	char *p = uuid;
 	int i;
-	static const u8 be[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
-	static const u8 le[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
+	static const u8 be[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
+	static const u8 le[16] = {6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34};
 	const u8 *index = be;
 	const char *hex = hex_asc;
 
@@ -1284,20 +1283,14 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 	}
 
 	for (i = 0; i < 16; i++) {
-		u8 byte = addr[index[i]];
-		*p++ = hex[byte >> 4];
-		*p++ = hex[byte & 0x0f];
-		switch (i) {
-		case 3:
-		case 5:
-		case 7:
-		case 9:
-			*p++ = '-';
-			break;
-		}
-	}
+		u8 byte = addr[i];
+		char *p = uuid + index[i];
 
-	*p = 0;
+		p[0] = hex[byte >> 4];
+		p[1] = hex[byte & 0x0f];
+	}
+	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
+	uuid[36] = 0;
 
 	return string(buf, end, uuid, spec);
 }
-- 
2.1.4

Re: [PATCH 2/2] lib/vsprintf.c: Further simplify uuid_string()

[Joe Perches]

On Mon, 2015-05-11 at 15:55 -0400, George Spelvin wrote:
> Make the endianness permutation table do double duty by having it
> list not source offsets, but destination offsets.  Thus, it both puts
> the bytes in the right order and skips the hyphens.

Thanks George.  One minor nit maybe not worth updating.

> diff --git a/lib/vsprintf.c b/lib/vsprintf.c
[]
> @@ -1265,10 +1265,9 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
>  		  struct printf_spec spec, const char *fmt)
>  {
>  	char uuid[sizeof("xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx")];
> -	char *p = uuid;
>  	int i;
> -	static const u8 be[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
> -	static const u8 le[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
> +	static const u8 be[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
> +	static const u8 le[16] = {6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34};

These might be better with a little comment/explanation
of the values as output offsets for each index.

[PATCH 2/2 v2] lib/vsprintf.c: Further simplify uuid_string()

[George Spelvin]

Make the endianness permutation table do double duty by having it
list not source offsets, but destination offsets.  Thus, it both puts
the bytes in the right order and skips the hyphens.

This further shrinks the code from 256 to 214 bytes.  Eliminating
erratic branches probably helps speed, too.

Signed-off-by: George Spelvin <linux@horizon.com>
---
> These might be better with a little comment/explanation
> of the values as output offsets for each index.

Like this?  I had thought about it, and had decied not to change the
existing lacomic code style, as it didn't seem any harder to understand
than the original.  But I'm happy to add comments.

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

diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index c3fb18bb..e5db83a9 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1265,14 +1265,14 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 		  struct printf_spec spec, const char *fmt)
 {
 	char uuid[sizeof("xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx")];
-	char *p = uuid;
-	int i;
-	static const u8 be[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
-	static const u8 le[16] = {3,2,1,0,5,4,7,6,8,9,10,11,12,13,14,15};
+	/* Offset in uuid[] where each byte is printed, two cases. */
+	static const u8 be[16] = {0,2,4,6,9,11,14,16,19,21,24,26,28,30,32,34};
+	static const u8 le[16] = {6,4,2,0,11,9,16,14,19,21,24,26,28,30,32,34};
 	const u8 *index = be;
 	const char *hex = hex_asc;
+	int i;
 
-	switch (*(++fmt)) {
+	switch (fmt[1]) {
 	case 'L':
 		hex = hex_asc_upper;	/* fall-through */
 	case 'l':
@@ -1283,21 +1283,17 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
 		break;
 	}
 
+	/* Format each byte of the raw uuid into the buffer */
 	for (i = 0; i < 16; i++) {
-		u8 byte = addr[index[i]];
-		*p++ = hex[byte >> 4];
-		*p++ = hex[byte & 0x0f];
-		switch (i) {
-		case 3:
-		case 5:
-		case 7:
-		case 9:
-			*p++ = '-';
-			break;
-		}
-	}
+		u8 byte = addr[i];
+		char *p = uuid + index[i];
 
-	*p = 0;
+		p[0] = hex[byte >> 4];
+		p[1] = hex[byte & 0x0f];
+	}
+	/* Insert the fixed punctuation */
+	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
+	uuid[36] = 0;
 
 	return string(buf, end, uuid, spec);
 }
-- 
2.1.4

Re: [PATCH 2/2 v2] lib/vsprintf.c: Further simplify uuid_string()

[Rasmus Villemoes]

On Tue, May 12 2015, "George Spelvin" <linux@horizon.com> wrote:

> Make the endianness permutation table do double duty by having it
> list not source offsets, but destination offsets.  Thus, it both puts
> the bytes in the right order and skips the hyphens.
>
> This further shrinks the code from 256 to 214 bytes.  Eliminating
> erratic branches probably helps speed, too.
>
> Signed-off-by: George Spelvin <linux@horizon.com>
> ---
>> These might be better with a little comment/explanation
>> of the values as output offsets for each index.
>
> Like this?  I had thought about it, and had decied not to change the
> existing lacomic code style, as it didn't seem any harder to understand
> than the original.  But I'm happy to add comments.
>

With or without comments and the microscopic nit below:

Acked-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>

You may want/need to include Andrew Morton in the cc-list to get these
picked up.

>
>  lib/vsprintf.c | 32 ++++++++++++++------------------
>  1 file changed, 14 insertions(+), 18 deletions(-)
>
> +	/* Insert the fixed punctuation */
> +	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
> +	uuid[36] = 0;

I think '\0' is more common.

Re: [PATCH 2/2 v2] lib/vsprintf.c: Further simplify uuid_string()

[George Spelvin]

> Acked-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> 
> You may want/need to include Andrew Morton in the cc-list to get these
> picked up.

Thank you; I sent it to you because I'm not sure who's really in charge
of this.

>> +	/* Insert the fixed punctuation */
>> +	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
>> +	uuid[36] = 0;

> I think '\0' is more common.

It's that way beause of it was replacing

>> -	*p = 0;

But yes, I prefer the char constant, too.  And it would be consistent with
the rest of the file.

Re: [PATCH 2/2 v2] lib/vsprintf.c: Further simplify uuid_string()

[Joe Perches]

On Tue, 2015-05-12 at 09:57 -0400, George Spelvin wrote:
> > Acked-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> > 
> > You may want/need to include Andrew Morton in the cc-list to get these
> > picked up.
> 
> Thank you; I sent it to you because I'm not sure who's really in charge
> of this.

Andrew generally gets these sorts of changes applied.

> >> +	/* Insert the fixed punctuation */
> >> +	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
> >> +	uuid[36] = 0;
> 
> > I think '\0' is more common.
> 
> It's that way beause of it was replacing
> 
> >> -	*p = 0;
> 
> But yes, I prefer the char constant, too.  And it would be consistent with
> the rest of the file.

I think I did that "*p = 0;" because that's what
I normally use, but consistency is better.