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