Back to index

tetex-bin  3.0
Function.cc
Go to the documentation of this file.
00001 //========================================================================
00002 //
00003 // Function.cc
00004 //
00005 // Copyright 2001-2003 Glyph & Cog, LLC
00006 //
00007 //========================================================================
00008 
00009 #include <aconf.h>
00010 
00011 #ifdef USE_GCC_PRAGMAS
00012 #pragma implementation
00013 #endif
00014 
00015 #include <stdlib.h>
00016 #include <string.h>
00017 #include <ctype.h>
00018 #include <math.h>
00019 #include "gmem.h"
00020 #include "Object.h"
00021 #include "Dict.h"
00022 #include "Stream.h"
00023 #include "Error.h"
00024 #include "Function.h"
00025 
00026 //------------------------------------------------------------------------
00027 // Function
00028 //------------------------------------------------------------------------
00029 
00030 Function::Function() {
00031 }
00032 
00033 Function::~Function() {
00034 }
00035 
00036 Function *Function::parse(Object *funcObj) {
00037   Function *func;
00038   Dict *dict;
00039   int funcType;
00040   Object obj1;
00041 
00042   if (funcObj->isStream()) {
00043     dict = funcObj->streamGetDict();
00044   } else if (funcObj->isDict()) {
00045     dict = funcObj->getDict();
00046   } else if (funcObj->isName("Identity")) {
00047     return new IdentityFunction();
00048   } else {
00049     error(-1, "Expected function dictionary or stream");
00050     return NULL;
00051   }
00052 
00053   if (!dict->lookup("FunctionType", &obj1)->isInt()) {
00054     error(-1, "Function type is missing or wrong type");
00055     obj1.free();
00056     return NULL;
00057   }
00058   funcType = obj1.getInt();
00059   obj1.free();
00060 
00061   if (funcType == 0) {
00062     func = new SampledFunction(funcObj, dict);
00063   } else if (funcType == 2) {
00064     func = new ExponentialFunction(funcObj, dict);
00065   } else if (funcType == 3) {
00066     func = new StitchingFunction(funcObj, dict);
00067   } else if (funcType == 4) {
00068     func = new PostScriptFunction(funcObj, dict);
00069   } else {
00070     error(-1, "Unimplemented function type (%d)", funcType);
00071     return NULL;
00072   }
00073   if (!func->isOk()) {
00074     delete func;
00075     return NULL;
00076   }
00077 
00078   return func;
00079 }
00080 
00081 GBool Function::init(Dict *dict) {
00082   Object obj1, obj2;
00083   int i;
00084 
00085   //----- Domain
00086   if (!dict->lookup("Domain", &obj1)->isArray()) {
00087     error(-1, "Function is missing domain");
00088     goto err2;
00089   }
00090   m = obj1.arrayGetLength() / 2;
00091   if (m > funcMaxInputs) {
00092     error(-1, "Functions with more than %d inputs are unsupported",
00093          funcMaxInputs);
00094     goto err2;
00095   }
00096   for (i = 0; i < m; ++i) {
00097     obj1.arrayGet(2*i, &obj2);
00098     if (!obj2.isNum()) {
00099       error(-1, "Illegal value in function domain array");
00100       goto err1;
00101     }
00102     domain[i][0] = obj2.getNum();
00103     obj2.free();
00104     obj1.arrayGet(2*i+1, &obj2);
00105     if (!obj2.isNum()) {
00106       error(-1, "Illegal value in function domain array");
00107       goto err1;
00108     }
00109     domain[i][1] = obj2.getNum();
00110     obj2.free();
00111   }
00112   obj1.free();
00113 
00114   //----- Range
00115   hasRange = gFalse;
00116   n = 0;
00117   if (dict->lookup("Range", &obj1)->isArray()) {
00118     hasRange = gTrue;
00119     n = obj1.arrayGetLength() / 2;
00120     if (n > funcMaxOutputs) {
00121       error(-1, "Functions with more than %d outputs are unsupported",
00122            funcMaxOutputs);
00123       goto err2;
00124     }
00125     for (i = 0; i < n; ++i) {
00126       obj1.arrayGet(2*i, &obj2);
00127       if (!obj2.isNum()) {
00128        error(-1, "Illegal value in function range array");
00129        goto err1;
00130       }
00131       range[i][0] = obj2.getNum();
00132       obj2.free();
00133       obj1.arrayGet(2*i+1, &obj2);
00134       if (!obj2.isNum()) {
00135        error(-1, "Illegal value in function range array");
00136        goto err1;
00137       }
00138       range[i][1] = obj2.getNum();
00139       obj2.free();
00140     }
00141   }
00142   obj1.free();
00143 
00144   return gTrue;
00145 
00146  err1:
00147   obj2.free();
00148  err2:
00149   obj1.free();
00150   return gFalse;
00151 }
00152 
00153 //------------------------------------------------------------------------
00154 // IdentityFunction
00155 //------------------------------------------------------------------------
00156 
00157 IdentityFunction::IdentityFunction() {
00158   int i;
00159 
00160   // fill these in with arbitrary values just in case they get used
00161   // somewhere
00162   m = funcMaxInputs;
00163   n = funcMaxOutputs;
00164   for (i = 0; i < funcMaxInputs; ++i) {
00165     domain[i][0] = 0;
00166     domain[i][1] = 1;
00167   }
00168   hasRange = gFalse;
00169 }
00170 
00171 IdentityFunction::~IdentityFunction() {
00172 }
00173 
00174 void IdentityFunction::transform(double *in, double *out) {
00175   int i;
00176 
00177   for (i = 0; i < funcMaxOutputs; ++i) {
00178     out[i] = in[i];
00179   }
00180 }
00181 
00182 //------------------------------------------------------------------------
00183 // SampledFunction
00184 //------------------------------------------------------------------------
00185 
00186 SampledFunction::SampledFunction(Object *funcObj, Dict *dict) {
00187   Stream *str;
00188   int nSamples, sampleBits;
00189   double sampleMul;
00190   Object obj1, obj2;
00191   Guint buf, bitMask;
00192   int bits;
00193   int s;
00194   int i;
00195 
00196   samples = NULL;
00197   ok = gFalse;
00198 
00199   //----- initialize the generic stuff
00200   if (!init(dict)) {
00201     goto err1;
00202   }
00203   if (!hasRange) {
00204     error(-1, "Type 0 function is missing range");
00205     goto err1;
00206   }
00207 
00208   //----- get the stream
00209   if (!funcObj->isStream()) {
00210     error(-1, "Type 0 function isn't a stream");
00211     goto err1;
00212   }
00213   str = funcObj->getStream();
00214 
00215   //----- Size
00216   if (!dict->lookup("Size", &obj1)->isArray() ||
00217       obj1.arrayGetLength() != m) {
00218     error(-1, "Function has missing or invalid size array");
00219     goto err2;
00220   }
00221   for (i = 0; i < m; ++i) {
00222     obj1.arrayGet(i, &obj2);
00223     if (!obj2.isInt()) {
00224       error(-1, "Illegal value in function size array");
00225       goto err3;
00226     }
00227     sampleSize[i] = obj2.getInt();
00228     obj2.free();
00229   }
00230   obj1.free();
00231 
00232   //----- BitsPerSample
00233   if (!dict->lookup("BitsPerSample", &obj1)->isInt()) {
00234     error(-1, "Function has missing or invalid BitsPerSample");
00235     goto err2;
00236   }
00237   sampleBits = obj1.getInt();
00238   sampleMul = 1.0 / (double)((1 << sampleBits) - 1);
00239   obj1.free();
00240 
00241   //----- Encode
00242   if (dict->lookup("Encode", &obj1)->isArray() &&
00243       obj1.arrayGetLength() == 2*m) {
00244     for (i = 0; i < m; ++i) {
00245       obj1.arrayGet(2*i, &obj2);
00246       if (!obj2.isNum()) {
00247        error(-1, "Illegal value in function encode array");
00248        goto err3;
00249       }
00250       encode[i][0] = obj2.getNum();
00251       obj2.free();
00252       obj1.arrayGet(2*i+1, &obj2);
00253       if (!obj2.isNum()) {
00254        error(-1, "Illegal value in function encode array");
00255        goto err3;
00256       }
00257       encode[i][1] = obj2.getNum();
00258       obj2.free();
00259     }
00260   } else {
00261     for (i = 0; i < m; ++i) {
00262       encode[i][0] = 0;
00263       encode[i][1] = sampleSize[i] - 1;
00264     }
00265   }
00266   obj1.free();
00267 
00268   //----- Decode
00269   if (dict->lookup("Decode", &obj1)->isArray() &&
00270       obj1.arrayGetLength() == 2*n) {
00271     for (i = 0; i < n; ++i) {
00272       obj1.arrayGet(2*i, &obj2);
00273       if (!obj2.isNum()) {
00274        error(-1, "Illegal value in function decode array");
00275        goto err3;
00276       }
00277       decode[i][0] = obj2.getNum();
00278       obj2.free();
00279       obj1.arrayGet(2*i+1, &obj2);
00280       if (!obj2.isNum()) {
00281        error(-1, "Illegal value in function decode array");
00282        goto err3;
00283       }
00284       decode[i][1] = obj2.getNum();
00285       obj2.free();
00286     }
00287   } else {
00288     for (i = 0; i < n; ++i) {
00289       decode[i][0] = range[i][0];
00290       decode[i][1] = range[i][1];
00291     }
00292   }
00293   obj1.free();
00294 
00295   //----- samples
00296   nSamples = n;
00297   for (i = 0; i < m; ++i)
00298     nSamples *= sampleSize[i];
00299   samples = (double *)gmalloc(nSamples * sizeof(double));
00300   buf = 0;
00301   bits = 0;
00302   bitMask = (1 << sampleBits) - 1;
00303   str->reset();
00304   for (i = 0; i < nSamples; ++i) {
00305     if (sampleBits == 8) {
00306       s = str->getChar();
00307     } else if (sampleBits == 16) {
00308       s = str->getChar();
00309       s = (s << 8) + str->getChar();
00310     } else if (sampleBits == 32) {
00311       s = str->getChar();
00312       s = (s << 8) + str->getChar();
00313       s = (s << 8) + str->getChar();
00314       s = (s << 8) + str->getChar();
00315     } else {
00316       while (bits < sampleBits) {
00317        buf = (buf << 8) | (str->getChar() & 0xff);
00318        bits += 8;
00319       }
00320       s = (buf >> (bits - sampleBits)) & bitMask;
00321       bits -= sampleBits;
00322     }
00323     samples[i] = (double)s * sampleMul;
00324   }
00325   str->close();
00326 
00327   ok = gTrue;
00328   return;
00329 
00330  err3:
00331   obj2.free();
00332  err2:
00333   obj1.free();
00334  err1:
00335   return;
00336 }
00337 
00338 SampledFunction::~SampledFunction() {
00339   if (samples) {
00340     gfree(samples);
00341   }
00342 }
00343 
00344 SampledFunction::SampledFunction(SampledFunction *func) {
00345   int nSamples, i;
00346 
00347   memcpy(this, func, sizeof(SampledFunction));
00348 
00349   nSamples = n;
00350   for (i = 0; i < m; ++i) {
00351     nSamples *= sampleSize[i];
00352   }
00353   samples = (double *)gmalloc(nSamples * sizeof(double));
00354   memcpy(samples, func->samples, nSamples * sizeof(double));
00355 }
00356 
00357 void SampledFunction::transform(double *in, double *out) {
00358   double x;
00359   int e[2][funcMaxInputs];
00360   double efrac[funcMaxInputs];
00361   double s0[1 << funcMaxInputs], s1[1 << funcMaxInputs];
00362   int i, j, k, idx;
00363 
00364   // map input values into sample array
00365   for (i = 0; i < m; ++i) {
00366     x = ((in[i] - domain[i][0]) / (domain[i][1] - domain[i][0])) *
00367         (encode[i][1] - encode[i][0]) + encode[i][0];
00368     if (x < 0) {
00369       x = 0;
00370     } else if (x > sampleSize[i] - 1) {
00371       x = sampleSize[i] - 1;
00372     }
00373     e[0][i] = (int)floor(x);
00374     e[1][i] = (int)ceil(x);
00375     efrac[i] = x - e[0][i];
00376   }
00377 
00378   // for each output, do m-linear interpolation
00379   for (i = 0; i < n; ++i) {
00380 
00381     // pull 2^m values out of the sample array
00382     for (j = 0; j < (1<<m); ++j) {
00383       idx = 0;
00384       for (k = m - 1; k >= 0; --k) {
00385        idx = idx * sampleSize[k] + e[(j >> k) & 1][k];
00386       }
00387       idx = idx * n + i;
00388       s0[j] = samples[idx];
00389     }
00390 
00391     // do m sets of interpolations
00392     for (j = 0; j < m; ++j) {
00393       for (k = 0; k < (1 << (m - j)); k += 2) {
00394        s1[k >> 1] = (1 - efrac[j]) * s0[k] + efrac[j] * s0[k+1];
00395       }
00396       memcpy(s0, s1, (1 << (m - j - 1)) * sizeof(double));
00397     }
00398 
00399     // map output value to range
00400     out[i] = s0[0] * (decode[i][1] - decode[i][0]) + decode[i][0];
00401     if (out[i] < range[i][0]) {
00402       out[i] = range[i][0];
00403     } else if (out[i] > range[i][1]) {
00404       out[i] = range[i][1];
00405     }
00406   }
00407 }
00408 
00409 //------------------------------------------------------------------------
00410 // ExponentialFunction
00411 //------------------------------------------------------------------------
00412 
00413 ExponentialFunction::ExponentialFunction(Object *funcObj, Dict *dict) {
00414   Object obj1, obj2;
00415   int i;
00416 
00417   ok = gFalse;
00418 
00419   //----- initialize the generic stuff
00420   if (!init(dict)) {
00421     goto err1;
00422   }
00423   if (m != 1) {
00424     error(-1, "Exponential function with more than one input");
00425     goto err1;
00426   }
00427 
00428   //----- C0
00429   if (dict->lookup("C0", &obj1)->isArray()) {
00430     if (hasRange && obj1.arrayGetLength() != n) {
00431       error(-1, "Function's C0 array is wrong length");
00432       goto err2;
00433     }
00434     n = obj1.arrayGetLength();
00435     for (i = 0; i < n; ++i) {
00436       obj1.arrayGet(i, &obj2);
00437       if (!obj2.isNum()) {
00438        error(-1, "Illegal value in function C0 array");
00439        goto err3;
00440       }
00441       c0[i] = obj2.getNum();
00442       obj2.free();
00443     }
00444   } else {
00445     if (hasRange && n != 1) {
00446       error(-1, "Function's C0 array is wrong length");
00447       goto err2;
00448     }
00449     n = 1;
00450     c0[0] = 0;
00451   }
00452   obj1.free();
00453 
00454   //----- C1
00455   if (dict->lookup("C1", &obj1)->isArray()) {
00456     if (obj1.arrayGetLength() != n) {
00457       error(-1, "Function's C1 array is wrong length");
00458       goto err2;
00459     }
00460     for (i = 0; i < n; ++i) {
00461       obj1.arrayGet(i, &obj2);
00462       if (!obj2.isNum()) {
00463        error(-1, "Illegal value in function C1 array");
00464        goto err3;
00465       }
00466       c1[i] = obj2.getNum();
00467       obj2.free();
00468     }
00469   } else {
00470     if (n != 1) {
00471       error(-1, "Function's C1 array is wrong length");
00472       goto err2;
00473     }
00474     c1[0] = 1;
00475   }
00476   obj1.free();
00477 
00478   //----- N (exponent)
00479   if (!dict->lookup("N", &obj1)->isNum()) {
00480     error(-1, "Function has missing or invalid N");
00481     goto err2;
00482   }
00483   e = obj1.getNum();
00484   obj1.free();
00485 
00486   ok = gTrue;
00487   return;
00488 
00489  err3:
00490   obj2.free();
00491  err2:
00492   obj1.free();
00493  err1:
00494   return;
00495 }
00496 
00497 ExponentialFunction::~ExponentialFunction() {
00498 }
00499 
00500 ExponentialFunction::ExponentialFunction(ExponentialFunction *func) {
00501   memcpy(this, func, sizeof(ExponentialFunction));
00502 }
00503 
00504 void ExponentialFunction::transform(double *in, double *out) {
00505   double x;
00506   int i;
00507 
00508   if (in[0] < domain[0][0]) {
00509     x = domain[0][0];
00510   } else if (in[0] > domain[0][1]) {
00511     x = domain[0][1];
00512   } else {
00513     x = in[0];
00514   }
00515   for (i = 0; i < n; ++i) {
00516     out[i] = c0[i] + pow(x, e) * (c1[i] - c0[i]);
00517     if (hasRange) {
00518       if (out[i] < range[i][0]) {
00519        out[i] = range[i][0];
00520       } else if (out[i] > range[i][1]) {
00521        out[i] = range[i][1];
00522       }
00523     }
00524   }
00525   return;
00526 }
00527 
00528 //------------------------------------------------------------------------
00529 // StitchingFunction
00530 //------------------------------------------------------------------------
00531 
00532 StitchingFunction::StitchingFunction(Object *funcObj, Dict *dict) {
00533   Object obj1, obj2;
00534   int i;
00535 
00536   ok = gFalse;
00537   funcs = NULL;
00538   bounds = NULL;
00539   encode = NULL;
00540 
00541   //----- initialize the generic stuff
00542   if (!init(dict)) {
00543     goto err1;
00544   }
00545   if (m != 1) {
00546     error(-1, "Stitching function with more than one input");
00547     goto err1;
00548   }
00549 
00550   //----- Functions
00551   if (!dict->lookup("Functions", &obj1)->isArray()) {
00552     error(-1, "Missing 'Functions' entry in stitching function");
00553     goto err1;
00554   }
00555   k = obj1.arrayGetLength();
00556   funcs = (Function **)gmalloc(k * sizeof(Function *));
00557   bounds = (double *)gmalloc((k + 1) * sizeof(double));
00558   encode = (double *)gmalloc(2 * k * sizeof(double));
00559   for (i = 0; i < k; ++i) {
00560     funcs[i] = NULL;
00561   }
00562   for (i = 0; i < k; ++i) {
00563     if (!(funcs[i] = Function::parse(obj1.arrayGet(i, &obj2)))) {
00564       goto err2;
00565     }
00566     if (i > 0 && (funcs[i]->getInputSize() != 1 ||
00567                 funcs[i]->getOutputSize() != funcs[0]->getOutputSize())) {
00568       error(-1, "Incompatible subfunctions in stitching function");
00569       goto err2;
00570     }
00571     obj2.free();
00572   }
00573   obj1.free();
00574 
00575   //----- Bounds
00576   if (!dict->lookup("Bounds", &obj1)->isArray() ||
00577       obj1.arrayGetLength() != k - 1) {
00578     error(-1, "Missing or invalid 'Bounds' entry in stitching function");
00579     goto err1;
00580   }
00581   bounds[0] = domain[0][0];
00582   for (i = 1; i < k; ++i) {
00583     if (!obj1.arrayGet(i - 1, &obj2)->isNum()) {
00584       error(-1, "Invalid type in 'Bounds' array in stitching function");
00585       goto err2;
00586     }
00587     bounds[i] = obj2.getNum();
00588     obj2.free();
00589   }
00590   bounds[k] = domain[0][1];
00591   obj1.free();
00592 
00593   //----- Encode
00594   if (!dict->lookup("Encode", &obj1)->isArray() ||
00595       obj1.arrayGetLength() != 2 * k) {
00596     error(-1, "Missing or invalid 'Encode' entry in stitching function");
00597     goto err1;
00598   }
00599   for (i = 0; i < 2 * k; ++i) {
00600     if (!obj1.arrayGet(i, &obj2)->isNum()) {
00601       error(-1, "Invalid type in 'Encode' array in stitching function");
00602       goto err2;
00603     }
00604     encode[i] = obj2.getNum();
00605     obj2.free();
00606   }
00607   obj1.free();
00608 
00609   ok = gTrue;
00610   return;
00611 
00612  err2:
00613   obj2.free();
00614  err1:
00615   obj1.free();
00616 }
00617 
00618 StitchingFunction::StitchingFunction(StitchingFunction *func) {
00619   int i;
00620 
00621   k = func->k;
00622   funcs = (Function **)gmalloc(k * sizeof(Function *));
00623   for (i = 0; i < k; ++i) {
00624     funcs[i] = func->funcs[i]->copy();
00625   }
00626   bounds = (double *)gmalloc((k + 1) * sizeof(double));
00627   memcpy(bounds, func->bounds, (k + 1) * sizeof(double));
00628   encode = (double *)gmalloc(2 * k * sizeof(double));
00629   memcpy(encode, func->encode, 2 * k * sizeof(double));
00630   ok = gTrue;
00631 }
00632 
00633 StitchingFunction::~StitchingFunction() {
00634   int i;
00635 
00636   if (funcs) {
00637     for (i = 0; i < k; ++i) {
00638       if (funcs[i]) {
00639        delete funcs[i];
00640       }
00641     }
00642   }
00643   gfree(funcs);
00644   gfree(bounds);
00645   gfree(encode);
00646 }
00647 
00648 void StitchingFunction::transform(double *in, double *out) {
00649   double x;
00650   int i;
00651 
00652   if (in[0] < domain[0][0]) {
00653     x = domain[0][0];
00654   } else if (in[0] > domain[0][1]) {
00655     x = domain[0][1];
00656   } else {
00657     x = in[0];
00658   }
00659   for (i = 0; i < k - 1; ++i) {
00660     if (x < bounds[i+1]) {
00661       break;
00662     }
00663   }
00664   x = encode[2*i] + ((x - bounds[i]) / (bounds[i+1] - bounds[i])) *
00665                     (encode[2*i+1] - encode[2*i]);
00666   funcs[i]->transform(&x, out);
00667 }
00668 
00669 //------------------------------------------------------------------------
00670 // PostScriptFunction
00671 //------------------------------------------------------------------------
00672 
00673 enum PSOp {
00674   psOpAbs,
00675   psOpAdd,
00676   psOpAnd,
00677   psOpAtan,
00678   psOpBitshift,
00679   psOpCeiling,
00680   psOpCopy,
00681   psOpCos,
00682   psOpCvi,
00683   psOpCvr,
00684   psOpDiv,
00685   psOpDup,
00686   psOpEq,
00687   psOpExch,
00688   psOpExp,
00689   psOpFalse,
00690   psOpFloor,
00691   psOpGe,
00692   psOpGt,
00693   psOpIdiv,
00694   psOpIndex,
00695   psOpLe,
00696   psOpLn,
00697   psOpLog,
00698   psOpLt,
00699   psOpMod,
00700   psOpMul,
00701   psOpNe,
00702   psOpNeg,
00703   psOpNot,
00704   psOpOr,
00705   psOpPop,
00706   psOpRoll,
00707   psOpRound,
00708   psOpSin,
00709   psOpSqrt,
00710   psOpSub,
00711   psOpTrue,
00712   psOpTruncate,
00713   psOpXor,
00714   psOpIf,
00715   psOpIfelse,
00716   psOpReturn
00717 };
00718 
00719 // Note: 'if' and 'ifelse' are parsed separately.
00720 // The rest are listed here in alphabetical order.
00721 // The index in this table is equivalent to the entry in PSOp.
00722 char *psOpNames[] = {
00723   "abs",
00724   "add",
00725   "and",
00726   "atan",
00727   "bitshift",
00728   "ceiling",
00729   "copy",
00730   "cos",
00731   "cvi",
00732   "cvr",
00733   "div",
00734   "dup",
00735   "eq",
00736   "exch",
00737   "exp",
00738   "false",
00739   "floor",
00740   "ge",
00741   "gt",
00742   "idiv",
00743   "index",
00744   "le",
00745   "ln",
00746   "log",
00747   "lt",
00748   "mod",
00749   "mul",
00750   "ne",
00751   "neg",
00752   "not",
00753   "or",
00754   "pop",
00755   "roll",
00756   "round",
00757   "sin",
00758   "sqrt",
00759   "sub",
00760   "true",
00761   "truncate",
00762   "xor"
00763 };
00764 
00765 #define nPSOps (sizeof(psOpNames) / sizeof(char *))
00766 
00767 enum PSObjectType {
00768   psBool,
00769   psInt,
00770   psReal,
00771   psOperator,
00772   psBlock
00773 };
00774 
00775 // In the code array, 'if'/'ifelse' operators take up three slots
00776 // plus space for the code in the subclause(s).
00777 //
00778 //         +---------------------------------+
00779 //         | psOperator: psOpIf / psOpIfelse |
00780 //         +---------------------------------+
00781 //         | psBlock: ptr=<A>                |
00782 //         +---------------------------------+
00783 //         | psBlock: ptr=<B>                |
00784 //         +---------------------------------+
00785 //         | if clause                       |
00786 //         | ...                             |
00787 //         | psOperator: psOpReturn          |
00788 //         +---------------------------------+
00789 //     <A> | else clause                     |
00790 //         | ...                             |
00791 //         | psOperator: psOpReturn          |
00792 //         +---------------------------------+
00793 //     <B> | ...                             |
00794 //
00795 // For 'if', pointer <A> is present in the code stream but unused.
00796 
00797 struct PSObject {
00798   PSObjectType type;
00799   union {
00800     GBool booln;            // boolean (stack only)
00801     int intg;               // integer (stack and code)
00802     double real;            // real (stack and code)
00803     PSOp op;                // operator (code only)
00804     int blk;                // if/ifelse block pointer (code only)
00805   };
00806 };
00807 
00808 #define psStackSize 100
00809 
00810 class PSStack {
00811 public:
00812 
00813   PSStack() { sp = psStackSize; }
00814   void pushBool(GBool booln);
00815   void pushInt(int intg);
00816   void pushReal(double real);
00817   GBool popBool();
00818   int popInt();
00819   double popNum();
00820   GBool empty() { return sp == psStackSize; }
00821   GBool topIsInt() { return sp < psStackSize && stack[sp].type == psInt; }
00822   GBool topTwoAreInts()
00823     { return sp < psStackSize - 1 &&
00824             stack[sp].type == psInt &&
00825              stack[sp+1].type == psInt; }
00826   GBool topIsReal() { return sp < psStackSize && stack[sp].type == psReal; }
00827   GBool topTwoAreNums()
00828     { return sp < psStackSize - 1 &&
00829             (stack[sp].type == psInt || stack[sp].type == psReal) &&
00830             (stack[sp+1].type == psInt || stack[sp+1].type == psReal); }
00831   void copy(int n);
00832   void roll(int n, int j);
00833   void index(int i);
00834   void pop();
00835 
00836 private:
00837 
00838   GBool checkOverflow(int n = 1);
00839   GBool checkUnderflow();
00840   GBool checkType(PSObjectType t1, PSObjectType t2);
00841 
00842   PSObject stack[psStackSize];
00843   int sp;
00844 };
00845 
00846 GBool PSStack::checkOverflow(int n) {
00847   if (sp - n < 0) {
00848     error(-1, "Stack overflow in PostScript function");
00849     return gFalse;
00850   }
00851   return gTrue;
00852 }
00853 
00854 GBool PSStack::checkUnderflow() {
00855   if (sp == psStackSize) {
00856     error(-1, "Stack underflow in PostScript function");
00857     return gFalse;
00858   }
00859   return gTrue;
00860 }
00861 
00862 GBool PSStack::checkType(PSObjectType t1, PSObjectType t2) {
00863   if (stack[sp].type != t1 && stack[sp].type != t2) {
00864     error(-1, "Type mismatch in PostScript function");
00865     return gFalse;
00866   }
00867   return gTrue;
00868 }
00869 
00870 void PSStack::pushBool(GBool booln) {
00871   if (checkOverflow()) {
00872     stack[--sp].type = psBool;
00873     stack[sp].booln = booln;
00874   }
00875 }
00876 
00877 void PSStack::pushInt(int intg) {
00878   if (checkOverflow()) {
00879     stack[--sp].type = psInt;
00880     stack[sp].intg = intg;
00881   }
00882 }
00883 
00884 void PSStack::pushReal(double real) {
00885   if (checkOverflow()) {
00886     stack[--sp].type = psReal;
00887     stack[sp].real = real;
00888   }
00889 }
00890 
00891 GBool PSStack::popBool() {
00892   if (checkUnderflow() && checkType(psBool, psBool)) {
00893     return stack[sp++].booln;
00894   }
00895   return gFalse;
00896 }
00897 
00898 int PSStack::popInt() {
00899   if (checkUnderflow() && checkType(psInt, psInt)) {
00900     return stack[sp++].intg;
00901   }
00902   return 0;
00903 }
00904 
00905 double PSStack::popNum() {
00906   double ret;
00907 
00908   if (checkUnderflow() && checkType(psInt, psReal)) {
00909     ret = (stack[sp].type == psInt) ? (double)stack[sp].intg : stack[sp].real;
00910     ++sp;
00911     return ret;
00912   }
00913   return 0;
00914 }
00915 
00916 void PSStack::copy(int n) {
00917   int i;
00918 
00919   if (!checkOverflow(n)) {
00920     return;
00921   }
00922   for (i = sp + n - 1; i <= sp; ++i) {
00923     stack[i - n] = stack[i];
00924   }
00925   sp -= n;
00926 }
00927 
00928 void PSStack::roll(int n, int j) {
00929   PSObject obj;
00930   int i, k;
00931 
00932   if (j >= 0) {
00933     j %= n;
00934   } else {
00935     j = -j % n;
00936     if (j != 0) {
00937       j = n - j;
00938     }
00939   }
00940   if (n <= 0 || j == 0) {
00941     return;
00942   }
00943   for (i = 0; i < j; ++i) {
00944     obj = stack[sp];
00945     for (k = sp; k < sp + n - 1; ++k) {
00946       stack[k] = stack[k+1];
00947     }
00948     stack[sp + n - 1] = obj;
00949   }
00950 }
00951 
00952 void PSStack::index(int i) {
00953   if (!checkOverflow()) {
00954     return;
00955   }
00956   --sp;
00957   stack[sp] = stack[sp + 1 + i];
00958 }
00959 
00960 void PSStack::pop() {
00961   if (!checkUnderflow()) {
00962     return;
00963   }
00964   ++sp;
00965 }
00966 
00967 PostScriptFunction::PostScriptFunction(Object *funcObj, Dict *dict) {
00968   Stream *str;
00969   int codePtr;
00970   GString *tok;
00971 
00972   code = NULL;
00973   codeSize = 0;
00974   ok = gFalse;
00975 
00976   //----- initialize the generic stuff
00977   if (!init(dict)) {
00978     goto err1;
00979   }
00980   if (!hasRange) {
00981     error(-1, "Type 4 function is missing range");
00982     goto err1;
00983   }
00984 
00985   //----- get the stream
00986   if (!funcObj->isStream()) {
00987     error(-1, "Type 4 function isn't a stream");
00988     goto err1;
00989   }
00990   str = funcObj->getStream();
00991 
00992   //----- parse the function
00993   str->reset();
00994   if (!(tok = getToken(str)) || tok->cmp("{")) {
00995     error(-1, "Expected '{' at start of PostScript function");
00996     if (tok) {
00997       delete tok;
00998     }
00999     goto err1;
01000   }
01001   delete tok;
01002   codePtr = 0;
01003   if (!parseCode(str, &codePtr)) {
01004     goto err2;
01005   }
01006   str->close();
01007 
01008   ok = gTrue;
01009 
01010  err2:
01011   str->close();
01012  err1:
01013   return;
01014 }
01015 
01016 PostScriptFunction::PostScriptFunction(PostScriptFunction *func) {
01017   memcpy(this, func, sizeof(PostScriptFunction));
01018   code = (PSObject *)gmalloc(codeSize * sizeof(PSObject));
01019   memcpy(code, func->code, codeSize * sizeof(PSObject));
01020 }
01021 
01022 PostScriptFunction::~PostScriptFunction() {
01023   gfree(code);
01024 }
01025 
01026 void PostScriptFunction::transform(double *in, double *out) {
01027   PSStack *stack;
01028   int i;
01029 
01030   stack = new PSStack();
01031   for (i = 0; i < m; ++i) {
01032     //~ may need to check for integers here
01033     stack->pushReal(in[i]);
01034   }
01035   exec(stack, 0);
01036   for (i = n - 1; i >= 0; --i) {
01037     out[i] = stack->popNum();
01038     if (out[i] < range[i][0]) {
01039       out[i] = range[i][0];
01040     } else if (out[i] > range[i][1]) {
01041       out[i] = range[i][1];
01042     }
01043   }
01044   // if (!stack->empty()) {
01045   //   error(-1, "Extra values on stack at end of PostScript function");
01046   // }
01047   delete stack;
01048 }
01049 
01050 GBool PostScriptFunction::parseCode(Stream *str, int *codePtr) {
01051   GString *tok;
01052   char *p;
01053   GBool isReal;
01054   int opPtr, elsePtr;
01055   int a, b, mid, cmp;
01056 
01057   while (1) {
01058     if (!(tok = getToken(str))) {
01059       error(-1, "Unexpected end of PostScript function stream");
01060       return gFalse;
01061     }
01062     p = tok->getCString();
01063     if (isdigit(*p) || *p == '.' || *p == '-') {
01064       isReal = gFalse;
01065       for (++p; *p; ++p) {
01066        if (*p == '.') {
01067          isReal = gTrue;
01068          break;
01069        }
01070       }
01071       resizeCode(*codePtr);
01072       if (isReal) {
01073        code[*codePtr].type = psReal;
01074        code[*codePtr].real = atof(tok->getCString());
01075       } else {
01076        code[*codePtr].type = psInt;
01077        code[*codePtr].intg = atoi(tok->getCString());
01078       }
01079       ++*codePtr;
01080       delete tok;
01081     } else if (!tok->cmp("{")) {
01082       delete tok;
01083       opPtr = *codePtr;
01084       *codePtr += 3;
01085       resizeCode(opPtr + 2);
01086       if (!parseCode(str, codePtr)) {
01087        return gFalse;
01088       }
01089       if (!(tok = getToken(str))) {
01090        error(-1, "Unexpected end of PostScript function stream");
01091        return gFalse;
01092       }
01093       if (!tok->cmp("{")) {
01094        elsePtr = *codePtr;
01095        if (!parseCode(str, codePtr)) {
01096          return gFalse;
01097        }
01098        delete tok;
01099        if (!(tok = getToken(str))) {
01100          error(-1, "Unexpected end of PostScript function stream");
01101          return gFalse;
01102        }
01103       } else {
01104        elsePtr = -1;
01105       }
01106       if (!tok->cmp("if")) {
01107        if (elsePtr >= 0) {
01108          error(-1, "Got 'if' operator with two blocks in PostScript function");
01109          return gFalse;
01110        }
01111        code[opPtr].type = psOperator;
01112        code[opPtr].op = psOpIf;
01113        code[opPtr+2].type = psBlock;
01114        code[opPtr+2].blk = *codePtr;
01115       } else if (!tok->cmp("ifelse")) {
01116        if (elsePtr < 0) {
01117          error(-1, "Got 'ifelse' operator with one blocks in PostScript function");
01118          return gFalse;
01119        }
01120        code[opPtr].type = psOperator;
01121        code[opPtr].op = psOpIfelse;
01122        code[opPtr+1].type = psBlock;
01123        code[opPtr+1].blk = elsePtr;
01124        code[opPtr+2].type = psBlock;
01125        code[opPtr+2].blk = *codePtr;
01126       } else {
01127        error(-1, "Expected if/ifelse operator in PostScript function");
01128        delete tok;
01129        return gFalse;
01130       }
01131       delete tok;
01132     } else if (!tok->cmp("}")) {
01133       delete tok;
01134       resizeCode(*codePtr);
01135       code[*codePtr].type = psOperator;
01136       code[*codePtr].op = psOpReturn;
01137       ++*codePtr;
01138       break;
01139     } else {
01140       a = -1;
01141       b = nPSOps;
01142       // invariant: psOpNames[a] < tok < psOpNames[b]
01143       while (b - a > 1) {
01144        mid = (a + b) / 2;
01145        cmp = tok->cmp(psOpNames[mid]);
01146        if (cmp > 0) {
01147          a = mid;
01148        } else if (cmp < 0) {
01149          b = mid;
01150        } else {
01151          a = b = mid;
01152        }
01153       }
01154       if (cmp != 0) {
01155        error(-1, "Unknown operator '%s' in PostScript function",
01156              tok->getCString());
01157        delete tok;
01158        return gFalse;
01159       }
01160       delete tok;
01161       resizeCode(*codePtr);
01162       code[*codePtr].type = psOperator;
01163       code[*codePtr].op = (PSOp)a;
01164       ++*codePtr;
01165     }
01166   }
01167   return gTrue;
01168 }
01169 
01170 GString *PostScriptFunction::getToken(Stream *str) {
01171   GString *s;
01172   int c;
01173 
01174   s = new GString();
01175   do {
01176     c = str->getChar();
01177   } while (c != EOF && isspace(c));
01178   if (c == '{' || c == '}') {
01179     s->append((char)c);
01180   } else if (isdigit(c) || c == '.' || c == '-') {
01181     while (1) {
01182       s->append((char)c);
01183       c = str->lookChar();
01184       if (c == EOF || !(isdigit(c) || c == '.' || c == '-')) {
01185        break;
01186       }
01187       str->getChar();
01188     }
01189   } else {
01190     while (1) {
01191       s->append((char)c);
01192       c = str->lookChar();
01193       if (c == EOF || !isalnum(c)) {
01194        break;
01195       }
01196       str->getChar();
01197     }
01198   }
01199   return s;
01200 }
01201 
01202 void PostScriptFunction::resizeCode(int newSize) {
01203   if (newSize >= codeSize) {
01204     codeSize += 64;
01205     code = (PSObject *)grealloc(code, codeSize * sizeof(PSObject));
01206   }
01207 }
01208 
01209 void PostScriptFunction::exec(PSStack *stack, int codePtr) {
01210   int i1, i2;
01211   double r1, r2;
01212   GBool b1, b2;
01213 
01214   while (1) {
01215     switch (code[codePtr].type) {
01216     case psInt:
01217       stack->pushInt(code[codePtr++].intg);
01218       break;
01219     case psReal:
01220       stack->pushReal(code[codePtr++].real);
01221       break;
01222     case psOperator:
01223       switch (code[codePtr++].op) {
01224       case psOpAbs:
01225        if (stack->topIsInt()) {
01226          stack->pushInt(abs(stack->popInt()));
01227        } else {
01228          stack->pushReal(fabs(stack->popNum()));
01229        }
01230        break;
01231       case psOpAdd:
01232        if (stack->topTwoAreInts()) {
01233          i2 = stack->popInt();
01234          i1 = stack->popInt();
01235          stack->pushInt(i1 + i2);
01236        } else {
01237          r2 = stack->popNum();
01238          r1 = stack->popNum();
01239          stack->pushReal(r1 + r2);
01240        }
01241        break;
01242       case psOpAnd:
01243        if (stack->topTwoAreInts()) {
01244          i2 = stack->popInt();
01245          i1 = stack->popInt();
01246          stack->pushInt(i1 & i2);
01247        } else {
01248          b2 = stack->popBool();
01249          b1 = stack->popBool();
01250          stack->pushBool(b1 && b2);
01251        }
01252        break;
01253       case psOpAtan:
01254        r2 = stack->popNum();
01255        r1 = stack->popNum();
01256        stack->pushReal(atan2(r1, r2));
01257        break;
01258       case psOpBitshift:
01259        i2 = stack->popInt();
01260        i1 = stack->popInt();
01261        if (i2 > 0) {
01262          stack->pushInt(i1 << i2);
01263        } else if (i2 < 0) {
01264          stack->pushInt((int)((Guint)i1 >> i2));
01265        } else {
01266          stack->pushInt(i1);
01267        }
01268        break;
01269       case psOpCeiling:
01270        if (!stack->topIsInt()) {
01271          stack->pushReal(ceil(stack->popNum()));
01272        }
01273        break;
01274       case psOpCopy:
01275        stack->copy(stack->popInt());
01276        break;
01277       case psOpCos:
01278        stack->pushReal(cos(stack->popNum()));
01279        break;
01280       case psOpCvi:
01281        if (!stack->topIsInt()) {
01282          stack->pushInt((int)stack->popNum());
01283        }
01284        break;
01285       case psOpCvr:
01286        if (!stack->topIsReal()) {
01287          stack->pushReal(stack->popNum());
01288        }
01289        break;
01290       case psOpDiv:
01291        r2 = stack->popNum();
01292        r1 = stack->popNum();
01293        stack->pushReal(r1 / r2);
01294        break;
01295       case psOpDup:
01296        stack->copy(1);
01297        break;
01298       case psOpEq:
01299        if (stack->topTwoAreInts()) {
01300          i2 = stack->popInt();
01301          i1 = stack->popInt();
01302          stack->pushBool(i1 == i2);
01303        } else if (stack->topTwoAreNums()) {
01304          r2 = stack->popNum();
01305          r1 = stack->popNum();
01306          stack->pushBool(r1 == r2);
01307        } else {
01308          b2 = stack->popBool();
01309          b1 = stack->popBool();
01310          stack->pushBool(b1 == b2);
01311        }
01312        break;
01313       case psOpExch:
01314        stack->roll(2, 1);
01315        break;
01316       case psOpExp:
01317        r2 = stack->popNum();
01318        r1 = stack->popNum();
01319        stack->pushReal(pow(r1, r2));
01320        break;
01321       case psOpFalse:
01322        stack->pushBool(gFalse);
01323        break;
01324       case psOpFloor:
01325        if (!stack->topIsInt()) {
01326          stack->pushReal(floor(stack->popNum()));
01327        }
01328        break;
01329       case psOpGe:
01330        if (stack->topTwoAreInts()) {
01331          i2 = stack->popInt();
01332          i1 = stack->popInt();
01333          stack->pushBool(i1 >= i2);
01334        } else {
01335          r2 = stack->popNum();
01336          r1 = stack->popNum();
01337          stack->pushBool(r1 >= r2);
01338        }
01339        break;
01340       case psOpGt:
01341        if (stack->topTwoAreInts()) {
01342          i2 = stack->popInt();
01343          i1 = stack->popInt();
01344          stack->pushBool(i1 > i2);
01345        } else {
01346          r2 = stack->popNum();
01347          r1 = stack->popNum();
01348          stack->pushBool(r1 > r2);
01349        }
01350        break;
01351       case psOpIdiv:
01352        i2 = stack->popInt();
01353        i1 = stack->popInt();
01354        stack->pushInt(i1 / i2);
01355        break;
01356       case psOpIndex:
01357        stack->index(stack->popInt());
01358        break;
01359       case psOpLe:
01360        if (stack->topTwoAreInts()) {
01361          i2 = stack->popInt();
01362          i1 = stack->popInt();
01363          stack->pushBool(i1 <= i2);
01364        } else {
01365          r2 = stack->popNum();
01366          r1 = stack->popNum();
01367          stack->pushBool(r1 <= r2);
01368        }
01369        break;
01370       case psOpLn:
01371        stack->pushReal(log(stack->popNum()));
01372        break;
01373       case psOpLog:
01374        stack->pushReal(log10(stack->popNum()));
01375        break;
01376       case psOpLt:
01377        if (stack->topTwoAreInts()) {
01378          i2 = stack->popInt();
01379          i1 = stack->popInt();
01380          stack->pushBool(i1 < i2);
01381        } else {
01382          r2 = stack->popNum();
01383          r1 = stack->popNum();
01384          stack->pushBool(r1 < r2);
01385        }
01386        break;
01387       case psOpMod:
01388        i2 = stack->popInt();
01389        i1 = stack->popInt();
01390        stack->pushInt(i1 % i2);
01391        break;
01392       case psOpMul:
01393        if (stack->topTwoAreInts()) {
01394          i2 = stack->popInt();
01395          i1 = stack->popInt();
01396          //~ should check for out-of-range, and push a real instead
01397          stack->pushInt(i1 * i2);
01398        } else {
01399          r2 = stack->popNum();
01400          r1 = stack->popNum();
01401          stack->pushReal(r1 * r2);
01402        }
01403        break;
01404       case psOpNe:
01405        if (stack->topTwoAreInts()) {
01406          i2 = stack->popInt();
01407          i1 = stack->popInt();
01408          stack->pushBool(i1 != i2);
01409        } else if (stack->topTwoAreNums()) {
01410          r2 = stack->popNum();
01411          r1 = stack->popNum();
01412          stack->pushBool(r1 != r2);
01413        } else {
01414          b2 = stack->popBool();
01415          b1 = stack->popBool();
01416          stack->pushBool(b1 != b2);
01417        }
01418        break;
01419       case psOpNeg:
01420        if (stack->topIsInt()) {
01421          stack->pushInt(-stack->popInt());
01422        } else {
01423          stack->pushReal(-stack->popNum());
01424        }
01425        break;
01426       case psOpNot:
01427        if (stack->topIsInt()) {
01428          stack->pushInt(~stack->popInt());
01429        } else {
01430          stack->pushBool(!stack->popBool());
01431        }
01432        break;
01433       case psOpOr:
01434        if (stack->topTwoAreInts()) {
01435          i2 = stack->popInt();
01436          i1 = stack->popInt();
01437          stack->pushInt(i1 | i2);
01438        } else {
01439          b2 = stack->popBool();
01440          b1 = stack->popBool();
01441          stack->pushBool(b1 || b2);
01442        }
01443        break;
01444       case psOpPop:
01445        stack->pop();
01446        break;
01447       case psOpRoll:
01448        i2 = stack->popInt();
01449        i1 = stack->popInt();
01450        stack->roll(i1, i2);
01451        break;
01452       case psOpRound:
01453        if (!stack->topIsInt()) {
01454          r1 = stack->popNum();
01455          stack->pushReal((r1 >= 0) ? floor(r1 + 0.5) : ceil(r1 - 0.5));
01456        }
01457        break;
01458       case psOpSin:
01459        stack->pushReal(sin(stack->popNum()));
01460        break;
01461       case psOpSqrt:
01462        stack->pushReal(sqrt(stack->popNum()));
01463        break;
01464       case psOpSub:
01465        if (stack->topTwoAreInts()) {
01466          i2 = stack->popInt();
01467          i1 = stack->popInt();
01468          stack->pushInt(i1 - i2);
01469        } else {
01470          r2 = stack->popNum();
01471          r1 = stack->popNum();
01472          stack->pushReal(r1 - r2);
01473        }
01474        break;
01475       case psOpTrue:
01476        stack->pushBool(gTrue);
01477        break;
01478       case psOpTruncate:
01479        if (!stack->topIsInt()) {
01480          r1 = stack->popNum();
01481          stack->pushReal((r1 >= 0) ? floor(r1) : ceil(r1));
01482        }
01483        break;
01484       case psOpXor:
01485        if (stack->topTwoAreInts()) {
01486          i2 = stack->popInt();
01487          i1 = stack->popInt();
01488          stack->pushInt(i1 ^ i2);
01489        } else {
01490          b2 = stack->popBool();
01491          b1 = stack->popBool();
01492          stack->pushBool(b1 ^ b2);
01493        }
01494        break;
01495       case psOpIf:
01496        b1 = stack->popBool();
01497        if (b1) {
01498          exec(stack, codePtr + 2);
01499        }
01500        codePtr = code[codePtr + 1].blk;
01501        break;
01502       case psOpIfelse:
01503        b1 = stack->popBool();
01504        if (b1) {
01505          exec(stack, codePtr + 2);
01506        } else {
01507          exec(stack, code[codePtr].blk);
01508        }
01509        codePtr = code[codePtr + 1].blk;
01510        break;
01511       case psOpReturn:
01512        return;
01513       }
01514       break;
01515     default:
01516       error(-1, "Internal: bad object in PostScript function code");
01517       break;
01518     }
01519   }
01520 }