From: Alexandru Ardelean <aardelean@baylibre.com>
To: linux-iio@vger.kernel.org, linux-kernel@vger.kernel.org
Cc: jic23@kernel.org, bartosz.golaszewski@linaro.org,
gregkh@linuxfoundation.org, akpm@linux-foundation.org,
Alexandru Ardelean <aardelean@baylibre.com>
Subject: [PATCH 1/2] util_macros.h: fix/rework find_closest() macros
Date: Thu, 31 Oct 2024 08:37:06 +0200 [thread overview]
Message-ID: <20241031063707.795842-1-aardelean@baylibre.com> (raw)
A bug was found in the find_closest() (find_closest_descending() is also
affected after some testing), where for certain values with small
progressions, the rounding (done by averaging 2 values) causes an incorrect
index to be returned.
The rounding issues occur for progressions of 1, 2 and 3. It goes away when
the progression/interval between two values is 4 or larger.
It's particularly bad for progressions of 1. For example if there's an
array of 'a = { 1, 2, 3 }', using 'find_closest(2, a ...)' would return 0
(the index of '1'), rather than returning 1 (the index of '2').
This means that for exact values (with a progression of 1), find_closest()
will misbehave and return the index of the value smaller than the one we're
searching for.
For progressions of 2 and 3, the exact values are obtained correctly; but
values aren't approximated correctly (as one would expect). Starting with
progressions of 4, all seems to be good.
This change reworks the find_closest(x,) macros to also check the
difference between the left and right elements when 'x'. If the distance to
the right is smaller (than the distance to the left), the index is
incremented by 1. This also makes redundant the need for using the
DIV_ROUND_CLOSEST() macro.
For find_closest_descending(), the operator was changed from '>=' to '>'.
Since the iteration is happening from the highest-to-lowest values, the
'>=' comparison would (for small progressions) prefer higher values (as
closer to the given values).
For example:
Given array 'a[] = { 10, 7, 4, 1 };'
find_closest_descending(2, a,...) returns the index[2] for 4
find_closest_descending(5, a,...) returns the index[1] for 7
find_closest_descending(8, a,...) returns the index[0] for 10
Signed-off-by: Alexandru Ardelean <aardelean@baylibre.com>
---
include/linux/util_macros.h | 14 ++++++++++----
1 file changed, 10 insertions(+), 4 deletions(-)
diff --git a/include/linux/util_macros.h b/include/linux/util_macros.h
index 6bb460c3e818..60c74770b703 100644
--- a/include/linux/util_macros.h
+++ b/include/linux/util_macros.h
@@ -7,12 +7,18 @@
#define __find_closest(x, a, as, op) \
({ \
typeof(as) __fc_i, __fc_as = (as) - 1; \
- typeof(x) __fc_x = (x); \
+ typeof(x) __fc_mid_x, __fc_x = (x); \
+ typeof(x) __fc_left, __fc_right; \
typeof(*a) const *__fc_a = (a); \
for (__fc_i = 0; __fc_i < __fc_as; __fc_i++) { \
- if (__fc_x op DIV_ROUND_CLOSEST(__fc_a[__fc_i] + \
- __fc_a[__fc_i + 1], 2)) \
+ __fc_mid_x = (__fc_a[__fc_i] + __fc_a[__fc_i + 1]) / 2; \
+ if (__fc_x op __fc_mid_x) { \
+ __fc_left = __fc_mid_x - __fc_a[__fc_i]; \
+ __fc_right = __fc_a[__fc_i + 1] - __fc_mid_x; \
+ if (__fc_right < __fc_left) \
+ __fc_i++; \
break; \
+ } \
} \
(__fc_i); \
})
@@ -38,7 +44,7 @@
* Similar to find_closest() but 'a' is expected to be sorted in descending
* order.
*/
-#define find_closest_descending(x, a, as) __find_closest(x, a, as, >=)
+#define find_closest_descending(x, a, as) __find_closest(x, a, as, >)
/**
* is_insidevar - check if the @ptr points inside the @var memory range.
--
2.46.1
next reply other threads:[~2024-10-31 6:37 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-10-31 6:37 Alexandru Ardelean [this message]
2024-10-31 6:37 ` [PATCH 2/2] lib: util_macros_kunit: add kunit test for util_macros.h Alexandru Ardelean
2024-11-01 1:59 ` [PATCH 1/2] util_macros.h: fix/rework find_closest() macros Andrew Morton
2024-11-01 9:07 ` Alexandru Ardelean
2024-11-01 20:04 ` Andrew Morton
2024-11-05 7:15 ` Alexandru Ardelean
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20241031063707.795842-1-aardelean@baylibre.com \
--to=aardelean@baylibre.com \
--cc=akpm@linux-foundation.org \
--cc=bartosz.golaszewski@linaro.org \
--cc=gregkh@linuxfoundation.org \
--cc=jic23@kernel.org \
--cc=linux-iio@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®