← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/ghostscript/jaunty-updates

« back to all changes in this revision

Viewing changes to src/zalg.c

  • Committer: Bazaar Package Importer
  • Author(s): Till Kamppeter
  • Date: 2009-01-20 16:40:45 UTC
  • mfrom: (1.1.10 upstream)
  • Revision ID: james.westby@ubuntu.com-20090120164045-lnfhi0n30o5lwhwa
Tags: 8.64.dfsg.1~svn9377-0ubuntu1
https://launchpad.net/bugs/317810
https://launchpad.net/bugs/314439
https://launchpad.net/bugs/314018
* New upstream release (SVN rev 9377)
   o Fixes many bugs concerning PDF rendering, to make the PDF printing
     workflow correctly working.
   o Fixes long-standing bugs in many drivers, like input paper tray and
     duplex options not working for the built-in PCL 4, 5, 5c, 5e, and
     6/XL drivers, PDF input not working for bjc600, bjc800, and cups
     output devices, several options not working and uninitialized
     memory with cups output device.
   o Merged nearly all patches of the Ubuntu and Debian packages upstream.
   o Fixes LP: #317810, LP: #314439, LP: #314018.
* debian/patches/03_libpaper_support.dpatch,
  debian/patches/11_gs-cjk_font_glyph_handling_fix.dpatch,
  debian/patches/12_gs-cjk_vertical_writing_metrics_fix.dpatch,
  debian/patches/13_gs-cjk_cjkps_examples.dpatch,
  debian/patches/20_bbox_segv_fix.dpatch,
  debian/patches/21_brother_7x0_gdi_fix.dpatch,
  debian/patches/22_epsn_margin_workaround.dpatch,
  debian/patches/24_gs_man_fix.dpatch,
  debian/patches/25_toolbin_insecure_tmp_usage_fix.dpatch,
  debian/patches/26_assorted_script_fixes.dpatch,
  debian/patches/29_gs_css_fix.dpatch,
  debian/patches/30_ps2pdf_man_improvement.dpatch,
  debian/patches/31_fix-gc-sigbus.dpatch,
  debian/patches/34_ftbfs-on-hurd-fix.dpatch,
  debian/patches/35_disable_libcairo.dpatch,
  debian/patches/38_pxl-duplex.dpatch,
  debian/patches/39_pxl-resolution.dpatch,
  debian/patches/42_gs-init-ps-delaybind-fix.dpatch,
  debian/patches/45_bjc600-bjc800-pdf-input.dpatch,
  debian/patches/48_cups-output-device-pdf-duplex-uninitialized-memory-fix.dpatch,
  debian/patches/50_lips4-floating-point-exception.dpatch,
  debian/patches/52_cups-device-logging.dpatch,
  debian/patches/55_pcl-input-slot-fix.dpatch,
  debian/patches/57_pxl-input-slot-fix.dpatch,
  debian/patches/60_pxl-cups-driver-pdf.dpatch,
  debian/patches/62_onebitcmyk-pdf.dpatch,
  debian/patches/65_too-big-temp-files-1.dpatch,
  debian/patches/67_too-big-temp-files-2.dpatch,
  debian/patches/70_take-into-account-data-in-stream-buffer-before-refill.dpatch:
  Removed, applied upstream.
* debian/patches/01_docdir_fix_for_debian.dpatch,
  debian/patches/02_gs_man_fix_debian.dpatch,
  debian/patches/01_docdir-fix-for-debian.dpatch,
  debian/patches/02_docdir-fix-for-debian.dpatch: Renamed patches to
  make merging with Debian easier.
* debian/patches/32_improve-handling-of-media-size-changes-from-gv.dpatch, 
  debian/patches/33_bad-params-to-xinitimage-on-large-bitmaps.dpatch:
  regenerated for new source directory structure.
* debian/rules: Corrected paths to remove cidfmap (it is in Resource/Init/
  in GS 8.64) and to install headers (source paths are psi/ and base/ now).
* debian/rules: Remove all fontmaps, as DeFoMa replaces them.
* debian/local/pdftoraster/pdftoraster.c,
  debian/local/pdftoraster/pdftoraster.convs, debian/rules: Removed
  added pdftoraster filter and use the one which comes with Ghostscript.
* debian/ghostscript.links: s/8.63/8.64/

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/zalg.c
1
 
