[PATCH] Make shr to divide by power of 2 (resend)

[PATCH] Make shr to divide by power of 2 (resend)

[Sergey Senozhatsky]

Make an arithmetic right shift to divide by power of 2.

Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
---
diff --git a/drivers/video/console/bitblit.c b/drivers/video/console/bitblit.c
index 69864b1..b816151 100644
--- a/drivers/video/console/bitblit.c
+++ b/drivers/video/console/bitblit.c
@@ -144,7 +144,7 @@ static void bit_putcs(struct vc_data *vc, struct fb_info *info,
 		      int fg, int bg)
 {
 	struct fb_image image;
-	u32 width = (vc->vc_font.width + 7)/8;
+	u32 width = (vc->vc_font.width + 7) >> 3;
 	u32 cellsize = width * vc->vc_font.height;
 	u32 maxcnt = info->pixmap.size/cellsize;
 	u32 scan_align = info->pixmap.scan_align - 1;

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Jiri Slaby]

On 08/15/2009 03:43 PM, Sergey Senozhatsky wrote:
> Make an arithmetic right shift to divide by power of 2.

Why? Is out there a compiler not doing that?

Seems like it should be rather converted to DIV_ROUND_UP.

> Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
> ---
> diff --git a/drivers/video/console/bitblit.c b/drivers/video/console/bitblit.c
> index 69864b1..b816151 100644
> --- a/drivers/video/console/bitblit.c
> +++ b/drivers/video/console/bitblit.c
> @@ -144,7 +144,7 @@ static void bit_putcs(struct vc_data *vc, struct fb_info *info,
>  		      int fg, int bg)
>  {
>  	struct fb_image image;
> -	u32 width = (vc->vc_font.width + 7)/8;
> +	u32 width = (vc->vc_font.width + 7) >> 3;
>  	u32 cellsize = width * vc->vc_font.height;
>  	u32 maxcnt = info->pixmap.size/cellsize;
>  	u32 scan_align = info->pixmap.scan_align - 1;

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Robert P. J. Day]

On Sat, 15 Aug 2009, Jiri Slaby wrote:

> On 08/15/2009 03:43 PM, Sergey Senozhatsky wrote:
> > Make an arithmetic right shift to divide by power of 2.
>
> Why? Is out there a compiler not doing that?
>
> Seems like it should be rather converted to DIV_ROUND_UP.
>
> > Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
> > ---
> > diff --git a/drivers/video/console/bitblit.c b/drivers/video/console/bitblit.c
> > index 69864b1..b816151 100644
> > --- a/drivers/video/console/bitblit.c
> > +++ b/drivers/video/console/bitblit.c
> > @@ -144,7 +144,7 @@ static void bit_putcs(struct vc_data *vc, struct fb_info *info,
> >  		      int fg, int bg)
> >  {
> >  	struct fb_image image;
> > -	u32 width = (vc->vc_font.width + 7)/8;
> > +	u32 width = (vc->vc_font.width + 7) >> 3;
> >  	u32 cellsize = width * vc->vc_font.height;
> >  	u32 maxcnt = info->pixmap.size/cellsize;
> >  	u32 scan_align = info->pixmap.scan_align - 1;

  it does seem like a DIV_ROUND_UP would be better but perhaps another
solution would be to define a meaningful macro name for that
operation.  if that conversion is going to be done regularly, a macro
with an informative name might be in order.  if it's a one-shot
operation, though, not much point.

rday
--

========================================================================
Robert P. J. Day                               Waterloo, Ontario, CANADA

        Linux Consulting, Training and Annoying Kernel Pedantry.

Web page:                                          http://crashcourse.ca
Twitter:                                       http://twitter.com/rpjday
========================================================================

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Sergey Senozhatsky]

