2024-05-09 18:43:47

by Devarsh Thakkar

[permalink] [raw]
Subject: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

Add macros to round to nearest specified power of 2. Two macros are added :
round_closest_up and round_closest_down which round up to nearest multiple
of 2 with a preference to round up or round down respectively if there are
two possible nearest values to the given number.

This patch is inspired from the Mentor Graphics IPU driver [1] which uses
similar macro locally and which can be updated to use this generic macro
instead along with other drivers having similar requirements.

[1]:
https://elixir.bootlin.com/linux/v6.8.9/source/drivers/gpu/ipu-v3/ipu-image-convert.c#L480

Signed-off-by: Devarsh Thakkar <[email protected]>
---
V1->V6 (No change, patch introduced in V7)
---
include/linux/math.h | 36 ++++++++++++++++++++++++++++++++++++
1 file changed, 36 insertions(+)

diff --git a/include/linux/math.h b/include/linux/math.h
index dd4152711de7..82ee3265c910 100644
--- a/include/linux/math.h
+++ b/include/linux/math.h
@@ -34,6 +34,42 @@
*/
#define round_down(x, y) ((x) & ~__round_mask(x, y))

+/**
+ * round_closest_up - round to nearest specified power of 2 with preference
+ * to rounding up
+ * @x: the value to round
+ * @y: multiple to round to (must be a power of 2)
+ *
+ * Rounds @x to nearest multiple of @y (which must be a power of 2).
+ * The rounded value can be greater than or less than @x depending
+ * upon it's nearness to @x. If there are two nearest possible values,
+ * then preference will be given to the greater value.
+ *
+ * Examples :
+ * round_closest_up(17, 4) = 16
+ * round_closest_up(15, 4) = 16
+ * round_closest_up(14, 4) = 16
+ */
+#define round_closest_up(x, y) round_down((x) + (y) / 2, (y))
+
+/**
+ * round_closest_down - round to nearest specified power of 2 with preference
+ * to rounding down
+ * @x: the value to round
+ * @y: multiple to round down to (must be a power of 2)
+ *
+ * Rounds @x to nearest multiple of @y (which must be a power of 2).
+ * The rounded value can be greater than or less than @x depending
+ * upon it's nearness to @x. If there are two nearest possible values,
+ * then preference will be given to the lesser value.
+ *
+ * Examples :
+ * round_closest_down(17, 4) = 16
+ * round_closest_down(15, 4) = 16
+ * round_closest_down(14, 4) = 12
+ */
+#define round_closest_down(x, y) round_up((x) - (y) / 2, (y))
+
#define DIV_ROUND_UP __KERNEL_DIV_ROUND_UP

#define DIV_ROUND_DOWN_ULL(ll, d) \
--
2.39.1



2024-05-10 15:15:58

by Jani Nikula

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Fri, 10 May 2024, Andy Shevchenko <[email protected]> wrote:
> On Fri, May 10, 2024 at 12:09:52AM +0530, Devarsh Thakkar wrote:
>> Add macros to round to nearest specified power of 2.
>
> This is not what they are doing. For the above we already have macros defined.
>
>> Two macros are added :
>
> (Yes, after I wrapped to comment this line looks better on its own,
> so whatever will be the first sentence, this line should be separated
> from.)
>
>> round_closest_up and round_closest_down which round up to nearest multiple
>
> round_closest_up() and round_closest_down()
>
>
>> of 2 with a preference to round up or round down respectively if there are
>> two possible nearest values to the given number.
>
> You should reformulate, because AFAICS there is the crucial difference
> from these and existing round_*_pow_of_two().

Moreover, I think the naming of round_up() and round_down() should have
reflected the fact that they operate on powers of 2. It's unfortunate
that the difference to roundup() and rounddown() is just the underscore!
That's just a trap.

So let's perhaps not repeat the same with round_closest_up() and
round_closest_down()?

BR,
Jani.


