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: <EFA01581-40EF-4E01-852F-E8D31D85653F@zytor.com>
Date: Wed, 21 Jan 2026 07:46:54 -0800
From: "H. Peter Anvin" <hpa@...or.com>
To: David Laight <david.laight.linux@...il.com>,
        David Desobry <david.desobry@...malgen.com>
CC: tglx@...nel.org, mingo@...hat.com, bp@...en8.de,
        dave.hansen@...ux.intel.com, x86@...nel.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH v4] x86/lib: Optimize num_digits() and fix INT_MIN overflow

On January 21, 2026 3:36:43 AM PST, David Laight <david.laight.linux@...il.com> wrote:
>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;
>>  }
>

No, please, it was a joke.