pdf2swf/xpdf/Function.cc

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