pdf/xpdf/Function.cc

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