[PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Justin Madru]

I was style fixing some code when I ran into this code.
It seems like the code could be reduced, by factoring the expression.
But this results in a very simple expression.

Am I assuming something wrong? Or is this a bug in the original code?
This doesn't look right because the assignment of s_move[i] has no mention
of the loop counter.

Justin

------

the code was looping, seting s_move[i] to the following calculations

if (actual_step >= 0)
        s_move[i] = ((((i + 1) * gain + 0x200) - (i * gain + 0x200)) / 0x400);
else
        s_move[i] = ((((i + 1) * gain - 0x200) - (i * gain - 0x200)) / 0x400);

but, by factoring the expression, it can be shown that they both reduce
to a very simple expression:

        s_move[i] = gain / 0x400;

Signed-off-by: Justin Madru <jdm64@gawab.com>
---
 drivers/staging/dream/camera/s5k3e2fx.c |   10 +++-------
 1 files changed, 3 insertions(+), 7 deletions(-)

diff --git a/drivers/staging/dream/camera/s5k3e2fx.c b/drivers/staging/dream/camera/s5k3e2fx.c
index f0e49be..d205a2d 100644
--- a/drivers/staging/dream/camera/s5k3e2fx.c
+++ b/drivers/staging/dream/camera/s5k3e2fx.c
@@ -1092,14 +1092,10 @@ static int32_t s5k3e2fx_move_focus(int direction, int32_t num_steps)
 
 	actual_step = step_direction * (int16_t)num_steps;
 	pos_offset = init_code + s5k3e2fx_ctrl->curr_lens_pos;
-	gain = actual_step * 0x400 / 5;
+	gain = actual_step / 5;
 
-	for (i = 0; i <= 4; i++) {
-		if (actual_step >= 0)
-			s_move[i] = ((((i+1)*gain+0x200) - (i*gain+0x200))/0x400);
-		else
-			s_move[i] = ((((i+1)*gain-0x200) - (i*gain-0x200))/0x400);
-	}
+	for (i = 0; i <= 4; i++)
+		s_move[i] = gain;
 
 	/* Ring Damping Code */
 	for (i = 0; i <= 4; i++) {
-- 
1.6.5.4

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Dan Carpenter]

On Sat, Dec 05, 2009 at 06:03:20PM -0800, Justin Madru wrote:
> I was style fixing some code when I ran into this code.
> It seems like the code could be reduced, by factoring the expression.
> But this results in a very simple expression.
> 
> Am I assuming something wrong? Or is this a bug in the original code?
> This doesn't look right because the assignment of s_move[i] has no mention
> of the loop counter.
> 
> Justin
> 
> ------
> 
> the code was looping, seting s_move[i] to the following calculations
> 
> if (actual_step >= 0)
>         s_move[i] = ((((i + 1) * gain + 0x200) - (i * gain + 0x200)) / 0x400);
> else
>         s_move[i] = ((((i + 1) * gain - 0x200) - (i * gain - 0x200)) / 0x400);
> 
> but, by factoring the expression, it can be shown that they both reduce
> to a very simple expression:
> 
>         s_move[i] = gain / 0x400;
> 

Heh.

Looks like an improvement to me.

If gain were 16 bits instead of 32 I would think the "* 0x400 / 0x400" was 
designed to mask out the highest 10 bits.

Acked-by:  Dan Carpenter <error27@gmail.com>

regards,
dan carpenter

> Signed-off-by: Justin Madru <jdm64@gawab.com>
> ---
>  drivers/staging/dream/camera/s5k3e2fx.c |   10 +++-------
>  1 files changed, 3 insertions(+), 7 deletions(-)
> 
> diff --git a/drivers/staging/dream/camera/s5k3e2fx.c b/drivers/staging/dream/camera/s5k3e2fx.c
> index f0e49be..d205a2d 100644
> --- a/drivers/staging/dream/camera/s5k3e2fx.c
> +++ b/drivers/staging/dream/camera/s5k3e2fx.c
> @@ -1092,14 +1092,10 @@ static int32_t s5k3e2fx_move_focus(int direction, int32_t num_steps)
>  
>  	actual_step = step_direction * (int16_t)num_steps;
>  	pos_offset = init_code + s5k3e2fx_ctrl->curr_lens_pos;
> -	gain = actual_step * 0x400 / 5;
> +	gain = actual_step / 5;
>  
> -	for (i = 0; i <= 4; i++) {
> -		if (actual_step >= 0)
> -			s_move[i] = ((((i+1)*gain+0x200) - (i*gain+0x200))/0x400);
> -		else
> -			s_move[i] = ((((i+1)*gain-0x200) - (i*gain-0x200))/0x400);
> -	}
> +	for (i = 0; i <= 4; i++)
> +		s_move[i] = gain;
>  
>  	/* Ring Damping Code */
>  	for (i = 0; i <= 4; i++) {
> -- 
> 1.6.5.4
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Justin Madru]

