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: <20160428175843.GZ21636@brightrain.aerifal.cx>
Date:	Thu, 28 Apr 2016 13:58:44 -0400
From:	Rich Felker <dalias@...c.org>
To:	Geert Uytterhoeven <geert@...ux-m68k.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 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.

Rich