linux-kernel - Re: [PATCH 1/1] vsprintf: optimize decimal conversion (again)

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: <CAK1hOcNZ1QdsT2Gajv1y-yAfF85hOTH=18vqqH4itURLtgYfdQ@mail.gmail.com>
Date:	Mon, 26 Mar 2012 21:56:38 +0200
From:	Denys Vlasenko <vda.linux@...glemail.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	linux-kernel@...r.kernel.org, Douglas W Jones <jones@...uiowa.edu>,
	Michal Nazarewicz <mnazarewicz@...gle.com>
Subject: Re: [PATCH 1/1] vsprintf: optimize decimal conversion (again)

On Mon, Mar 26, 2012 at 9:51 PM, Andrew Morton
<akpm@...ux-foundation.org> wrote:
> On Mon, 26 Mar 2012 20:51:24 +0200
> Denys Vlasenko <vda.linux@...glemail.com> wrote:
>
>> commit 01a2904d31d2373886f489429ec662c9be64a6ab
>> Author: Denys Vlasenko <vda.linux@...glemail.com>
>> Date:   Mon Mar 26 20:40:53 2012 +0200
>>
>>     vsprintf: optimize decimal conversion (again)
>>
>>     Previous code was using optimizations which were developed
>>     to work well even on narrow-word CPUs (by today's standards).
>>     But Linux runs only on 32-bit and wider CPUs. We can use that.
>>
>>     First: using 32x32->64 multiply and trivial 32-bit shift,
>>     we can correctly divide by 10 much larger numbers, and thus
>>     we can print groups of 9 digits instead of groups of 5 digits.
>>
>>     Next: there are two algorithms to print larger numbers.
>>     One is generic: divide by 1000000000 and repeatedly print
>>     groups of (up to) 9 digits. It's conceptually simple,
>>     but requires an (unsigned long long) / 1000000000 division.
>>
>>     Second algorithm splits 64-bit unsigned long long into 16-bit chunks,
>>     manipulates them cleverly and generates groups of 4 decimal digits.
>>     It so happens that it does NOT require long long division.
>>
>>     If long is > 32 bits, division of 64-bit values is relatively easy,
>>     and we will use the first algorithm.
>>     If long long is > 64 bits (strange architecture with VERY large long long),
>>     second algorithm can't be used, and we again use the first one.
>>
>>     Else (if long is 32 bits and long long is 64 bits) we use second one.
>>
>>     And third: there is a simple optimization which takes fast path
>>     not only for zero as was done before, but for all one-digit numbers.
>>
>>     In all tested cases new code is faster than old one, in many cases by 30%,
>>     in few cases by more than 50% (for example, on x86-32, conversion of 12345678).
>>     Code growth is ~0 in 32-bit case and ~130 bytes in 64-bit case.
>>
>
> This patch is so nutty that I like it.
>
>> +#if BITS_PER_LONG != 32 || (~(0ULL)>>1) != ((1ULL<<63)-1)
>
> What's this for?

The second check should be just BITS_PER_LONG_LONG != 64,
but we don't have BITS_PER_LONG_LONG.

-- 
vda
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/