pdf/xpdf/Function.cc

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