On 12/09/2009 01:57 AM, Dan Carpenter wrote:
> On Sat, Dec 05, 2009 at 06:03:20PM -0800, Justin Madru wrote:
>    
>> I was style fixing some code when I ran into this code.
>> It seems like the code could be reduced, by factoring the expression.
>> But this results in a very simple expression.
>>
>> Am I assuming something wrong? Or is this a bug in the original code?
>> This doesn't look right because the assignment of s_move[i] has no mention
>> of the loop counter.
>>
>> Justin
>>
>> ------
>>
>> the code was looping, seting s_move[i] to the following calculations
>>
>> if (actual_step>= 0)
>>          s_move[i] = ((((i + 1) * gain + 0x200) - (i * gain + 0x200)) / 0x400);
>> else
>>          s_move[i] = ((((i + 1) * gain - 0x200) - (i * gain - 0x200)) / 0x400);
>>
>> but, by factoring the expression, it can be shown that they both reduce
>> to a very simple expression:
>>
>>          s_move[i] = gain / 0x400;
>>
>>      
> Heh.
>
> Looks like an improvement to me.
>
> If gain were 16 bits instead of 32 I would think the "* 0x400 / 0x400" was
> designed to mask out the highest 10 bits.
>
> Acked-by:  Dan Carpenter<error27@gmail.com>
>
> regards,
> dan carpenter
>
>    
>> Signed-off-by: Justin Madru<jdm64@gawab.com>
>> ---
>>   drivers/staging/dream/camera/s5k3e2fx.c |   10 +++-------
>>   1 files changed, 3 insertions(+), 7 deletions(-)
>>
>> diff --git a/drivers/staging/dream/camera/s5k3e2fx.c b/drivers/staging/dream/camera/s5k3e2fx.c
>> index f0e49be..d205a2d 100644
>> --- a/drivers/staging/dream/camera/s5k3e2fx.c
>> +++ b/drivers/staging/dream/camera/s5k3e2fx.c
>> @@ -1092,14 +1092,10 @@ static int32_t s5k3e2fx_move_focus(int direction, int32_t num_steps)
>>
>>   	actual_step = step_direction * (int16_t)num_steps;
>>   	pos_offset = init_code + s5k3e2fx_ctrl->curr_lens_pos;
>> -	gain = actual_step * 0x400 / 5;
>> +	gain = actual_step / 5;
>>
>> -	for (i = 0; i<= 4; i++) {
>> -		if (actual_step>= 0)
>> -			s_move[i] = ((((i+1)*gain+0x200) - (i*gain+0x200))/0x400);
>> -		else
>> -			s_move[i] = ((((i+1)*gain-0x200) - (i*gain-0x200))/0x400);
>> -	}
>> +	for (i = 0; i<= 4; i++)
>> +		s_move[i] = gain;
>>
>>   	/* Ring Damping Code */
>>   	for (i = 0; i<= 4; i++) {
>> -- 
>> 1.6.5.4
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>> Please read the FAQ at  http://www.tux.org/lkml/
>>      

I've yet to see a reply from GregH. Has this patch been misplaced or 
dropped?
Or is the patch no longer valid/correct?

Justin Madru

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Greg KH]

