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: <20120326125129.78975baf.akpm@linux-foundation.org>
Date:	Mon, 26 Mar 2012 12:51:29 -0700
From:	Andrew Morton <akpm@...ux-foundation.org>
To:	Denys Vlasenko <vda.linux@...glemail.com>
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, 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?

--
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/