LXR linux/lib/math/gcd.c

   1// SPDX-License-Identifier: GPL-2.0-only
   2#include <linux/kernel.h>
   3#include <linux/gcd.h>
   4#include <linux/export.h>
   5
   6/*
   7 * This implements the binary GCD algorithm. (Often attributed to Stein,
   8 * but as Knuth has noted, appears in a first-century Chinese math text.)
   9 *
  10 * This is faster than the division-based algorithm even on x86, which
  11 * has decent hardware division.
  12 */
  13
  14#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
  15
  16/* If __ffs is available, the even/odd algorithm benchmarks slower. */
  17
  18/**
  19 * gcd - calculate and return the greatest common divisor of 2 unsigned longs
  20 * @a: first value
  21 * @b: second value
  22 */
  23unsigned long gcd(unsigned long a, unsigned long b)
  24{
  25        unsigned long r = a | b;
  26
  27        if (!a || !b)
  28                return r;
  29
  30        b >>= __ffs(b);
  31        if (b == 1)
  32                return r & -r;
  33
  34        for (;;) {
  35                a >>= __ffs(a);
  36                if (a == 1)
  37                        return r & -r;
  38                if (a == b)
  39                        return a << __ffs(r);
  40
  41                if (a < b)
  42                        swap(a, b);
  43                a -= b;
  44        }
  45}
  46
  47#else
  48
  49/* If normalization is done by loops, the even/odd algorithm is a win. */
  50unsigned long gcd(unsigned long a, unsigned long b)
  51{
  52        unsigned long r = a | b;
  53
  54        if (!a || !b)
  55                return r;
  56
  57        /* Isolate lsbit of r */
  58        r &= -r;
  59
  60        while (!(b & r))
  61                b >>= 1;
  62        if (b == r)
  63                return r;
  64
  65        for (;;) {
  66                while (!(a & r))
  67                        a >>= 1;
  68                if (a == r)
  69                        return r;
  70                if (a == b)
  71                        return a;
  72
  73                if (a < b)
  74                        swap(a, b);
  75                a -= b;
  76                a >>= 1;
  77                if (a & r)
  78                        a += b;
  79                a >>= 1;
  80        }
  81}
  82
  83#endif
  84
  85EXPORT_SYMBOL_GPL(gcd);
  86