linux-kernel - Re: [PATCH 1/8] add lib/gcd.c

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: <m38wjwz5ur.fsf@lugabout.jhcloos.org>
Date:	Sat, 13 Jun 2009 08:16:04 -0400
From:	James Cloos <cloos@...loos.com>
To:	linux-kernel@...r.kernel.org
Cc:	"Linux-MIPS" <linux-mips@...ux-mips.org>,
	Florian Fainelli <florian@...nwrt.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Takashi Iwai <tiwai@...e.de>,
	Ralf Baechle <ralf@...ux-mips.org>
Subject: Re: [PATCH 1/8] add lib/gcd.c

>>>>> "Florian" == Florian Fainelli <florian@...nwrt.org> writes:

Florian> This patch adds lib/gcd.c which contains a greatest
Florian> common divider implementation taken from
Florian> sound/core/pcm_timer.c

Would the binary gcd algorithm not be a better fit for the kernel?

It avoids division, using only shifts and subtraction:

unsigned long gcd (unsigned long a, unsigned long b) {
	unsigned int shift;
	unsigned long d;
    
	if (a == 0 || b == 0)
		return a | b;
    
	for (shift = 0; ((a | b) & 1) == 0; ++shift) {
		a >>= 1;
		b >>= 1;
	}
    
	while ((a & 1) == 0)
		a >>= 1;
    
	do {
		while ((b & 1) == 0)
			b >>= 1;
	
		if (a < b) {
			b -= a;
		} else {
			d = a - b;
			a = b; b = d;
		}
		b >>= 1;
	} while (b != 0);
    
	return a << shift;
}

-JimC
-- 
James Cloos <cloos@...loos.com>         OpenPGP: 1024D/ED7DAEA6
--
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/