1 // Copyright (C) 2020-2021 Intel Corporation
2 // SPDX-License-Identifier: Apache-2.0
3
4 #pragma once
5 #include <cmath>
6
7 #include "hexl/util/check.hpp"
8 #include "hexl/util/types.hpp"
9
10 namespace intel {
11 namespace hexl {
12
13 #ifdef HEXL_USE_CLANG
14 // Return x * y as 128-bit integer
15 // Correctness if x * y < 128 bits
MultiplyUInt64(uint64_t x,uint64_t y)16 inline uint128_t MultiplyUInt64(uint64_t x, uint64_t y) {
17 return uint128_t(x) * uint128_t(y);
18 }
19
BarrettReduce128(uint64_t input_hi,uint64_t input_lo,uint64_t modulus)20 inline uint64_t BarrettReduce128(uint64_t input_hi, uint64_t input_lo,
21 uint64_t modulus) {
22 HEXL_CHECK(modulus != 0, "modulus == 0")
23 uint128_t n = (static_cast<uint128_t>(input_hi) << 64) |
24 (static_cast<uint128_t>(input_lo));
25
26 return n % modulus;
27 // TODO(fboemer): actually use barrett reduction if performance-critical
28 }
29
30 // Returns low 64bit of 128b/64b where x1=high 64b, x0=low 64b
DivideUInt128UInt64Lo(uint64_t x1,uint64_t x0,uint64_t y)31 inline uint64_t DivideUInt128UInt64Lo(uint64_t x1, uint64_t x0, uint64_t y) {
32 uint128_t n =
33 (static_cast<uint128_t>(x1) << 64) | (static_cast<uint128_t>(x0));
34 uint128_t q = n / y;
35
36 return static_cast<uint64_t>(q);
37 }
38
39 // Multiplies x * y as 128-bit integer.
40 // @param prod_hi Stores high 64 bits of product
41 // @param prod_lo Stores low 64 bits of product
MultiplyUInt64(uint64_t x,uint64_t y,uint64_t * prod_hi,uint64_t * prod_lo)42 inline void MultiplyUInt64(uint64_t x, uint64_t y, uint64_t* prod_hi,
43 uint64_t* prod_lo) {
44 uint128_t prod = MultiplyUInt64(x, y);
45 *prod_hi = static_cast<uint64_t>(prod >> 64);
46 *prod_lo = static_cast<uint64_t>(prod);
47 }
48
49 // Return the high 128 minus BitShift bits of the 128-bit product x * y
50 template <int BitShift>
MultiplyUInt64Hi(uint64_t x,uint64_t y)51 inline uint64_t MultiplyUInt64Hi(uint64_t x, uint64_t y) {
52 uint128_t product = static_cast<uint128_t>(x) * y;
53 return static_cast<uint64_t>(product >> BitShift);
54 }
55
56 // Returns most-significant bit of the input
MSB(uint64_t input)57 inline uint64_t MSB(uint64_t input) {
58 return static_cast<uint64_t>(std::log2l(input));
59 }
60
61 #define HEXL_LOOP_UNROLL_4 _Pragma("clang loop unroll_count(4)")
62 #define HEXL_LOOP_UNROLL_8 _Pragma("clang loop unroll_count(8)")
63
64 #endif
65
66 } // namespace hexl
67 } // namespace intel
68