From aba18d5b6785d501996b475d58a05cc26707d370 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Mon, 8 Jan 2024 13:28:59 -0800 Subject: [PATCH] math/big: fix uint64 overflow in nat.mulRange Compute median as a + (b-a)/2 instead of (a + b)/2. Add additional test cases. Fixes #65025. Change-Id: Ib716a1036c17f8f33f51e33cedab13512eb7e0be Reviewed-on: https://go-review.googlesource.com/c/go/+/554617 Reviewed-by: Robert Griesemer Auto-Submit: Robert Griesemer TryBot-Result: Gopher Robot Run-TryBot: Robert Griesemer Reviewed-by: Rob Pike Reviewed-by: Dmitri Shuralyov --- src/math/big/int_test.go | 10 ++++++++++ src/math/big/nat.go | 2 +- src/math/big/nat_test.go | 5 +++++ 3 files changed, 16 insertions(+), 1 deletion(-) diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go index cb964a43cd..088bce09f9 100644 --- a/src/math/big/int_test.go +++ b/src/math/big/int_test.go @@ -200,12 +200,22 @@ var mulRangesZ = []struct { "638952175999932299156089414639761565182862536979208272237582" + "511852109168640000000000000000000000", // -99! }, + + // overflow situations + {math.MaxInt64 - 0, math.MaxInt64, "9223372036854775807"}, + {math.MaxInt64 - 1, math.MaxInt64, "85070591730234615838173535747377725442"}, + {math.MaxInt64 - 2, math.MaxInt64, "784637716923335094969050127519550606919189611815754530810"}, + {math.MaxInt64 - 3, math.MaxInt64, "7237005577332262206126809393809643289012107973151163787181513908099760521240"}, } func TestMulRangeZ(t *testing.T) { var tmp Int // test entirely positive ranges for i, r := range mulRangesN { + // skip mulRangesN entries that overflow int64 + if int64(r.a) < 0 || int64(r.b) < 0 { + continue + } prod := tmp.MulRange(int64(r.a), int64(r.b)).String() if prod != r.prod { t.Errorf("#%da: got %s; want %s", i, prod, r.prod) diff --git a/src/math/big/nat.go b/src/math/big/nat.go index b9f4026a04..ecb7d363d4 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -624,7 +624,7 @@ func (z nat) mulRange(a, b uint64) nat { case a+1 == b: return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b)) } - m := (a + b) / 2 + m := a + (b-a)/2 // avoid overflow return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b)) } diff --git a/src/math/big/nat_test.go b/src/math/big/nat_test.go index b84a7be5bc..4722548fa9 100644 --- a/src/math/big/nat_test.go +++ b/src/math/big/nat_test.go @@ -6,6 +6,7 @@ package big import ( "fmt" + "math" "runtime" "strings" "testing" @@ -155,6 +156,10 @@ var mulRangesN = []struct { "638952175999932299156089414639761565182862536979208272237582" + "51185210916864000000000000000000000000", // 100! }, + {math.MaxUint64 - 0, math.MaxUint64, "18446744073709551615"}, + {math.MaxUint64 - 1, math.MaxUint64, "340282366920938463408034375210639556610"}, + {math.MaxUint64 - 2, math.MaxUint64, "6277101735386680761794095221682035635525021984684230311930"}, + {math.MaxUint64 - 3, math.MaxUint64, "115792089237316195360799967654821100226821973275796746098729803619699194331160"}, } func TestMulRangeN(t *testing.T) { -- 2.48.1