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