On Mon, Dec 14, 2009 at 04:38:40PM -0800, Justin Madru wrote:
> On 12/09/2009 01:57 AM, Dan Carpenter wrote:
> > On Sat, Dec 05, 2009 at 06:03:20PM -0800, Justin Madru wrote:
> >    
> >> I was style fixing some code when I ran into this code.
> >> It seems like the code could be reduced, by factoring the expression.
> >> But this results in a very simple expression.
> >>
> >> Am I assuming something wrong? Or is this a bug in the original code?
> >> This doesn't look right because the assignment of s_move[i] has no mention
> >> of the loop counter.
> >>
> >> Justin
> >>
> >> ------
> >>
> >> the code was looping, seting s_move[i] to the following calculations
> >>
> >> if (actual_step>= 0)
> >>          s_move[i] = ((((i + 1) * gain + 0x200) - (i * gain + 0x200)) / 0x400);
> >> else
> >>          s_move[i] = ((((i + 1) * gain - 0x200) - (i * gain - 0x200)) / 0x400);
> >>
> >> but, by factoring the expression, it can be shown that they both reduce
> >> to a very simple expression:
> >>
> >>          s_move[i] = gain / 0x400;
> >>
> >>      
> > Heh.
> >
> > Looks like an improvement to me.
> >
> > If gain were 16 bits instead of 32 I would think the "* 0x400 / 0x400" was
> > designed to mask out the highest 10 bits.
> >
> > Acked-by:  Dan Carpenter<error27@gmail.com>
> >
> > regards,
> > dan carpenter
> >
> >    
> >> Signed-off-by: Justin Madru<jdm64@gawab.com>
> >> ---
> >>   drivers/staging/dream/camera/s5k3e2fx.c |   10 +++-------
> >>   1 files changed, 3 insertions(+), 7 deletions(-)
> >>
> >> diff --git a/drivers/staging/dream/camera/s5k3e2fx.c b/drivers/staging/dream/camera/s5k3e2fx.c
> >> index f0e49be..d205a2d 100644
> >> --- a/drivers/staging/dream/camera/s5k3e2fx.c
> >> +++ b/drivers/staging/dream/camera/s5k3e2fx.c
> >> @@ -1092,14 +1092,10 @@ static int32_t s5k3e2fx_move_focus(int direction, int32_t num_steps)
> >>
> >>   	actual_step = step_direction * (int16_t)num_steps;
> >>   	pos_offset = init_code + s5k3e2fx_ctrl->curr_lens_pos;
> >> -	gain = actual_step * 0x400 / 5;
> >> +	gain = actual_step / 5;
> >>
> >> -	for (i = 0; i<= 4; i++) {
> >> -		if (actual_step>= 0)
> >> -			s_move[i] = ((((i+1)*gain+0x200) - (i*gain+0x200))/0x400);
> >> -		else
> >> -			s_move[i] = ((((i+1)*gain-0x200) - (i*gain-0x200))/0x400);
> >> -	}
> >> +	for (i = 0; i<= 4; i++)
> >> +		s_move[i] = gain;
> >>
> >>   	/* Ring Damping Code */
> >>   	for (i = 0; i<= 4; i++) {
> >> -- 
> >> 1.6.5.4
> >>
> >> --
> >> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> >> the body of a message to majordomo@vger.kernel.org
> >> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> >> Please read the FAQ at  http://www.tux.org/lkml/
> >>      
> 
> I've yet to see a reply from GregH. Has this patch been misplaced or 
> dropped?
> Or is the patch no longer valid/correct?

It's in my "to-apply" queue.  I was working on the .33-rc1 merge first.
After that comes out I'll get to my patch queue.

thanks,

greg k-h

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Ray Lee]

On Sat, Dec 5, 2009 at 6:03 PM, Justin Madru <jdm64@gawab.com> wrote:
> I was style fixing some code when I ran into this code.
> It seems like the code could be reduced, by factoring the expression.
> But this results in a very simple expression.
>
> Am I assuming something wrong? Or is this a bug in the original code?
> This doesn't look right because the assignment of s_move[i] has no mention
> of the loop counter.

Algebraic factoring is not valid in general when dealing with pure
integer expressions that may contain rounding issues. I haven't
checked to see if that's the case with the code you're changing, but
that sort of expression you're removing is very commonly used exactly
to deal with rounding issues.

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Justin Madru]

On 12/14/2009 08:02 PM, Ray Lee wrote:
> On Sat, Dec 5, 2009 at 6:03 PM, Justin Madru<jdm64@gawab.com>  wrote:
>    
>> I was style fixing some code when I ran into this code.
>> It seems like the code could be reduced, by factoring the expression.
>> But this results in a very simple expression.
>>
>> Am I assuming something wrong? Or is this a bug in the original code?
>> This doesn't look right because the assignment of s_move[i] has no mention
>> of the loop counter.
>>      
> Algebraic factoring is not valid in general when dealing with pure
> integer expressions that may contain rounding issues. I haven't
> checked to see if that's the case with the code you're changing, but
> that sort of expression you're removing is very commonly used exactly
> to deal with rounding issues.
>    

I know that's true and that's why I was questioning if my patch actually 
removed a necessary calculation.
But, wouldn't you agree that if the code was suppose to deal with 
"rounding issues" that there's a
simpler expression?

Justin

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Ray Lee]

On Tue, Dec 15, 2009 at 10:37 AM, Justin Madru <jdm64@gawab.com> wrote:
> But, wouldn't you agree that if the code was suppose to deal with "rounding
> issues" that there's a
> simpler expression?

No, I don't agree. Five minutes of effort below shows your patch will
generate different numbers than the original. If this is controlling a
stepper motor trying to hit a home position, it's off now. Or, the
errors in the expressions for moving near and far may have balanced
each other out before, and now there may be a systematic error causing
a skew over time toward one end rather than the other.

My point is that you need to run this past the guy with the actual
hardware who wrote it in the first place such that it can be tested,
and make sure the slapped-together expression isn't just working by
accident, as ugly as it might be.

#include <stdio.h>

typedef int int32_t;
typedef short int16_t;
typedef unsigned int uint32_t;

enum {MOVE_NEAR, MOVE_FAR} move_direction;

