From: Søren Sandmann Pedersen <s...@redhat.com> The computations in pixman-gradient-walker.c currently take place at very limited 8 bit precision which results in quite visible artefacts in gradients. An example is the one produced by demos/linear-gradient which currently looks like this:
http://i.imgur.com/kQbX8nd.png With the changes in this commit, the gradient looks like this: http://i.imgur.com/nUlyuKI.png The images are also available here: http://people.freedesktop.org/~sandmann/gradients/before.png http://people.freedesktop.org/~sandmann/gradients/after.png This patch computes pixels using floating point, but uses a faster algorithm, which makes up for the loss of performance. == Theory: In both the new and the old algorithm, the various gradient implementations compute a parameter x that indicates how far along the gradient the current scanline is. The current algorithm has a cache of the two color stops surrounding the last parameter; those are used in a SIMD-within-register fashion in this way: t1 = walker->left_rb * idist + walker->right_rb * dist; where dist and idist are the distances to the left and right color stops respectively normalized to the distance between the left and right stops. The normalization (which involves a division) is captured in another cached variable "stepper". The cached values are recomputed whenever the parameter moves in between two different stops (called "reset" in the implementation). Because idist and dist are computed in 8 bits only, a lot of information is lost, which is quite visible as the image linked above shows. The new algorithm caches more information in the following way. When interpolating between stops, the formula to be used is this: t = ((x - left) / (right - left)); result = lc * (1 - t) + rc * t; where - x is the parameter as computed by the main gradient code, - left is the position of the left color stop, - right is the position of the right color stop - lc is the color of the left color stop - rc is the color of the right color stop That formula can also be written like this: result = lc * (1 - t) + rc * t; = lc + (rc - lc) * t = lc + (rc - lc) * ((x - left) / (right - left)) = (rc - lc) / (right - left) * x + lc - (left * (rc - lc)) / (right - left) = s * x + b where s = (rc - lc) / (right - left) and b = lc - left * (rc - lc) / (right - left) = (lc * (right - left) - left * (rc - lc)) / (right - left) = (lc * right - rc * left) / (right - left) To summarize, setting w = (right - left): s = (rc - lc) / w b = (lc * right - rc * left) / w r = s * x + b Since s and b only depend on the two active stops, both can be cached so that the computation only needs to do one multiplication and one addition per pixel (followed by premultiplication of the alpha channel). That is, seven multiplications in total, which is the same number as the old SIMD-within-register implementation had. == Implementation notes: The new formula described above is implemented in single precision floating point, and the eight divisions necessary to compute the cached values are done by multiplication with the reciprocal of the distance between the color stops. The alpha values used in the cached computation are scaled by 255.0, whereas the RGB values are kept in the [0, 1] interval. The ensures that after premultiplication, all values will be in the [0, 255] interval. This scaling is done by first dividing all the all the channels by 257, and then later on dividing the r, g, b channels by 255. It would be more natural to do all this scaling in only one place, but inexplicably, that results in a (substantial) slowdown on Sandy Bridge with GCC v 4.7. == Performance impact (median of three runs of radial-perf-test): == Intel Sandy Bridge, Core i3 @ 1.2GHz Before: 0.014553 After: 0.014410 Change: 1.0% faster == AMD Barcelona @ 1.2 GHz Before: 0.021735 After: 0.021328 Change: 1.9% faster Ie., slightly faster, though conceivably there could be a negative impact on machines with a bigger difference between integer and floating point performance. V2: - Use 's' and 'b' in the variable names instead of 'm' and 'd'. This way they match the explanation above - Move variable declarations to the top of the function - Remove unused stepper field - Some formatting fixes - Don't pointlessly include pixman-combine32.h - Don't offset x for each pixel; go back to offsetting left_x and right_x at reset time. The offsets cancel out in the formula above, so there is no impact on the calcualations. --- pixman/pixman-gradient-walker.c | 106 +++++++++++++++++++++++++-------------- pixman/pixman-private.h | 9 ++-- 2 files changed, 72 insertions(+), 43 deletions(-) diff --git a/pixman/pixman-gradient-walker.c b/pixman/pixman-gradient-walker.c index e7e724f..5944a55 100644 --- a/pixman/pixman-gradient-walker.c +++ b/pixman/pixman-gradient-walker.c @@ -37,11 +37,14 @@ _pixman_gradient_walker_init (pixman_gradient_walker_t *walker, walker->stops = gradient->stops; walker->left_x = 0; walker->right_x = 0x10000; - walker->stepper = 0; - walker->left_ag = 0; - walker->left_rb = 0; - walker->right_ag = 0; - walker->right_rb = 0; + walker->a_s = 0.0f; + walker->a_b = 0.0f; + walker->r_s = 0.0f; + walker->r_b = 0.0f; + walker->g_s = 0.0f; + walker->g_b = 0.0f; + walker->b_s = 0.0f; + walker->b_b = 0.0f; walker->repeat = repeat; walker->need_reset = TRUE; @@ -55,6 +58,9 @@ gradient_walker_reset (pixman_gradient_walker_t *walker, pixman_color_t *left_c, *right_c; int n, count = walker->num_stops; pixman_gradient_stop_t *stops = walker->stops; + float la, lr, lg, lb; + float ra, rr, rg, rb; + float lx, rx; if (walker->repeat == PIXMAN_REPEAT_NORMAL) { @@ -116,24 +122,49 @@ gradient_walker_reset (pixman_gradient_walker_t *walker, left_c = right_c; } - walker->left_x = left_x; - walker->right_x = right_x; - walker->left_ag = ((left_c->alpha >> 8) << 16) | (left_c->green >> 8); - walker->left_rb = ((left_c->red & 0xff00) << 8) | (left_c->blue >> 8); - walker->right_ag = ((right_c->alpha >> 8) << 16) | (right_c->green >> 8); - walker->right_rb = ((right_c->red & 0xff00) << 8) | (right_c->blue >> 8); - - if (walker->left_x == walker->right_x || - (walker->left_ag == walker->right_ag && - walker->left_rb == walker->right_rb)) + /* The alpha channel is scaled to be in the [0, 255] interval, + * and the red/green/blue channels are scaled to be in [0, 1]. + * This ensures that after premultiplication all channels will + * be in the [0, 255] interval. + */ + la = (left_c->alpha * (1.0f/257.0f)); + lr = (left_c->red * (1.0f/257.0f)); + lg = (left_c->green * (1.0f/257.0f)); + lb = (left_c->blue * (1.0f/257.0f)); + + ra = (right_c->alpha * (1.0f/257.0f)); + rr = (right_c->red * (1.0f/257.0f)); + rg = (right_c->green * (1.0f/257.0f)); + rb = (right_c->blue * (1.0f/257.0f)); + + lx = left_x * (1.0f/65536.0f); + rx = right_x * (1.0f/65536.0f); + + if (FLOAT_IS_ZERO (rx - lx) || left_x == INT32_MIN || right_x == INT32_MAX) { - walker->stepper = 0; + walker->a_s = walker->r_s = walker->g_s = walker->b_s = 0.0f; + walker->a_b = (la + ra) / 2.0f; + walker->r_b = (lr + rr) / 510.0f; + walker->g_b = (lg + rg) / 510.0f; + walker->b_b = (lb + rb) / 510.0f; } else { - int32_t width = right_x - left_x; - walker->stepper = ((1 << 24) + width / 2) / width; + float w_rec = 1.0f / (rx - lx); + + walker->a_b = (la * rx - ra * lx) * w_rec; + walker->r_b = (lr * rx - rr * lx) * w_rec * (1.0f/255.0f); + walker->g_b = (lg * rx - rg * lx) * w_rec * (1.0f/255.0f); + walker->b_b = (lb * rx - rb * lx) * w_rec * (1.0f/255.0f); + + walker->a_s = (ra - la) * w_rec; + walker->r_s = (rr - lr) * w_rec * (1.0f/255.0f); + walker->g_s = (rg - lg) * w_rec * (1.0f/255.0f); + walker->b_s = (rb - lb) * w_rec * (1.0f/255.0f); } + + walker->left_x = left_x; + walker->right_x = right_x; walker->need_reset = FALSE; } @@ -142,31 +173,30 @@ uint32_t _pixman_gradient_walker_pixel (pixman_gradient_walker_t *walker, pixman_fixed_48_16_t x) { - int dist, idist; - uint32_t t1, t2, a, color; + float a, r, g, b; + uint8_t a8, r8, g8, b8; + uint32_t v; + float y; if (walker->need_reset || x < walker->left_x || x >= walker->right_x) - gradient_walker_reset (walker, x); - - dist = ((int)(x - walker->left_x) * walker->stepper) >> 16; - idist = 256 - dist; + gradient_walker_reset (walker, x); - /* combined INTERPOLATE and premultiply */ - t1 = walker->left_rb * idist + walker->right_rb * dist; - t1 = (t1 >> 8) & 0xff00ff; + y = x * (1.0f / 65536.0f); - t2 = walker->left_ag * idist + walker->right_ag * dist; - t2 &= 0xff00ff00; + a = walker->a_s * y + walker->a_b; + r = a * (walker->r_s * y + walker->r_b); + g = a * (walker->g_s * y + walker->g_b); + b = a * (walker->b_s * y + walker->b_b); - color = t2 & 0xff000000; - a = t2 >> 24; + a8 = a + 0.5f; + r8 = r + 0.5f; + g8 = g + 0.5f; + b8 = b + 0.5f; - t1 = t1 * a + 0x800080; - t1 = (t1 + ((t1 >> 8) & 0xff00ff)) >> 8; + v = ((a8 << 24) & 0xff000000) | + ((r8 << 16) & 0x00ff0000) | + ((g8 << 8) & 0x0000ff00) | + ((b8 >> 0) & 0x000000ff); - t2 = (t2 >> 8) * a + 0x800080; - t2 = (t2 + ((t2 >> 8) & 0xff00ff)); - - return (color | (t1 & 0xff00ff) | (t2 & 0xff00)); + return v; } - diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h index 91e329f..6d9c053 100644 --- a/pixman/pixman-private.h +++ b/pixman/pixman-private.h @@ -319,13 +319,12 @@ _pixman_image_validate (pixman_image_t *image); */ typedef struct { - uint32_t left_ag; - uint32_t left_rb; - uint32_t right_ag; - uint32_t right_rb; + float a_s, a_b; + float r_s, r_b; + float g_s, g_b; + float b_s, b_b; pixman_fixed_t left_x; pixman_fixed_t right_x; - pixman_fixed_t stepper; pixman_gradient_stop_t *stops; int num_stops; -- 1.7.4 _______________________________________________ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman