diff options
author | Rémy Oudompheng <remyoudompheng@gmail.com> | 2020-03-05 07:59:00 +0100 |
---|---|---|
committer | Andrew Bonventre <andybons@golang.org> | 2020-04-27 16:42:55 +0000 |
commit | cd65852feeef2e6e8d8c06bbf037bc4d6372e93d (patch) | |
tree | 9ad9109121a78d7fecf291882fce96d6cd603c70 | |
parent | 768e5d1e4d079e1c941c154ae0397369567a5190 (diff) | |
download | go-cd65852feeef2e6e8d8c06bbf037bc4d6372e93d.tar.gz go-cd65852feeef2e6e8d8c06bbf037bc4d6372e93d.zip |
[release-branch.go1.14] 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 #37501
Change-Id: I15089da4a4027beda43af497bf6de261eb792f94
Reviewed-on: https://go-review.googlesource.com/c/go/+/221980
Reviewed-by: Robert Griesemer <gri@golang.org>
(cherry picked from commit ac1fd419b6d2af8b0e69b13fa5c794705095db0a)
Reviewed-on: https://go-review.googlesource.com/c/go/+/227877
Run-TryBot: Emmanuel Odeke <emm.odeke@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
-rw-r--r-- | src/math/big/nat.go | 15 | ||||
-rw-r--r-- | src/math/big/nat_test.go | 18 |
2 files changed, 31 insertions, 2 deletions
diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 1b771ca7c6..c31ec5156b 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -740,7 +740,8 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) { // The remainder overwrites input u. // // Precondition: -// - len(q) >= len(u)-len(v) +// - q is large enough to hold the quotient u / v +// which has a maximum length of len(u)-len(v)+1. func (q nat) divBasic(u, v nat) { n := len(v) m := len(u) - n @@ -779,6 +780,8 @@ func (q nat) divBasic(u, v nat) { } // D4. + // Compute the remainder u - (q̂*v) << (_W*j). + // The subtraction may overflow if q̂ estimate was off by one. qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0) qhl := len(qhatv) if j+qhl > len(u) && qhatv[n] == 0 { @@ -787,7 +790,11 @@ func (q nat) divBasic(u, v nat) { c := subVV(u[j:j+qhl], u[j:], qhatv) if c != 0 { c := addVV(u[j:j+n], u[j:], v) - u[j+n] += c + // If n == qhl, the carry from subVV and the carry from addVV + // cancel out and don't affect u[j+n]. + if n < qhl { + u[j+n] += c + } qhat-- } @@ -827,6 +834,10 @@ func (z nat) divRecursive(u, v nat) { putNat(tmp) } +// divRecursiveStep computes the division of u by v. +// - z must be large enough to hold the quotient +// - the quotient will overwrite z +// - the remainder will overwrite u func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat) { u = u.norm() v = v.norm() diff --git a/src/math/big/nat_test.go b/src/math/big/nat_test.go index 32f29e3876..89e913fc16 100644 --- a/src/math/big/nat_test.go +++ b/src/math/big/nat_test.go @@ -786,3 +786,21 @@ func TestNatDiv(t *testing.T) { } } } + +// TestIssue37499 triggers the edge case of divBasic where +// the inaccurate estimate of the first word's quotient +// happens at the very beginning of the loop. +func TestIssue37499(t *testing.T) { + // Choose u and v such that v is slightly larger than u >> N. + // This tricks divBasic into choosing 1 as the first word + // of the quotient. This works in both 32-bit and 64-bit settings. + u := natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706b39f8489c1d28e57bb5ba4ef9fd9387a3e344402c0a453381") + v := natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706c") + + q := nat(nil).make(8) + q.divBasic(u, v) + q = q.norm() + if s := string(q.utoa(16)); s != "fffffffffffffffffffffffffffffffffffffffffffffffb" { + t.Fatalf("incorrect quotient: %s", s) + } +} |