Bug 703414 : Halftone artifacts

There are two different representations of the turn-on-sequence
in GS.  One of them uses an array of unsigned short integers that
indicate what bits get turned on.  The array stores an address
offset into the bitmap tile that is created for a particular level.
The decision to use this representation is made in gsht.c
in the gx_ht_alloc_theshold_order method and is based upon the
width and height of the threshold array which indicates the total
number of addresses or offsets into the tile to reference which
bits get turned on in the tile by the turn-on-sequence.  The tiles
themselves however are forced to have their rows raster aligned meaning
that if w*h <= 65535 the offsets into the tile dots can be larger
than 65535, which will not fit in the short turn-on-sequence array.
The code uses a different representation for the TOS if the number
of elements is less than 2000.  Then it stores a pointer to a structure
for every element.  That is the "default" implementation.  Here
a uint (32-bit) implementation is added for cases where the tile is
larger than 65536 (e.g. bigger than 256 x 256).  The implementation is
the same as the ushort case, but just uses four byte offsets for the TOS.

3 files changed, 166 insertions, 8 deletions

diff --git a/base/gsht.c b/base/gsht.c
index 6be423ac6..e7b183f33 100644
--- a/base/gsht.c
+++ b/base/gsht.c
@@ -387,12 +387,20 @@ gx_ht_alloc_threshold_order(gx_ht_order * porder, uint width, uint height,
                             uint num_levels, gs_memory_t * mem)
 {
     gx_ht_order order;
-    uint num_bits = width * height;
-    const gx_ht_order_procs_t *procs =
-        (num_bits > 2000 && num_bits <= max_ushort ?
-         &ht_order_procs_short : &ht_order_procs_default);
+
+    unsigned long num_bits = bitmap_raster(width) * 8 * height;
+    const gx_ht_order_procs_t *procs;
     int code;
 
+    if (num_bits <= 2000)
+        procs = &ht_order_procs_default;
+    else if (num_bits <= max_ushort + 1)  /* We can index 0 to 65535 so a size of 65536 (max_ushort + 1) is OK */
+        procs = &ht_order_procs_short;
+    else if (num_bits <= max_uint)
+        procs = &ht_order_procs_uint;
+    else
+        return_error(gs_error_VMerror);  /* At this point in history, this is way too large of a screen */
+
     order = *porder;
     gx_compute_cell_values(&order.params);
     code = gx_ht_alloc_ht_order(&order, width, height, num_levels,
diff --git a/base/gxdht.h b/base/gxdht.h
index 8bb51c2c7..b4b85307f 100644
--- a/base/gxdht.h
+++ b/base/gxdht.h
@@ -188,11 +188,14 @@ typedef struct gx_ht_order_procs_s {
 } gx_ht_order_procs_t;
 /*
  * Define the procedure vectors for the supported implementations
- * (in gxhtbit.c).
+ * (in gxhtbit.c).  This defines the type of data that the turn-on-sequence (TOS)
+ * elements are pointing too.  For the ushort and uint case, they are offsets
+ * into the address of the bitmap tiles.
  */
-extern const gx_ht_order_procs_t ht_order_procs_table[2];
+extern const gx_ht_order_procs_t ht_order_procs_table[3];
 #define ht_order_procs_default ht_order_procs_table[0]	/* bit_data is gx_ht_bit[] */
 #define ht_order_procs_short ht_order_procs_table[1]	/* bit_data is ushort[] */
+#define ht_order_procs_uint ht_order_procs_table[2]     /* bit_data is uint[] */
 /* For screen/spot halftones, we must record additional parameters. */
 typedef struct gx_ht_order_screen_params_s {
     gs_matrix matrix;		/* CTM when the function was sampled */
diff --git a/base/gxhtbit.c b/base/gxhtbit.c
index 442952486..03a09c1b6 100644
--- a/base/gxhtbit.c
+++ b/base/gxhtbit.c
@@ -136,6 +136,81 @@ construct_ht_order_short(gx_ht_order *porder, const byte *thresholds)
     return 0;
 }
 
+/*
+ * Construct a uint-representation order from a threshold array.
+ * Uses porder->width, num_levels, num_bits, levels, bit_data;
+ * sets porder->levels[], bit_data[].
+ */
+static int
+construct_ht_order_uint(gx_ht_order *porder, const byte *thresholds)
+{
+    uint size = porder->num_bits;
+    uint i;
+    uint *bits = (uint *)porder->bit_data;
+    uint *levels = porder->levels;
+    uint num_levels = porder->num_levels;
+
+    memset(levels, 0, num_levels * sizeof(*levels));
+
+    /* Count the number of threshold elements with each value. */
+    for (i = 0; i < size; i++) {
+        uint value = max(1, thresholds[i]);
+
+        if (value + 1 < num_levels)
+            levels[value + 1]++;
+    }
+    for (i = 2; i < num_levels; ++i)
+        levels[i] += levels[i - 1];
+    /* Now construct the actual order. */
+    {
+        uint width = porder->width;
+        uint padding = bitmap_raster(width) * 8 - width;
+
+        for (i = 0; i < size; i++) {
+            uint value = max(1, thresholds[i]);
+
+            bits[levels[value]++] = i + (i / width * padding);
+        }
+    }
+
+    /* Check whether this is a predefined halftone. */
+    {
+        const gx_dht_proc *phtrp = gx_device_halftone_list;
+
+        for (; *phtrp; ++phtrp) {
+            const gx_device_halftone_resource_t *const *pphtr = (*phtrp)();
+            const gx_device_halftone_resource_t *phtr;
+
+            while ((phtr = *pphtr++) != 0) {
+                if (phtr->Width == porder->width &&
+                    phtr->Height == porder->height &&
+                    phtr->elt_size == sizeof(uint) &&
+                    !memcmp(phtr->levels, levels, num_levels * sizeof(*levels)) &&
+                    !memcmp(phtr->bit_data, porder->bit_data,
+                        (size_t)size * phtr->elt_size)
+                    ) {
+                    /*
+                     * This is a predefined halftone.  Free the levels and
+                     * bit_data arrays, replacing them with the built-in ones.
+                     */
+                    if (porder->data_memory) {
+                        gs_free_object(porder->data_memory, porder->bit_data,
+                            "construct_ht_order_uint(bit_data)");
+                        gs_free_object(porder->data_memory, porder->levels,
+                            "construct_ht_order_uint(levels)");
+                    }
+                    porder->data_memory = 0;
+                    porder->levels = (uint *)phtr->levels; /* actually const */
+                    porder->bit_data = (void *)phtr->bit_data; /* actually const */
+                    goto out;
+                }
+            }
+        }
+    }
+out:
+    return 0;
+}
+
 /* Return the bit coordinate using the standard representation. */
 static int
 ht_bit_index_default(const gx_ht_order *porder, uint index, gs_int_point *ppt)
@@ -163,6 +238,18 @@ ht_bit_index_short(const gx_ht_order *porder, uint index, gs_int_point *ppt)
     return 0;
 }
 
+/* Return the bit coordinate using the uint representation. */
+static int
+ht_bit_index_uint(const gx_ht_order *porder, uint index, gs_int_point *ppt)
+{
+    uint bit_index = ((const uint *)porder->bit_data)[index];
+    uint bit_raster = porder->raster * 8;
+
+    ppt->x = bit_index % bit_raster;
+    ppt->y = bit_index / bit_raster;
+    return 0;
+}
+
 /* Update a halftone tile using the default order representation. */
 static int
 render_ht_default(gx_ht_tile *pbt, int level, const gx_ht_order *porder)
@@ -282,10 +369,70 @@ render_ht_short(gx_ht_tile *pbt, int level, const gx_ht_order *porder)
     return 0;
 }
 
