add lib/gcd.c
Subsystems (4)
PATCH 1/8 add lib/gcd.c
This patch adds lib/gcd.c which contains a greatest common divider implementation taken from sound/core/pcm_timer.c
---
include/linux/gcd.h new file +8 -0
@@ -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 */
lib/Kconfig +3 -0
@@ -10,6 +10,9 @@ menu "Library routines" config BITREVERSE tristate +config GCD + bool + config GENERIC_FIND_FIRST_BIT bool
lib/Makefile +1 -0
@@ -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/
lib/gcd.c new file +20 -0
@@ -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);
Hello.
Quoted 5 lines · Florian Fainelli
This patch adds
lib/gcd.cwhich contains a greatest common divider implementation taken fromsound/core/pcm_timer.cSigned-off-by Florian Fainelli <[email protected]>
[...]
Quoted 8 lines
lib/gcd.c new file +2
-0@@ -0,0 +1,20 @@ +#include <linux/gcd.h> +#include <linux/module.h>
lib/gcd.c line 12
Quoted 10 lines
lib/gcd.c new file +10
-0+ +/* 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.
lib/gcd.c line 20
Quoted 8 lines
lib/gcd.c new file +8
-0+ } +while ((r = a % b) !=0 ) { + a = b; + b = r; + } +return b; +} +EXPORT_SYMBOL (gcd);
WBR, Sergei
Hello.
Quoted 5 lines · Florian Fainelli
This patch adds
lib/gcd.cwhich contains a greatest common divider implementation taken fromsound/core/pcm_timer.cSigned-off-by Florian Fainelli <[email protected]>
[...]
Quoted 8 lines
lib/gcd.c new file +2
-0@@ -0,0 +1,20 @@ +#include <linux/gcd.h> +#include <linux/module.h>
lib/gcd.c line 12
Quoted 10 lines
lib/gcd.c new file +10
-0+ +/* 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.
lib/gcd.c line 20
Quoted 8 lines
lib/gcd.c new file +8
-0+ } +while ((r = a % b) !=0 ) { + a = b; + b = r; + } +return b; +} +EXPORT_SYMBOL (gcd);
WBR, Sergei
Hi Sergei,
Le Thursday 04 June 2009 16:31:09 Sergei Shtylyov, vous avez écrit :
Quoted 23 lines
Hello.
Quoted 5 lines · Florian Fainelli
This patch adds
lib/gcd.cwhich contains a greatest common divider implementation taken fromsound/core/pcm_timer.cSigned-off-by Florian Fainelli <[email protected]>[...]
Quoted 12 lines
lib/gcd.c new file +6
-0@@ -0,0 +1,20 @@ +#include <linux/gcd.h> +#include <linux/module.h> + +/* Greatest common divisor */ +unsigned long gcd (unsigned long a,unsigned long b) +{
Quoted 8 lines
lib/gcd.c line 12
Quoted 6 lines
lib/gcd.c new file +6
-0+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 <[email protected]>
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
--
include/linux/gcd.h new file +8 -0
@@ -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 */
lib/Kconfig +3 -0
@@ -10,6 +10,9 @@ menu "Library routines" config BITREVERSE tristate +config GCD + bool + config GENERIC_FIND_FIRST_BIT bool
lib/Makefile +1 -0
@@ -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/
lib/gcd.c new file +20 -0
@@ -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);
Quoted 8 lines · Florian Fainelli
lib/gcd.c new file +2
-0@@ -0,0 +1,20 @@ +#include <linux/gcd.h> +#include <linux/module.h>
lib/gcd.c line 12
Quoted 10 lines
lib/gcd.c new file +10
-0+ +/* 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)
lib/gcd.c line 20
Quoted 8 lines
lib/gcd.c new file +8
-0+ } +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)?
Andrew Morton
maintainerQuoted 12 lines · On Thu, 04 Jun 2009 08:57:24 -0700 Joe Perches <[email protected]> wrote:
Quoted 11 lines · Florian Fainelli
lib/gcd.c new file +5
-0@@ -0,0 +1,20 @@ +#include <linux/gcd.h> +#include <linux/module.h> + +/* Greatest common divisor */ +unsigned long gcd (unsigned long a,unsigned long b)
Quoted 8 lines
lib/gcd.c line 12
Quoted 7 lines
lib/gcd.c new file +7
-0+{ +unsigned long r; + +if (a < b) { + r = a; + a = b; + b = r;swap(a, b)
yup
Quoted 11 lines
lib/gcd.c line 20
Quoted 8 lines
lib/gcd.c new file +8
-0+ } +while ((r = a % b) !=0 ) { + a = b; + b = r; + } +return b; +} +EXPORT_SYMBOL_GPL (gcd);Shouldn't a generic gcd protect against a div0
ifgcd(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.
Andrew Morton
maintainerQuoted 8 lines · On Thu, 4 Jun 2009 16:39:03 +0200 Florian Fainelli <[email protected]> wrote:
This patch adds
lib/gcd.cwhich contains a greatest common divider implementation taken fromsound/core/pcm_timer.cChanges from v1:
- fixed indentation
- useEXPORT_SYMBOL_GPLinstead ofEXPORT_SYMBOLas 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 <[email protected]>
- use swap() (pointed out by Joe)
- Just add gcd.o to lib-y, reove Kconfig changes.
---
lib/Kconfig | 3 --- lib/Makefile | 3 +-- lib/gcd.c | 8 +++----- 3 files changed, 4 insertions(+), 10 deletions(-)
lib/Kconfig renamed from lib/Kconfig~lib-add-lib-gcdc-fix +0 -3
@@ -10,9 +10,6 @@ menu "Library routines" config BITREVERSE tristate -config GCD - bool - config GENERIC_FIND_FIRST_BIT bool
lib/Makefile renamed from lib/Makefile~lib-add-lib-gcdc-fix +1 -2
@@ -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/
lib/gcd.c renamed from lib/gcd.c~lib-add-lib-gcdc-fix +3 -5
@@ -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;
_
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"Florian" == Florian Fainelli <[email protected]> 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
Signature · 1 line
James Cloos <[email protected]> OpenPGP: 1024D/ED7DAEA6
Quoted 3 lines
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.
Quoted 3 lines
Quoted 3 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
"Alan" == Alan Cox <[email protected]> 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
Signature · 1 line
James Cloos <[email protected]> OpenPGP: 1024D/ED7DAEA6
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
"|" == James Cloos <[email protected]> writes:
"Alan" == Alan Cox <[email protected]> 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
Signature · 1 line
James Cloos <[email protected]> OpenPGP: 1024D/ED7DAEA6