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@xxxxxxxxx>
>
> Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@xxxxxxxxx>
> ---
>  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 -----------------------------------------------------------