/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 | | #if defined(_M_ARM64) |
16 | | #pragma intrinsic(__umulh) |
17 | | #else |
18 | | #pragma intrinsic(_umul128) |
19 | | #endif |
20 | | #endif |
21 | | |
22 | | namespace Botan { |
23 | | |
24 | | #if defined(__SIZEOF_INT128__) && defined(BOTAN_TARGET_CPU_HAS_NATIVE_64BIT) |
25 | | #define BOTAN_TARGET_HAS_NATIVE_UINT128 |
26 | | |
27 | | // Prefer TI mode over __int128 as GCC rejects the latter in pendantic mode |
28 | | #if defined(__GNUG__) |
29 | | typedef unsigned int uint128_t __attribute__((mode(TI))); |
30 | | #else |
31 | | typedef unsigned __int128 uint128_t; |
32 | | #endif |
33 | | #endif |
34 | | |
35 | | /** |
36 | | * Perform a 64x64->128 bit multiplication |
37 | | */ |
38 | | inline void mul64x64_128(uint64_t a, uint64_t b, uint64_t* lo, uint64_t* hi) |
39 | 0 | { |
40 | 0 | #if defined(BOTAN_TARGET_HAS_NATIVE_UINT128) |
41 | 0 |
|
42 | 0 | const uint128_t r = static_cast<uint128_t>(a) * b; |
43 | 0 | *hi = (r >> 64) & 0xFFFFFFFFFFFFFFFF; |
44 | 0 | *lo = (r ) & 0xFFFFFFFFFFFFFFFF; |
45 | 0 |
|
46 | 0 | #elif defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_CPU_HAS_NATIVE_64BIT) |
47 | 0 | #if defined(_M_ARM64) |
48 | 0 | *lo = a * b; |
49 | 0 | *hi = __umulh(a, b); |
50 | 0 | #else |
51 | 0 | *lo = _umul128(a, b, hi); |
52 | 0 | #endif |
53 | 0 |
|
54 | 0 | #elif defined(BOTAN_USE_GCC_INLINE_ASM) && defined(BOTAN_TARGET_ARCH_IS_X86_64) |
55 | 0 | asm("mulq %3" |
56 | 0 | : "=d" (*hi), "=a" (*lo) |
57 | 0 | : "a" (a), "rm" (b) |
58 | 0 | : "cc"); |
59 | 0 |
|
60 | 0 | #elif defined(BOTAN_USE_GCC_INLINE_ASM) && defined(BOTAN_TARGET_ARCH_IS_PPC64) |
61 | 0 | asm("mulhdu %0,%1,%2" |
62 | 0 | : "=r" (*hi) |
63 | 0 | : "r" (a), "r" (b) |
64 | 0 | : "cc"); |
65 | 0 | *lo = a * b; |
66 | 0 |
|
67 | 0 | #else |
68 | 0 |
|
69 | 0 | /* |
70 | 0 | * Do a 64x64->128 multiply using four 32x32->64 multiplies plus |
71 | 0 | * some adds and shifts. Last resort for CPUs like UltraSPARC (with |
72 | 0 | * 64-bit registers/ALU, but no 64x64->128 multiply) or 32-bit CPUs. |
73 | 0 | */ |
74 | 0 | const size_t HWORD_BITS = 32; |
75 | 0 | const uint32_t HWORD_MASK = 0xFFFFFFFF; |
76 | 0 |
|
77 | 0 | const uint32_t a_hi = (a >> HWORD_BITS); |
78 | 0 | const uint32_t a_lo = (a & HWORD_MASK); |
79 | 0 | const uint32_t b_hi = (b >> HWORD_BITS); |
80 | 0 | const uint32_t b_lo = (b & HWORD_MASK); |
81 | 0 |
|
82 | 0 | uint64_t x0 = static_cast<uint64_t>(a_hi) * b_hi; |
83 | 0 | uint64_t x1 = static_cast<uint64_t>(a_lo) * b_hi; |
84 | 0 | uint64_t x2 = static_cast<uint64_t>(a_hi) * b_lo; |
85 | 0 | uint64_t x3 = static_cast<uint64_t>(a_lo) * b_lo; |
86 | 0 |
|
87 | 0 | // this cannot overflow as (2^32-1)^2 + 2^32-1 < 2^64-1 |
88 | 0 | x2 += x3 >> HWORD_BITS; |
89 | 0 |
|
90 | 0 | // this one can overflow |
91 | 0 | x2 += x1; |
92 | 0 |
|
93 | 0 | // propagate the carry if any |
94 | 0 | x0 += static_cast<uint64_t>(static_cast<bool>(x2 < x1)) << HWORD_BITS; |
95 | 0 |
|
96 | 0 | *hi = x0 + (x2 >> HWORD_BITS); |
97 | 0 | *lo = ((x2 & HWORD_MASK) << HWORD_BITS) + (x3 & HWORD_MASK); |
98 | 0 | #endif |
99 | 0 | } |
100 | | |
101 | | } |
102 | | |
103 | | #endif |