[M] Change in coreboot[main]: lib: Add GCD function

[Yidi Lin (Code Review)]

Yidi Lin has uploaded this change for review. ( https://review.coreboot.org/c/coreboot/+/78798?usp=email )

Change subject: lib: Add GCD function
......................................................................

lib: Add GCD function

Port GCD (greatest common divisor) function from Linux kernel.

BUG=b:307790895
TEST=emerge-geralt coreboot

Change-Id: I21819cda4299b3809b8ca7a95cbdc6a87e4b3481
Signed-off-by: Yidi Lin 
---
A src/include/gcd.h
M src/lib/Makefile.inc
A src/lib/gcd.c
3 files changed, 58 insertions(+), 1 deletion(-)

git pull ssh://review.coreboot.org:29418/coreboot refs/changes/98/78798/1

diff --git a/src/include/gcd.h b/src/include/gcd.h
new file mode 100644
index 0000000..7b10502
--- /dev/null
+++ b/src/include/gcd.h
@@ -0,0 +1,7 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+#ifndef __GCD_H__
+#define __GCD_H__
+
+unsigned long gcd(unsigned long a, unsigned long b);
+
+#endif /* _GCD_H */
diff --git a/src/lib/Makefile.inc b/src/lib/Makefile.inc
index 53ff2d3..1eebdba 100644
--- a/src/lib/Makefile.inc
+++ b/src/lib/Makefile.inc
@@ -28,7 +28,7 @@
 $(obj)/ramstage/lib/asan.o: CFLAGS_asan =
 endif

-all-y += list.c
+all-y += gcd.c list.c

decompressor-y += decompressor.c
 $(call src-to-obj,decompressor,$(dir)/decompressor.c): $(objcbfs)/bootblock.lz4
diff --git a/src/lib/gcd.c b/src/lib/gcd.c
new file mode 100644
index 0000000..fdef6ec
--- /dev/null
+++ b/src/lib/gcd.c
@@ -0,0 +1,50 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#include <gcd.h>
+#include <lib.h>
+
+/*
+ * This implements the binary GCD algorithm. (Often attributed to Stein,
+ * but as Knuth has noted, appears in a first-century Chinese math text.)
+ *
+ * This is faster than the division-based algorithm even on x86, which
+ * has decent hardware division.
+ */
+
+static void swap(unsigned long *a, unsigned long *b)
+{
+	if (*a == *b || a == b)
+		return;
+	*a ^= *b;
+	*b ^= *a;
+	*a ^= *b;
+}
+
+/**
+ * gcd - calculate and return the greatest common divisor of 2 unsigned longs
+ * @a: first value
+ * @b: second value
+ */
+unsigned long gcd(unsigned long a, unsigned long b)
+{
+	unsigned long r = a | b;
+
+	if (!a || !b)
+		return r;
+
+	b >>= __ffs(b);
+	if (b == 1)
+		return r & -r;
+
+	for (;;) {
+		a >>= __ffs(a);
+		if (a == 1)
+			return r & -r;
+		if (a == b)
+			return a << __ffs(r);
+
+		if (a < b)
+			swap(&a, &b);
+		a -= b;
+	}
+}