math/bits: make Add and Sub fallbacks constant time

Make the extended precision add-with-carry and sub-with-carry operations
take a constant amount of time to execute, regardless of input.

name             old time/op  new time/op  delta
Add-4            1.16ns ±11%  1.51ns ± 5%  +30.52%  (p=0.008 n=5+5)
Add32-4          1.08ns ± 0%  1.03ns ± 1%   -4.86%  (p=0.029 n=4+4)
Add64-4          1.09ns ± 1%  1.95ns ± 3%  +79.23%  (p=0.008 n=5+5)
Add64multiple-4  4.03ns ± 1%  4.55ns ±11%  +13.07%  (p=0.008 n=5+5)
Sub-4            1.08ns ± 1%  1.50ns ± 0%  +38.17%  (p=0.016 n=5+4)
Sub32-4          1.09ns ± 2%  1.53ns ±10%  +40.26%  (p=0.008 n=5+5)
Sub64-4          1.10ns ± 1%  1.47ns ± 1%  +33.39%  (p=0.008 n=5+5)
Sub64multiple-4  4.30ns ± 2%  4.08ns ± 4%   -5.07%  (p=0.032 n=5+5)

Fixes #31267

Change-Id: I1824b1b3ab8f09902ce8b5fef84ce2fdb8847ed9
Reviewed-on: https://go-review.googlesource.com/c/go/+/170758
Reviewed-by: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 19 insertions, 30 deletions

diff --git a/src/math/bits/bits.go b/src/math/bits/bits.go
index 24d910c27e..1a85485a5a 100644
--- a/src/math/bits/bits.go
+++ b/src/math/bits/bits.go
@@ -332,23 +332,21 @@ func Len64(x uint64) (n int) {
 // The carry input must be 0 or 1; otherwise the behavior is undefined.
 // The carryOut output is guaranteed to be 0 or 1.
 func Add(x, y, carry uint) (sum, carryOut uint) {
-	yc := y + carry
-	sum = x + yc
-	if sum < x || yc < y {
-		carryOut = 1
+	if UintSize == 32 {
+		s32, c32 := Add32(uint32(x), uint32(y), uint32(carry))
+		return uint(s32), uint(c32)
 	}
-	return
+	s64, c64 := Add64(uint64(x), uint64(y), uint64(carry))
+	return uint(s64), uint(c64)
 }
 
 // Add32 returns the sum with carry of x, y and carry: sum = x + y + carry.
 // The carry input must be 0 or 1; otherwise the behavior is undefined.
 // The carryOut output is guaranteed to be 0 or 1.
 func Add32(x, y, carry uint32) (sum, carryOut uint32) {
-	yc := y + carry
-	sum = x + yc
-	if sum < x || yc < y {
-		carryOut = 1
-	}
+	sum64 := uint64(x) + uint64(y) + uint64(carry)
+	sum = uint32(sum64)
+	carryOut = uint32(sum64 >> 32)
 	return
 }
 
@@ -356,11 +354,8 @@ func Add32(x, y, carry uint32) (sum, carryOut uint32) {
 // The carry input must be 0 or 1; otherwise the behavior is undefined.
 // The carryOut output is guaranteed to be 0 or 1.
 func Add64(x, y, carry uint64) (sum, carryOut uint64) {
-	yc := y + carry
-	sum = x + yc
-	if sum < x || yc < y {
-		carryOut = 1
-	}
+	sum = x + y + carry
+	carryOut = ((x & y) | ((x | y) &^ sum)) >> 63
 	return
 }
 
@@ -370,23 +365,20 @@ func Add64(x, y, carry uint64) (sum, carryOut uint64) {
 // The borrow input must be 0 or 1; otherwise the behavior is undefined.
 // The borrowOut output is guaranteed to be 0 or 1.
 func Sub(x, y, borrow uint) (diff, borrowOut uint) {
-	yb := y + borrow
-	diff = x - yb
-	if diff > x || yb < y {
-		borrowOut = 1
+	if UintSize == 32 {
+		d32, b32 := Sub32(uint32(x), uint32(y), uint32(borrow))
+		return uint(d32), uint(b32)
 	}
-	return
+	d64, b64 := Sub64(uint64(x), uint64(y), uint64(borrow))
+	return uint(d64), uint(b64)
 }
 
 // Sub32 returns the difference of x, y and borrow, diff = x - y - borrow.
 // The borrow input must be 0 or 1; otherwise the behavior is undefined.
 // The borrowOut output is guaranteed to be 0 or 1.
 func Sub32(x, y, borrow uint32) (diff, borrowOut uint32) {
-	yb := y + borrow
-	diff = x - yb
-	if diff > x || yb < y {
-		borrowOut = 1
-	}
+	diff = x - y - borrow
+	borrowOut = ((^x & y) | (^(x ^ y) & diff)) >> 31
 	return
 }
 
@@ -394,11 +386,8 @@ func Sub32(x, y, borrow uint32) (diff, borrowOut uint32) {
 // The borrow input must be 0 or 1; otherwise the behavior is undefined.
 // The borrowOut output is guaranteed to be 0 or 1.
 func Sub64(x, y, borrow uint64) (diff, borrowOut uint64) {
-	yb := y + borrow
-	diff = x - yb
-	if diff > x || yb < y {
-		borrowOut = 1
-	}
+	diff = x - y - borrow
+	borrowOut = ((^x & y) | (^(x ^ y) & diff)) >> 63
 	return
 }