int32_t s5k3e2fx_move_focus(int direction, int32_t num_steps)
{
        int32_t i;
        int16_t step_direction;
        int16_t actual_step;
        int16_t s_move[5], s_move_2[5];
        uint32_t gain, gain_2;

        if (direction == MOVE_NEAR)
                step_direction = 20;
        else
                step_direction = -20;

        actual_step = step_direction * (int16_t)num_steps;

        gain = actual_step * 0x400 / 5;
	gain_2 = actual_step / 5;
	
        for (i = 0; i <= 4; i++) {
                if (actual_step >= 0)
                        s_move[i] = ((((i+1)*gain+0x200) -
(i*gain+0x200))/0x400);
                else
                        s_move[i] = ((((i+1)*gain-0x200) -
(i*gain-0x200))/0x400);
        }

        for (i = 0; i <= 4; i++)
                s_move_2[i] = gain_2;

	if (memcmp(s_move, s_move_2, sizeof(s_move))) {
		printf("s1, s2 differ for direction %d, num_steps %d\n", direction,
num_steps);
		for (i=0; i<5; i++)
			printf(" [%d] %d %d", i, s_move[i], s_move_2[i]);
		printf("\n");
	}

}

int main(void) {
	int steps;
	for (steps = -65535; steps < 65536; steps++) {
		s5k3e2fx_move_focus(MOVE_NEAR, steps);
		s5k3e2fx_move_focus(MOVE_FAR, steps);
	}
}



>
> Justin
>

Re: [PATCH] staging: s5k3e2fx.c: reduce complexity by factoring

[Justin Madru]

On 12/15/2009 11:10 AM, Ray Lee wrote:
> On Tue, Dec 15, 2009 at 10:37 AM, Justin Madru<jdm64@gawab.com>  wrote:
>    
>> But, wouldn't you agree that if the code was suppose to deal with "rounding
>> issues" that there's a
>> simpler expression?
>>      
> No, I don't agree. Five minutes of effort below shows your patch will
> generate different numbers than the original. If this is controlling a
> stepper motor trying to hit a home position, it's off now. Or, the
> errors in the expressions for moving near and far may have balanced
> each other out before, and now there may be a systematic error causing
> a skew over time toward one end rather than the other.
>
> My point is that you need to run this past the guy with the actual
> hardware who wrote it in the first place such that it can be tested,
> and make sure the slapped-together expression isn't just working by
> accident, as ugly as it might be.
>
> #include<stdio.h>
>
> typedef int int32_t;
> typedef short int16_t;
> typedef unsigned int uint32_t;
>
> enum {MOVE_NEAR, MOVE_FAR} move_direction;
>
> int32_t s5k3e2fx_move_focus(int direction, int32_t num_steps)
> {
>          int32_t i;
>          int16_t step_direction;
>          int16_t actual_step;
>          int16_t s_move[5], s_move_2[5];
>          uint32_t gain, gain_2;
>
>          if (direction == MOVE_NEAR)
>                  step_direction = 20;
>          else
>                  step_direction = -20;
>
>          actual_step = step_direction * (int16_t)num_steps;
>
>          gain = actual_step * 0x400 / 5;
> 	gain_2 = actual_step / 5;
> 	
>          for (i = 0; i<= 4; i++) {
>                  if (actual_step>= 0)
>                          s_move[i] = ((((i+1)*gain+0x200) -
> (i*gain+0x200))/0x400);
>                  else
>                          s_move[i] = ((((i+1)*gain-0x200) -
> (i*gain-0x200))/0x400);
>          }
>
>          for (i = 0; i<= 4; i++)
>                  s_move_2[i] = gain_2;
>
> 	if (memcmp(s_move, s_move_2, sizeof(s_move))) {
> 		printf("s1, s2 differ for direction %d, num_steps %d\n", direction,
> num_steps);
> 		for (i=0; i<5; i++)
> 			printf(" [%d] %d %d", i, s_move[i], s_move_2[i]);
> 		printf("\n");
> 	}
>
> }
>
> int main(void) {
> 	int steps;
> 	for (steps = -65535; steps<  65536; steps++) {
> 		s5k3e2fx_move_focus(MOVE_NEAR, steps);
> 		s5k3e2fx_move_focus(MOVE_FAR, steps);
> 	}
> }
>
>    

Ok, I tested the example code and it does lead to different values!
But, I did some testing and came up with a new patch that has been tested
this time to come up with the same values as the old code but uses less 
calculations.

gain = ((actual_step << 10) / 5) >> 10;
         for (i = 0; i <= 4; i++)
                 s_move[i] = gain;

Greg, disregard my last patch. Instead, please accept my new patch -- 
pending review.
         http://lkml.org/lkml/2009/12/15/453

Justin Madru