Skip to contentSkip to conversation

math.h Add macros to round to closest specified power of 2

PATCH Superseded Devarsh Thakkar 4 participants 13 messages May 9, 2024 – May 13, 2024 Media (V4L/DVB)

v7 of 14 Superseded Latest is v14 →

lore
Share & tools
lore
#0 lore raw

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

---
V1->V6 (No change, patch introduced in V7)

---
 include/linux/math.h | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
include/linux/math.h +36 -0
index dd4152711de7..82ee3265c910 100644
@@ -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) \
Signature · 1 line
2.39.1
#1 lore raw
Quoted 1 line · Devarsh Thakkar

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.

Quoted 1 line

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.)

Quoted 1 line

round_closest_up and round_closest_down which round up to nearest multiple

round_closest_up() and round_closest_down()

Quoted 2 lines

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().

Quoted 6 lines

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.

Quoted 4 lines

---
V1->V6 (No change, patch introduced in V7)
---

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#2 lore raw
Quoted 13 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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.

Quoted 1 line

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.)

Quoted 1 line

round_closest_up and round_closest_down which round up to nearest multiple

Quoted 8 lines

round_closest_up() and round_closest_down()

Quoted 2 lines

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.

Quoted 15 lines
Quoted 7 lines

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.

Quoted 4 lines

---
V1->V6 (No change, patch introduced in V7)
---

Signature · 1 line
Jani Nikula, Intel
#3 lore raw
Quoted 20 lines · Jani Nikula
Quoted 19 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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.

Quoted 1 line

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.)

Quoted 1 line

round_closest_up and round_closest_down which round up to nearest multiple

round_closest_up() and round_closest_down()

Quoted 2 lines

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

Quoted 7 lines
Quoted 2 lines

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

Quoted 2 lines

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

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#4 lore raw
In reply to Jani Nikula

Hi Jani,

Thanks for the quick review.

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

[...]

Quoted 8 lines

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

#5 lore raw
Quoted 1 line · Devarsh Thakkar

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

[...]

Quoted 14 lines
Quoted 7 lines

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

Quoted 8 lines
    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.

Quoted 7 lines

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.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#6 lore raw

Hi Andy,

Quoted 34 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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

[...]

Quoted 14 lines
Quoted 7 lines

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

Quoted 8 lines
    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.

Quoted 3 lines

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

Quoted 9 lines
Quoted 4 lines

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.

Quoted 4 lines

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

#7 lore raw
Quoted 3 lines · Devarsh Thakkar
Quoted 2 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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

[...]

Quoted 69 lines
Quoted 29 lines
Quoted 14 lines
Quoted 7 lines

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

Quoted 8 lines
    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.

Quoted 3 lines

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

Quoted 8 lines
Quoted 4 lines

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.

Quoted 3 lines

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] :

Quoted 7 lines

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)

Quoted 4 lines

[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

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#8 lore raw

Hi Andy,

Quoted 7 lines · Andy Shevchenko
Quoted 3 lines · Devarsh Thakkar
Quoted 2 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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?

Quoted 1 line

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

Agreed

Quoted 1 line

- add test cases (you need to create lib/math_kunit.c for that)

Agreed.

Quoted 2 lines

- 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

#9 lore raw
Quoted 5 lines · Devarsh Thakkar
Quoted 4 lines · Andy Shevchenko
Quoted 3 lines · Devarsh Thakkar
Quoted 2 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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

[...]

Quoted 6 lines
Quoted 1 line

- 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])

Quoted 6 lines

"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!

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#10 lore raw
In reply to Andy Shevchenko

Hi Andy,

Thanks for the quick review.

Quoted 5 lines · Andy Shevchenko
Quoted 1 line · Devarsh Thakkar

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.

Quoted 6 lines
Quoted 1 line

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.

Quoted 11 lines
Quoted 1 line

round_closest_up and round_closest_down which round up to nearest multiple

round_closest_up() and round_closest_down()

Quoted 2 lines

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

#12 lore raw
Quoted 3 lines · Alexey Dobriyan

I think

	roundup(x, 1 << n)

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

Quoted 1 line

is more readable.

Signature · 2 lines
With Best Regards,
Andy Shevchenko