Make shr to divide by power of 2 (resend)

PATCH In review Sergey Senozhatsky 3 participants 14 messages Aug 15, 2009 – Aug 17, 2009

Subsystems (2)

Framebuffer layer Console

lore

Share & tools

lore

Sergey Senozhatsky

author

2009-08-15 13:41 UTC #0 lore raw

PATCH 1/1 Make shr to divide by power of 2 (resend)

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

Signed-off-by Sergey Senozhatsky <[email protected]>

---

drivers/video/console/bitblit.c +1 -1

index 69864b1..b816151 100644
@@ -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;

Jiri Slaby

2009-08-15 13:48 UTC #1 lore raw

Quoted 1 line · Sergey Senozhatsky

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.

Quoted 15 lines

Signed-off-by Sergey Senozhatsky <[email protected]>

---

drivers/video/console/bitblit.c +1 -1

index 69864b1..b816151 100644
@@ -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;

Robert P. J. Day

2009-08-15 13:52 UTC #2 lore raw

Quoted 7 lines · Jiri Slaby

Quoted 1 line · Sergey Senozhatsky
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.

Quoted 15 lines

Quoted 7 lines
Signed-off-by Sergey Senozhatsky <[email protected]>
---
drivers/video/console/bitblit.c +0 -0
index 69864b1..b816151 100644
drivers/video/console/bitblit.c static void bit_putcs(struct vc_data *vc, struct fb_info *info, · line 150
Quoted 8 lines
drivers/video/console/bitblit.c +1 -1
@@ -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

========================================================================

Sergey Senozhatsky

author

2009-08-15 14:09 UTC #3 lore raw

Quoted 9 lines · Robert P. J. Day

Date: Sat, 15 Aug 2009 09:49:15 -0400 (EDT)
From: "Robert P. J. Day" <[email protected]>
To: Jiri Slaby <[email protected]>
cc: Sergey Senozhatsky <[email protected]>,
Andrew Morton <[email protected]>, [email protected]
Subject: Re: [PATCH] Make shr to divide by power of 2 (resend)
User-Agent: Alpine 2.00 (LFD 1167 2008-08-23)

Quoted 9 lines

Quoted 7 lines · Jiri Slaby
Quoted 1 line · Sergey Senozhatsky
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.

Quoted 9 lines · Andi Kleen

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;

Quoted 3 lines

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;

Quoted 6 lines

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

Jiri Slaby

2009-08-15 20:42 UTC #4 lore raw

Quoted 15 lines · Sergey Senozhatsky

Quoted 14 lines · Robert P. J. Day
Date: Sat, 15 Aug 2009 09:49:15 -0400 (EDT)
From: "Robert P. J. Day" <[email protected]>
To: Jiri Slaby <[email protected]>
cc: Sergey Senozhatsky <[email protected]>,
Andrew Morton <[email protected]>, [email protected]
Subject: Re: [PATCH] Make shr to divide by power of 2 (resend)
User-Agent: Alpine 2.00 (LFD 1167 2008-08-23)
Quoted 3 lines · Jiri Slaby
Quoted 1 line · Sergey Senozhatsky
Make an arithmetic right shift to divide by power of 2.

Quoted 16 lines

Quoted 4 lines
Quoted 4 lines
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.
Quoted 8 lines · Andi Kleen
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.

Quoted 22 lines

        int width = (vc->vc_font.width + 7) >> 3;
Quoted 3 lines
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;
Quoted 6 lines
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.

Quoted 4 lines

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.

Sergey Senozhatsky

author

2009-08-16 09:11 UTC #5 lore raw

Quoted 21 lines · Jiri Slaby

Quoted 20 lines · Sergey Senozhatsky
Quoted 9 lines · Robert P. J. Day
Quoted 7 lines · Jiri Slaby
Quoted 1 line · Sergey Senozhatsky
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.
Quoted 6 lines · Andi Kleen
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.

Quoted 5 lines

Quoted 2 lines
Quoted 2 lines
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 <[email protected]>

Quoted 23 lines

Quoted 23 lines
        int width = (vc->vc_font.width + 7) >> 3;
Quoted 3 lines
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;
Quoted 6 lines
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.

Quoted 7 lines

Quoted 4 lines
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

Jiri Slaby

2009-08-17 07:15 UTC #6 lore raw

Quoted 9 lines · Sergey Senozhatsky

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

Quoted 7 lines

#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 Senozhatsky

author

2009-08-17 07:28 UTC #7 lore raw

Quoted 9 lines · Jiri Slaby

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

Quoted 5 lines

Quoted 1 line
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.

Quoted 11 lines

Quoted 7 lines
#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

Jiri Slaby

2009-08-17 07:48 UTC #8 lore raw

PATCH 1/1 VIDEO: console, use DIV_ROUND_UP

Quoted 9 lines · Sergey Senozhatsky

Quoted 3 lines · Jiri Slaby
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 <[email protected]>

---
 drivers/video/console/bitblit.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

drivers/video/console/bitblit.c +4 -4

index 69864b1..6b7c8fb 100644
@@ -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;

Signature · 1 line

1.6.3.3

Sergey Senozhatsky

author

2009-08-17 07:57 UTC #9 lore raw

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

Quoted 32 lines · Jiri Slaby

Quoted 9 lines · Sergey Senozhatsky
Quoted 3 lines · Jiri Slaby
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 <[email protected]>
---
 drivers/video/console/bitblit.c |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)
drivers/video/console/bitblit.c +0 -0
index 69864b1..6b7c8fb 100644

drivers/video/console/bitblit.c static inline void update_attr(u8 *dst, u8 *src, int attribute, · line 28

Quoted 5 lines

drivers/video/console/bitblit.c +1 -1

@@ -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

Jiri Slaby

2009-08-17 08:00 UTC #10 lore raw

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

Quoted 1 line · Sergey Senozhatsky

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?

Quoted 1 line

Are you sure we really can use DIV_ROUND_UP?

Yeah, pretty sure.

Sergey Senozhatsky

author

2009-08-17 08:05 UTC #11 lore raw

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

Quoted 5 lines · Jiri Slaby

Quoted 1 line · Sergey Senozhatsky
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.

Quoted 10 lines

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

Quoted 5 lines

Quoted 2 lines
Are you sure we really can use DIV_ROUND_UP?
Yeah, pretty sure.

OK.

Jiri Slaby

2009-08-17 08:11 UTC #12 lore raw

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

Quoted 2 lines · Sergey Senozhatsky

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.

Sergey Senozhatsky

author

2009-08-15 14:30 UTC #13 lore raw

In reply to Robert P. J. Day

Quoted 6 lines · Robert P. J. Day

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