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.
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.
11 // A Word represents a single digit of a multi-precision unsigned integer.
15 // Compute the size _S of a Word in bytes.
17 _logS
= _m
>>8&1 + _m
>>16&1 + _m
>>32&1
20 _W
= _S
<< 3 // word size in bits
21 _B
= 1 << _W
// digit base
22 _M
= _B
- 1 // digit mask
24 _W2
= _W
/ 2 // half word size in bits
25 _B2
= 1 << _W2
// half digit base
26 _M2
= _B2
- 1 // half digit mask
29 // ----------------------------------------------------------------------------
30 // Elementary operations on words
32 // These operations are used by the vector operations below.
34 // z1<<_W + z0 = x+y+c, with c == 0 or 1
35 func addWW_g(x
, y
, c Word
) (z1
, z0 Word
) {
44 // z1<<_W + z0 = x-y-c, with c == 0 or 1
45 func subWW_g(x
, y
, c Word
) (z1
, z0 Word
) {
55 func mulWW(x
, y Word
) (z1
, z0 Word
) { return mulWW_g(x
, y
) }
57 // Adapted from Warren, Hacker's Delight, p. 132.
58 func mulWW_g(x
, y Word
) (z1
, z0 Word
) {
68 z1
= x1
*y1
+ w2
+ w1
>>_W2
73 // z1<<_W + z0 = x*y + c
74 func mulAddWWW_g(x
, y
, c Word
) (z1
, z0 Word
) {
75 z1
, zz0
:= mulWW(x
, y
)
76 if z0
= zz0
+ c
; z0
< zz0
{
82 // Length of x in bits.
83 func bitLen(x Word
) (n
int) { return bitLen_g(x
) }
84 func bitLen_g(x Word
) (n
int) {
85 for ; x
>= 0x8000; x
>>= 16 {
106 // log2 computes the integer binary logarithm of x.
107 // The result is the integer n for which 2^n <= x < 2^(n+1).
108 // If x == 0, the result is -1.
109 func log2(x Word
) int {
113 // Number of leading zeros in x.
114 func leadingZeros(x Word
) uint {
115 return uint(_W
- bitLen(x
))
118 // q = (u1<<_W + u0 - r)/y
119 func divWW(x1
, x0
, y Word
) (q
, r Word
) { return divWW_g(x1
, x0
, y
) }
121 // Adapted from Warren, Hacker's Delight, p. 152.
122 func divWW_g(u1
, u0
, v Word
) (q
, r Word
) {
124 return 1<<_W
- 1, 1<<_W
- 1
132 un32
:= u1
<<s | u0
>>(_W
-s
)
137 rhat
:= un32
- q1
*vn1
140 if q1
>= _B2 || q1
*vn0
> _B2
*rhat
+un1
{
148 un21
:= un32
*_B2
+ un1
- q1
*v
153 if q0
>= _B2 || q0
*vn0
> _B2
*rhat
+un0
{
161 return q1
*_B2
+ q0
, (un21
*_B2
+ un0
- q0
*v
) >> s
164 func addVV(z
, x
, y
[]Word
) (c Word
) { return addVV_g(z
, x
, y
) }
165 func addVV_g(z
, x
, y
[]Word
) (c Word
) {
167 c
, z
[i
] = addWW_g(x
[i
], y
[i
], c
)
172 func subVV(z
, x
, y
[]Word
) (c Word
) { return subVV_g(z
, x
, y
) }
173 func subVV_g(z
, x
, y
[]Word
) (c Word
) {
175 c
, z
[i
] = subWW_g(x
[i
], y
[i
], c
)
180 func addVW(z
, x
[]Word
, y Word
) (c Word
) { return addVW_g(z
, x
, y
) }
181 func addVW_g(z
, x
[]Word
, y Word
) (c Word
) {
184 c
, z
[i
] = addWW_g(x
[i
], c
, 0)
189 func subVW(z
, x
[]Word
, y Word
) (c Word
) { return subVW_g(z
, x
, y
) }
190 func subVW_g(z
, x
[]Word
, y Word
) (c Word
) {
193 c
, z
[i
] = subWW_g(x
[i
], c
, 0)
198 func shlVU(z
, x
[]Word
, s
uint) (c Word
) { return shlVU_g(z
, x
, s
) }
199 func shlVU_g(z
, x
[]Word
, s
uint) (c Word
) {
200 if n
:= len(z
); n
> 0 {
204 for i
:= n
- 1; i
> 0; i
-- {
214 func shrVU(z
, x
[]Word
, s
uint) (c Word
) { return shrVU_g(z
, x
, s
) }
215 func shrVU_g(z
, x
[]Word
, s
uint) (c Word
) {
216 if n
:= len(z
); n
> 0 {
220 for i
:= 0; i
< n
-1; i
++ {
230 func mulAddVWW(z
, x
[]Word
, y
, r Word
) (c Word
) { return mulAddVWW_g(z
, x
, y
, r
) }
231 func mulAddVWW_g(z
, x
[]Word
, y
, r Word
) (c Word
) {
234 c
, z
[i
] = mulAddWWW_g(x
[i
], y
, c
)
239 func addMulVVW(z
, x
[]Word
, y Word
) (c Word
) { return addMulVVW_g(z
, x
, y
) }
240 func addMulVVW_g(z
, x
[]Word
, y Word
) (c Word
) {
242 z1
, z0
:= mulAddWWW_g(x
[i
], y
, z
[i
])
243 c
, z
[i
] = addWW_g(z0
, c
, 0)
249 func divWVW(z
[]Word
, xn Word
, x
[]Word
, y Word
) (r Word
) { return divWVW_g(z
, xn
, x
, y
) }
250 func divWVW_g(z
[]Word
, xn Word
, x
[]Word
, y Word
) (r Word
) {
252 for i
:= len(z
) - 1; i
>= 0; i
-- {
253 z
[i
], r
= divWW_g(r
, x
[i
], y
)