>
>> This patch is inspired from the Mentor Graphics IPU driver [1] which uses
>> similar macro locally and which can be updated to use this generic macro
>> instead along with other drivers having similar requirements.
>>
>> [1]:
>> https://elixir.bootlin.com/linux/v6.8.9/source/drivers/gpu/ipu-v3/ipu-image-convert.c#L480
>
> Instead of this, just add a patch to convert that driver to use this new macro.
> Besides, this paragraph should go to the comment/changelog area below.
>
>> Signed-off-by: Devarsh Thakkar <[email protected]>
>> ---
>> V1->V6 (No change, patch introduced in V7)
>> ---

--
Jani Nikula, Intel

2024-05-10 16:40:05

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Fri, May 10, 2024 at 06:15:34PM +0300, Jani Nikula wrote:
> On Fri, 10 May 2024, Andy Shevchenko <[email protected]> wrote:
> > On Fri, May 10, 2024 at 12:09:52AM +0530, Devarsh Thakkar wrote:
> >> Add macros to round to nearest specified power of 2.
> >
> > This is not what they are doing. For the above we already have macros defined.
> >
> >> Two macros are added :
> >
> > (Yes, after I wrapped to comment this line looks better on its own,
> > so whatever will be the first sentence, this line should be separated
> > from.)
> >
> >> round_closest_up and round_closest_down which round up to nearest multiple
> >
> > round_closest_up() and round_closest_down()
> >
> >
> >> of 2 with a preference to round up or round down respectively if there are
> >> two possible nearest values to the given number.
> >
> > You should reformulate, because AFAICS there is the crucial difference
> > from these and existing round_*_pow_of_two().
>
> Moreover, I think the naming of round_up() and round_down() should have
> reflected the fact that they operate on powers of 2. It's unfortunate
> that the difference to roundup() and rounddown() is just the underscore!
> That's just a trap.

FYI:
https://stackoverflow.com/questions/58139219/difference-of-align-and-round-up-macro-in-the-linux-kernel

> So let's perhaps not repeat the same with round_closest_up() and
> round_closest_down()?


--
With Best Regards,
Andy Shevchenko



2024-05-10 20:04:37

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Fri, May 10, 2024 at 12:09:52AM +0530, Devarsh Thakkar wrote:
> Add macros to round to nearest specified power of 2.

This is not what they are doing. For the above we already have macros defined.

> Two macros are added :

(Yes, after I wrapped to comment this line looks better on its own,
so whatever will be the first sentence, this line should be separated
from.)

> round_closest_up and round_closest_down which round up to nearest multiple

round_closest_up() and round_closest_down()


> of 2 with a preference to round up or round down respectively if there are
> two possible nearest values to the given number.

You should reformulate, because AFAICS there is the crucial difference
from these and existing round_*_pow_of_two().

> This patch is inspired from the Mentor Graphics IPU driver [1] which uses
> similar macro locally and which can be updated to use this generic macro
> instead along with other drivers having similar requirements.
>
> [1]:
> https://elixir.bootlin.com/linux/v6.8.9/source/drivers/gpu/ipu-v3/ipu-image-convert.c#L480

Instead of this, just add a patch to convert that driver to use this new macro.
Besides, this paragraph should go to the comment/changelog area below.

> Signed-off-by: Devarsh Thakkar <[email protected]>
> ---
> V1->V6 (No change, patch introduced in V7)
> ---

--
With Best Regards,
Andy Shevchenko



2024-05-11 17:27:18

by Devarsh Thakkar

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

Hi Andy,

Thanks for the quick review.

On 10/05/24 20:31, Andy Shevchenko wrote:
> On Fri, May 10, 2024 at 12:09:52AM +0530, Devarsh Thakkar wrote:
>> Add macros to round to nearest specified power of 2.
>
> This is not what they are doing. For the above we already have macros defined.
>

Sorry I did not understand this comment, if you are talking about
existing macros round_up & round_down they either round "up" and round
"down" to specified power of 2 as specified here [1].
whereas the macros introduced in this patch round to "nearest" specified
power of 2.

>> Two macros are added :
>
> (Yes, after I wrapped to comment this line looks better on its own,
> so whatever will be the first sentence, this line should be separated
> from.)
>

