diff options
| author | Rémy Oudompheng <remyoudompheng@gmail.com> | 2019-11-13 06:53:22 +0100 |
|---|---|---|
| committer | Robert Griesemer <gri@golang.org> | 2019-11-13 19:15:27 +0000 |
| commit | 7ad27481f84dbf325ee348831ed0f95dbf04094e (patch) | |
| tree | f9410e54e46fcbf89c82f30c09917afd76fb8bcb /src/math/big | |
| parent | e762378c42b786233ea13affa1cc2ee132ceefaf (diff) | |
| download | go-7ad27481f84dbf325ee348831ed0f95dbf04094e.tar.xz | |
math/big: fix out-of-bounds panic in divRecursive
The bounds in the last carry branch were wrong as there
is no reason for len(u) >= n+n/2 to always hold true.
We also adjust test to avoid using a remainder of 1
(in which case, the last step of the algorithm computes
(qhatv+1) - qhatv which rarely produces a carry).
Change-Id: I69fbab9c5e19d0db1c087fbfcd5b89352c2d26fb
Reviewed-on: https://go-review.googlesource.com/c/go/+/206839
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/math/big')
| -rw-r--r-- | src/math/big/nat.go | 2 | ||||
| -rw-r--r-- | src/math/big/nat_test.go | 13 |
2 files changed, 11 insertions, 4 deletions
diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 6667319100..9d7da1ee16 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -941,7 +941,7 @@ func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat) { } c := subVV(u[0:len(qhatv)], u[0:len(qhatv)], qhatv) if c > 0 { - c = subVW(u[len(qhatv):B+n], u[len(qhatv):B+n], c) + c = subVW(u[len(qhatv):], u[len(qhatv):], c) } if c > 0 { panic("impossible") diff --git a/src/math/big/nat_test.go b/src/math/big/nat_test.go index cbbaf02771..32f29e3876 100644 --- a/src/math/big/nat_test.go +++ b/src/math/big/nat_test.go @@ -765,16 +765,23 @@ func TestNatDiv(t *testing.T) { if len(b) == 1 && b[0] == 1 { b[0] = 2 } + // choose a remainder c < b + c := rndNat1(len(b)) + if len(c) == len(b) && c[len(c)-1] >= b[len(b)-1] { + c[len(c)-1] = 0 + c = c.norm() + } + // compute x = a*b+c x := nat(nil).mul(a, b) - addVW(x, x, 1) + x = x.add(x, c) var q, r nat q, r = q.div(r, x, b) if q.cmp(a) != 0 { t.Fatalf("wrong quotient: got %s; want %s for %s/%s", q.utoa(10), a.utoa(10), x.utoa(10), b.utoa(10)) } - if len(r) != 1 || r[0] != 1 { - t.Fatalf("wrong remainder: got %s; want 1 for %s/%s", r.utoa(10), x.utoa(10), b.utoa(10)) + if r.cmp(c) != 0 { + t.Fatalf("wrong remainder: got %s; want %s for %s/%s", r.utoa(10), c.utoa(10), x.utoa(10), b.utoa(10)) } } } |