1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // UNSUPPORTED: c++03, c++11, c++14 10 11 // <numeric> 12 13 // template<class _M, class _N> 14 // constexpr common_type_t<_M,_N> gcd(_M __m, _N __n) 15 16 #include <numeric> 17 #include <cassert> 18 #include <climits> 19 #include <cstdint> 20 #include <limits> 21 #include <random> 22 #include <type_traits> 23 24 #include "test_macros.h" 25 26 constexpr struct { 27 int x; 28 int y; 29 int expect; 30 } Cases[] = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {1, 1, 1}, {2, 3, 1}, {2, 4, 2}, {11, 9, 1}, {36, 17, 1}, {36, 18, 18}}; 31 32 template <typename Input1, typename Input2, typename Output> 33 constexpr bool test0(int in1, int in2, int out) 34 { 35 auto value1 = static_cast<Input1>(in1); 36 auto value2 = static_cast<Input2>(in2); 37 static_assert(std::is_same_v<Output, decltype(std::gcd(value1, value2))>, ""); 38 static_assert(std::is_same_v<Output, decltype(std::gcd(value2, value1))>, ""); 39 assert(static_cast<Output>(out) == std::gcd(value1, value2)); 40 return true; 41 } 42 43 template <typename T> 44 T basic_gcd_(T m, T n) { 45 return n == 0 ? m : basic_gcd_<T>(n, m % n); 46 } 47 48 template <typename T> 49 T basic_gcd(T m, T n) { 50 using Tp = std::make_unsigned_t<T>; 51 if constexpr (std::is_signed_v<T>) { 52 if (m < 0 && m != std::numeric_limits<T>::min()) 53 m = -m; 54 if (n < 0 && n != std::numeric_limits<T>::min()) 55 n = -n; 56 } 57 return basic_gcd_(static_cast<Tp>(m), static_cast<Tp>(n)); 58 } 59 60 template <typename Input> 61 void do_fuzzy_tests() { 62 std::mt19937 gen(1938); 63 using DistIntType = std::conditional_t<sizeof(Input) == 1, int, Input>; // See N4981 [rand.req.genl]/1.5 64 constexpr Input max_input = std::numeric_limits<Input>::max(); 65 std::uniform_int_distribution<DistIntType> distrib(0, max_input); 66 67 constexpr int nb_rounds = 10000; 68 for (int i = 0; i < nb_rounds; ++i) { 69 Input n = static_cast<Input>(distrib(gen)); 70 Input m = static_cast<Input>(distrib(gen)); 71 assert(std::gcd(n, m) == basic_gcd(n, m)); 72 } 73 } 74 75 template <typename Input> 76 void do_limit_tests() { 77 Input inputs[] = { 78 // The behavior of std::gcd is undefined if the absolute value of one of its 79 // operand is not representable in the result type. 80 std::numeric_limits<Input>::min() + (std::is_signed<Input>::value ? 3 : 0), 81 std::numeric_limits<Input>::min() + 1, 82 std::numeric_limits<Input>::min() + 2, 83 std::numeric_limits<Input>::max(), 84 std::numeric_limits<Input>::max() - 1, 85 std::numeric_limits<Input>::max() - 2, 86 0, 87 1, 88 2, 89 3, 90 4, 91 5, 92 6, 93 7, 94 8, 95 9, 96 10, 97 (Input)-1, 98 (Input)-2, 99 (Input)-3, 100 (Input)-4, 101 (Input)-5, 102 (Input)-6, 103 (Input)-7, 104 (Input)-8, 105 (Input)-9, 106 (Input)-10, 107 }; 108 109 for (auto n : inputs) { 110 for (auto m : inputs) { 111 assert(std::gcd(n, m) == basic_gcd(n, m)); 112 } 113 } 114 } 115 116 template <typename Input1, typename Input2 = Input1> 117 constexpr bool do_test(int = 0) 118 { 119 using S1 = std::make_signed_t<Input1>; 120 using S2 = std::make_signed_t<Input2>; 121 using U1 = std::make_unsigned_t<Input1>; 122 using U2 = std::make_unsigned_t<Input2>; 123 bool accumulate = true; 124 for (auto TC : Cases) { 125 { // Test with two signed types 126 using Output = std::common_type_t<S1, S2>; 127 accumulate &= test0<S1, S2, Output>(TC.x, TC.y, TC.expect); 128 accumulate &= test0<S1, S2, Output>(-TC.x, TC.y, TC.expect); 129 accumulate &= test0<S1, S2, Output>(TC.x, -TC.y, TC.expect); 130 accumulate &= test0<S1, S2, Output>(-TC.x, -TC.y, TC.expect); 131 accumulate &= test0<S2, S1, Output>(TC.x, TC.y, TC.expect); 132 accumulate &= test0<S2, S1, Output>(-TC.x, TC.y, TC.expect); 133 accumulate &= test0<S2, S1, Output>(TC.x, -TC.y, TC.expect); 134 accumulate &= test0<S2, S1, Output>(-TC.x, -TC.y, TC.expect); 135 } 136 { // test with two unsigned types 137 using Output = std::common_type_t<U1, U2>; 138 accumulate &= test0<U1, U2, Output>(TC.x, TC.y, TC.expect); 139 accumulate &= test0<U2, U1, Output>(TC.x, TC.y, TC.expect); 140 } 141 { // Test with mixed signs 142 using Output = std::common_type_t<S1, U2>; 143 accumulate &= test0<S1, U2, Output>(TC.x, TC.y, TC.expect); 144 accumulate &= test0<U2, S1, Output>(TC.x, TC.y, TC.expect); 145 accumulate &= test0<S1, U2, Output>(-TC.x, TC.y, TC.expect); 146 accumulate &= test0<U2, S1, Output>(TC.x, -TC.y, TC.expect); 147 } 148 { // Test with mixed signs 149 using Output = std::common_type_t<S2, U1>; 150 accumulate &= test0<S2, U1, Output>(TC.x, TC.y, TC.expect); 151 accumulate &= test0<U1, S2, Output>(TC.x, TC.y, TC.expect); 152 accumulate &= test0<S2, U1, Output>(-TC.x, TC.y, TC.expect); 153 accumulate &= test0<U1, S2, Output>(TC.x, -TC.y, TC.expect); 154 } 155 } 156 return accumulate; 157 } 158 159 int main(int argc, char**) 160 { 161 int non_cce = argc; // a value that can't possibly be constexpr 162 163 static_assert(do_test<signed char>(), ""); 164 static_assert(do_test<short>(), ""); 165 static_assert(do_test<int>(), ""); 166 static_assert(do_test<long>(), ""); 167 static_assert(do_test<long long>(), ""); 168 169 assert(do_test<signed char>(non_cce)); 170 assert(do_test<short>(non_cce)); 171 assert(do_test<int>(non_cce)); 172 assert(do_test<long>(non_cce)); 173 assert(do_test<long long>(non_cce)); 174 175 static_assert(do_test<std::int8_t>(), ""); 176 static_assert(do_test<std::int16_t>(), ""); 177 static_assert(do_test<std::int32_t>(), ""); 178 static_assert(do_test<std::int64_t>(), ""); 179 180 assert(do_test<std::int8_t>(non_cce)); 181 assert(do_test<std::int16_t>(non_cce)); 182 assert(do_test<std::int32_t>(non_cce)); 183 assert(do_test<std::int64_t>(non_cce)); 184 185 static_assert(do_test<signed char, int>(), ""); 186 static_assert(do_test<int, signed char>(), ""); 187 static_assert(do_test<short, int>(), ""); 188 static_assert(do_test<int, short>(), ""); 189 static_assert(do_test<int, long>(), ""); 190 static_assert(do_test<long, int>(), ""); 191 static_assert(do_test<int, long long>(), ""); 192 static_assert(do_test<long long, int>(), ""); 193 194 assert((do_test<signed char, int>(non_cce))); 195 assert((do_test<int, signed char>(non_cce))); 196 assert((do_test<short, int>(non_cce))); 197 assert((do_test<int, short>(non_cce))); 198 assert((do_test<int, long>(non_cce))); 199 assert((do_test<long, int>(non_cce))); 200 assert((do_test<int, long long>(non_cce))); 201 assert((do_test<long long, int>(non_cce))); 202 203 // LWG#2837 204 { 205 auto res = std::gcd(static_cast<std::int64_t>(1234), INT32_MIN); 206 static_assert(std::is_same_v<decltype(res), std::int64_t>, ""); 207 assert(res == 2); 208 } 209 210 do_fuzzy_tests<std::int8_t>(); 211 do_fuzzy_tests<std::int16_t>(); 212 do_fuzzy_tests<std::int32_t>(); 213 do_fuzzy_tests<std::int64_t>(); 214 do_fuzzy_tests<std::uint8_t>(); 215 do_fuzzy_tests<std::uint16_t>(); 216 do_fuzzy_tests<std::uint32_t>(); 217 do_fuzzy_tests<std::uint64_t>(); 218 219 do_limit_tests<std::int8_t>(); 220 do_limit_tests<std::int16_t>(); 221 do_limit_tests<std::int32_t>(); 222 do_limit_tests<std::int64_t>(); 223 do_limit_tests<std::uint8_t>(); 224 do_limit_tests<std::uint16_t>(); 225 do_limit_tests<std::uint32_t>(); 226 do_limit_tests<std::uint64_t>(); 227 228 return 0; 229 } 230