From 7ad27481f84dbf325ee348831ed0f95dbf04094e Mon Sep 17 00:00:00 2001 From: =?utf8?q?R=C3=A9my=20Oudompheng?= Date: Wed, 13 Nov 2019 06:53:22 +0100 Subject: [PATCH] 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 TryBot-Result: Gobot Gobot Reviewed-by: Robert Griesemer --- src/math/big/nat.go | 2 +- 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)) } } } -- 2.50.0