Skip to contentSkip to conversation

strings: helper for maximum decimal encoding of an unsigned integer

PATCH In review J. Bruce Fields 5 participants 17 messages Aug 21, 2012 – Sep 14, 2012

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

PATCH 1/1 strings: helper for maximum decimal encoding of an unsigned integer

From: "J. Bruce Fields" <[email protected]>

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help? Is there some better way?

(Approximation due to Jim Rees).

---
 include/linux/string.h |    6 ++++++
 net/sunrpc/cache.c     |    2 +-
 2 files changed, 7 insertions(+), 1 deletion(-)
include/linux/string.h +6 -0
index ffe0442..d4809b7 100644
@@ -126,6 +126,12 @@ extern void argv_free(char **argv);
 extern bool sysfs_streq(const char *s1, const char *s2);
 extern int strtobool(const char *s, bool *res);
 
+/*
+ * length of the decimal representation of an unsigned integer.  Just an
+ * approximation, but it's right for types of size 1 to 36 bytes:
+ */
+#define base10len(i) (sizeof(i) * 24 / 10 + 1)
+
 #ifdef CONFIG_BINARY_PRINTF
 int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args);
 int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf);
net/sunrpc/cache.c +1 -1
index 2afd2a8..1dcd2b3 100644
@@ -1409,7 +1409,7 @@ static ssize_t read_flush(struct file *file, char __user *buf,
 			  size_t count, loff_t *ppos,
 			  struct cache_detail *cd)
 {
-	char tbuf[20];
+	char tbuf[base10len(long) + 2];
 	unsigned long p = *ppos;
 	size_t len;
 
Signature · 1 line
1.7.9.5
#1 lore raw

J. Bruce Fields wrote:

From: "J. Bruce Fields" <[email protected]>

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help? Is there some better way?

(Approximation due to Jim Rees).

Please add Suggested-by: Jim Rees <[email protected]>. I'm thinking of patenting the algorithm.

#2 lore raw
Quoted 11 lines · Jim Rees

J. Bruce Fields wrote:

From: "J. Bruce Fields" <[email protected]>

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help? Is there some better way?

(Approximation due to Jim Rees).

Please add Suggested-by: Jim Rees <[email protected]>. I'm thinking of patenting the algorithm.

Is that a joke? Patenting the fact that log10(256) is 2.408..., which is about 2.4, which is 24/10? I really hope we are Poe'd... BTW, NAK the comment - s/36/26/ in there; check it yourself -

$ echo '2^(8*27)' | bc
105312291668557186697918027683670432318895095400549111254310977536
which is 66-digit, not 65 as the estimate would be.
#3 lore raw
Quoted 13 lines · Al Viro
Quoted 11 lines · Jim Rees

J. Bruce Fields wrote:

From: "J. Bruce Fields" <[email protected]>

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help? Is there some better way?

(Approximation due to Jim Rees).

Please add Suggested-by: Jim Rees <[email protected]>. I'm thinking of patenting the algorithm.

Quoted 6 lines

Is that a joke? Patenting the fact that log10(256) is 2.408..., which is about 2.4, which is 24/10? I really hope we are Poe'd... BTW, NAK the comment - s/36/26/ in there; check it yourself -

$ echo '2^(8*27)' | bc
105312291668557186697918027683670432318895095400549111254310977536
which is 66-digit, not 65 as the estimate would be.

Erp, you're right.

Anyway, does something like base10len(type) seem reasonable? Or define macros that enumerate the sizes? (ULONG_STR_MAX or something?)

--b.

#4 lore raw
In reply to Al Viro

Al Viro wrote:

Quoted 11 lines · Jim Rees

J. Bruce Fields wrote:

From: "J. Bruce Fields" <[email protected]>

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help? Is there some better way?

(Approximation due to Jim Rees).

Please add Suggested-by: Jim Rees <[email protected]>. I'm thinking of patenting the algorithm.

Is that a joke?

Yes, that's a joke. Sorry if it wasn't obvious.

I am, however offering up licenses at a cost of one pint of beer per thousand digits converted.

#5 lore raw
In reply to J. Bruce Fields

include/linux/string.h extern void argv_free(char **argv); · line 133

Quoted 9 lines · J. Bruce Fields

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help? Is there some better way? (Approximation due to Jim Rees).

include/linux/string.h +5 -0
+/*
+ * length of the decimal representation of an unsigned integer.  Just an
+ * approximation, but it's right for types of size 1 to 36 bytes:
+ */
+#define base10len(i) (sizeof(i) * 24 / 10 + 1)

gcc provides... "interesting" features at times.

/* for unsigned "i"s */
#define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[i])

But enumerating it (using your ULONG_MAX_STR proposal) should be sufficient, since there is only a limited number of types that get e.g. sprintf'ed into a buffer.

Something else tho, it seems some don't know that sizeof("") is already 1, and an extra \0 is often unneeded, like in:

arch/um/drivers/net_user.c: char addr_buf[sizeof("255.255.255.255\0")];

#6 lore raw
Quoted 1 line · Jan Engelhardt

On Tuesday 2012-08-21 23:29, J. Bruce Fields wrote:

[...]

Quoted 10 lines

include/linux/string.h extern void argv_free(char **argv); · line 133

Quoted 5 lines
include/linux/string.h +5 -0
+/*
+ * length of the decimal representation of an unsigned integer.  Just an
+ * approximation, but it's right for types of size 1 to 36 bytes:
+ */
+#define base10len(i) (sizeof(i) * 24 / 10 + 1)

gcc provides... "interesting" features at times.

/* for unsigned "i"s */
#define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[i])

Shouldn't that have been
---- snip ----
#define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[sizeof(i)]) ---- snip ----
?

A pure K&R-C version would use a string:
---- snip ----
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] ---- snip ----
(if I converted them properly into hexadecimal) and that gives a "char" which is happily promoted to whatever one needs in that place.

