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