/* Copyright (C) 2006 Artifex Software, Inc.
2
 
   All Rights Reserved.
3
 
  
4
 
   This software is provided AS-IS with no warranty, either express or
5
 
   implied.
6
 
 
7
 
   This software is distributed under license and may not be copied, modified
8
 
   or distributed except as expressly authorized under the terms of that
9
 
   license.  Refer to licensing information at http://www.artifex.com/
10
 
   or contact Artifex Software, Inc.,  7 Mt. Lassen Drive - Suite A-134,
11
 
   San Rafael, CA  94903, U.S.A., +1(415)492-9861, for further information.
12
 
*/
13
 
 
14
 
/* $Id: zalg.c 8250 2007-09-25 13:31:24Z giles $ */
15
 
/* Operators for general-purpose algorithms. For now, only sorting. */
16
 
#include "ghost.h"
17
 
#include "gserrors.h"
18
 
#include "oper.h"
19
 
#include "store.h"
20
 
#include "estack.h"
21
 
 
22
 
/* ========================================================================= */
23
 
 
24
 
/*
25
 
 * The "heap sort" algorithm, as implementation of the .sort operator
26
 
 *
27
 
 * The implementation follows Algorithm H from Donald Knuth's
28
 
 * "The Art of Computer Programming", volume 3, section 5.2.3
29
 
 *
30
 
 * Notes:
31
 
 * i.   Execution time: O(n log n) in the average and worst cases.
32
 
 * ii.  The sort is not "stable" (the relative order of elements with
33
 
 *      equal keys is not necessarily preserved).
34
 
 * iii. Status variables:
35
 
 *      - stored on the e-stack;
36
 
 *      - "l", "r", "i", "j" and "R" correspond directly to variables in
37
 
 *        Algorithm H (including the fact that indices are 1-based);
38
 
 *      - variable "K" from Algorithm H is not used here, because we don't
39
 
 *        distinguish a "key part" of the array elements;
40
 
 *      - "H" indicates the step to execute; used when resuming after executing
41
 
 *        <lt> (to execute it, we have to return to the interpreter).
42
 
 *      - "array" and "lt" are refs to the parameters; avoids using them from the
43
 
 *        o-stack after resuming, in case the predicate has odd side-efects
44
 
 */
45
 
 
46
 
static int zsort(i_ctx_t *i_ctx_p);
47
 
static int zsort_continue(i_ctx_t *i_ctx_p);
48
 
static int zsort_cleanup(i_ctx_t *i_ctx_p);
49
 
 
50
 
/* <array> <lt> .sort <array> */
51
 
static int
52
 
zsort(i_ctx_t *i_ctx_p)
53
 
{
54
 
    os_ptr op = osp;
55
 
    uint N;
56
 
 
57
 
    /* Check operands for type and access */
58
 
    /* we can sort only writable [and unpacked] arrays */
59
 
    if (r_type(&op[-1]) == t_mixedarray || r_type(&op[-1]) == t_shortarray)
60
 
        return_error(e_invalidaccess);
61
 
    check_write_type(op[-1], t_array);
62
 
    /* the predicate must be an executable array/ string/ name/ [pseudo-]operator */
63
 
    if (!r_has_attr(&op[0], a_executable))
64
 
        return_op_typecheck(&op[0]);
65
 
    switch (r_btype(&op[0])) {
66
 
        case t_array:
67
 
        case t_mixedarray:
68
 
        case t_shortarray:
69
 
        case t_string:
70
 
            if (!r_has_attr(&op[0], a_execute))
71
 
                return_error(e_invalidaccess);
72
 
            break;
73
 
        case t_name:
74
 
        case t_operator:
75
 
        case t_oparray:
76
 
            break;
77
 
        default:
78
 
            return_op_typecheck(&op[0]);
79
 
    }
80
 
    /*
81
 
     * if array length <= 1, then nothing to sort
82
 
     * else prepare the status variables and launch the main sorting routine zsort_continue()
83
 
     */
84
 
    N = r_size(&op[-1]);
85
 
    if (N <= 1) {
86
 
        pop(1);
87
 
        return 0;
88
 
    } else {
89
 
        check_estack(11);
90
 
        push_mark_estack(es_other, zsort_cleanup);
91
 
/*H1:*/ make_int(&esp[1], N / 2 + 1);   /* l */
92
 
        make_int(&esp[2], N);           /* r */
93
 
        make_int(&esp[3], 0);           /* i */
94
 
        make_int(&esp[4], 0);           /* j */
95
 
        make_null(&esp[5]);             /* R */
96
 
        make_int(&esp[6], 2);           /* H */
97
 
        ref_assign(&esp[7], &op[0]);    /* lt */
98
 
        ref_assign(&esp[8], &op[-1]);   /* the array */
99
 
        esp += 8;
100
 
        make_op_estack(&esp[1], zsort_continue);
101
 
        make_null(&op[0]);              /* result of <lt>, not used when H = 2 */
102
 
        return zsort_continue(i_ctx_p);
103
 
    }
104
 
}
105
 
 
106
 
