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

[Davidlohr Bueso <dave@gnu.org>]

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