blob: aa65dbd7a8feba218ace72f9cd409a86f4d6ac0b [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. // Fast versions of the routines in this file are in fast.arith.s. // Simply replace this file with arith.s (renamed from fast.arith.s) // and the bignum package will build and run on a platform that // supports the assembly routines. package bignum import "unsafe" // z1<<64 + z0 = x*y func Mul128(x, y uint64) (z1, z0 uint64) { // Split x and y into 2 halfwords each, multiply // the halfwords separately while avoiding overflow, // and return the product as 2 words. const ( W = uint(unsafe.Sizeof(x)) * 8 W2 = W / 2 B2 = 1 << W2 M2 = B2 - 1 ) if x < y { x, y = y, x } if x < B2 { // y < B2 because y <= x // sub-digits of x and y are (0, x) and (0, y) // z = z[0] = x*y z0 = x * y return } if y < B2 { // sub-digits of x and y are (x1, x0) and (0, y) // x = (x1*B2 + x0) // y = (y1*B2 + y0) x1, x0 := x>>W2, x&M2 // x*y = t2*B2*B2 + t1*B2 + t0 t0 := x0 * y t1 := x1 * y // compute result digits but avoid overflow // z = z[1]*B + z[0] = x*y z0 = t1<>W2) >> W2 return } // general case // sub-digits of x and y are (x1, x0) and (y1, y0) // x = (x1*B2 + x0) // y = (y1*B2 + y0) x1, x0 := x>>W2, x&M2 y1, y0 := y>>W2, y&M2 // x*y = t2*B2*B2 + t1*B2 + t0 t0 := x0 * y0 t1 := x1*y0 + x0*y1 t2 := x1 * y1 // compute result digits but avoid overflow // z = z[1]*B + z[0] = x*y z0 = t1<>W2)>>W2 return } // z1<<64 + z0 = x*y + c func MulAdd128(x, y, c uint64) (z1, z0 uint64) { // Split x and y into 2 halfwords each, multiply // the halfwords separately while avoiding overflow, // and return the product as 2 words. const ( W = uint(unsafe.Sizeof(x)) * 8 W2 = W / 2 B2 = 1 << W2 M2 = B2 - 1 ) // TODO(gri) Should implement special cases for faster execution. // general case // sub-digits of x, y, and c are (x1, x0), (y1, y0), (c1, c0) // x = (x1*B2 + x0) // y = (y1*B2 + y0) x1, x0 := x>>W2, x&M2 y1, y0 := y>>W2, y&M2 c1, c0 := c>>W2, c&M2 // x*y + c = t2*B2*B2 + t1*B2 + t0 t0 := x0*y0 + c0 t1 := x1*y0 + x0*y1 + c1 t2 := x1 * y1 // compute result digits but avoid overflow // z = z[1]*B + z[0] = x*y z0 = t1<>W2)>>W2 return } // q = (x1<<64 + x0)/y + r func Div128(x1, x0, y uint64) (q, r uint64) { if x1 == 0 { q, r = x0/y, x0%y return } // TODO(gri) Implement general case. panic("Div128 not implemented for x > 1<<64-1") }