blob: b0885f261fe9bad8e35290b94200a98a2048505b [file] [log] [blame]
 // Copyright 2009 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. // This file provides Go implementations of elementary multi-precision // arithmetic operations on word vectors. These have the suffix _g. // These are needed for platforms without assembly implementations of these routines. // This file also contains elementary operations that can be implemented // sufficiently efficiently in Go. package big import "math/bits" // A Word represents a single digit of a multi-precision unsigned integer. type Word uint const ( _S = _W / 8 // word size in bytes _W = bits.UintSize // word size in bits _B = 1 << _W // digit base _M = _B - 1 // digit mask ) // Many of the loops in this file are of the form // for i := 0; i < len(z) && i < len(x) && i < len(y); i++ // i < len(z) is the real condition. // However, checking i < len(x) && i < len(y) as well is faster than // having the compiler do a bounds check in the body of the loop; // remarkably it is even faster than hoisting the bounds check // out of the loop, by doing something like // _, _ = x[len(z)-1], y[len(z)-1] // There are other ways to hoist the bounds check out of the loop, // but the compiler's BCE isn't powerful enough for them (yet?). // See the discussion in CL 164966. // ---------------------------------------------------------------------------- // Elementary operations on words // // These operations are used by the vector operations below. // z1<<_W + z0 = x*y func mulWW_g(x, y Word) (z1, z0 Word) { hi, lo := bits.Mul(uint(x), uint(y)) return Word(hi), Word(lo) } // z1<<_W + z0 = x*y + c func mulAddWWW_g(x, y, c Word) (z1, z0 Word) { hi, lo := bits.Mul(uint(x), uint(y)) var cc uint lo, cc = bits.Add(lo, uint(c), 0) return Word(hi + cc), Word(lo) } // nlz returns the number of leading zeros in x. // Wraps bits.LeadingZeros call for convenience. func nlz(x Word) uint { return uint(bits.LeadingZeros(uint(x))) } // q = (u1<<_W + u0 - r)/v func divWW_g(u1, u0, v Word) (q, r Word) { qq, rr := bits.Div(uint(u1), uint(u0), uint(v)) return Word(qq), Word(rr) } // The resulting carry c is either 0 or 1. func addVV_g(z, x, y []Word) (c Word) { // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x) && i < len(y); i++ { zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c)) z[i] = Word(zi) c = Word(cc) } return } // The resulting carry c is either 0 or 1. func subVV_g(z, x, y []Word) (c Word) { // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x) && i < len(y); i++ { zi, cc := bits.Sub(uint(x[i]), uint(y[i]), uint(c)) z[i] = Word(zi) c = Word(cc) } return } // The resulting carry c is either 0 or 1. func addVW_g(z, x []Word, y Word) (c Word) { c = y // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x); i++ { zi, cc := bits.Add(uint(x[i]), uint(c), 0) z[i] = Word(zi) c = Word(cc) } return } // addVWlarge is addVW, but intended for large z. // The only difference is that we check on every iteration // whether we are done with carries, // and if so, switch to a much faster copy instead. // This is only a good idea for large z, // because the overhead of the check and the function call // outweigh the benefits when z is small. func addVWlarge(z, x []Word, y Word) (c Word) { c = y // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x); i++ { if c == 0 { copy(z[i:], x[i:]) return } zi, cc := bits.Add(uint(x[i]), uint(c), 0) z[i] = Word(zi) c = Word(cc) } return } func subVW_g(z, x []Word, y Word) (c Word) { c = y // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x); i++ { zi, cc := bits.Sub(uint(x[i]), uint(c), 0) z[i] = Word(zi) c = Word(cc) } return } // subVWlarge is to subVW as addVWlarge is to addVW. func subVWlarge(z, x []Word, y Word) (c Word) { c = y // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x); i++ { if c == 0 { copy(z[i:], x[i:]) return } zi, cc := bits.Sub(uint(x[i]), uint(c), 0) z[i] = Word(zi) c = Word(cc) } return } func shlVU_g(z, x []Word, s uint) (c Word) { if s == 0 { copy(z, x) return } if len(z) == 0 { return } s &= _W - 1 // hint to the compiler that shifts by s don't need guard code ŝ := _W - s ŝ &= _W - 1 // ditto c = x[len(z)-1] >> ŝ for i := len(z) - 1; i > 0; i-- { z[i] = x[i]<>ŝ } z = x << s return } func shrVU_g(z, x []Word, s uint) (c Word) { if s == 0 { copy(z, x) return } if len(z) == 0 { return } s &= _W - 1 // hint to the compiler that shifts by s don't need guard code ŝ := _W - s ŝ &= _W - 1 // ditto c = x << ŝ for i := 0; i < len(z)-1; i++ { z[i] = x[i]>>s | x[i+1]<<ŝ } z[len(z)-1] = x[len(z)-1] >> s return } func mulAddVWW_g(z, x []Word, y, r Word) (c Word) { c = r // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x); i++ { c, z[i] = mulAddWWW_g(x[i], y, c) } return } func addMulVVW_g(z, x []Word, y Word) (c Word) { // The comment near the top of this file discusses this for loop condition. for i := 0; i < len(z) && i < len(x); i++ { z1, z0 := mulAddWWW_g(x[i], y, z[i]) lo, cc := bits.Add(uint(z0), uint(c), 0) c, z[i] = Word(cc), Word(lo) c += z1 } return } func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) { r = xn for i := len(z) - 1; i >= 0; i-- { z[i], r = divWW_g(r, x[i], y) } return }