[-- Attachment #1: Type: text/plain, Size: 2038 bytes --]

On (08/15/09 09:49), Robert P. J. Day wrote:
> Date: Sat, 15 Aug 2009 09:49:15 -0400 (EDT)
> From: "Robert P. J. Day" <rpjday@crashcourse.ca>
> To: Jiri Slaby <jirislaby@gmail.com>
> cc: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>,
> 	Andrew Morton <akpm@linux-foundation.org>,
> 	linux-kernel@vger.kernel.org
> Subject: Re: [PATCH] Make shr to divide by power of 2 (resend)
> User-Agent: Alpine 2.00 (LFD 1167 2008-08-23)
> 
> On Sat, 15 Aug 2009, Jiri Slaby wrote:
> 
> > On 08/15/2009 03:43 PM, Sergey Senozhatsky wrote:
> > > Make an arithmetic right shift to divide by power of 2.
> >
> > Why? Is out there a compiler not doing that?
> >
> > Seems like it should be rather converted to DIV_ROUND_UP.
> >

                                 
It was duscussed, so I'll just copy paste my answer.
On (08/08/09 09:35), Andi Kleen wrote:
> DIV should be always slower than a SHIFT.
>
> But it has nothing really to do with the CPU. The point is that the compiler
> always selects a suitable one by itself. Rewriting x / 2 to x >> 1 is
> one of the easiest exercises in compiler optimizations.
>
> The only case when the compiler cannot do this easily by itself is
> when the dividend is not a constant.
>

        int width = (vc->vc_font.width + 7) >> 3;

> That said -Os sometimes screws us up on this, but it's still not worth
> doing this change manually.
>

My point is that it should 'look the same'.
I mean there are 5
        int width = (vc->vc_font.width + 7) >> 3;
*not exactly this one, but vc->vc_font.width (+ 7)? >> 3

and _only_ one
        int width = (vc->vc_font.width + 7) / 8;


>   it does seem like a DIV_ROUND_UP would be better but perhaps another
> solution would be to define a meaningful macro name for that
> operation.  if that conversion is going to be done regularly, a macro
> with an informative name might be in order.  if it's a one-shot
> operation, though, not much point.
> 

No, it's not a one-shot.

grep -c '>>' bitblit.c
7

	Sergey

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 315 bytes --]

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Jiri Slaby]

On 08/15/2009 04:12 PM, Sergey Senozhatsky wrote:
> On (08/15/09 09:49), Robert P. J. Day wrote:
>> Date: Sat, 15 Aug 2009 09:49:15 -0400 (EDT)
>> From: "Robert P. J. Day" <rpjday@crashcourse.ca>
>> To: Jiri Slaby <jirislaby@gmail.com>
>> cc: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>,
>> 	Andrew Morton <akpm@linux-foundation.org>,
>> 	linux-kernel@vger.kernel.org
>> Subject: Re: [PATCH] Make shr to divide by power of 2 (resend)
>> User-Agent: Alpine 2.00 (LFD 1167 2008-08-23)
>>
>> On Sat, 15 Aug 2009, Jiri Slaby wrote:
>>
>>> On 08/15/2009 03:43 PM, Sergey Senozhatsky wrote:
>>>> Make an arithmetic right shift to divide by power of 2.
>>>
>>> Why? Is out there a compiler not doing that?
>>>
>>> Seems like it should be rather converted to DIV_ROUND_UP.
>>>
> 
>                                  
> It was duscussed, so I'll just copy paste my answer.
> On (08/08/09 09:35), Andi Kleen wrote:
>> DIV should be always slower than a SHIFT.
>>
>> But it has nothing really to do with the CPU. The point is that the compiler
>> always selects a suitable one by itself. Rewriting x / 2 to x >> 1 is
>> one of the easiest exercises in compiler optimizations.
>>
>> The only case when the compiler cannot do this easily by itself is
>> when the dividend is not a constant.

I think Andi (Cced again) meant divisor. When a divisor is constant, you
can always transform division to some of subs/adds/muls/shifts.

