[PATCH] lib/gcd: Convert to Rust

[PATCH] lib/gcd: Convert to Rust

[Raymond Newman]

From 96902ad2caf167ca0377e0b2063973e2183465b4 Mon Sep 17 00:00:00 2001
From: Raymond Newman <raymondcharlesnewman@gmail.com>
Date: Tue, 5 May 2026 21:29:29 -0400
Subject: [PATCH] lib/gcd: Convert to Rust

Convert lib/math/gcd.c to Rust. The binary GCD algorithm is preserved
exactly, including both the efficient-ffs fast path and the even/odd
fallback for CONFIG_CPU_NO_EFFICIENT_FFS targets.

__ffs() is replaced with trailing_zeros(), which maps to the same
hardware instruction. swap() is replaced with core::mem::swap().
Unary negation for the bitmask isolation trick is replaced with
wrapping_neg() to make the intentional wrapping behavior explicit.

ABI compatibility is preserved via #[no_mangle] pub extern "C".

Signed-off-by: Raymond Newman <raymondcharlesnewman@gmail.com>
---
 Documentation/core-api/kernel-api.rst         |   2 +-
 .../zh_CN/core-api/kernel-api.rst             |   2 +-
 lib/math/gcd.c                                |  88 ---------------
 lib/math/gcd.rs                               | 103 ++++++++++++++++++
 4 files changed, 105 insertions(+), 90 deletions(-)
 delete mode 100644 lib/math/gcd.c
 create mode 100644 lib/math/gcd.rs

diff --git a/Documentation/core-api/kernel-api.rst
b/Documentation/core-api/kernel-api.rst
index e8211c4ca..fff8ecc47 100644
--- a/Documentation/core-api/kernel-api.rst
+++ b/Documentation/core-api/kernel-api.rst
@@ -178,7 +178,7 @@ Division Functions
 .. kernel-doc:: include/linux/math64.h
    :internal:

-.. kernel-doc:: lib/math/gcd.c
+.. kernel-doc:: lib/math/gcd.rs
    :export:

 UUID/GUID
diff --git a/Documentation/translations/zh_CN/core-api/kernel-api.rst
b/Documentation/translations/zh_CN/core-api/kernel-api.rst
index a1ea70810..3a9d4a3a3 100644
--- a/Documentation/translations/zh_CN/core-api/kernel-api.rst
+++ b/Documentation/translations/zh_CN/core-api/kernel-api.rst
@@ -174,7 +174,7 @@ include/asm-generic/div64.h

 include/linux/math64.h

-lib/math/gcd.c
+lib/math/gcd.rs

 UUID/GUID
 ---------
