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