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 0c68263a57d8674e2ae8a22fc74cb735c49ef4b2..f0d8390f75790687e55dc2a24d36a8768668c876 100644 (file)
--- 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 42c5f4c7cce25f5477587c239820eed500a375ce..5b0da2c48fcd7e5ce3a87ee68f2ef184ac2ae9c4 100644 (file)
--- 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)
        }
 }