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