/* Continuation operator for .sort */
107
 
static int
108
 
zsort_continue(i_ctx_t *i_ctx_p)
109
 
{
110
 
    os_ptr op = osp;
111
 
    ref *status;
112
 
    ref *Rn;
113
 
#   define l    (status[1].value.intval)
114
 
#   define r    (status[2].value.intval)
115
 
#   define i    (status[3].value.intval)
116
 
#   define j    (status[4].value.intval)
117
 
#   define R    (status[5])
118
 
#   define H    (status[6].value.intval)
119
 
#   define lt   (status[7])
120
 
#   define arry (status[8])
121
 
 
122
 
    status = esp - 8;
123
 
    Rn = arry.value.refs - 1; /* the -1 compensates for using 1-based indices */
124
 
    switch (H) {
125
 
        case 2:
126
 
H2:         if (l > 1) {
127
 
                l--;
128
 
                ref_assign(&R, &Rn[l]);
129
 
            } else {
130
 
                ref_assign(&R, &Rn[r]);
131
 
                ref_assign_old(&arry, &Rn[r], &Rn[1], ".sort(H2-a)");
132
 
                r--;
133
 
                if (r <= 1) {
134
 
                    ref_assign_old(&arry, &Rn[1], &R, ".sort(H2-b)");
135
 
                    esp -= 9;
136
 
                    pop(1);
137
 
                    return o_pop_estack;
138
 
                }
139
 
            }
140
 
/* H3: */   j = l;
141
 
H4:         i = j;
142
 
            j <<= 1;
143
 
            if (j >= r)
144
 
                if (j == r)
145
 
                    goto H6;
146
 
                else
147
 
                    goto H8;
148
 
            else {
149
 
/* H5: */       H = 5;
150
 
                push(1);
151
 
                ref_assign(&op[-1], &Rn[j]);
152
 
                ref_assign(&op[0], &Rn[j + 1]);
153
 
                break;
154
 
            }
155
 
        case 5:
156
 
/*H5_cont:*/if (!r_has_type(&op[0], t_boolean))
157
 
                return_error(e_typecheck);
158
 
            if (op[0].value.boolval)
159
 
                j++;
160
 
H6:         H = 6;
161
 
            push(1);
162
 
            ref_assign(&op[-1], &R);
163
 
            ref_assign(&op[0], &Rn[j]);
164
 
            break;
165
 
        case 6:
166
 
/*H6_cont:*/if (!r_has_type(&op[0], t_boolean))
167
 
                return_error(e_typecheck);
168
 
            if (op[0].value.boolval) {
169
 
/* H7: */       ref_assign_old(&arry, &Rn[i], &Rn[j], ".sort(H7)");
170
 
                goto H4;
171
 
            } else {
172
 
H8:             ref_assign_old(&arry, &Rn[i], &R, ".sort(H8)");
173
 
                goto H2;
174
 
            }
175
 
        default:
176
 
            pop(1);
177
 
            return_error(gs_error_unregistered); /* Must not happen. */
178
 
    }
179
 
    esp += 2;
180
 
    ref_assign(esp, &lt);
181
 
    return o_push_estack;
182
 
#undef l
183
 
#undef r
184
 
#undef i
185
 
#undef j
186
 
#undef R
187
 
#undef H
188
 
#undef lt
189
 
}
190
 
 
191
 
/* No-op cleanup routine for .sort */
192
 
static int
193
 
zsort_cleanup(i_ctx_t *i_ctx_p)
194
 
{
195
 
    return 0;
196
 
}
197
 
 
198
 
/* ------ Initialization procedure ------ */
199
 
 
200
 
const op_def zalg_op_defs[] =
201
 
{
202
 
    {"2.sort", zsort},
203
 
                /* Internal operators */
204
 
    {"1%zsort_continue", zsort_continue},
205
 
    op_def_end(0)
206
 
};