pdf/xpdf/Function.cc

   1 //========================================================================
   2 //
   3 // Function.cc
   4 //
   5 // Copyright 2001-2002 Glyph & Cog, LLC
   6 //
   7 //========================================================================
   8
   9 #include <aconf.h>
  10
  11 #ifdef USE_GCC_PRAGMAS
  12 #pragma implementation
  13 #endif
  14
  15 #include <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         code[*codePtr].real = atof(tok->getCString());
1076       } else {
1077         code[*codePtr].type = psInt;
1078         code[*codePtr].intg = atoi(tok->getCString());
1079       }
1080       ++*codePtr;
1081       delete tok;
1082     } else if (!tok->cmp("{")) {
1083       delete tok;
1084       opPtr = *codePtr;
1085       *codePtr += 3;
1086       resizeCode(opPtr + 2);
1087       if (!parseCode(str, codePtr)) {
1088         return gFalse;
1089       }
1090       if (!(tok = getToken(str))) {
1091         error(-1, "Unexpected end of PostScript function stream");
1092         return gFalse;
1093       }
1094       if (!tok->cmp("{")) {
1095         elsePtr = *codePtr;
1096         if (!parseCode(str, codePtr)) {
1097           return gFalse;
1098         }
1099         delete tok;
1100         if (!(tok = getToken(str))) {
1101           error(-1, "Unexpected end of PostScript function stream");
1102           return gFalse;
1103         }
1104       } else {
1105         elsePtr = -1;
1106       }
1107       if (!tok->cmp("if")) {
1108         if (elsePtr >= 0) {
1109           error(-1, "Got 'if' operator with two blocks in PostScript function");
1110           return gFalse;
1111         }
1112         code[opPtr].type = psOperator;
1113         code[opPtr].op = psOpIf;
1114         code[opPtr+2].type = psBlock;
1115         code[opPtr+2].blk = *codePtr;
1116       } else if (!tok->cmp("ifelse")) {
1117         if (elsePtr < 0) {
1118           error(-1, "Got 'ifelse' operator with one blocks in PostScript function");
1119           return gFalse;
1120         }
1121         code[opPtr].type = psOperator;
1122         code[opPtr].op = psOpIfelse;
1123         code[opPtr+1].type = psBlock;
1124         code[opPtr+1].blk = elsePtr;
1125         code[opPtr+2].type = psBlock;
1126         code[opPtr+2].blk = *codePtr;
1127       } else {
1128         error(-1, "Expected if/ifelse operator in PostScript function");
1129         delete tok;
1130         return gFalse;
1131       }
1132       delete tok;
1133     } else if (!tok->cmp("}")) {
1134       delete tok;
1135       resizeCode(*codePtr);
1136       code[*codePtr].type = psOperator;
1137       code[*codePtr].op = psOpReturn;
1138       ++*codePtr;
1139       break;
1140     } else {
1141       a = -1;
1142       b = nPSOps;
1143       // invariant: psOpNames[a] < tok < psOpNames[b]
1144       while (b - a > 1) {
1145         mid = (a + b) / 2;
1146         cmp = tok->cmp(psOpNames[mid]);
1147         if (cmp > 0) {
1148           a = mid;
1149         } else if (cmp < 0) {
1150           b = mid;
1151         } else {
1152           a = b = mid;
1153         }
1154       }
1155       if (cmp != 0) {
1156         error(-1, "Unknown operator '%s' in PostScript function",
1157               tok->getCString());
1158         delete tok;
1159         return gFalse;
1160       }
1161       delete tok;
1162       resizeCode(*codePtr);
1163       code[*codePtr].type = psOperator;
1164       code[*codePtr].op = (PSOp)a;
1165       ++*codePtr;
1166     }
1167   }
1168   return gTrue;
1169 }
1170
1171 GString *PostScriptFunction::getToken(Stream *str) {
1172   GString *s;
1173   int c;
1174
1175   s = new GString();
1176   do {
1177     c = str->getChar();
1178   } while (c != EOF && isspace(c));
1179   if (c == '{' || c == '}') {
1180     s->append((char)c);
1181   } else if (isdigit(c) || c == '.' || c == '-') {
1182     while (1) {
1183       s->append((char)c);
1184       c = str->lookChar();
1185       if (c == EOF || !(isdigit(c) || c == '.' || c == '-')) {
1186         break;
1187       }
1188       str->getChar();
1189     }
1190   } else {
1191     while (1) {
1192       s->append((char)c);
1193       c = str->lookChar();
1194       if (c == EOF || !isalnum(c)) {
1195         break;
1196       }
1197       str->getChar();
1198     }
1199   }
1200   return s;
1201 }
1202
1203 void PostScriptFunction::resizeCode(int newSize) {
1204   if (newSize >= codeSize) {
1205     codeSize += 64;
1206     code = (PSObject *)grealloc(code, codeSize * sizeof(PSObject));
1207   }
1208 }
1209
1210 void PostScriptFunction::exec(PSStack *stack, int codePtr) {
1211   int i1, i2;
1212   double r1, r2;
1213   GBool b1, b2;
1214
1215   while (1) {
1216     switch (code[codePtr].type) {
1217     case psInt:
1218       stack->pushInt(code[codePtr++].intg);
1219       break;
1220     case psReal:
1221       stack->pushReal(code[codePtr++].real);
1222       break;
1223     case psOperator:
1224       switch (code[codePtr++].op) {
1225       case psOpAbs:
1226         if (stack->topIsInt()) {
1227           stack->pushInt(abs(stack->popInt()));
1228         } else {
1229           stack->pushReal(fabs(stack->popNum()));
1230         }
1231         break;
1232       case psOpAdd:
1233         if (stack->topTwoAreInts()) {
1234           i2 = stack->popInt();
1235           i1 = stack->popInt();
1236           stack->pushInt(i1 + i2);
1237         } else {
1238           r2 = stack->popNum();
1239           r1 = stack->popNum();
1240           stack->pushReal(r1 + r2);
1241         }
1242         break;
1243       case psOpAnd:
1244         if (stack->topTwoAreInts()) {
1245           i2 = stack->popInt();
1246           i1 = stack->popInt();
1247           stack->pushInt(i1 & i2);
1248         } else {
1249           b2 = stack->popBool();
1250           b1 = stack->popBool();
1251           stack->pushReal(b1 && b2);
1252         }
1253         break;
1254       case psOpAtan:
1255         r2 = stack->popNum();
1256         r1 = stack->popNum();
1257         stack->pushReal(atan2(r1, r2));
1258         break;
1259       case psOpBitshift:
1260         i2 = stack->popInt();
1261         i1 = stack->popInt();
1262         if (i2 > 0) {
1263           stack->pushInt(i1 << i2);
1264         } else if (i2 < 0) {
1265           stack->pushInt((int)((Guint)i1 >> i2));
1266         } else {
1267           stack->pushInt(i1);
1268         }
1269         break;
1270       case psOpCeiling:
1271         if (!stack->topIsInt()) {
1272           stack->pushReal(ceil(stack->popNum()));
1273         }
1274         break;
1275       case psOpCopy:
1276         stack->copy(stack->popInt());
1277         break;
1278       case psOpCos:
1279         stack->pushReal(cos(stack->popNum()));
1280         break;
1281       case psOpCvi:
1282         if (!stack->topIsInt()) {
1283           stack->pushInt((int)stack->popNum());
1284         }
1285         break;
1286       case psOpCvr:
1287         if (!stack->topIsReal()) {
1288           stack->pushReal(stack->popNum());
1289         }
1290         break;
1291       case psOpDiv:
1292         r2 = stack->popNum();
1293         r1 = stack->popNum();
1294         stack->pushReal(r1 / r2);
1295         break;
1296       case psOpDup:
1297         stack->copy(1);
1298         break;
1299       case psOpEq:
1300         if (stack->topTwoAreInts()) {
1301           i2 = stack->popInt();
1302           i1 = stack->popInt();
1303           stack->pushBool(i1 == i2);
1304         } else if (stack->topTwoAreNums()) {
1305           r2 = stack->popNum();
1306           r1 = stack->popNum();
1307           stack->pushBool(r1 == r2);
1308         } else {
1309           b2 = stack->popBool();
1310           b1 = stack->popBool();
1311           stack->pushBool(b1 == b2);
1312         }
1313         break;
1314       case psOpExch:
1315         stack->roll(2, 1);
1316         break;
1317       case psOpExp:
1318         r2 = stack->popInt();
1319         r1 = stack->popInt();
1320         stack->pushReal(pow(r1, r2));
1321         break;
1322       case psOpFalse:
1323         stack->pushBool(gFalse);
1324         break;
1325       case psOpFloor:
1326         if (!stack->topIsInt()) {
1327           stack->pushReal(floor(stack->popNum()));
1328         }
1329         break;
1330       case psOpGe:
1331         if (stack->topTwoAreInts()) {
1332           i2 = stack->popInt();
1333           i1 = stack->popInt();
1334           stack->pushBool(i1 >= i2);
1335         } else {
1336           r2 = stack->popNum();
1337           r1 = stack->popNum();
1338           stack->pushBool(r1 >= r2);
1339         }
1340         break;
1341       case psOpGt:
1342         if (stack->topTwoAreInts()) {
1343           i2 = stack->popInt();
1344           i1 = stack->popInt();
1345           stack->pushBool(i1 > i2);
1346         } else {
1347           r2 = stack->popNum();
1348           r1 = stack->popNum();
1349           stack->pushBool(r1 > r2);
1350         }
1351         break;
1352       case psOpIdiv:
1353         i2 = stack->popInt();
1354         i1 = stack->popInt();
1355         stack->pushInt(i1 / i2);
1356         break;
1357       case psOpIndex:
1358         stack->index(stack->popInt());
1359         break;
1360       case psOpLe:
1361         if (stack->topTwoAreInts()) {
1362           i2 = stack->popInt();
1363           i1 = stack->popInt();
1364           stack->pushBool(i1 <= i2);
1365         } else {
1366           r2 = stack->popNum();
1367           r1 = stack->popNum();
1368           stack->pushBool(r1 <= r2);
1369         }
1370         break;
1371       case psOpLn:
1372         stack->pushReal(log(stack->popNum()));
1373         break;
1374       case psOpLog:
1375         stack->pushReal(log10(stack->popNum()));
1376         break;
1377       case psOpLt:
1378         if (stack->topTwoAreInts()) {
1379           i2 = stack->popInt();
1380           i1 = stack->popInt();
1381           stack->pushBool(i1 < i2);
1382         } else {
1383           r2 = stack->popNum();
1384           r1 = stack->popNum();
1385           stack->pushBool(r1 < r2);
1386         }
1387         break;
1388       case psOpMod:
1389         i2 = stack->popInt();
1390         i1 = stack->popInt();
1391         stack->pushInt(i1 % i2);
1392         break;
1393       case psOpMul:
1394         if (stack->topTwoAreInts()) {
1395           i2 = stack->popInt();
1396           i1 = stack->popInt();
1397           //~ should check for out-of-range, and push a real instead
1398           stack->pushInt(i1 * i2);
1399         } else {
1400           r2 = stack->popNum();
1401           r1 = stack->popNum();
1402           stack->pushReal(r1 * r2);
1403         }
1404         break;
1405       case psOpNe:
1406         if (stack->topTwoAreInts()) {
1407           i2 = stack->popInt();
1408           i1 = stack->popInt();
1409           stack->pushBool(i1 != i2);
1410         } else if (stack->topTwoAreNums()) {
1411           r2 = stack->popNum();
1412           r1 = stack->popNum();
1413           stack->pushBool(r1 != r2);
1414         } else {
1415           b2 = stack->popBool();
1416           b1 = stack->popBool();
1417           stack->pushBool(b1 != b2);
1418         }
1419         break;
1420       case psOpNeg:
1421         if (stack->topIsInt()) {
1422           stack->pushInt(-stack->popInt());
1423         } else {
1424           stack->pushReal(-stack->popNum());
1425         }
1426         break;
1427       case psOpNot:
1428         if (stack->topIsInt()) {
1429           stack->pushInt(~stack->popInt());
1430         } else {
1431           stack->pushReal(!stack->popBool());
1432         }
1433         break;
1434       case psOpOr:
1435         if (stack->topTwoAreInts()) {
1436           i2 = stack->popInt();
1437           i1 = stack->popInt();
1438           stack->pushInt(i1 | i2);
1439         } else {
1440           b2 = stack->popBool();
1441           b1 = stack->popBool();
1442           stack->pushReal(b1 || b2);
1443         }
1444         break;
1445       case psOpPop:
1446         stack->pop();
1447         break;
1448       case psOpRoll:
1449         i2 = stack->popInt();
1450         i1 = stack->popInt();
1451         stack->roll(i1, i2);
1452         break;
1453       case psOpRound:
1454         if (!stack->topIsInt()) {
1455           r1 = stack->popNum();
1456           stack->pushReal((r1 >= 0) ? floor(r1 + 0.5) : ceil(r1 - 0.5));
1457         }
1458         break;
1459       case psOpSin:
1460         stack->pushReal(cos(stack->popNum()));
1461         break;
1462       case psOpSqrt:
1463         stack->pushReal(sqrt(stack->popNum()));
1464         break;
1465       case psOpSub:
1466         if (stack->topTwoAreInts()) {
1467           i2 = stack->popInt();
1468           i1 = stack->popInt();
1469           stack->pushInt(i1 - i2);
1470         } else {
1471           r2 = stack->popNum();
1472           r1 = stack->popNum();
1473           stack->pushReal(r1 - r2);
1474         }
1475         break;
1476       case psOpTrue:
1477         stack->pushBool(gTrue);
1478         break;
1479       case psOpTruncate:
1480         if (!stack->topIsInt()) {
1481           r1 = stack->popNum();
1482           stack->pushReal((r1 >= 0) ? floor(r1) : ceil(r1));
1483         }
1484         break;
1485       case psOpXor:
1486         if (stack->topTwoAreInts()) {
1487           i2 = stack->popInt();
1488           i1 = stack->popInt();
1489           stack->pushInt(i1 ^ i2);
1490         } else {
1491           b2 = stack->popBool();
1492           b1 = stack->popBool();
1493           stack->pushReal(b1 ^ b2);
1494         }
1495         break;
1496       case psOpIf:
1497         b1 = stack->popBool();
1498         if (b1) {
1499           exec(stack, codePtr + 2);
1500         }
1501         codePtr = code[codePtr + 1].blk;
1502         break;
1503       case psOpIfelse:
1504         b1 = stack->popBool();
1505         if (b1) {
1506           exec(stack, codePtr + 2);
1507         } else {
1508           exec(stack, code[codePtr].blk);
1509         }
1510         codePtr = code[codePtr + 1].blk;
1511         break;
1512       case psOpReturn:
1513         return;
1514       }
1515       break;
1516     default:
1517       error(-1, "Internal: bad object in PostScript function code");
1518       break;
1519     }
1520   }
1521 }