lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <xa1t1t3fg83y.fsf@mina86.com>
Date:	Wed, 29 Jun 2016 20:31:13 +0200
From:	Michal Nazarewicz <mina86@...a86.com>
To:	zengzhaoxiu@....com, linux-kernel@...r.kernel.org
Cc:	Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Hidehiro Kawai <hidehiro.kawai.ez@...achi.com>,
	Borislav Petkov <bp@...e.de>, Michal Hocko <mhocko@...e.com>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Nicolas Iooss <nicolas.iooss_linux@....org>,
	"Steven Rostedt \(Red Hat\)" <rostedt@...dmis.org>,
	Gustavo Padovan <gustavo.padovan@...labora.co.uk>,
	Geert Uytterhoeven <geert@...ux-m68k.org>,
	Horacio Mijail Anton Quiles <hmijail@...il.com>,
	Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Subject: Re: [PATCH 1/2] lib: hexdump: use a look-up table to do hex_to_bin

On Thu, Jun 30 2016, zengzhaoxiu wrote:
> From: Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
>
> Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@...il.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@...a86.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@...a86.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»

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