>         int width = (vc->vc_font.width + 7) >> 3;
> 
>> That said -Os sometimes screws us up on this, but it's still not worth
>> doing this change manually.
>>
> 
> My point is that it should 'look the same'.
> I mean there are 5
>         int width = (vc->vc_font.width + 7) >> 3;
> *not exactly this one, but vc->vc_font.width (+ 7)? >> 3
> 
> and _only_ one
>         int width = (vc->vc_font.width + 7) / 8;
> 
> 
>>   it does seem like a DIV_ROUND_UP would be better but perhaps another
>> solution would be to define a meaningful macro name for that
>> operation.  if that conversion is going to be done regularly, a macro
>> with an informative name might be in order.  if it's a one-shot
>> operation, though, not much point.
>>
> 
> No, it's not a one-shot.
> 
> grep -c '>>' bitblit.c
> 7

Then please use DIV_ROUND_UP macro (or whatever alias) all over the place.

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Sergey Senozhatsky]

[-- Attachment #1: Type: text/plain, Size: 2714 bytes --]

On (08/15/09 22:42), Jiri Slaby wrote:
> On 08/15/2009 04:12 PM, Sergey Senozhatsky wrote:
> > On (08/15/09 09:49), Robert P. J. Day wrote:
> >> On Sat, 15 Aug 2009, Jiri Slaby wrote:
> >>
> >>> On 08/15/2009 03:43 PM, Sergey Senozhatsky wrote:
> >>>> Make an arithmetic right shift to divide by power of 2.
> >>>
> >>> Why? Is out there a compiler not doing that?
> >>>
> >>> Seems like it should be rather converted to DIV_ROUND_UP.
> >>>
> > 
> >                                  
> > It was duscussed, so I'll just copy paste my answer.
> > On (08/08/09 09:35), Andi Kleen wrote:
> >> DIV should be always slower than a SHIFT.
> >>
> >> But it has nothing really to do with the CPU. The point is that the compiler
> >> always selects a suitable one by itself. Rewriting x / 2 to x >> 1 is
> >> one of the easiest exercises in compiler optimizations.
> >>
> >> The only case when the compiler cannot do this easily by itself is
> >> when the dividend is not a constant.
> 
> I think Andi (Cced again) meant divisor. When a divisor is constant, you
> can always transform division to some of subs/adds/muls/shifts.

Cced  Andi Kleen <andi@firstfloor.org>


> 
> >         int width = (vc->vc_font.width + 7) >> 3;
> > 
> >> That said -Os sometimes screws us up on this, but it's still not worth
> >> doing this change manually.
> >>
> > 
> > My point is that it should 'look the same'.
> > I mean there are 5
> >         int width = (vc->vc_font.width + 7) >> 3;
> > *not exactly this one, but vc->vc_font.width (+ 7)? >> 3
> > 
> > and _only_ one
> >         int width = (vc->vc_font.width + 7) / 8;
> > 
> > 
> >>   it does seem like a DIV_ROUND_UP would be better but perhaps another
> >> solution would be to define a meaningful macro name for that
> >> operation.  if that conversion is going to be done regularly, a macro
> >> with an informative name might be in order.  if it's a one-shot
> >> operation, though, not much point.
> >>
> > 
> > No, it's not a one-shot.
> > 
> > grep -c '>>' bitblit.c
> > 7
> 
> Then please use DIV_ROUND_UP macro (or whatever alias) all over the place.
> 

Sorry, once again (just to clear).

There are different shr/shl operations in bitblit.c. Like,
#1
cur_height = vc->vc_font.height >> 1
cur_height = (vc->vc_font.height << 1)/3;
c |= c >> 1;
u32 idx = vc->vc_font.width >> 3;
etc.

So, should I convert it to something like:
#2
cur_height = DIV_XXX(vc->vc_font.height, 2)
cur_height = DIV_XXX( MUL_XXX(vc->vc_font.height, 2), 3); or cur_height = DIV_XXX( (vc->vc_font.height * 2), 3);
c |= DIV_XXX(c, 1);
u32 idx = DIV_XXX(vc->vc_font.width, 8);

#1 is better-looking I think.

	Sergey

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 315 bytes --]

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Jiri Slaby]

