cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

gcd.c (1424B)

      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);