Agreed.

>> round_closest_up and round_closest_down which round up to nearest multiple
>
> round_closest_up() and round_closest_down()
>
>
>> of 2 with a preference to round up or round down respectively if there are
>> two possible nearest values to the given number.
>
> You should reformulate, because AFAICS there is the crucial difference
> from these and existing round_*_pow_of_two().
>

In math.h, we already have round_up/round_down macros which rounded
up/down to next specified power of 2. Then we had the DIV_ROUND_CLOSEST
which used the suffix _CLOSEST to imply the meaning that divided value
will be rounded to nearest/closest int value either by rounding up or
rounding down.

So inspired from naming convention of this macros given developers are
already familiar with them, I used round_closest for specifying the
rounded value to nearest/closest value which can be achieved either by
rounding up/down. And I also wanted user to have finer control for the
scenarios where there are two possible nearest values :

For e.g round(160, 64) can be either 192 and 128 and both are 32 away
from 160.

And that's the reason I went ahead with two macros instead i.e
round_closest_up, round_closest_down so that developers can choose
exactly what they want.

Regards
Devarsh

2024-05-11 17:42:05

by Devarsh Thakkar

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

Hi Jani,

Thanks for the quick review.

On 10/05/24 20:45, Jani Nikula wrote:

[...]
> Moreover, I think the naming of round_up() and round_down() should have
> reflected the fact that they operate on powers of 2. It's unfortunate
> that the difference to roundup() and rounddown() is just the underscore!
> That's just a trap.
>
> So let's perhaps not repeat the same with round_closest_up() and
> round_closest_down()?
>

Yes the naming is inspired by existing macros i.e. round_up, round_down
(which round up/down to next pow of 2) and DIV_ROUND_CLOSEST (which
round the divided value to closest value) and there are already a lot of
users for these API's :

linux-next git:(heads/next-20240509) ✗ grep -nr round_up drivers | wc
730 4261 74775

linux-next git:(heads/next-20240509) ✗ grep -nr round_down drivers | wc
226 1293 22194

linux-next git:(heads/next-20240509) ✗ grep -nr DIV_ROUND_CLOSEST
drivers | wc
1207 7461 111822


so I thought to align with existing naming convention assuming
developers are already familiar with this.

But if a wider consensus is to go with a newer naming convention then I
am open to it, although a challenge there would be to keep it short. For
e.g. this one is already 3 words, if we go with more explicit
"round_closest_up_pow_2" it looks quite long in my opinion :) .

Regards
Devarsh

2024-05-12 04:47:15

by Alexey Dobriyan

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

I think

roundup(x, 1 << n)

is more readable.

2024-05-13 09:07:03

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Sat, May 11, 2024 at 11:11:14PM +0530, Devarsh Thakkar wrote:
> On 10/05/24 20:45, Jani Nikula wrote:

[...]

> > Moreover, I think the naming of round_up() and round_down() should have
> > reflected the fact that they operate on powers of 2. It's unfortunate
> > that the difference to roundup() and rounddown() is just the underscore!
> > That's just a trap.
> >
> > So let's perhaps not repeat the same with round_closest_up() and
> > round_closest_down()?
>
> Yes the naming is inspired by existing macros i.e. round_up, round_down
> (which round up/down to next pow of 2) and DIV_ROUND_CLOSEST (which
> round the divided value to closest value) and there are already a lot of
> users for these API's :
>
> linux-next git:(heads/next-20240509) ✗ grep -nr round_up drivers | wc
> 730 4261 74775
>
> linux-next git:(heads/next-20240509) ✗ grep -nr round_down drivers | wc
> 226 1293 22194
>
> linux-next git:(heads/next-20240509) ✗ grep -nr DIV_ROUND_CLOSEST
> drivers | wc
> 1207 7461 111822

Side note, discover `git grep ...`: it's much much faster on Git index,
than classic one on a working copy.