On 08/16/2009 11:14 AM, Sergey Senozhatsky wrote:
> There are different shr/shl operations in bitblit.c. Like,
> #1
> cur_height = vc->vc_font.height >> 1
> cur_height = (vc->vc_font.height << 1)/3;
> c |= c >> 1;
> u32 idx = vc->vc_font.width >> 3;
> etc.
> 
> So, should I convert it to something like:

Not at all. I was writing about about (X + 7) / 8 [or >> 3] which is
DIV_ROUND_UP(X, 8).

> #2
> cur_height = DIV_XXX(vc->vc_font.height, 2)
> cur_height = DIV_XXX( MUL_XXX(vc->vc_font.height, 2), 3); or cur_height = DIV_XXX( (vc->vc_font.height * 2), 3);
> c |= DIV_XXX(c, 1);
> u32 idx = DIV_XXX(vc->vc_font.width, 8);
> 
> #1 is better-looking I think.

Agreed. I would write it without shifts though. But we were talking
about the roundup case not about the shifts all over the code.

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Sergey Senozhatsky]

[-- Attachment #1: Type: text/plain, Size: 1249 bytes --]

On (08/17/09 09:15), Jiri Slaby wrote:
> On 08/16/2009 11:14 AM, Sergey Senozhatsky wrote:
> > There are different shr/shl operations in bitblit.c. Like,
> > #1
> > cur_height = vc->vc_font.height >> 1
> > cur_height = (vc->vc_font.height << 1)/3;
> > c |= c >> 1;
> > u32 idx = vc->vc_font.width >> 3;
> > etc.
> > 
> > So, should I convert it to something like:
> 
> Not at all. I was writing about about (X + 7) / 8 [or >> 3] which is
> DIV_ROUND_UP(X, 8).
> 
As far as I can understand: 
DIV_ROUND_UP(61, 8):
(111101 + 111) >> 3 -> 1000 == 8

(int)(61/8) == 7

So, we need not DIV_ROUND_UP but (let it be) DIV_SHR (a,b) (a) >> (b);
In that case cur_height = vc->vc_font.height >> 2 should be cur_height = DIV_SHR(vc->vc_font.height, 1).
And this is kind of obfuscation I think.

> > #2
> > cur_height = DIV_XXX(vc->vc_font.height, 2)
> > cur_height = DIV_XXX( MUL_XXX(vc->vc_font.height, 2), 3); or cur_height = DIV_XXX( (vc->vc_font.height * 2), 3);
> > c |= DIV_XXX(c, 1);
> > u32 idx = DIV_XXX(vc->vc_font.width, 8);
> > 
> > #1 is better-looking I think.
> 
> Agreed. I would write it without shifts though. But we were talking
> about the roundup case not about the shifts all over the code.
> 

	Sergey

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 315 bytes --]

[PATCH 1/1] VIDEO: console, use DIV_ROUND_UP

[Jiri Slaby]

On 08/17/2009 09:31 AM, Sergey Senozhatsky wrote:
> On (08/17/09 09:15), Jiri Slaby wrote:
>> Not at all. I was writing about about (X + 7) / 8 [or >> 3] which is
>> DIV_ROUND_UP(X, 8).
>>
> As far as I can understand: 
> DIV_ROUND_UP(61, 8):
> (111101 + 111) >> 3 -> 1000 == 8
> 
> (int)(61/8) == 7

Yeah, that's why there is the ROUND_UP keyword in the macro.

I mean this:
--
Use DIV_ROUND_UP explicitly instead of manual shifts and adds. It makes
the code more readable and consistent (sometimes there were shifts,
sometimes divs).

There is no change on the assembly level (compilers should do the right
job).

