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