From nobody Sat Jun 13 19:20:17 2026 Received: from mail-dy1-f193.google.com (mail-dy1-f193.google.com [74.125.82.193]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 006D32288CB for ; Wed, 6 May 2026 01:37:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=pass smtp.client-ip=74.125.82.193 ARC-Seal: i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778031461; cv=pass; b=TnEA/ndSvERQWSZ+nORQoleBL0ih2Uq7m3wbsnr1fl0lzdqySfMFZwIIcaUcQ+fsBj4q8ZC49vugXqw2DRVwSB1M0zs9Cg52H7yDsAlQNlMCuQaaoyJ/GUWbhuZgYonuj+r4r3hc7FgGQseefBrag41lA6hcoBrvQ15fdZUowhc= ARC-Message-Signature: i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778031461; c=relaxed/simple; bh=C7qsdyfRZwLfmFcnjYA15m8oaydBcIlTQ0Il36+MFvs=; h=MIME-Version:From:Date:Message-ID:Subject:To:Cc:Content-Type; b=sVMAVPaXqRz3NPixdCsUejUoex2kTVqzZS7zo39ESLxmiDXAt+N+Ab/uTrgtMnvayf53PJ3BxYoTsu6R9ILcwENpkwIiXabH3MpnM8auNlanZiTCa45ZYqYuq5WfiC4A792WPSazBjsX19iUjKLG9GmQWDPIwv0U9WUMsvSujXM= ARC-Authentication-Results: i=2; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ixCnj17V; arc=pass smtp.client-ip=74.125.82.193 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ixCnj17V" Received: by mail-dy1-f193.google.com with SMTP id 5a478bee46e88-2c156c4a9efso10249239eec.1 for ; Tue, 05 May 2026 18:37:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1778031458; cv=none; d=google.com; s=arc-20240605; b=fVQC8nPP+6/LL8vCIiaZZ/Opxg2tqUbKOAFrb4I5ImsLW035tkWR3V3C0uO5ljGq8n wHID+lD9W72zDkjXBDu2N6TxxmbEGvRq8SezSN+/8qHrbxZ4hlulsidcfeZ6aC6EVwOB 1VGiq13tWhR9TwM8jTUetKXH/9c5tuTTzF86D0FLb6xye4hy2MPuOFO4Hj22m081m0Yz TcXhHqpT40TXulAvM+G5D17TOcedQCNzihX0ZHtvrOZ6ayp3NT/DfdkbeXgLHNsHbZTt KsliBsQ9L4crnKG+S2Gj3/+und5sj/QwHZtc5CaaCXbuNAfe23kWSMd2+Gb/QLNoyss5 8wTg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:mime-version:dkim-signature; bh=+u3Nykeuw01L3aBy0CHhFQn8xLtqxnKceotQdPF0M3Y=; fh=h566vjL01JSLMSrcBVEHmcv46F+Yzpfua82D8M558qM=; b=XvniXzHRSAFMLM5bXDkYA73MTXLqNn2jQVwXmuaaf/JCDDJsbP9+DVNofmySmOPRpr lDde1Ie2kBRF2jdBp9BCkFfTb2D3RFH0pY5PPE1I5C4k/DmLCpViCPvkzjzz+1XhfpJj vDsYWshL5VNtfTq217girsPusAykewyBBpVLVL18USA0fdepe/TSm3SAkc3KLrygYlKa u1bxWwyIoRpvI8pc7yO0OJVb/VeAYrNzi9mmRqORH548ONnhvfpSoW8ysL5+CFi9enbr JRj4bKnQuChZCBBJ3eCscajbpK637pUKQtNonnlCHGFMhVIbQs55fzmUO2YcpE0tapmL 0liw==; darn=vger.kernel.org ARC-Authentication-Results: i=1; mx.google.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1778031458; x=1778636258; darn=vger.kernel.org; h=cc:to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=+u3Nykeuw01L3aBy0CHhFQn8xLtqxnKceotQdPF0M3Y=; b=ixCnj17VLPQg9lheYEj3yITgmaUrlpKFp3UIKE7a10tV77if6of1U/OCN4iR+kW/yn +lCITkH5gIr+j4XmpIjU6JffIB1d21gnY4B+XV5yyfO3jNLFs4sEVx0eAeOIj2UiC36X PCmqQtquocwae3+Cad9kKtLyn6ccJk+krU8gfFzvrWWx24ThoJMQPIBCpxAgKREOiIku pm6WCo7lcPwJn4A57PpID296FsHg68BgO+YMjZHycUoGfvSvjAXmoxPAWtpcpG62GCy7 oBkbEd+sGZuCulyjcDY1VhgYMdm3NRf7L5mg1+xsbmXx0uNzyqtV1H2HJd6OUonOFrXE wFag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1778031458; x=1778636258; h=cc:to:subject:message-id:date:from:mime-version:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=+u3Nykeuw01L3aBy0CHhFQn8xLtqxnKceotQdPF0M3Y=; b=PcXZsTAu0ljKtYo7XQlBPwUQzpaXogvY44OFTDP2ONfD4RRd6rMSuxLD7KCeMgkjGR Q7HXvHi8vi8HTKNtyizB1lJTEUayWJRJirLEQdeY3I3ClOv0Qqeb75f2etb6HkVABHff 6Cihi6sriClqbnbIAgDM+JgeBQiFNiNCMHEn46xcpQjK2lIv4Ld8zr6WLxLWEHnBo3pM O+65D/lp43YO6tF2ve15hBY16mfE1b34wAITgzwpSIUYHBCw3pYKNYmVnhYIinjn/YI+ 57LQNenMBv5bmXKugvtYZKQl5ecTpWnXbuQYHuhzcx8jGfr4r9dCiloubO3g0Us74ORw VlKg== X-Gm-Message-State: AOJu0Ywt+Gfbw9CQaY65Wh+g3XubaVIY68XeCGvdbu5NEdp2ay7oTRLc 44DcmqNc7c+WpBzgzDM6B8w5XtT1sbueNOxzWCMmoT6VsY7nhJzNySCOrFxXUpRIg/ap/P3Tb6L Cvi6JDP6IihyaK68+ntCJIyiHhuMwj3Vfk6N4C7/hGQ== X-Gm-Gg: AeBDievHBgq59Gg7yl9S/LJNkJg0Uq3qq1+YkXScphPZx8gLBFu9z7pKa/6DZfCfdN/ iUKfPHrRY4aSS5+65ihPBrxs6qA748Zo409625nJ3D+DeRxvwZPoGXa9Td6j20hMmim7dnHRXRS ErNYiQhC7rdp2yOeILLRnPCp/ThWqP91ujtqfYszKhW6AgMdVSYl+L3avKvAhwnPYNemSfTew6K qNQQ51Tu380eD7/VutC5qwuy5K7asVS4GZyWc+DlTW7Dlywm9wOU1kZdE5NL24AlZQEVus0cQGh wjlG0+6hQAWglvhzuyL9bLeewy892SEkVnAsEtnxvQQctCMOF3Pq X-Received: by 2002:a05:7022:251f:b0:127:5cd6:fa45 with SMTP id a92af1059eb24-1319cc19f1dmr852370c88.14.1778031457882; Tue, 05 May 2026 18:37:37 -0700 (PDT) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 From: Raymond Newman Date: Tue, 5 May 2026 21:37:26 -0400 X-Gm-Features: AVHnY4Kf8u22XpqbbYHu0UkH0cArPL6iBBLagzAn_rgaMABRGr1lNMEyPN9lh80 Message-ID: Subject: [PATCH] lib/gcd: Convert to Rust To: linux-kernel@vger.kernel.org Cc: ojeda@kernel.org, boqun@kernel.org, gary@garyguo.net, bjorn3_gh@protonmail.com, lossin@kernel.org, a.hindborg@kernel.org, aliceryhl@google.com, tmgross@umich.edu, dakr@kernel.org, corbet@lwn.net, skhan@linuxfoundation.org, rust-for-linux@vger.kernel.org, linux-doc@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From 96902ad2caf167ca0377e0b2063973e2183465b4 Mon Sep 17 00:00:00 2001 From: Raymond Newman 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 --- 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 -#include -#include - -/* - * 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 =3D a | b; - - b >>=3D __ffs(b); - if (b =3D=3D 1) - return r & -r; - - for (;;) { - a >>=3D __ffs(a); - if (a =3D=3D 1) - return r & -r; - if (a =3D=3D b) - return a << __ffs(r); - - if (a < b) - swap(a, b); - a -=3D 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 lo= ngs - * @a: first value - * @b: second value - */ -unsigned long gcd(unsigned long a, unsigned long b) -{ - unsigned long r =3D 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 &=3D -r; - - while (!(b & r)) - b >>=3D 1; - if (b =3D=3D r) - return r; - - for (;;) { - while (!(a & r)) - a >>=3D 1; - if (a =3D=3D r) - return r; - if (a =3D=3D b) - return a; - - if (a < b) - swap(a, b); - a -=3D b; - a >>=3D 1; - if (a & r) - a +=3D b; - a >>=3D 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 =3D a | b; + + if a =3D=3D 0 || b =3D=3D 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 =3D r & r.wrapping_neg(); + + while (b & r) =3D=3D 0 { + b >>=3D 1; + } + if b =3D=3D r { + return r; + } + + loop { + while (a & r) =3D=3D 0 { + a >>=3D 1; + } + if a =3D=3D r { + return r; + } + if a =3D=3D b { + return a; + } + if a < b { + core::mem::swap(&mut a, &mut b); + } + a -=3D b; + a >>=3D 1; + if (a & r) !=3D 0 { + a +=3D b; + } + a >>=3D 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 =3D a | b; + + b >>=3D b.trailing_zeros(); + if b =3D=3D 1 { + return r & r.wrapping_neg(); + } + + loop { + a >>=3D a.trailing_zeros(); + + if a =3D=3D 1 { + return r & r.wrapping_neg(); + } + if a =3D=3D b { + return a << r.trailing_zeros(); + } + if a < b { + core::mem::swap(&mut a, &mut b); + } + a -=3D b; + } +} --=20 2.54.0