> so I thought to align with existing naming convention assuming
> developers are already familiar with this.
>
> But if a wider consensus is to go with a newer naming convention then I
> am open to it, although a challenge there would be to keep it short. For
> e.g. this one is already 3 words, if we go with more explicit
> "round_closest_up_pow_2" it looks quite long in my opinion :) .

You need properly name the macros. Again, round_up() / roundup() and
roundup_pow_of_two() are three _different_ macros, and it's not clear
why you can't use one of them in your case.

The patch that changes those to a new one are doubtful to begin with.
I.e. need a careful review on the arithmetics side of the change
including HW capabilities of handling "closest" results.

--
With Best Regards,
Andy Shevchenko



2024-05-13 11:26:39

by Devarsh Thakkar

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

Hi Andy,

On 13/05/24 14:29, Andy Shevchenko wrote:
> On Sat, May 11, 2024 at 11:11:14PM +0530, Devarsh Thakkar wrote:
>> On 10/05/24 20:45, Jani Nikula wrote:
>
> [...]
>
>>> Moreover, I think the naming of round_up() and round_down() should have
>>> reflected the fact that they operate on powers of 2. It's unfortunate
>>> that the difference to roundup() and rounddown() is just the underscore!
>>> That's just a trap.
>>>
>>> So let's perhaps not repeat the same with round_closest_up() and
>>> round_closest_down()?
>>
>> Yes the naming is inspired by existing macros i.e. round_up, round_down
>> (which round up/down to next pow of 2) and DIV_ROUND_CLOSEST (which
>> round the divided value to closest value) and there are already a lot of
>> users for these API's :
>>
>> linux-next git:(heads/next-20240509) ✗ grep -nr round_up drivers | wc
>> 730 4261 74775
>>
>> linux-next git:(heads/next-20240509) ✗ grep -nr round_down drivers | wc
>> 226 1293 22194
>>
>> linux-next git:(heads/next-20240509) ✗ grep -nr DIV_ROUND_CLOSEST
>> drivers | wc
>> 1207 7461 111822
>
> Side note, discover `git grep ...`: it's much much faster on Git index,
> than classic one on a working copy.
>
>> so I thought to align with existing naming convention assuming
>> developers are already familiar with this.
>>
>> But if a wider consensus is to go with a newer naming convention then I
>> am open to it, although a challenge there would be to keep it short. For
>> e.g. this one is already 3 words, if we go with more explicit
>> "round_closest_up_pow_2" it looks quite long in my opinion :) .
>
> You need properly name the macros. Again, round_up() / roundup() and
> roundup_pow_of_two() are three _different_ macros, and it's not clear
> why you can't use one of them in your case.
>

I can't use any of these because these macros either round up or round down,
whereas I want to round to closest value for the argument specified by the
user, be it achieved either by rounding up or rounding down depending upon
whichever makes the answer closer to the user-specified argument.

To make it clear, I have already included the examples in the macro
description [2], copying it here, maybe I can put the same examples in the
commit message too to avoid confusions :

round_closest_up(17, 4) = 16
round_closest_up(15, 4) = 16
round_closest_up(14, 4) = 16

round_closest_down(17, 4) = 16
round_closest_down(15, 4) = 16
round_closest_down(14, 4) = 12

Coming back to naming, this is as per existing convention used for naming
round_up, round_down (notice the `_` being used for macros working with pow of
2) and DIV_ROUND_CLOSEST (notice the work `closest` used to specify the answer
to be nearest to specified value). Naming is a bit subjective, but I
personally don't think it is a good idea to go away with the existing naming
convention or go with longer names.

> The patch that changes those to a new one are doubtful to begin with.
> I.e. need a careful review on the arithmetics side of the change
> including HW capabilities of handling "closest" results.
>

This is already tested from my side, in-fact I have posted some of the results
in cover-letter with these macros [1] :

Regarding hardware capabilities, it uses existing round_up, round_down macros
underneath which are optimized to handle pow of 2 after modifying the user
provided argument using addition/subtraction and division, so I don't think it
should generally a problem with the hardware.
And I see other macros DIV_ROUND_CLOSEST [3] already using similar operations
i.e. addition/subtraction and division so don't think it should be a problem
to keep similar other macros in the same file.

