[PATCH] lib/gcd: Convert to Rust

Patch content 4 changed files

From 96902ad2caf167ca0377e0b2063973e2183465b4 Mon Sep 17 00:00:00 2001From: Raymond Newman <raymondcharlesnewman@gmail.com>Date: Tue, 5 May 2026 21:29:29 -0400Subject: [PATCH] lib/gcd: Convert to Rust Convert lib/math/gcd.c to Rust. The binary GCD algorithm is preservedexactly, including both the efficient-ffs fast path and the even/oddfallback for CONFIG_CPU_NO_EFFICIENT_FFS targets. __ffs() is replaced with trailing_zeros(), which maps to the samehardware instruction. swap() is replaced with core::mem::swap().Unary negation for the bitmask isolation trick is replaced withwrapping_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.rstb/Documentation/core-api/kernel-api.rstindex 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/GUIDdiff --git a/Documentation/translations/zh_CN/core-api/kernel-api.rstb/Documentation/translations/zh_CN/core-api/kernel-api.rstindex 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.cdeleted file mode 100644index 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.rsnew file mode 100644index 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