1 //========================================================================
2 //
3 // Function.cc
4 //
5 // Copyright 2001-2003 Glyph & Cog, LLC
6 //
7 //========================================================================
8
9 #include <aconf.h>
10
11 #ifdef USE_GCC_PRAGMAS
12 #pragma implementation
13 #endif
14
15 #include <stdlib.h>
16 #include <string.h>
17 #include <ctype.h>
18 #include <math.h>
19 #include "gmem.h"
20 #include "GList.h"
21 #include "Object.h"
22 #include "Dict.h"
23 #include "Stream.h"
24 #include "Error.h"
25 #include "Function.h"
26
27 //------------------------------------------------------------------------
28
29 // Max depth of nested functions. This is used to catch infinite
30 // loops in the function object structure.
31 #define recursionLimit 8
32
33 //------------------------------------------------------------------------
34 // Function
35 //------------------------------------------------------------------------
36
Function()37 Function::Function() {
38 }
39
~Function()40 Function::~Function() {
41 }
42
parse(Object * funcObj,int recursion)43 Function *Function::parse(Object *funcObj, int recursion) {
44 Function *func;
45 Dict *dict;
46 int funcType;
47 Object obj1;
48
49 if (recursion > recursionLimit) {
50 error(errSyntaxError, -1, "Loop detected in function objects");
51 return NULL;
52 }
53
54 if (funcObj->isStream()) {
55 dict = funcObj->streamGetDict();
56 } else if (funcObj->isDict()) {
57 dict = funcObj->getDict();
58 } else if (funcObj->isName("Identity")) {
59 return new IdentityFunction();
60 } else {
61 error(errSyntaxError, -1, "Expected function dictionary or stream");
62 return NULL;
63 }
64
65 if (!dict->lookup("FunctionType", &obj1)->isInt()) {
66 error(errSyntaxError, -1, "Function type is missing or wrong type");
67 obj1.free();
68 return NULL;
69 }
70 funcType = obj1.getInt();
71 obj1.free();
72
73 if (funcType == 0) {
74 func = new SampledFunction(funcObj, dict);
75 } else if (funcType == 2) {
76 func = new ExponentialFunction(funcObj, dict);
77 } else if (funcType == 3) {
78 func = new StitchingFunction(funcObj, dict, recursion);
79 } else if (funcType == 4) {
80 func = new PostScriptFunction(funcObj, dict);
81 } else {
82 error(errSyntaxError, -1, "Unimplemented function type ({0:d})", funcType);
83 return NULL;
84 }
85 if (!func->isOk()) {
86 delete func;
87 return NULL;
88 }
89
90 return func;
91 }
92
init(Dict * dict)93 GBool Function::init(Dict *dict) {
94 Object obj1, obj2;
95 int i;
96
97 //----- Domain
98 if (!dict->lookup("Domain", &obj1)->isArray()) {
99 error(errSyntaxError, -1, "Function is missing domain");
100 goto err2;
101 }
102 m = obj1.arrayGetLength() / 2;
103 if (m > funcMaxInputs) {
104 error(errSyntaxError, -1,
105 "Functions with more than {0:d} inputs are unsupported",
106 funcMaxInputs);
107 goto err2;
108 }
109 for (i = 0; i < m; ++i) {
110 obj1.arrayGet(2*i, &obj2);
111 if (!obj2.isNum()) {
112 error(errSyntaxError, -1, "Illegal value in function domain array");
113 goto err1;
114 }
115 domain[i][0] = obj2.getNum();
116 obj2.free();
117 obj1.arrayGet(2*i+1, &obj2);
118 if (!obj2.isNum()) {
119 error(errSyntaxError, -1, "Illegal value in function domain array");
120 goto err1;
121 }
122 domain[i][1] = obj2.getNum();
123 obj2.free();
124 }
125 obj1.free();
126
127 //----- Range
128 hasRange = gFalse;
129 n = 0;
130 if (dict->lookup("Range", &obj1)->isArray()) {
131 hasRange = gTrue;
132 n = obj1.arrayGetLength() / 2;
133 if (n > funcMaxOutputs) {
134 error(errSyntaxError, -1,
135 "Functions with more than {0:d} outputs are unsupported",
136 funcMaxOutputs);
137 goto err2;
138 }
139 for (i = 0; i < n; ++i) {
140 obj1.arrayGet(2*i, &obj2);
141 if (!obj2.isNum()) {
142 error(errSyntaxError, -1, "Illegal value in function range array");
143 goto err1;
144 }
145 range[i][0] = obj2.getNum();
146 obj2.free();
147 obj1.arrayGet(2*i+1, &obj2);
148 if (!obj2.isNum()) {
149 error(errSyntaxError, -1, "Illegal value in function range array");
150 goto err1;
151 }
152 range[i][1] = obj2.getNum();
153 obj2.free();
154 }
155 }
156 obj1.free();
157
158 return gTrue;
159
160 err1:
161 obj2.free();
162 err2:
163 obj1.free();
164 return gFalse;
165 }
166
167 //------------------------------------------------------------------------
168 // IdentityFunction
169 //------------------------------------------------------------------------
170
IdentityFunction()171 IdentityFunction::IdentityFunction() {
172 int i;
173
174 // fill these in with arbitrary values just in case they get used
175 // somewhere
176 m = funcMaxInputs;
177 n = funcMaxOutputs;
178 for (i = 0; i < funcMaxInputs; ++i) {
179 domain[i][0] = 0;
180 domain[i][1] = 1;
181 }
182 hasRange = gFalse;
183 }
184
~IdentityFunction()185 IdentityFunction::~IdentityFunction() {
186 }
187
transform(double * in,double * out)188 void IdentityFunction::transform(double *in, double *out) {
189 int i;
190
191 for (i = 0; i < funcMaxOutputs; ++i) {
192 out[i] = in[i];
193 }
194 }
195
196 //------------------------------------------------------------------------
197 // SampledFunction
198 //------------------------------------------------------------------------
199
SampledFunction(Object * funcObj,Dict * dict)200 SampledFunction::SampledFunction(Object *funcObj, Dict *dict) {
201 Stream *str;
202 int sampleBits;
203 double sampleMul;
204 Object obj1, obj2;
205 Guint buf, bitMask;
206 int bits;
207 Guint s;
208 double in[funcMaxInputs];
209 int i, j, t, bit, idx;
210
211 idxOffset = NULL;
212 samples = NULL;
213 sBuf = NULL;
214 ok = gFalse;
215
216 //----- initialize the generic stuff
217 if (!init(dict)) {
218 goto err1;
219 }
220 if (!hasRange) {
221 error(errSyntaxError, -1, "Type 0 function is missing range");
222 goto err1;
223 }
224 if (m > sampledFuncMaxInputs) {
225 error(errSyntaxError, -1,
226 "Sampled functions with more than {0:d} inputs are unsupported",
227 sampledFuncMaxInputs);
228 goto err1;
229 }
230
231 //----- buffer
232 sBuf = (double *)gmallocn(1 << m, sizeof(double));
233
234 //----- get the stream
235 if (!funcObj->isStream()) {
236 error(errSyntaxError, -1, "Type 0 function isn't a stream");
237 goto err1;
238 }
239 str = funcObj->getStream();
240
241 //----- Size
242 if (!dict->lookup("Size", &obj1)->isArray() ||
243 obj1.arrayGetLength() != m) {
244 error(errSyntaxError, -1, "Function has missing or invalid size array");
245 goto err2;
246 }
247 for (i = 0; i < m; ++i) {
248 obj1.arrayGet(i, &obj2);
249 if (!obj2.isInt()) {
250 error(errSyntaxError, -1, "Illegal value in function size array");
251 goto err3;
252 }
253 sampleSize[i] = obj2.getInt();
254 if (sampleSize[i] <= 0) {
255 error(errSyntaxError, -1, "Illegal non-positive value in function size array");
256 goto err3;
257 }
258 obj2.free();
259 }
260 obj1.free();
261 idxOffset = (int *)gmallocn(1 << m, sizeof(int));
262 for (i = 0; i < (1<<m); ++i) {
263 idx = 0;
264 for (j = m - 1, t = i; j >= 1; --j, t <<= 1) {
265 if (sampleSize[j] == 1) {
266 bit = 0;
267 } else {
268 bit = (t >> (m - 1)) & 1;
269 }
270 idx = (idx + bit) * sampleSize[j-1];
271 }
272 if (sampleSize[0] == 1) {
273 bit = 0;
274 } else {
275 bit = (t >> (m - 1)) & 1;
276 }
277 idxOffset[i] = (idx + bit) * n;
278 }
279
280 //----- BitsPerSample
281 if (!dict->lookup("BitsPerSample", &obj1)->isInt()) {
282 error(errSyntaxError, -1, "Function has missing or invalid BitsPerSample");
283 goto err2;
284 }
285 sampleBits = obj1.getInt();
286 sampleMul = 1.0 / (pow(2.0, (double)sampleBits) - 1);
287 obj1.free();
288
289 //----- Encode
290 if (dict->lookup("Encode", &obj1)->isArray() &&
291 obj1.arrayGetLength() == 2*m) {
292 for (i = 0; i < m; ++i) {
293 obj1.arrayGet(2*i, &obj2);
294 if (!obj2.isNum()) {
295 error(errSyntaxError, -1, "Illegal value in function encode array");
296 goto err3;
297 }
298 encode[i][0] = obj2.getNum();
299 obj2.free();
300 obj1.arrayGet(2*i+1, &obj2);
301 if (!obj2.isNum()) {
302 error(errSyntaxError, -1, "Illegal value in function encode array");
303 goto err3;
304 }
305 encode[i][1] = obj2.getNum();
306 obj2.free();
307 }
308 } else {
309 for (i = 0; i < m; ++i) {
310 encode[i][0] = 0;
311 encode[i][1] = sampleSize[i] - 1;
312 }
313 }
314 obj1.free();
315 for (i = 0; i < m; ++i) {
316 inputMul[i] = (encode[i][1] - encode[i][0]) /
317 (domain[i][1] - domain[i][0]);
318 }
319
320 //----- Decode
321 if (dict->lookup("Decode", &obj1)->isArray() &&
322 obj1.arrayGetLength() == 2*n) {
323 for (i = 0; i < n; ++i) {
324 obj1.arrayGet(2*i, &obj2);
325 if (!obj2.isNum()) {
326 error(errSyntaxError, -1, "Illegal value in function decode array");
327 goto err3;
328 }
329 decode[i][0] = obj2.getNum();
330 obj2.free();
331 obj1.arrayGet(2*i+1, &obj2);
332 if (!obj2.isNum()) {
333 error(errSyntaxError, -1, "Illegal value in function decode array");
334 goto err3;
335 }
336 decode[i][1] = obj2.getNum();
337 obj2.free();
338 }
339 } else {
340 for (i = 0; i < n; ++i) {
341 decode[i][0] = range[i][0];
342 decode[i][1] = range[i][1];
343 }
344 }
345 obj1.free();
346
347 //----- samples
348 nSamples = n;
349 for (i = 0; i < m; ++i)
350 nSamples *= sampleSize[i];
351 samples = (double *)gmallocn(nSamples, sizeof(double));
352 buf = 0;
353 bits = 0;
354 bitMask = (sampleBits < 32) ? ((1 << sampleBits) - 1) : 0xffffffffU;
355 str->reset();
356 for (i = 0; i < nSamples; ++i) {
357 if (sampleBits == 8) {
358 s = str->getChar();
359 } else if (sampleBits == 16) {
360 s = str->getChar();
361 s = (s << 8) + str->getChar();
362 } else if (sampleBits == 32) {
363 s = str->getChar();
364 s = (s << 8) + str->getChar();
365 s = (s << 8) + str->getChar();
366 s = (s << 8) + str->getChar();
367 } else {
368 while (bits < sampleBits) {
369 buf = (buf << 8) | (str->getChar() & 0xff);
370 bits += 8;
371 }
372 s = (buf >> (bits - sampleBits)) & bitMask;
373 bits -= sampleBits;
374 }
375 samples[i] = (double)s * sampleMul;
376 }
377 str->close();
378
379 // set up the cache
380 for (i = 0; i < m; ++i) {
381 in[i] = domain[i][0];
382 cacheIn[i] = in[i] - 1;
383 }
384 transform(in, cacheOut);
385
386 ok = gTrue;
387 return;
388
389 err3:
390 obj2.free();
391 err2:
392 obj1.free();
393 err1:
394 return;
395 }
396
~SampledFunction()397 SampledFunction::~SampledFunction() {
398 if (idxOffset) {
399 gfree(idxOffset);
400 }
401 if (samples) {
402 gfree(samples);
403 }
404 if (sBuf) {
405 gfree(sBuf);
406 }
407 }
408
SampledFunction(SampledFunction * func)409 SampledFunction::SampledFunction(SampledFunction *func) {
410 memcpy(this, func, sizeof(SampledFunction));
411 idxOffset = (int *)gmallocn(1 << m, sizeof(int));
412 memcpy(idxOffset, func->idxOffset, (1 << m) * (int)sizeof(int));
413 samples = (double *)gmallocn(nSamples, sizeof(double));
414 memcpy(samples, func->samples, nSamples * sizeof(double));
415 sBuf = (double *)gmallocn(1 << m, sizeof(double));
416 }
417
transform(double * in,double * out)418 void SampledFunction::transform(double *in, double *out) {
419 double x;
420 int e[funcMaxInputs];
421 double efrac0[funcMaxInputs];
422 double efrac1[funcMaxInputs];
423 int i, j, k, idx0, t;
424
425 // check the cache
426 for (i = 0; i < m; ++i) {
427 if (in[i] != cacheIn[i]) {
428 break;
429 }
430 }
431 if (i == m) {
432 for (i = 0; i < n; ++i) {
433 out[i] = cacheOut[i];
434 }
435 return;
436 }
437
438 // map input values into sample array
439 for (i = 0; i < m; ++i) {
440 x = (in[i] - domain[i][0]) * inputMul[i] + encode[i][0];
441 if (x < 0 || x != x) { // x!=x is a more portable version of isnan(x)
442 x = 0;
443 } else if (x > sampleSize[i] - 1) {
444 x = sampleSize[i] - 1;
445 }
446 e[i] = (int)x;
447 if (e[i] == sampleSize[i] - 1 && sampleSize[i] > 1) {
448 // this happens if in[i] = domain[i][1]
449 e[i] = sampleSize[i] - 2;
450 }
451 efrac1[i] = x - e[i];
452 efrac0[i] = 1 - efrac1[i];
453 }
454
455 // compute index for the first sample to be used
456 idx0 = 0;
457 for (k = m - 1; k >= 1; --k) {
458 idx0 = (idx0 + e[k]) * sampleSize[k-1];
459 }
460 idx0 = (idx0 + e[0]) * n;
461
462 // for each output, do m-linear interpolation
463 for (i = 0; i < n; ++i) {
464
465 // pull 2^m values out of the sample array
466 for (j = 0; j < (1<<m); ++j) {
467 sBuf[j] = samples[idx0 + idxOffset[j] + i];
468 }
469
470 // do m sets of interpolations
471 for (j = 0, t = (1<<m); j < m; ++j, t >>= 1) {
472 for (k = 0; k < t; k += 2) {
473 sBuf[k >> 1] = efrac0[j] * sBuf[k] + efrac1[j] * sBuf[k+1];
474 }
475 }
476
477 // map output value to range
478 out[i] = sBuf[0] * (decode[i][1] - decode[i][0]) + decode[i][0];
479 if (out[i] < range[i][0]) {
480 out[i] = range[i][0];
481 } else if (out[i] > range[i][1]) {
482 out[i] = range[i][1];
483 }
484 }
485
486 // save current result in the cache
487 for (i = 0; i < m; ++i) {
488 cacheIn[i] = in[i];
489 }
490 for (i = 0; i < n; ++i) {
491 cacheOut[i] = out[i];
492 }
493 }
494
495 //------------------------------------------------------------------------
496 // ExponentialFunction
497 //------------------------------------------------------------------------
498
ExponentialFunction(Object * funcObj,Dict * dict)499 ExponentialFunction::ExponentialFunction(Object *funcObj, Dict *dict) {
500 Object obj1, obj2;
501 int i;
502
503 ok = gFalse;
504
505 //----- initialize the generic stuff
506 if (!init(dict)) {
507 goto err1;
508 }
509 if (m != 1) {
510 error(errSyntaxError, -1, "Exponential function with more than one input");
511 goto err1;
512 }
513
514 //----- C0
515 if (dict->lookup("C0", &obj1)->isArray()) {
516 if (hasRange && obj1.arrayGetLength() != n) {
517 error(errSyntaxError, -1, "Function's C0 array is wrong length");
518 goto err2;
519 }
520 n = obj1.arrayGetLength();
521 for (i = 0; i < n; ++i) {
522 obj1.arrayGet(i, &obj2);
523 if (!obj2.isNum()) {
524 error(errSyntaxError, -1, "Illegal value in function C0 array");
525 goto err3;
526 }
527 c0[i] = obj2.getNum();
528 obj2.free();
529 }
530 } else {
531 if (hasRange && n != 1) {
532 error(errSyntaxError, -1, "Function's C0 array is wrong length");
533 goto err2;
534 }
535 n = 1;
536 c0[0] = 0;
537 }
538 obj1.free();
539
540 //----- C1
541 if (dict->lookup("C1", &obj1)->isArray()) {
542 if (obj1.arrayGetLength() != n) {
543 error(errSyntaxError, -1, "Function's C1 array is wrong length");
544 goto err2;
545 }
546 for (i = 0; i < n; ++i) {
547 obj1.arrayGet(i, &obj2);
548 if (!obj2.isNum()) {
549 error(errSyntaxError, -1, "Illegal value in function C1 array");
550 goto err3;
551 }
552 c1[i] = obj2.getNum();
553 obj2.free();
554 }
555 } else {
556 if (n != 1) {
557 error(errSyntaxError, -1, "Function's C1 array is wrong length");
558 goto err2;
559 }
560 c1[0] = 1;
561 }
562 obj1.free();
563
564 //----- N (exponent)
565 if (!dict->lookup("N", &obj1)->isNum()) {
566 error(errSyntaxError, -1, "Function has missing or invalid N");
567 goto err2;
568 }
569 e = obj1.getNum();
570 obj1.free();
571
572 ok = gTrue;
573 return;
574
575 err3:
576 obj2.free();
577 err2:
578 obj1.free();
579 err1:
580 return;
581 }
582
~ExponentialFunction()583 ExponentialFunction::~ExponentialFunction() {
584 }
585
ExponentialFunction(ExponentialFunction * func)586 ExponentialFunction::ExponentialFunction(ExponentialFunction *func) {
587 memcpy(this, func, sizeof(ExponentialFunction));
588 }
589
transform(double * in,double * out)590 void ExponentialFunction::transform(double *in, double *out) {
591 double x;
592 int i;
593
594 if (in[0] < domain[0][0]) {
595 x = domain[0][0];
596 } else if (in[0] > domain[0][1]) {
597 x = domain[0][1];
598 } else {
599 x = in[0];
600 }
601 for (i = 0; i < n; ++i) {
602 out[i] = c0[i] + pow(x, e) * (c1[i] - c0[i]);
603 if (hasRange) {
604 if (out[i] < range[i][0]) {
605 out[i] = range[i][0];
606 } else if (out[i] > range[i][1]) {
607 out[i] = range[i][1];
608 }
609 }
610 }
611 return;
612 }
613
614 //------------------------------------------------------------------------
615 // StitchingFunction
616 //------------------------------------------------------------------------
617
StitchingFunction(Object * funcObj,Dict * dict,int recursion)618 StitchingFunction::StitchingFunction(Object *funcObj, Dict *dict,
619 int recursion) {
620 Object obj1, obj2;
621 int i;
622
623 ok = gFalse;
624 funcs = NULL;
625 bounds = NULL;
626 encode = NULL;
627 scale = NULL;
628
629 //----- initialize the generic stuff
630 if (!init(dict)) {
631 goto err1;
632 }
633 if (m != 1) {
634 error(errSyntaxError, -1, "Stitching function with more than one input");
635 goto err1;
636 }
637
638 //----- Functions
639 if (!dict->lookup("Functions", &obj1)->isArray()) {
640 error(errSyntaxError, -1,
641 "Missing 'Functions' entry in stitching function");
642 goto err1;
643 }
644 k = obj1.arrayGetLength();
645 funcs = (Function **)gmallocn(k, sizeof(Function *));
646 bounds = (double *)gmallocn(k + 1, sizeof(double));
647 encode = (double *)gmallocn(2 * k, sizeof(double));
648 scale = (double *)gmallocn(k, sizeof(double));
649 for (i = 0; i < k; ++i) {
650 funcs[i] = NULL;
651 }
652 for (i = 0; i < k; ++i) {
653 if (!(funcs[i] = Function::parse(obj1.arrayGet(i, &obj2),
654 recursion + 1))) {
655 goto err2;
656 }
657 if (funcs[i]->getInputSize() != 1 ||
658 (i > 0 && funcs[i]->getOutputSize() != funcs[0]->getOutputSize())) {
659 error(errSyntaxError, -1,
660 "Incompatible subfunctions in stitching function");
661 goto err2;
662 }
663 obj2.free();
664 }
665 obj1.free();
666
667 //----- Bounds
668 if (!dict->lookup("Bounds", &obj1)->isArray() ||
669 obj1.arrayGetLength() != k - 1) {
670 error(errSyntaxError, -1,
671 "Missing or invalid 'Bounds' entry in stitching function");
672 goto err1;
673 }
674 bounds[0] = domain[0][0];
675 for (i = 1; i < k; ++i) {
676 if (!obj1.arrayGet(i - 1, &obj2)->isNum()) {
677 error(errSyntaxError, -1,
678 "Invalid type in 'Bounds' array in stitching function");
679 goto err2;
680 }
681 bounds[i] = obj2.getNum();
682 obj2.free();
683 }
684 bounds[k] = domain[0][1];
685 obj1.free();
686
687 //----- Encode
688 if (!dict->lookup("Encode", &obj1)->isArray() ||
689 obj1.arrayGetLength() != 2 * k) {
690 error(errSyntaxError, -1,
691 "Missing or invalid 'Encode' entry in stitching function");
692 goto err1;
693 }
694 for (i = 0; i < 2 * k; ++i) {
695 if (!obj1.arrayGet(i, &obj2)->isNum()) {
696 error(errSyntaxError, -1,
697 "Invalid type in 'Encode' array in stitching function");
698 goto err2;
699 }
700 encode[i] = obj2.getNum();
701 obj2.free();
702 }
703 obj1.free();
704
705 //----- pre-compute the scale factors
706 for (i = 0; i < k; ++i) {
707 if (bounds[i] == bounds[i+1]) {
708 // avoid a divide-by-zero -- in this situation, function i will
709 // never be used anyway
710 scale[i] = 0;
711 } else {
712 scale[i] = (encode[2*i+1] - encode[2*i]) / (bounds[i+1] - bounds[i]);
713 }
714 }
715
716 ok = gTrue;
717 return;
718
719 err2:
720 obj2.free();
721 err1:
722 obj1.free();
723 }
724
StitchingFunction(StitchingFunction * func)725 StitchingFunction::StitchingFunction(StitchingFunction *func) {
726 int i;
727
728 memcpy(this, func, sizeof(StitchingFunction));
729 funcs = (Function **)gmallocn(k, sizeof(Function *));
730 for (i = 0; i < k; ++i) {
731 funcs[i] = func->funcs[i]->copy();
732 }
733 bounds = (double *)gmallocn(k + 1, sizeof(double));
734 memcpy(bounds, func->bounds, (k + 1) * sizeof(double));
735 encode = (double *)gmallocn(2 * k, sizeof(double));
736 memcpy(encode, func->encode, 2 * k * sizeof(double));
737 scale = (double *)gmallocn(k, sizeof(double));
738 memcpy(scale, func->scale, k * sizeof(double));
739 ok = gTrue;
740 }
741
~StitchingFunction()742 StitchingFunction::~StitchingFunction() {
743 int i;
744
745 if (funcs) {
746 for (i = 0; i < k; ++i) {
747 if (funcs[i]) {
748 delete funcs[i];
749 }
750 }
751 }
752 gfree(funcs);
753 gfree(bounds);
754 gfree(encode);
755 gfree(scale);
756 }
757
transform(double * in,double * out)758 void StitchingFunction::transform(double *in, double *out) {
759 double x;
760 int i;
761
762 if (in[0] < domain[0][0]) {
763 x = domain[0][0];
764 } else if (in[0] > domain[0][1]) {
765 x = domain[0][1];
766 } else {
767 x = in[0];
768 }
769 for (i = 0; i < k - 1; ++i) {
770 if (x < bounds[i+1]) {
771 break;
772 }
773 }
774 x = encode[2*i] + (x - bounds[i]) * scale[i];
775 funcs[i]->transform(&x, out);
776 }
777
778 //------------------------------------------------------------------------
779 // PostScriptFunction
780 //------------------------------------------------------------------------
781
782 // This is not an enum, because we can't foreward-declare the enum
783 // type in Function.h
784 #define psOpAbs 0
785 #define psOpAdd 1
786 #define psOpAnd 2
787 #define psOpAtan 3
788 #define psOpBitshift 4
789 #define psOpCeiling 5
790 #define psOpCopy 6
791 #define psOpCos 7
792 #define psOpCvi 8
793 #define psOpCvr 9
794 #define psOpDiv 10
795 #define psOpDup 11
796 #define psOpEq 12
797 #define psOpExch 13
798 #define psOpExp 14
799 #define psOpFalse 15
800 #define psOpFloor 16
801 #define psOpGe 17
802 #define psOpGt 18
803 #define psOpIdiv 19
804 #define psOpIndex 20
805 #define psOpLe 21
806 #define psOpLn 22
807 #define psOpLog 23
808 #define psOpLt 24
809 #define psOpMod 25
810 #define psOpMul 26
811 #define psOpNe 27
812 #define psOpNeg 28
813 #define psOpNot 29
814 #define psOpOr 30
815 #define psOpPop 31
816 #define psOpRoll 32
817 #define psOpRound 33
818 #define psOpSin 34
819 #define psOpSqrt 35
820 #define psOpSub 36
821 #define psOpTrue 37
822 #define psOpTruncate 38
823 #define psOpXor 39
824 #define psOpPush 40
825 #define psOpJ 41
826 #define psOpJz 42
827
828 #define nPSOps 43
829
830 // Note: 'if' and 'ifelse' are parsed separately.
831 // The rest are listed here in alphabetical order.
832 // The index in this table is equivalent to the psOpXXX defines.
833 static const char *psOpNames[] = {
834 "abs",
835 "add",
836 "and",
837 "atan",
838 "bitshift",
839 "ceiling",
840 "copy",
841 "cos",
842 "cvi",
843 "cvr",
844 "div",
845 "dup",
846 "eq",
847 "exch",
848 "exp",
849 "false",
850 "floor",
851 "ge",
852 "gt",
853 "idiv",
854 "index",
855 "le",
856 "ln",
857 "log",
858 "lt",
859 "mod",
860 "mul",
861 "ne",
862 "neg",
863 "not",
864 "or",
865 "pop",
866 "roll",
867 "round",
868 "sin",
869 "sqrt",
870 "sub",
871 "true",
872 "truncate",
873 "xor"
874 };
875
876 struct PSCode {
877 int op;
878 union {
879 double d;
880 int i;
881 } val;
882 };
883
884 #define psStackSize 100
885
PostScriptFunction(Object * funcObj,Dict * dict)886 PostScriptFunction::PostScriptFunction(Object *funcObj, Dict *dict) {
887 Stream *str;
888 GList *tokens;
889 GString *tok;
890 double in[funcMaxInputs];
891 int tokPtr, codePtr, i;
892
893 codeString = NULL;
894 code = NULL;
895 codeSize = 0;
896 ok = gFalse;
897
898 //----- initialize the generic stuff
899 if (!init(dict)) {
900 goto err1;
901 }
902 if (!hasRange) {
903 error(errSyntaxError, -1, "Type 4 function is missing range");
904 goto err1;
905 }
906
907 //----- get the stream
908 if (!funcObj->isStream()) {
909 error(errSyntaxError, -1, "Type 4 function isn't a stream");
910 goto err1;
911 }
912 str = funcObj->getStream();
913
914 //----- tokenize the function
915 codeString = new GString();
916 tokens = new GList();
917 str->reset();
918 while ((tok = getToken(str))) {
919 tokens->append(tok);
920 }
921 str->close();
922
923 //----- parse the function
924 if (tokens->getLength() < 1 ||
925 ((GString *)tokens->get(0))->cmp("{")) {
926 error(errSyntaxError, -1, "Expected '{' at start of PostScript function");
927 goto err2;
928 }
929 tokPtr = 1;
930 codePtr = 0;
931 if (!parseCode(tokens, &tokPtr, &codePtr)) {
932 goto err2;
933 }
934 codeLen = codePtr;
935
936 //----- set up the cache
937 for (i = 0; i < m; ++i) {
938 in[i] = domain[i][0];
939 cacheIn[i] = in[i] - 1;
940 }
941 transform(in, cacheOut);
942
943 ok = gTrue;
944
945 err2:
946 deleteGList(tokens, GString);
947 err1:
948 return;
949 }
950
PostScriptFunction(PostScriptFunction * func)951 PostScriptFunction::PostScriptFunction(PostScriptFunction *func) {
952 memcpy(this, func, sizeof(PostScriptFunction));
953 codeString = func->codeString->copy();
954 code = (PSCode *)gmallocn(codeSize, sizeof(PSCode));
955 memcpy(code, func->code, codeSize * sizeof(PSCode));
956 }
957
~PostScriptFunction()958 PostScriptFunction::~PostScriptFunction() {
959 gfree(code);
960 if (codeString) {
961 delete codeString;
962 }
963 }
964
transform(double * in,double * out)965 void PostScriptFunction::transform(double *in, double *out) {
966 double stack[psStackSize];
967 double x;
968 int sp, i;
969
970 // check the cache
971 for (i = 0; i < m; ++i) {
972 if (in[i] != cacheIn[i]) {
973 break;
974 }
975 }
976 if (i == m) {
977 for (i = 0; i < n; ++i) {
978 out[i] = cacheOut[i];
979 }
980 return;
981 }
982
983 for (i = 0; i < m; ++i) {
984 stack[psStackSize - 1 - i] = in[i];
985 }
986 sp = exec(stack, psStackSize - m);
987 // if (sp < psStackSize - n) {
988 // error(errSyntaxWarning, -1,
989 // "Extra values on stack at end of PostScript function");
990 // }
991 if (sp > psStackSize - n) {
992 error(errSyntaxError, -1, "Stack underflow in PostScript function");
993 sp = psStackSize - n;
994 }
995 for (i = 0; i < n; ++i) {
996 x = stack[sp + n - 1 - i];
997 if (x < range[i][0]) {
998 out[i] = range[i][0];
999 } else if (x > range[i][1]) {
1000 out[i] = range[i][1];
1001 } else {
1002 out[i] = x;
1003 }
1004 }
1005
1006 // save current result in the cache
1007 for (i = 0; i < m; ++i) {
1008 cacheIn[i] = in[i];
1009 }
1010 for (i = 0; i < n; ++i) {
1011 cacheOut[i] = out[i];
1012 }
1013 }
1014
parseCode(GList * tokens,int * tokPtr,int * codePtr)1015 GBool PostScriptFunction::parseCode(GList *tokens, int *tokPtr, int *codePtr) {
1016 GString *tok;
1017 char *p;
1018 int a, b, mid, cmp;
1019 int codePtr0, codePtr1;
1020
1021 while (1) {
1022 if (*tokPtr >= tokens->getLength()) {
1023 error(errSyntaxError, -1,
1024 "Unexpected end of PostScript function stream");
1025 return gFalse;
1026 }
1027 tok = (GString *)tokens->get((*tokPtr)++);
1028 p = tok->getCString();
1029 if (isdigit(*p) || *p == '.' || *p == '-') {
1030 addCodeD(codePtr, psOpPush, atof(tok->getCString()));
1031 } else if (!tok->cmp("{")) {
1032 codePtr0 = *codePtr;
1033 addCodeI(codePtr, psOpJz, 0);
1034 if (!parseCode(tokens, tokPtr, codePtr)) {
1035 return gFalse;
1036 }
1037 if (*tokPtr >= tokens->getLength()) {
1038 error(errSyntaxError, -1,
1039 "Unexpected end of PostScript function stream");
1040 return gFalse;
1041 }
1042 tok = (GString *)tokens->get((*tokPtr)++);
1043 if (!tok->cmp("if")) {
1044 code[codePtr0].val.i = *codePtr;
1045 } else if (!tok->cmp("{")) {
1046 codePtr1 = *codePtr;
1047 addCodeI(codePtr, psOpJ, 0);
1048 code[codePtr0].val.i = *codePtr;
1049 if (!parseCode(tokens, tokPtr, codePtr)) {
1050 return gFalse;
1051 }
1052 if (*tokPtr >= tokens->getLength()) {
1053 error(errSyntaxError, -1,
1054 "Unexpected end of PostScript function stream");
1055 return gFalse;
1056 }
1057 tok = (GString *)tokens->get((*tokPtr)++);
1058 if (!tok->cmp("ifelse")) {
1059 code[codePtr1].val.i = *codePtr;
1060 } else {
1061 error(errSyntaxError, -1,
1062 "Expected 'ifelse' in PostScript function stream");
1063 return gFalse;
1064 }
1065 } else {
1066 error(errSyntaxError, -1,
1067 "Expected 'if' in PostScript function stream");
1068 return gFalse;
1069 }
1070 } else if (!tok->cmp("}")) {
1071 break;
1072 } else if (!tok->cmp("if")) {
1073 error(errSyntaxError, -1,
1074 "Unexpected 'if' in PostScript function stream");
1075 return gFalse;
1076 } else if (!tok->cmp("ifelse")) {
1077 error(errSyntaxError, -1,
1078 "Unexpected 'ifelse' in PostScript function stream");
1079 return gFalse;
1080 } else {
1081 a = -1;
1082 b = nPSOps;
1083 cmp = 0; // make gcc happy
1084 // invariant: psOpNames[a] < tok < psOpNames[b]
1085 while (b - a > 1) {
1086 mid = (a + b) / 2;
1087 cmp = tok->cmp(psOpNames[mid]);
1088 if (cmp > 0) {
1089 a = mid;
1090 } else if (cmp < 0) {
1091 b = mid;
1092 } else {
1093 a = b = mid;
1094 }
1095 }
1096 if (cmp != 0) {
1097 error(errSyntaxError, -1,
1098 "Unknown operator '{0:t}' in PostScript function",
1099 tok);
1100 return gFalse;
1101 }
1102 addCode(codePtr, a);
1103 }
1104 }
1105 return gTrue;
1106 }
1107
addCode(int * codePtr,int op)1108 void PostScriptFunction::addCode(int *codePtr, int op) {
1109 if (*codePtr >= codeSize) {
1110 if (codeSize) {
1111 codeSize *= 2;
1112 } else {
1113 codeSize = 16;
1114 }
1115 code = (PSCode *)greallocn(code, codeSize, sizeof(PSCode));
1116 }
1117 code[*codePtr].op = op;
1118 ++(*codePtr);
1119 }
1120
addCodeI(int * codePtr,int op,int x)1121 void PostScriptFunction::addCodeI(int *codePtr, int op, int x) {
1122 if (*codePtr >= codeSize) {
1123 if (codeSize) {
1124 codeSize *= 2;
1125 } else {
1126 codeSize = 16;
1127 }
1128 code = (PSCode *)greallocn(code, codeSize, sizeof(PSCode));
1129 }
1130 code[*codePtr].op = op;
1131 code[*codePtr].val.i = x;
1132 ++(*codePtr);
1133 }
1134
addCodeD(int * codePtr,int op,double x)1135 void PostScriptFunction::addCodeD(int *codePtr, int op, double x) {
1136 if (*codePtr >= codeSize) {
1137 if (codeSize) {
1138 codeSize *= 2;
1139 } else {
1140 codeSize = 16;
1141 }
1142 code = (PSCode *)greallocn(code, codeSize, sizeof(PSCode));
1143 }
1144 code[*codePtr].op = op;
1145 code[*codePtr].val.d = x;
1146 ++(*codePtr);
1147 }
1148
getToken(Stream * str)1149 GString *PostScriptFunction::getToken(Stream *str) {
1150 GString *s;
1151 int c;
1152 GBool comment;
1153
1154 s = new GString();
1155 comment = gFalse;
1156 while (1) {
1157 if ((c = str->getChar()) == EOF) {
1158 delete s;
1159 return NULL;
1160 }
1161 codeString->append(c);
1162 if (comment) {
1163 if (c == '\x0a' || c == '\x0d') {
1164 comment = gFalse;
1165 }
1166 } else if (c == '%') {
1167 comment = gTrue;
1168 } else if (!isspace(c)) {
1169 break;
1170 }
1171 }
1172 if (c == '{' || c == '}') {
1173 s->append((char)c);
1174 } else if (isdigit(c) || c == '.' || c == '-') {
1175 while (1) {
1176 s->append((char)c);
1177 c = str->lookChar();
1178 if (c == EOF || !(isdigit(c) || c == '.' || c == '-')) {
1179 break;
1180 }
1181 str->getChar();
1182 codeString->append(c);
1183 }
1184 } else {
1185 while (1) {
1186 s->append((char)c);
1187 c = str->lookChar();
1188 if (c == EOF || !isalnum(c)) {
1189 break;
1190 }
1191 str->getChar();
1192 codeString->append(c);
1193 }
1194 }
1195 return s;
1196 }
1197
exec(double * stack,int sp0)1198 int PostScriptFunction::exec(double *stack, int sp0) {
1199 PSCode *c;
1200 double tmp[psStackSize];
1201 double t;
1202 int sp, ip, nn, k, i;
1203
1204 sp = sp0;
1205 ip = 0;
1206 while (ip < codeLen) {
1207 c = &code[ip++];
1208 switch(c->op) {
1209 case psOpAbs:
1210 if (sp >= psStackSize) {
1211 goto underflow;
1212 }
1213 stack[sp] = fabs(stack[sp]);
1214 break;
1215 case psOpAdd:
1216 if (sp + 1 >= psStackSize) {
1217 goto underflow;
1218 }
1219 stack[sp + 1] = stack[sp + 1] + stack[sp];
1220 ++sp;
1221 break;
1222 case psOpAnd:
1223 if (sp + 1 >= psStackSize) {
1224 goto underflow;
1225 }
1226 stack[sp + 1] = (int)stack[sp + 1] & (int)stack[sp];
1227 ++sp;
1228 break;
1229 case psOpAtan:
1230 if (sp + 1 >= psStackSize) {
1231 goto underflow;
1232 }
1233 stack[sp + 1] = atan2(stack[sp + 1], stack[sp]);
1234 ++sp;
1235 break;
1236 case psOpBitshift:
1237 if (sp + 1 >= psStackSize) {
1238 goto underflow;
1239 }
1240 k = (int)stack[sp + 1];
1241 nn = (int)stack[sp];
1242 if (nn > 0) {
1243 stack[sp + 1] = k << nn;
1244 } else if (nn < 0) {
1245 stack[sp + 1] = k >> -nn;
1246 } else {
1247 stack[sp + 1] = k;
1248 }
1249 ++sp;
1250 break;
1251 case psOpCeiling:
1252 if (sp >= psStackSize) {
1253 goto underflow;
1254 }
1255 stack[sp] = ceil(stack[sp]);
1256 break;
1257 case psOpCopy:
1258 if (sp >= psStackSize) {
1259 goto underflow;
1260 }
1261 nn = (int)stack[sp++];
1262 if (nn < 0) {
1263 goto invalidArg;
1264 }
1265 if (sp + nn > psStackSize) {
1266 goto underflow;
1267 }
1268 if (sp - nn < 0) {
1269 goto overflow;
1270 }
1271 for (i = 0; i < nn; ++i) {
1272 stack[sp - nn + i] = stack[sp + i];
1273 }
1274 sp -= nn;
1275 break;
1276 case psOpCos:
1277 if (sp >= psStackSize) {
1278 goto underflow;
1279 }
1280 stack[sp] = cos(stack[sp]);
1281 break;
1282 case psOpCvi:
1283 if (sp >= psStackSize) {
1284 goto underflow;
1285 }
1286 stack[sp] = (int)stack[sp];
1287 break;
1288 case psOpCvr:
1289 if (sp >= psStackSize) {
1290 goto underflow;
1291 }
1292 break;
1293 case psOpDiv:
1294 if (sp + 1 >= psStackSize) {
1295 goto underflow;
1296 }
1297 stack[sp + 1] = stack[sp + 1] / stack[sp];
1298 ++sp;
1299 break;
1300 case psOpDup:
1301 if (sp >= psStackSize) {
1302 goto underflow;
1303 }
1304 if (sp < 1) {
1305 goto overflow;
1306 }
1307 stack[sp - 1] = stack[sp];
1308 --sp;
1309 break;
1310 case psOpEq:
1311 if (sp + 1 >= psStackSize) {
1312 goto underflow;
1313 }
1314 stack[sp + 1] = stack[sp + 1] == stack[sp] ? 1 : 0;
1315 ++sp;
1316 break;
1317 case psOpExch:
1318 if (sp + 1 >= psStackSize) {
1319 goto underflow;
1320 }
1321 t = stack[sp];
1322 stack[sp] = stack[sp + 1];
1323 stack[sp + 1] = t;
1324 break;
1325 case psOpExp:
1326 if (sp + 1 >= psStackSize) {
1327 goto underflow;
1328 }
1329 stack[sp + 1] = pow(stack[sp + 1], stack[sp]);
1330 ++sp;
1331 break;
1332 case psOpFalse:
1333 if (sp < 1) {
1334 goto overflow;
1335 }
1336 stack[sp - 1] = 0;
1337 --sp;
1338 break;
1339 case psOpFloor:
1340 if (sp >= psStackSize) {
1341 goto underflow;
1342 }
1343 stack[sp] = floor(stack[sp]);
1344 break;
1345 case psOpGe:
1346 if (sp + 1 >= psStackSize) {
1347 goto underflow;
1348 }
1349 stack[sp + 1] = stack[sp + 1] >= stack[sp] ? 1 : 0;
1350 ++sp;
1351 break;
1352 case psOpGt:
1353 if (sp + 1 >= psStackSize) {
1354 goto underflow;
1355 }
1356 stack[sp + 1] = stack[sp + 1] > stack[sp] ? 1 : 0;
1357 ++sp;
1358 break;
1359 case psOpIdiv:
1360 if (sp + 1 >= psStackSize) {
1361 goto underflow;
1362 }
1363 stack[sp + 1] = (int)stack[sp + 1] / (int)stack[sp];
1364 ++sp;
1365 break;
1366 case psOpIndex:
1367 if (sp >= psStackSize) {
1368 goto underflow;
1369 }
1370 k = (int)stack[sp];
1371 if (k < 0) {
1372 goto invalidArg;
1373 }
1374 if (sp + 1 + k >= psStackSize) {
1375 goto underflow;
1376 }
1377 stack[sp] = stack[sp + 1 + k];
1378 break;
1379 case psOpLe:
1380 if (sp + 1 >= psStackSize) {
1381 goto underflow;
1382 }
1383 stack[sp + 1] = stack[sp + 1] <= stack[sp] ? 1 : 0;
1384 ++sp;
1385 break;
1386 case psOpLn:
1387 if (sp >= psStackSize) {
1388 goto underflow;
1389 }
1390 stack[sp] = log(stack[sp]);
1391 break;
1392 case psOpLog:
1393 if (sp >= psStackSize) {
1394 goto underflow;
1395 }
1396 stack[sp] = log10(stack[sp]);
1397 break;
1398 case psOpLt:
1399 if (sp + 1 >= psStackSize) {
1400 goto underflow;
1401 }
1402 stack[sp + 1] = stack[sp + 1] < stack[sp] ? 1 : 0;
1403 ++sp;
1404 break;
1405 case psOpMod:
1406 if (sp + 1 >= psStackSize) {
1407 goto underflow;
1408 }
1409 stack[sp + 1] = (int)stack[sp + 1] % (int)stack[sp];
1410 ++sp;
1411 break;
1412 case psOpMul:
1413 if (sp + 1 >= psStackSize) {
1414 goto underflow;
1415 }
1416 stack[sp + 1] = stack[sp + 1] * stack[sp];
1417 ++sp;
1418 break;
1419 case psOpNe:
1420 if (sp + 1 >= psStackSize) {
1421 goto underflow;
1422 }
1423 stack[sp + 1] = stack[sp + 1] != stack[sp] ? 1 : 0;
1424 ++sp;
1425 break;
1426 case psOpNeg:
1427 if (sp >= psStackSize) {
1428 goto underflow;
1429 }
1430 stack[sp] = -stack[sp];
1431 break;
1432 case psOpNot:
1433 if (sp >= psStackSize) {
1434 goto underflow;
1435 }
1436 stack[sp] = stack[sp] == 0 ? 1 : 0;
1437 break;
1438 case psOpOr:
1439 if (sp + 1 >= psStackSize) {
1440 goto underflow;
1441 }
1442 stack[sp + 1] = (int)stack[sp + 1] | (int)stack[sp];
1443 ++sp;
1444 break;
1445 case psOpPop:
1446 if (sp >= psStackSize) {
1447 goto underflow;
1448 }
1449 ++sp;
1450 break;
1451 case psOpRoll:
1452 if (sp + 1 >= psStackSize) {
1453 goto underflow;
1454 }
1455 k = (int)stack[sp++];
1456 nn = (int)stack[sp++];
1457 if (nn < 0) {
1458 goto invalidArg;
1459 }
1460 if (sp + nn > psStackSize) {
1461 goto underflow;
1462 }
1463 if (k >= 0) {
1464 k %= nn;
1465 } else {
1466 k = -k % nn;
1467 if (k) {
1468 k = nn - k;
1469 }
1470 }
1471 for (i = 0; i < nn; ++i) {
1472 tmp[i] = stack[sp + i];
1473 }
1474 for (i = 0; i < nn; ++i) {
1475 stack[sp + i] = tmp[(i + k) % nn];
1476 }
1477 break;
1478 case psOpRound:
1479 if (sp >= psStackSize) {
1480 goto underflow;
1481 }
1482 t = stack[sp];
1483 stack[sp] = (t >= 0) ? floor(t + 0.5) : ceil(t - 0.5);
1484 break;
1485 case psOpSin:
1486 if (sp >= psStackSize) {
1487 goto underflow;
1488 }
1489 stack[sp] = sin(stack[sp]);
1490 break;
1491 case psOpSqrt:
1492 if (sp >= psStackSize) {
1493 goto underflow;
1494 }
1495 stack[sp] = sqrt(stack[sp]);
1496 break;
1497 case psOpSub:
1498 if (sp + 1 >= psStackSize) {
1499 goto underflow;
1500 }
1501 stack[sp + 1] = stack[sp + 1] - stack[sp];
1502 ++sp;
1503 break;
1504 case psOpTrue:
1505 if (sp < 1) {
1506 goto overflow;
1507 }
1508 stack[sp - 1] = 1;
1509 --sp;
1510 break;
1511 case psOpTruncate:
1512 if (sp >= psStackSize) {
1513 goto underflow;
1514 }
1515 t = stack[sp];
1516 stack[sp] = (t >= 0) ? floor(t) : ceil(t);
1517 break;
1518 case psOpXor:
1519 if (sp + 1 >= psStackSize) {
1520 goto underflow;
1521 }
1522 stack[sp + 1] = (int)stack[sp + 1] ^ (int)stack[sp];
1523 ++sp;
1524 break;
1525 case psOpPush:
1526 if (sp < 1) {
1527 goto overflow;
1528 }
1529 stack[--sp] = c->val.d;
1530 break;
1531 case psOpJ:
1532 ip = c->val.i;
1533 break;
1534 case psOpJz:
1535 if (sp >= psStackSize) {
1536 goto underflow;
1537 }
1538 k = (int)stack[sp++];
1539 if (k == 0) {
1540 ip = c->val.i;
1541 }
1542 break;
1543 }
1544 }
1545 return sp;
1546
1547 underflow:
1548 error(errSyntaxError, -1, "Stack underflow in PostScript function");
1549 return sp;
1550 overflow:
1551 error(errSyntaxError, -1, "Stack overflow in PostScript function");
1552 return sp;
1553 invalidArg:
1554 error(errSyntaxError, -1, "Invalid arg in PostScript function");
1555 return sp;
1556 }
1557