[1]:
https://gist.github.com/devarsht/de6f5142f678bb1a5338abfd9f814abd#file-v7_jpeg_encoder_crop_validation-L204
[2]: https://lore.kernel.org/all/[email protected]/
[3]: https://elixir.bootlin.com/linux/latest/source/include/linux/math.h#L86

Regards
Devarsh

2024-05-13 13:05:09

by Devarsh Thakkar

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

Hi Andy,

On 13/05/24 17:55, Andy Shevchenko wrote:
> On Mon, May 13, 2024 at 04:55:58PM +0530, Devarsh Thakkar wrote:
>> On 13/05/24 14:29, Andy Shevchenko wrote:
>>> On Sat, May 11, 2024 at 11:11:14PM +0530, Devarsh Thakkar wrote:
>>>> On 10/05/24 20:45, Jani Nikula wrote:
>
> [...]
> - align naming (with the existing round*() macros)

I think round_closest_up/round_closest_down align already and inspired by the
existing naming convention used for round*() and DIV_ROUND_CLOSEST() macros in
math.h as explained below (copied from my previous reply [1])

"Coming back to naming, this is as per existing convention used for naming
round_up, round_down (notice the `_` being used for macros working with pow of
2) and DIV_ROUND_CLOSEST (notice the work `closest` used to specify the answer
to be nearest to specified value)"

But do let me know if you have any other suggestions for naming?

> - add examples into commit message of the math.h patch

Agreed
> - add test cases (you need to create lib/math_kunit.c for that)
Agreed.
> - elaborate in the commit message of the IPU3 change what you posted above
> (some kind of a summary)
Agreed.


[1]: https://lore.kernel.org/all/[email protected]/

Regards
Devarsh

2024-05-13 13:50:02

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Sun, May 12, 2024 at 07:46:58AM +0300, Alexey Dobriyan wrote:
> I think
>
> roundup(x, 1 << n)

Since it's about power-of-two, round_up() is better.

> is more readable.

--
With Best Regards,
Andy Shevchenko



2024-05-13 18:11:27

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Mon, May 13, 2024 at 06:34:19PM +0530, Devarsh Thakkar wrote:
> On 13/05/24 17:55, Andy Shevchenko wrote:
> > On Mon, May 13, 2024 at 04:55:58PM +0530, Devarsh Thakkar wrote:
> >> On 13/05/24 14:29, Andy Shevchenko wrote:
> >>> On Sat, May 11, 2024 at 11:11:14PM +0530, Devarsh Thakkar wrote:
> >>>> On 10/05/24 20:45, Jani Nikula wrote:

[...]

> > - align naming (with the existing round*() macros)
>
> I think round_closest_up/round_closest_down align already and inspired by the
> existing naming convention used for round*() and DIV_ROUND_CLOSEST() macros in
> math.h as explained below (copied from my previous reply [1])
>
> "Coming back to naming, this is as per existing convention used for naming
> round_up, round_down (notice the `_` being used for macros working with pow of
> 2) and DIV_ROUND_CLOSEST (notice the work `closest` used to specify the answer
> to be nearest to specified value)"
>
> But do let me know if you have any other suggestions for naming?

Just make sure that semantically the naming is aligned, that's it.
If you think it's already done that way, fine!

--
With Best Regards,
Andy Shevchenko



2024-05-13 18:30:09

by Andy Shevchenko

[permalink] [raw]
Subject: Re: [PATCH v7 6/8] math.h Add macros to round to closest specified power of 2

On Mon, May 13, 2024 at 04:55:58PM +0530, Devarsh Thakkar wrote:
> On 13/05/24 14:29, Andy Shevchenko wrote:
> > On Sat, May 11, 2024 at 11:11:14PM +0530, Devarsh Thakkar wrote:
> >> On 10/05/24 20:45, Jani Nikula wrote:

[...]

