linux-kernel - Re: [PATCH 16/16] lib: move find_closest() and find_closest

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ba79221f-9acd-4919-abe9-e2c49e80fb6c@baylibre.com>
Date: Mon, 19 May 2025 11:35:48 -0500
From: David Lechner <dlechner@...libre.com>
To: Alexandru Soponar <asoponar@...adin.ro>, linux-kernel@...r.kernel.org,
 linux-hwmon@...r.kernel.org, linux-iio@...r.kernel.org,
 linux-leds@...r.kernel.org, linux-watchdog@...r.kernel.org
Cc: jdelvare@...e.com, linux@...ck-us.net, jic23@...nel.org, pavel@....cz,
 lee@...nel.org, baocheng.su@...mens.com, wim@...ux-watchdog.org,
 tobias.schaffner@...mens.com, angelogioacchino.delregno@...labora.com,
 benedikt.niedermayr@...mens.com, matthias.bgg@...il.com,
 aardelean@...libre.com, contact@...y.one
Subject: Re: [PATCH 16/16] lib: move find_closest() and
 find_closest_descending() to lib functions

On 5/15/25 3:13 AM, Alexandru Soponar wrote:
> Move the utility macros find_closest() and find_closest_descending()
> from inline macros to proper library functions in lib/.
> 
> Signed-off-by: Alexandru Soponar <asoponar@...adin.ro>
> ---
>  include/linux/find_closest.h | 13 +++++++
>  include/linux/util_macros.h  | 61 +------------------------------
>  lib/Makefile                 |  2 +-
>  lib/find_closest.c           | 71 ++++++++++++++++++++++++++++++++++++
>  4 files changed, 86 insertions(+), 61 deletions(-)
>  create mode 100644 include/linux/find_closest.h
>  create mode 100644 lib/find_closest.c
> 
> diff --git a/include/linux/find_closest.h b/include/linux/find_closest.h
> new file mode 100644
> index 000000000000..28a5c4d0c768
> --- /dev/null
> +++ b/include/linux/find_closest.h
> @@ -0,0 +1,13 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +/*
> + * Find closest element functions
> + */
> +#ifndef _LINUX_FIND_CLOSEST_H_
> +#define _LINUX_FIND_CLOSEST_H_
> +
> +#include <linux/types.h>

Is this header really needed?

> +
> +unsigned int find_closest(int x, const int *a, unsigned int as);
> +unsigned int find_closest_descending(int x, const int *a, unsigned int as);
> +
> +#endif /* _LINUX_FIND_CLOSEST_H_ */

...

> diff --git a/lib/find_closest.c b/lib/find_closest.c
> new file mode 100644
> index 000000000000..d481625cae9d
> --- /dev/null
> +++ b/lib/find_closest.c
> @@ -0,0 +1,71 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Find closest element functions
> + *
> + * Based on previous util_macros.h implementation
> + */
> +
> +#include <linux/find_closest.h>
> +#include <linux/module.h>
> +
> +/**
> + * find_closest - locate the closest element in a sorted array
> + * @x: The reference value.
> + * @a: The array in which to look for the closest element. Must be sorted
> + *  in ascending order.
> + * @as: Size of 'a'.
> + *
> + * Returns the index of the element closest to 'x'.

s/Returns/Returns:/

for kernel-doc semantics

> + */
> +unsigned int find_closest(int x, const int *a, unsigned int as)
> +{
> +	unsigned int array_size = as - 1;
> +	int mid_x, left, right;
> +	unsigned int i;
> +
> +	for (i = 0; i < array_size; i++) {
> +		mid_x = (a[i] + a[i + 1]) / 2;
> +		if (x <= mid_x) {
> +			left = x - a[i];
> +			right = a[i + 1] - x;
> +			if (right < left)
> +				i++;
> +			break;
> +		}
> +	}
> +
> +	return i;
> +}
> +EXPORT_SYMBOL_GPL(find_closest);
> +
> +/**
> + * find_closest_descending - locate the closest element in a sorted array
> + * @x: The reference value.
> + * @a: The array in which to look for the closest element. Must be sorted
> + *  in descending order.
> + * @as: Size of 'a'.
> + *

Would repeat the Returns: section here for completeness.

> + * Similar to find_closest() but 'a' is expected to be sorted in descending
> + * order.

This seems redundant since @a already says this.

>             The iteration is done in reverse order, so that the comparison> + * of 'right' & 'left' also works for unsigned numbers.

This seems like an implementation detail so would be better as a comment inside
the function. Although, since @a is always signed, is this comment actually
still applicable?

> + */
> +unsigned int find_closest_descending(int x, const int *a, unsigned int as)
> +{
> +	unsigned int array_size = as - 1;
> +	int mid_x, left, right;
> +	unsigned int i;
> +
> +	for (i = array_size; i >= 1; i--) {
> +		mid_x = (a[i] + a[i - 1]) / 2;
> +		if (x <= mid_x) {
> +			left = x - a[i];
> +			right = a[i - 1] - x;
> +			if (right < left)
> +				i--;
> +			break;
> +		}
> +	}
> +
> +	return i;
> +}
> +EXPORT_SYMBOL_GPL(find_closest_descending);