1 // Copyright 2016-2021 Francesco Biscani (bluescarni@gmail.com) 2 // 3 // This file is part of the mp++ library. 4 // 5 // This Source Code Form is subject to the terms of the Mozilla 6 // Public License v. 2.0. If a copy of the MPL was not distributed 7 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 8 9 #include <mp++/config.hpp> 10 11 #include <atomic> 12 #include <cstddef> 13 #include <iostream> 14 #include <limits> 15 #include <random> 16 #include <sstream> 17 #include <stdexcept> 18 #include <string> 19 #include <thread> 20 #include <tuple> 21 #include <type_traits> 22 #include <utility> 23 24 #if defined(MPPP_HAVE_STRING_VIEW) 25 #include <string_view> 26 #endif 27 28 #include <gmp.h> 29 30 #include <mp++/detail/type_traits.hpp> 31 #include <mp++/integer.hpp> 32 33 #include "catch.hpp" 34 #include "test_utils.hpp" 35 36 static const int ntries = 1000; 37 38 // NOLINTNEXTLINE(google-build-using-namespace) 39 using namespace mppp; 40 // NOLINTNEXTLINE(google-build-using-namespace) 41 using namespace mppp_test; 42 43 using int_types = std::tuple<char, signed char, unsigned char, short, unsigned short, int, unsigned, long, 44 unsigned long, long long, unsigned long long, wchar_t 45 #if defined(MPPP_HAVE_GCC_INT128) 46 , 47 __uint128_t, __int128_t 48 #endif 49 >; 50 51 using sizes = std::tuple<std::integral_constant<std::size_t, 1>, std::integral_constant<std::size_t, 2>, 52 std::integral_constant<std::size_t, 3>, std::integral_constant<std::size_t, 6>, 53 std::integral_constant<std::size_t, 10>>; 54 55 // A seed that will be used to init rngs in the multithreaded tests. Each time a batch of N threads 56 // finishes, this value gets bumped up by N, so that the next time a multithreaded test which uses rng 57 // is launched it will be inited with a different seed. 58 // NOLINTNEXTLINE(cppcoreguidelines-avoid-non-const-global-variables) 59 static std::mt19937::result_type mt_rng_seed(0u); 60 61 // NOLINTNEXTLINE(cert-err58-cpp, cert-msc32-c, cert-msc51-cpp, cppcoreguidelines-avoid-non-const-global-variables) 62 static std::mt19937 rng; 63 64 struct no_const { 65 }; 66 67 struct nbits_ctor_tester { 68 template <typename S> operator ()nbits_ctor_tester69 void operator()(const S &) const 70 { 71 using integer = integer<S::value>; 72 REQUIRE((integer{integer_bitcnt_t(0)}.is_static())); 73 REQUIRE((integer{integer_bitcnt_t(0)}.is_zero())); 74 REQUIRE((integer{integer_bitcnt_t(1)}.is_static())); 75 REQUIRE((integer{integer_bitcnt_t(1)}.is_zero())); 76 REQUIRE((integer{integer_bitcnt_t(2)}.is_static())); 77 REQUIRE((integer{integer_bitcnt_t(2)}.is_zero())); 78 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS)}.is_static())); 79 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS)}.is_zero())); 80 if (S::value == 1) { 81 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS + 1)}.is_dynamic())); 82 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS + 1)}.is_zero())); 83 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS + 1)}.get_mpz_t()->_mp_alloc == 2)); 84 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS + 2)}.is_dynamic())); 85 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS + 2)}.is_zero())); 86 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS + 2)}.get_mpz_t()->_mp_alloc == 2)); 87 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * 2)}.is_dynamic())); 88 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * 2)}.is_zero())); 89 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * 2)}.get_mpz_t()->_mp_alloc == 2)); 90 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * 2 + 1)}.is_dynamic())); 91 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * 2 + 1)}.is_zero())); 92 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * 2 + 1)}.get_mpz_t()->_mp_alloc == 3)); 93 } 94 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * S::value)}.is_static())); 95 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * S::value)}.is_zero())); 96 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * S::value + 1)}.is_dynamic())); 97 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * S::value + 1)}.is_zero())); 98 REQUIRE((integer{integer_bitcnt_t(GMP_NUMB_BITS * S::value + 1)}.get_mpz_t()->_mp_alloc == S::value + 1)); 99 } 100 }; 101 102 TEST_CASE("nbits constructor") 103 { 104 tuple_for_each(sizes{}, nbits_ctor_tester{}); 105 } 106 107 struct copy_move_tester { 108 template <typename S> operator ()copy_move_tester109 void operator()(const S &) const 110 { 111 using integer = integer<S::value>; 112 #if MPPP_CPLUSPLUS >= 201402L 113 REQUIRE(std::is_nothrow_move_constructible<integer>::value); 114 #endif 115 integer n; 116 REQUIRE(n.is_static()); 117 n = 123; 118 REQUIRE(n.is_static()); 119 integer m{n}; 120 REQUIRE(n.is_static()); 121 REQUIRE(m.is_static()); 122 REQUIRE(n == 123); 123 REQUIRE(m == 123); 124 m.promote(); 125 REQUIRE(m.is_dynamic()); 126 integer m2{std::move(m)}; 127 REQUIRE(m2.is_dynamic()); 128 // NOLINTNEXTLINE(bugprone-use-after-move, clang-analyzer-cplusplus.Move, hicpp-invalid-access-moved) 129 REQUIRE(m.is_static()); 130 REQUIRE(m == 0); 131 m = 123; 132 integer m3{std::move(m)}; 133 REQUIRE(m3 == 123); 134 // NOLINTNEXTLINE(bugprone-use-after-move, clang-analyzer-cplusplus.Move, hicpp-invalid-access-moved) 135 REQUIRE(m.is_static()); 136 REQUIRE(m3.is_static()); 137 m3.promote(); 138 integer m4{m3}; 139 REQUIRE(m3 == 123); 140 REQUIRE(m4 == 123); 141 REQUIRE(m3.is_dynamic()); 142 REQUIRE(m4.is_dynamic()); 143 m4 = *&m4; 144 REQUIRE(m4.is_dynamic()); 145 REQUIRE(m4 == 123); 146 m4 = std::move(m4); 147 // NOLINTNEXTLINE(bugprone-use-after-move, clang-analyzer-cplusplus.Move, hicpp-invalid-access-moved) 148 REQUIRE(m4.is_dynamic()); 149 REQUIRE(m4 == 123); 150 integer m5{12}, m6{-10}; 151 m5 = m6; 152 REQUIRE(m5.is_static()); 153 REQUIRE(m5 == -10); 154 m5 = m4; 155 REQUIRE(m5.is_dynamic()); 156 REQUIRE(m5 == 123); 157 m4 = m6; 158 REQUIRE(m4.is_static()); 159 REQUIRE(m4 == -10); 160 m4.promote(); 161 m5 = m4; 162 REQUIRE(m5.is_dynamic()); 163 REQUIRE(m5 == -10); 164 m4 = std::move(m5); 165 REQUIRE(m4.is_dynamic()); 166 REQUIRE(m4 == -10); 167 m4 = integer{-1}; 168 REQUIRE(m4.is_static()); 169 REQUIRE(m4 == -1); 170 m4.promote(); 171 m5 = 10; 172 m5.promote(); 173 m4 = std::move(m5); 174 REQUIRE(m4.is_dynamic()); 175 REQUIRE(m4 == 10); 176 // NOLINTNEXTLINE(bugprone-use-after-move, clang-analyzer-cplusplus.Move, hicpp-invalid-access-moved) 177 m5 = -1; 178 m5 = std::move(m4); 179 // NOLINTNEXTLINE(bugprone-use-after-move, clang-analyzer-cplusplus.Move, hicpp-invalid-access-moved) 180 REQUIRE(m4.is_static()); 181 REQUIRE(m4 == 0); 182 REQUIRE(m5.is_dynamic()); 183 REQUIRE(m5 == 10); 184 } 185 }; 186 187 TEST_CASE("copy and move") 188 { 189 tuple_for_each(sizes{}, copy_move_tester{}); 190 } 191 192 struct mpz_copy_ass_tester { 193 template <typename S> operator ()mpz_copy_ass_tester194 void operator()(const S &) const 195 { 196 using integer = integer<S::value>; 197 integer n; 198 detail::mpz_raii m; 199 n = &m.m_mpz; 200 REQUIRE(lex_cast(n) == "0"); 201 mpz_set_si(&m.m_mpz, 1234); 202 n = &m.m_mpz; 203 REQUIRE(n == 1234); 204 mpz_set_si(&m.m_mpz, -1234); 205 n = &m.m_mpz; 206 REQUIRE(n == -1234); 207 mpz_set_str(&m.m_mpz, "3218372891372987328917389127389217398271983712987398127398172389712937819237", 10); 208 n = &m.m_mpz; 209 REQUIRE(n == integer("3218372891372987328917389127389217398271983712987398127398172389712937819237")); 210 mpz_set_str(&m.m_mpz, "-3218372891372987328917389127389217398271983712987398127398172389712937819237", 10); 211 n = &m.m_mpz; 212 REQUIRE(n == integer("-3218372891372987328917389127389217398271983712987398127398172389712937819237")); 213 // Random testing. 214 std::atomic<bool> fail(false); 215 auto f = [&fail](unsigned u) { 216 std::uniform_int_distribution<long> dist(detail::nl_min<long>(), detail::nl_max<long>()); 217 std::uniform_int_distribution<int> sdist(0, 1); 218 std::mt19937 eng(static_cast<std::mt19937::result_type>(u + mt_rng_seed)); 219 for (auto i = 0; i < ntries; ++i) { 220 detail::mpz_raii mpz; 221 auto tmp = dist(eng); 222 mpz_set_si(&mpz.m_mpz, tmp); 223 integer z; 224 if (sdist(eng)) { 225 z.promote(); 226 } 227 z = &mpz.m_mpz; 228 if (z != tmp) { 229 fail.store(false); 230 } 231 } 232 }; 233 std::thread t0(f, 0u), t1(f, 1u), t2(f, 2u), t3(f, 3u); 234 t0.join(); 235 t1.join(); 236 t2.join(); 237 t3.join(); 238 REQUIRE(!fail.load()); 239 mt_rng_seed += 4u; 240 } 241 }; 242 243 TEST_CASE("mpz_t copy assignment") 244 { 245 tuple_for_each(sizes{}, mpz_copy_ass_tester{}); 246 } 247 248 #if !defined(_MSC_VER) 249 250 struct mpz_move_ass_tester { 251 template <typename S> operator ()mpz_move_ass_tester252 void operator()(const S &) const 253 { 254 using integer = integer<S::value>; 255 integer n; 256 ::mpz_t m0; 257 mpz_init(m0); 258 // NOLINTNEXTLINE(hicpp-move-const-arg, performance-move-const-arg) 259 n = std::move(m0); 260 REQUIRE(lex_cast(n) == "0"); 261 mpz_init(m0); 262 mpz_set_si(m0, 1234); 263 // NOLINTNEXTLINE(hicpp-move-const-arg, performance-move-const-arg) 264 n = std::move(m0); 265 REQUIRE(n == 1234); 266 mpz_init(m0); 267 mpz_set_si(m0, -1234); 268 // NOLINTNEXTLINE(hicpp-move-const-arg, performance-move-const-arg) 269 n = std::move(m0); 270 REQUIRE(n == -1234); 271 mpz_init(m0); 272 mpz_set_str(m0, "3218372891372987328917389127389217398271983712987398127398172389712937819237", 10); 273 // NOLINTNEXTLINE(hicpp-move-const-arg, performance-move-const-arg) 274 n = std::move(m0); 275 REQUIRE(n == integer("3218372891372987328917389127389217398271983712987398127398172389712937819237")); 276 mpz_init(m0); 277 mpz_set_str(m0, "-3218372891372987328917389127389217398271983712987398127398172389712937819237", 10); 278 // NOLINTNEXTLINE(hicpp-move-const-arg, performance-move-const-arg) 279 n = std::move(m0); 280 REQUIRE(n == integer("-3218372891372987328917389127389217398271983712987398127398172389712937819237")); 281 // Random testing. 282 std::atomic<bool> fail(false); 283 auto f = [&fail](unsigned u) { 284 std::uniform_int_distribution<long> dist(detail::nl_min<long>(), detail::nl_max<long>()); 285 std::uniform_int_distribution<int> sdist(0, 1); 286 std::mt19937 eng(static_cast<std::mt19937::result_type>(u + mt_rng_seed)); 287 for (auto i = 0; i < ntries; ++i) { 288 ::mpz_t m1; 289 mpz_init(m1); 290 auto tmp = dist(eng); 291 mpz_set_si(m1, tmp); 292 integer z; 293 if (sdist(eng)) { 294 z.promote(); 295 } 296 // NOLINTNEXTLINE(hicpp-move-const-arg, performance-move-const-arg) 297 z = std::move(m1); 298 if (z != tmp) { 299 fail.store(false); 300 } 301 } 302 }; 303 std::thread t0(f, 0u), t1(f, 1u), t2(f, 2u), t3(f, 3u); 304 t0.join(); 305 t1.join(); 306 t2.join(); 307 t3.join(); 308 REQUIRE(!fail.load()); 309 mt_rng_seed += 4u; 310 } 311 }; 312 313 TEST_CASE("mpz_t move assignment") 314 { 315 tuple_for_each(sizes{}, mpz_move_ass_tester{}); 316 } 317 318 #endif 319 320 struct string_ass_tester { 321 template <typename S> operator ()string_ass_tester322 void operator()(const S &) const 323 { 324 using integer = integer<S::value>; 325 integer n; 326 n = "123"; 327 REQUIRE(n == 123); 328 n = " -456 "; 329 REQUIRE(n == -456); 330 n = std::string("123"); 331 REQUIRE(n == 123); 332 n = std::string(" -456 "); 333 REQUIRE(n == -456); 334 REQUIRE_THROWS_PREDICATE(n = "", std::invalid_argument, [](const std::invalid_argument &ia) { 335 return std::string(ia.what()) == "The string '' is not a valid integer in base 10"; 336 }); 337 #if defined(MPPP_HAVE_STRING_VIEW) 338 n = std::string_view(" -123 "); 339 REQUIRE(n == -123); 340 n = std::string_view("4563 "); 341 REQUIRE(n == 4563); 342 REQUIRE_THROWS_PREDICATE(n = std::string_view(""), std::invalid_argument, [](const std::invalid_argument &ia) { 343 return std::string(ia.what()) == "The string '' is not a valid integer in base 10"; 344 }); 345 #endif 346 } 347 }; 348 349 TEST_CASE("string assignment") 350 { 351 tuple_for_each(sizes{}, string_ass_tester{}); 352 } 353 354 struct promdem_tester { 355 template <typename S> operator ()promdem_tester356 void operator()(const S &) const 357 { 358 using integer = integer<S::value>; 359 integer n; 360 REQUIRE(n.promote()); 361 REQUIRE(n.sgn() == 0); 362 REQUIRE(n.is_dynamic()); 363 REQUIRE(!n.promote()); 364 REQUIRE(n.demote()); 365 REQUIRE(n.sgn() == 0); 366 REQUIRE(n.is_static()); 367 REQUIRE(!n.demote()); 368 n = -5; 369 REQUIRE(n.promote()); 370 REQUIRE(n == -5); 371 REQUIRE(n.is_dynamic()); 372 REQUIRE(!n.promote()); 373 REQUIRE(n.demote()); 374 REQUIRE(n == -5); 375 REQUIRE(n.is_static()); 376 REQUIRE(!n.demote()); 377 n = integer{"312321983721983791287392817328917398217398712938719273981273"}; 378 if (n.size() > S::value) { 379 REQUIRE(n.is_dynamic()); 380 REQUIRE(!n.demote()); 381 REQUIRE(n.is_dynamic()); 382 } 383 } 384 }; 385 386 TEST_CASE("promote and demote") 387 { 388 tuple_for_each(sizes{}, promdem_tester{}); 389 } 390 391 struct sign_tester { 392 template <typename S> operator ()sign_tester393 void operator()(const S &) const 394 { 395 using integer = integer<S::value>; 396 integer n; 397 REQUIRE(n.sgn() == 0); 398 REQUIRE(sgn(n) == 0); 399 n.promote(); 400 REQUIRE(n.sgn() == 0); 401 REQUIRE(sgn(n) == 0); 402 n = 12; 403 REQUIRE(n.sgn() == 1); 404 REQUIRE(sgn(n) == 1); 405 n.promote(); 406 REQUIRE(n.sgn() == 1); 407 REQUIRE(sgn(n) == 1); 408 n = -34; 409 REQUIRE(n.sgn() == -1); 410 REQUIRE(sgn(n) == -1); 411 n.promote(); 412 REQUIRE(n.sgn() == -1); 413 REQUIRE(sgn(n) == -1); 414 } 415 }; 416 417 TEST_CASE("sign") 418 { 419 tuple_for_each(sizes{}, sign_tester{}); 420 } 421 422 struct to_string_tester { 423 template <typename S> operator ()to_string_tester424 void operator()(const S &) const 425 { 426 using integer = integer<S::value>; 427 REQUIRE(integer{}.to_string() == "0"); 428 REQUIRE(integer{1}.to_string() == "1"); 429 REQUIRE(integer{-1}.to_string() == "-1"); 430 REQUIRE(integer{123}.to_string() == "123"); 431 REQUIRE(integer{-123}.to_string() == "-123"); 432 REQUIRE(integer{123}.to_string(3) == "11120"); 433 REQUIRE(integer{-123}.to_string(3) == "-11120"); 434 REQUIRE_THROWS_PREDICATE((integer{}.to_string(1)), std::invalid_argument, [](const std::invalid_argument &ia) { 435 return std::string(ia.what()) 436 == "Invalid base for string conversion: the base must be between " 437 "2 and 62, but a value of 1 was provided instead"; 438 }); 439 REQUIRE_THROWS_PREDICATE((integer{}.to_string(-12)), std::invalid_argument, 440 [](const std::invalid_argument &ia) { 441 return std::string(ia.what()) 442 == "Invalid base for string conversion: the base must be between " 443 "2 and 62, but a value of -12 was provided instead"; 444 }); 445 REQUIRE_THROWS_PREDICATE((integer{}.to_string(63)), std::invalid_argument, [](const std::invalid_argument &ia) { 446 return std::string(ia.what()) 447 == "Invalid base for string conversion: the base must be between " 448 "2 and 62, but a value of 63 was provided instead"; 449 }); 450 } 451 }; 452 453 TEST_CASE("to_string") 454 { 455 tuple_for_each(sizes{}, to_string_tester{}); 456 } 457 458 struct stream_tester { 459 template <typename S> operator ()stream_tester460 void operator()(const S &) const 461 { 462 using integer = integer<S::value>; 463 { 464 std::ostringstream oss; 465 oss << integer{}; 466 REQUIRE(oss.str() == "0"); 467 } 468 { 469 std::ostringstream oss; 470 oss << integer{123}; 471 REQUIRE(oss.str() == "123"); 472 } 473 { 474 std::ostringstream oss; 475 oss << integer{-123}; 476 REQUIRE(oss.str() == "-123"); 477 } 478 } 479 }; 480 481 TEST_CASE("stream") 482 { 483 tuple_for_each(sizes{}, stream_tester{}); 484 } 485