Re: [PATCH v2 1/3] backlight: pwm_bl: Fix interpolation

On Wed, 14 Oct 2020 at 23:55, Geert Uytterhoeven [off-list ref] wrote:

Hi Alexandru,

On Tue, Oct 13, 2020 at 1:57 PM Alexandru Stan [off-list ref] wrote:

quoted

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

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

quoted

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

quoted

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