linux-kernel - Re: [PATCH 1/1] 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: <20140815135855.GG19379@twins.programming.kicks-ass.net>
Date:	Fri, 15 Aug 2014 15:58:55 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	Ingo Molnar <mingo@...nel.org>,
	George Spelvin <linux@...izon.com>,
	David Howells <dhowells@...hat.com>,
	AKASHI Takahiro <takahiro.akashi@...aro.org>,
	Josh Boyer <jwboyer@...hat.com>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/1] GCD: add binary GCD algorithm

On Fri, Aug 15, 2014 at 08:49:16PM +0800, Zhaoxiu Zeng wrote:
> Because some architectures (alpha, armv6, etc.) don't provide hardware division,
> the mod operation is slow! Binary GCD algorithm uses simple arithmetic operations,
> it replaces division with arithmetic shifts, comparisons, and subtraction.
> 
> Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
> ---
>  lib/Kconfig | 15 +++++++++++++++
>  lib/gcd.c   | 31 ++++++++++++++++++++++++++++++-
>  2 files changed, 45 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/Kconfig b/lib/Kconfig
> index a5ce0c7..80e8e54 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -177,6 +177,21 @@ config CRC8
>  	  when they need to do cyclic redundancy check according CRC8
>  	  algorithm. Module will be called crc8.
>  
> +#
> +# GCD
> +#
> +choice
> +	prompt "GCD implementation"
> +	default GCD_ALGO_EUCLIDEAN
> +
> +config GCD_ALGO_EUCLIDEAN
> +	bool "Euclidean algorithm"
> +
> +config GCD_ALGO_BINARY
> +	bool "Binary GCD algorithm (Stein's algorithm)"
> +
> +endchoice

Does this result in the user being asked which GCD algo he wants? If so,
I think that's bad.


> +#else
> +	r = a | b;
> +
> +	if (!a || !b)
> +		return r;
> +
> +	r = r ^ (r - 1);
> +	if (!(a & r))
> +		goto even_odd; /* a/c even, b/c odd */
> +	if (!(b & r))
> +		goto odd_even; /* a/c odd, b/c even */
> +
> +	/* a/c and b/c both odd */
> +	while (a != b) {
> +		if (a > b) {
> +			a -= b;
> +even_odd:
> +			do
> +				a >>= 1;
> +			while (!(a & r));
> +		} else {
> +			b -= a;
> +odd_even:
> +			do
> +				b >>= 1;
> +			while (!(b & r));
> +		}
> +	}
> +#endif
>  	return b;
>  }

So I looked at wikipedia (I wasn't aware of this algorithm, clever
though), and am still somewhat puzzled by your 'r'.

What's 'wrong' with their iterative version, or what's better about your
'r' stuff?

Content of type "application/pgp-signature" skipped