Import Ghostscript 9.50ghostscript-9.50

Signed-off-by: Thomas Deutschmann <whissi@gentoo.org>

1 files changed, 716 insertions, 0 deletions

diff --git a/base/gxpath2.c b/base/gxpath2.c
new file mode 100644
index 00000000..49cad4d7
--- /dev/null
+++ b/base/gxpath2.c
@@ -0,0 +1,716 @@
+/* Copyright (C) 2001-2019 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 the license contained in the file LICENSE in this distribution.
+
+   Refer to licensing information at http://www.artifex.com or contact
+   Artifex Software, Inc.,  1305 Grant Avenue - Suite 200, Novato,
+   CA 94945, U.S.A., +1(415)492-9861, for further information.
+*/
+
+
+/* Path tracing procedures for Ghostscript library */
+#include "math_.h"
+#include "gx.h"
+#include "gserrors.h"
+#include "gspath.h"		/* for gs_path_enum_alloc prototype */
+#include "gsstruct.h"
+#include "gxfixed.h"
+#include "gxarith.h"
+#include "gzpath.h"
+
+/* Define the enumeration structure. */
+public_st_path_enum();
+
+/* Read the current point of a path. */
+int
+gx_path_current_point(const gx_path * ppath, gs_fixed_point * ppt)
+{
+    if (!path_position_valid(ppath))
+        return_error(gs_error_nocurrentpoint);
+    /* Copying the coordinates individually */
+    /* is much faster on a PC, and almost as fast on other machines.... */
+    ppt->x = ppath->position.x, ppt->y = ppath->position.y;
+    return 0;
+}
+
+/* Read the start point of the current subpath. */
+int
+gx_path_subpath_start_point(const gx_path * ppath, gs_fixed_point * ppt)
+{
+    const subpath *psub = ppath->current_subpath;
+
+    if (!psub)
+        return_error(gs_error_nocurrentpoint);
+    *ppt = psub->pt;
+    return 0;
+}
+
+/* Read the bounding box of a path. */
+/* Note that if the last element of the path is a moveto, */
+/* the bounding box does not include this point, */
+/* unless this is the only element of the path. */
+int
+gx_path_bbox(gx_path * ppath, gs_fixed_rect * pbox)
+{
+    if (ppath->bbox_accurate) {
+        /* The bounding box was set by setbbox. */
+        *pbox = ppath->bbox;
+        return 0;
+    }
+    if (ppath->first_subpath == 0) {
+        /* The path is empty, use the current point if any. */
+        int code = gx_path_current_point(ppath, &pbox->p);
+
+        if (code < 0) {
+            /*
+             * Don't return garbage, in case the caller doesn't
+             * check the return code.
+             */
+            pbox->p.x = pbox->p.y = 0;
+        }
+        pbox->q = pbox->p;
+        return code;
+    }
+    /* The stored bounding box may not be up to date. */
+    /* Correct it now if necessary. */
+    if (ppath->box_last == ppath->current_subpath->last) {
+        /* Box is up to date */
+        *pbox = ppath->bbox;
+    } else {
+        fixed px, py, qx, qy;
+        const segment *pseg = ppath->box_last;
+
+        if (pseg == 0) {	/* box is uninitialized */
+            pseg = (const segment *)ppath->first_subpath;
+            px = qx = pseg->pt.x;
+            py = qy = pseg->pt.y;
+        } else {
+            px = ppath->bbox.p.x, py = ppath->bbox.p.y;
+            qx = ppath->bbox.q.x, qy = ppath->bbox.q.y;
+        }
+
+/* Macro for adjusting the bounding box when adding a point */
+#define ADJUST_BBOX(pt)\
+  if ((pt).x < px) px = (pt).x;\
+  else if ((pt).x > qx) qx = (pt).x;\
+  if ((pt).y < py) py = (pt).y;\
+  else if ((pt).y > qy) qy = (pt).y
+
+        while ((pseg = pseg->next) != 0) {
+            switch (pseg->type) {
+                case s_curve:
+                    ADJUST_BBOX(((const curve_segment *)pseg)->p1);
+                    ADJUST_BBOX(((const curve_segment *)pseg)->p2);
+                    /* falls through */
+                default:
+                    ADJUST_BBOX(pseg->pt);
+            }
+        }
+#undef ADJUST_BBOX
+
+#define STORE_BBOX(b)\
+  (b).p.x = px, (b).p.y = py, (b).q.x = qx, (b).q.y = qy;
+        STORE_BBOX(*pbox);
+        STORE_BBOX(ppath->bbox);
+#undef STORE_BBOX
+
+        ppath->box_last = ppath->current_subpath->last;
+    }
+    return 0;
+}
+
+/* A variation of gs_path_bbox, to be used by the patbbox operator */
+int
+gx_path_bbox_set(gx_path * ppath, gs_fixed_rect * pbox)
+{
+    if (ppath->bbox_set) {
+        /* The bounding box was set by setbbox. */
+        *pbox = ppath->bbox;
+        return 0;
+    } else
+        return gx_path_bbox(ppath, pbox);
+}
+
+/* Test if a path has any curves. */
+#undef gx_path_has_curves
+bool
+gx_path_has_curves(const gx_path * ppath)
+{
+    return gx_path_has_curves_inline(ppath);
+}
+#define gx_path_has_curves(ppath)\
+  gx_path_has_curves_inline(ppath)
+
+/* Test if a path has no segments. */
+#undef gx_path_is_void
+bool
+gx_path_is_void(const gx_path * ppath)
+{
+    return gx_path_is_void_inline(ppath);
+}
+#define gx_path_is_void(ppath)\
+  gx_path_is_void_inline(ppath)
+
+/* Test if a path has no elements at all. */
+bool
+gx_path_is_null(const gx_path * ppath)
+{
+    return gx_path_is_null_inline(ppath);
+}
+
+/*
+ * Test if a subpath is a rectangle; if so, return its bounding box
+ * and the start of the next subpath.
+ * Note that this must recognize:
+ *      ordinary closed rectangles (M, L, L, L, C);
+ *      open rectangles (M, L, L, L);
+ *      rectangles closed with lineto (Mo, L, L, L, Lo);
+ *      rectangles closed with *both* lineto and closepath (bad PostScript,
+ *        but unfortunately not rare) (Mo, L, L, L, Lo, C).
+ */
+gx_path_rectangular_type
+gx_subpath_is_rectangular(const subpath * pseg0, gs_fixed_rect * pbox,
+                          const subpath ** ppnext)
+{
+    const segment *pseg1, *pseg2, *pseg3, *pseg4;
+    gx_path_rectangular_type type = prt_none;
+    fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y;
+    fixed x1, y1, x2, y2, x3, y3;
+
+    pseg1 = (const segment *)pseg0;
+    do {
+        pseg1 = pseg1->next;
+        if (pseg1 == NULL)
+            return prt_none;
+        x1 = pseg1->pt.x;
+        y1 = pseg1->pt.y;
+        if (pseg1->type == s_curve) {
+            if (gx_curve_is_really_point(x0, y0, pseg1))
+                continue; /* Ignore this one and try again */
+            if (gx_curve_is_really_line(x0, y0, pseg1))
+                break; /* That'll do! */
+            return prt_none;
+        } else if (pseg1->type != s_line && pseg1->type != s_gap)
+            return prt_none;
+    } while (x1 == x0 && y1 == y0);
+
+    pseg2 = pseg1;
+    do {
+        pseg2 = pseg2->next;
+        if (pseg2 == NULL)
+            return prt_none;
+        x2 = pseg2->pt.x;
+        y2 = pseg2->pt.y;
+        if (pseg2->type == s_curve) {
+            if (gx_curve_is_really_point(x1, y1, pseg2))
+                continue; /* Ignore this one and try again */
+            if (gx_curve_is_really_line(x1, y1, pseg2))
+                break; /* That'll do! */
+            return prt_none;
+        } else if (pseg2->type != s_line && pseg2->type != s_gap)
+            return prt_none;
+    } while (x2 == x1 && y2 == y1);
+
+    pseg3 = pseg2;
+    do {
+        pseg3 = pseg3->next;
+        if (pseg3 == NULL)
+            return prt_none;
+        x3 = pseg3->pt.x;
+        y3 = pseg3->pt.y;
+        if (pseg3->type == s_curve) {
+            if (gx_curve_is_really_point(x2, y2, pseg3))
+                continue; /* Ignore this one and try again */
+            if (gx_curve_is_really_line(x2, y2, pseg3))
+                break; /* That'll do! */
+            return prt_none;
+        } else if (pseg3->type != s_line && pseg3->type != s_gap)
+            return prt_none;
+    } while (x3 == x2 && y3 == y2);
+
+    pseg4 = pseg3;
+    do {
+        pseg4 = pseg4->next;
+        if (pseg4 == NULL || pseg4->type == s_start) {
+            type = prt_open; /* M, L, L, L */
+            goto type_known;
+        }
+        if (pseg4->type == s_curve) {
+            if (gx_curve_is_really_point(x3, y3, pseg4))
+                continue; /* Ignore this one and try again */
+            if (gx_curve_is_really_line(x3, y3, pseg4))
+                break; /* That'll do! */
+            return prt_none;
+        } else if (pseg4->type == s_line_close) {
+            type = prt_closed; /* M, L, L, L, C */
+            goto type_known;
+        }
+    } while (pseg4->pt.x == x3 && pseg4->pt.y == y3);
+
+    if (pseg4->pt.x != pseg0->pt.x || pseg4->pt.y != pseg0->pt.y)
+        return prt_none;
+    else if (pseg4->next == NULL || pseg4->next->type == s_start)
+        type = prt_fake_closed;	/* Mo, L, L, L, L, Mo */
+    else
+        return prt_none;
+
+type_known:
+
+    if ((x0 == x1 && y1 == y2 && x2 == x3 && y3 == y0) ||
+        (x0 == x3 && y3 == y2 && x2 == x1 && y1 == y0)) {
+        /* Path is a rectangle.  Return the bounding box. */
+        if (x0 < x2)
+            pbox->p.x = x0, pbox->q.x = x2;
+        else
+            pbox->p.x = x2, pbox->q.x = x0;
+        if (y0 < y2)
+            pbox->p.y = y0, pbox->q.y = y2;
+        else
+            pbox->p.y = y2, pbox->q.y = y0;
+        while (pseg4 != 0 && pseg4->type != s_start)
+            pseg4 = pseg4->next;
+        *ppnext = (const subpath *)pseg4;
+        return type;
+    }
+    return prt_none;
+}
+/* Test if an entire path to be filled is a rectangle. */
+gx_path_rectangular_type
+gx_path_is_rectangular(const gx_path * ppath, gs_fixed_rect * pbox)
+{
+    const subpath *pnext;
+
+    return
+        (gx_path_subpath_count(ppath) == 1 ?
+         gx_subpath_is_rectangular(ppath->first_subpath, pbox, &pnext) :
+         prt_none);
+}
+
+/* Translate an already-constructed path (in device space). */
+/* Don't bother to update the cbox. */
+int
+gx_path_translate(gx_path * ppath, fixed dx, fixed dy)
+{
+    segment *pseg;
+
+#define update_xy(pt)\
+  pt.x += dx, pt.y += dy
+    if (ppath->box_last != 0) {
+        update_xy(ppath->bbox.p);
+        update_xy(ppath->bbox.q);
+    }
+    if (path_position_valid(ppath))
+        update_xy(ppath->position);
+    for (pseg = (segment *) (ppath->first_subpath); pseg != 0;
+         pseg = pseg->next
+        )
+        switch (pseg->type) {
+            case s_curve:
+#define pcseg ((curve_segment *)pseg)
+                update_xy(pcseg->p1);
+                update_xy(pcseg->p2);
+#undef pcseg
+                /* fall through */
+            default:
+                update_xy(pseg->pt);
+        }
+#undef update_xy
+    return 0;
+}
+
+/* Scale an existing path by a power of 2 (positive or negative).
+ * Currently the path drawing routines can't handle values
+ * close to the edge of the representable space.
+ * Also see clamp_point() in gspath.c .
+ */
+void
+gx_point_scale_exp2(gs_fixed_point * pt, int sx, int sy)
+{
+    int v;
+
+    if (sx > 0) {
+        v = (max_int - int2fixed(1000)) >> sx; /* arbitrary */
+        if (pt->x > v)
+            pt->x = v;
+        else if (pt->x < -v)
+            pt->x = -v;
+        pt->x <<= sx;
+    } else
+        pt->x >>= -sx;
+
+    if (sy > 0) {
+        v = (max_int - int2fixed(1000)) >> sy;
+        if (pt->y > v)
+            pt->y = v;
+        else if (pt->y < -v)
+            pt->y = -v;
+        pt->y <<= sy;
+    } else
+        pt->y >>= -sy;
+}
+void
+gx_rect_scale_exp2(gs_fixed_rect * pr, int sx, int sy)
+{
+    gx_point_scale_exp2(&pr->p, sx, sy);
+    gx_point_scale_exp2(&pr->q, sx, sy);
+}
+int
+gx_path_scale_exp2_shared(gx_path * ppath, int log2_scale_x, int log2_scale_y,
+                          bool segments_shared)
+{
+    segment *pseg;
+
+    gx_rect_scale_exp2(&ppath->bbox, log2_scale_x, log2_scale_y);
+#define SCALE_XY(pt) gx_point_scale_exp2(&pt, log2_scale_x, log2_scale_y)
+    SCALE_XY(ppath->position);
+    if (!segments_shared) {
+        for (pseg = (segment *) (ppath->first_subpath); pseg != 0;
+             pseg = pseg->next
+             )
+            switch (pseg->type) {
+            case s_curve:
+                SCALE_XY(((curve_segment *)pseg)->p1);
+                SCALE_XY(((curve_segment *)pseg)->p2);
+                /* fall through */
+            default:
+                SCALE_XY(pseg->pt);
+            }
+    }
+#undef SCALE_XY
+    return 0;
+}
+
+/*
+ * Reverse a path.  We know ppath != ppath_old.
+ * NOTE: in releases 5.01 and earlier, the implicit line added by closepath
+ * became the first segment of the reversed path.  Starting in release
+ * 5.02, the code follows the Adobe implementation (and LanguageLevel 3
+ * specification), in which this line becomes the *last* segment of the
+ * reversed path.  This can produce some quite unintuitive results.
+ *
+ * The order of the subpaths is unspecified in the PLRM, but the CPSI
+ * reverses the subpaths, and the CET (11-05 p6, test 3) tests for it.
+ */
+int
+gx_path_copy_reversed(const gx_path * ppath_old, gx_path * ppath)
+{
+    const subpath *psub = ppath_old->current_subpath;
+
+#ifdef DEBUG
+    if (gs_debug_c('P'))
+        gx_dump_path(ppath_old, "before reversepath");
+#endif
+ nsp:
+    if (psub) {
+        const segment *prev = psub->last;
+        const segment *pseg;
+        segment_notes notes =
+            (prev == (const segment *)psub ? sn_none :
+             psub->next->notes);
+        segment_notes prev_notes;
+        int code;
+
+        if (!psub->is_closed) {
+            code = gx_path_add_point(ppath, prev->pt.x, prev->pt.y);
+            if (code < 0)
+                return code;
+        }
+        /*
+         * The do ... while structure of this loop is artificial,
+         * designed solely to keep compilers from complaining about
+         * 'statement not reached' or 'end-of-loop code not reached'.
+         * The normal exit from this loop is the goto statement in
+         * the s_start arm of the switch.
+         */
+        do {
+            pseg = prev;
+            prev_notes = notes;
+            prev = pseg->prev;
+            notes = pseg->notes;
+            prev_notes = (prev_notes & sn_not_first) |
+                (notes & ~sn_not_first);
+            switch (pseg->type) {
+                case s_start:
+                    /* Finished subpath */
+                    if (psub->is_closed) {
+                        code =
+                            gx_path_close_subpath_notes(ppath, prev_notes);
+                        if (code < 0)
+                            return code;
+                    }
+                    do {
+                        psub = (const subpath *)psub->prev;
+                    } while (psub && psub->type != s_start);
+                    goto nsp;
+                case s_curve:
+                    {
+                        const curve_segment *pc =
+                        (const curve_segment *)pseg;
+
+                        code = gx_path_add_curve_notes(ppath,
+                                                       pc->p2.x, pc->p2.y,
+                                                       pc->p1.x, pc->p1.y,
+                                        prev->pt.x, prev->pt.y, prev_notes);
+                        break;
+                    }
+                case s_line:
+                    code = gx_path_add_line_notes(ppath,
+                                        prev->pt.x, prev->pt.y, prev_notes);
+                    break;
+                case s_gap:
+                    code = gx_path_add_gap_notes(ppath,
+                                        prev->pt.x, prev->pt.y, prev_notes);
+                    break;
+                case s_line_close:
+                    /* Skip the closing line. */
+                    code = gx_path_add_point(ppath, prev->pt.x,
+                                             prev->pt.y);
+                    break;
+                default:	/* not possible */
+                    return_error(gs_error_Fatal);
+            }
+        } while (code >= 0);
+        return code;		/* only reached if code < 0 */
+    }
+#undef sn_not_end
+    /*
+     * In the Adobe implementations, reversepath discards a trailing
+     * moveto unless the path consists only of a moveto.  We reproduce
+     * this behavior here, even though we consider it a bug.
+     */
+    if (ppath_old->first_subpath == 0 &&
+        path_last_is_moveto(ppath_old)
+        ) {
+        int code = gx_path_add_point(ppath, ppath_old->position.x,
+                                     ppath_old->position.y);
+
+        if (code < 0)
+            return code;
+    }
+#ifdef DEBUG
+    if (gs_debug_c('P'))
+        gx_dump_path(ppath, "after reversepath");
+#endif
+    return 0;
+}
+
+int
+gx_path_append_reversed(const gx_path * ppath_old, gx_path * ppath)
+{
+    const subpath *psub = ppath_old->current_subpath;
+
+#ifdef DEBUG
+    if (gs_debug_c('P'))
+        gx_dump_path(ppath_old, "before reversepath");
+#endif
+ nsp:
+    if (psub) {
+        const segment *prev = psub->last;
+        const segment *pseg;
+        segment_notes notes =
+            (prev == (const segment *)psub ? sn_none :
+             psub->next->notes);
+        segment_notes prev_notes;
+        int code;
+
+        if (!psub->is_closed) {
+            code = gx_path_add_line(ppath, prev->pt.x, prev->pt.y);
+            if (code < 0)
+                return code;
+        }
+        /*
+         * The do ... while structure of this loop is artificial,
+         * designed solely to keep compilers from complaining about
+         * 'statement not reached' or 'end-of-loop code not reached'.
+         * The normal exit from this loop is the goto statement in
+         * the s_start arm of the switch.
+         */
+        do {
+            pseg = prev;
+            prev_notes = notes;
+            prev = pseg->prev;
+            notes = pseg->notes;
+            prev_notes = (prev_notes & sn_not_first) |
+                (notes & ~sn_not_first);
+            switch (pseg->type) {
+                case s_start:
+                    /* Finished subpath */
+                    if (psub->is_closed) {
+                        code =
+                            gx_path_close_subpath_notes(ppath, prev_notes);
+                        if (code < 0)
+                            return code;
+                    }
+                    do {
+                        psub = (const subpath *)psub->prev;
+                    } while (psub && psub->type != s_start);
+                    goto nsp;
+                case s_curve:
+                    {
+                        const curve_segment *pc =
+                        (const curve_segment *)pseg;
+
+                        code = gx_path_add_curve_notes(ppath,
+                                                       pc->p2.x, pc->p2.y,
+                                                       pc->p1.x, pc->p1.y,
+                                        prev->pt.x, prev->pt.y, prev_notes);
+                        break;
+                    }
+                case s_line:
+                    code = gx_path_add_line_notes(ppath,
+                                        prev->pt.x, prev->pt.y, prev_notes);
+                    break;
+                case s_gap:
+                    code = gx_path_add_gap_notes(ppath,
+                                        prev->pt.x, prev->pt.y, prev_notes);
+                    break;
+                case s_line_close:
+                    /* Skip the closing line. */
+                    code = gx_path_add_point(ppath, prev->pt.x,
+                                             prev->pt.y);
+                    break;
+                default:	/* not possible */
+                    return_error(gs_error_Fatal);
+            }
+        } while (code >= 0);
+        return code;		/* only reached if code < 0 */
+    }
+#undef sn_not_end
+    /*
+     * In the Adobe implementations, reversepath discards a trailing
+     * moveto unless the path consists only of a moveto.  We reproduce
+     * this behavior here, even though we consider it a bug.
+     */
+    if (ppath_old->first_subpath == 0 &&
+        path_last_is_moveto(ppath_old)
+        ) {
+        int code = gx_path_add_point(ppath, ppath_old->position.x,
+                                     ppath_old->position.y);
+
+        if (code < 0)
+            return code;
+    }
+#ifdef DEBUG
+    if (gs_debug_c('P'))
+        gx_dump_path(ppath, "after reversepath");
+#endif
+    return 0;
+}
+
+/* ------ Path enumeration ------ */
+
+/* Allocate a path enumerator. */
+gs_path_enum *
+gs_path_enum_alloc(gs_memory_t * mem, client_name_t cname)
+{
+    return gs_alloc_struct(mem, gs_path_enum, &st_path_enum, cname);
+}
+
+/* Start enumerating a path. */
+int
+gx_path_enum_init(gs_path_enum * penum, const gx_path * ppath)
+{
+    penum->memory = 0;		/* path not copied */
+    penum->path = ppath;
+    penum->copied_path = 0;	/* not copied */
+    penum->pseg = (const segment *)ppath->first_subpath;
+    penum->moveto_done = false;
+    penum->notes = sn_none;
+    return 0;
+}
+
+/* Enumerate the next element of a path. */
+/* If the path is finished, return 0; */
+/* otherwise, return the element type. */
+int
+gx_path_enum_next(gs_path_enum * penum, gs_fixed_point ppts[3])
+{
+    const segment *pseg = penum->pseg;
+
+    if (pseg == 0) {		/* We've enumerated all the segments, but there might be */
+        /* a trailing moveto. */
+        const gx_path *ppath = penum->path;
+
+        if (path_last_is_moveto(ppath) && !penum->moveto_done) {	/* Handle a trailing moveto */
+            penum->moveto_done = true;
+            penum->notes = sn_none;
+            ppts[0] = ppath->position;
+            return gs_pe_moveto;
+        }
+        return 0;
+    }
+    penum->pseg = pseg->next;
+    penum->notes = pseg->notes;
+    switch (pseg->type) {
+        case s_start:
+            ppts[0] = pseg->pt;
+            return gs_pe_moveto;
+        case s_line:
+            ppts[0] = pseg->pt;
+            return gs_pe_lineto;
+        case s_gap:
+            ppts[0] = pseg->pt;
+            return gs_pe_gapto;
+        case s_line_close:
+            ppts[0] = pseg->pt;
+            return gs_pe_closepath;
+        case s_curve:
+#define pcseg ((const curve_segment *)pseg)
+            ppts[0] = pcseg->p1;
+            ppts[1] = pcseg->p2;
+            ppts[2] = pseg->pt;
+            return gs_pe_curveto;
+#undef pcseg
+        default:
+            lprintf1("bad type %x in gx_path_enum_next!\n", pseg->type);
+            return_error(gs_error_Fatal);
+    }
+}
+
+/* Return the notes from the last-enumerated segment. */
+segment_notes
+gx_path_enum_notes(const gs_path_enum * penum)
+{
+    return penum->notes;
+}
+
+/* Back up 1 element in the path being enumerated. */
+/* Return true if successful, false if we are at the beginning of the path. */
+/* This implementation allows backing up multiple times, */
+/* but no client currently relies on this. */
+bool
+gx_path_enum_backup(gs_path_enum * penum)
+{
+    const segment *pseg = penum->pseg;
+
+    if (pseg != 0) {
+        if ((pseg = pseg->prev) == 0)
+            return false;
+        penum->pseg = pseg;
+        return true;
+    }
+    /* We're at the end of the path.  Check to see whether */
+    /* we need to back up over a trailing moveto. */
+    {
+        const gx_path *ppath = penum->path;
+
+        if (path_last_is_moveto(ppath) && penum->moveto_done) {		/* Back up over the trailing moveto. */
+            penum->moveto_done = false;
+            return true;
+        } {
+            const subpath *psub = ppath->current_subpath;
+
+            if (psub == 0)	/* empty path */
+                return false;
+            /* Back up to the last segment of the last subpath. */
+            penum->pseg = psub->last;
+            return true;
+        }
+    }
+}