[PATCH v2] lib: gcd: prevent possible div by 0

[PATCH v2] lib: gcd: prevent possible div by 0

[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

Cc: stable@vger.kernel.org
Signed-off-by: Davidlohr Bueso <dave@gnu.org>
---
V2: simplified checking with b = 0 (Eric)

 lib/gcd.c |    3 +++
 1 file changed, 3 insertions(+)

diff --git a/lib/gcd.c b/lib/gcd.c
index cce4f3c..3657f12 100644
--- a/lib/gcd.c
+++ b/lib/gcd.c
@@ -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;
-- 
1.7.9.5

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Davidlohr Bueso]

ping? Cc'ing Greg for stable.

On Mon, 2012-09-10 at 16:35 +0200, Davidlohr Bueso wrote:
> Account for all properties when a and/or b are 0:
> gcd(0, 0) = 0
> gcd(a, 0) = a
> gcd(0, b) = b
> 
> Cc: stable@vger.kernel.org
> Signed-off-by: Davidlohr Bueso <dave@gnu.org>
> ---
> V2: simplified checking with b = 0 (Eric)
> 
>  lib/gcd.c |    3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/lib/gcd.c b/lib/gcd.c
> index cce4f3c..3657f12 100644
> --- a/lib/gcd.c
> +++ b/lib/gcd.c
> @@ -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;

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Andrew Morton]

On Mon, 10 Sep 2012 16:35:19 +0200
Davidlohr Bueso <dave@gnu.org> wrote:

> Account for all properties when a and/or b are 0:
> gcd(0, 0) = 0
> gcd(a, 0) = a
> gcd(0, b) = b
> 
> Cc: stable@vger.kernel.org

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.

> ...
> --- a/lib/gcd.c
> +++ b/lib/gcd.c
> @@ -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;
> -- 
> 1.7.9.5
> 
> 

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Davidlohr Bueso]

On Wed, 2012-09-12 at 12:10 -0700, Andrew Morton wrote:
> On Mon, 10 Sep 2012 16:35:19 +0200
> Davidlohr Bueso <dave@gnu.org> wrote:
> 
> > Account for all properties when a and/or b are 0:
> > gcd(0, 0) = 0
> > gcd(a, 0) = a
> > gcd(0, b) = b
> > 
> > Cc: stable@vger.kernel.org
> 
> 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.

> 
> > ...
> > --- a/lib/gcd.c
> > +++ b/lib/gcd.c
> > @@ -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;
> > -- 
> > 1.7.9.5
> > 
> > 
> 

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Andrew Morton]

On Wed, 12 Sep 2012 21:20:30 +0200
Davidlohr Bueso <dave@gnu.org> wrote:

> On Wed, 2012-09-12 at 12:10 -0700, Andrew Morton wrote:
> > On Mon, 10 Sep 2012 16:35:19 +0200
> > Davidlohr Bueso <dave@gnu.org> wrote:
> > 
> > > Account for all properties when a and/or b are 0:
> > > gcd(0, 0) = 0
> > > gcd(a, 0) = a
> > > gcd(0, b) = b
> > > 
> > > Cc: stable@vger.kernel.org
> > 
> > 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....

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Greg Kroah-Hartman]

On Wed, Sep 12, 2012 at 09:05:06PM +0200, Davidlohr Bueso wrote:
> ping? Cc'ing Greg for stable.

Why?  That's not how a patch gets added to the stable tree, right?

greg k-h

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Davidlohr Bueso]

On Wed, 2012-09-12 at 12:36 -0700, Andrew Morton wrote:
> On Wed, 12 Sep 2012 21:20:30 +0200
> Davidlohr Bueso <dave@gnu.org> wrote:
> 
> > On Wed, 2012-09-12 at 12:10 -0700, Andrew Morton wrote:
> > > On Mon, 10 Sep 2012 16:35:19 +0200
> > > Davidlohr Bueso <dave@gnu.org> wrote:
> > > 
> > > > Account for all properties when a and/or b are 0:
> > > > gcd(0, 0) = 0
> > > > gcd(a, 0) = a
> > > > gcd(0, b) = b
> > > > 
> > > > Cc: stable@vger.kernel.org
> > > 
> > > 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.

Yes, my thoughts exactly.
> 
> 
> 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

Re: [PATCH v2] lib: gcd: prevent possible div by 0

[Nick Bowler]

On 2012-09-12 12:36 -0700, Andrew Morton wrote:
> On Wed, 12 Sep 2012 21:20:30 +0200
> Davidlohr Bueso <dave@gnu.org> wrote:
> > On Wed, 2012-09-12 at 12:10 -0700, Andrew Morton wrote:
> > > On Mon, 10 Sep 2012 16:35:19 +0200
> > > Davidlohr Bueso <dave@gnu.org> wrote:
> > > 
> > > > Account for all properties when a and/or b are 0:
> > > > gcd(0, 0) = 0
> > > > gcd(a, 0) = a
> > > > gcd(0, b) = b
[...]
> 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,
-- 
Nick Bowler, Elliptic Technologies (http://www.elliptictech.com/)