diff options
Diffstat (limited to 'libgo/go/math/big/nat.go')
| -rw-r--r-- | libgo/go/math/big/nat.go | 33 |
1 files changed, 28 insertions, 5 deletions
diff --git a/libgo/go/math/big/nat.go b/libgo/go/math/big/nat.go index 79cf6e07..2e65d2a 100644 --- a/libgo/go/math/big/nat.go +++ b/libgo/go/math/big/nat.go @@ -8,7 +8,10 @@ package big -import "math/rand" +import ( + "math/rand" + "sync" +) // An unsigned integer x of the form // @@ -539,6 +542,21 @@ func (z nat) div(z2, u, v nat) (q, r nat) { return } +// getNat returns a nat of len n. The contents may not be zero. +func getNat(n int) nat { + var z nat + if v := natPool.Get(); v != nil { + z = v.(nat) + } + return z.make(n) +} + +func putNat(x nat) { + natPool.Put(x) +} + +var natPool sync.Pool + // q = (uIn-r)/v, with 0 <= r < y // Uses z as storage for q, and u as storage for r if possible. // See Knuth, Volume 2, section 4.3.1, Algorithm D. @@ -557,7 +575,7 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { } q = z.make(m + 1) - qhatv := make(nat, n+1) + qhatv := getNat(n + 1) if alias(u, uIn) || alias(u, v) { u = nil // u is an alias for uIn or v - cannot reuse } @@ -565,10 +583,11 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { u.clear() // TODO(gri) no need to clear if we allocated a new u // D1. + var v1 nat shift := nlz(v[n-1]) if shift > 0 { // do not modify v, it may be used by another goroutine simultaneously - v1 := make(nat, n) + v1 = getNat(n) shlVU(v1, v, shift) v = v1 } @@ -609,6 +628,10 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { q[j] = qhat } + if v1 != nil { + putNat(v1) + } + putNat(qhatv) q = q.norm() shrVU(u, u, shift) @@ -647,7 +670,7 @@ func trailingZeroBits(x Word) uint { // x & -x leaves only the right-most bit set in the word. Let k be the // index of that bit. Since only a single bit is set, the value is two // to the power of k. Multiplying by a power of two is equivalent to - // left shifting, in this case by k bits. The de Bruijn constant is + // left shifting, in this case by k bits. The de Bruijn constant is // such that all six bit, consecutive substrings are distinct. // Therefore, if we have a left shifted version of this constant we can // find by how many bits it was shifted by looking at which six bit @@ -1018,7 +1041,7 @@ func (z nat) expNNWindowed(x, y, m nat) nat { for j := 0; j < _W; j += n { if i != len(y)-1 || j != 0 { // Unrolled loop for significant performance - // gain. Use go test -bench=".*" in crypto/rsa + // gain. Use go test -bench=".*" in crypto/rsa // to check performance before making changes. zz = zz.mul(z, z) zz, z = z, zz |