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