linux-kernel - Re: [PATCH v2] 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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20260120214612.73b83cbe@pumpkin>
Date: Tue, 20 Jan 2026 21:46:12 +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 v2] x86/lib: Optimize num_digits() and fix INT_MIN
 overflow

On Tue, 20 Jan 2026 18:47:48 +0100
David Desobry <david.desobry@...malgen.com> wrote:

> The current implementation of num_digits() uses a loop with repeated
> multiplication, which is inefficient. Furthermore, the negation of
> the input value "val = -val" causes undefined behavior when val is
> INT_MIN, as its absolute value cannot be represented as a 32-bit integer.
> 
> Replace the loop with a switch statement using GCC case ranges. This
> allows the compiler to generate a jump table or a series of optimized
> comparisons, providing O(1) performance. By using an unsigned int to
> handle the magnitude, we safely handle the INT_MIN case without
> relying on 64-bit types or undefined signed overflow.
> 
> Removed the outdated comment.
> 
> Signed-off-by: David Desobry <david.desobry@...malgen.com>
> ---
> v2:
>  - Replaced loop with switch statement and GCC case ranges.
>  - Fixed INT_MIN overflow using unsigned int cast instead of s64/long long.
>  - Removed outdated comment regarding mobile submission.
>  arch/x86/lib/misc.c | 35 +++++++++++++++++++++++++----------
>  1 file changed, 25 insertions(+), 10 deletions(-)
> 
> diff --git a/arch/x86/lib/misc.c b/arch/x86/lib/misc.c
> index 40b81c338ae5..03ba028d5326 100644
> --- a/arch/x86/lib/misc.c
> +++ b/arch/x86/lib/misc.c
> @@ -3,22 +3,37 @@
>  
>  /*
>   * Count the digits of @val including a possible sign.
> - *
> - * (Typed on and submitted from hpa's mobile phone.)
>   */
>  int num_digits(int val)
>  {
> -	long long m = 10;
> -	int d = 1;
> +	unsigned int v = val;
> +	int d = 0;
>  
>  	if (val < 0) {
> -		d++;
> -		val = -val;
> +		d = 1;
> +		v = -v;
>  	}

Maybe better to write as:
	if (val < 0) {
		d = 1;
		v = -val;
	} else {
		d = 0;
		v = val;
	}

The compiler will only generate one jump.

>  
> -	while (val >= m) {
> -		m *= 10;
> -		d++;
> +	switch (v) {
> +	case 0 ... 9:
> +		return d + 1;
> +	case 10 ... 99:
> +		return d + 2;
> +	case 100 ... 999:
> +		return d + 3;
> +	case 1000 ... 9999:
> +		return d + 4;
> +	case 10000 ... 99999:
> +		return d + 5;
> +	case 100000 ... 999999:
> +		return d + 6;
> +	case 1000000 ... 9999999:
> +		return d + 7;
> +	case 10000000 ... 99999999:
> +		return d + 8;
> +	case 100000000 ... 999999999:
> +		return d + 9;
> +	default:
> +		return d + 10;

clang generates something really horrid for that.

Either:
    if (v <= 9) return d + 1;
    if (v <= 99) return d + 2;
    if (v <= 999) return d + 3;
    if (v <= 9999) return d + 4;
    if (v <= 99999) return d + 5;
    if (v <= 999999) return d + 6;
    if (v <= 9999999) return d + 7;
    if (v <= 99999999) return d + 8;
    if (v <= 999999999) return d + 9;
    return d + 10;
or:
    if ((++d && v > 9) &&
        (++d && v > 99) &&
        (++d && v > 999) &&
        (++d && v > 9999) &&
        (++d && v > 99999) &&
        (++d && v > 999999) &&
        (++d && v > 9999999) &&
        (++d && v > 99999999) &&
        (++d && v > 999999999))
        d++;
    return d;
generate better code.
In particular it is almost certainly best to only have one taken branch.
Dumping in a load of unlikely() might help that as well.
(Neither compiler does the ++d inline, the add is done before the return.)

	David

>  	}
> -	return d;
>  }