From 5f7826270c9e87509fd7731ec64953a5e4761de0 Mon Sep 17 00:00:00 2001
From: Felix Lange <fjl@users.noreply.github.com>
Date: Tue, 28 Feb 2017 15:09:11 +0100
Subject: all: unify big.Int zero checks, use common/math in more places
 (#3716)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* common/math: optimize PaddedBigBytes, use it more

name              old time/op    new time/op    delta
PaddedBigBytes-8    71.1ns ± 5%    46.1ns ± 1%  -35.15%  (p=0.000 n=20+19)

name              old alloc/op   new alloc/op   delta
PaddedBigBytes-8     48.0B ± 0%     32.0B ± 0%  -33.33%  (p=0.000 n=20+20)

* all: unify big.Int zero checks

Various checks were in use. This commit replaces them all with Int.Sign,
which is cheaper and less code.

eg templates:

    func before(x *big.Int) bool { return x.BitLen() == 0 }
    func after(x *big.Int) bool  { return x.Sign() == 0 }

    func before(x *big.Int) bool { return x.BitLen() > 0 }
    func after(x *big.Int) bool  { return x.Sign() != 0 }

    func before(x *big.Int) int { return x.Cmp(common.Big0) }
    func after(x *big.Int) int  { return x.Sign() }

* common/math, crypto/secp256k1: make ReadBits public in package math
---
 common/math/big.go | 33 +++++++++++++++++++++++++--------
 1 file changed, 25 insertions(+), 8 deletions(-)

(limited to 'common/math/big.go')

diff --git a/common/math/big.go b/common/math/big.go
index c0508c102..704ca40a9 100644
--- a/common/math/big.go
+++ b/common/math/big.go
@@ -28,6 +28,13 @@ var (
 	MaxBig256 = new(big.Int).Set(tt256m1)
 )
 
+const (
+	// number of bits in a big.Word
+	wordBits = 32 << (uint64(^big.Word(0)) >> 63)
+	// number of bytes in a big.Word
+	wordBytes = wordBits / 8
+)
+
 // ParseBig256 parses s as a 256 bit integer in decimal or hexadecimal syntax.
 // Leading zeros are accepted. The empty string parses as zero.
 func ParseBig256(s string) (*big.Int, bool) {
@@ -91,12 +98,25 @@ func FirstBitSet(v *big.Int) int {
 // PaddedBigBytes encodes a big integer as a big-endian byte slice. The length
 // of the slice is at least n bytes.
 func PaddedBigBytes(bigint *big.Int, n int) []byte {
-	bytes := bigint.Bytes()
-	if len(bytes) >= n {
-		return bytes
+	if bigint.BitLen()/8 >= n {
+		return bigint.Bytes()
 	}
 	ret := make([]byte, n)
-	return append(ret[:len(ret)-len(bytes)], bytes...)
+	ReadBits(bigint, ret)
+	return ret
+}
+
+// ReadBits encodes the absolute value of bigint as big-endian bytes. Callers must ensure
+// that buf has enough space. If buf is too short the result will be incomplete.
+func ReadBits(bigint *big.Int, buf []byte) {
+	i := len(buf)
+	for _, d := range bigint.Bits() {
+		for j := 0; j < wordBytes && i > 0; j++ {
+			i--
+			buf[i] = byte(d)
+			d >>= 8
+		}
+	}
 }
 
 // U256 encodes as a 256 bit two's complement number. This operation is destructive.
@@ -119,9 +139,6 @@ func S256(x *big.Int) *big.Int {
 	}
 }
 
-// wordSize is the size number of bits in a big.Word.
-const wordSize = 32 << (uint64(^big.Word(0)) >> 63)
-
 // Exp implements exponentiation by squaring.
 // Exp returns a newly-allocated big integer and does not change
 // base or exponent. The result is truncated to 256 bits.
@@ -131,7 +148,7 @@ func Exp(base, exponent *big.Int) *big.Int {
 	result := big.NewInt(1)
 
 	for _, word := range exponent.Bits() {
-		for i := 0; i < wordSize; i++ {
+		for i := 0; i < wordBits; i++ {
 			if word&1 == 1 {
 				U256(result.Mul(result, base))
 			}
-- 
cgit