Re: [PATCH v2 1/3] backlight: pwm_bl: Fix interpolation
On Wed, 14 Oct 2020 at 23:55, Geert Uytterhoeven wrote: > > Hi Alexandru, > > On Tue, Oct 13, 2020 at 1:57 PM 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. > > > > 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 > > 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 -- > ge...@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)
Re: [PATCH v2 1/3] backlight: pwm_bl: Fix interpolation
Hi Alexandru, On Tue, Oct 13, 2020 at 1:57 PM 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. > > 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 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 -- Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- ge...@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 ___ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
Re: [PATCH v2 1/3] backlight: pwm_bl: Fix interpolation
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 > --- > > 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; >
[PATCH v2 1/3] backlight: pwm_bl: Fix interpolation
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 --- 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 { -