libgo: update to Go 1.14.4 release

Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/241999

2 files changed, 31 insertions, 2 deletions

diff --git a/libgo/go/math/big/nat.go b/libgo/go/math/big/nat.go
index 1b771ca..c31ec51 100644
--- a/libgo/go/math/big/nat.go
+++ b/libgo/go/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/libgo/go/math/big/nat_test.go b/libgo/go/math/big/nat_test.go
index 32f29e3..89e913f 100644
--- a/libgo/go/math/big/nat_test.go
+++ b/libgo/go/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)
+	}
+}