1 /* Copyright (C) 2001-2012 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,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, San Rafael,
13 CA 94903, U.S.A., +1(415)492-9861, for further information.
14 */
15
16
17 /* Miscellaneous utilities for Ghostscript library */
18
19 /*
20 * In order to capture the original definition of sqrt, which might be
21 * either a procedure or a macro and might not have an ANSI-compliant
22 * prototype (!), we need to do the following:
23 */
24 #include "std.h"
25 #if defined(VMS) && defined(__GNUC__)
26 /* DEC VAX/VMS C comes with a math.h file, but GNU VAX/VMS C does not. */
27 # include "vmsmath.h"
28 #else
29 # include <math.h>
30 #endif
31 static inline double
orig_sqrt(double x)32 orig_sqrt(double x)
33 {
34 return sqrt(x);
35 }
36
37 /* Here is the real #include section. */
38 #include "ctype_.h"
39 #include "malloc_.h"
40 #include "math_.h"
41 #include "memory_.h"
42 #include "string_.h"
43 #include "gx.h"
44 #include "gpcheck.h" /* for gs_return_check_interrupt */
45 #include "gserrors.h"
46 #include "gxfarith.h"
47 #include "gxfixed.h"
48 #include "stdint_.h"
49 #include "stdio_.h"
50
51 /* ------ Redirected stdout and stderr ------ */
52
53 #include <stdarg.h>
54 #define PRINTF_BUF_LENGTH 1024
55
56 static const char msg_truncated[] = "\n*** Previous line has been truncated.\n";
57
outprintf(const gs_memory_t * mem,const char * fmt,...)58 int outprintf(const gs_memory_t *mem, const char *fmt, ...)
59 {
60 int count;
61 char buf[PRINTF_BUF_LENGTH];
62 va_list args;
63
64 va_start(args, fmt);
65 count = vsnprintf(buf, sizeof(buf), fmt, args);
66 if (count >= sizeof(buf) || count < 0) { /* C99 || MSVC */
67 outwrite(mem, buf, sizeof(buf) - 1);
68 outwrite(mem, msg_truncated, sizeof(msg_truncated) - 1);
69 } else {
70 outwrite(mem, buf, count);
71 }
72 va_end(args);
73 return count;
74 }
75
errprintf_nomem(const char * fmt,...)76 int errprintf_nomem(const char *fmt, ...)
77 {
78 int count;
79 char buf[PRINTF_BUF_LENGTH];
80 va_list args;
81
82 va_start(args, fmt);
83 count = vsnprintf(buf, sizeof(buf), fmt, args);
84 if (count >= sizeof(buf) || count < 0) { /* C99 || MSVC */
85 errwrite_nomem(buf, sizeof(buf) - 1);
86 errwrite_nomem(msg_truncated, sizeof(msg_truncated) - 1);
87 } else {
88 errwrite_nomem(buf, count);
89 }
90 va_end(args);
91 return count;
92 }
93
errprintf(const gs_memory_t * mem,const char * fmt,...)94 int errprintf(const gs_memory_t *mem, const char *fmt, ...)
95 {
96 int count;
97 char buf[PRINTF_BUF_LENGTH];
98 va_list args;
99
100 va_start(args, fmt);
101 count = vsnprintf(buf, sizeof(buf), fmt, args);
102 if (count >= sizeof(buf) || count < 0) { /* C99 || MSVC */
103 errwrite(mem, buf, sizeof(buf) - 1);
104 errwrite(mem, msg_truncated, sizeof(msg_truncated) - 1);
105 } else {
106 errwrite(mem, buf, count);
107 }
108 va_end(args);
109 return count;
110 }
111
112 /* ------ Debugging ------ */
113
114 /* We define gs_debug even if DEBUG isn't defined, */
115 /* so that we can compile individual modules with DEBUG set. */
116 /* gs_debug is therefore shared between all instances in a multi-instance
117 * setup. This means that {en,dis}abling a debugging flag in one instance
118 * will affect all other instances. */
119 char gs_debug[128];
120
121 /* Test whether a given debugging option is selected. */
122 /* Some letters automatically imply others. */
123 bool
gs_debug_c(int c)124 gs_debug_c(int c)
125 {
126 bool ret = gs_debug[c];
127
128 /* Unroll the first one, to minimise the speed hit */
129 c = gs_debug_flag_implied_by[c];
130 if (c == 0)
131 return ret;
132
133 do {
134 ret |= gs_debug[c];
135 } while (c = gs_debug_flag_implied_by[c]);
136 return ret;
137 }
138
139 /* Define the formats for debugging printout. */
140 const char *const dprintf_file_and_line_format = "%10s(%4d): ";
141 const char *const dprintf_file_only_format = "%10s(unkn): ";
142
143 /*
144 * Define the trace printout procedures. We always include these, in case
145 * other modules were compiled with DEBUG set. Note that they must use
146 * out/errprintf, not fprintf nor fput[cs], because of the way that
147 * stdout/stderr are implemented on DLL/shared library builds.
148 */
149 void
dflush(void)150 dflush(void)
151 {
152 errflush_nomem();
153 }
154 static const char *
dprintf_file_tail(const char * file)155 dprintf_file_tail(const char *file)
156 {
157 const char *tail = file + strlen(file);
158
159 while (tail > file &&
160 (isalnum((unsigned char)tail[-1]) || tail[-1] == '.' || tail[-1] == '_')
161 )
162 --tail;
163 return tail;
164 }
165 #if __LINE__ /* compiler provides it */
166 void
dprintf_file_and_line(const char * file,int line)167 dprintf_file_and_line(const char *file, int line)
168 {
169 if (gs_debug['/'])
170 dpf(dprintf_file_and_line_format,
171 dprintf_file_tail(file), line);
172 }
173 #else
174 void
dprintf_file_only(const char * file)175 dprintf_file_only(const char *file)
176 {
177 if (gs_debug['/'])
178 dpf(dprintf_file_only_format, dprintf_file_tail(file));
179 }
180 #endif
181 void
printf_program_ident(const gs_memory_t * mem,const char * program_name,long revision_number)182 printf_program_ident(const gs_memory_t *mem, const char *program_name, long revision_number)
183 {
184 if (program_name)
185 outprintf(mem, (revision_number ? "%s " : "%s"), program_name);
186 if (revision_number) {
187 int fpart = revision_number % 100;
188
189 outprintf(mem, "%d.%02d", (int)(revision_number / 100), fpart);
190 }
191 }
192 void
eprintf_program_ident(const char * program_name,long revision_number)193 eprintf_program_ident(const char *program_name,
194 long revision_number)
195 {
196 if (program_name) {
197 epf((revision_number ? "%s " : "%s"), program_name);
198 if (revision_number) {
199 int fpart = revision_number % 100;
200
201 epf("%d.%02d", (int)(revision_number / 100), fpart);
202 }
203 epf(": ");
204 }
205 }
206 void
emprintf_program_ident(const gs_memory_t * mem,const char * program_name,long revision_number)207 emprintf_program_ident(const gs_memory_t *mem,
208 const char *program_name,
209 long revision_number)
210 {
211 if (program_name) {
212 epfm(mem, (revision_number ? "%s " : "%s"), program_name);
213 if (revision_number) {
214 int fpart = revision_number % 100;
215
216 epfm(mem, "%d.%02d", (int)(revision_number / 100), fpart);
217 }
218 epfm(mem, ": ");
219 }
220 }
221 #if __LINE__ /* compiler provides it */
222 void
lprintf_file_and_line(const char * file,int line)223 lprintf_file_and_line(const char *file, int line)
224 {
225 epf("%s(%d): ", file, line);
226 }
227 #else
228 void
lprintf_file_only(FILE * f,const char * file)229 lprintf_file_only(FILE * f, const char *file)
230 {
231 epf("%s(?): ", file);
232 }
233 #endif
234
235 /* Log an error return. We always include this, in case other */
236 /* modules were compiled with DEBUG set. */
237 #undef gs_log_error /* in case DEBUG isn't set */
238 int
gs_log_error(int err,const char * file,int line)239 gs_log_error(int err, const char *file, int line)
240 {
241 if (gs_log_errors) {
242 if (file == NULL)
243 dprintf1("Returning error %d.\n", err);
244 else
245 dprintf3("%s(%d): Returning error %d.\n",
246 (const char *)file, line, err);
247 }
248 return err;
249 }
250
251 /* Check for interrupts before a return. */
252 int
gs_return_check_interrupt(const gs_memory_t * mem,int code)253 gs_return_check_interrupt(const gs_memory_t *mem, int code)
254 {
255 if (code < 0)
256 return code;
257 {
258 int icode = gp_check_interrupts(mem);
259
260 return (icode == 0 ? code :
261 gs_note_error((icode > 0 ? gs_error_interrupt : icode)));
262 }
263 }
264
gs_throw_imp(const char * func,const char * file,int line,int op,int code,const char * fmt,...)265 int gs_throw_imp(const char *func, const char *file, int line, int op, int code, const char *fmt, ...)
266 {
267 char msg[1024];
268 va_list ap;
269
270 va_start(ap, fmt);
271 vsnprintf(msg, sizeof(msg), fmt, ap);
272 msg[sizeof(msg) - 1] = 0;
273 va_end(ap);
274
275 if (!gs_debug_c('#')) {
276 ; /* NB: gs_log_errors
277 * we could disable these printfs, and probably will when,
278 * the code becomes more stable:
279 * return code;
280 */
281 }
282
283 /* throw */
284 if (op == 0)
285 errprintf_nomem("+ %s:%d: %s(): %s\n", file, line, func, msg);
286
287 /* rethrow */
288 if (op == 1)
289 errprintf_nomem("| %s:%d: %s(): %s\n", file, line, func, msg);
290
291 /* catch */
292 if (op == 2)
293 errprintf_nomem("- %s:%d: %s(): %s\n", file, line, func, msg);
294
295 /* warn */
296 if (op == 3)
297 errprintf_nomem(" %s:%d: %s(): %s\n", file, line, func, msg);
298
299 return code;
300 }
301
gs_errstr(int code)302 const char *gs_errstr(int code)
303 {
304 switch (code) {
305 default:
306 case gs_error_unknownerror: return "unknownerror";
307 case gs_error_interrupt: return "interrupt";
308 case gs_error_invalidaccess: return "invalidaccess";
309 case gs_error_invalidfileaccess: return "invalidfileaccess";
310 case gs_error_invalidfont: return "invalidfont";
311 case gs_error_ioerror: return "ioerror";
312 case gs_error_limitcheck: return "limitcheck";
313 case gs_error_nocurrentpoint: return "nocurrentpoint";
314 case gs_error_rangecheck: return "rangecheck";
315 case gs_error_typecheck: return "typecheck";
316 case gs_error_undefined: return "undefined";
317 case gs_error_undefinedfilename: return "undefinedfilename";
318 case gs_error_undefinedresult: return "undefinedresult";
319 case gs_error_VMerror: return "vmerror";
320 case gs_error_unregistered: return "unregistered";
321 case gs_error_hit_detected: return "hit_detected";
322 case gs_error_Fatal: return "Fatal";
323 }
324 }
325
326 /* ------ Substitutes for missing C library functions ------ */
327
328 #ifdef MEMORY__NEED_MEMMOVE /* see memory_.h */
329 /* Copy bytes like memcpy, guaranteed to handle overlap correctly. */
330 /* ANSI C defines the returned value as being the src argument, */
331 /* but with the const restriction removed! */
332 void *
gs_memmove(void * dest,const void * src,size_t len)333 gs_memmove(void *dest, const void *src, size_t len)
334 {
335 if (!len)
336 return (void *)src;
337 #define bdest ((byte *)dest)
338 #define bsrc ((const byte *)src)
339 /* We use len-1 for comparisons because adding len */
340 /* might produce an offset overflow on segmented systems. */
341 if (PTR_LE(bdest, bsrc)) {
342 register byte *end = bdest + (len - 1);
343
344 if (PTR_LE(bsrc, end)) {
345 /* Source overlaps destination from above. */
346 register const byte *from = bsrc;
347 register byte *to = bdest;
348
349 for (;;) {
350 *to = *from;
351 if (to >= end) /* faster than = */
352 return (void *)src;
353 to++;
354 from++;
355 }
356 }
357 } else {
358 register const byte *from = bsrc + (len - 1);
359
360 if (PTR_LE(bdest, from)) {
361 /* Source overlaps destination from below. */
362 register const byte *end = bsrc;
363 register byte *to = bdest + (len - 1);
364
365 for (;;) {
366 *to = *from;
367 if (from <= end) /* faster than = */
368 return (void *)src;
369 to--;
370 from--;
371 }
372 }
373 }
374 #undef bdest
375 #undef bsrc
376 /* No overlap, it's safe to use memcpy. */
377 memcpy(dest, src, len);
378 return (void *)src;
379 }
380 #endif
381
382 #ifdef MEMORY__NEED_MEMCPY /* see memory_.h */
383 void *
gs_memcpy(void * dest,const void * src,size_t len)384 gs_memcpy(void *dest, const void *src, size_t len)
385 {
386 if (len > 0) {
387 #define bdest ((byte *)dest)
388 #define bsrc ((const byte *)src)
389 /* We can optimize this much better later on. */
390 register byte *end = bdest + (len - 1);
391 register const byte *from = bsrc;
392 register byte *to = bdest;
393
394 for (;;) {
395 *to = *from;
396 if (to >= end) /* faster than = */
397 break;
398 to++;
399 from++;
400 }
401 }
402 #undef bdest
403 #undef bsrc
404 return (void *)src;
405 }
406 #endif
407
408 #ifdef MEMORY__NEED_MEMCHR /* see memory_.h */
409 /* ch should obviously be char rather than int, */
410 /* but the ANSI standard declaration uses int. */
411 void *
gs_memchr(const void * ptr,int ch,size_t len)412 gs_memchr(const void *ptr, int ch, size_t len)
413 {
414 if (len > 0) {
415 register const char *p = ptr;
416 register uint count = len;
417
418 do {
419 if (*p == (char)ch)
420 return (void *)p;
421 p++;
422 } while (--count);
423 }
424 return 0;
425 }
426 #endif
427
428 #ifdef MEMORY__NEED_MEMSET /* see memory_.h */
429 /* ch should obviously be char rather than int, */
430 /* but the ANSI standard declaration uses int. */
431 void *
gs_memset(void * dest,register int ch,size_t len)432 gs_memset(void *dest, register int ch, size_t len)
433 {
434 /*
435 * This procedure is used a lot to fill large regions of images,
436 * so we take some trouble to optimize it.
437 */
438 register char *p = dest;
439 register size_t count = len;
440
441 ch &= 255;
442 if (len >= sizeof(long) * 3) {
443 long wd = (ch << 24) | (ch << 16) | (ch << 8) | ch;
444
445 while (ALIGNMENT_MOD(p, sizeof(long)))
446 *p++ = (char)ch, --count;
447 for (; count >= sizeof(long) * 4;
448 p += sizeof(long) * 4, count -= sizeof(long) * 4
449 )
450 ((long *)p)[3] = ((long *)p)[2] = ((long *)p)[1] =
451 ((long *)p)[0] = wd;
452 switch (count >> ARCH_LOG2_SIZEOF_LONG) {
453 case 3:
454 *((long *)p) = wd; p += sizeof(long);
455 case 2:
456 *((long *)p) = wd; p += sizeof(long);
457 case 1:
458 *((long *)p) = wd; p += sizeof(long);
459 count &= sizeof(long) - 1;
460 case 0:
461 default: /* can't happen */
462 DO_NOTHING;
463 }
464 }
465 /* Do any leftover bytes. */
466 for (; count > 0; --count)
467 *p++ = (char)ch;
468 return dest;
469 }
470 #endif
471
472 #ifdef malloc__need_realloc /* see malloc_.h */
473 /* Some systems have non-working implementations of realloc. */
474 void *
gs_realloc(void * old_ptr,size_t old_size,size_t new_size)475 gs_realloc(void *old_ptr, size_t old_size, size_t new_size)
476 {
477 void *new_ptr;
478
479 if (new_size) {
480 new_ptr = malloc(new_size);
481 if (new_ptr == NULL)
482 return NULL;
483 } else
484 new_ptr = NULL;
485 /* We have to pass in the old size, since we have no way to */
486 /* determine it otherwise. */
487 if (old_ptr != NULL) {
488 if (new_ptr != NULL)
489 memcpy(new_ptr, old_ptr, min(old_size, new_size));
490 free(old_ptr);
491 }
492 return new_ptr;
493 }
494 #endif
495
496 /* ------ Debugging support ------ */
497
498 /* Dump a region of memory. */
499 void
debug_dump_bytes(const byte * from,const byte * to,const char * msg)500 debug_dump_bytes(const byte * from, const byte * to, const char *msg)
501 {
502 const byte *p = from;
503
504 if (from < to && msg)
505 dprintf1("%s:\n", msg);
506 while (p != to) {
507 const byte *q = min(p + 16, to);
508
509 dprintf1("0x%lx:", (ulong) p);
510 while (p != q)
511 dprintf1(" %02x", *p++);
512 dputc('\n');
513 }
514 }
515
516 /* Dump a bitmap. */
517 void
debug_dump_bitmap(const byte * bits,uint raster,uint height,const char * msg)518 debug_dump_bitmap(const byte * bits, uint raster, uint height, const char *msg)
519 {
520 uint y;
521 const byte *data = bits;
522
523 for (y = 0; y < height; ++y, data += raster)
524 debug_dump_bytes(data, data + raster, (y == 0 ? msg : NULL));
525 }
526
527 /* Print a string. */
528 void
debug_print_string(const byte * chrs,uint len)529 debug_print_string(const byte * chrs, uint len)
530 {
531 uint i;
532
533 for (i = 0; i < len; i++)
534 dputc(chrs[i]);
535 dflush();
536 }
537
538 /* Print a string in hexdump format. */
539 void
debug_print_string_hex(const byte * chrs,uint len)540 debug_print_string_hex(const byte * chrs, uint len)
541 {
542 uint i;
543
544 for (i = 0; i < len; i++)
545 dprintf1("%02x", chrs[i]);
546 dflush();
547 }
548
549 /*
550 * The following code prints a hex stack backtrace on Linux/Intel systems.
551 * It is here to be patched into places where we need to print such a trace
552 * because of gdb's inability to put breakpoints in dynamically created
553 * threads.
554 *
555 * first_arg is the first argument of the procedure into which this code
556 * is patched.
557 */
558 #define BACKTRACE(first_arg)\
559 BEGIN\
560 ulong *fp_ = (ulong *)&first_arg - 2;\
561 for (; fp_ && (fp_[1] & 0xff000000) == 0x08000000; fp_ = (ulong *)*fp_)\
562 dprintf2(" fp=0x%lx ip=0x%lx\n", (ulong)fp_, fp_[1]);\
563 END
564
565 /* ------ Arithmetic ------ */
566
567 /* Compute M modulo N. Requires N > 0; guarantees 0 <= imod(M,N) < N, */
568 /* regardless of the whims of the % operator for negative operands. */
569 int
imod(int m,int n)570 imod(int m, int n)
571 {
572 if (n <= 0)
573 return 0; /* sanity check */
574 if (m >= 0)
575 return m % n;
576 {
577 int r = -m % n;
578
579 return (r == 0 ? 0 : n - r);
580 }
581 }
582
583 /* Compute the GCD of two integers. */
584 int
igcd(int x,int y)585 igcd(int x, int y)
586 {
587 int c = x, d = y;
588
589 if (c < 0)
590 c = -c;
591 if (d < 0)
592 d = -d;
593 while (c != 0 && d != 0)
594 if (c > d)
595 c %= d;
596 else
597 d %= c;
598 return d + c; /* at most one is non-zero */
599 }
600
601 /* Compute X such that A*X = B mod M. See gxarith.h for details. */
602 int
idivmod(int a,int b,int m)603 idivmod(int a, int b, int m)
604 {
605 /*
606 * Use the approach indicated in Knuth vol. 2, section 4.5.2, Algorithm
607 * X (p. 302) and exercise 15 (p. 315, solution p. 523).
608 */
609 int u1 = 0, u3 = m;
610 int v1 = 1, v3 = a;
611 /*
612 * The following loop will terminate with a * u1 = gcd(a, m) mod m.
613 * Then x = u1 * b / gcd(a, m) mod m. Since we require that
614 * gcd(a, m) | gcd(a, b), it follows that gcd(a, m) | b, so the
615 * division is exact.
616 */
617 while (v3) {
618 int q = u3 / v3, t;
619
620 t = u1 - v1 * q, u1 = v1, v1 = t;
621 t = u3 - v3 * q, u3 = v3, v3 = t;
622 }
623 return imod(u1 * b / igcd(a, m), m);
624 }
625
626 /* Compute floor(log2(N)). Requires N > 0. */
627 int
ilog2(int n)628 ilog2(int n)
629 {
630 int m = n, l = 0;
631
632 while (m >= 16)
633 m >>= 4, l += 4;
634 return
635 (m <= 1 ? l :
636 "\000\000\001\001\002\002\002\002\003\003\003\003\003\003\003\003"[m] + l);
637 }
638
639 /*
640 * Compute A * B / C when 0 <= B < C and A * B exceeds (or might exceed)
641 * the capacity of a long.
642 * Note that this procedure takes the floor, rather than truncating
643 * towards zero, if A < 0. This ensures that 0 <= R < C.
644 */
645
646 #define num_bits (sizeof(fixed) * 8)
647 #define half_bits (num_bits / 2)
648 #define half_mask ((1L << half_bits) - 1)
649
650 /*
651 * If doubles aren't wide enough, we lose too much precision by using double
652 * arithmetic: we have to use the slower, accurate fixed-point algorithm.
653 * See the simpler implementation below for more information.
654 */
655 #define MAX_OTHER_FACTOR_BITS\
656 (ARCH_DOUBLE_MANTISSA_BITS - ARCH_SIZEOF_FIXED * 8)
657 #define ROUND_BITS\
658 (ARCH_SIZEOF_FIXED * 8 * 2 - ARCH_DOUBLE_MANTISSA_BITS)
659
660 #if ROUND_BITS >= MAX_OTHER_FACTOR_BITS - 1
661
662 #ifdef DEBUG
663 struct {
664 long mnanb, mnab, manb, mab, mnc, mdq, mde, mds, mqh, mql;
665 } fmq_stat;
666 # define mincr(x) ++fmq_stat.x
667 #else
668 # define mincr(x) DO_NOTHING
669 #endif
670 fixed
fixed_mult_quo(fixed signed_A,fixed B,fixed C)671 fixed_mult_quo(fixed signed_A, fixed B, fixed C)
672 {
673 /* First compute A * B in double-fixed precision. */
674 ulong A = (signed_A < 0 ? -signed_A : signed_A);
675 long msw;
676 ulong lsw;
677 ulong p1;
678
679 if (B <= half_mask) {
680 if (A <= half_mask) {
681 ulong P = A * B;
682 fixed Q = P / (ulong)C;
683
684 mincr(mnanb);
685 /* If A < 0 and the division isn't exact, take the floor. */
686 return (signed_A >= 0 ? Q : Q * C == P ? -Q : ~Q /* -Q - 1 */);
687 }
688 /*
689 * We might still have C <= half_mask, which we can
690 * handle with a simpler algorithm.
691 */
692 lsw = (A & half_mask) * B;
693 p1 = (A >> half_bits) * B;
694 if (C <= half_mask) {
695 fixed q0 = (p1 += lsw >> half_bits) / C;
696 ulong rem = ((p1 - C * q0) << half_bits) + (lsw & half_mask);
697 ulong q1 = rem / (ulong)C;
698 fixed Q = (q0 << half_bits) + q1;
699
700 mincr(mnc);
701 /* If A < 0 and the division isn't exact, take the floor. */
702 return (signed_A >= 0 ? Q : q1 * C == rem ? -Q : ~Q);
703 }
704 msw = p1 >> half_bits;
705 mincr(manb);
706 } else if (A <= half_mask) {
707 p1 = A * (B >> half_bits);
708 msw = p1 >> half_bits;
709 lsw = A * (B & half_mask);
710 mincr(mnab);
711 } else { /* We have to compute all 4 products. :-( */
712 ulong lo_A = A & half_mask;
713 ulong hi_A = A >> half_bits;
714 ulong lo_B = B & half_mask;
715 ulong hi_B = B >> half_bits;
716 ulong p1x = hi_A * lo_B;
717
718 msw = hi_A * hi_B;
719 lsw = lo_A * lo_B;
720 p1 = lo_A * hi_B;
721 if (p1 > max_ulong - p1x)
722 msw += 1L << half_bits;
723 p1 += p1x;
724 msw += p1 >> half_bits;
725 mincr(mab);
726 }
727 /* Finish up by adding the low half of p1 to the high half of lsw. */
728 #if max_fixed < max_long
729 p1 &= half_mask;
730 #endif
731 p1 <<= half_bits;
732 if (p1 > max_ulong - lsw)
733 msw++;
734 lsw += p1;
735 /*
736 * Now divide the double-length product by C. Note that we know msw
737 * < C (otherwise the quotient would overflow). Start by shifting
738 * (msw,lsw) and C left until C >= 1 << (num_bits - 1).
739 */
740 {
741 ulong denom = C;
742 int shift = 0;
743
744 #define bits_4th (num_bits / 4)
745 if (denom < 1L << (num_bits - bits_4th)) {
746 mincr(mdq);
747 denom <<= bits_4th, shift += bits_4th;
748 }
749 #undef bits_4th
750 #define bits_8th (num_bits / 8)
751 if (denom < 1L << (num_bits - bits_8th)) {
752 mincr(mde);
753 denom <<= bits_8th, shift += bits_8th;
754 }
755 #undef bits_8th
756 while (!(denom & (-1L << (num_bits - 1)))) {
757 mincr(mds);
758 denom <<= 1, ++shift;
759 }
760 msw = (msw << shift) + (lsw >> (num_bits - shift));
761 lsw <<= shift;
762 #if max_fixed < max_long
763 lsw &= (1L << (sizeof(fixed) * 8)) - 1;
764 #endif
765 /* Compute a trial upper-half quotient. */
766 {
767 ulong hi_D = denom >> half_bits;
768 ulong lo_D = denom & half_mask;
769 ulong hi_Q = (ulong) msw / hi_D;
770
771 /* hi_Q might be too high by 1 or 2, but it isn't too low. */
772 ulong p0 = hi_Q * hi_D;
773 ulong p1 = hi_Q * lo_D;
774 ulong hi_P;
775
776 while ((hi_P = p0 + (p1 >> half_bits)) > msw ||
777 (hi_P == msw && ((p1 & half_mask) << half_bits) > lsw)
778 ) { /* hi_Q was too high by 1. */
779 --hi_Q;
780 p0 -= hi_D;
781 p1 -= lo_D;
782 mincr(mqh);
783 }
784 p1 = (p1 & half_mask) << half_bits;
785 if (p1 > lsw)
786 msw--;
787 lsw -= p1;
788 msw -= hi_P;
789 /* Now repeat to get the lower-half quotient. */
790 msw = (msw << half_bits) + (lsw >> half_bits);
791 #if max_fixed < max_long
792 lsw &= half_mask;
793 #endif
794 lsw <<= half_bits;
795 {
796 ulong lo_Q = (ulong) msw / hi_D;
797 long Q;
798
799 p1 = lo_Q * lo_D;
800 p0 = lo_Q * hi_D;
801 while ((hi_P = p0 + (p1 >> half_bits)) > msw ||
802 (hi_P == msw && ((p1 & half_mask) << half_bits) > lsw)
803 ) { /* lo_Q was too high by 1. */
804 --lo_Q;
805 p0 -= hi_D;
806 p1 -= lo_D;
807 mincr(mql);
808 }
809 Q = (hi_Q << half_bits) + lo_Q;
810 return (signed_A >= 0 ? Q : p0 | p1 ? ~Q /* -Q - 1 */ : -Q);
811 }
812 }
813 }
814 }
815
816 #else /* use doubles */
817
818 /*
819 * Compute A * B / C as above using doubles. If floating point is
820 * reasonably fast, this is much faster than the fixed-point algorithm.
821 */
822 fixed
fixed_mult_quo(fixed signed_A,fixed B,fixed C)823 fixed_mult_quo(fixed signed_A, fixed B, fixed C)
824 {
825 /*
826 * Check whether A * B will fit in the mantissa of a double.
827 */
828 #define MAX_OTHER_FACTOR (1L << MAX_OTHER_FACTOR_BITS)
829 if (B < MAX_OTHER_FACTOR || any_abs(signed_A) < MAX_OTHER_FACTOR) {
830 #undef MAX_OTHER_FACTOR
831 /*
832 * The product fits, so a straightforward double computation
833 * will be exact.
834 */
835 return (fixed)floor((double)signed_A * B / C);
836 } else {
837 /*
838 * The product won't fit. However, the approximate product will
839 * only be off by at most +/- 1/2 * (1 << ROUND_BITS) because of
840 * rounding. If we add 1 << ROUND_BITS to the value of the product
841 * (i.e., 1 in the least significant bit of the mantissa), the
842 * result is always greater than the correct product by between 1/2
843 * and 3/2 * (1 << ROUND_BITS). We know this is less than C:
844 * because of the 'if' just above, we know that B >=
845 * MAX_OTHER_FACTOR; since B <= C, we know C >= MAX_OTHER_FACTOR;
846 * and because of the #if that chose between the two
847 * implementations, we know that C >= 2 * (1 << ROUND_BITS). Hence,
848 * the quotient after dividing by C will be at most 1 too large.
849 */
850 fixed q =
851 (fixed)floor(((double)signed_A * B + (1L << ROUND_BITS)) / C);
852
853 /*
854 * Compute the remainder R. If the quotient was correct,
855 * 0 <= R < C. If the quotient was too high, -C <= R < 0.
856 */
857 if (signed_A * B - q * C < 0)
858 --q;
859 return q;
860 }
861 }
862
863 #endif
864
865 #undef MAX_OTHER_FACTOR_BITS
866 #undef ROUND_BITS
867
868 #undef num_bits
869 #undef half_bits
870 #undef half_mask
871
872 /* Trace calls on sqrt when debugging. */
873 double
gs_sqrt(double x,const char * file,int line)874 gs_sqrt(double x, const char *file, int line)
875 {
876 if (gs_debug_c('~')) {
877 dprintf3("[~]sqrt(%g) at %s:%d\n", x, (const char *)file, line);
878 dflush();
879 }
880 return orig_sqrt(x);
881 }
882
883 static const int isincos[5] =
884 {0, 1, 0, -1, 0};
885
886 /* GCC with -ffast-math compiles ang/90. as ang*(1/90.), losing precission.
887 * This doesn't happen when the numeral is replaced with a non-const variable.
888 * So we define the variable to work around the GCC problem.
889 */
890 double const_90_degrees = 90.;
891
892 double
gs_sin_degrees(double ang)893 gs_sin_degrees(double ang)
894 {
895 double quot = ang / const_90_degrees;
896
897 if (floor(quot) == quot) {
898 /*
899 * We need 4.0, rather than 4, here because of non-ANSI compilers.
900 * The & 3 is because quot might be negative.
901 */
902 return isincos[(int)fmod(quot, 4.0) & 3];
903 }
904 return sin(ang * (M_PI / 180));
905 }
906
907 double
gs_cos_degrees(double ang)908 gs_cos_degrees(double ang)
909 {
910 double quot = ang / const_90_degrees;
911
912 if (floor(quot) == quot) {
913 /* See above re the following line. */
914 return isincos[((int)fmod(quot, 4.0) & 3) + 1];
915 }
916 return cos(ang * (M_PI / 180));
917 }
918
919 void
gs_sincos_degrees(double ang,gs_sincos_t * psincos)920 gs_sincos_degrees(double ang, gs_sincos_t * psincos)
921 {
922 double quot = ang / const_90_degrees;
923
924 if (floor(quot) == quot) {
925 /* See above re the following line. */
926 int quads = (int)fmod(quot, 4.0) & 3;
927
928 psincos->sin = isincos[quads];
929 psincos->cos = isincos[quads + 1];
930 psincos->orthogonal = true;
931 } else {
932 double arad = ang * (M_PI / 180);
933
934 psincos->sin = sin(arad);
935 psincos->cos = cos(arad);
936 psincos->orthogonal = false;
937 }
938 }
939
940 /*
941 * Define an atan2 function that returns an angle in degrees and uses
942 * the PostScript quadrant rules. Note that it may return
943 * gs_error_undefinedresult.
944 */
945 int
gs_atan2_degrees(double y,double x,double * pangle)946 gs_atan2_degrees(double y, double x, double *pangle)
947 {
948 if (y == 0) { /* on X-axis, special case */
949 if (x == 0)
950 return_error(gs_error_undefinedresult);
951 *pangle = (x < 0 ? 180 : 0);
952 } else {
953 double result = atan2(y, x) * radians_to_degrees;
954
955 if (result < 0)
956 result += 360;
957 *pangle = result;
958 }
959 return 0;
960 }
961
962 /*
963 * Define a function for finding intersection of small bars.
964 * Coordinates must be so small that their cubes fit into 60 bits.
965 * This function doesn't check intersections at end of bars,
966 * so the caller must care of them on necessity.
967 * Returns : *ry is the Y-coordinate of the intersection
968 * truncated to 'fixed'; *ey is 1 iff the precise Y coordinate of
969 * the intersection is greater than *ry (used by the shading algorithm).
970 */
971 bool
gx_intersect_small_bars(fixed q0x,fixed q0y,fixed q1x,fixed q1y,fixed q2x,fixed q2y,fixed q3x,fixed q3y,fixed * ry,fixed * ey)972 gx_intersect_small_bars(fixed q0x, fixed q0y, fixed q1x, fixed q1y, fixed q2x, fixed q2y,
973 fixed q3x, fixed q3y, fixed *ry, fixed *ey)
974 {
975 fixed dx1 = q1x - q0x, dy1 = q1y - q0y;
976 fixed dx2 = q2x - q0x, dy2 = q2y - q0y;
977 fixed dx3 = q3x - q0x, dy3 = q3y - q0y;
978
979 int64_t vp2a, vp2b, vp3a, vp3b;
980 int s2, s3;
981
982 if (dx1 == 0 && dy1 == 0)
983 return false; /* Zero length bars are out of interest. */
984 if (dx2 == 0 && dy2 == 0)
985 return false; /* Contacting ends are out of interest. */
986 if (dx3 == 0 && dy3 == 0)
987 return false; /* Contacting ends are out of interest. */
988 if (dx2 == dx1 && dy2 == dy1)
989 return false; /* Contacting ends are out of interest. */
990 if (dx3 == dx1 && dy3 == dy1)
991 return false; /* Contacting ends are out of interest. */
992 if (dx2 == dx3 && dy2 == dy3)
993 return false; /* Zero length bars are out of interest. */
994 vp2a = (int64_t)dx1 * dy2;
995 vp2b = (int64_t)dy1 * dx2;
996 /* vp2 = vp2a - vp2b; It can overflow int64_t, but we only need the sign. */
997 if (vp2a > vp2b)
998 s2 = 1;
999 else if (vp2a < vp2b)
1000 s2 = -1;
1001 else
1002 s2 = 0;
1003 vp3a = (int64_t)dx1 * dy3;
1004 vp3b = (int64_t)dy1 * dx3;
1005 /* vp3 = vp3a - vp3b; It can overflow int64_t, but we only need the sign. */
1006 if (vp3a > vp3b)
1007 s3 = 1;
1008 else if (vp3a < vp3b)
1009 s3 = -1;
1010 else
1011 s3 = 0;
1012 if (s2 == 0) {
1013 if (s3 == 0)
1014 return false; /* Collinear bars - out of interest. */
1015 if (0 <= dx2 && dx2 <= dx1 && 0 <= dy2 && dy2 <= dy1) {
1016 /* The start of the bar 2 is in the bar 1. */
1017 *ry = q2y;
1018 *ey = 0;
1019 return true;
1020 }
1021 } else if (s3 == 0) {
1022 if (0 <= dx3 && dx3 <= dx1 && 0 <= dy3 && dy3 <= dy1) {
1023 /* The end of the bar 2 is in the bar 1. */
1024 *ry = q3y;
1025 *ey = 0;
1026 return true;
1027 }
1028 } else if (s2 * s3 < 0) {
1029 /* The intersection definitely exists, so the determinant isn't zero. */
1030 fixed d23x = dx3 - dx2, d23y = dy3 - dy2;
1031 int64_t det = (int64_t)dx1 * d23y - (int64_t)dy1 * d23x;
1032 int64_t mul = (int64_t)dx2 * d23y - (int64_t)dy2 * d23x;
1033 {
1034 /* Assuming small bars : cubes of coordinates must fit into int64_t.
1035 curve_samples must provide that. */
1036 int64_t num = dy1 * mul, iiy;
1037 fixed iy;
1038 fixed pry, pey;
1039
1040 { /* Likely when called form wedge_trap_decompose or constant_color_quadrangle,
1041 we always have det > 0 && num >= 0, but we check here for a safety reason. */
1042 if (det < 0)
1043 num = -num, det = -det;
1044 iiy = (num >= 0 ? num / det : (num - det + 1) / det);
1045 iy = (fixed)iiy;
1046 if (iy != iiy) {
1047 /* If it is inside the bars, it must fit into fixed. */
1048 return false;
1049 }
1050 }
1051 if (dy1 > 0) {
1052 if (iy < 0 || iy >= dy1)
1053 return false; /* Outside the bar 1. */
1054 } else {
1055 if (iy > 0 || iy <= dy1)
1056 return false; /* Outside the bar 1. */
1057 }
1058 if (dy2 < dy3) {
1059 if (iy <= dy2 || iy >= dy3)
1060 return false; /* Outside the bar 2. */
1061 } else {
1062 if (iy >= dy2 || iy <= dy3)
1063 return false; /* Outside the bar 2. */
1064 }
1065 pry = q0y + (fixed)iy;
1066 pey = (iy * det < num ? 1 : 0);
1067 *ry = pry;
1068 *ey = pey;
1069 }
1070 return true;
1071 }
1072 return false;
1073 }
1074
1075 /* gs_debug_flags handling code */
1076
1077 const gs_debug_flag_details gs_debug_flags[] =
1078 {
1079 #define FLAG(a,b,c,d) {1, # a ,d}
1080 #define UNUSED(a) { 0, "", "" },
1081 #include "gdbflags.h"
1082 #undef FLAG
1083 #undef UNUSED
1084 };
1085
1086 const byte gs_debug_flag_implied_by[] =
1087 {
1088 #define FLAG(a,b,c,d) c
1089 #define UNUSED(a) 0,
1090 #include "gdbflags.h"
1091 #undef FLAG
1092 #undef UNUSED
1093 };
1094
gs_debug_flags_parse(gs_memory_t * heap,const char * arg)1095 int gs_debug_flags_parse(gs_memory_t *heap, const char *arg)
1096 {
1097 #ifdef DEBUG
1098 const char *p;
1099 int i, j;
1100 int result = 0;
1101
1102 while (*arg != 0) {
1103 /* Skip over any commas */
1104 byte value = 0xff;
1105 while (*arg == ',')
1106 arg++;
1107 if (*arg == '-') {
1108 value = 0;
1109 arg++;
1110 }
1111 if (*arg == ',') {
1112 arg++;
1113 continue;
1114 }
1115 if (*arg == 0)
1116 return result;
1117 for (i=0; i < gs_debug_flags_max; i++) {
1118 char c, d;
1119 if (!gs_debug_flags[i].used)
1120 continue;
1121 p = arg;
1122 for (j=0; j < sizeof(gs_debug_flags[i].short_desc); j++) {
1123 d = gs_debug_flags[i].short_desc[j];
1124 c = *p++;
1125 if (d == '_') d = '-';
1126 if (c == ',')
1127 c = 0;
1128 if ((c != d) || (c == 0))
1129 break;
1130 }
1131 if ((c == 0) && (d == 0))
1132 break;
1133 }
1134 if (i < gs_debug_flags_max)
1135 gs_debug[i] = value;
1136 else {
1137 outprintf(heap, "Unknown debug flag: ");
1138 p = arg;
1139 do {
1140 char c = *p++;
1141 if ((c == 0) || (c == ','))
1142 break;
1143 outprintf(heap, "%c", c);
1144 } while (1);
1145 outprintf(heap, "\n");
1146 result = gs_error_Fatal;
1147 }
1148 arg = p-1;
1149 }
1150 return result;
1151 #else
1152 outprintf(heap, "Warning: debug flags ignored in release builds\n");
1153 return 0;
1154 #endif
1155 }
1156
1157 void
gs_debug_flags_list(gs_memory_t * heap)1158 gs_debug_flags_list(gs_memory_t *heap)
1159 {
1160 #ifdef DEBUG
1161 int i, j;
1162
1163 outprintf(heap, "Debugging flags are as follows:\n\n-Z --debug= Description\n");
1164 for (i=0; i < gs_debug_flags_max; i++) {
1165 if (!gs_debug_flags[i].used)
1166 continue;
1167 outprintf(heap, " %c ", (i < 32 || i > 126 ? ' ' : i));
1168 for (j=0; j < sizeof(gs_debug_flags[i].short_desc); j++) {
1169 char c = gs_debug_flags[i].short_desc[j];
1170 if (c == 0)
1171 break;
1172 if (c == '_')
1173 c = '-';
1174 outprintf(heap, "%c", c);
1175 }
1176 for (; j < sizeof(gs_debug_flags[i].short_desc); j++) {
1177 outprintf(heap, " ");
1178 }
1179 outprintf(heap, "%s\n", gs_debug_flags[i].long_desc);
1180 }
1181 outprintf(heap,
1182 "\nDebugging may be enabled by using -Zx (where x is one of the 1 character\n"
1183 "codes given above), or by using --debug=xxxxx. Multiple flags may be specified\n"
1184 "at once, using -Zxyz or --debug=xxxxx,yyyyy,zzzzz. -Z=-x or --debug=-xxxxx\n"
1185 "disables a flag once set.\n");
1186 #else
1187 outprintf(heap, "No debug flags supported in release builds\n");
1188 #endif
1189 }
1190
1191