Skip to contentSkip to conversation

lib/vsprintf.c: Simplify uuid_string()

RFC PATCH In review George Spelvin 3 participants 10 messages May 11, 2015 – May 12, 2015

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

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.

Quoted 1 line

From 065a49efdf601acdf8f9c2689259a4210a527da0 Mon Sep 17 00:00:00 2001

From: George Spelvin <[email protected]>
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.

---
 lib/vsprintf.c | 17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)
lib/vsprintf.c +6 -11
index 452e4a16..de7f5bde 100644
@@ -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);
 }
 
Signature · 1 line
2.1.4
Quoted 1 line

From 744056f73bb5625d52de61605b31300ba3d3fbc6 Mon Sep 17 00:00:00 2001

From: George Spelvin <[email protected]>
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.

---
 lib/vsprintf.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)
lib/vsprintf.c +9 -16
index de7f5bde..38c1d87e 100644
@@ -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);
 }
Signature · 1 line
2.1.4
#1 lore raw
Quoted 2 lines · George Spelvin

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

lib/vsprintf.c

Quoted 1 line
lib/vsprintf.c +0 -0

[]

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1289

Quoted 5 lines
lib/vsprintf.c +3 -1
 	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];
#2 lore raw
Quoted 1 line

From [email protected] Mon May 11 16:49:27 2015

X-Session-Marker: 6A6F6540706572636865732E636F6D
X-Spam-Summary: 2,0,0,,d41d8cd98f00b204,[email protected],:::::,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 <[email protected]>
To: George Spelvin <[email protected]>
Cc: [email protected], [email protected]
Date: Mon, 11 May 2015 09:49:23 -0700
In-Reply-To: <[email protected]>
References: <[email protected]>
Content-Type: text/plain; charset="ISO-8859-1"
X-Mailer: Evolution 3.12.11-0ubuntu3
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit

Quoted 2 lines · George Spelvin

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.

Quoted 4 lines · Joe Perches

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.

#3 lore raw

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

In reply to George Spelvin
Quoted 1 line

From a53aa64b7b508d1f7cddbad556fb94f2c9c0191f Mon Sep 17 00:00:00 2001

From: George Spelvin <[email protected]>
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.

---
With apologies for the un-compilable intermediate state of the draft.

 lib/vsprintf.c | 17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)
lib/vsprintf.c +6 -11
index 452e4a16..4c4f9055 100644
@@ -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);
 }
 
Signature · 1 line
2.1.4
#4 lore raw

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

In reply to 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.

---
 lib/vsprintf.c | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)
lib/vsprintf.c +9 -16
index 4c4f9055..38c1d87e 100644
@@ -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);
 }
Signature · 1 line
2.1.4
#5 lore raw

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

Quoted 3 lines · 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.

Thanks George. One minor nit maybe not worth updating.

lib/vsprintf.c

Quoted 1 line
lib/vsprintf.c +0 -0

[]

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1270

Quoted 10 lines
lib/vsprintf.c +2 -3
@@ -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.

#6 lore raw

PATCH v2 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.

---

Quoted 2 lines

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(-)
lib/vsprintf.c +14 -18
index c3fb18bb..e5db83a9 100644
@@ -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);
 }
Signature · 1 line
2.1.4
reviewer Acked-by on v2 2/2
#7 lore raw

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

Quoted 7 lines · 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.

Quoted 9 lines

---

Quoted 2 lines

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:

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

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1296

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

I think '\0' is more common.

#8 lore raw

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

Quoted 4 lines

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.

Quoted 5 lines

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1296

Quoted 3 lines
lib/vsprintf.c +3 -0
+	/* 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

Quoted 1 line

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1300

Quoted 1 line
lib/vsprintf.c +0 -1
-	*p = 0;

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

#9 lore raw

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

Quoted 7 lines · George Spelvin
Quoted 4 lines

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.

Quoted 6 lines
Quoted 5 lines

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1296

Quoted 3 lines
lib/vsprintf.c +3 -0
+	/* Insert the fixed punctuation */
+	uuid[23] = uuid[18] = uuid[13] = uuid[8] = '-';
+	uuid[36] = 0;

I think '\0' is more common.

Quoted 6 lines

It's that way beause of it was replacing

Quoted 1 line

lib/vsprintf.c char *uuid_string(char *buf, char *end, const u8 *addr, · line 1300

Quoted 1 line
lib/vsprintf.c +0 -1
-	*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.