linux-kernel - Re: [PATCH v4] x86/lib: Optimize num_digits() and fix INT

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: <20260121113643.22718a3d@pumpkin>
Date: Wed, 21 Jan 2026 11:36:43 +0000
From: David Laight <david.laight.linux@...il.com>
To: David Desobry <david.desobry@...malgen.com>
Cc: tglx@...nel.org, mingo@...hat.com, bp@...en8.de,
 dave.hansen@...ux.intel.com, x86@...nel.org, hpa@...or.com,
 linux-kernel@...r.kernel.org
Subject: Re: [PATCH v4] x86/lib: Optimize num_digits() and fix INT_MIN
 overflow

On Wed, 21 Jan 2026 10:39:11 +0100
David Desobry <david.desobry@...malgen.com> wrote:

> The current implementation of num_digits() uses a loop with repeated
> multiplication, which is inefficient. Furthermore, it takes a signed
> integer which leads to undefined behavior when negating INT_MIN.
> 
> As this function is only used for unsigned magnitudes in the kernel code,
> convert the interface to take an unsigned int. This naturally resolves
> the INT_MIN overflow issue.
> 
> Replace the loop with a branchless sequence using inline assembly. By
> using the 'sbb' instruction against the carry flag after comparisons,
> we eliminate all conditional branches. This provides constant-time
> performance and avoids CPU branch misprediction penalties.

Don't do this version, it isn't worth the effort.

	David

> 
> Update the function comment to reflect that signs are no longer handled.
> 
> Signed-off-by: David Desobry <david.desobry@...malgen.com>
> ---
>  v4:
>  - Switched to branchless inline assembly. 
>  - Changed function signature to unsigned int.
>  - Updated prototype in arch/x86/include/asm/misc.h. 
> 
>  arch/x86/include/asm/misc.h |  2 +-
>  arch/x86/lib/misc.c         | 28 +++++++++++++---------------
>  2 files changed, 14 insertions(+), 16 deletions(-)
> 
> diff --git a/arch/x86/include/asm/misc.h b/arch/x86/include/asm/misc.h
> index bb049cca3729..48b6bd7c08b9 100644
> --- a/arch/x86/include/asm/misc.h
> +++ b/arch/x86/include/asm/misc.h
> @@ -2,6 +2,6 @@
>  #ifndef _ASM_X86_MISC_H
>  #define _ASM_X86_MISC_H
>  
> -int num_digits(int val);
> +int num_digits(unsigned int val);
>  
>  #endif /* _ASM_X86_MISC_H */
> diff --git a/arch/x86/lib/misc.c b/arch/x86/lib/misc.c
> index 40b81c338ae5..9623795b059f 100644
> --- a/arch/x86/lib/misc.c
> +++ b/arch/x86/lib/misc.c
> @@ -2,23 +2,21 @@
>  #include <asm/misc.h>
>  
>  /*
> - * Count the digits of @val including a possible sign.
> - *
> - * (Typed on and submitted from hpa's mobile phone.)
> + * Count the decimal digits of an unsigned integer.
>   */
> -int num_digits(int val)
> +int num_digits(unsigned int x)
>  {
> -	long long m = 10;
> -	int d = 1;
> +	int n = 0;
>  
> -	if (val < 0) {
> -		d++;
> -		val = -val;
> -	}
> +	asm("cmp %2,%1; sbb $-2,%0" : "+r" (n) : "r" (x), "g" (10));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (100));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (1000));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (10000));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (100000));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (1000000));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (10000000));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (100000000));
> +	asm("cmp %2,%1; sbb $-1,%0" : "+r" (n) : "r" (x), "g" (1000000000));
>  
> -	while (val >= m) {
> -		m *= 10;
> -		d++;
> -	}
> -	return d;
> +	return n;
>  }