diff options
Diffstat (limited to 'libavutil/mathematics.c')
| -rw-r--r-- | libavutil/mathematics.c | 26 |
1 files changed, 21 insertions, 5 deletions
diff --git a/libavutil/mathematics.c b/libavutil/mathematics.c index 252794e460..16e4eba5b9 100644 --- a/libavutil/mathematics.c +++ b/libavutil/mathematics.c @@ -27,16 +27,32 @@ #include <limits.h> #include "mathematics.h" +#include "libavutil/intmath.h" #include "libavutil/common.h" #include "avassert.h" #include "version.h" -int64_t av_gcd(int64_t a, int64_t b) -{ - if (b) - return av_gcd(b, a % b); - else +/* Stein's binary GCD algorithm: + * https://en.wikipedia.org/wiki/Binary_GCD_algorithm */ +int64_t av_gcd(int64_t a, int64_t b) { + int za, zb, k; + int64_t u, v; + if (a == 0) + return b; + if (b == 0) return a; + za = ff_ctzll(a); + zb = ff_ctzll(b); + k = FFMIN(za, zb); + u = llabs(a >> za); + v = llabs(b >> zb); + while (u != v) { + if (u > v) + FFSWAP(int64_t, v, u); + v -= u; + v >>= ff_ctzll(v); + } + return u << k; } int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd) |