Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752366AbcD1SLh (ORCPT ); Thu, 28 Apr 2016 14:11:37 -0400 Received: from mail-io0-f196.google.com ([209.85.223.196]:36589 "EHLO mail-io0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751539AbcD1SLf (ORCPT ); Thu, 28 Apr 2016 14:11:35 -0400 MIME-Version: 1.0 In-Reply-To: <20160428175843.GZ21636@brightrain.aerifal.cx> References: <1461843824-19853-1-git-send-email-zengzhaoxiu@163.com> <20160428164856.10120.qmail@ns.horizon.com> <20160428175843.GZ21636@brightrain.aerifal.cx> Date: Thu, 28 Apr 2016 20:11:32 +0200 X-Google-Sender-Auth: aTRi6KVGPiXYVDG8MkNjxNydI9U Message-ID: Subject: Re: [patch V3] lib: GCD: add binary GCD algorithm From: Geert Uytterhoeven To: Rich Felker Cc: George Spelvin , Andrew Morton , Peter Zijlstra , zengzhaoxiu@163.com, "David S. Miller" , Helge Deller , Ivan Kokshaysky , James Hogan , "James E.J. Bottomley" , Jonas Bonn , Lennox Wu , Ley Foon Tan , alpha , "linux-arm-kernel@lists.infradead.org" , "linux-kernel@vger.kernel.org" , linux-m68k , "open list:METAG ARCHITECTURE" , Linux MIPS Mailing List , Parisc List , Linux-sh list , Russell King , linux , Chen Liqin , Matt Turner , Michal Simek , nios2-dev@lists.rocketboards.org, Ralf Baechle , Richard Henderson , sparclinux , uclinux-h8-devel@lists.sourceforge.jp, Yoshinori Sato , zhaoxiu.zeng@gmail.com Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1581 Lines: 40 On Thu, Apr 28, 2016 at 7:58 PM, Rich Felker 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 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@linux-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