Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1433901 > unrolled thread

[PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin

Back to article view | Back to linux.kernel

Contents

  [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin zengzhaoxiu@163.com - 2016-06-29 18:30 +0200
    Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2016-06-29 18:30 +0200
    Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Michal Nazarewicz <mina86@mina86.com> - 2016-06-29 20:40 +0200
      Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2016-06-29 21:00 +0200
        Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Joe Perches <joe@perches.com> - 2016-06-30 21:30 +0200
          Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Geert Uytterhoeven <geert@linux-m68k.org> - 2016-06-30 21:50 +0200
            Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Joe Perches <joe@perches.com> - 2016-06-30 22:10 +0200
              Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Andy Shevchenko <andriy.shevchenko@linux.intel.com> - 2016-06-30 22:50 +0200
          Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Michal Nazarewicz <mina86@mina86.com> - 2016-06-30 23:20 +0200
      Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin Zhaoxiu Zeng <zengzhaoxiu@163.com> - 2016-06-30 16:30 +0200

#1433901 — [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin

From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>

Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
---
 include/linux/kernel.h | 15 ++++++++++++++-
 lib/hexdump.c          | 36 +++++++++++++++++++-----------------
 2 files changed, 33 insertions(+), 18 deletions(-)

diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 94aa10f..72a0432 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -532,7 +532,20 @@ static inline char *hex_byte_pack_upper(char *buf, u8 byte)
 	return buf;
 }
 
-extern int hex_to_bin(char ch);
+extern const int8_t h2b_lut[];
+
+/**
+ * hex_to_bin - convert a hex digit to its real value
+ * @ch: ascii character represents hex digit
+ *
+ * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad
+ * input.
+ */
+static inline int hex_to_bin(char ch)
+{
+	return h2b_lut[(unsigned char)ch];
+}
+
 extern int __must_check hex2bin(u8 *dst, const char *src, size_t count);
 extern char *bin2hex(char *dst, const void *src, size_t count);
 
diff --git a/lib/hexdump.c b/lib/hexdump.c
index 992457b..878697f 100644
--- a/lib/hexdump.c
+++ b/lib/hexdump.c
@@ -18,23 +18,25 @@ EXPORT_SYMBOL(hex_asc);
 const char hex_asc_upper[] = "0123456789ABCDEF";
 EXPORT_SYMBOL(hex_asc_upper);
 
-/**
- * hex_to_bin - convert a hex digit to its real value
- * @ch: ascii character represents hex digit
- *
- * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad
- * input.
- */
-int hex_to_bin(char ch)
-{
-	if ((ch >= '0') && (ch <= '9'))
-		return ch - '0';
-	ch = tolower(ch);
-	if ((ch >= 'a') && (ch <= 'f'))
-		return ch - 'a' + 10;
-	return -1;
-}
-EXPORT_SYMBOL(hex_to_bin);
+const int8_t h2b_lut[] = {
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1,
+	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+};
+EXPORT_SYMBOL(h2b_lut);
 
 /**
  * hex2bin - convert an ascii hexadecimal string to its binary representation
-- 
2.7.4

[toc] | [next] | [standalone]

#1433902

On Thu, 2016-06-30 at 00:15 +0800, zengzhaoxiu@163.com wrote:
> From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
> 

No way.

At least commit message.
And prerequisite is the performance / memory foot print tests.

> Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
> ---
>  include/linux/kernel.h | 15 ++++++++++++++-
>  lib/hexdump.c          | 36 +++++++++++++++++++-----------------
>  2 files changed, 33 insertions(+), 18 deletions(-)
> 
> diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> index 94aa10f..72a0432 100644
> --- a/include/linux/kernel.h
> +++ b/include/linux/kernel.h
> @@ -532,7 +532,20 @@ static inline char *hex_byte_pack_upper(char
> *buf, u8 byte)
>  	return buf;
>  }
>  
> -extern int hex_to_bin(char ch);
> +extern const int8_t h2b_lut[];
> +
> +/**
> + * hex_to_bin - convert a hex digit to its real value
> + * @ch: ascii character represents hex digit
> + *
> + * hex_to_bin() converts one hex digit to its actual value or -1 in
> case of bad
> + * input.
> + */
> +static inline int hex_to_bin(char ch)
> +{
> +	return h2b_lut[(unsigned char)ch];
> +}
> +
>  extern int __must_check hex2bin(u8 *dst, const char *src, size_t
> count);
>  extern char *bin2hex(char *dst, const void *src, size_t count);
>  
> diff --git a/lib/hexdump.c b/lib/hexdump.c
> index 992457b..878697f 100644
> --- a/lib/hexdump.c
> +++ b/lib/hexdump.c
> @@ -18,23 +18,25 @@ EXPORT_SYMBOL(hex_asc);
>  const char hex_asc_upper[] = "0123456789ABCDEF";
>  EXPORT_SYMBOL(hex_asc_upper);
>  
> -/**
> - * hex_to_bin - convert a hex digit to its real value
> - * @ch: ascii character represents hex digit
> - *
> - * hex_to_bin() converts one hex digit to its actual value or -1 in
> case of bad
> - * input.
> - */
> -int hex_to_bin(char ch)
> -{
> -	if ((ch >= '0') && (ch <= '9'))
> -		return ch - '0';
> -	ch = tolower(ch);
> -	if ((ch >= 'a') && (ch <= 'f'))
> -		return ch - 'a' + 10;
> -	return -1;
> -}
> -EXPORT_SYMBOL(hex_to_bin);
> +const int8_t h2b_lut[] = {
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1,
> -1,
> +	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1,
> +};
> +EXPORT_SYMBOL(h2b_lut);
>  
>  /**
>   * hex2bin - convert an ascii hexadecimal string to its binary
> representation

-- 

Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

[toc] | [prev] | [next] | [standalone]

#1433965

On Thu, Jun 30 2016, zengzhaoxiu wrote:
> From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
>
> Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
> ---
>  include/linux/kernel.h | 15 ++++++++++++++-
>  lib/hexdump.c          | 36 +++++++++++++++++++-----------------
>  2 files changed, 33 insertions(+), 18 deletions(-)
>
> diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> index 94aa10f..72a0432 100644
> --- a/include/linux/kernel.h
> +++ b/include/linux/kernel.h
> @@ -532,7 +532,20 @@ static inline char *hex_byte_pack_upper(char *buf, u8 byte)
>  	return buf;
>  }
>  
> -extern int hex_to_bin(char ch);
> +extern const int8_t h2b_lut[];
> +
> +/**
> + * hex_to_bin - convert a hex digit to its real value
> + * @ch: ascii character represents hex digit
> + *
> + * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad
> + * input.
> + */
> +static inline int hex_to_bin(char ch)
> +{
> +	return h2b_lut[(unsigned char)ch];
> +}
> +
>  extern int __must_check hex2bin(u8 *dst, const char *src, size_t count);
>  extern char *bin2hex(char *dst, const void *src, size_t count);
>  
> diff --git a/lib/hexdump.c b/lib/hexdump.c
> index 992457b..878697f 100644
> --- a/lib/hexdump.c
> +++ b/lib/hexdump.c
> @@ -18,23 +18,25 @@ EXPORT_SYMBOL(hex_asc);
>  const char hex_asc_upper[] = "0123456789ABCDEF";
>  EXPORT_SYMBOL(hex_asc_upper);
>  
> -/**
> - * hex_to_bin - convert a hex digit to its real value
> - * @ch: ascii character represents hex digit
> - *
> - * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad
> - * input.
> - */
> -int hex_to_bin(char ch)
> -{
> -	if ((ch >= '0') && (ch <= '9'))
> -		return ch - '0';
> -	ch = tolower(ch);
> -	if ((ch >= 'a') && (ch <= 'f'))
> -		return ch - 'a' + 10;
> -	return -1;
> -}
> -EXPORT_SYMBOL(hex_to_bin);
> +const int8_t h2b_lut[] = {
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1,
> +	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +};
> +EXPORT_SYMBOL(h2b_lut);
>  
>  /**
>   * hex2bin - convert an ascii hexadecimal string to its binary representation

So this replaces table lookup in tolower with an explicit table lookup
here while also removing some branches.

Is that an improvement?  Hard to say.  _ctype table is used by all the
other isfoo macros so there’s a chance it’s already in cache the first
time hex_to_bin is called.  Having to read the data into cache may
overwhelm advantages of lack of branches.

Perhaps it’s better to get rid of existing table lookup instead (as well
as a single branch):

--------- >8 -----------------------------------------------------------
From c6a104a0e3c11ef5172dd00d2dcd44df486d1b58 Mon Sep 17 00:00:00 2001
From: Michal Nazarewicz <mina86@mina86.com>
Date: Wed, 29 Jun 2016 20:16:34 +0200
Subject: [PATCH] lib: hexdump: avoid _ctype table lookup in hex_to_bin
 function

tolower macro maps to __tolower function which calls isupper to
to determine if character is an upper case letter before converting
it to lower case.  This preservers non-letters unchanged which is
what you want in usual case.

However, hex_to_bin does not care about non-letter characters so
such conversion can be performed as long as (i) upper case letters
become lower case, (ii) lower case letters are unchanged and (iii)
non-letters stay non-letters.

This is exactly what _tolower function does and using it makes it
possible to avoid _ctype table lookup performed by the isupper
table.

Furthermore, since _tolower conversion is done unconditionally, this
also eliminates a single branch.

Signed-off-by: Michal Nazarewicz <mina86@mina86.com>
---
 lib/hexdump.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/hexdump.c b/lib/hexdump.c
index 992457b..f184d7a 100644
--- a/lib/hexdump.c
+++ b/lib/hexdump.c
@@ -29,7 +29,7 @@ int hex_to_bin(char ch)
 {
 	if ((ch >= '0') && (ch <= '9'))
 		return ch - '0';
-	ch = tolower(ch);
+	ch = _tolower(ch);
 	if ((ch >= 'a') && (ch <= 'f'))
 		return ch - 'a' + 10;
 	return -1;
-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴイツ
«If at first you don’t succeed, give up skydiving»

[toc] | [prev] | [next] | [standalone]

#1433977

On Wed, 2016-06-29 at 20:31 +0200, Michal Nazarewicz wrote:
> On Thu, Jun 30 2016, zengzhaoxiu wrote:
> > From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
> > 
> > Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
> > ---
> >  include/linux/kernel.h | 15 ++++++++++++++-
> >  lib/hexdump.c          | 36 +++++++++++++++++++-----------------
> >  2 files changed, 33 insertions(+), 18 deletions(-)
> > 
> > diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> > index 94aa10f..72a0432 100644
> > --- a/include/linux/kernel.h
> > +++ b/include/linux/kernel.h
> > @@ -532,7 +532,20 @@ static inline char *hex_byte_pack_upper(char
> > *buf, u8 byte)
> >  	return buf;
> >  }
> >  
> > -extern int hex_to_bin(char ch);
> > +extern const int8_t h2b_lut[];
> > +
> > +/**
> > + * hex_to_bin - convert a hex digit to its real value
> > + * @ch: ascii character represents hex digit
> > + *
> > + * hex_to_bin() converts one hex digit to its actual value or -1 in
> > case of bad
> > + * input.
> > + */
> > +static inline int hex_to_bin(char ch)
> > +{
> > +	return h2b_lut[(unsigned char)ch];
> > +}
> > +
> >  extern int __must_check hex2bin(u8 *dst, const char *src, size_t
> > count);
> >  extern char *bin2hex(char *dst, const void *src, size_t count);
> >  
> > diff --git a/lib/hexdump.c b/lib/hexdump.c
> > index 992457b..878697f 100644
> > --- a/lib/hexdump.c
> > +++ b/lib/hexdump.c
> > @@ -18,23 +18,25 @@ EXPORT_SYMBOL(hex_asc);
> >  const char hex_asc_upper[] = "0123456789ABCDEF";
> >  EXPORT_SYMBOL(hex_asc_upper);
> >  
> > -/**
> > - * hex_to_bin - convert a hex digit to its real value
> > - * @ch: ascii character represents hex digit
> > - *
> > - * hex_to_bin() converts one hex digit to its actual value or -1 in
> > case of bad
> > - * input.
> > - */
> > -int hex_to_bin(char ch)
> > -{
> > -	if ((ch >= '0') && (ch <= '9'))
> > -		return ch - '0';
> > -	ch = tolower(ch);
> > -	if ((ch >= 'a') && (ch <= 'f'))
> > -		return ch - 'a' + 10;
> > -	return -1;
> > -}
> > -EXPORT_SYMBOL(hex_to_bin);
> > +const int8_t h2b_lut[] = {
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> > -1,
> > +};
> > +EXPORT_SYMBOL(h2b_lut);
> >  
> >  /**
> >   * hex2bin - convert an ascii hexadecimal string to its binary
> > representation
> 
> So this replaces table lookup in tolower with an explicit table lookup
> here while also removing some branches.
> 
> Is that an improvement?  Hard to say.  _ctype table is used by all the
> other isfoo macros so there’s a chance it’s already in cache the first
> time hex_to_bin is called.  Having to read the data into cache may
> overwhelm advantages of lack of branches.
> 
> Perhaps it’s better to get rid of existing table lookup instead (as
> well
> as a single branch):
> 
> --------- >8 -------------------------------------------------------
> ----
> From c6a104a0e3c11ef5172dd00d2dcd44df486d1b58 Mon Sep 17 00:00:00 2001
> From: Michal Nazarewicz <mina86@mina86.com>
> Date: Wed, 29 Jun 2016 20:16:34 +0200
> Subject: [PATCH] lib: hexdump: avoid _ctype table lookup in hex_to_bin
>  function
> 
> tolower macro maps to __tolower function which calls isupper to
> to determine if character is an upper case letter before converting
> it to lower case.  This preservers non-letters unchanged which is
> what you want in usual case.
> 
> However, hex_to_bin does not care about non-letter characters so
> such conversion can be performed as long as (i) upper case letters
> become lower case, (ii) lower case letters are unchanged and (iii)
> non-letters stay non-letters.
> 
> This is exactly what _tolower function does and using it makes it
> possible to avoid _ctype table lookup performed by the isupper
> table.
> 
> Furthermore, since _tolower conversion is done unconditionally, this
> also eliminates a single branch.

This change I agree with since _tolower() is specific for lib internal
usage in the kernel.

FWIW:
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>

> 
> Signed-off-by: Michal Nazarewicz <mina86@mina86.com>
> ---
>  lib/hexdump.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/hexdump.c b/lib/hexdump.c
> index 992457b..f184d7a 100644
> --- a/lib/hexdump.c
> +++ b/lib/hexdump.c
> @@ -29,7 +29,7 @@ int hex_to_bin(char ch)
>  {
>  	if ((ch >= '0') && (ch <= '9'))
>  		return ch - '0';
> -	ch = tolower(ch);
> +	ch = _tolower(ch);
>  	if ((ch >= 'a') && (ch <= 'f'))
>  		return ch - 'a' + 10;
>  	return -1;

-- 

Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

[toc] | [prev] | [next] | [standalone]

#1434803

On Wed, 2016-06-29 at 21:52 +0300, Andy Shevchenko wrote:
> On Wed, 2016-06-29 at 20:31 +0200, Michal Nazarewicz wrote:
[]
> > tolower macro maps to __tolower function which calls isupper to
> > to determine if character is an upper case letter before converting
> > it to lower case.  This preservers non-letters unchanged which is
> > what you want in usual case.
> > 
> > However, hex_to_bin does not care about non-letter characters so
> > such conversion can be performed as long as (i) upper case letters
> > become lower case, (ii) lower case letters are unchanged and (iii)
> > non-letters stay non-letters.
> > 
> > This is exactly what _tolower function does and using it makes it
> > possible to avoid _ctype table lookup performed by the isupper
> > table.
> > 
> > Furthermore, since _tolower conversion is done unconditionally, this
> > also eliminates a single branch.
> This change I agree with since _tolower() is specific for lib internal
> usage in the kernel.

Perhaps _tolower should be used a bit more in lib
---
 lib/string.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/lib/string.c b/lib/string.c
index ed83562..b0e72fd 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -53,8 +53,8 @@ int strncasecmp(const char *s1, const char *s2, size_t len)
 			break;
 		if (c1 == c2)
 			continue;
-		c1 = tolower(c1);
-		c2 = tolower(c2);
+		c1 = _tolower(c1);
+		c2 = _tolower(c2);
 		if (c1 != c2)
 			break;
 	} while (--len);
@@ -69,8 +69,8 @@ int strcasecmp(const char *s1, const char *s2)
 	int c1, c2;
 
 	do {
-		c1 = tolower(*s1++);
-		c2 = tolower(*s2++);
+		c1 = _tolower(*s1++);
+		c2 = _tolower(*s2++);
 	} while (c1 == c2 && c1 != 0);
 	return c1 - c2;
 }

[toc] | [prev] | [next] | [standalone]

#1434817

Hi Joe,

On Thu, Jun 30, 2016 at 9:26 PM, Joe Perches <joe@perches.com> wrote:
> On Wed, 2016-06-29 at 21:52 +0300, Andy Shevchenko wrote:
>> On Wed, 2016-06-29 at 20:31 +0200, Michal Nazarewicz wrote:
> []
>> > tolower macro maps to __tolower function which calls isupper to
>> > to determine if character is an upper case letter before converting
>> > it to lower case.  This preservers non-letters unchanged which is
>> > what you want in usual case.
>> >
>> > However, hex_to_bin does not care about non-letter characters so
>> > such conversion can be performed as long as (i) upper case letters
>> > become lower case, (ii) lower case letters are unchanged and (iii)
>> > non-letters stay non-letters.
>> >
>> > This is exactly what _tolower function does and using it makes it
>> > possible to avoid _ctype table lookup performed by the isupper
>> > table.
>> >
>> > Furthermore, since _tolower conversion is done unconditionally, this
>> > also eliminates a single branch.
>> This change I agree with since _tolower() is specific for lib internal
>> usage in the kernel.
>
> Perhaps _tolower should be used a bit more in lib
> ---
>  lib/string.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/lib/string.c b/lib/string.c
> index ed83562..b0e72fd 100644
> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -53,8 +53,8 @@ int strncasecmp(const char *s1, const char *s2, size_t len)
>                         break;
>                 if (c1 == c2)
>                         continue;
> -               c1 = tolower(c1);
> -               c2 = tolower(c2);
> +               c1 = _tolower(c1);
> +               c2 = _tolower(c2);

No, we do care about non-alphabetical characters here.
Using _tolower is equivalent to ignoring bit 5 in each byte of the string.

>                 if (c1 != c2)
>                         break;
>         } while (--len);
> @@ -69,8 +69,8 @@ int strcasecmp(const char *s1, const char *s2)
>         int c1, c2;
>
>         do {
> -               c1 = tolower(*s1++);
> -               c2 = tolower(*s2++);
> +               c1 = _tolower(*s1++);
> +               c2 = _tolower(*s2++);

Likewise

>         } while (c1 == c2 && c1 != 0);
>         return c1 - c2;
>  }

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

[toc] | [prev] | [next] | [standalone]

#1434826

On Thu, 2016-06-30 at 21:42 +0200, Geert Uytterhoeven wrote:
> Hi Joe,

Hi Geert.

> On Thu, Jun 30, 2016 at 9:26 PM, Joe Perches <joe@perches.com> wrote:
[]
> > Perhaps _tolower should be used a bit more in lib
[]
> No, we do care about non-alphabetical characters here.
> Using _tolower is equivalent to ignoring bit 5 in each byte of the string.

Yeah, that can't work.
Rasmus V wrote the same thing to me offline.

[toc] | [prev] | [next] | [standalone]

#1434835

On Thu, 2016-06-30 at 13:06 -0700, Joe Perches wrote:
> On Thu, 2016-06-30 at 21:42 +0200, Geert Uytterhoeven wrote:
> > 
> Yeah, that can't work.
> Rasmus V wrote the same thing to me offline.

Just read the thread and +1 to Rasmus' and Geert's opinion.

-- 

Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

[toc] | [prev] | [next] | [standalone]

#1434857

On Thu, Jun 30 2016, Joe Perches wrote:
> On Wed, 2016-06-29 at 21:52 +0300, Andy Shevchenko wrote:
>> On Wed, 2016-06-29 at 20:31 +0200, Michal Nazarewicz wrote:
> []
>> > tolower macro maps to __tolower function which calls isupper to
>> > to determine if character is an upper case letter before converting
>> > it to lower case.  This preservers non-letters unchanged which is
>> > what you want in usual case.
>> > 
>> > However, hex_to_bin does not care about non-letter characters so
>> > such conversion can be performed as long as (i) upper case letters
>> > become lower case, (ii) lower case letters are unchanged and (iii)
>> > non-letters stay non-letters.
>> > 
>> > This is exactly what _tolower function does and using it makes it
>> > possible to avoid _ctype table lookup performed by the isupper
>> > table.
>> > 
>> > Furthermore, since _tolower conversion is done unconditionally, this
>> > also eliminates a single branch.
>> This change I agree with since _tolower() is specific for lib internal
>> usage in the kernel.
>
> Perhaps _tolower should be used a bit more in lib
> ---
>  lib/string.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/lib/string.c b/lib/string.c
> index ed83562..b0e72fd 100644
> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -53,8 +53,8 @@ int strncasecmp(const char *s1, const char *s2, size_t len)
>  			break;
>  		if (c1 == c2)
>  			continue;
> -		c1 = tolower(c1);
> -		c2 = tolower(c2);
> +		c1 = _tolower(c1);
> +		c2 = _tolower(c2);

That won’t work.  If someone really wanted, we probably could get away
with:

bool strneq(const char *s1, const char *s2, size_t len)
{
	/* Yes, Virginia, it had better be unsigned */
	unsigned char c1, c2, x;

	if (!len)
		return true;

	do {
		c1 = *s1++;
		c2 = *s2++;
		if (!c1 || !c2)
			break;
		x = c1 ^ c2;
		if (x && (x != 0x20 || !isalpha(c1) ||
			  _tolower(c1) != _tolower(c2)))
			return false;
	} while (--len);
	return c1 == c2;
}

I didn’t find any uses of strncasecmp where the result isn’t simply used
as a boolean equal/non-equal test.  This is a bigger undertaking though.

We could try doing this though:

---
 include/linux/ctype.h | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/include/linux/ctype.h b/include/linux/ctype.h
index 653589e..b1ef461 100644
--- a/include/linux/ctype.h
+++ b/include/linux/ctype.h
@@ -35,17 +35,19 @@ extern const unsigned char _ctype[];
 #define isascii(c) (((unsigned char)(c))<=0x7f)
 #define toascii(c) (((unsigned char)(c))&0x7f)
 
+#define _CTYPE_LOWER_BIT 0x20  /* bit determining if letter is lower case */
+
 static inline unsigned char __tolower(unsigned char c)
 {
 	if (isupper(c))
-		c -= 'A'-'a';
+		c |= _CTYPE_LOWER_BIT;
 	return c;
 }
 
 static inline unsigned char __toupper(unsigned char c)
 {
 	if (islower(c))
-		c -= 'a'-'A';
+		c &= ~_CTYPE_LOWER_BIT;
 	return c;
 }
 
@@ -58,7 +60,7 @@ static inline unsigned char __toupper(unsigned char c)
  */
 static inline char _tolower(const char c)
 {
-	return c | 0x20;
+	return c | _CTYPE_LOWER_BIT;
 }
 
 /* Fast check for octal digit */
