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	}