Kind regards,
Bernd

Signature · 2 lines
Bernd Petrovitsch                  Email : [email protected]
                     LUGA : http://www.luga.at
#7 lore raw

Bernd Petrovitsch wrote:

Quoted 1 line · Jan Engelhardt

On Tuesday 2012-08-21 23:29, J. Bruce Fields wrote:

[...]

Quoted 10 lines

include/linux/string.h extern void argv_free(char **argv); · line 133

Quoted 5 lines
include/linux/string.h +5 -0
+/*
+ * length of the decimal representation of an unsigned integer.  Just an
+ * approximation, but it's right for types of size 1 to 36 bytes:
+ */
+#define base10len(i) (sizeof(i) * 24 / 10 + 1)

gcc provides... "interesting" features at times.

/* for unsigned "i"s */
#define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[i])

  Shouldn't that have been
  ----  snip ----
  #define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[sizeof(i)])
  ----  snip ----
  ?

A pure K&R-C version would use a string:
---- snip ----
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] ---- snip ----
(if I converted them properly into hexadecimal) and that gives a "char" which is happily promoted to whatever one needs in that place.

1. That may give you a signed char on some architectures, which is not what you want (although it doesn't matter since the values are all < 128)

2. If you put this in a .h, you'll get multiple copies of the array

3. No bounds checking (but in ninja K&R style you never check bounds)

4. Unreadable.

Pure K&R:

base10.h:
extern unsigned char base10len_vals[];
#define base10len(i) (base10len_vals[sizeof(i)])

base10.c:
unsigned char base10len_vals[] = {1,3,5,8,10,13,15,17,20};

But I still like my way better.

#13 lore raw
In reply to Bernd Petrovitsch
Quoted 4 lines · Bernd Petrovitsch

Shouldn't that have been
---- snip ----
#define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[sizeof(i)]) ---- snip ----

Yeah.

Quoted 3 lines

A pure K&R-C version would use a string:
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] (if I converted them properly into hexadecimal)

The syntax is \x01\x03\x05...

Quoted 2 lines

and that gives a "char"
which is happily promoted to whatever one needs in that place.

So just convert it; there are no less than two ways to do so
((const unsigned char *)"\x01\x03...")[sizeof(i)] (boatfloating_t)("\x01\x03..."[sizeof(i)])

#8 lore raw
In reply to Jim Rees
Quoted 1 line · Jim Rees

But I still like my way better.

Yeah. It looks less mysterious once you realize it's just a straightforward application of the usual coincidence

	2^10 = 1024 ~ 1000 = 10^3

How about this? Also with some more defines because I like typing

	char buf[ULONG_STR_MAX + 1];

better than

	char bug[base10len(unsigned long) + 1];

--b.

commit 59a620640cd05d3d29e678ff893cfe266091fba7

Author: J. Bruce Fields <[email protected]>
Date:   Wed Aug 15 17:41:47 2012 -0400

strings: helper for maximum decimal encoding of an unsigned integer

I've seen a couple examples recently where we've gotten this wrong. Maybe something like this would help?

include/linux/string.h +21 -0
index ffe0442..38da7a0 100644
@@ -126,6 +126,27 @@ extern void argv_free(char **argv);
 extern bool sysfs_streq(const char *s1, const char *s2);
 extern int strtobool(const char *s, bool *res);
 
+/*
+ * length of the decimal representation of an integer, not including any
+ * sign or null termination.  Just an approximation, but it's right for
+ * unsigned types of size 1 to 26 bytes:
+ */
+#define base10len(i) (sizeof(i) * 8 * 3 / 10 + 1)
+
+/* Actually a slight overestimate in the signed 64-bit case: */
+
+#define UCHAR_STR_MAX	base10len(char)
+#define CHAR_STR_MAX	base10len(char) + 1
+#define UINT_STR_MAX	base10len(int)
+#define INT_STR_MAX	base10len(int) + 1
+#define ULONG_STR_MAX	base10len(long)
+#define LONG_STR_MAX	base10len(long) + 1
+
+#define U32_STR_MAX	base10len(u32)
+#define S32_STR_MAX	base10len(u32) + 1
+#define U64_STR_MAX	base10len(u64)
+#define S64_STR_MAX	base10len(u64) + 1
+
 #ifdef CONFIG_BINARY_PRINTF
 int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args);
 int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf);
net/sunrpc/cache.c +1 -1
index 2afd2a8..d80d482 100644
@@ -1409,7 +1409,7 @@ static ssize_t read_flush(struct file *file, char __user *buf,
 			  size_t count, loff_t *ppos,
 			  struct cache_detail *cd)
 {
-	char tbuf[20];
+	char tbuf[ULONG_STR_MAX + 1];
 	unsigned long p = *ppos;
 	size_t len;
 
#9 lore raw
In reply to Jim Rees
Quoted 1 line · Jim Rees

Bernd Petrovitsch wrote:

[...]

Quoted 9 lines

A pure K&R-C version would use a string:
---- snip ----
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] ---- snip ----
(if I converted them properly into hexadecimal) and that gives a "char" which is happily promoted to whatever one needs in that place.

1. That may give you a signed char on some architectures, which is not what you want (although it doesn't matter since the values are all < 128)

And it depends on compiler options BTW.

But we can easily cast it:
#define base10len(i) ((unsigned char)"\x1\x3\x5\x8\xA\xD\xF\x11\x14"[sizeof(i)])

Quoted 1 line

2. If you put this in a .h, you'll get multiple copies of the array

That depends on the compiler.

Quoted 1 line

3. No bounds checking (but in ninja K&R style you never check bounds)

Well, I assumed that we don't use VLAs as parameter for the sizeof() so the value is compile time known and the better C compilers can check it. And then, there is no reason to store the string as such too.

[....]

Quoted 1 line

Pure K&R:

We can (and should) make it "const" too.

Quoted 2 lines

base10.h:
extern unsigned char base10len_vals[];

extern const unsigned char base10len_vals[];

Quoted 4 lines

#define base10len(i) (base10len_vals[sizeof(i)])

base10.c:
unsigned char base10len_vals[] = {1,3,5,8,10,13,15,17,20};

const unsigned char base10len_vals[] = {1,3,5,8,10,13,15,17,20};

Quoted 1 line

But I still like my way better.

The 8 wasted bytes probably do not matter ....

Bernd

Signature · 2 lines
Bernd Petrovitsch                  Email : [email protected]
                     LUGA : http://www.luga.at
#11 lore raw
In reply to Jim Rees

On Friday 2012-09-14 14:30, Jim Rees wrote in an odd quote style (the > are mine):

Quoted 11 lines

Bernd Petrovitsch wrote:

A pure K&R-C version would use a string:
---- snip ----
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] ---- snip ----
(if I converted them properly into hexadecimal) and that gives a "char" which is happily promoted to whatever one needs in that place.

