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

[Andy Shevchenko <andriy.shevchenko@linux.intel.com>]

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