Signed-off-by: Jiri Slaby <jirislaby@gmail.com>
---
 drivers/video/console/bitblit.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/drivers/video/console/bitblit.c b/drivers/video/console/bitblit.c
index 69864b1..6b7c8fb 100644
--- a/drivers/video/console/bitblit.c
+++ b/drivers/video/console/bitblit.c
@@ -25,7 +25,7 @@ static inline void update_attr(u8 *dst, u8 *src, int attribute,
 			       struct vc_data *vc)
 {
 	int i, offset = (vc->vc_font.height < 10) ? 1 : 2;
-	int width = (vc->vc_font.width + 7) >> 3;
+	int width = DIV_ROUND_UP(vc->vc_font.width, 8);
 	unsigned int cellsize = vc->vc_font.height * width;
 	u8 c;
 
@@ -144,7 +144,7 @@ static void bit_putcs(struct vc_data *vc, struct fb_info *info,
 		      int fg, int bg)
 {
 	struct fb_image image;
-	u32 width = (vc->vc_font.width + 7)/8;
+	u32 width = DIV_ROUND_UP(vc->vc_font.width, 8);
 	u32 cellsize = width * vc->vc_font.height;
 	u32 maxcnt = info->pixmap.size/cellsize;
 	u32 scan_align = info->pixmap.scan_align - 1;
@@ -173,7 +173,7 @@ static void bit_putcs(struct vc_data *vc, struct fb_info *info,
 			cnt = count;
 
 		image.width = vc->vc_font.width * cnt;
-		pitch = ((image.width + 7) >> 3) + scan_align;
+		pitch = DIV_ROUND_UP(image.width, 8) + scan_align;
 		pitch &= ~scan_align;
 		size = pitch * image.height + buf_align;
 		size &= ~buf_align;
@@ -239,7 +239,7 @@ static void bit_cursor(struct vc_data *vc, struct fb_info *info, int mode,
 	struct fb_cursor cursor;
 	struct fbcon_ops *ops = info->fbcon_par;
 	unsigned short charmask = vc->vc_hi_font_mask ? 0x1ff : 0xff;
-	int w = (vc->vc_font.width + 7) >> 3, c;
+	int w = DIV_ROUND_UP(vc->vc_font.width, 8), c;
 	int y = real_y(ops->p, vc->vc_y);
 	int attribute, use_sw = (vc->vc_cursor_type & 0x10);
 	int err = 1;
-- 
1.6.3.3

Re: [PATCH 1/1] VIDEO: console, use DIV_ROUND_UP

[Sergey Senozhatsky]

[-- Attachment #1: Type: text/plain, Size: 1657 bytes --]

On (08/17/09 09:48), Jiri Slaby wrote:
> On 08/17/2009 09:31 AM, Sergey Senozhatsky wrote:
> > On (08/17/09 09:15), Jiri Slaby wrote:
> >> Not at all. I was writing about about (X + 7) / 8 [or >> 3] which is
> >> DIV_ROUND_UP(X, 8).
> >>
> > As far as I can understand: 
> > DIV_ROUND_UP(61, 8):
> > (111101 + 111) >> 3 -> 1000 == 8
> > 
> > (int)(61/8) == 7
> 
> Yeah, that's why there is the ROUND_UP keyword in the macro.
> 
> I mean this:
> --
> Use DIV_ROUND_UP explicitly instead of manual shifts and adds. It makes
> the code more readable and consistent (sometimes there were shifts,
> sometimes divs).
> 
> There is no change on the assembly level (compilers should do the right
> job).
> 
> Signed-off-by: Jiri Slaby <jirislaby@gmail.com>
> ---
>  drivers/video/console/bitblit.c |    8 ++++----
>  1 files changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/drivers/video/console/bitblit.c b/drivers/video/console/bitblit.c
> index 69864b1..6b7c8fb 100644
> --- a/drivers/video/console/bitblit.c
> +++ b/drivers/video/console/bitblit.c
> @@ -25,7 +25,7 @@ static inline void update_attr(u8 *dst, u8 *src, int attribute,
>  			       struct vc_data *vc)
>  {
>  	int i, offset = (vc->vc_font.height < 10) ? 1 : 2;
> -	int width = (vc->vc_font.width + 7) >> 3;
> +	int width = DIV_ROUND_UP(vc->vc_font.width, 8);

So... In general, ((vc->vc_font.width + 7) >> 3) ==  DIV_ROUND_UP(vc->vc_font.width, 8) - 1;
That means:
unsigned int cellsize = vc->vc_font.height * width;  now is  unsigned int cellsize = vc->vc_font.height * (width + 1);

Are you sure we really can use DIV_ROUND_UP?

	Sergey


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 315 bytes --]

Re: [PATCH 1/1] VIDEO: console, use DIV_ROUND_UP

[Jiri Slaby]

On 08/17/2009 10:00 AM, Sergey Senozhatsky wrote:
> So... In general, ((vc->vc_font.width + 7) >> 3) ==  DIV_ROUND_UP(vc->vc_font.width, 8) - 1;

?

#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))

DIV_ROUND_UP(vc->vc_font.width, 8) expands to:
(((vc->vc_font.width) + (8) - 1) / (8))
which is pretty printed:
(vc->vc_font.width + 7) / 8
and that's equivalent to:
(vc->vc_font.width + 7) >> 3

Correct?

> Are you sure we really can use DIV_ROUND_UP?

Yeah, pretty sure.

Re: [PATCH 1/1] VIDEO: console, use DIV_ROUND_UP

[Sergey Senozhatsky]

[-- Attachment #1: Type: text/plain, Size: 691 bytes --]

On (08/17/09 10:00), Jiri Slaby wrote:
> On 08/17/2009 10:00 AM, Sergey Senozhatsky wrote:
> > So... In general, ((vc->vc_font.width + 7) >> 3) ==  DIV_ROUND_UP(vc->vc_font.width, 8) - 1;
> 
> ?
> 
Oops, silly me. Somehow I thought about
DIV_ROUND_UP((vc->vc_font.width + 7) , 8). My fault. Sorry.

> #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
> 
> DIV_ROUND_UP(vc->vc_font.width, 8) expands to:
> (((vc->vc_font.width) + (8) - 1) / (8))
> which is pretty printed:
> (vc->vc_font.width + 7) / 8
> and that's equivalent to:
> (vc->vc_font.width + 7) >> 3
> 
> Correct?
Right.

> 
> > Are you sure we really can use DIV_ROUND_UP?
> 
> Yeah, pretty sure.
> 
OK.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 315 bytes --]

Re: [PATCH 1/1] VIDEO: console, use DIV_ROUND_UP

[Jiri Slaby]

On 08/17/2009 10:08 AM, Sergey Senozhatsky wrote:
> Oops, silly me. Somehow I thought about
> DIV_ROUND_UP((vc->vc_font.width + 7) , 8). My fault. Sorry.

No problem at all. We converged our thoughts, that's success.

Re: [PATCH] Make shr to divide by power of 2 (resend)

[Sergey Senozhatsky]

[-- Attachment #1: Type: text/plain, Size: 625 bytes --]

On (08/15/09 09:49), Robert P. J. Day wrote:
>   it does seem like a DIV_ROUND_UP would be better but perhaps another
> solution would be to define a meaningful macro name for that
> operation.  if that conversion is going to be done regularly, a macro
> with an informative name might be in order.  if it's a one-shot
> operation, though, not much point.
> 

There are different shr/shl operations in bitblit.c. Like,
cur_height = vc->vc_font.height >> 1
cur_height = (vc->vc_font.height << 1)/3;
c |= c >> 1;
u32 idx = vc->vc_font.width >> 3;
etc.

So I don't think we really need a macros here.

	Sergey

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 315 bytes --]