From 5ca44dc403d4a609eeafb0f699a63f19ef045cd6 Mon Sep 17 00:00:00 2001 From: smasher164 Date: Thu, 4 Apr 2019 15:57:24 -0400 Subject: [PATCH] math/bits: make Add and Sub fallbacks constant time MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 Reviewed-by: Keith Randall Run-TryBot: Filippo Valsorda TryBot-Result: Gobot Gobot --- src/math/bits/bits.go | 49 +++++++++++++++++-------------------------- 1 file 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 } -- 2.50.0