+/* Update a halftone tile using the uint representation. */
+static int
+render_ht_uint(gx_ht_tile *pbt, int level, const gx_ht_order *porder)
+{
+    int old_level = pbt->level;
+    register const uint *p = (const uint *)porder->bit_data + old_level;
+    register byte *data = pbt->tiles.data;
+
+    /* Invert bits between the two levels. */
+#define INVERT_DATA(i)\
+     BEGIN\
+       uint bit_index = p[i];\
+       byte *dp = &data[bit_index >> 3];\
+       *dp ^= 0x80 >> (bit_index & 7);\
+     END
+#ifdef DEBUG
+#  define INVERT(i)\
+     BEGIN\
+       if_debug3('H', "[H]invert level=%d offset=%u mask=0x%x\n",\
+                 (int)(p + i - (const uint *)porder->bit_data),\
+                 p[i] >> 3, 0x80 >> (p[i] & 7));\
+       INVERT_DATA(i);\
+     END
+#else
+#  define INVERT(i) INVERT_DATA(i)
+#endif
+sw:switch (level - old_level) {
+default:
+    if (level > old_level) {
+        INVERT(0); INVERT(1); INVERT(2); INVERT(3);
+        p += 4; old_level += 4;
+    }
+    else {
+        INVERT(-1); INVERT(-2); INVERT(-3); INVERT(-4);
+        p -= 4; old_level -= 4;
+    }
+    goto sw;
+case 7: INVERT(6);
+case 6: INVERT(5);
+case 5: INVERT(4);
+case 4: INVERT(3);
+case 3: INVERT(2);
+case 2: INVERT(1);
+case 1: INVERT(0);
+case 0: break;		/* Shouldn't happen! */
+case -7: INVERT(-7);
+case -6: INVERT(-6);
+case -5: INVERT(-5);
+case -4: INVERT(-4);
+case -3: INVERT(-3);
+case -2: INVERT(-2);
+case -1: INVERT(-1);
+}
+#undef INVERT_DATA
+#undef INVERT
+return 0;
+}
+
 /* Define the procedure vectors for the order data implementations. */
-const gx_ht_order_procs_t ht_order_procs_table[2] = {
+const gx_ht_order_procs_t ht_order_procs_table[3] = {
     { sizeof(gx_ht_bit), construct_ht_order_default, ht_bit_index_default,
       render_ht_default },
     { sizeof(ushort), construct_ht_order_short, ht_bit_index_short,
-      render_ht_short }
+      render_ht_short },
+    { sizeof(uint), construct_ht_order_uint, ht_bit_index_uint,
+      render_ht_uint }
 };