1. That may give you a signed char on some architectures, which is not what you want (although it doesn't matter since the values are all < 128)

Convert.

Quoted 1 line

2. If you put this in a .h, you'll get multiple copies of the array

The gcc compiler is smart enough to optimize that away. A string literal is known at compile-time and immutable by definition. sizeof(i) is a compile-time constant, also by definition. Therefore, any "foo"[bar] is resolvable at compile time. Even gcc -O0 knows that.

That makes it possible to write
char f[base10len(whatever)];
without depending on C99 VLAs.

Quoted 10 lines

Pure K&R:

base10.h:
extern unsigned char base10len_vals[];
#define base10len(i) (base10len_vals[sizeof(i)])

base10.c:
unsigned char base10len_vals[] = {1,3,5,8,10,13,15,17,20};

But I still like my way better.

Your way does not function as originally desired.

* base10len(i) no longer expands to a compile-time constant

* you will definitely have a variable base10len_vals in your objects, so you waste a read operation whenever it is used.

#14 lore raw
In reply to Jan Engelhardt
Quoted 3 lines · Jan Engelhardt

A pure K&R-C version would use a string:
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] (if I converted them properly into hexadecimal)

The syntax is \x01\x03\x05...

K&R doesn't have the \x escape, only \0 (octal).

#10 lore raw
In reply to Bernd Petrovitsch

Bernd Petrovitsch wrote:

[....]

Quoted 1 line

Pure K&R:

We can (and should) make it "const" too.

No "const" in K&R either. But I think we can assume the kernel will be compiled with something a bit more advance.

#12 lore raw
In reply to Jan Engelhardt

Jan Engelhardt wrote:

Your way does not function as originally desired.

* base10len(i) no longer expands to a compile-time constant

* you will definitely have a variable base10len_vals in your objects, so you waste a read operation whenever it is used.

No, I meant my original way:
#define base10len(i) (sizeof(i) * 8 * 3 / 10 + 1)

#15 lore raw
In reply to Jim Rees
Quoted 8 lines · Jim Rees
Quoted 3 lines · Jan Engelhardt

A pure K&R-C version would use a string:
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] (if I converted them properly into hexadecimal)

The syntax is \x01\x03\x05...

K&R doesn't have the \x escape, only \0 (octal).

People recommend K&R only for the introductory reading, not for its actuality.

#16 lore raw
Quoted 8 lines · Jan Engelhardt
Quoted 7 lines · Jim Rees
Quoted 3 lines · Jan Engelhardt

A pure K&R-C version would use a string:
#define base10len(i) "\0x1\0x3\0x5\0x8\0x0A\0x0D\0x0F\0x11\0x14"[sizeof(i)] (if I converted them properly into hexadecimal)

The syntax is \x01\x03\x05...

K&R doesn't have the \x escape, only \0 (octal).

We cuold use octal too.

Quoted 2 lines

People recommend K&R only for the introductory reading, not for its actuality.

And I actually used it to show that no gcc-isms are necessary. ANSI-C is fine too for that case.

Bernd

Signature · 2 lines
Bernd Petrovitsch                  Email : [email protected]
                     LUGA : http://www.luga.at