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

[James Cloos <cloos@jhcloos.com>]

>>>>> "Florian" == Florian Fainelli <florian@openwrt.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@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6