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 = e[j & 1][m - 1];
 385       for (k = m - 2; 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   k = func->k;
 621   funcs = (Function **)gmalloc(k * sizeof(Function *));
 622   memcpy(funcs, func->funcs, k * sizeof(Function *));
 623   bounds = (double *)gmalloc((k + 1) * sizeof(double));
 624   memcpy(bounds, func->bounds, (k + 1) * sizeof(double));
 625   encode = (double *)gmalloc(2 * k * sizeof(double));
 626   memcpy(encode, func->encode, 2 * k * sizeof(double));
 627   ok = gTrue;
 628 }
 629
 630 StitchingFunction::~StitchingFunction() {
 631   int i;
 632
 633   for (i = 0; i < k; ++i) {
 634     if (funcs[i]) {
 635       delete funcs[i];
 636     }
 637   }
 638   gfree(funcs);
 639   gfree(bounds);
 640   gfree(encode);
 641 }
 642
 643 void StitchingFunction::transform(double *in, double *out) {
 644   double x;
 645   int i;
 646
 647   if (in[0] < domain[0][0]) {
 648     x = domain[0][0];
 649   } else if (in[0] > domain[0][1]) {
 650     x = domain[0][1];
 651   } else {
 652     x = in[0];
 653   }
 654   for (i = 0; i < k - 1; ++i) {
 655     if (x < bounds[i+1]) {
 656       break;
 657     }
 658   }
 659   x = encode[2*i] + ((x - bounds[i]) / (bounds[i+1] - bounds[i])) *
 660                     (encode[2*i+1] - encode[2*i]);
 661   funcs[i]->transform(&x, out);
 662 }
 663
 664 //------------------------------------------------------------------------
 665 // PostScriptFunction
 666 //------------------------------------------------------------------------
 667
 668 enum PSOp {
 669   psOpAbs,
 670   psOpAdd,
 671   psOpAnd,
 672   psOpAtan,
 673   psOpBitshift,
 674   psOpCeiling,
 675   psOpCopy,
 676   psOpCos,
 677   psOpCvi,
 678   psOpCvr,
 679   psOpDiv,
 680   psOpDup,
 681   psOpEq,
 682   psOpExch,
 683   psOpExp,
 684   psOpFalse,
 685   psOpFloor,
 686   psOpGe,
 687   psOpGt,
 688   psOpIdiv,
 689   psOpIndex,
 690   psOpLe,
 691   psOpLn,
 692   psOpLog,
 693   psOpLt,
 694   psOpMod,
 695   psOpMul,
 696   psOpNe,
 697   psOpNeg,
 698   psOpNot,
 699   psOpOr,
 700   psOpPop,
 701   psOpRoll,
 702   psOpRound,
 703   psOpSin,
 704   psOpSqrt,
 705   psOpSub,
 706   psOpTrue,
 707   psOpTruncate,
 708   psOpXor,
 709   psOpIf,
 710   psOpIfelse,
 711   psOpReturn
 712 };
 713
 714 // Note: 'if' and 'ifelse' are parsed separately.
 715 // The rest are listed here in alphabetical order.
 716 // The index in this table is equivalent to the entry in PSOp.
 717 char *psOpNames[] = {
 718   "abs",
 719   "add",
 720   "and",
 721   "atan",
 722   "bitshift",
 723   "ceiling",
 724   "copy",
 725   "cos",
 726   "cvi",
 727   "cvr",
 728   "div",
 729   "dup",
 730   "eq",
 731   "exch",
 732   "exp",
 733   "false",
 734   "floor",
 735   "ge",
 736   "gt",
 737   "idiv",
 738   "index",
 739   "le",
 740   "ln",
 741   "log",
 742   "lt",
 743   "mod",
 744   "mul",
 745   "ne",
 746   "neg",
 747   "not",
 748   "or",
 749   "pop",
 750   "roll",
 751   "round",
 752   "sin",
 753   "sqrt",
 754   "sub",
 755   "true",
 756   "truncate",
 757   "xor"
 758 };
 759
 760 #define nPSOps (sizeof(psOpNames) / sizeof(char *))
 761
 762 enum PSObjectType {
 763   psBool,
 764   psInt,
 765   psReal,
 766   psOperator,
 767   psBlock
 768 };
 769
 770 // In the code array, 'if'/'ifelse' operators take up three slots
 771 // plus space for the code in the subclause(s).
 772 //
 773 //         +---------------------------------+
 774 //         | psOperator: psOpIf / psOpIfelse |
 775 //         +---------------------------------+
 776 //         | psBlock: ptr=<A>                |
 777 //         +---------------------------------+
 778 //         | psBlock: ptr=<B>                |
 779 //         +---------------------------------+
 780 //         | if clause                       |
 781 //         | ...                             |
 782 //         | psOperator: psOpReturn          |
 783 //         +---------------------------------+
 784 //     <A> | else clause                     |
 785 //         | ...                             |
 786 //         | psOperator: psOpReturn          |
 787 //         +---------------------------------+
 788 //     <B> | ...                             |
 789 //
 790 // For 'if', pointer <A> is present in the code stream but unused.
 791
 792 struct PSObject {
 793   PSObjectType type;
 794   union {
 795     GBool booln;                // boolean (stack only)
 796     int intg;                   // integer (stack and code)
 797     double real;                // real (stack and code)
 798     PSOp op;                    // operator (code only)
 799     int blk;                    // if/ifelse block pointer (code only)
 800   };
 801 };
 802
 803 #define psStackSize 100
 804
 805 class PSStack {
 806 public:
 807
 808   PSStack() { sp = psStackSize; }
 809   void pushBool(GBool booln);
 810   void pushInt(int intg);
 811   void pushReal(double real);
 812   GBool popBool();
 813   int popInt();
 814   double popNum();
 815   GBool empty() { return sp == psStackSize; }
 816   GBool topIsInt() { return sp < psStackSize && stack[sp].type == psInt; }
 817   GBool topTwoAreInts()
 818     { return sp < psStackSize - 1 &&
 819              stack[sp].type == psInt &&
 820              stack[sp+1].type == psInt; }
 821   GBool topIsReal() { return sp < psStackSize && stack[sp].type == psReal; }
 822   GBool topTwoAreNums()
 823     { return sp < psStackSize - 1 &&
 824              (stack[sp].type == psInt || stack[sp].type == psReal) &&
 825              (stack[sp+1].type == psInt || stack[sp+1].type == psReal); }
 826   void copy(int n);
 827   void roll(int n, int j);
 828   void index(int i);
 829   void pop();
 830
 831 private:
 832
 833   GBool checkOverflow(int n = 1);
 834   GBool checkUnderflow();
 835   GBool checkType(PSObjectType t1, PSObjectType t2);
 836
 837   PSObject stack[psStackSize];
 838   int sp;
 839 };
 840
 841 GBool PSStack::checkOverflow(int n) {
 842   if (sp - n < 0) {
 843     error(-1, "Stack overflow in PostScript function");
 844     return gFalse;
 845   }
 846   return gTrue;
 847 }
 848
 849 GBool PSStack::checkUnderflow() {
 850   if (sp == psStackSize) {
 851     error(-1, "Stack underflow in PostScript function");
 852     return gFalse;
 853   }
 854   return gTrue;
 855 }
 856
 857 GBool PSStack::checkType(PSObjectType t1, PSObjectType t2) {
 858   if (stack[sp].type != t1 && stack[sp].type != t2) {
 859     error(-1, "Type mismatch in PostScript function");
 860     return gFalse;
 861   }
 862   return gTrue;
 863 }
 864
 865 void PSStack::pushBool(GBool booln) {
 866   if (checkOverflow()) {
 867     stack[--sp].type = psBool;
 868     stack[sp].booln = booln;
 869   }
 870 }
 871
 872 void PSStack::pushInt(int intg) {
 873   if (checkOverflow()) {
 874     stack[--sp].type = psInt;
 875     stack[sp].intg = intg;
 876   }
 877 }
 878
 879 void PSStack::pushReal(double real) {
 880   if (checkOverflow()) {
 881     stack[--sp].type = psReal;
 882     stack[sp].real = real;
 883   }
 884 }
 885
 886 GBool PSStack::popBool() {
 887   if (checkUnderflow() && checkType(psBool, psBool)) {
 888     return stack[sp++].booln;
 889   }
 890   return gFalse;
 891 }
 892
 893 int PSStack::popInt() {
 894   if (checkUnderflow() && checkType(psInt, psInt)) {
 895     return stack[sp++].intg;
 896   }
 897   return 0;
 898 }
 899
 900 double PSStack::popNum() {
 901   double ret;
 902
 903   if (checkUnderflow() && checkType(psInt, psReal)) {
 904     ret = (stack[sp].type == psInt) ? (double)stack[sp].intg : stack[sp].real;
 905     ++sp;
 906     return ret;
 907   }
 908   return 0;
 909 }
 910
 911 void PSStack::copy(int n) {
 912   int i;
 913
 914   if (!checkOverflow(n)) {
 915     return;
 916   }
 917   for (i = sp + n - 1; i <= sp; ++i) {
 918     stack[i - n] = stack[i];
 919   }
 920   sp -= n;
 921 }
 922
 923 void PSStack::roll(int n, int j) {
 924   PSObject obj;
 925   int i, k;
 926
 927   if (j >= 0) {
 928     j %= n;
 929   } else {
 930     j = -j % n;
 931     if (j != 0) {
 932       j = n - j;
 933     }
 934   }
 935   if (n <= 0 || j == 0) {
 936     return;
 937   }
 938   for (i = 0; i < j; ++i) {
 939     obj = stack[sp];
 940     for (k = sp; k < sp + n - 1; ++k) {
 941       stack[k] = stack[k+1];
 942     }
 943     stack[sp + n - 1] = obj;
 944   }
 945 }
 946
 947 void PSStack::index(int i) {
 948   if (!checkOverflow()) {
 949     return;
 950   }
 951   --sp;
 952   stack[sp] = stack[sp + 1 + i];
 953 }
 954
 955 void PSStack::pop() {
 956   if (!checkUnderflow()) {
 957     return;
 958   }
 959   ++sp;
 960 }
 961
 962 PostScriptFunction::PostScriptFunction(Object *funcObj, Dict *dict) {
 963   Stream *str;
 964   int codePtr;
 965   GString *tok;
 966
 967   code = NULL;
 968   codeSize = 0;
 969   ok = gFalse;
 970
 971   //----- initialize the generic stuff
 972   if (!init(dict)) {
 973     goto err1;
 974   }
 975   if (!hasRange) {
 976     error(-1, "Type 4 function is missing range");
 977     goto err1;
 978   }
 979
 980   //----- get the stream
 981   if (!funcObj->isStream()) {
 982     error(-1, "Type 4 function isn't a stream");
 983     goto err1;
 984   }
 985   str = funcObj->getStream();
 986
 987   //----- parse the function
 988   str->reset();
 989   if (!(tok = getToken(str)) || tok->cmp("{")) {
 990     error(-1, "Expected '{' at start of PostScript function");
 991     if (tok) {
 992       delete tok;
 993     }
 994     goto err1;
 995   }
 996   delete tok;
 997   codePtr = 0;
 998   if (!parseCode(str, &codePtr)) {
 999     goto err2;
1000   }
1001   str->close();
1002
1003   ok = gTrue;
1004
1005  err2:
1006   str->close();
1007  err1:
1008   return;
1009 }
1010
1011 PostScriptFunction::PostScriptFunction(PostScriptFunction *func) {
1012   memcpy(this, func, sizeof(PostScriptFunction));
1013   code = (PSObject *)gmalloc(codeSize * sizeof(PSObject));
1014   memcpy(code, func->code, codeSize * sizeof(PSObject));
1015 }
1016
1017 PostScriptFunction::~PostScriptFunction() {
1018   gfree(code);
1019 }
1020
1021 void PostScriptFunction::transform(double *in, double *out) {
1022   PSStack *stack;
1023   int i;
1024
1025   stack = new PSStack();
1026   for (i = 0; i < m; ++i) {
1027     //~ may need to check for integers here
1028     stack->pushReal(in[i]);
1029   }
1030   exec(stack, 0);
1031   for (i = n - 1; i >= 0; --i) {
1032     out[i] = stack->popNum();
1033     if (out[i] < range[i][0]) {
1034       out[i] = range[i][0];
1035     } else if (out[i] > range[i][1]) {
1036       out[i] = range[i][1];
1037     }
1038   }
1039   // if (!stack->empty()) {
1040   //   error(-1, "Extra values on stack at end of PostScript function");
1041   // }
1042   delete stack;
1043 }
1044
1045 GBool PostScriptFunction::parseCode(Stream *str, int *codePtr) {
1046   GString *tok;
1047   char *p;
1048   GBool isReal;
1049   int opPtr, elsePtr;
1050   int a, b, mid, cmp;
1051
1052   while (1) {
1053     if (!(tok = getToken(str))) {
1054       error(-1, "Unexpected end of PostScript function stream");
1055       return gFalse;
1056     }
1057     p = tok->getCString();
1058     if (isdigit(*p) || *p == '.' || *p == '-') {
1059       isReal = gFalse;
1060       for (++p; *p; ++p) {
1061         if (*p == '.') {
1062           isReal = gTrue;
1063           break;
1064         }
1065       }
1066       resizeCode(*codePtr);
1067       if (isReal) {
1068         code[*codePtr].type = psReal;
1069         {
1070           char *theLocale = setlocale(LC_NUMERIC, "C");
1071           code[*codePtr].real = atof(tok->getCString());
1072           setlocale(LC_NUMERIC, theLocale);
1073         }
1074       } else {
1075         code[*codePtr].type = psInt;
1076         code[*codePtr].intg = atoi(tok->getCString());
1077       }
1078       ++*codePtr;
1079       delete tok;
1080     } else if (!tok->cmp("{")) {
1081       delete tok;
1082       opPtr = *codePtr;
1083       *codePtr += 3;
1084       resizeCode(opPtr + 2);
1085       if (!parseCode(str, codePtr)) {
1086         return gFalse;
1087       }
1088       if (!(tok = getToken(str))) {
1089         error(-1, "Unexpected end of PostScript function stream");
1090         return gFalse;
1091       }
1092       if (!tok->cmp("{")) {
1093         elsePtr = *codePtr;
1094         if (!parseCode(str, codePtr)) {
1095           return gFalse;
1096         }
1097         delete tok;
1098         if (!(tok = getToken(str))) {
1099           error(-1, "Unexpected end of PostScript function stream");
1100           return gFalse;
1101         }
1102       } else {
1103         elsePtr = -1;
1104       }
1105       if (!tok->cmp("if")) {
1106         if (elsePtr >= 0) {
1107           error(-1, "Got 'if' operator with two blocks in PostScript function");
1108           return gFalse;
1109         }
1110         code[opPtr].type = psOperator;
1111         code[opPtr].op = psOpIf;
1112         code[opPtr+2].type = psBlock;
1113         code[opPtr+2].blk = *codePtr;
1114       } else if (!tok->cmp("ifelse")) {
1115         if (elsePtr < 0) {
1116           error(-1, "Got 'ifelse' operator with one blocks in PostScript function");
1117           return gFalse;
1118         }
1119         code[opPtr].type = psOperator;
1120         code[opPtr].op = psOpIfelse;
1121         code[opPtr+1].type = psBlock;
1122         code[opPtr+1].blk = elsePtr;
1123         code[opPtr+2].type = psBlock;
1124         code[opPtr+2].blk = *codePtr;
1125       } else {
1126         error(-1, "Expected if/ifelse operator in PostScript function");
1127         delete tok;
1128         return gFalse;
1129       }
1130       delete tok;
1131     } else if (!tok->cmp("}")) {
1132       delete tok;
1133       resizeCode(*codePtr);
1134       code[*codePtr].type = psOperator;
1135       code[*codePtr].op = psOpReturn;
1136       ++*codePtr;
1137       break;
1138     } else {
1139       a = -1;
1140       b = nPSOps;
1141       // invariant: psOpNames[a] < tok < psOpNames[b]
1142       while (b - a > 1) {
1143         mid = (a + b) / 2;
1144         cmp = tok->cmp(psOpNames[mid]);
1145         if (cmp > 0) {
1146           a = mid;
1147         } else if (cmp < 0) {
1148           b = mid;
1149         } else {
1150           a = b = mid;
1151         }
1152       }
1153       if (cmp != 0) {
1154         error(-1, "Unknown operator '%s' in PostScript function",
1155               tok->getCString());
1156         delete tok;
1157         return gFalse;
1158       }
1159       delete tok;
1160       resizeCode(*codePtr);
1161       code[*codePtr].type = psOperator;
1162       code[*codePtr].op = (PSOp)a;
1163       ++*codePtr;
1164     }
1165   }
1166   return gTrue;
1167 }
1168
1169 GString *PostScriptFunction::getToken(Stream *str) {
1170   GString *s;
1171   int c;
1172
1173   s = new GString();
1174   do {
1175     c = str->getChar();
1176   } while (c != EOF && isspace(c));
1177   if (c == '{' || c == '}') {
1178     s->append((char)c);
1179   } else if (isdigit(c) || c == '.' || c == '-') {
1180     while (1) {
1181       s->append((char)c);
1182       c = str->lookChar();
1183       if (c == EOF || !(isdigit(c) || c == '.' || c == '-')) {
1184         break;
1185       }
1186       str->getChar();
1187     }
1188   } else {
1189     while (1) {
1190       s->append((char)c);
1191       c = str->lookChar();
1192       if (c == EOF || !isalnum(c)) {
1193         break;
1194       }
1195       str->getChar();
1196     }
1197   }
1198   return s;
1199 }
1200
1201 void PostScriptFunction::resizeCode(int newSize) {
1202   if (newSize >= codeSize) {
1203     codeSize += 64;
1204     code = (PSObject *)grealloc(code, codeSize * sizeof(PSObject));
1205   }
1206 }
1207
1208 void PostScriptFunction::exec(PSStack *stack, int codePtr) {
1209   int i1, i2;
1210   double r1, r2;
1211   GBool b1, b2;
1212
1213   while (1) {
1214     switch (code[codePtr].type) {
1215     case psInt:
1216       stack->pushInt(code[codePtr++].intg);
1217       break;
1218     case psReal:
1219       stack->pushReal(code[codePtr++].real);
1220       break;
1221     case psOperator:
1222       switch (code[codePtr++].op) {
1223       case psOpAbs:
1224         if (stack->topIsInt()) {
1225           stack->pushInt(abs(stack->popInt()));
1226         } else {
1227           stack->pushReal(fabs(stack->popNum()));
1228         }
1229         break;
1230       case psOpAdd:
1231         if (stack->topTwoAreInts()) {
1232           i2 = stack->popInt();
1233           i1 = stack->popInt();
1234           stack->pushInt(i1 + i2);
1235         } else {
1236           r2 = stack->popNum();
1237           r1 = stack->popNum();
1238           stack->pushReal(r1 + r2);
1239         }
1240         break;
1241       case psOpAnd:
1242         if (stack->topTwoAreInts()) {
1243           i2 = stack->popInt();
1244           i1 = stack->popInt();
1245           stack->pushInt(i1 & i2);
1246         } else {
1247           b2 = stack->popBool();
1248           b1 = stack->popBool();
1249           stack->pushReal(b1 && b2);
1250         }
1251         break;
1252       case psOpAtan:
1253         r2 = stack->popNum();
1254         r1 = stack->popNum();
1255         stack->pushReal(atan2(r1, r2));
1256         break;
1257       case psOpBitshift:
1258         i2 = stack->popInt();
1259         i1 = stack->popInt();
1260         if (i2 > 0) {
1261           stack->pushInt(i1 << i2);
1262         } else if (i2 < 0) {
1263           stack->pushInt((int)((Guint)i1 >> i2));
1264         } else {
1265           stack->pushInt(i1);
1266         }
1267         break;
1268       case psOpCeiling:
1269         if (!stack->topIsInt()) {
1270           stack->pushReal(ceil(stack->popNum()));
1271         }
1272         break;
1273       case psOpCopy:
1274         stack->copy(stack->popInt());
1275         break;
1276       case psOpCos:
1277         stack->pushReal(cos(stack->popNum()));
1278         break;
1279       case psOpCvi:
1280         if (!stack->topIsInt()) {
1281           stack->pushInt((int)stack->popNum());
1282         }
1283         break;
1284       case psOpCvr:
1285         if (!stack->topIsReal()) {
1286           stack->pushReal(stack->popNum());
1287         }
1288         break;
1289       case psOpDiv:
1290         r2 = stack->popNum();
1291         r1 = stack->popNum();
1292         stack->pushReal(r1 / r2);
1293         break;
1294       case psOpDup:
1295         stack->copy(1);
1296         break;
1297       case psOpEq:
1298         if (stack->topTwoAreInts()) {
1299           i2 = stack->popInt();
1300           i1 = stack->popInt();
1301           stack->pushBool(i1 == i2);
1302         } else if (stack->topTwoAreNums()) {
1303           r2 = stack->popNum();
1304           r1 = stack->popNum();
1305           stack->pushBool(r1 == r2);
1306         } else {
1307           b2 = stack->popBool();
1308           b1 = stack->popBool();
1309           stack->pushBool(b1 == b2);
1310         }
1311         break;
1312       case psOpExch:
1313         stack->roll(2, 1);
1314         break;
1315       case psOpExp:
1316         r2 = stack->popInt();
1317         r1 = stack->popInt();
1318         stack->pushReal(pow(r1, r2));
1319         break;
1320       case psOpFalse:
1321         stack->pushBool(gFalse);
1322         break;
1323       case psOpFloor:
1324         if (!stack->topIsInt()) {
1325           stack->pushReal(floor(stack->popNum()));
1326         }
1327         break;
1328       case psOpGe:
1329         if (stack->topTwoAreInts()) {
1330           i2 = stack->popInt();
1331           i1 = stack->popInt();
1332           stack->pushBool(i1 >= i2);
1333         } else {
1334           r2 = stack->popNum();
1335           r1 = stack->popNum();
1336           stack->pushBool(r1 >= r2);
1337         }
1338         break;
1339       case psOpGt:
1340         if (stack->topTwoAreInts()) {
1341           i2 = stack->popInt();
1342           i1 = stack->popInt();
1343           stack->pushBool(i1 > i2);
1344         } else {
1345           r2 = stack->popNum();
1346           r1 = stack->popNum();
1347           stack->pushBool(r1 > r2);
1348         }
1349         break;
1350       case psOpIdiv:
1351         i2 = stack->popInt();
1352         i1 = stack->popInt();
1353         stack->pushInt(i1 / i2);
1354         break;
1355       case psOpIndex:
1356         stack->index(stack->popInt());
1357         break;
1358       case psOpLe:
1359         if (stack->topTwoAreInts()) {
1360           i2 = stack->popInt();
1361           i1 = stack->popInt();
1362           stack->pushBool(i1 <= i2);
1363         } else {
1364           r2 = stack->popNum();
1365           r1 = stack->popNum();
1366           stack->pushBool(r1 <= r2);
1367         }
1368         break;
1369       case psOpLn:
1370         stack->pushReal(log(stack->popNum()));
1371         break;
1372       case psOpLog:
1373         stack->pushReal(log10(stack->popNum()));
1374         break;
1375       case psOpLt:
1376         if (stack->topTwoAreInts()) {
1377           i2 = stack->popInt();
1378           i1 = stack->popInt();
1379           stack->pushBool(i1 < i2);
1380         } else {
1381           r2 = stack->popNum();
1382           r1 = stack->popNum();
1383           stack->pushBool(r1 < r2);
1384         }
1385         break;
1386       case psOpMod:
1387         i2 = stack->popInt();
1388         i1 = stack->popInt();
1389         stack->pushInt(i1 % i2);
1390         break;
1391       case psOpMul:
1392         if (stack->topTwoAreInts()) {
1393           i2 = stack->popInt();
1394           i1 = stack->popInt();
1395           //~ should check for out-of-range, and push a real instead
1396           stack->pushInt(i1 * i2);
1397         } else {
1398           r2 = stack->popNum();
1399           r1 = stack->popNum();
1400           stack->pushReal(r1 * r2);
1401         }
1402         break;
1403       case psOpNe:
1404         if (stack->topTwoAreInts()) {
1405           i2 = stack->popInt();
1406           i1 = stack->popInt();
1407           stack->pushBool(i1 != i2);
1408         } else if (stack->topTwoAreNums()) {
1409           r2 = stack->popNum();
1410           r1 = stack->popNum();
1411           stack->pushBool(r1 != r2);
1412         } else {
1413           b2 = stack->popBool();
1414           b1 = stack->popBool();
1415           stack->pushBool(b1 != b2);
1416         }
1417         break;
1418       case psOpNeg:
1419         if (stack->topIsInt()) {
1420           stack->pushInt(-stack->popInt());
1421         } else {
1422           stack->pushReal(-stack->popNum());
1423         }
1424         break;
1425       case psOpNot:
1426         if (stack->topIsInt()) {
1427           stack->pushInt(~stack->popInt());
1428         } else {
1429           stack->pushReal(!stack->popBool());
1430         }
1431         break;
1432       case psOpOr:
1433         if (stack->topTwoAreInts()) {
1434           i2 = stack->popInt();
1435           i1 = stack->popInt();
1436           stack->pushInt(i1 | i2);
1437         } else {
1438           b2 = stack->popBool();
1439           b1 = stack->popBool();
1440           stack->pushReal(b1 || b2);
1441         }
1442         break;
1443       case psOpPop:
1444         stack->pop();
1445         break;
1446       case psOpRoll:
1447         i2 = stack->popInt();
1448         i1 = stack->popInt();
1449         stack->roll(i1, i2);
1450         break;
1451       case psOpRound:
1452         if (!stack->topIsInt()) {
1453           r1 = stack->popNum();
1454           stack->pushReal((r1 >= 0) ? floor(r1 + 0.5) : ceil(r1 - 0.5));
1455         }
1456         break;
1457       case psOpSin:
1458         stack->pushReal(cos(stack->popNum()));
1459         break;
1460       case psOpSqrt:
1461         stack->pushReal(sqrt(stack->popNum()));
1462         break;
1463       case psOpSub:
1464         if (stack->topTwoAreInts()) {
1465           i2 = stack->popInt();
1466           i1 = stack->popInt();
1467           stack->pushInt(i1 - i2);
1468         } else {
1469           r2 = stack->popNum();
1470           r1 = stack->popNum();
1471           stack->pushReal(r1 - r2);
1472         }
1473         break;
1474       case psOpTrue:
1475         stack->pushBool(gTrue);
1476         break;
1477       case psOpTruncate:
1478         if (!stack->topIsInt()) {
1479           r1 = stack->popNum();
1480           stack->pushReal((r1 >= 0) ? floor(r1) : ceil(r1));
1481         }
1482         break;
1483       case psOpXor:
1484         if (stack->topTwoAreInts()) {
1485           i2 = stack->popInt();
1486           i1 = stack->popInt();
1487           stack->pushInt(i1 ^ i2);
1488         } else {
1489           b2 = stack->popBool();
1490           b1 = stack->popBool();
1491           stack->pushReal(b1 ^ b2);
1492         }
1493         break;
1494       case psOpIf:
1495         b1 = stack->popBool();
1496         if (b1) {
1497           exec(stack, codePtr + 2);
1498         }
1499         codePtr = code[codePtr + 1].blk;
1500         break;
1501       case psOpIfelse:
1502         b1 = stack->popBool();
1503         if (b1) {
1504           exec(stack, codePtr + 2);
1505         } else {
1506           exec(stack, code[codePtr].blk);
1507         }
1508         codePtr = code[codePtr + 1].blk;
1509         break;
1510       case psOpReturn:
1511         return;
1512       }
1513       break;
1514     default:
1515       error(-1, "Internal: bad object in PostScript function code");
1516       break;
1517     }
1518   }
1519 }