| Message ID | 20201013010056.v2.1.I4dcea1c90e9da3902d466033aa73351e19e49c49@changeid |
|---|---|
| State | Not Applicable |
| Headers | show |
| Series | PWM backlight interpolation adjustments | expand |
On Tue, Oct 13, 2020 at 01:01:01AM -0700, Alexandru Stan wrote: > Whenever num-interpolated-steps was larger than the distance > between 2 consecutive brightness levels the table would get really > discontinuous. The slope of the interpolation would stick with > integers only and if it was 0 the whole line segment would get skipped. > > Example settings: > brightness-levels = <0 1 2 4 8 16 32 64 128 256>; > num-interpolated-steps = <16>; > > The distances between 1 2 4 and 8 would be 1, and only starting with 16 > it would start to interpolate properly. Both comments a perilously close to nitpicking but enough that I wanted to reply... I'd suggest that the current behaviour as having two properties. 1. It was designed to generate strictly increasing tables (no repeated values). 2. It's implementation contains quantization errors when calculating the step size. This results in both the discards of some interpolated steps you mentioned (it is possible to insert extra steps between 4 and 8 whilst retaining a strictly increasing table). It also results in a potentially large undershoot when multiplying a step size (64 interpolated steps and a gap of 127 is likely to get a visual jump as we hop through 63 physical steps in one go). #1 can is a policy that can be changed. #2 is a bug that could be fixed. To be clear I don't object to generating a monotonically increasing table but I'd prefer the policy change to be explicitly described in the description. > Let's change it so there's always interpolation happening, even if > there's no enough points available (read: values in the table would > appear more than once). This should match the expected behavior much > more closely. > > Signed-off-by: Alexandru Stan <amstan@chromium.org> > --- > > drivers/video/backlight/pwm_bl.c | 70 ++++++++++++++------------------ > 1 file changed, 31 insertions(+), 39 deletions(-) > > diff --git a/drivers/video/backlight/pwm_bl.c b/drivers/video/backlight/pwm_bl.c > index dfc760830eb9..3e77f6b73fd9 100644 > --- a/drivers/video/backlight/pwm_bl.c > +++ b/drivers/video/backlight/pwm_bl.c > @@ -230,8 +230,7 @@ static int pwm_backlight_parse_dt(struct device *dev, > struct platform_pwm_backlight_data *data) > { > struct device_node *node = dev->of_node; > - unsigned int num_levels = 0; > - unsigned int levels_count; > + unsigned int num_levels; > unsigned int num_steps = 0; > struct property *prop; > unsigned int *table; > @@ -260,12 +259,11 @@ static int pwm_backlight_parse_dt(struct device *dev, > if (!prop) > return 0; > > - data->max_brightness = length / sizeof(u32); > + num_levels = length / sizeof(u32); > > /* read brightness levels from DT property */ > - if (data->max_brightness > 0) { > - size_t size = sizeof(*data->levels) * data->max_brightness; > - unsigned int i, j, n = 0; > + if (num_levels > 0) { > + size_t size = sizeof(*data->levels) * num_levels; > > data->levels = devm_kzalloc(dev, size, GFP_KERNEL); > if (!data->levels) > @@ -273,7 +271,7 @@ static int pwm_backlight_parse_dt(struct device *dev, > > ret = of_property_read_u32_array(node, "brightness-levels", > data->levels, > - data->max_brightness); > + num_levels); > if (ret < 0) > return ret; > > @@ -298,7 +296,13 @@ static int pwm_backlight_parse_dt(struct device *dev, > * between two points. > */ > if (num_steps) { > - if (data->max_brightness < 2) { > + unsigned int num_input_levels = num_levels; > + unsigned int i; > + u32 x1, x2, x, dx; > + u32 y1, y2; > + s64 dy; > + > + if (num_input_levels < 2) { > dev_err(dev, "can't interpolate\n"); > return -EINVAL; > } > @@ -308,14 +312,7 @@ static int pwm_backlight_parse_dt(struct device *dev, > * taking in consideration the number of interpolated > * steps between two levels. > */ > - for (i = 0; i < data->max_brightness - 1; i++) { > - if ((data->levels[i + 1] - data->levels[i]) / > - num_steps) > - num_levels += num_steps; > - else > - num_levels++; > - } > - num_levels++; > + num_levels = (num_input_levels - 1) * num_steps + 1; > dev_dbg(dev, "new number of brightness levels: %d\n", > num_levels); > > @@ -327,24 +324,25 @@ static int pwm_backlight_parse_dt(struct device *dev, > table = devm_kzalloc(dev, size, GFP_KERNEL); > if (!table) > return -ENOMEM; > - > - /* Fill the interpolated table. */ > - levels_count = 0; > - for (i = 0; i < data->max_brightness - 1; i++) { > - value = data->levels[i]; > - n = (data->levels[i + 1] - value) / num_steps; > - if (n > 0) { > - for (j = 0; j < num_steps; j++) { > - table[levels_count] = value; > - value += n; > - levels_count++; > - } > - } else { > - table[levels_count] = data->levels[i]; > - levels_count++; > + /* > + * Fill the interpolated table[x] = y > + * by draw lines between each (x1, y1) to (x2, y2). > + */ > + dx = num_steps; > + for (i = 0; i < num_input_levels - 1; i++) { > + x1 = i * dx; > + x2 = x1 + dx; > + y1 = data->levels[i]; > + y2 = data->levels[i + 1]; > + dy = (s64)y2 - y1; > + > + for (x = x1; x < x2; x++) { > + table[x] = y1 + > + div_s64(dy * ((s64)x - x1), dx); I don't think it is possible for x - x1 to be negative (e.g. what is the s64 for). Obviously it makes little functional difference whether the cast is there or not but I don't like fixed point code that has been written with "just in case" casts. Daniel. > } > } > - table[levels_count] = data->levels[i]; > + /* Fill in the last point, since no line starts here. */ > + table[x2] = y2; > > /* > * As we use interpolation lets remove current > @@ -353,15 +351,9 @@ static int pwm_backlight_parse_dt(struct device *dev, > */ > devm_kfree(dev, data->levels); > data->levels = table; > - > - /* > - * Reassign max_brightness value to the new total number > - * of brightness levels. > - */ > - data->max_brightness = num_levels; > } > > - data->max_brightness--; > + data->max_brightness = num_levels - 1; > } > > return 0; > -- > 2.28.0 >
Hi Alexandru, On Tue, Oct 13, 2020 at 1:57 PM Alexandru Stan <amstan@chromium.org> wrote: > Whenever num-interpolated-steps was larger than the distance > between 2 consecutive brightness levels the table would get really > discontinuous. The slope of the interpolation would stick with > integers only and if it was 0 the whole line segment would get skipped. > > Example settings: > brightness-levels = <0 1 2 4 8 16 32 64 128 256>; > num-interpolated-steps = <16>; > > The distances between 1 2 4 and 8 would be 1, and only starting with 16 > it would start to interpolate properly. > > Let's change it so there's always interpolation happening, even if > there's no enough points available (read: values in the table would > appear more than once). This should match the expected behavior much > more closely. > > Signed-off-by: Alexandru Stan <amstan@chromium.org> Thanks for your patch! > --- a/drivers/video/backlight/pwm_bl.c > +++ b/drivers/video/backlight/pwm_bl.c > @@ -327,24 +324,25 @@ static int pwm_backlight_parse_dt(struct device *dev, > table = devm_kzalloc(dev, size, GFP_KERNEL); > if (!table) > return -ENOMEM; > - > - /* Fill the interpolated table. */ > - levels_count = 0; > - for (i = 0; i < data->max_brightness - 1; i++) { > - value = data->levels[i]; > - n = (data->levels[i + 1] - value) / num_steps; > - if (n > 0) { > - for (j = 0; j < num_steps; j++) { > - table[levels_count] = value; > - value += n; > - levels_count++; > - } > - } else { > - table[levels_count] = data->levels[i]; > - levels_count++; > + /* > + * Fill the interpolated table[x] = y > + * by draw lines between each (x1, y1) to (x2, y2). > + */ > + dx = num_steps; > + for (i = 0; i < num_input_levels - 1; i++) { > + x1 = i * dx; > + x2 = x1 + dx; > + y1 = data->levels[i]; > + y2 = data->levels[i + 1]; > + dy = (s64)y2 - y1; > + > + for (x = x1; x < x2; x++) { > + table[x] = y1 + > + div_s64(dy * ((s64)x - x1), dx); Yummy, 64-by-32 divisions. Shouldn't this use a rounded division? Nevertheless, I think it would be worthwhile to implement this using a (modified) Bresenham algorithm, avoiding multiplications and divisions, and possibly increasing accuracy as well. https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm > } > } > - table[levels_count] = data->levels[i]; > + /* Fill in the last point, since no line starts here. */ > + table[x2] = y2; > > /* > * As we use interpolation lets remove current Gr{oetje,eeting}s, Geert
On Wed, 14 Oct 2020 at 23:55, Geert Uytterhoeven <geert@linux-m68k.org> wrote: > > Hi Alexandru, > > On Tue, Oct 13, 2020 at 1:57 PM Alexandru Stan <amstan@chromium.org> wrote: > > Whenever num-interpolated-steps was larger than the distance > > between 2 consecutive brightness levels the table would get really > > discontinuous. The slope of the interpolation would stick with > > integers only and if it was 0 the whole line segment would get skipped. > > > > Example settings: > > brightness-levels = <0 1 2 4 8 16 32 64 128 256>; > > num-interpolated-steps = <16>; > > > > The distances between 1 2 4 and 8 would be 1, and only starting with 16 > > it would start to interpolate properly. > > > > Let's change it so there's always interpolation happening, even if > > there's no enough points available (read: values in the table would > > appear more than once). This should match the expected behavior much > > more closely. > > > > Signed-off-by: Alexandru Stan <amstan@chromium.org> > > Thanks for your patch! Thanks for your reply! I'm sorry I haven't replied earlier. Looks like your reply was marked as spam. Rest be assured my spam filter has been disciplined! :D > > > --- a/drivers/video/backlight/pwm_bl.c > > +++ b/drivers/video/backlight/pwm_bl.c > > @@ -327,24 +324,25 @@ static int pwm_backlight_parse_dt(struct device *dev, > > table = devm_kzalloc(dev, size, GFP_KERNEL); > > if (!table) > > return -ENOMEM; > > - > > - /* Fill the interpolated table. */ > > - levels_count = 0; > > - for (i = 0; i < data->max_brightness - 1; i++) { > > - value = data->levels[i]; > > - n = (data->levels[i + 1] - value) / num_steps; > > - if (n > 0) { > > - for (j = 0; j < num_steps; j++) { > > - table[levels_count] = value; > > - value += n; > > - levels_count++; > > - } > > - } else { > > - table[levels_count] = data->levels[i]; > > - levels_count++; > > + /* > > + * Fill the interpolated table[x] = y > > + * by draw lines between each (x1, y1) to (x2, y2). > > + */ > > + dx = num_steps; > > + for (i = 0; i < num_input_levels - 1; i++) { > > + x1 = i * dx; > > + x2 = x1 + dx; > > + y1 = data->levels[i]; > > + y2 = data->levels[i + 1]; > > + dy = (s64)y2 - y1; > > + > > + for (x = x1; x < x2; x++) { > > + table[x] = y1 + > > + div_s64(dy * ((s64)x - x1), dx); > > Yummy, 64-by-32 divisions. > Shouldn't this use a rounded division? It won't hurt. But it really doesn't make much of a difference either way. > > Nevertheless, I think it would be worthwhile to implement this using > a (modified) Bresenham algorithm, avoiding multiplications and > divisions, and possibly increasing accuracy as well. > > https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm Sure, it might be a little faster to use Bresenham's line algorithm. Looks like to implement it I would have to deal with some fixed point math and still have to do divisions occasionally. I don't think performance is critical here, the values get calculated only once when the driver loads, and the algorithm's accuracy improvements might be at most 1 LSB. Meanwhile the formula I already implemented is almost the same as the formulas found at https://en.wikipedia.org/wiki/Linear_interpolation#:~:text=gives I would like to keep it as is, as straightforward as possible. > > > } > > } > > - table[levels_count] = data->levels[i]; > > + /* Fill in the last point, since no line starts here. */ > > + table[x2] = y2; > > > > /* > > * As we use interpolation lets remove current > > Gr{oetje,eeting}s, > > Geert > > -- > Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org > > In personal conversations with technical people, I call myself a hacker. But > when I'm talking to journalists I just say "programmer" or something like that. > -- Linus Torvalds Alexandru Stan (amstan)
diff --git a/drivers/video/backlight/pwm_bl.c b/drivers/video/backlight/pwm_bl.c index dfc760830eb9..3e77f6b73fd9 100644 --- a/drivers/video/backlight/pwm_bl.c +++ b/drivers/video/backlight/pwm_bl.c @@ -230,8 +230,7 @@ static int pwm_backlight_parse_dt(struct device *dev, struct platform_pwm_backlight_data *data) { struct device_node *node = dev->of_node; - unsigned int num_levels = 0; - unsigned int levels_count; + unsigned int num_levels; unsigned int num_steps = 0; struct property *prop; unsigned int *table; @@ -260,12 +259,11 @@ static int pwm_backlight_parse_dt(struct device *dev, if (!prop) return 0; - data->max_brightness = length / sizeof(u32); + num_levels = length / sizeof(u32); /* read brightness levels from DT property */ - if (data->max_brightness > 0) { - size_t size = sizeof(*data->levels) * data->max_brightness; - unsigned int i, j, n = 0; + if (num_levels > 0) { + size_t size = sizeof(*data->levels) * num_levels; data->levels = devm_kzalloc(dev, size, GFP_KERNEL); if (!data->levels) @@ -273,7 +271,7 @@ static int pwm_backlight_parse_dt(struct device *dev, ret = of_property_read_u32_array(node, "brightness-levels", data->levels, - data->max_brightness); + num_levels); if (ret < 0) return ret; @@ -298,7 +296,13 @@ static int pwm_backlight_parse_dt(struct device *dev, * between two points. */ if (num_steps) { - if (data->max_brightness < 2) { + unsigned int num_input_levels = num_levels; + unsigned int i; + u32 x1, x2, x, dx; + u32 y1, y2; + s64 dy; + + if (num_input_levels < 2) { dev_err(dev, "can't interpolate\n"); return -EINVAL; } @@ -308,14 +312,7 @@ static int pwm_backlight_parse_dt(struct device *dev, * taking in consideration the number of interpolated * steps between two levels. */ - for (i = 0; i < data->max_brightness - 1; i++) { - if ((data->levels[i + 1] - data->levels[i]) / - num_steps) - num_levels += num_steps; - else - num_levels++; - } - num_levels++; + num_levels = (num_input_levels - 1) * num_steps + 1; dev_dbg(dev, "new number of brightness levels: %d\n", num_levels); @@ -327,24 +324,25 @@ static int pwm_backlight_parse_dt(struct device *dev, table = devm_kzalloc(dev, size, GFP_KERNEL); if (!table) return -ENOMEM; - - /* Fill the interpolated table. */ - levels_count = 0; - for (i = 0; i < data->max_brightness - 1; i++) { - value = data->levels[i]; - n = (data->levels[i + 1] - value) / num_steps; - if (n > 0) { - for (j = 0; j < num_steps; j++) { - table[levels_count] = value; - value += n; - levels_count++; - } - } else { - table[levels_count] = data->levels[i]; - levels_count++; + /* + * Fill the interpolated table[x] = y + * by draw lines between each (x1, y1) to (x2, y2). + */ + dx = num_steps; + for (i = 0; i < num_input_levels - 1; i++) { + x1 = i * dx; + x2 = x1 + dx; + y1 = data->levels[i]; + y2 = data->levels[i + 1]; + dy = (s64)y2 - y1; + + for (x = x1; x < x2; x++) { + table[x] = y1 + + div_s64(dy * ((s64)x - x1), dx); } } - table[levels_count] = data->levels[i]; + /* Fill in the last point, since no line starts here. */ + table[x2] = y2; /* * As we use interpolation lets remove current @@ -353,15 +351,9 @@ static int pwm_backlight_parse_dt(struct device *dev, */ devm_kfree(dev, data->levels); data->levels = table; - - /* - * Reassign max_brightness value to the new total number - * of brightness levels. - */ - data->max_brightness = num_levels; } - data->max_brightness--; + data->max_brightness = num_levels - 1; } return 0;
Whenever num-interpolated-steps was larger than the distance between 2 consecutive brightness levels the table would get really discontinuous. The slope of the interpolation would stick with integers only and if it was 0 the whole line segment would get skipped. Example settings: brightness-levels = <0 1 2 4 8 16 32 64 128 256>; num-interpolated-steps = <16>; The distances between 1 2 4 and 8 would be 1, and only starting with 16 it would start to interpolate properly. Let's change it so there's always interpolation happening, even if there's no enough points available (read: values in the table would appear more than once). This should match the expected behavior much more closely. Signed-off-by: Alexandru Stan <amstan@chromium.org> --- drivers/video/backlight/pwm_bl.c | 70 ++++++++++++++------------------ 1 file changed, 31 insertions(+), 39 deletions(-)