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