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

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

[zengzhaoxiu]

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

[PATCH 2/2] lib: kstrtox: _parse_integer: use hex_to_bin instead local conversion, and reduce branches

[zengzhaoxiu]

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

Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com>
---
 lib/kstrtox.c | 22 +++++-----------------
 1 file changed, 5 insertions(+), 17 deletions(-)

diff --git a/lib/kstrtox.c b/lib/kstrtox.c
index d8a5cf6..70d3374 100644
--- a/lib/kstrtox.c
+++ b/lib/kstrtox.c
@@ -48,38 +48,26 @@ unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long
 {
 	unsigned long long res;
 	unsigned int rv;
-	int overflow;
+	unsigned int overflow;
+	unsigned int val;
 
 	res = 0;
 	rv = 0;
 	overflow = 0;
-	while (*s) {
-		unsigned int val;
-
-		if ('0' <= *s && *s <= '9')
-			val = *s - '0';
-		else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')
-			val = _tolower(*s) - 'a' + 10;
-		else
-			break;
-
-		if (val >= base)
-			break;
+	while ((val = hex_to_bin(*s++)) < base) {
 		/*
 		 * Check for overflow only if we are within range of
 		 * it in the max base we support (16)
 		 */
 		if (unlikely(res & (~0ull << 60))) {
 			if (res > div_u64(ULLONG_MAX - val, base))
-				overflow = 1;
+				overflow = KSTRTOX_OVERFLOW;
 		}
 		res = res * base + val;
 		rv++;
-		s++;
 	}
 	*p = res;
-	if (overflow)
-		rv |= KSTRTOX_OVERFLOW;
+	rv |= overflow;
 	return rv;
 }
 
-- 
2.7.4

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

[Andy Shevchenko]

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

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

[Steven Rostedt]

On Thu, 30 Jun 2016 00:15:54 +0800
zengzhaoxiu@163.com wrote:

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

I have to ask, what hot paths call this where we need to add a table
for optimization. And there's a chance that this wont even optimize the
flow and may even slow down execution as the table will now need to be
loaded into cache.

-- Steve


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

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

[Michal Nazarewicz]

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»

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

[Andy Shevchenko]

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

Re: [PATCH 2/2] lib: kstrtox: _parse_integer: use hex_to_bin instead local conversion, and reduce branches

[Alexey Dobriyan]

On Thu, Jun 30, 2016 at 12:22:13AM +0800, zengzhaoxiu@163.com wrote:
> --- a/lib/kstrtox.c
> +++ b/lib/kstrtox.c
> @@ -48,38 +48,26 @@ unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long
>  {
>  	unsigned long long res;
>  	unsigned int rv;
> -	int overflow;
> +	unsigned int overflow;
> +	unsigned int val;
>  
>  	res = 0;
>  	rv = 0;
>  	overflow = 0;
> -	while (*s) {
> -		unsigned int val;
> -
> -		if ('0' <= *s && *s <= '9')
> -			val = *s - '0';
> -		else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')
> -			val = _tolower(*s) - 'a' + 10;
> -		else
> -			break;
> -
> -		if (val >= base)
> -			break;
> +	while ((val = hex_to_bin(*s++)) < base) {

I hate this function. And it has a branch if your table patch doesn't
go it. And it is beartrap (unsigned int = -1 < base).

ACK *s++ bit, though. Should make code smaller in my experience.
Please, change to "unsigned char c; while ((c = *s++)".
This is about maximum code compression I can understand.

>  		/*
>  		 * Check for overflow only if we are within range of
>  		 * it in the max base we support (16)
>  		 */
>  		if (unlikely(res & (~0ull << 60))) {
>  			if (res > div_u64(ULLONG_MAX - val, base))
> -				overflow = 1;
> +				overflow = KSTRTOX_OVERFLOW;

Just do |= KSTRTOX_OVERFLOW here directly, it is the leftmost bit.

>  		}
>  		res = res * base + val;
>  		rv++;
> -		s++;
>  	}
>  	*p = res;
> -	if (overflow)
> -		rv |= KSTRTOX_OVERFLOW;
> +	rv |= overflow;
>  	return rv;
>  }

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

[Zhaoxiu Zeng]

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.

Re: [PATCH 2/2] lib: kstrtox: _parse_integer: use hex_to_bin instead local conversion, and reduce branches

[Zhaoxiu Zeng]

On 2016/6/30 6:06, Alexey Dobriyan wrote:
> On Thu, Jun 30, 2016 at 12:22:13AM +0800, zengzhaoxiu@163.com wrote:
>> --- a/lib/kstrtox.c
>> +++ b/lib/kstrtox.c
>> @@ -48,38 +48,26 @@ unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long
>>  {
>>  	unsigned long long res;
>>  	unsigned int rv;
>> -	int overflow;
>> +	unsigned int overflow;
>> +	unsigned int val;
>>  
>>  	res = 0;
>>  	rv = 0;
>>  	overflow = 0;
>> -	while (*s) {
>> -		unsigned int val;
>> -
>> -		if ('0' <= *s && *s <= '9')
>> -			val = *s - '0';
>> -		else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')
>> -			val = _tolower(*s) - 'a' + 10;
>> -		else
>> -			break;
>> -
>> -		if (val >= base)
>> -			break;
>> +	while ((val = hex_to_bin(*s++)) < base) {
> I hate this function. And it has a branch if your table patch doesn't
> go it. And it is beartrap (unsigned int = -1 < base).

How about this?

for (;;) {
    unsigned int val = hex_to_bin(*s++);
    if (val >= base)
        break;

> ACK *s++ bit, though. Should make code smaller in my experience.
> Please, change to "unsigned char c; while ((c = *s++)".
> This is about maximum code compression I can understand.

The previous tests are useless until reach the end of s.
The '\0' will be caught by "if (val >= base)" too.

>>  		/*
>>  		 * Check for overflow only if we are within range of
>>  		 * it in the max base we support (16)
>>  		 */
>>  		if (unlikely(res & (~0ull << 60))) {
>>  			if (res > div_u64(ULLONG_MAX - val, base))
>> -				overflow = 1;
>> +				overflow = KSTRTOX_OVERFLOW;
> Just do |= KSTRTOX_OVERFLOW here directly, it is the leftmost bit.

I thought so too at first， but finally I decided to reserve the varaible "overflow",
because this hack depend on the definition of KSTRTOX_OVERFLOW.

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

[Joe Perches]

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;
 }

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

[Geert Uytterhoeven]

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

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

[Joe Perches]

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.

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

[Andy Shevchenko]

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

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

[Michal Nazarewicz]

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»