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

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

[Florian Fainelli]

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

Signed-off-by: Florian Fainelli <florian@openwrt.org>
---
diff --git a/include/linux/gcd.h b/include/linux/gcd.h
new file mode 100644
index 0000000..69f5e8a
--- /dev/null
+++ b/include/linux/gcd.h
@@ -0,0 +1,8 @@
+#ifndef _GCD_H
+#define _GCD_H
+
+#include <linux/compiler.h>
+
+unsigned long gcd(unsigned long a, unsigned long b) __attribute_const__;
+
+#endif /* _GCD_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 8ade0a7..70a9906 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -10,6 +10,9 @@ menu "Library routines"
 config BITREVERSE
 	tristate
 
+config GCD
+	bool
+
 config GENERIC_FIND_FIRST_BIT
 	bool
 
diff --git a/lib/Makefile b/lib/Makefile
index 33a40e4..389bdd2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -57,6 +57,7 @@ obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
+obj-$(CONFIG_GCD)	+= gcd.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff --git a/lib/gcd.c b/lib/gcd.c
new file mode 100644
index 0000000..fbf81a8
--- /dev/null
+++ b/lib/gcd.c
@@ -0,0 +1,20 @@
+#include <linux/gcd.h>
+#include <linux/module.h>
+
+/* Greatest common divisor */
+unsigned long gcd(unsigned long a, unsigned long b)
+{
+	unsigned long r;
+
+	if (a < b) {
+		r = a;
+		a = b;
+	b = r;
+	}
+	while ((r = a % b) != 0) {
+		a = b;
+		b = r;
+	}
+	return b;
+}
+EXPORT_SYMBOL(gcd);

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

[Sergei Shtylyov]

Hello.

Florian Fainelli wrote:

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

> Signed-off-by: Florian Fainelli <florian@openwrt.org>

[...]

> diff --git a/lib/gcd.c b/lib/gcd.c
> new file mode 100644
> index 0000000..fbf81a8
> --- /dev/null
> +++ b/lib/gcd.c
> @@ -0,0 +1,20 @@
> +#include <linux/gcd.h>
> +#include <linux/module.h>
> +
> +/* Greatest common divisor */
> +unsigned long gcd(unsigned long a, unsigned long b)
> +{
> +	unsigned long r;
> +
> +	if (a < b) {
> +		r = a;
> +		a = b;
> +	b = r;

    Fix indetnation please.

> +	}
> +	while ((r = a % b) != 0) {
> +		a = b;
> +		b = r;
> +	}
> +	return b;
> +}
> +EXPORT_SYMBOL(gcd);

WBR, Sergei

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

[Sergei Shtylyov]

Hello.

Florian Fainelli wrote:

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

> Signed-off-by: Florian Fainelli <florian@openwrt.org>

[...]

> diff --git a/lib/gcd.c b/lib/gcd.c
> new file mode 100644
> index 0000000..fbf81a8
> --- /dev/null
> +++ b/lib/gcd.c
> @@ -0,0 +1,20 @@
> +#include <linux/gcd.h>
> +#include <linux/module.h>
> +
> +/* Greatest common divisor */
> +unsigned long gcd(unsigned long a, unsigned long b)
> +{
> +	unsigned long r;
> +
> +	if (a < b) {
> +		r = a;
> +		a = b;
> +	b = r;

    Fix indentation please.

> +	}
> +	while ((r = a % b) != 0) {
> +		a = b;
> +		b = r;
> +	}
> +	return b;
> +}
> +EXPORT_SYMBOL(gcd);

WBR, Sergei

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

[Florian Fainelli]

Hi Sergei,

