Source file src/pkg/math/big/arith.go
1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // This file provides Go implementations of elementary multi-precision 6 // arithmetic operations on word vectors. Needed for platforms without 7 // assembly implementations of these routines. 8 9 package big 10 11 // A Word represents a single digit of a multi-precision unsigned integer. 12 type Word uintptr 13 14 const ( 15 // Compute the size _S of a Word in bytes. 16 _m = ^Word(0) 17 _logS = _m>>8&1 + _m>>16&1 + _m>>32&1 18 _S = 1 << _logS 19 20 _W = _S << 3 // word size in bits 21 _B = 1 << _W // digit base 22 _M = _B - 1 // digit mask 23 24 _W2 = _W / 2 // half word size in bits 25 _B2 = 1 << _W2 // half digit base 26 _M2 = _B2 - 1 // half digit mask 27 ) 28 29 // ---------------------------------------------------------------------------- 30 // Elementary operations on words 31 // 32 // These operations are used by the vector operations below. 33 34 // z1<<_W + z0 = x+y+c, with c == 0 or 1 35 func addWW_g(x, y, c Word) (z1, z0 Word) { 36 yc := y + c 37 z0 = x + yc 38 if z0 < x || yc < y { 39 z1 = 1 40 } 41 return 42 } 43 44 // z1<<_W + z0 = x-y-c, with c == 0 or 1 45 func subWW_g(x, y, c Word) (z1, z0 Word) { 46 yc := y + c 47 z0 = x - yc 48 if z0 > x || yc < y { 49 z1 = 1 50 } 51 return 52 } 53 54 // z1<<_W + z0 = x*y 55 // Adapted from Warren, Hacker's Delight, p. 132. 56 func mulWW_g(x, y Word) (z1, z0 Word) { 57 x0 := x & _M2 58 x1 := x >> _W2 59 y0 := y & _M2 60 y1 := y >> _W2 61 w0 := x0 * y0 62 t := x1*y0 + w0>>_W2 63 w1 := t & _M2 64 w2 := t >> _W2 65 w1 += x0 * y1 66 z1 = x1*y1 + w2 + w1>>_W2 67 z0 = x * y 68 return 69 } 70 71 // z1<<_W + z0 = x*y + c 72 func mulAddWWW_g(x, y, c Word) (z1, z0 Word) { 73 z1, zz0 := mulWW(x, y) 74 if z0 = zz0 + c; z0 < zz0 { 75 z1++ 76 } 77 return 78 } 79 80 // Length of x in bits. 81 func bitLen_g(x Word) (n int) { 82 for ; x >= 0x8000; x >>= 16 { 83 n += 16 84 } 85 if x >= 0x80 { 86 x >>= 8 87 n += 8 88 } 89 if x >= 0x8 { 90 x >>= 4 91 n += 4 92 } 93 if x >= 0x2 { 94 x >>= 2 95 n += 2 96 } 97 if x >= 0x1 { 98 n++ 99 } 100 return 101 } 102 103 // log2 computes the integer binary logarithm of x. 104 // The result is the integer n for which 2^n <= x < 2^(n+1). 105 // If x == 0, the result is -1. 106 func log2(x Word) int { 107 return bitLen(x) - 1 108 } 109 110 // Number of leading zeros in x. 111 func leadingZeros(x Word) uint { 112 return uint(_W - bitLen(x)) 113 } 114 115 // q = (u1<<_W + u0 - r)/y 116 // Adapted from Warren, Hacker's Delight, p. 152. 117 func divWW_g(u1, u0, v Word) (q, r Word) { 118 if u1 >= v { 119 return 1<<_W - 1, 1<<_W - 1 120 } 121 122 s := leadingZeros(v) 123 v <<= s 124 125 vn1 := v >> _W2 126 vn0 := v & _M2 127 un32 := u1<<s | u0>>(_W-s) 128 un10 := u0 << s 129 un1 := un10 >> _W2 130 un0 := un10 & _M2 131 q1 := un32 / vn1 132 rhat := un32 - q1*vn1 133 134 again1: 135 if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 { 136 q1-- 137 rhat += vn1 138 if rhat < _B2 { 139 goto again1 140 } 141 } 142 143 un21 := un32*_B2 + un1 - q1*v 144 q0 := un21 / vn1 145 rhat = un21 - q0*vn1 146 147 again2: 148 if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 { 149 q0-- 150 rhat += vn1 151 if rhat < _B2 { 152 goto again2 153 } 154 } 155 156 return q1*_B2 + q0, (un21*_B2 + un0 - q0*v) >> s 157 } 158 159 func addVV_g(z, x, y []Word) (c Word) { 160 for i := range z { 161 c, z[i] = addWW_g(x[i], y[i], c) 162 } 163 return 164 } 165 166 func subVV_g(z, x, y []Word) (c Word) { 167 for i := range z { 168 c, z[i] = subWW_g(x[i], y[i], c) 169 } 170 return 171 } 172 173 func addVW_g(z, x []Word, y Word) (c Word) { 174 c = y 175 for i := range z { 176 c, z[i] = addWW_g(x[i], c, 0) 177 } 178 return 179 } 180 181 func subVW_g(z, x []Word, y Word) (c Word) { 182 c = y 183 for i := range z { 184 c, z[i] = subWW_g(x[i], c, 0) 185 } 186 return 187 } 188 189 func shlVU_g(z, x []Word, s uint) (c Word) { 190 if n := len(z); n > 0 { 191 ŝ := _W - s 192 w1 := x[n-1] 193 c = w1 >> ŝ 194 for i := n - 1; i > 0; i-- { 195 w := w1 196 w1 = x[i-1] 197 z[i] = w<<s | w1>>ŝ 198 } 199 z[0] = w1 << s 200 } 201 return 202 } 203 204 func shrVU_g(z, x []Word, s uint) (c Word) { 205 if n := len(z); n > 0 { 206 ŝ := _W - s 207 w1 := x[0] 208 c = w1 << ŝ 209 for i := 0; i < n-1; i++ { 210 w := w1 211 w1 = x[i+1] 212 z[i] = w>>s | w1<<ŝ 213 } 214 z[n-1] = w1 >> s 215 } 216 return 217 } 218 219 func mulAddVWW_g(z, x []Word, y, r Word) (c Word) { 220 c = r 221 for i := range z { 222 c, z[i] = mulAddWWW_g(x[i], y, c) 223 } 224 return 225 } 226 227 func addMulVVW_g(z, x []Word, y Word) (c Word) { 228 for i := range z { 229 z1, z0 := mulAddWWW_g(x[i], y, z[i]) 230 c, z[i] = addWW_g(z0, c, 0) 231 c += z1 232 } 233 return 234 } 235 236 func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) { 237 r = xn 238 for i := len(z) - 1; i >= 0; i-- { 239 z[i], r = divWW_g(r, x[i], y) 240 } 241 return 242 }