Skip to contentSkip to conversation

lib: gcd: prevent possible div by 0

PATCH In review Davidlohr Bueso 4 participants 8 messages Sep 10, 2012 – Sep 12, 2012 Library code

lore
Share & tools
lore
#0 lore raw

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) = 0
gcd(a, 0) = a
gcd(0, b) = b

---
V2: simplified checking with b = 0 (Eric)

 lib/gcd.c |    3 +++
 1 file changed, 3 insertions(+)
lib/gcd.c +3 -0
index cce4f3c..3657f12 100644
@@ -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
#1 lore raw

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) = 0
gcd(a, 0) = a
gcd(0, b) = b

---
V2: simplified checking with b = 0 (Eric)

 lib/gcd.c |    3 +++
 1 file changed, 3 insertions(+)
lib/gcd.c +3 -0
index cce4f3c..3657f12 100644
@@ -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;
#2 lore raw
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

maintainer
#3 lore raw
In reply to Davidlohr Bueso
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) = 0
gcd(a, 0) = a
gcd(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
#4 lore raw
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) = 0
gcd(a, 0) = a
gcd(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
maintainer
#5 lore raw
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) = 0
gcd(a, 0) = a
gcd(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....

#6 lore raw
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) = 0
gcd(a, 0) = a
gcd(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.

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

#7 lore raw
In reply to Andrew Morton
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) = 0
gcd(a, 0) = a
gcd(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/)