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] [day] [month] [year] [list]

Date:	22 Aug 2014 18:36:56 -0400
From:	"George Spelvin" <linux@...izon.com>
To:	akpm@...ux-foundation.org, zhaoxiu.zeng@...il.com
Cc:	dhowells@...hat.com, jwboyer@...hat.com,
	linux-kernel@...r.kernel.org, linux@...izon.com, mingo@...nel.org,
	peterz@...radead.org, takahiro.akashi@...aro.org
Subject: Re: [PATCH 1/1] GCD: add binary GCD algorithm

> Otherwise I don't think we can justify the additional maintenance
> cost/risk, sorry.

This is am extremely self-contained and easy to test piece of code.
Look at the history; the total edits to the function since the
beginning of git in 2005 are:
- A theoretical bug fix to handle zero arguments better
- A global header file cleanup that hit lib/gcd.c
- Relocation to lib/ from sound/core/pcm_timer.c

And... nothing else.

This is the sort of leaf function that, once it works, gets left alone
forever.

Your point about "it's not a bottleneck, so why optimize it?" is valid,
but the maintenance issue is something of a red herring.

The maintenance hassle I *do* worry about the Kconfig magic to decide
whether to enable it.  But that's something I'd defer to the ARM
maintainers on.

> And if we *do* decide to proceed with this patch, we should include a
> patch which enables it on as many architectures as possible, so it gets
> runtime tested.

It's pretty harmless even on machines which *do* have fast division,
so we could just enable it everywhere.

GMP, whose benchmarking I'm inclined to trust, uses binary GCD for all
small (3-word or less) values.

https://gmplib.org/manual/Binary-GCD.html

The expected nymber of iterations to perform the Euclidean algorithm
for two random numbers 1 <= x,y <= n is 1.216 log2(n) + 0.06.
Binary GCD is quite similar.  Its main advantage is the large gain
in the first step when the inputs are of very different size.

Binary GCD's perfoemance problems come from unpredictable branches.
Euclid's algorithm has less of those.
--
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/