/src/botan/build/include/botan/internal/mul128.h
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * 64x64->128 bit multiply operation |
3 | | * (C) 2013,2015 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #ifndef BOTAN_UTIL_MUL128_H_ |
9 | | #define BOTAN_UTIL_MUL128_H_ |
10 | | |
11 | | #include <botan/types.h> |
12 | | |
13 | | #if defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_CPU_HAS_NATIVE_64BIT) |
14 | | #include <intrin.h> |
15 | | #endif |
16 | | |
17 | | namespace Botan { |
18 | | |
19 | | #if defined(__SIZEOF_INT128__) && defined(BOTAN_TARGET_CPU_HAS_NATIVE_64BIT) |
20 | | #define BOTAN_TARGET_HAS_NATIVE_UINT128 |
21 | | |
22 | | // GCC complains if this isn't marked with __extension__ |
23 | | __extension__ typedef unsigned __int128 uint128_t; |
24 | | #endif |
25 | | |
26 | | /** |
27 | | * Perform a 64x64->128 bit multiplication |
28 | | */ |
29 | 0 | inline void mul64x64_128(uint64_t a, uint64_t b, uint64_t* lo, uint64_t* hi) { |
30 | 0 | #if defined(BOTAN_TARGET_HAS_NATIVE_UINT128) |
31 | 0 |
|
32 | 0 | const uint128_t r = static_cast<uint128_t>(a) * b; |
33 | 0 | *hi = (r >> 64) & 0xFFFFFFFFFFFFFFFF; |
34 | 0 | *lo = (r)&0xFFFFFFFFFFFFFFFF; |
35 | 0 |
|
36 | 0 | #elif defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_ARCH_IS_X86_64) |
37 | 0 | *lo = _umul128(a, b, hi); |
38 | 0 |
|
39 | 0 | #elif defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_ARCH_IS_ARM64) |
40 | 0 | *lo = a * b; |
41 | 0 | *hi = __umulh(a, b); |
42 | 0 |
|
43 | 0 | #elif defined(BOTAN_USE_GCC_INLINE_ASM) && defined(BOTAN_TARGET_ARCH_IS_X86_64) |
44 | 0 | asm("mulq %3" : "=d"(*hi), "=a"(*lo) : "a"(a), "rm"(b) : "cc"); |
45 | 0 |
|
46 | 0 | #elif defined(BOTAN_USE_GCC_INLINE_ASM) && defined(BOTAN_TARGET_ARCH_IS_PPC64) |
47 | 0 | asm("mulhdu %0,%1,%2" : "=r"(*hi) : "r"(a), "r"(b) : "cc"); |
48 | 0 | *lo = a * b; |
49 | 0 |
|
50 | 0 | #else |
51 | 0 |
|
52 | 0 | /* |
53 | 0 | * Do a 64x64->128 multiply using four 32x32->64 multiplies plus |
54 | 0 | * some adds and shifts. Last resort for CPUs like UltraSPARC (with |
55 | 0 | * 64-bit registers/ALU, but no 64x64->128 multiply) or 32-bit CPUs. |
56 | 0 | */ |
57 | 0 | const size_t HWORD_BITS = 32; |
58 | 0 | const uint32_t HWORD_MASK = 0xFFFFFFFF; |
59 | 0 |
|
60 | 0 | const uint32_t a_hi = (a >> HWORD_BITS); |
61 | 0 | const uint32_t a_lo = (a & HWORD_MASK); |
62 | 0 | const uint32_t b_hi = (b >> HWORD_BITS); |
63 | 0 | const uint32_t b_lo = (b & HWORD_MASK); |
64 | 0 |
|
65 | 0 | uint64_t x0 = static_cast<uint64_t>(a_hi) * b_hi; |
66 | 0 | uint64_t x1 = static_cast<uint64_t>(a_lo) * b_hi; |
67 | 0 | uint64_t x2 = static_cast<uint64_t>(a_hi) * b_lo; |
68 | 0 | uint64_t x3 = static_cast<uint64_t>(a_lo) * b_lo; |
69 | 0 |
|
70 | 0 | // this cannot overflow as (2^32-1)^2 + 2^32-1 < 2^64-1 |
71 | 0 | x2 += x3 >> HWORD_BITS; |
72 | 0 |
|
73 | 0 | // this one can overflow |
74 | 0 | x2 += x1; |
75 | 0 |
|
76 | 0 | // propagate the carry if any |
77 | 0 | x0 += static_cast<uint64_t>(static_cast<bool>(x2 < x1)) << HWORD_BITS; |
78 | 0 |
|
79 | 0 | *hi = x0 + (x2 >> HWORD_BITS); |
80 | 0 | *lo = ((x2 & HWORD_MASK) << HWORD_BITS) + (x3 & HWORD_MASK); |
81 | 0 | #endif |
82 | 0 | } |
83 | | |
84 | | } // namespace Botan |
85 | | |
86 | | #endif |