Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jim Rees]

J. Bruce Fields wrote:

  From: "J. Bruce Fields" <bfields@redhat.com>
  
  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 <rees@umich.edu>.  I'm thinking of
patenting the algorithm.

[PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[J. Bruce Fields]

From: "J. Bruce Fields" <bfields@redhat.com>

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).

Signed-off-by: J. Bruce Fields <bfields@redhat.com>
---
 include/linux/string.h |    6 ++++++
 net/sunrpc/cache.c     |    2 +-
 2 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/include/linux/string.h b/include/linux/string.h
index ffe0442..d4809b7 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -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);
diff --git a/net/sunrpc/cache.c b/net/sunrpc/cache.c
index 2afd2a8..1dcd2b3 100644
--- a/net/sunrpc/cache.c
+++ b/net/sunrpc/cache.c
@@ -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;
 
-- 
1.7.9.5

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Al Viro]

On Tue, Aug 21, 2012 at 05:22:27PM -0400, Jim Rees wrote:
> J. Bruce Fields wrote:
> 
>   From: "J. Bruce Fields" <bfields@redhat.com>
>   
>   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 <rees@umich.edu>.  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.

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[J. Bruce Fields]

On Tue, Aug 21, 2012 at 11:06:13PM +0100, Al Viro wrote:
> On Tue, Aug 21, 2012 at 05:22:27PM -0400, Jim Rees wrote:
> > J. Bruce Fields wrote:
> > 
> >   From: "J. Bruce Fields" <bfields@redhat.com>
> >   
> >   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 <rees@umich.edu>.  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.

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.

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jim Rees]

Al Viro wrote:

  On Tue, Aug 21, 2012 at 05:22:27PM -0400, Jim Rees wrote:
  > J. Bruce Fields wrote:
  > 
  >   From: "J. Bruce Fields" <bfields@redhat.com>
  >   
  >   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 <rees@umich.edu>.  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.

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jan Engelhardt]

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

>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).
>
>+/*
>+ * 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")];

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Bernd Petrovitsch]

On Mon, 2012-09-10 at 08:19 +0200, Jan Engelhardt wrote:
> On Tuesday 2012-08-21 23:29, J. Bruce Fields wrote:
[...]
> >+/*
> >+ * 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
-- 
Bernd Petrovitsch                  Email : bernd@petrovitsch.priv.at
                     LUGA : http://www.luga.at

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jim Rees]

Bernd Petrovitsch wrote:

  On Mon, 2012-09-10 at 08:19 +0200, Jan Engelhardt wrote:
  > On Tuesday 2012-08-21 23:29, J. Bruce Fields wrote:
  [...]
  > >+/*
  > >+ * 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.

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jan Engelhardt]

On Friday 2012-09-14 11:17, Bernd Petrovitsch wrote:
>Shouldn't that have been
>----  snip ----
>#define base10len(i) ((const int[]){1,3,5,8,10,13,15,17,20}[sizeof(i)])
>----  snip ----
Yeah.

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

>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)])

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[J. Bruce Fields]

On Fri, Sep 14, 2012 at 08:30:14AM -0400, Jim Rees wrote:
> 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 <bfields@redhat.com>
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?
    
    Suggested-by: Jim Rees <rees@umich.edu>
    Signed-off-by: J. Bruce Fields <bfields@redhat.com>

diff --git a/include/linux/string.h b/include/linux/string.h
index ffe0442..38da7a0 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -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);
diff --git a/net/sunrpc/cache.c b/net/sunrpc/cache.c
index 2afd2a8..d80d482 100644
--- a/net/sunrpc/cache.c
+++ b/net/sunrpc/cache.c
@@ -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;
 

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Bernd Petrovitsch]

On Fre, 2012-09-14 at 08:30 -0400, Jim Rees wrote:
> 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)

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)])

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

That depends on the compiler.

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

[....]
> Pure K&R:

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

> base10.h:
> extern unsigned char base10len_vals[];
extern const 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};
const unsigned char base10len_vals[] = {1,3,5,8,10,13,15,17,20};
> But I still like my way better.

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

	Bernd
-- 
Bernd Petrovitsch                  Email : bernd@petrovitsch.priv.at
                     LUGA : http://www.luga.at

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jan Engelhardt]

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

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

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

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

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jim Rees]

Jan Engelhardt wrote:

  >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).

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jim Rees]

Bernd Petrovitsch wrote:

  [....]
  > 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.

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jim Rees]

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)

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Jan Engelhardt]

On Friday 2012-09-14 15:46, Jim Rees wrote:

>Jan Engelhardt wrote:
>
>  >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.

Re: [PATCH] strings: helper for maximum decimal encoding of an unsigned integer

[Bernd Petrovitsch]

On Fre, 2012-09-14 at 16:25 +0200, Jan Engelhardt wrote:
> On Friday 2012-09-14 15:46, Jim Rees wrote:
> >Jan Engelhardt wrote:
> >  >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.

> 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
-- 
Bernd Petrovitsch                  Email : bernd@petrovitsch.priv.at
                     LUGA : http://www.luga.at