Botan 3.0.0
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
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
22namespace 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*/
38inline void mul64x64_128(uint64_t a, uint64_t b, uint64_t* lo, uint64_t* hi)
39 {
40#if defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
41
42 const uint128_t r = static_cast<uint128_t>(a) * b;
43 *hi = (r >> 64) & 0xFFFFFFFFFFFFFFFF;
44 *lo = (r ) & 0xFFFFFFFFFFFFFFFF;
45
46#elif defined(BOTAN_BUILD_COMPILER_IS_MSVC) && defined(BOTAN_TARGET_CPU_HAS_NATIVE_64BIT)
47 #if defined(_M_ARM64)
48 *lo = a * b;
49 *hi = __umulh(a, b);
50 #else
51 *lo = _umul128(a, b, hi);
52 #endif
53
54#elif defined(BOTAN_USE_GCC_INLINE_ASM) && defined(BOTAN_TARGET_ARCH_IS_X86_64)
55 asm("mulq %3"
56 : "=d" (*hi), "=a" (*lo)
57 : "a" (a), "rm" (b)
58 : "cc");
59
60#elif defined(BOTAN_USE_GCC_INLINE_ASM) && defined(BOTAN_TARGET_ARCH_IS_PPC64)
61 asm("mulhdu %0,%1,%2"
62 : "=r" (*hi)
63 : "r" (a), "r" (b)
64 : "cc");
65 *lo = a * b;
66
67#else
68
69 /*
70 * Do a 64x64->128 multiply using four 32x32->64 multiplies plus
71 * some adds and shifts. Last resort for CPUs like UltraSPARC (with
72 * 64-bit registers/ALU, but no 64x64->128 multiply) or 32-bit CPUs.
73 */
74 const size_t HWORD_BITS = 32;
75 const uint32_t HWORD_MASK = 0xFFFFFFFF;
76
77 const uint32_t a_hi = (a >> HWORD_BITS);
78 const uint32_t a_lo = (a & HWORD_MASK);
79 const uint32_t b_hi = (b >> HWORD_BITS);
80 const uint32_t b_lo = (b & HWORD_MASK);
81
82 uint64_t x0 = static_cast<uint64_t>(a_hi) * b_hi;
83 uint64_t x1 = static_cast<uint64_t>(a_lo) * b_hi;
84 uint64_t x2 = static_cast<uint64_t>(a_hi) * b_lo;
85 uint64_t x3 = static_cast<uint64_t>(a_lo) * b_lo;
86
87 // this cannot overflow as (2^32-1)^2 + 2^32-1 < 2^64-1
88 x2 += x3 >> HWORD_BITS;
89
90 // this one can overflow
91 x2 += x1;
92
93 // propagate the carry if any
94 x0 += static_cast<uint64_t>(static_cast<bool>(x2 < x1)) << HWORD_BITS;
95
96 *hi = x0 + (x2 >> HWORD_BITS);
97 *lo = ((x2 & HWORD_MASK) << HWORD_BITS) + (x3 & HWORD_MASK);
98#endif
99 }
100
101}
102
103#endif
Definition: alg_id.cpp:12
void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)
Definition: mul128.h:38