[PATCH] b43: LP-PHY: Fix and simplify Qdiv roundup

[PATCH] b43: LP-PHY: Fix and simplify Qdiv roundup

[Gábor Stefanik]

The Qdiv roundup routine is essentially a fixed-point
division algorithm, using only integer math.
However, the version in the specs had a major error
that has been recently fixed (a missing quotient++).

Replace Qdiv roundup with a rewritten, simplified version.

Signed-off-by: Gábor Stefanik <netrolller.3d@gmail.com>
---
 drivers/net/wireless/b43/phy_lp.c |   14 ++++----------
 1 files changed, 4 insertions(+), 10 deletions(-)

diff --git a/drivers/net/wireless/b43/phy_lp.c b/drivers/net/wireless/b43/phy_lp.c
index 7e70c07..d0280d5 100644
--- a/drivers/net/wireless/b43/phy_lp.c
+++ b/drivers/net/wireless/b43/phy_lp.c
@@ -1034,7 +1034,7 @@ static int lpphy_loopback(struct b43_wldev *dev)
 
 static u32 lpphy_qdiv_roundup(u32 dividend, u32 divisor, u8 precision)
 {
-	u32 quotient, remainder, rbit, roundup, tmp;
+	u32 quotient, remainder;
 
 	if (divisor == 0)
 		return 0;
@@ -1042,20 +1042,14 @@ static u32 lpphy_qdiv_roundup(u32 dividend, u32 divisor, u8 precision)
 	quotient = dividend / divisor;
 	remainder = dividend % divisor;
 
-	rbit = divisor & 0x1;
-	roundup = (divisor >> 1) + rbit;
-
 	while (precision != 0) {
-		tmp = remainder - roundup;
 		quotient <<= 1;
-		if (remainder >= roundup)
-			remainder = (tmp << 1) + rbit;
-		else
-			remainder <<= 1;
+		quotient |= (remainder << 1) / divisor;
+		remainder = (remainder << 1) % divisor;
 		precision--;
 	}
 
-	if (remainder >= roundup)
+	if (remainder << 1 >= divisor)
 		quotient++;
 
 	return quotient;
-- 
1.5.6

Re: [PATCH] b43: LP-PHY: Fix and simplify Qdiv roundup

[Bob Copeland]

2009/8/25 Gábor Stefanik <netrolller.3d@gmail.com>:
> The Qdiv roundup routine is essentially a fixed-point
> division algorithm, using only integer math.
> However, the version in the specs had a major error
> that has been recently fixed (a missing quotient++).
>
> Replace Qdiv roundup with a rewritten, simplified version.

Hi!

> @@ -1042,20 +1042,14 @@ static u32 lpphy_qdiv_roundup(u32 dividend, u32 divisor, u8 precision)
>        quotient = dividend / divisor;
>        remainder = dividend % divisor;
>
> -       rbit = divisor & 0x1;
> -       roundup = (divisor >> 1) + rbit;
> -
>        while (precision != 0) {
> -               tmp = remainder - roundup;
>                quotient <<= 1;
> -               if (remainder >= roundup)
> -                       remainder = (tmp << 1) + rbit;
> -               else
> -                       remainder <<= 1;
> +               quotient |= (remainder << 1) / divisor;
> +               remainder = (remainder << 1) % divisor;
>                precision--;
>        }

Unless precision is 0, this just added a bunch of divides into
the inner loop, which might be a big surprise to anyone expecting
this to be fast...

-- 
Bob Copeland %% www.bobcopeland.com

Re: [PATCH] b43: LP-PHY: Fix and simplify Qdiv roundup

[Michael Buesch]

On Tuesday 25 August 2009 16:40:17 Gábor Stefanik wrote:
> The Qdiv roundup routine is essentially a fixed-point
> division algorithm, using only integer math.
> However, the version in the specs had a major error
> that has been recently fixed (a missing quotient++).
> 
> Replace Qdiv roundup with a rewritten, simplified version.

Don't we have some sort of standard library function somewhere in
the kernel for this? If not, what about creating one?

> 
> Signed-off-by: Gábor Stefanik <netrolller.3d@gmail.com>
> ---
>  drivers/net/wireless/b43/phy_lp.c |   14 ++++----------
>  1 files changed, 4 insertions(+), 10 deletions(-)
> 
> diff --git a/drivers/net/wireless/b43/phy_lp.c b/drivers/net/wireless/b43/phy_lp.c
> index 7e70c07..d0280d5 100644
> --- a/drivers/net/wireless/b43/phy_lp.c
> +++ b/drivers/net/wireless/b43/phy_lp.c
> @@ -1034,7 +1034,7 @@ static int lpphy_loopback(struct b43_wldev *dev)
>  
>  static u32 lpphy_qdiv_roundup(u32 dividend, u32 divisor, u8 precision)
>  {
> -	u32 quotient, remainder, rbit, roundup, tmp;
> +	u32 quotient, remainder;
>  
>  	if (divisor == 0)
>  		return 0;
> @@ -1042,20 +1042,14 @@ static u32 lpphy_qdiv_roundup(u32 dividend, u32 divisor, u8 precision)
>  	quotient = dividend / divisor;
>  	remainder = dividend % divisor;
>  
> -	rbit = divisor & 0x1;
> -	roundup = (divisor >> 1) + rbit;
> -
>  	while (precision != 0) {
> -		tmp = remainder - roundup;
>  		quotient <<= 1;
> -		if (remainder >= roundup)
> -			remainder = (tmp << 1) + rbit;
> -		else
> -			remainder <<= 1;
> +		quotient |= (remainder << 1) / divisor;
> +		remainder = (remainder << 1) % divisor;
>  		precision--;
>  	}
>  
> -	if (remainder >= roundup)
> +	if (remainder << 1 >= divisor)
>  		quotient++;
>  
>  	return quotient;



-- 
Greetings, Michael.