Open bitlush opened 5 years ago
Hi Keith / @bitlush ,
Thank you for your interest in the project! I've never tried compiling with MS's Visual Studio, nor do I have windows/Visual Studio... Would you be interested in contributing, e.g., by sending a pull request?
__uint128_t is indeed a clang/gcc-only thing. Do you know whether MS has something like that? Probably, some macros (or constexpr-if) can help here to switch this case off for the MS compiler. BTW, even if MS does not provide a 128-bit type, then as a workaround you can use the big-ints with 32-bit limbs, since most of the code is templated on the limb type, or I can define a dedicated 64x64bit mul function. (I already did that once, but removed it some time ago)
Regarding the always inline, this should probably be "__forceinline" for Visual Studio, a macro should then choose between the GNU and Microsoft pragma based on the detected compiler.
Regarding:
explicit operator auto() const { return data; }
I am not sure if I actually use that somewhere. Does the following (explicitly spelling the type to the compiler) compile?
explicit operator big_int<sizeof...(Modulus), T>() const { return data; }
The error with:
constexpr auto ext_gcd(std::integer_sequence<T, A...>,
std::integer_sequence<T, B...>)
must have been caused by the Is
template parameter pack, which did not serve any purpose (it probably originated from some copy pasting from ext_gcd_impl
), but neither clang nor gcc complained about it. I have already removed that.
I'll fork and create a pull request as I've managed to get the bits I've tried compiling. I've also had to sprinkle a few static_casts around the code to remove compiler warnings. I also use Clang and AppleClang as well so I can easily do a regression on those.
Great work by the way, this is a wonderful library.
Great! I'd be very interested to see where exactly those static_casts are needed.
BTW The old multiplication code (circumventing __uint128_t ) can be found commit: fba16e2ef5b908a33cd198fb
@bitlush,
I discovered that in type_traits.hpp
, the specialization of dbl_bitlen
for unsigned long
interfered with that of uint64_t
, so I commented-out the former, see commit 1223979
@niekbouman, OK thanks for the heads up. It'll be a day or two before I can check my changes through as the tests are problematic under MSVC.
I'm going to propose using the following to fix the missing 128-bit integers in type_traits.hpp
:
#if defined(_MSC_VER)
using default_limb_t = uint32_t;
#else
using default_limb_t = uint64_t;
#endif
And then I can update all templates like so:
template <size_t N, typename T = default_limb_t,
typename = std::enable_if_t<std::is_integral<T>::value>>
struct big_int : std::array<T, N> {};
If you've got a view on this approach, please let me know, I'm not overly convinced it's a great way to go.
I'm undecided if a better approach is to actually use a zero abstraction wrapper for limb data types i.e. limb8_t
, limb32_t
, limb64_t
which would overload the maths operations, provide a better route to fix all the overflow warnings in MSVC by keeping the code free of static_cast
fixes, allow limb64_t
to use platform specific code for multiplications etc when 128-bit integers don't exist, but it's a lot of work and adds more code and complexity.
After some more thought, I think the simplest approach is to provide a custom implementation of 128 integers for non-supporting platforms so that enough of __uint128_t
would need implementing for the library to work.
I haven't spent enough time understanding the compiler warnings to have a strong view on the cleanest way to avoid them.
With respect to 128-bit arithmetic, the following seems to be useful, i.e., an 128-bit multiply intrinsic for MS Visual C++: https://docs.microsoft.com/en-gb/cpp/intrinsics/mul128?view=vs-2017
However, double-word (128bit) addition is also needed, because of line 53 in the mul
function:
TT t = static_cast<TT>(u[i]) * static_cast<TT>(v[j]) + w[i + j] + k;
what is used here, is that if you multiply two unsigned operands A and B that can maximally be 2^{64}-1, then there is room left for adding two extra unsigned operands C and D to the result, where C and D can also maximally be 2^{64}-1. Maybe there is also an intrinsic for that (or we can simply use the addition function defined in add.hpp for this purpose)
Hi Keith @bitlush ,
Any luck so far getting the code to run on MSVC?
best, Niek
A couple of problems when compiling in MSVC (latest version)
Compiler errors:
Severity Code Description Project File Line Suppression State Error C3177 you cannot have a conversion function to a type that contains 'auto' ctbignum\field.hpp 29
Severity Code Description Project File Line Suppression State Error C3547 template parameter 'Is' cannot be used because it follows a template parameter pack and cannot be deduced from the function parameters of 'cbn::ext_gcd' dsapp ctbignum\gcd.hpp 69
Incompatible features
define CBN_ALWAYS_INLINE [[gnu::always_inline]] in config.hpp
template <> struct dbl_bitlen { using type = uint128_t; };
template <> struct dbl_bitlen { using type = uint128_t; };
in type_traits.hpp