From: Sergey Matveev <stargrave@stargrave.org>
Date: Fri, 18 Jan 2019 22:23:31 +0000 (+0300)
Subject: Performance optimizations
X-Git-Tag: v1.0.0~4
X-Git-Url: http://www.git.cypherpunks.ru/?p=balloon.git;a=commitdiff_plain;h=9a1a4ae452c536a3523b31269697c85479465b87

Performance optimizations

* Use single large slice for buffer, instead of many smaller ones
* Less integer-format conversions
* Use SHA512 instead of SHA256 in tests for speed
---

diff --git a/balloon.go b/balloon.go
index 0c68263..f0d8390 100644
--- a/balloon.go
+++ b/balloon.go
@@ -52,48 +52,49 @@ const (
 //                buf[m] = hash(cnt++ || buf[m] || buf[other])
 //    # Extract output from buffer.
 //    return buf[sCost-1]
-func B(h hash.Hash, passwd, salt []byte, sCost, tCost int) []byte {
+func B(h hash.Hash, passwd, salt []byte, sCost, tCost uint64) []byte {
 	var cnt uint64
 	intBuf := make([]byte, 8)
-	buf := make([][]byte, sCost)
+	hSize := uint64(h.Size())
+	buf := make([]byte, 0, sCost*hSize)
 	// Expand input into buffer
 	binary.BigEndian.PutUint64(intBuf, cnt)
 	cnt++
 	h.Write(intBuf)
 	h.Write(passwd)
 	h.Write(salt)
-	buf[0] = h.Sum(nil)
-	var m int
+	buf = h.Sum(buf)
+	var m uint64
 	for m = 1; m < sCost; m++ {
 		binary.BigEndian.PutUint64(intBuf, cnt)
 		cnt++
 		h.Reset()
 		h.Write(intBuf)
-		h.Write(buf[m-1])
-		buf[m] = h.Sum(nil)
+		h.Write(buf[(m-1)*hSize : m*hSize])
+		buf = h.Sum(buf)
 	}
 	// Mix buffer contents
 	var prev []byte
-	var i int
+	var i uint64
+	var neigh uint64
 	bi := big.NewInt(0)
 	bs := big.NewInt(int64(sCost))
 	biBuf := make([]byte, 0, h.Size())
-	var other int
-	for t := 0; t < tCost; t++ {
+	for t := uint64(0); t < tCost; t++ {
 		for m = 0; m < sCost; m++ {
 			// Hash last and current blocks
 			if m == 0 {
-				prev = buf[len(buf)-1]
+				prev = buf[(sCost-1)*hSize:]
 			} else {
-				prev = buf[m-1]
+				prev = buf[(m-1)*hSize : m*hSize]
 			}
 			binary.BigEndian.PutUint64(intBuf, cnt)
 			cnt++
 			h.Reset()
 			h.Write(intBuf)
 			h.Write(prev)
-			h.Write(buf[m])
-			buf[m] = h.Sum(buf[m][:0])
+			h.Write(buf[m*hSize : (m+1)*hSize])
+			buf = h.Sum(buf[:m*hSize])
 
 			// Hash in pseudorandomly chosen blocks
 			for i = 0; i < delta; i++ {
@@ -102,28 +103,28 @@ func B(h hash.Hash, passwd, salt []byte, sCost, tCost int) []byte {
 				h.Reset()
 				h.Write(intBuf)
 				h.Write(salt)
-				binary.BigEndian.PutUint64(intBuf, uint64(t))
+				binary.BigEndian.PutUint64(intBuf, t)
 				h.Write(intBuf)
-				binary.BigEndian.PutUint64(intBuf, uint64(m))
+				binary.BigEndian.PutUint64(intBuf, m)
 				h.Write(intBuf)
-				binary.BigEndian.PutUint64(intBuf, uint64(i))
+				binary.BigEndian.PutUint64(intBuf, i)
 				h.Write(intBuf)
 				biBuf = h.Sum(biBuf[:0])
 				bi.SetBytes(biBuf)
 				bi.Mod(bi, bs)
-				other = int(bi.Uint64())
 				binary.BigEndian.PutUint64(intBuf, cnt)
 				cnt++
 				h.Reset()
 				h.Write(intBuf)
-				h.Write(buf[m])
-				h.Write(buf[other])
-				buf[m] = h.Sum(buf[m][:0])
+				h.Write(buf[m*hSize : (m+1)*hSize])
+				neigh = bi.Uint64()
+				h.Write(buf[neigh*hSize : (neigh+1)*hSize])
+				buf = h.Sum(buf[:m*hSize])
 			}
 		}
 	}
 	// Extract output from buffer
-	return buf[sCost-1]
+	return buf[(sCost-1)*hSize:]
 }
 
 // This function adds additional functionality over pure B(): ability to
diff --git a/balloon_test.go b/balloon_test.go
index 42c5f4c..5b0da2c 100644
--- a/balloon_test.go
+++ b/balloon_test.go
@@ -21,7 +21,7 @@ package balloon
 
 import (
 	"crypto/rand"
-	"crypto/sha256"
+	"crypto/sha512"
 	"testing"
 	"testing/quick"
 )
@@ -31,7 +31,7 @@ func TestB(t *testing.T) {
 		if len(passwd) == 0 || len(salt) == 0 {
 			return true
 		}
-		B(sha256.New(), passwd, salt, int(s)%16+1, int(t)%16+1)
+		B(sha512.New(), passwd, salt, uint64(s)%16+1, uint64(t)%16+1)
 		return true
 	}
 	if err := quick.Check(f, nil); err != nil {
@@ -44,7 +44,7 @@ func TestH(t *testing.T) {
 		if len(passwd) == 0 || len(salt) == 0 {
 			return true
 		}
-		H(sha256.New, passwd, salt, int(s)%16+1, int(t)%16+1, int(p)%8+1)
+		H(sha512.New, passwd, salt, int(s)%16+1, int(t)%16+1, int(p)%8+1)
 		return true
 	}
 	if err := quick.Check(f, nil); err != nil {
@@ -57,9 +57,11 @@ func BenchmarkB(b *testing.B) {
 	rand.Read(passwd)
 	salt := make([]byte, 8)
 	rand.Read(salt)
+	h := sha512.New()
+	sCost := uint64(1 << 10 / h.Size())
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
-		B(sha256.New(), passwd, salt, 1<<10/sha256.New().Size(), 4)
+		B(h, passwd, salt, sCost, 4)
 	}
 }
 
@@ -68,8 +70,9 @@ func BenchmarkH(b *testing.B) {
 	rand.Read(passwd)
 	salt := make([]byte, 8)
 	rand.Read(salt)
+	sCost := 1 << 10 / sha512.New().Size()
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
-		H(sha256.New, passwd, salt, 1<<10/sha256.New().Size(), 4, 4)
+		H(sha512.New, passwd, salt, sCost, 4, 4)
 	}
 }