[libc++] Fix sub-overflow in std::gcd implementation (#117984)
Fix #117249
GitOrigin-RevId: f7ff3cde96c4b81b032c58cafee7bf77233f5517
diff --git a/include/__numeric/gcd_lcm.h b/include/__numeric/gcd_lcm.h
index 9be6cf8..f15f64e 100644
--- a/include/__numeric/gcd_lcm.h
+++ b/include/__numeric/gcd_lcm.h
@@ -55,7 +55,8 @@
constexpr _LIBCPP_HIDDEN _Tp __gcd(_Tp __a, _Tp __b) {
static_assert(!is_signed<_Tp>::value, "");
- // From: https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor
+ // Using Binary GCD algorithm https://en.wikipedia.org/wiki/Binary_GCD_algorithm, based on an implementation
+ // from https://lemire.me/blog/2024/04/13/greatest-common-divisor-the-extended-euclidean-algorithm-and-speed/
//
// If power of two divides both numbers, we can push it out.
// - gcd( 2^x * a, 2^x * b) = 2^x * gcd(a, b)
@@ -76,21 +77,17 @@
if (__a == 0)
return __b;
- int __az = std::__countr_zero(__a);
- int __bz = std::__countr_zero(__b);
- int __shift = std::min(__az, __bz);
- __a >>= __az;
- __b >>= __bz;
+ _Tp __c = __a | __b;
+ int __shift = std::__countr_zero(__c);
+ __a >>= std::__countr_zero(__a);
do {
- _Tp __diff = __a - __b;
- if (__a > __b) {
- __a = __b;
- __b = __diff;
+ _Tp __t = __b >> std::__countr_zero(__b);
+ if (__a > __t) {
+ __b = __a - __t;
+ __a = __t;
} else {
- __b = __b - __a;
+ __b = __t - __a;
}
- if (__diff != 0)
- __b >>= std::__countr_zero(__diff);
} while (__b != 0);
return __a << __shift;
}
diff --git a/test/std/numerics/numeric.ops/numeric.ops.gcd/gcd.pass.cpp b/test/std/numerics/numeric.ops/numeric.ops.gcd/gcd.pass.cpp
index 6a9ec1a..975b53a 100644
--- a/test/std/numerics/numeric.ops/numeric.ops.gcd/gcd.pass.cpp
+++ b/test/std/numerics/numeric.ops/numeric.ops.gcd/gcd.pass.cpp
@@ -27,17 +27,7 @@
int x;
int y;
int expect;
-} Cases[] = {
- {0, 0, 0},
- {1, 0, 1},
- {0, 1, 1},
- {1, 1, 1},
- {2, 3, 1},
- {2, 4, 2},
- {36, 17, 1},
- {36, 18, 18}
-};
-
+} 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}};
template <typename Input1, typename Input2, typename Output>
constexpr bool test0(int in1, int in2, int out)