[gs-cvs] rev 8421 - trunk/gs/src

[leonardo at ghostscript.com]

Author: leonardo
Date: 2007-12-03 12:07:05 -0800 (Mon, 03 Dec 2007)
New Revision: 8421

Modified:
   trunk/gs/src/gdevdsha.c
Log:
Fix (shadings) : Optimize fill_linear_color_scanline with analitic computation of the color change position.

DETAILS :

Debugged with the test case of the bug 689155.

This optimizes slightly changing gradients.
It speeds up the test case from 6 hours to 5 hours.

The old code in gx_default_fill_linear_color_scanline 
recomputes color for each pixel.
The new code checks whether neighbour pixels have same color,
and if so it finds the color change position 
with solving a linear equation, 
and fills entire constant color interval 
without computing color for each pixel.

The linear equation is solved with 64 bits arithmetics.
We would like to create a 32bits algorithm someday.
We think it is possible with rounding colors to 16 bits
and restricting a run length with 15 bits. 
Note it must not accummulate rounding errors,
so it needs to compute from the run start at each iteration.
So if the scanline is wide, first split it into smaller ones
by coordinates, then break each subscanline into runs by color changes.

EXPECTED DIFFERENCES :
      
None.


Modified: trunk/gs/src/gdevdsha.c
===================================================================
--- trunk/gs/src/gdevdsha.c	2007-11-30 22:13:49 UTC (rev 8420)
+++ trunk/gs/src/gdevdsha.c	2007-12-03 20:07:05 UTC (rev 8421)
@@ -32,11 +32,11 @@
      */
     frac31 c[GX_DEVICE_COLOR_MAX_COMPONENTS];
     ulong f[GX_DEVICE_COLOR_MAX_COMPONENTS];
-    int i, i1 = i0 + w, bi = i0, k;
+    int i, i1 = i0 + w, i1a = i1 - 1, bi = i0, k;
     gx_color_index ci0 = 0, ci1;
     const gx_device_color_info *cinfo = &dev->color_info;
     int n = cinfo->num_components;
-    int si, ei, code;
+    int si, ei, di, code;
 
     if (j < fixed2int(fa->clip->p.y) ||
 	    j > fixed2int_ceiling(fa->clip->q.y)) /* Must be compatible to the clipping logic. */
@@ -49,27 +49,53 @@
 	f[k] = c0f[k];
 	ci0 |= (gx_color_index)(c[k] >> (sizeof(c[k]) * 8 - 1 - bits)) << shift;
     }
-    for (i = i0 + 1; i < i1; i++) {
-	ci1 = 0;
-	for (k = 0; k < n; k++) {
-	    int shift = cinfo->comp_shift[k];
-	    int bits = cinfo->comp_bits[k];
-	    int32_t m = f[k] + cg_num[k];
+    for (i = i0 + 1, di = 1; i < i1; i += di) {
+	if (di == 1) {
+	    /* Advance colors by 1 pixel. */
+	    ci1 = 0;
+	    for (k = 0; k < n; k++) {
+		int shift = cinfo->comp_shift[k];
+		int bits = cinfo->comp_bits[k];
 
-	    c[k] += m / cg_den;
-	    m -= m / cg_den * cg_den;
-	    if (m < 0) {
-		c[k]--;
-		m += cg_den;
+		if (cg_num[k]) {
+		    int32_t m = f[k] + cg_num[k];
+
+		    c[k] += m / cg_den;
+		    m -= m / cg_den * cg_den;
+		    if (m < 0) {
+			c[k]--;
+			m += cg_den;
+		    }
+		    f[k] = m;
+		}
+		ci1 |= (gx_color_index)(c[k] >> (sizeof(c[k]) * 8 - 1 - bits)) << shift;
 	    }
-	    f[k] = m;
-	    ci1 |= (gx_color_index)(c[k] >> (sizeof(c[k]) * 8 - 1 - bits)) << shift;
+	} else {
+	    /* Advance colors by di pixels. */
+	    ci1 = 0;
+	    for (k = 0; k < n; k++) {
+		int shift = cinfo->comp_shift[k];
+		int bits = cinfo->comp_bits[k];
+
+		if (cg_num[k]) {
+		    int64_t M = f[k] + (int64_t)cg_num[k] * di;
+		    int32_t m;
+
+		    c[k] += (frac31)(M / cg_den);
+		    m = (int32_t)(M - M / cg_den * cg_den);
+		    if (m < 0) {
+			c[k]--;
+			m += cg_den;
+		    }
+		    f[k] = m;
+		}
+		ci1 |= (gx_color_index)(c[k] >> (sizeof(c[k]) * 8 - 1 - bits)) << shift;
+	    }
 	}
 	if (ci1 != ci0) {
 	    si = max(bi, fixed2int(fa->clip->p.x));	    /* Must be compatible to the clipping logic. */
 	    ei = min(i, fixed2int_ceiling(fa->clip->q.x));  /* Must be compatible to the clipping logic. */
 	    if (si < ei) {
-		
 		if (fa->swap_axes) {
 		    vd_rect(int2fixed(j), int2fixed(si), int2fixed(j + 1), int2fixed(ei), 1, (ulong)ci0);
 		    code = dev_proc(dev, fill_rectangle)(dev, j, si, 1, ei - si, ci0);
@@ -82,6 +108,42 @@
 	    }
 	    bi = i;
 	    ci0 = ci1;
+	    di = 1;
+	} else if (i == i1) {
+	    i++;
+	    break;
+	} else {
+	    /* Compute a color change pixel analitically. */
+	    di = i1 - i;
+	    for (k = 0; k < n; k++) {
+		int32_t a;
+		int64_t x;
+		frac31 v = 1 << (31 - cinfo->comp_bits[k]); /* Color index precision in frac31. */
+		frac31 u = c[k] & (v - 1);
+
+		if (cg_num[k] == 0) {
+		    /* No change. */
+		    continue;
+		} if (cg_num[k] > 0) {
+		    /* Solve[(f[k] + cg_num[k]*x)/cg_den == v - u, x]  */
+		    a = v - u;
+		} else {
+		    /* Solve[(f[k] + cg_num[k]*x)/cg_den == - u - 1, x]  */
+		    a = -u - 1;
+		}
+		x = ((int64_t)a * cg_den - f[k]) / cg_num[k];
+		if (i + x >= i1)
+		    continue;
+		else if (x < 0)
+		    return_error(gs_error_unregistered); /* Must not happen. */
+		else if (di > (int)x) {
+		    di = (int)x;
+		    if (di <= 1) {
+			di = 1;
+			break;
+		    }
+		}
+	    }
 	}
     }
     si = max(bi, fixed2int(fa->clip->p.x));	    /* Must be compatible to the clipping logic. */