]> Cypherpunks repositories - gostls13.git/commit
math/big: correct off-by-one access in divBasic
authorRémy Oudompheng <remyoudompheng@gmail.com>
Thu, 5 Mar 2020 06:59:00 +0000 (07:59 +0100)
committerRobert Griesemer <gri@golang.org>
Wed, 8 Apr 2020 20:53:58 +0000 (20:53 +0000)
commitac1fd419b6d2af8b0e69b13fa5c794705095db0a
tree59070e2d53e5fd1e2d6b9d2638c1afbb21c8c267
parenta59465b545cd66e0796b5c7649a87a6f1b657cb4
math/big: correct off-by-one access in divBasic

The divBasic function computes the quotient of big nats u/v word by word.
It estimates each word qhat by performing a long division (top 2 words of u
divided by top word of v), looks at the next word to correct the estimate,
then perform a full multiplication (qhat*v) to catch any inaccuracy in the
estimate.

In the latter case, "negative" values appear temporarily and carries
must be carefully managed, and the recursive division refactoring
introduced a case where qhat*v has the same length as v, triggering an
out-of-bounds write in the case it happens when computing the top word
of the quotient.

Fixes #37499

Change-Id: I15089da4a4027beda43af497bf6de261eb792f94
Reviewed-on: https://go-review.googlesource.com/c/go/+/221980
Reviewed-by: Robert Griesemer <gri@golang.org>
src/math/big/nat.go
src/math/big/nat_test.go