-- 
2.8.0.rc3.226.g39d4020

but whether it’s actually faster on modern hardware, I have no idea.
Similarly, a lot of ‘foo - '0'’ could be replaced by ‘foo & 0xf’, but
this again is a bigger undertaking.

>  		if (c1 != c2)
>  			break;
>  	} while (--len);
> @@ -69,8 +69,8 @@ int strcasecmp(const char *s1, const char *s2)
>  	int c1, c2;
>  
>  	do {
> -		c1 = tolower(*s1++);
> -		c2 = tolower(*s2++);
> +		c1 = _tolower(*s1++);
> +		c2 = _tolower(*s2++);
>  	} while (c1 == c2 && c1 != 0);
>  	return c1 - c2;
>  }
>
>

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴイツ
«If at first you don’t succeed, give up skydiving»

[toc] | [prev] | [next] | [standalone]

#1434622

On 2016/6/30 2:31, Michal Nazarewicz wrote:
> On Thu, Jun 30 2016, zengzhaoxiu wrote:
.......
>> So this replaces table lookup in tolower with an explicit table lookup
>> here while also removing some branches.
>>
>> Is that an improvement?  Hard to say.  _ctype table is used by all the
>> other isfoo macros so there’s a chance it’s already in cache the first
>> time hex_to_bin is called.  Having to read the data into cache may
>> overwhelm advantages of lack of branches.

In the 2nd patch, I use the inlined hex_to_bin to replace the local conversion
in _parse_integer which used by all kstrto... functions, so the heat of h2b_lut
may not be less than _ctype table. 

Additionally，in the vast majority of cases，only these bytes (0x00, 0x30~0x39,
 0x41~0x46, 0x61~0x66) will be used.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web