> >>> Moreover, I think the naming of round_up() and round_down() should have
> >>> reflected the fact that they operate on powers of 2. It's unfortunate
> >>> that the difference to roundup() and rounddown() is just the underscore!
> >>> That's just a trap.
> >>>
> >>> So let's perhaps not repeat the same with round_closest_up() and
> >>> round_closest_down()?
> >>
> >> Yes the naming is inspired by existing macros i.e. round_up, round_down
> >> (which round up/down to next pow of 2) and DIV_ROUND_CLOSEST (which
> >> round the divided value to closest value) and there are already a lot of
> >> users for these API's :
> >>
> >> linux-next git:(heads/next-20240509) ✗ grep -nr round_up drivers | wc
> >> 730 4261 74775
> >>
> >> linux-next git:(heads/next-20240509) ✗ grep -nr round_down drivers | wc
> >> 226 1293 22194
> >>
> >> linux-next git:(heads/next-20240509) ✗ grep -nr DIV_ROUND_CLOSEST
> >> drivers | wc
> >> 1207 7461 111822
> >
> > Side note, discover `git grep ...`: it's much much faster on Git index,
> > than classic one on a working copy.
> >
> >> so I thought to align with existing naming convention assuming
> >> developers are already familiar with this.
> >>
> >> But if a wider consensus is to go with a newer naming convention then I
> >> am open to it, although a challenge there would be to keep it short. For
> >> e.g. this one is already 3 words, if we go with more explicit
> >> "round_closest_up_pow_2" it looks quite long in my opinion :) .
> >
> > You need properly name the macros. Again, round_up() / roundup() and
> > roundup_pow_of_two() are three _different_ macros, and it's not clear
> > why you can't use one of them in your case.
>
> I can't use any of these because these macros either round up or round down,
> whereas I want to round to closest value for the argument specified by the
> user, be it achieved either by rounding up or rounding down depending upon
> whichever makes the answer closer to the user-specified argument.
>
> To make it clear, I have already included the examples in the macro
> description [2], copying it here, maybe I can put the same examples in the
> commit message too to avoid confusions :
>
> round_closest_up(17, 4) = 16
> round_closest_up(15, 4) = 16
> round_closest_up(14, 4) = 16
>
> round_closest_down(17, 4) = 16
> round_closest_down(15, 4) = 16
> round_closest_down(14, 4) = 12
>
> Coming back to naming, this is as per existing convention used for naming
> round_up, round_down (notice the `_` being used for macros working with pow of
> 2) and DIV_ROUND_CLOSEST (notice the work `closest` used to specify the answer
> to be nearest to specified value). Naming is a bit subjective, but I
> personally don't think it is a good idea to go away with the existing naming
> convention or go with longer names.
>
> > The patch that changes those to a new one are doubtful to begin with.
> > I.e. need a careful review on the arithmetics side of the change
> > including HW capabilities of handling "closest" results.
>
> This is already tested from my side, in-fact I have posted some of the results
> in cover-letter with these macros [1] :
>
> Regarding hardware capabilities, it uses existing round_up, round_down macros
> underneath which are optimized to handle pow of 2 after modifying the user
> provided argument using addition/subtraction and division, so I don't think it
> should generally a problem with the hardware.
> And I see other macros DIV_ROUND_CLOSEST [3] already using similar operations
> i.e. addition/subtraction and division so don't think it should be a problem
> to keep similar other macros in the same file.

Okay, thank you for elaborating. So, what I would expect in the new version of
the series is that:
- align naming (with the existing round*() macros)
- add examples into commit message of the math.h patch
- add test cases (you need to create lib/math_kunit.c for that)
- elaborate in the commit message of the IPU3 change what you posted above
(some kind of a summary)

> [1]:
> https://gist.github.com/devarsht/de6f5142f678bb1a5338abfd9f814abd#file-v7_jpeg_encoder_crop_validation-L204
> [2]: https://lore.kernel.org/all/[email protected]/
> [3]: https://elixir.bootlin.com/linux/latest/source/include/linux/math.h#L86

--
With Best Regards,
Andy Shevchenko