linux-kernel - Re: [patch V3] lib: GCD: add binary GCD algorithm

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: <CAMuHMdUBWqdyS4w7EKsnvQLXJVgQh624AQsjgQvxT9FRW4s_6g@mail.gmail.com>
Date:	Thu, 28 Apr 2016 20:11:32 +0200
From:	Geert Uytterhoeven <geert@...ux-m68k.org>
To:	Rich Felker <dalias@...c.org>
Cc:	George Spelvin <linux@...izon.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Peter Zijlstra <peterz@...radead.org>, zengzhaoxiu@....com,
	"David S. Miller" <davem@...emloft.net>,
	Helge Deller <deller@....de>,
	Ivan Kokshaysky <ink@...assic.park.msu.ru>,
	James Hogan <james.hogan@...tec.com>,
	"James E.J. Bottomley" <jejb@...isc-linux.org>,
	Jonas Bonn <jonas@...thpole.se>,
	Lennox Wu <lennox.wu@...il.com>,
	Ley Foon Tan <lftan@...era.com>,
	alpha <linux-alpha@...r.kernel.org>,
	"linux-arm-kernel@...ts.infradead.org" 
	<linux-arm-kernel@...ts.infradead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	linux-m68k <linux-m68k@...ts.linux-m68k.org>,
	"open list:METAG ARCHITECTURE" <linux-metag@...r.kernel.org>,
	Linux MIPS Mailing List <linux-mips@...ux-mips.org>,
	Parisc List <linux-parisc@...r.kernel.org>,
	Linux-sh list <linux-sh@...r.kernel.org>,
	Russell King <linux@....linux.org.uk>,
	linux <linux@...ts.openrisc.net>,
	Chen Liqin <liqin.linux@...il.com>,
	Matt Turner <mattst88@...il.com>,
	Michal Simek <monstr@...str.eu>,
	nios2-dev@...ts.rocketboards.org,
	Ralf Baechle <ralf@...ux-mips.org>,
	Richard Henderson <rth@...ddle.net>,
	sparclinux <sparclinux@...r.kernel.org>,
	uclinux-h8-devel@...ts.sourceforge.jp,
	Yoshinori Sato <ysato@...rs.sourceforge.jp>,
	zhaoxiu.zeng@...il.com
Subject: Re: [patch V3] lib: GCD: add binary GCD algorithm

On Thu, Apr 28, 2016 at 7:58 PM, Rich Felker <dalias@...c.org> wrote:
> On Thu, Apr 28, 2016 at 07:51:06PM +0200, Geert Uytterhoeven wrote:
>> On Thu, Apr 28, 2016 at 6:48 PM, George Spelvin <linux@...izon.com> wrote:
>> > Another few comments:
>> >
>> > 1. Would ARCH_HAS_FAST_FFS involve fewer changes than CPU_NO_EFFICIENT_FFS?
>>
>> No, as you want to _disable_ ARCH_HAS_FAST_FFS / _enable_
>> CPU_NO_EFFICIENT_FFS as soon as you're enabling support for a
>> CPU that doesn't support it.
>>
>> Logical OR is easier in both the Kconfig and C preprocessor languages
>> than logical NAND.
>>
>> E.g. in Kconfig, a CPU core not supporting it can just select
>> CPU_NO_EFFICIENT_FFS.
>
> How does a CPU lack an efficient ffs/ctz anyway? There are all sorts
> of ways to implement it without a native insn, some of which are
> almost or just as fast as the native insn on cpus that have the
> latter. On anything with a fast multiply, the de Bruijn sequence
> approach is near-optimal, and otherwise one of the binary-search type
> approaches (possibly branchless) can be used. If the compiler doesn't
> generate an appropriate one for __builtin_ctz, that's arguably a
> compiler bug.

m68k-linux-gcc 4.6.3 generates:

        jsr __ctzsi2

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@...ux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds