Botan 3.8.1
Crypto and TLS for C&
mul128.h
Go to the documentation of this file.
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#include <botan/internal/target_info.h>
13#include <type_traits>
14
15#if defined(BOTAN_BUILD_COMPILER_IS_MSVC)
16 #include <intrin.h>
17#endif
18
19namespace Botan {
20
21/**
22* Perform a 64x64->128 bit multiplication
23*/
24constexpr inline void mul64x64_128(uint64_t a, uint64_t b, uint64_t* lo, uint64_t* hi) {
25 if(!std::is_constant_evaluated()) {
26#if defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_ARCH_IS_X86_64)
27 *lo = _umul128(a, b, hi);
28 return;
29
30#elif defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_ARCH_IS_ARM64)
31 *lo = a * b;
32 *hi = __umulh(a, b);
33 return;
34#endif
35 }
36
37#if defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
38 const uint128_t r = static_cast<uint128_t>(a) * b;
39 *hi = (r >> 64) & 0xFFFFFFFFFFFFFFFF;
40 *lo = (r) & 0xFFFFFFFFFFFFFFFF;
41#else
42
43 /*
44 * Do a 64x64->128 multiply using four 32x32->64 multiplies plus
45 * some adds and shifts.
46 */
47 const size_t HWORD_BITS = 32;
48 const uint32_t HWORD_MASK = 0xFFFFFFFF;
49
50 const uint32_t a_hi = (a >> HWORD_BITS);
51 const uint32_t a_lo = (a & HWORD_MASK);
52 const uint32_t b_hi = (b >> HWORD_BITS);
53 const uint32_t b_lo = (b & HWORD_MASK);
54
55 const uint64_t x0 = static_cast<uint64_t>(a_hi) * b_hi;
56 const uint64_t x1 = static_cast<uint64_t>(a_lo) * b_hi;
57 const uint64_t x2 = static_cast<uint64_t>(a_hi) * b_lo;
58 const uint64_t x3 = static_cast<uint64_t>(a_lo) * b_lo;
59
60 // this cannot overflow as (2^32-1)^2 + 2^32-1 + 2^32-1 = 2^64-1
61 const uint64_t middle = x2 + (x3 >> HWORD_BITS) + (x1 & HWORD_MASK);
62
63 // likewise these cannot overflow
64 *hi = x0 + (middle >> HWORD_BITS) + (x1 >> HWORD_BITS);
65 *lo = (middle << HWORD_BITS) + (x3 & HWORD_MASK);
66#endif
67}
68
69} // namespace Botan
70
71#endif
constexpr void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)
Definition mul128.h:24