summaryrefslogtreecommitdiff
path: root/gs/base/gdevmrun.c
diff options
context:
space:
mode:
Diffstat (limited to 'gs/base/gdevmrun.c')
-rw-r--r--gs/base/gdevmrun.c617
1 files changed, 617 insertions, 0 deletions
diff --git a/gs/base/gdevmrun.c b/gs/base/gdevmrun.c
new file mode 100644
index 000000000..c5433dbd3
--- /dev/null
+++ b/gs/base/gdevmrun.c
@@ -0,0 +1,617 @@
+/* Copyright (C) 2001-2006 Artifex Software, Inc.
+ All Rights Reserved.
+
+ This software is provided AS-IS with no warranty, either express or
+ implied.
+
+ This software is distributed under license and may not be copied, modified
+ or distributed except as expressly authorized under the terms of that
+ license. Refer to licensing information at http://www.artifex.com/
+ or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
+ San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information.
+*/
+/* $Id$ */
+/* Run-length encoded memory device */
+#include "memory_.h"
+#include "gx.h"
+#include "gserrors.h"
+#include "gxdevice.h"
+#include "gdevmrun.h"
+
+/*
+ * NOTE: THIS CODE HAS NOT BEEN TESTED. IF YOU WANT TO USE IT, PLEASE
+ * TEST IT CAREFULLY AND REPORT ANY PROBLEMS.
+ */
+
+/*
+ * Define the representation of each run. We store runs in a doubly-linked
+ * list. Run 0 is a dummy end-of-line run; run 1 is a dummy start-of-line
+ * run. The dummy runs have length MAX_RUN_LENGTH to prevent merging.
+ *
+ * We limit the number of runs per line for two reasons: if there are many
+ * runs, the run-length representation probably isn't buying us much; and
+ * we need to allocate temporary space on the stack for the runs when we
+ * expand a line to uncompressed form.
+ */
+typedef gx_color_index run_value;
+typedef uint run_index;
+#define RUN_INDEX_BITS 10 /* see above */
+#define MAX_RUNS (1 << RUN_INDEX_BITS)
+#define MAX_RUN_INDEX (MAX_RUNS - 1)
+typedef uint run_length;
+#define RUN_LENGTH_BITS (32 - 2 * RUN_INDEX_BITS)
+#define MAX_RUN_LENGTH ((1 << RUN_LENGTH_BITS) - 1)
+typedef struct run_s {
+ run_value value;
+ run_length length : RUN_LENGTH_BITS;
+ run_index next : RUN_INDEX_BITS;
+ run_index prev : RUN_INDEX_BITS; /* 0 iff free run */
+} run;
+
+/*
+ * Define a pointer into a run list.
+ * For speed, we keep both the index of and the pointer to the current run.
+ */
+typedef struct run_ptr_s {
+ run *ptr;
+ run_index index; /* index of current run */
+} run_ptr;
+typedef struct const_run_ptr_s {
+ const run *ptr;
+ run_index index; /* index of current run */
+} const_run_ptr;
+
+/* Accessors */
+#define RP_LENGTH(rp) ((rp).ptr->length)
+#define RP_VALUE(rp) ((rp).ptr->value)
+#define RP_NEXT(rp) ((rp).ptr->next)
+#define RP_PREV(rp) ((rp).ptr->prev)
+#define RL_DATA(line) ((run *)((line) + 1))
+#define CONST_RL_DATA(line) ((const run *)((line) + 1))
+#define RDEV_LINE(rdev, y) ((run_line *)scan_line_base(&(rdev)->md, y))
+/* Traversers */
+#define RP_AT_START(rp) ((rp).index == 1)
+#define RP_AT_END(rp) ((rp).index == 0)
+#define RP_TO_START(rp, data)\
+ ((rp).index = (data)[1].next,\
+ (rp).ptr = (data) + (rp).index)
+/* Note that RP_TO_NEXT and RP_TO_PREV allow rpn == rpc. */
+#define RP_TO_NEXT(rpc, data, rpn)\
+ ((rpn).ptr = (data) + ((rpn).index = RP_NEXT(rpc)))
+#define RP_TO_PREV(rpc, data, rpp)\
+ ((rpp).ptr = (data) + ((rpp).index = RP_PREV(rpc)))
+
+/*
+ * Define the state of a single scan line.
+ *
+ * We maintain the following invariant: if two adjacent runs have the
+ * same value, the sum of their lengths is greater than MAX_RUN_LENGTH.
+ * This may miss optimality by nearly a factor of 2, but it's far easier
+ * to maintain than a true optimal representation.
+ *
+ * For speed in the common case where nothing other than white is ever stored,
+ * we initially don't bother to construct the runs (or the free run list)
+ * for a line at all.
+ */
+typedef struct run_line_s {
+ gx_color_index zero; /* device white if line not initialized, */
+ /* gx_no_color_index if initialized */
+ uint xcur; /* x value at cursor position */
+ run_ptr rpcur; /* cursor */
+ run_index free; /* head of free list */
+} run_line;
+
+/* Insert/delete */
+static void
+rp_delete_next(run_ptr *prpc, run *data, run_line *line)
+{
+ run_ptr rpn, rpn2;
+
+ RP_TO_NEXT(*prpc, data, rpn);
+ RP_TO_NEXT(rpn, data, rpn2);
+ RP_NEXT(*prpc) = rpn2.index;
+ RP_PREV(rpn2) = prpc->index;
+ RP_NEXT(rpn) = line->free;
+ RP_PREV(rpn) = 0;
+ line->free = rpn.index;
+}
+static int
+rp_insert_next(run_ptr *prpc, run *data, run_line *line, run_ptr *prpn)
+{
+ run_index new = line->free;
+ run *prnew = data + new;
+
+ if (new == 0)
+ return -1;
+ RP_TO_NEXT(*prpc, data, *prpn);
+ RP_NEXT(*prpc) = new;
+ RP_PREV(*prpn) = new;
+ line->free = prnew->next;
+ prnew->prev = prpc->index;
+ prnew->next = prpn->index;
+ prpn->index = new;
+ prpn->ptr = prnew;
+ return 0;
+}
+static int
+rp_insert_prev(run_ptr *prpc, run *data, run_line *line, run_ptr *prpp)
+{
+ run_index new = line->free;
+ run *prnew = data + new;
+
+ if (new == 0)
+ return -1;
+ RP_TO_PREV(*prpc, data, *prpp);
+ RP_NEXT(*prpp) = new;
+ RP_PREV(*prpc) = new;
+ line->free = prnew->next;
+ prnew->prev = prpp->index;
+ prnew->next = prpc->index;
+ prpp->index = new;
+ prpp->ptr = prnew;
+ return 0;
+}
+
+/* Define the run-oriented device procedures. */
+static dev_proc_copy_mono(run_copy_mono);
+static dev_proc_copy_color(run_copy_color);
+static dev_proc_fill_rectangle(run_fill_rectangle);
+static dev_proc_copy_alpha(run_copy_alpha);
+static dev_proc_strip_tile_rectangle(run_strip_tile_rectangle);
+static dev_proc_strip_copy_rop(run_strip_copy_rop);
+static dev_proc_get_bits_rectangle(run_get_bits_rectangle);
+
+/*
+ * Convert a memory device to run-length form. The mdev argument should be
+ * const, but it isn't because we need to call gx_device_white.
+ */
+int
+gdev_run_from_mem(gx_device_run *rdev, gx_device_memory *mdev)
+{
+ int runs_per_line =
+ (bitmap_raster(mdev->width * mdev->color_info.depth) -
+ sizeof(run_line)) / sizeof(run);
+ /*
+ * We use the scan lines of the memory device for storing runs. We need
+ * ceil(width / MAX_RUN_LENGTH) runs to represent a line where all
+ * elements have the same value, +2 for the start and end runs.
+ */
+ int min_runs = (mdev->width + (MAX_RUN_LENGTH - 1)) / MAX_RUN_LENGTH + 2;
+ int i;
+ gx_color_index white = gx_device_white((gx_device *)mdev);
+
+ rdev->md = *mdev;
+ if (runs_per_line > MAX_RUNS)
+ runs_per_line = MAX_RUNS;
+ if (runs_per_line < min_runs)
+ return 0; /* just use the memory device as-is */
+ for (i = 0; i < mdev->height; ++i) {
+ run_line *line = RDEV_LINE(rdev, i);
+
+ line->zero = white;
+ }
+ rdev->runs_per_line = runs_per_line;
+ rdev->umin = 0;
+ rdev->umax1 = mdev->height;
+ rdev->smin = mdev->height;
+ rdev->smax1 = 0;
+ /* Save and replace the representation-aware rendering procedures. */
+#define REPLACE(proc, rproc)\
+ (rdev->save_procs.proc = dev_proc(&rdev->md, proc),\
+ set_dev_proc(&rdev->md, proc, rproc))
+ REPLACE(copy_mono, run_copy_mono);
+ REPLACE(copy_color, run_copy_color);
+ REPLACE(fill_rectangle, run_fill_rectangle);
+ REPLACE(copy_alpha, run_copy_alpha);
+ REPLACE(strip_tile_rectangle, run_strip_tile_rectangle);
+ REPLACE(strip_copy_rop, run_strip_copy_rop);
+ REPLACE(get_bits_rectangle, run_get_bits_rectangle);
+#undef REPLACE
+ return 0;
+}
+
+/* Convert a scan line to expanded form in place. */
+static int
+run_expand(gx_device_run *rdev, int y)
+{
+ const run_line *line = RDEV_LINE(rdev, y);
+ const run *const data = CONST_RL_DATA(line);
+ const_run_ptr rp;
+ int n, x, w;
+#if RUN_LENGTH_BITS <= 8
+ byte length[MAX_RUNS];
+#else
+# if RUN_LENGTH_BITS <= 16
+ ushort length[MAX_RUNS];
+# else
+ uint length[MAX_RUNS];
+# endif
+#endif
+ gx_color_index value[MAX_RUNS];
+
+ if (line->zero != gx_no_color_index) {
+ rdev->save_procs.fill_rectangle((gx_device *)&rdev->md,
+ 0, y, rdev->md.width, 1, line->zero);
+ return 0;
+ }
+ /* Copy the runs into local storage to avoid stepping on our own toes. */
+ for (n = 0, RP_TO_START(rp, data); !RP_AT_END(rp);
+ ++n, RP_TO_NEXT(rp, data, rp)
+ ) {
+ length[n] = RP_LENGTH(rp);
+ value[n] = RP_VALUE(rp);
+ }
+ for (x = 0, n = 0; x < rdev->md.width; x += w, ++n) {
+ w = length[n];
+ rdev->save_procs.fill_rectangle((gx_device *)&rdev->md,
+ x, y, w, 1, value[n]);
+ }
+ return 0;
+}
+
+/*
+ * Convert a range of scan lines to standard form.
+ */
+static int
+run_standardize(gx_device_run *rdev, int y, int h)
+{
+ int ye, iy;
+
+ fit_fill_y(&rdev->md, y, h);
+ fit_fill_h(&rdev->md, y, h);
+ ye = y + h;
+ if (y < rdev->smin) {
+ if (ye > rdev->smax1)
+ run_standardize(rdev, rdev->smax1, ye - rdev->smax1);
+ if (ye < rdev->smin)
+ ye = rdev->smin;
+ rdev->smin = y;
+ } else if (ye > rdev->smax1) {
+ if (y > rdev->smax1)
+ y = rdev->smax1;
+ rdev->smax1 = ye;
+ } else
+ return 0;
+ for (iy = y; iy < ye; ++iy)
+ run_expand(rdev, iy);
+ return 0;
+}
+
+/* Trampoline rendering procedures */
+static int
+run_copy_mono(gx_device * dev, const byte * data, int dx, int raster,
+ gx_bitmap_id id, int x, int y, int w, int h,
+ gx_color_index zero, gx_color_index one)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+
+ run_standardize(rdev, y, h);
+ return rdev->save_procs.copy_mono((gx_device *)&rdev->md,
+ data, dx, raster, id,
+ x, y, w, h, zero, one);
+}
+static int
+run_copy_color(gx_device * dev, const byte * data,
+ int data_x, int raster, gx_bitmap_id id,
+ int x, int y, int w, int h)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+
+ run_standardize(rdev, y, h);
+ return rdev->save_procs.copy_color((gx_device *)&rdev->md,
+ data, data_x, raster, id,
+ x, y, w, h);
+}
+static int
+run_copy_alpha(gx_device * dev, const byte * data, int data_x, int raster,
+ gx_bitmap_id id, int x, int y, int w, int h,
+ gx_color_index color, int depth)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+
+ run_standardize(rdev, y, h);
+ return rdev->save_procs.copy_alpha((gx_device *)&rdev->md,
+ data, data_x, raster, id,
+ x, y, w, h, color, depth);
+}
+static int
+run_strip_tile_rectangle(gx_device * dev, const gx_strip_bitmap * tiles,
+ int x, int y, int w, int h, gx_color_index color0, gx_color_index color1,
+ int px, int py)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+
+ run_standardize(rdev, y, h);
+ return rdev->save_procs.strip_tile_rectangle((gx_device *)&rdev->md,
+ tiles, x, y, w, h,
+ color0, color1, px, py);
+}
+static int
+run_strip_copy_rop(gx_device * dev, const byte * sdata, int sourcex,
+ uint sraster, gx_bitmap_id id,
+ const gx_color_index * scolors,
+ const gx_strip_bitmap * textures,
+ const gx_color_index * tcolors,
+ int x, int y, int w, int h, int px, int py,
+ gs_logical_operation_t lop)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+
+ run_standardize(rdev, y, h);
+ return rdev->save_procs.strip_copy_rop((gx_device *)&rdev->md,
+ sdata, sourcex, sraster,
+ id, scolors, textures, tcolors,
+ x, y, w, h, px, py, lop);
+}
+static int
+run_get_bits_rectangle(gx_device * dev, const gs_int_rect * prect,
+ gs_get_bits_params_t * params, gs_int_rect **unread)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+
+ run_standardize(rdev, prect->p.y, prect->q.y - prect->p.y);
+ return rdev->save_procs.get_bits_rectangle((gx_device *)&rdev->md,
+ prect, params, unread);
+}
+
+/* Finish initializing a line. This is a separate procedure only */
+/* for readability. */
+static void
+run_line_initialize(gx_device_run *rdev, int y)
+{
+ run_line *line = RDEV_LINE(rdev, y);
+ run *data = RL_DATA(line);
+ int left = rdev->md.width;
+ run_index index = 2;
+ run *rcur;
+
+ line->zero = gx_no_color_index;
+ data[0].length = MAX_RUN_LENGTH; /* see above */
+ data[0].value = gx_no_color_index; /* shouldn't matter */
+ data[1].length = MAX_RUN_LENGTH;
+ data[1].value = gx_no_color_index;
+ data[1].next = 2;
+ rcur = data + index;
+ for (; left > 0; index++, rcur++, left -= MAX_RUN_LENGTH) {
+ rcur->length = min(left, MAX_RUN_LENGTH);
+ rcur->value = 0;
+ rcur->prev = index - 1;
+ rcur->next = index + 1;
+ }
+ rcur->next = 0;
+ data[0].prev = index - 1;
+ line->xcur = 0;
+ line->rpcur.ptr = data + 2;
+ line->rpcur.index = 2;
+ line->free = index;
+ for (; index < rdev->runs_per_line; ++index)
+ data[index].next = index + 1;
+ data[index - 1].next = 0;
+ if (y >= rdev->umin && y < rdev->umax1) {
+ if (y > (rdev->umin + rdev->umax1) >> 1)
+ rdev->umax1 = y;
+ else
+ rdev->umin = y + 1;
+ }
+}
+
+/*
+ * Replace an interval of a line with a new value. This is the procedure
+ * that does all the interesting work. We assume the line has been
+ * initialized, and that 0 <= xo < xe <= dev->width.
+ */
+static int
+run_fill_interval(run_line *line, int xo, int xe, run_value new)
+{
+ run *data = RL_DATA(line);
+ int xc = line->xcur;
+ run_ptr rpc;
+ int x0, x1;
+ run_ptr rp0;
+ int code;
+
+ rpc = line->rpcur;
+
+ /* Find the run that contains xo. */
+
+ if (xo < xc) {
+ while (xo < xc)
+ RP_TO_PREV(rpc, data, rpc), xc -= RP_LENGTH(rpc);
+ } else {
+ while (xo >= xc + RP_LENGTH(rpc))
+ xc += RP_LENGTH(rpc), RP_TO_NEXT(rpc, data, rpc);
+ }
+
+ /*
+ * Skip runs above xo that already contain the new value.
+ * If the entire interval already has the correct value, exit.
+ * If we skip any such runs, set xo to just above them.
+ */
+
+ for (; !RP_AT_END(rpc) && RP_VALUE(rpc) == new;
+ RP_TO_NEXT(rpc, data, rpc)
+ )
+ if ((xo = xc += RP_LENGTH(rpc)) >= xe)
+ return 0;
+ x0 = xc, rp0 = rpc;
+
+ /* Find the run that contains xe-1. */
+
+ while (xe > xc + RP_LENGTH(rpc))
+ xc += RP_LENGTH(rpc), RP_TO_NEXT(rpc, data, rpc);
+
+ /*
+ * Skip runs below xe that already contain the new value.
+ * (We know that some run between xo and xe doesn't.)
+ * If we skip any such runs, set xe to just below them.
+ */
+
+ while (RP_TO_PREV(rpc, data, rpc), RP_VALUE(rpc) == new)
+ xe = xc -= RP_LENGTH(rpc);
+ RP_TO_NEXT(rpc, data, rpc);
+
+ /*
+ * At this point, we know the following:
+ * x0 <= xo < x0 + RP_LENGTH(rp0).
+ * RP_VALUE(rp0) != new.
+ * xc <= xe-1 < xc + RP_LENGTH(rpc).
+ * RP_VALUE(rpc) != new.
+ * Note that rp0 and rpc may point to the same run.
+ */
+
+ /* Split off any unaffected prefix of the run at rp0. */
+
+ if (x0 < xo) {
+ uint diff = xo - x0;
+ run_value v0 = RP_VALUE(rp0);
+ run_ptr rpp;
+
+ RP_TO_PREV(rp0, data, rpp);
+ if (RP_VALUE(rpp) == v0 && RP_LENGTH(rpp) + diff <= MAX_RUN_LENGTH)
+ RP_LENGTH(rpp) += diff;
+ else {
+ code = rp_insert_prev(&rp0, data, line, &rpp);
+ if (code < 0)
+ return code;
+ RP_LENGTH(rpp) = diff;
+ RP_VALUE(rpp) = v0;
+ }
+ RP_LENGTH(rp0) -= diff;
+ }
+
+ /* Split off any unaffected suffix of the run at rpc. */
+
+ x1 = xc + RP_LENGTH(rpc);
+ if (x1 > xe) {
+ uint diff = x1 - xe;
+ run_value vc = RP_VALUE(rpc);
+ run_ptr rpn;
+
+ RP_TO_NEXT(rpc, data, rpn);
+ if (RP_VALUE(rpn) == vc && RP_LENGTH(rpn) + diff <= MAX_RUN_LENGTH)
+ RP_LENGTH(rpn) += diff;
+ else {
+ code = rp_insert_next(&rpc, data, line, &rpn);
+ if (code < 0)
+ return code;
+ RP_LENGTH(rpn) = diff;
+ RP_VALUE(rpn) = vc;
+ }
+ RP_LENGTH(rpc) -= diff;
+ }
+
+ /* Delete all runs from rp0 through rpc. */
+
+ RP_TO_PREV(rp0, data, rp0);
+ while (RP_NEXT(rp0) != RP_NEXT(rpc))
+ rp_delete_next(&rp0, data, line);
+
+ /*
+ * Finally, insert new runs with the new value.
+ * We need to check for one boundary case, namely,
+ * xo == x0 and the next lower run has the new value.
+ * (There's probably a way to structure the code just slightly
+ * differently to avoid this test.)
+ */
+
+ {
+ uint left = xe - xo;
+
+ if (xo == x0 && RP_VALUE(rp0) == new &&
+ RP_LENGTH(rp0) + left <= MAX_RUN_LENGTH
+ )
+ RP_LENGTH(rp0) += left;
+ else {
+ /*
+ * If we need more than one run, we divide up the length to
+ * create more runs with length less than MAX_RUN_LENGTH in
+ * order to improve the chances of a later merge. However,
+ * we still guarantee that we won't create more runs than
+ * the minimum number required to represent the length.
+ */
+ run_length len;
+
+ if (left <= MAX_RUN_LENGTH)
+ len = left;
+ else {
+ /*len = ceil(left / ceil(left / MAX_RUN_LENGTH))*/
+ int pieces = left + (MAX_RUN_LENGTH - 1) / MAX_RUN_LENGTH;
+
+ len = (left + pieces - 1) / pieces;
+ }
+ do {
+ run_ptr rpn;
+
+ /*
+ * The allocation in rp_insert_next can't fail, because
+ * we just deleted at least as many runs as we're going
+ * to insert.
+ */
+ rp_insert_next(&rp0, data, line, &rpn);
+ RP_LENGTH(rpn) = min(left, len);
+ RP_VALUE(rpn) = new;
+ }
+ while ((left -= len) > 0);
+ }
+ }
+
+ return 0;
+}
+
+/* Replace a rectangle with a new value. */
+static int
+run_fill_rectangle(gx_device *dev, int x, int y, int w, int h,
+ gx_color_index color)
+{
+ gx_device_run *const rdev = (gx_device_run *)dev;
+ int xe, ye;
+ int iy;
+
+ fit_fill(dev, x, y, w, h);
+ ye = y + h;
+ /*
+ * If the new value is white and the rectangle falls entirely within
+ * the uninitialized region that we're keeping track of,
+ * we can skip the entire operation.
+ */
+ if (y >= rdev->umin && ye <= rdev->umax1 &&
+ color == RDEV_LINE(rdev, y)->zero
+ )
+ return 0;
+
+ /*
+ * Hand off any parts of the operation that fall within the area
+ * already in standard form.
+ */
+ if (y < rdev->smax1 && ye > rdev->smin) {
+ /* Some part of the operation must be handed off. */
+ if (y < rdev->smin) {
+ run_fill_rectangle(dev, x, y, w, rdev->smin - y, color);
+ y = rdev->smin;
+ }
+ /* Now rdev->smin <= y < ye. */
+ rdev->save_procs.fill_rectangle((gx_device *)&rdev->md,
+ x, y, w, min(ye, rdev->smax1) - y,
+ color);
+ if (ye <= rdev->smax1)
+ return 0;
+ y = rdev->smax1;
+ }
+ xe = x + w;
+ for (iy = y; iy < ye; ++iy) {
+ run_line *line = RDEV_LINE(rdev, iy);
+
+ if (color != line->zero) {
+ if (line->zero != gx_no_color_index)
+ run_line_initialize(rdev, iy);
+ if (run_fill_interval(line, x, xe, color) < 0) {
+ /* We ran out of runs. Convert to expanded form. */
+ run_standardize(rdev, iy, 1);
+ rdev->save_procs.fill_rectangle((gx_device *)&rdev->md,
+ x, iy, w, 1, color);
+ }
+ }
+ }
+ return 0;
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-08 11:45:35 +0000