1 /**
2  * @file lv_draw_sw_dither.c
3  *
4  */
5 
6 /*********************
7  *      INCLUDES
8  *********************/
9 #include "lv_draw_sw_dither.h"
10 #include "lv_draw_sw_gradient.h"
11 #include "../../misc/lv_color.h"
12 
13 /**********************
14  *   STATIC FUNCTIONS
15  **********************/
16 
17 #if _DITHER_GRADIENT
18 
lv_dither_none(lv_grad_t * grad,lv_coord_t x,lv_coord_t y,lv_coord_t w)19 void LV_ATTRIBUTE_FAST_MEM lv_dither_none(lv_grad_t * grad, lv_coord_t x, lv_coord_t y, lv_coord_t w)
20 {
21     LV_UNUSED(x);
22     LV_UNUSED(y);
23     if(grad == NULL || grad->filled) return;
24     for(lv_coord_t i = 0; i < w; i++) {
25         grad->map[i] = lv_color_hex(grad->hmap[i].full);
26     }
27     grad->filled = 1;
28 }
29 
30 static const uint8_t dither_ordered_threshold_matrix[8 * 8] = {
31     0,  48, 12, 60,  3, 51, 15, 63,
32     32, 16, 44, 28, 35, 19, 47, 31,
33     8,  56,  4, 52, 11, 59,  7, 55,
34     40, 24, 36, 20, 43, 27, 39, 23,
35     2,  50, 14, 62,  1, 49, 13, 61,
36     34, 18, 46, 30, 33, 17, 45, 29,
37     10, 58,  6, 54,  9, 57,  5, 53,
38     42, 26, 38, 22, 41, 25, 37, 21
39 }; /* Shift by 6 to normalize */
40 
lv_dither_ordered_hor(lv_grad_t * grad,lv_coord_t x,lv_coord_t y,lv_coord_t w)41 void LV_ATTRIBUTE_FAST_MEM lv_dither_ordered_hor(lv_grad_t * grad, lv_coord_t x, lv_coord_t y, lv_coord_t w)
42 {
43     LV_UNUSED(x);
44     /* For vertical dithering, the error is spread on the next column (and not next line).
45        Since the renderer is scanline based, it's not obvious what could be used to perform the rendering efficiently.
46        The algorithm below is based on few assumptions:
47          1. An error diffusion algorithm (like Floyd Steinberg) here would be hard to implement since it means that a pixel on column n depends on the pixel on row n
48          2. Instead an ordered dithering algorithm shift the value a bit, but the influence only spread from the matrix size (used 8x8 here)
49          3. It means that a pixel i,j only depends on the value of a pixel i-7, j-7 to i,j and no other one.
50        Then we compute a complete row of ordered dither and store it in out. */
51 
52     /*The apply the algorithm for this patch*/
53     for(lv_coord_t j = 0; j < w; j++) {
54         int8_t factor = dither_ordered_threshold_matrix[(y & 7) * 8 + ((j) & 7)] - 32;
55         lv_color32_t tmp = grad->hmap[LV_CLAMP(0, j - 4, grad->size)];
56         lv_color32_t t;
57         t.ch.red   = LV_CLAMP(0, tmp.ch.red + factor, 255);
58         t.ch.green = LV_CLAMP(0, tmp.ch.green + factor, 255);
59         t.ch.blue  = LV_CLAMP(0, tmp.ch.blue + factor, 255);
60 
61         grad->map[j] = lv_color_hex(t.full);
62     }
63 }
64 
lv_dither_ordered_ver(lv_grad_t * grad,lv_coord_t x,lv_coord_t y,lv_coord_t w)65 void LV_ATTRIBUTE_FAST_MEM lv_dither_ordered_ver(lv_grad_t * grad, lv_coord_t x, lv_coord_t y, lv_coord_t w)
66 {
67     /* For vertical dithering, the error is spread on the next column (and not next line).
68        Since the renderer is scanline based, it's not obvious what could be used to perform the rendering efficiently.
69        The algorithm below is based on few assumptions:
70          1. An error diffusion algorithm (like Floyd Steinberg) here would be hard to implement since it means that a pixel on column n depends on the pixel on row n
71          2. Instead an ordered dithering algorithm shift the value a bit, but the influence only spread from the matrix size (used 8x8 here)
72          3. It means that a pixel i,j only depends on the value of a pixel i-7, j-7 to i,j and no other one.
73        Then we compute a complete row of ordered dither and store it in out. */
74 
75     /*Extract patch for working with, selected pseudo randomly*/
76     lv_color32_t tmp = grad->hmap[LV_CLAMP(0, y - 4, grad->size)];
77 
78     /*The apply the algorithm for this patch*/
79     for(lv_coord_t j = 0; j < 8; j++) {
80         int8_t factor = dither_ordered_threshold_matrix[(y & 7) * 8 + ((j + x) & 7)] - 32;
81         lv_color32_t t;
82         t.ch.red   = LV_CLAMP(0, tmp.ch.red + factor, 255);
83         t.ch.green = LV_CLAMP(0, tmp.ch.green + factor, 255);
84         t.ch.blue  = LV_CLAMP(0, tmp.ch.blue + factor, 255);
85 
86         grad->map[j] = lv_color_hex(t.full);
87     }
88     /*Finally fill the line*/
89     lv_coord_t j = 8;
90     for(; j < w - 8; j += 8) {
91         lv_memcpy(grad->map + j, grad->map, 8 * sizeof(*grad->map));
92     }
93     /* Prevent overwriting */
94     for(; j < w; j++) {
95         grad->map[j] = grad->map[j & 7];
96     }
97 }
98 
99 #if LV_DITHER_ERROR_DIFFUSION == 1
lv_dither_err_diff_hor(lv_grad_t * grad,lv_coord_t xs,lv_coord_t y,lv_coord_t w)100 void LV_ATTRIBUTE_FAST_MEM lv_dither_err_diff_hor(lv_grad_t * grad, lv_coord_t xs, lv_coord_t y, lv_coord_t w)
101 {
102     LV_UNUSED(xs);
103     LV_UNUSED(y);
104     LV_UNUSED(w);
105 
106     /* Implement Floyd Steinberg algorithm, see https://surma.dev/things/ditherpunk/
107         Coefs are:   x 7
108                    3 5 1
109                    / 16
110         Can be implemented as:            x       (x<<3 - x)
111                               (x<<2 - x) (x<<2+x)   x
112     */
113     int coef[4] = {0, 0, 0, 0};
114 #define FS_COMPUTE_ERROR(e) { coef[0] = (e<<3) - e; coef[1] = (e<<2) - e; coef[2] = (e<<2) + e; coef[3] = e; }
115 #define FS_COMPONENTS(A, OP, B, C) A.ch.red = LV_CLAMP(0, A.ch.red OP B.r OP C.r, 255); A.ch.green = LV_CLAMP(0, A.ch.green OP B.g OP C.g, 255); A.ch.blue = LV_CLAMP(0, A.ch.blue OP B.b OP C.b, 255);
116 #define FS_QUANT_ERROR(e, t, q) { lv_color32_t u; u.full = lv_color_to32(q); e.r = (int8_t)(t.ch.red - u.ch.red); e.g = (int8_t)(t.ch.green - u.ch.green); e.b = (int8_t)(t.ch.blue - u.ch.blue); }
117     lv_scolor24_t next_px_err = {0}, next_l = {0}, error;
118     /*First last pixel are not dithered */
119     grad->map[0] = lv_color_hex(grad->hmap[0].full);
120     for(lv_coord_t x = 1; x < grad->size - 1; x++) {
121         lv_color32_t t = grad->hmap[x];
122         lv_color_t q;
123         /*Add error term*/
124         FS_COMPONENTS(t, +, next_px_err, next_l);
125         next_l = grad->error_acc[x + 1];
126         /*Quantify*/
127         q = lv_color_hex(t.full);
128         /*Then compute error*/
129         FS_QUANT_ERROR(error, t, q);
130         /*Dither the error*/
131         FS_COMPUTE_ERROR(error.r);
132         next_px_err.r      = coef[0] >> 4;
133         grad->error_acc[x - 1].r += coef[1] >> 4;
134         grad->error_acc[x].r     += coef[2] >> 4;
135         grad->error_acc[x + 1].r = coef[3] >> 4;
136 
137         FS_COMPUTE_ERROR(error.g);
138         next_px_err.g      = coef[0] >> 4;
139         grad->error_acc[x - 1].g += coef[1] >> 4;
140         grad->error_acc[x].g     += coef[2] >> 4;
141         grad->error_acc[x + 1].g = coef[3] >> 4;
142 
143         FS_COMPUTE_ERROR(error.b);
144         next_px_err.b      = coef[0] >> 4;
145         grad->error_acc[x - 1].b += coef[1] >> 4;
146         grad->error_acc[x].b     += coef[2] >> 4;
147         grad->error_acc[x + 1].b = coef[3] >> 4;
148 
149         grad->map[x] = q;
150     }
151     grad->map[grad->size - 1] = lv_color_hex(grad->hmap[grad->size - 1].full);
152 }
153 
lv_dither_err_diff_ver(lv_grad_t * grad,lv_coord_t xs,lv_coord_t y,lv_coord_t w)154 void LV_ATTRIBUTE_FAST_MEM lv_dither_err_diff_ver(lv_grad_t * grad, lv_coord_t xs, lv_coord_t y, lv_coord_t w)
155 {
156     /* Try to implement error diffusion on a vertical gradient and an horizontal map using those tricks:
157         Since the given hi-resolution gradient (in src) is vertical, the Floyd Steinberg algorithm pass need to be rotated,
158         so we'll get this instead (from top to bottom):
159 
160           A   B   C
161        1 [  ][  ][  ]
162        2 [  ][  ][  ]     Pixel A2 will spread its error on pixel A3 with coefficient 7,
163        3 [  ][  ][  ]     Pixel A2 will spread its error on pixel B1 with coefficient 3, B2 with coef 5 and B3 with coef 1
164 
165        When taking into account an arbitrary pixel P(i,j), its added error diffusion term is:
166            e(i,j) = 1/16 * [ e(i-1,j) * 5 + e(i-1,j+1) * 3 + e(i-1,j-1) * 1 + e(i,j-1) * 7]
167 
168        This means that the error term depends on pixel W, NW, N and SW.
169        If we consider that we are generating the error diffused gradient map from top to bottom, we can remember the previous
170        line (N, NW) in the term above. Also, we remember the (W) term too since we are computing the gradient map from left to right.
171        However, the SW term is painful for us, we can't support it (since to get it, we need its own SW term and so on).
172        Let's remove it and re-dispatch the error factor accordingly so they stays normalized:
173            e(i,j) ~= 1/16 * [ e(i-1,j) * 6 + e(i-1,j-1) * 1 + e(i,j-1) * 9]
174 
175        That's the idea of this pseudo Floyd Steinberg dithering */
176 #define FS_APPLY(d, s, c) d.r = (int8_t)(s.r * c) >> 4; d.g = (int8_t)(s.g * c) >> 4; d.b = (int8_t)(s.b * c) >> 4;
177 #define FS_COMPONENTS3(A, OP, B, b, C, c, D, d) \
178     A.ch.red   = LV_CLAMP(0, A.ch.red   OP ((B.r * b OP C.r * c OP D.r * d) >> 4), 255); \
179     A.ch.green = LV_CLAMP(0, A.ch.green OP ((B.r * b OP C.r * c OP D.r * d) >> 4), 255); \
180     A.ch.blue  = LV_CLAMP(0, A.ch.blue  OP ((B.r * b OP C.r * c OP D.r * d) >> 4), 255);
181 
182     lv_scolor24_t next_px_err, prev_l = grad->error_acc[0];
183     /*Compute the error term for the current pixel (first pixel is never dithered)*/
184     if(xs == 0) {
185         grad->map[0] = lv_color_hex(grad->hmap[y].full);
186         FS_QUANT_ERROR(next_px_err, grad->hmap[y], grad->map[0]);
187     }
188     else {
189         lv_color_t tmp = lv_color_hex(grad->hmap[y].full);
190         lv_color32_t t = grad->hmap[y];
191         FS_QUANT_ERROR(next_px_err, grad->hmap[y], tmp);
192         FS_COMPONENTS3(t, +, next_px_err, 6, prev_l, 1, grad->error_acc[0], 9);
193         grad->map[0] = lv_color_hex(t.full);
194     }
195 
196     for(lv_coord_t x = 1; x < w; x++) {
197         lv_color32_t t = grad->hmap[y];
198         lv_color_t q;
199         /*Add the current error term*/
200         FS_COMPONENTS3(t, +, next_px_err, 6, prev_l, 1, grad->error_acc[x], 9);
201         prev_l = grad->error_acc[x];
202         /*Quantize and compute error term*/
203         q = lv_color_hex(t.full);
204         FS_QUANT_ERROR(next_px_err, t, q);
205         /*Store error for next line computation*/
206         grad->error_acc[x] = next_px_err;
207         grad->map[x] = q;
208     }
209 }
210 #endif
211 #endif
212