[PATCH 1/9] kernel: export sound/core/pcm_timer.c gcd implementation

[PATCH 1/9] kernel: export sound/core/pcm_timer.c gcd implementation

[Florian Fainelli]

This patch exports the gcd implementation from
sound/core/pcm_timer.c into include/linux/kernel.h.
AR7 uses it in its clock routines.

Signed-off-by: Florian Fainelli <florian@openwrt.org>
---
diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 883cd44..878a27a 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -147,6 +147,22 @@ extern int _cond_resched(void);
 		(__x < 0) ? -__x : __x;		\
 	})
 
+/* Greatest common divisor */
+static inline 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;
+}
+
 #ifdef CONFIG_PROVE_LOCKING
 void might_fault(void);
 #else
diff --git a/sound/core/pcm_timer.c b/sound/core/pcm_timer.c
index ca8068b..e9dbf62 100644
--- a/sound/core/pcm_timer.c
+++ b/sound/core/pcm_timer.c
@@ -20,6 +20,7 @@
  */
 
 #include <linux/time.h>
+#include <linux/kernel.h>
 #include <sound/core.h>
 #include <sound/pcm.h>
 #include <sound/timer.h>
@@ -28,22 +29,6 @@
  *  Timer functions
  */
 
-/* Greatest common divisor */
-static 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;
-}
-
 void snd_pcm_timer_resolution_change(struct snd_pcm_substream *substream)
 {
 	unsigned long rate, mult, fsize, l, post;

Re: [PATCH 1/9] kernel: export sound/core/pcm_timer.c gcd implementation

[Andrew Morton]

On Mon, 1 Jun 2009 13:57:09 +0200 Florian Fainelli <florian@openwrt.org> wrote:

> This patch exports the gcd implementation from
> sound/core/pcm_timer.c into include/linux/kernel.h.
> AR7 uses it in its clock routines.
> 
> ...
>
> diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> index 883cd44..878a27a 100644
> --- a/include/linux/kernel.h
> +++ b/include/linux/kernel.h
> @@ -147,6 +147,22 @@ extern int _cond_resched(void);
>  		(__x < 0) ? -__x : __x;		\
>  	})
>  
> +/* Greatest common divisor */
> +static inline 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;
> +}

a) the name's a bit sucky.   Is there some convention for this name?

b) It looks too large to be inlined.  lib/gdc.c?

b) there's an implementation of gcd() in
   net/netfilter/ipvs/ip_vs_wrr.c.  I expect that this patch broke the
   build.

Re: [PATCH 1/9] kernel: export sound/core/pcm_timer.c gcd implementation

[Geert Uytterhoeven]

On Tue, Jun 2, 2009 at 06:50, Andrew Morton <akpm@linux-foundation.org> wrote:
> On Mon, 1 Jun 2009 13:57:09 +0200 Florian Fainelli <florian@openwrt.org> wrote:
>
>> This patch exports the gcd implementation from
>> sound/core/pcm_timer.c into include/linux/kernel.h.
>> AR7 uses it in its clock routines.
>>
>> ...
>>
>> diff --git a/include/linux/kernel.h b/include/linux/kernel.h
>> index 883cd44..878a27a 100644
>> --- a/include/linux/kernel.h
>> +++ b/include/linux/kernel.h
>> @@ -147,6 +147,22 @@ extern int _cond_resched(void);
>>               (__x < 0) ? -__x : __x;         \
>>       })
>>
>> +/* Greatest common divisor */
>> +static inline 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;
>> +}
>
> a) the name's a bit sucky.   Is there some convention for this name?

Well, `gcd' is a quite common acronym, probably almost as well known as `min'
and `max'...

Gr{oetje,eeting}s,

						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
							    -- Linus Torvalds

Re: [PATCH 1/9] kernel: export sound/core/pcm_timer.c gcd implementation

[Florian Fainelli]

[-- Attachment #1: Type: text/plain, Size: 1795 bytes --]

Le Tuesday 02 June 2009 06:50:34 Andrew Morton, vous avez écrit :
> On Mon, 1 Jun 2009 13:57:09 +0200 Florian Fainelli <florian@openwrt.org> 
wrote:
> > This patch exports the gcd implementation from
> > sound/core/pcm_timer.c into include/linux/kernel.h.
> > AR7 uses it in its clock routines.
> >
> > ...
> >
> > diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> > index 883cd44..878a27a 100644
> > --- a/include/linux/kernel.h
> > +++ b/include/linux/kernel.h
> > @@ -147,6 +147,22 @@ extern int _cond_resched(void);
> >  		(__x < 0) ? -__x : __x;		\
> >  	})
> >
> > +/* Greatest common divisor */
> > +static inline 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;
> > +}
>
> a) the name's a bit sucky.   Is there some convention for this name?

We might want something better like greatest_common_divisor which is a bit 
more self-explanatory ?

>
> b) It looks too large to be inlined.  lib/gdc.c?

And its users select it in order not to increase the size of kernel.h, sounds 
good.

>
> b) there's an implementation of gcd() in
>    net/netfilter/ipvs/ip_vs_wrr.c.  I expect that this patch broke the
>    build.

I did forget about this. That gcd implementation only treats the a > b case.

What do you prefer, each user keeps its gcd implementation locally or we make 
a lib/gcd.c for it ?

Thanks
-- 
Best regards, Florian Fainelli
Email : florian@openwrt.org
http://openwrt.org
-------------------------------

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 1/9] kernel: export sound/core/pcm_timer.c gcd implementation

[Andrew Morton]

On Tue, 2 Jun 2009 09:19:22 +0200 Florian Fainelli <florian@openwrt.org> wrote:

> Le Tuesday 02 June 2009 06:50:34 Andrew Morton, vous avez __crit__:
> > On Mon, 1 Jun 2009 13:57:09 +0200 Florian Fainelli <florian@openwrt.org> 
> wrote:
> > > This patch exports the gcd implementation from
> > > sound/core/pcm_timer.c into include/linux/kernel.h.
> > > AR7 uses it in its clock routines.
> > >
> > > ...
> > >
> > > diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> > > index 883cd44..878a27a 100644
> > > --- a/include/linux/kernel.h
> > > +++ b/include/linux/kernel.h
> > > @@ -147,6 +147,22 @@ extern int _cond_resched(void);
> > >  		(__x < 0) ? -__x : __x;		\
> > >  	})
> > >
> > > +/* Greatest common divisor */
> > > +static inline 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;
> > > +}
> >
> > a) the name's a bit sucky.   Is there some convention for this name?
> 
> We might want something better like greatest_common_divisor which is a bit 
> more self-explanatory ?

Well, if gcd() is a commonly used name then let's use that.  I don't
personally recall seeing it used but that doesn't mean much.

> >
> > b) It looks too large to be inlined.  lib/gdc.c?
> 
> And its users select it in order not to increase the size of kernel.h, sounds 
> good.
> 
> >
> > b) there's an implementation of gcd() in
> >    net/netfilter/ipvs/ip_vs_wrr.c.  I expect that this patch broke the
> >    build.
> 
> I did forget about this. That gcd implementation only treats the a > b case.
> 
> What do you prefer, each user keeps its gcd implementation locally or we make 
> a lib/gcd.c for it ?

I think lib/gcd.c would be better.  Then migrate current code over to
use that.

The problem with offering a generic version is types: will it work
correctly and sensibly for all combinations of signed/unsigned
char/short/int/long/longlong?  All but the last, I expect.  In which
case that'll be good enough for now.