[gs-cvs] rev 7868 - in trunk/gs: lib src
leonardo at ghostscript.com
leonardo at ghostscript.com
Sun Apr 22 10:55:57 PDT 2007
Author: leonardo
Date: 2007-04-22 10:55:56 -0700 (Sun, 22 Apr 2007)
New Revision: 7868
Added:
trunk/gs/src/zalg.c
Modified:
trunk/gs/lib/gs_init.ps
trunk/gs/src/int.mak
Log:
Implementing the PS operator .sort in C language.
DETAILS :
This is a partial fix for bug 688971
"huge performace problem (with large TT font?)".
Patch from SaGS.
The old PS implementation of lib\gs_init.ps::.sort uses a
slow O(n^2) algorithm. Plus, array indexing operations are lenghty
in PostScript. It seems to me this was initially written to sort
the very few "%disk*%" names, so speed was irrelevant. Now, it is
used to sort 'loca' tables (in some damaged TTFs).
The patch implements the heap sort algorithm from the programmer's
bible. This algorithm is guaranteed to be O(n log n) in the worst
case. Variable's names are those from Knuth's book. Labels denote the
algorithm's steps.
The implementation retains the maximum generality for the predicate,
i.e. it can be anything that is able to compare 2 objects on the
o-stack and leave a bool in their place. The predicate is not
restricted to what's available to a FunctionType 4 function.
EXPECTED DIFFERENCES :
None.
Modified: trunk/gs/lib/gs_init.ps
===================================================================
--- trunk/gs/lib/gs_init.ps 2007-04-22 11:50:25 UTC (rev 7867)
+++ trunk/gs/lib/gs_init.ps 2007-04-22 17:55:56 UTC (rev 7868)
@@ -330,21 +330,6 @@
/unread /.unread load def % use .peekstring instead
%**************** END OF BACKWARD COMPATIBILITY SECTION ****************
-% Utility procedure to sort an array
-% <array> <lt-proc> .sort <array>
-/.sort {
- 1 index length 1 sub -1 1 {
- 2 index exch 2 copy get 3 copy % arr proc arr i arr[i] arr i arr[i]
- 0 1 3 index 1 sub {
- 3 index 1 index get % arr proc arr i arr[i] arr imax amax j arr[j]
- 2 index 1 index 10 index exec { % ... amax < arr[j]
- 4 2 roll
- } if pop pop
- } for % arr proc arr i arr[i] arr imax amax
- 4 -1 roll exch 4 1 roll put put
- } for pop
-} bind def
-
% Utility for removing all entries from a dictionary
/.PurgeDict % <dict> .PurgeDict -
{ { true
Modified: trunk/gs/src/int.mak
===================================================================
--- trunk/gs/src/int.mak 2007-04-22 11:50:25 UTC (rev 7867)
+++ trunk/gs/src/int.mak 2007-04-22 17:55:56 UTC (rev 7868)
@@ -369,6 +369,10 @@
$(PSOBJ)zmath.$(OBJ) : $(PSSRC)zmath.c $(OP) $(math__h) $(gxfarith_h) $(store_h)
$(PSCC) $(PSO_)zmath.$(OBJ) $(C_) $(PSSRC)zmath.c
+$(PSOBJ)zalg.$(OBJ) : $(PSSRC)zalg.c $(OP) $(ghost_h) $(gserrors_h)\
+ $(oper_h) $(store_h) $(estack_h)
+ $(PSCC) $(PSO_)zalg.$(OBJ) $(C_) $(PSSRC)zalg.c
+
$(PSOBJ)zmisc.$(OBJ) : $(PSSRC)zmisc.c $(OP) $(gscdefs_h) $(gp_h)\
$(errno__h) $(memory__h) $(string__h)\
$(ialloc_h) $(idict_h) $(dstack_h) $(iname_h) $(ivmspace_h) $(ipacked_h) $(store_h)
@@ -509,7 +513,7 @@
Z1=$(PSOBJ)zarith.$(OBJ) $(PSOBJ)zarray.$(OBJ) $(PSOBJ)zcontrol.$(OBJ)
Z2=$(PSOBJ)zdict.$(OBJ) $(PSOBJ)zfile.$(OBJ) $(PSOBJ)zfile1.$(OBJ) $(PSOBJ)zfileio.$(OBJ)
Z3=$(PSOBJ)zfilter.$(OBJ) $(PSOBJ)zfproc.$(OBJ) $(PSOBJ)zgeneric.$(OBJ)
-Z4=$(PSOBJ)ziodev.$(OBJ) $(PSOBJ)ziodevs$(STDIO_IMPLEMENTATION).$(OBJ) $(PSOBJ)zmath.$(OBJ)
+Z4=$(PSOBJ)ziodev.$(OBJ) $(PSOBJ)ziodevs$(STDIO_IMPLEMENTATION).$(OBJ) $(PSOBJ)zmath.$(OBJ) $(PSOBJ)zalg.$(OBJ)
Z5=$(PSOBJ)zmisc.$(OBJ) $(PSOBJ)zpacked.$(OBJ) $(PSOBJ)zrelbit.$(OBJ)
Z6=$(PSOBJ)zstack.$(OBJ) $(PSOBJ)zstring.$(OBJ) $(PSOBJ)zsysvm.$(OBJ)
Z7=$(PSOBJ)ztoken.$(OBJ) $(PSOBJ)ztype.$(OBJ) $(PSOBJ)zvmem.$(OBJ)
@@ -520,7 +524,7 @@
Z12=$(PSOBJ)zncdummy.$(OBJ)
Z1OPS=zarith zarray zcontrol1 zcontrol2 zcontrol3
Z2OPS=zdict1 zdict2 zfile zfile1 zfileio1 zfileio2
-Z3_4OPS=zfilter zfproc zgeneric ziodev zmath
+Z3_4OPS=zfilter zfproc zgeneric ziodev zmath zalg
Z5_6OPS=zmisc zpacked zrelbit zstack zstring zsysvm
Z7_8OPS=ztoken ztype zvmem zbfont zchar zcolor
Z9OPS=zdevice zfont zfontenum zgstate1 zgstate2 zgstate3
Added: trunk/gs/src/zalg.c
===================================================================
--- trunk/gs/src/zalg.c 2007-04-22 11:50:25 UTC (rev 7867)
+++ trunk/gs/src/zalg.c 2007-04-22 17:55:56 UTC (rev 7868)
@@ -0,0 +1,208 @@
+/* Copyright (C) 2006 artofcode LLC.
+ 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$ */
+/* Operators for general-purpose algorithms. For now, only sorting. */
+#include "ghost.h"
+#include "gserrors.h"
+#include "oper.h"
+#include "store.h"
+#include "estack.h"
+
+/* ========================================================================= */
+
+/*
+ * The "heap sort" algorithm, as implementation of the .sort operator
+ *
+ * The implementation follows Algorithm H from Donald Knuth's
+ * "The Art of Computer Programming", volume 3, section 5.2.3
+ *
+ * Notes:
+ * i. Execution time: O(n log n) in the average and worst cases.
+ * ii. The sort is not "stable" (the relative order of elements with
+ * equal keys is not necessarily preserved).
+ * iii. Status variables:
+ * - stored on the e-stack;
+ * - "l", "r", "i", "j" and "R" correspond directly to variables in
+ * Algorithm H (including the fact that indices are 1-based);
+ * - variable "K" from Algorithm H is not used here, because we don't
+ * distinguish a "key part" of the array elements;
+ * - "H" indicates the step to execute; used when resuming after executing
+ * <lt> (to execute it, we have to return to the interpreter).
+ * - "array" and "lt" are refs to the parameters; avoids using them from the
+ * o-stack after resuming, in case the predicate has odd side-efects
+ */
+
+private int zsort(i_ctx_t *i_ctx_p);
+private int zsort_continue(i_ctx_t *i_ctx_p);
+private int zsort_cleanup(i_ctx_t *i_ctx_p);
+
+/* <array> <lt> .sort <array> */
+private int
+zsort(i_ctx_t *i_ctx_p)
+{
+ int code;
+ os_ptr op = osp;
+ uint N;
+ ref status;
+
+ /* Check operands for type and access */
+ /* we can sort only writable [and unpacked] arrays */
+ if (r_type(&op[-1]) == t_mixedarray || r_type(&op[-1]) == t_shortarray)
+ return_error(e_invalidaccess);
+ check_write_type(op[-1], t_array);
+ /* the predicate must be an executable array/ string/ name/ [pseudo-]operator */
+ if (!r_has_attr(&op[0], a_executable))
+ return_op_typecheck(&op[0]);
+ switch (r_btype(&op[0])) {
+ case t_array:
+ case t_mixedarray:
+ case t_shortarray:
+ case t_string:
+ if (!r_has_attr(&op[0], a_execute))
+ return_error(e_invalidaccess);
+ break;
+ case t_name:
+ case t_operator:
+ case t_oparray:
+ break;
+ default:
+ return_op_typecheck(&op[0]);
+ }
+ /*
+ * if array length <= 1, then nothing to sort
+ * else prepare the status variables and launch the main sorting routine zsort_continue()
+ */
+ N = r_size(&op[-1]);
+ if (N <= 1) {
+ pop(1);
+ return 0;
+ } else {
+ check_estack(11);
+ push_mark_estack(es_other, zsort_cleanup);
+H1: make_int(&esp[1], N / 2 + 1); /* l */
+ make_int(&esp[2], N); /* r */
+ make_int(&esp[3], 0); /* i */
+ make_int(&esp[4], 0); /* j */
+ make_null(&esp[5]); /* R */
+ make_int(&esp[6], 2); /* H */
+ ref_assign(&esp[7], &op[0]); /* lt */
+ ref_assign(&esp[8], &op[-1]); /* the array */
+ esp += 8;
+ make_op_estack(&esp[1], zsort_continue);
+ make_null(&op[0]); /* result of <lt>, not used when H = 2 */
+ return zsort_continue(i_ctx_p);
+ }
+}
+
+/* Continuation operator for .sort */
+private int
+zsort_continue(i_ctx_t *i_ctx_p)
+{
+ os_ptr op = osp;
+ ref *status;
+ ref *Rn;
+# define l (status[1].value.intval)
+# define r (status[2].value.intval)
+# define i (status[3].value.intval)
+# define j (status[4].value.intval)
+# define R (status[5])
+# define H (status[6].value.intval)
+# define lt (status[7])
+# define arry (status[8])
+
+ status = esp - 8;
+ Rn = arry.value.refs - 1; /* the -1 compensates for using 1-based indices */
+ switch (H) {
+ case 2:
+H2: if (l > 1) {
+ l--;
+ ref_assign(&R, &Rn[l]);
+ } else {
+ ref_assign(&R, &Rn[r]);
+ ref_assign_old(&arry, &Rn[r], &Rn[1], ".sort(H2-a)");
+ r--;
+ if (r <= 1) {
+ ref_assign_old(&arry, &Rn[1], &R, ".sort(H2-b)");
+ esp -= 9;
+ pop(1);
+ return o_pop_estack;
+ }
+ }
+H3: j = l;
+H4: i = j;
+ j <<= 1;
+ if (j >= r)
+ if (j == r)
+ goto H6;
+ else
+ goto H8;
+ else {
+H5: H = 5;
+ push(1);
+ ref_assign(&op[-1], &Rn[j]);
+ ref_assign(&op[0], &Rn[j + 1]);
+ break;
+ }
+ case 5:
+H5_cont: if (!r_has_type(&op[0], t_boolean))
+ return_error(e_typecheck);
+ if (op[0].value.boolval)
+ j++;
+H6: H = 6;
+ push(1);
+ ref_assign(&op[-1], &R);
+ ref_assign(&op[0], &Rn[j]);
+ break;
+ case 6:
+H6_cont: if (!r_has_type(&op[0], t_boolean))
+ return_error(e_typecheck);
+ if (op[0].value.boolval) {
+H7: ref_assign_old(&arry, &Rn[i], &Rn[j], ".sort(H7)");
+ goto H4;
+ } else {
+H8: ref_assign_old(&arry, &Rn[i], &R, ".sort(H8)");
+ goto H2;
+ }
+ default:
+ pop(1);
+ return_error(gs_error_unregistered); /* Must not happen. */
+ }
+ esp += 2;
+ ref_assign(esp, <);
+ return o_push_estack;
+#undef l
+#undef r
+#undef i
+#undef j
+#undef R
+#undef H
+#undef lt
+}
+
+/* No-op cleanup routine for .sort */
+private int
+zsort_cleanup(i_ctx_t *i_ctx_p)
+{
+ return 0;
+}
+
+/* ------ Initialization procedure ------ */
+
+const op_def zalg_op_defs[] =
+{
+ {"2.sort", zsort},
+ /* Internal operators */
+ {"1%zsort_continue", zsort_continue},
+ op_def_end(0)
+};
Property changes on: trunk/gs/src/zalg.c
___________________________________________________________________
Name: svn:keywords
+ Id
Name: svn:eol-style
+ native
More information about the gs-cvs
mailing list