diff --git a/lib/math/gcd.c b/lib/math/gcd.c
deleted file mode 100644
index 62efca678..000000000
--- a/lib/math/gcd.c
+++ /dev/null
@@ -1,88 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0-only
-#include <linux/kernel.h>
-#include <linux/gcd.h>
-#include <linux/export.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.
- */
-
-DEFINE_STATIC_KEY_TRUE(efficient_ffs_key);
-
-#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
-
-/* If __ffs is available, the even/odd algorithm benchmarks slower. */
-
-static unsigned long binary_gcd(unsigned long a, unsigned long b)
-{
- unsigned long r = a | b;
-
- 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;
- }
-}
-
-#endif
-
-/* If normalization is done by loops, the even/odd algorithm is a win. */
-
-/**
- * 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;
-
-#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
- if (static_branch_likely(&efficient_ffs_key))
- return binary_gcd(a, b);
-#endif
-
- /* Isolate lsbit of r */
- r &= -r;
-
- while (!(b & r))
- b >>= 1;
- if (b == r)
- return r;
-
- for (;;) {
- while (!(a & r))
- a >>= 1;
- if (a == r)
- return r;
- if (a == b)
- return a;
-
- if (a < b)
- swap(a, b);
- a -= b;
- a >>= 1;
- if (a & r)
- a += b;
- a >>= 1;
- }
-}
-
-EXPORT_SYMBOL_GPL(gcd);
diff --git a/lib/math/gcd.rs b/lib/math/gcd.rs
new file mode 100644
index 000000000..29397c669
--- /dev/null
+++ b/lib/math/gcd.rs
@@ -0,0 +1,103 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+//! Greatest Common Divisor
+//!
+//! 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.
+
+use kernel::prelude::*;
+
+/// Calculate the greatest common divisor of two `usize` values
+/// using the binary GCD algorithm.
+///
+/// Returns 0 if both inputs are 0. If only one input is 0, returns
+/// the non-zero value. The result is the largest integer that divides
+/// both `a` and `b` without remainder.
+///
+/// On architectures with an efficient find-first-set instruction,
+/// uses a faster bit-shifting path. On architectures without
+/// (CONFIG_CPU_NO_EFFICIENT_FFS), falls back to an even/odd loop
+/// which benchmarks better under those conditions.
+#[no_mangle]
+pub extern "C" fn gcd(mut a: usize, mut b: usize) -> usize {
+    let r = a | b;
+
+    if a == 0 || b == 0 {
+        return r;
+    }
+
+    #[cfg(not(CONFIG_CPU_NO_EFFICIENT_FFS))]
+    {
+        return binary_gcd(a, b);
+    }
+
+    // Isolate least significant set bit of r, which is shared by
+    // both a and b and must therefore be a factor of the GCD.
+    let r = r & r.wrapping_neg();
+
+    while (b & r) == 0 {
+        b >>= 1;
+    }
+    if b == r {
+        return r;
+    }
+
+    loop {
+        while (a & r) == 0 {
+            a >>= 1;
+        }
+        if a == r {
+            return r;
+        }
+        if a == b {
+            return a;
+        }
+        if a < b {
+            core::mem::swap(&mut a, &mut b);
+        }
+        a -= b;
+        a >>= 1;
+        if (a & r) != 0 {
+            a += b;
+        }
+        a >>= 1;
+    }
+}
+
+/// Inner fast path for architectures with efficient find-first-set.
+///
+/// Uses `trailing_zeros()` which maps directly to the hardware
+/// instruction (e.g. BSF on x86, CLZ on ARM). Not compiled on
+/// CONFIG_CPU_NO_EFFICIENT_FFS targets where the loop-based
+/// even/odd path in `gcd()` benchmarks faster.
+///
+/// `r` captures the shared trailing zeros between `a` and `b`,
+/// representing the power-of-two component of the GCD, which
+/// is restored via shift at the end.
+#[cfg(not(CONFIG_CPU_NO_EFFICIENT_FFS))]
+fn binary_gcd(mut a: usize, mut b: usize) -> usize {
+    let r = a | b;
+
+    b >>= b.trailing_zeros();
+    if b == 1 {
+        return r & r.wrapping_neg();
+    }
+
+    loop {
+        a >>= a.trailing_zeros();
+
+        if a == 1 {
+            return r & r.wrapping_neg();
+        }
+        if a == b {
+            return a << r.trailing_zeros();
+        }
+        if a < b {
+            core::mem::swap(&mut a, &mut b);
+        }
+        a -= b;
+    }
+}
-- 
2.54.0

Re: [PATCH] lib/gcd: Convert to Rust

[Greg KH]

On Tue, May 05, 2026 at 09:37:26PM -0400, Raymond Newman wrote:
> >From 96902ad2caf167ca0377e0b2063973e2183465b4 Mon Sep 17 00:00:00 2001
> From: Raymond Newman <raymondcharlesnewman@gmail.com>
> Date: Tue, 5 May 2026 21:29:29 -0400
> Subject: [PATCH] lib/gcd: Convert to Rust
> 
> Convert lib/math/gcd.c to Rust. The binary GCD algorithm is preserved
> exactly, including both the efficient-ffs fast path and the even/odd
> fallback for CONFIG_CPU_NO_EFFICIENT_FFS targets.

This says what you are doing, but not why.  Why make this change?

> -static unsigned long binary_gcd(unsigned long a, unsigned long b)
> -{
> - unsigned long r = a | b;
> -

<snip>

whitespace is damaged and this does not apply.

thanks,

greg k-h