1 /** 2 * Botan 64x64=128 multiplication 3 * 4 * Copyright: 5 * (C) 1999-2010,2014 Jack Lloyd 6 * (C) 2014-2015 Etienne Cimon 7 * 2006 Luca Piccarreta 8 * 9 * License: 10 * Botan is released under the Simplified BSD License (see LICENSE.md) 11 */ 12 module botan_math.mul128; 13 14 void mul64x64_128(ulong a, ulong b, ref ulong[2] res) pure 15 { 16 version (D_InlineAsm_X86_64) { 17 ulong* lo = res.ptr; 18 ulong* hi = &res[1]; 19 asm pure nothrow @nogc { 20 mov RAX, a; 21 mul b; 22 mov RBX, lo; 23 mov RCX, hi; 24 mov [RBX], RAX; 25 mov [RCX], RDX; 26 } 27 } 28 else { 29 /* 30 * Do a 64x64->128 multiply using four 32x32->64 multiplies plus 31 * some adds and shifts. Last resort for CPUs like UltraSPARC (with 32 * 64-bit registers/ALU, but no 64x64->128 multiply) or 32-bit CPUs. 33 */ 34 const size_t HWORD_BITS = 32; 35 const uint HWORD_MASK = 0xFFFFFFFF; 36 37 const uint a_hi = (a >> HWORD_BITS); 38 const uint a_lo = (a & HWORD_MASK); 39 const uint b_hi = (b >> HWORD_BITS); 40 const uint b_lo = (b & HWORD_MASK); 41 42 ulong x0 = cast(ulong)(a_hi) * b_hi; 43 ulong x1 = cast(ulong)(a_lo) * b_hi; 44 ulong x2 = cast(ulong)(a_hi) * b_lo; 45 ulong x3 = cast(ulong)(a_lo) * b_lo; 46 47 // this cannot overflow as (2^32-1)^2 + 2^32-1 < 2^64-1 48 x2 += x3 >> HWORD_BITS; 49 50 // this one can overflow 51 x2 += x1; 52 53 // propagate the carry if any 54 x0 += cast(ulong)(cast(bool)(x2 < x1)) << HWORD_BITS; 55 56 res[1] = x0 + (x2 >> HWORD_BITS); 57 res[0] = ((x2 & HWORD_MASK) << HWORD_BITS) + (x3 & HWORD_MASK); 58 } 59 }