lib: gcd: prevent possible div by 0
PATCH v2 1/1 lib: gcd: prevent possible div by 0
Account for all properties when a and/or b are 0:gcd(0, 0) = 0gcd(a, 0) = agcd(0, b) = b
---
V2: simplified checking with b = 0 (Eric)
lib/gcd.c | 3 +++ 1 file changed, 3 insertions(+)
lib/gcd.c +3 -0
@@ -9,6 +9,9 @@ unsigned long gcd(unsigned long a, unsigned long b)if (a < b)swap (a, b); + +if (!b) +return a;while ((r = a % b) !=0 ) { a = b; b = r;
Signature · 1 line
1.7.9.5
ping? Cc'ing Greg for stable.
Quoted 27 lines · Davidlohr Bueso
Account for all properties when a and/or b are 0:
gcd(0, 0)= 0gcd(a, 0)= agcd(0, b)= bSigned-off-by Davidlohr Bueso <[email protected]>---
V2: simplified checking with b = 0 (Eric)lib/gcd.c | 3 +++ 1 file changed, 3 insertions(+)lib/gcd.c +3
-0@@ -9,6 +9,9 @@ unsigned long gcd(unsigned long a, unsigned long b)if (a < b)swap (a, b); + +if (!b) +return a;while ((r = a % b) !=0 ) { a = b; b = r;
Quoted 1 line · Davidlohr Bueso
ping? Cc'ing Greg for stable.
Why? That's not how a patch gets added to the stable tree, right?
greg k-h
Andrew Morton
maintainerQuoted 6 lines · On Mon, 10 Sep 2012 16:35:19 +0200 Davidlohr Bueso <[email protected]> wrote:
Account for all properties when a and/or b are 0:
gcd(0, 0)= 0gcd(a, 0)= agcd(0, b)= b
Why cc:stable? If this patch fixes some known problem in the current kernel then that really really should have been described in the changelog. Always. Please.
Quoted 17 lines
...
lib/gcd.c +3
-0@@ -9,6 +9,9 @@ unsigned long gcd(unsigned long a, unsigned long b)if (a < b)swap (a, b); + +if (!b) +return a;while ((r = a % b) !=0 ) { a = b; b = r;Signature · 1 line
1.7.9.5
Quoted 8 lines · Andrew Morton
Quoted 5 lines · On Mon, 10 Sep 2012 16:35:19 +0200 Davidlohr Bueso <[email protected]> wrote:
Account for all properties when a and/or b are 0:
gcd(0, 0)= 0gcd(a, 0)= agcd(0, b)= b
Quoted 5 lines
Quoted 1 line
Why cc:stable? If this patch fixes some known problem in the current kernel then that really really should have been described in the changelog. Always. Please.
Ok, I will keep it in mind next time. No known problem (at least that I know of), but due to the nature of the potential bug, I thought that it was worth adding it to stable.
Thanks.
Quoted 19 lines
Quoted 18 lines
...
lib/gcd.c +3
-0@@ -9,6 +9,9 @@ unsigned long gcd(unsigned long a, unsigned long b)if (a < b)swap (a, b); + +if (!b) +return a;while ((r = a % b) !=0 ) { a = b; b = r;Signature · 1 line
1.7.9.5
Andrew Morton
maintainerQuoted 11 lines · On Wed, 12 Sep 2012 21:20:30 +0200 Davidlohr Bueso <[email protected]> wrote:
Quoted 10 lines · Andrew Morton
Quoted 6 lines · On Mon, 10 Sep 2012 16:35:19 +0200 Davidlohr Bueso <[email protected]> wrote:
Account for all properties when a and/or b are 0:
gcd(0, 0)= 0gcd(a, 0)= agcd(0, b)= b
Quoted 7 lines
Quoted 3 lines
Why cc:stable? If this patch fixes some known problem in the current kernel then that really really should have been described in the changelog. Always. Please.
Ok, I will keep it in mind next time. No known problem (at least that I know of), but due to the nature of the potential bug, I thought that it was worth adding it to stable.
OK.
I'm not personally averse to fixing such problems in -stable, particualrly in lib/ code. After all, people who take -stable kernels will then change them and add drivers and backport changes from later kernels, etc. They might be bitten by such a bug.
I'm scratching my head a bit at the patch though. What does gcd(0, 13) mean? That 0 can be divided by 13 zero times, which is an integer result? I wonder why any non-buggy code would do that....
Quoted 22 lines · Andrew Morton
Quoted 11 lines · On Wed, 12 Sep 2012 21:20:30 +0200 Davidlohr Bueso <[email protected]> wrote:
Quoted 10 lines · Andrew Morton
Quoted 6 lines · On Mon, 10 Sep 2012 16:35:19 +0200 Davidlohr Bueso <[email protected]> wrote:
Account for all properties when a and/or b are 0:
gcd(0, 0)= 0gcd(a, 0)= agcd(0, b)= bQuoted 7 lines
Quoted 3 lines
Why cc:stable? If this patch fixes some known problem in the current kernel then that really really should have been described in the changelog. Always. Please.
Ok, I will keep it in mind next time. No known problem (at least that I know of), but due to the nature of the potential bug, I thought that it was worth adding it to stable.
Quoted 6 lines
OK.
I'm not personally averse to fixing such problems in -stable, particualrly in
lib/code. After all, people who take -stable kernels will then change them and add drivers and backport changes from later kernels, etc. They might be bitten by such a bug.
Yes, my thoughts exactly.
Quoted 6 lines
I'm scratching my head a bit at the patch though. What does
gcd(0, 13)mean? That 0 can be divided by 13 zero times, which is an integer result? I wonder why any non-buggy code would do that....
While I've been away from this kind of math for a while, based on the Euclid's algorithm, if r = a mod b, then gcd(a, b) = gcd(b, r), so:
gcd(0, 13) = gcd(13, 0 mod 13) = gcd(13, 0)
Since the GCD of a and b is "the largest integer that divides both a and b with no remainder", when r = 0, the algorithm will stop and therefore gcd(13, 0) = 13.
http://mitpress.mit.edu/sicp/full-text/sicp/book/node19.html
Quoted 10 lines · Andrew Morton
Quoted 8 lines · On Wed, 12 Sep 2012 21:20:30 +0200 Davidlohr Bueso <[email protected]> wrote:
Quoted 7 lines · Andrew Morton
Quoted 4 lines · On Mon, 10 Sep 2012 16:35:19 +0200 Davidlohr Bueso <[email protected]> wrote:
Account for all properties when a and/or b are 0:
gcd(0, 0)= 0gcd(a, 0)= agcd(0, b)= b
[...]
Quoted 3 lines
I'm scratching my head a bit at the patch though. What does
gcd(0, 13)mean? That 0 can be divided by 13 zero times, which is an integer result? I wonder why any non-buggy code would do that....
The number-theoretical definition of gcd(a, b) on the integers, leaving aside the case where a and b are both 0, are defined as the greatest integer which divides both a and b.
An integer x divides y if there exists an integer M such that x*M equals y.
Observe that all integers divide zero (since we can set M to 0, and x*0 = 0 for any x). So it's easy to see that the result of gcd(x, 0) and gcd(0, x) must be |x|.
The case of gcd(0, 0) is tricky. Clearly, as all integers divide zero, none of these can be the greatest one. So this is normally treated as a special case, defined to be 0 by convention, as this makes the use of gcd "nicer" in other areas of mathematics.
Cheers,
Signature · 1 line
Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/)