Le Thursday 04 June 2009 16:31:09 Sergei Shtylyov, vous avez écrit :
> Hello.
>
> Florian Fainelli wrote:
> > This patch adds lib/gcd.c which contains a greatest
> > common divider implementation taken from
> > sound/core/pcm_timer.c
> >
> > Signed-off-by: Florian Fainelli <florian@openwrt.org>
>
> [...]
>
> > diff --git a/lib/gcd.c b/lib/gcd.c
> > new file mode 100644
> > index 0000000..fbf81a8
> > --- /dev/null
> > +++ b/lib/gcd.c
> > @@ -0,0 +1,20 @@
> > +#include <linux/gcd.h>
> > +#include <linux/module.h>
> > +
> > +/* Greatest common divisor */
> > +unsigned long gcd(unsigned long a, unsigned long b)
> > +{
> > +	unsigned long r;
> > +
> > +	if (a < b) {
> > +		r = a;
> > +		a = b;
> > +	b = r;
>
>     Fix indentation please.

Fixed in the following version. Also putting David in copy since it
he was not in copy of the first patch and could not know why there
is a following patch on net/netfilter/ipvs/ip_vs_wrr.c to use lib/gcd.c
--
From: Florian Fainelli <florian@openwrt.org>

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

Changes from v1:
- fixed indentation
- use EXPORT_SYMBOL_GPL instead of EXPORT_SYMBOL as
suggested by Ralf Baechle

Signed-off-by: Florian Fainelli <florian@openwrt.org>
--
diff --git a/include/linux/gcd.h b/include/linux/gcd.h
new file mode 100644
index 0000000..69f5e8a
--- /dev/null
+++ b/include/linux/gcd.h
@@ -0,0 +1,8 @@
+#ifndef _GCD_H
+#define _GCD_H
+
+#include <linux/compiler.h>
+
+unsigned long gcd(unsigned long a, unsigned long b) __attribute_const__;
+
+#endif /* _GCD_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 8ade0a7..70a9906 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -10,6 +10,9 @@ menu "Library routines"
 config BITREVERSE
 	tristate
 
+config GCD
+	bool
+
 config GENERIC_FIND_FIRST_BIT
 	bool
 
diff --git a/lib/Makefile b/lib/Makefile
index 33a40e4..389bdd2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -57,6 +57,7 @@ obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
+obj-$(CONFIG_GCD)	+= gcd.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff --git a/lib/gcd.c b/lib/gcd.c
new file mode 100644
index 0000000..6634741
--- /dev/null
+++ b/lib/gcd.c
@@ -0,0 +1,20 @@
+#include <linux/gcd.h>
+#include <linux/module.h>
+
+/* Greatest common divisor */
+unsigned long gcd(unsigned long a, unsigned long b)
+{
+	unsigned long r;
+
+	if (a < b) {
+		r = a;
+		a = b;
+		b = r;
+	}
+	while ((r = a % b) != 0) {
+		a = b;
+		b = r;
+	}
+	return b;
+}
+EXPORT_SYMBOL_GPL(gcd);

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

[Joe Perches]

On Thu, 2009-06-04 at 16:39 +0200, Florian Fainelli wrote:
> diff --git a/lib/gcd.c b/lib/gcd.c
> new file mode 100644
> index 0000000..6634741
> --- /dev/null
> +++ b/lib/gcd.c
> @@ -0,0 +1,20 @@
> +#include <linux/gcd.h>
> +#include <linux/module.h>
> +
> +/* Greatest common divisor */
> +unsigned long gcd(unsigned long a, unsigned long b)
> +{
> +	unsigned long r;
> +
> +	if (a < b) {
> +		r = a;
> +		a = b;
> +		b = r;
	swap(a, b)
> +	}
> +	while ((r = a % b) != 0) {
> +		a = b;
> +		b = r;
> +	}
> +	return b;
> +}
> +EXPORT_SYMBOL_GPL(gcd);

Shouldn't a generic gcd protect against a div0
if gcd(0,0)?

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

[Andrew Morton]

On Thu, 04 Jun 2009 08:57:24 -0700 Joe Perches <joe@perches.com> wrote:

> On Thu, 2009-06-04 at 16:39 +0200, Florian Fainelli wrote:
> > diff --git a/lib/gcd.c b/lib/gcd.c
> > new file mode 100644
> > index 0000000..6634741
> > --- /dev/null
> > +++ b/lib/gcd.c
> > @@ -0,0 +1,20 @@
> > +#include <linux/gcd.h>
> > +#include <linux/module.h>
> > +
> > +/* Greatest common divisor */
> > +unsigned long gcd(unsigned long a, unsigned long b)
> > +{
> > +	unsigned long r;
> > +
> > +	if (a < b) {
> > +		r = a;
> > +		a = b;
> > +		b = r;
> 	swap(a, b)

yup

> > +	}
> > +	while ((r = a % b) != 0) {
> > +		a = b;
> > +		b = r;
> > +	}
> > +	return b;
> > +}
> > +EXPORT_SYMBOL_GPL(gcd);
> 
> Shouldn't a generic gcd protect against a div0
> if gcd(0,0)?

nope.  It's a caller bug, there's nothing the callee can do to fix it,
so an oops is a fine response.

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

[Andrew Morton]

On Thu, 4 Jun 2009 16:39:03 +0200
Florian Fainelli <florian@openwrt.org> wrote:

> This patch adds lib/gcd.c which contains a greatest
> common divider implementation taken from
> sound/core/pcm_timer.c
> 
> Changes from v1:
> - fixed indentation
> - use EXPORT_SYMBOL_GPL instead of EXPORT_SYMBOL as
> suggested by Ralf Baechle

I'm not sure about the _GPL change really - it's just a little helper
function.  But whatever - I'm trained to avoid that issue.

I made some changes:

From: Andrew Morton <akpm@linux-foundation.org>

- use swap() (pointed out by Joe)

- Just add gcd.o to lib-y, reove Kconfig changes.

Cc: David S. Miller <davem@davemloft.net>
Cc: Florian Fainelli <florian@openwrt.org>
Cc: Julius Volz <juliusv@google.com>
Cc: Sergei Shtylyov <sshtylyov@ru.mvista.com>
Cc: Simon Horman <horms@verge.net.au>
Cc: Takashi Iwai <tiwai@suse.de>
Cc: Joe Perches <joe@perches.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/Kconfig  |    3 ---
 lib/Makefile |    3 +--
 lib/gcd.c    |    8 +++-----
 3 files changed, 4 insertions(+), 10 deletions(-)

diff -puN lib/Kconfig~lib-add-lib-gcdc-fix lib/Kconfig
--- a/lib/Kconfig~lib-add-lib-gcdc-fix
+++ a/lib/Kconfig
@@ -10,9 +10,6 @@ menu "Library routines"
 config BITREVERSE
 	tristate
 
-config GCD
-	bool
-
 config GENERIC_FIND_FIRST_BIT
 	bool
 
diff -puN lib/Makefile~lib-add-lib-gcdc-fix lib/Makefile
--- a/lib/Makefile~lib-add-lib-gcdc-fix
+++ a/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o gcd.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
@@ -57,7 +57,6 @@ obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
 obj-$(CONFIG_CRC7)	+= crc7.o
 obj-$(CONFIG_LIBCRC32C)	+= libcrc32c.o
-obj-$(CONFIG_GCD)	+= gcd.o
 obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff -puN lib/gcd.c~lib-add-lib-gcdc-fix lib/gcd.c
--- a/lib/gcd.c~lib-add-lib-gcdc-fix
+++ a/lib/gcd.c
@@ -1,3 +1,4 @@
+#include <linux/kernel.h>
 #include <linux/gcd.h>
 #include <linux/module.h>
 
@@ -6,11 +7,8 @@ unsigned long gcd(unsigned long a, unsig
 {
 	unsigned long r;
 
-	if (a < b) {
-		r = a;
-		a = b;
-		b = r;
-	}
+	if (a < b)
+		swap(a, b);
 	while ((r = a % b) != 0) {
 		a = b;
 		b = r;
_

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

[James Cloos]

>>>>> "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

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

[Alan Cox]

> Would the binary gcd algorithm not be a better fit for the kernel?
> 
> It avoids division, using only shifts and subtraction:

Time them both and see. I suspect on a lot of processors the divide based
one now wins. We also have fls() and ffs() which may mean some platforms
can implement the first two loops even better.

Could well be the shift based one is better for some processors only.

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

[James Cloos]

>>>>> "Alan" == Alan Cox <alan@lxorguk.ukuu.org.uk> writes:

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

Alan> Could well be the shift based one is better for some processors only.

Very likely, I suspect.

And the version of the euclid algo in that patch is better than most
references that I've seen.  (q=a/b;r=a%b; is common, probably because
the texts use the same algo for computing the continued fraction.)

In any case, I do not have the hardware to do any statistically
significant testing; the closest I could do would be a speed test
on hera, which I expect would be discouraged.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

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

[James Cloos]

>>>>> "|" == James Cloos <cloos@jhcloos.com> writes:
>>>>> "Alan" == Alan Cox <alan@lxorguk.ukuu.org.uk> writes:

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

Alan> Could well be the shift based one is better for some processors only.

|> Very likely, I suspect.

|> In any case, I do not have the hardware to do any statistically
|> significant testing;

I take that back.  Just in case speed is a relevant issue, I ran a test
on my MX, which is a small xen domU running on a:
,----
| EFamily: 0 EModel: 0 Family: 6 Model: 15 Stepping: 11
| CPU Model: Core 2 Quad 
| Processor name string: Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
`----
I got, compiling with gcc-4.4 -march=native -O3:

binary
408.39user 0.05system 6:52.75elapsed 98%CPU

quick (the code in the kernel)
600.96user 0.16system 10:19.06elapsed 97%CPU

contfrac (the typical euclid algo)
569.19user 0.12system 9:35.50elapsed 98%CPU

extended euclid (calculates g=ia+jb=gcd(a,b))
684.53user 0.13system 11:32.77elapsed 98%CPU

I also tried on an old Alpha at freeshell; it had gcc-3.3; gcc's -S
output looks like it uses hardware div there, just like it does on
x86 and amd64.  The bgcd, though, was 10-16 times faster than either
version of euclid's algo.

On my laptop's P3M, binary gcd was about twice as fast as euclid.

So, although modern processors are *much* better at int div, the
binary gcd algo is still faster.

The timings on the alpha and the laptop were of:

    for (a=0xFFF; a > 0; a--)
        for (b=a; b > 0; b--)
            g=gcd(a,b);

For the core2 times quoted above, I started with a=0xFFFF.

And I forgot to mention:  the bgcd code I posted was based on
some old notes of mine which most likely trace to TAoCP.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6