pdf/xpdf/TextOutputDev.cc

   1 //========================================================================
   2 //
   3 // TextOutputDev.cc
   4 //
   5 // Copyright 1997-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 <stdio.h>
  16 #include <stdlib.h>
  17 #include <stddef.h>
  18 #include <math.h>
  19 #include <ctype.h>
  20 #include "GString.h"
  21 #include "gmem.h"
  22 #include "config.h"
  23 #include "Error.h"
  24 #include "GlobalParams.h"
  25 #include "UnicodeMap.h"
  26 #include "GfxState.h"
  27 #include "TextOutputDev.h"
  28
  29 #ifdef MACOS
  30 // needed for setting type/creator of MacOS files
  31 #include "ICSupport.h"
  32 #endif
  33
  34 //------------------------------------------------------------------------
  35
  36 #define textOutSpace    0.2
  37 #define textOutColSpace 0.2
  38
  39 //------------------------------------------------------------------------
  40
  41 struct TextOutColumnEdge {
  42   double x, y0, y1;
  43 };
  44
  45 //------------------------------------------------------------------------
  46 // TextBlock
  47 //------------------------------------------------------------------------
  48
  49 class TextBlock {
  50 public:
  51
  52   TextBlock();
  53   ~TextBlock();
  54
  55   double xMin, xMax;
  56   double yMin, yMax;
  57   TextString *strings;          // list of strings in the block
  58   TextBlock *next;              // next block in line
  59   TextBlock *xyNext;            // next block on xyBlocks list
  60   Unicode *text;                // Unicode text of the block, including
  61                                 //   spaces between strings
  62   double *xRight;               // right-hand x coord of each char
  63   int len;                      // total number of Unicode characters
  64   int convertedLen;             // total number of converted characters
  65   int *col;                     // starting column number for each
  66                                 //   Unicode character
  67 };
  68
  69 TextBlock::TextBlock() {
  70   strings = NULL;
  71   next = NULL;
  72   xyNext = NULL;
  73   text = NULL;
  74   xRight = NULL;
  75   col = NULL;
  76 }
  77
  78 TextBlock::~TextBlock() {
  79   TextString *p1, *p2;
  80
  81   for (p1 = strings; p1; p1 = p2) {
  82     p2 = p1->next;
  83     delete p1;
  84   }
  85   gfree(text);
  86   gfree(xRight);
  87   gfree(col);
  88 }
  89
  90 //------------------------------------------------------------------------
  91 // TextLine
  92 //------------------------------------------------------------------------
  93
  94 class TextLine {
  95 public:
  96
  97   TextLine();
  98   ~TextLine();
  99
 100   TextBlock *blocks;
 101   TextLine *next;
 102   double yMin, yMax;
 103 };
 104
 105 TextLine::TextLine() {
 106   blocks = NULL;
 107   next = NULL;
 108 }
 109
 110 TextLine::~TextLine() {
 111   TextBlock *p1, *p2;
 112
 113   for (p1 = blocks; p1; p1 = p2) {
 114     p2 = p1->next;
 115     delete p1;
 116   }
 117 }
 118
 119 //------------------------------------------------------------------------
 120 // TextString
 121 //------------------------------------------------------------------------
 122
 123 TextString::TextString(GfxState *state, double x0, double y0,
 124                        double fontSize) {
 125   GfxFont *font;
 126   double x, y;
 127
 128   state->transform(x0, y0, &x, &y);
 129   if ((font = state->getFont())) {
 130     yMin = y - font->getAscent() * fontSize;
 131     yMax = y - font->getDescent() * fontSize;
 132   } else {
 133     // this means that the PDF file draws text without a current font,
 134     // which should never happen
 135     yMin = y - 0.95 * fontSize;
 136     yMax = y + 0.35 * fontSize;
 137   }
 138   if (yMin == yMax) {
 139     // this is a sanity check for a case that shouldn't happen -- but
 140     // if it does happen, we want to avoid dividing by zero later
 141     yMin = y;
 142     yMax = y + 1;
 143   }
 144   marked = gFalse;
 145   text = NULL;
 146   xRight = NULL;
 147   len = size = 0;
 148   next = NULL;
 149 }
 150
 151
 152 TextString::~TextString() {
 153   gfree(text);
 154   gfree(xRight);
 155 }
 156
 157 void TextString::addChar(GfxState *state, double x, double y,
 158                          double dx, double dy, Unicode u) {
 159   if (len == size) {
 160     size += 16;
 161     text = (Unicode *)grealloc(text, size * sizeof(Unicode));
 162     xRight = (double *)grealloc(xRight, size * sizeof(double));
 163   }
 164   text[len] = u;
 165   if (len == 0) {
 166     xMin = x;
 167   }
 168   xMax = xRight[len] = x + dx;
 169   ++len;
 170 }
 171
 172 //------------------------------------------------------------------------
 173 // TextPage
 174 //------------------------------------------------------------------------
 175
 176 TextPage::TextPage(GBool rawOrderA) {
 177   rawOrder = rawOrderA;
 178   curStr = NULL;
 179   fontSize = 0;
 180   xyStrings = NULL;
 181   xyCur1 = xyCur2 = NULL;
 182   lines = NULL;
 183   nest = 0;
 184   nTinyChars = 0;
 185 }
 186
 187 TextPage::~TextPage() {
 188   clear();
 189 }
 190
 191 void TextPage::updateFont(GfxState *state) {
 192   GfxFont *font;
 193   double *fm;
 194   char *name;
 195   int code, mCode, letterCode, anyCode;
 196   double w;
 197
 198   // adjust the font size
 199   fontSize = state->getTransformedFontSize();
 200   if ((font = state->getFont()) && font->getType() == fontType3) {
 201     // This is a hack which makes it possible to deal with some Type 3
 202     // fonts.  The problem is that it's impossible to know what the
 203     // base coordinate system used in the font is without actually
 204     // rendering the font.  This code tries to guess by looking at the
 205     // width of the character 'm' (which breaks if the font is a
 206     // subset that doesn't contain 'm').
 207     mCode = letterCode = anyCode = -1;
 208     for (code = 0; code < 256; ++code) {
 209       name = ((Gfx8BitFont *)font)->getCharName(code);
 210       if (name && name[0] == 'm' && name[1] == '\0') {
 211         mCode = code;
 212       }
 213       if (letterCode < 0 && name && name[1] == '\0' &&
 214           ((name[0] >= 'A' && name[0] <= 'Z') ||
 215            (name[0] >= 'a' && name[0] <= 'z'))) {
 216         letterCode = code;
 217       }
 218       if (anyCode < 0 && name && ((Gfx8BitFont *)font)->getWidth(code) > 0) {
 219         anyCode = code;
 220       }
 221     }
 222     if (mCode >= 0 &&
 223         (w = ((Gfx8BitFont *)font)->getWidth(mCode)) > 0) {
 224       // 0.6 is a generic average 'm' width -- yes, this is a hack
 225       fontSize *= w / 0.6;
 226     } else if (letterCode >= 0 &&
 227                (w = ((Gfx8BitFont *)font)->getWidth(letterCode)) > 0) {
 228       // even more of a hack: 0.5 is a generic letter width
 229       fontSize *= w / 0.5;
 230     } else if (anyCode >= 0 &&
 231                (w = ((Gfx8BitFont *)font)->getWidth(anyCode)) > 0) {
 232       // better than nothing: 0.5 is a generic character width
 233       fontSize *= w / 0.5;
 234     }
 235     fm = font->getFontMatrix();
 236     if (fm[0] != 0) {
 237       fontSize *= fabs(fm[3] / fm[0]);
 238     }
 239   }
 240 }
 241
 242 void TextPage::beginString(GfxState *state, double x0, double y0) {
 243   // This check is needed because Type 3 characters can contain
 244   // text-drawing operations.
 245   if (curStr) {
 246     ++nest;
 247     return;
 248   }
 249
 250   curStr = new TextString(state, x0, y0, fontSize);
 251 }
 252
 253 void TextPage::addChar(GfxState *state, double x, double y,
 254                        double dx, double dy, Unicode *u, int uLen) {
 255   double x1, y1, w1, h1, dx2, dy2;
 256   int n, i;
 257
 258   state->transform(x, y, &x1, &y1);
 259   if (x1 < 0 || x1 > state->getPageWidth() ||
 260       y1 < 0 || y1 > state->getPageHeight()) {
 261     return;
 262   }
 263   state->textTransformDelta(state->getCharSpace() * state->getHorizScaling(),
 264                             0, &dx2, &dy2);
 265   dx -= dx2;
 266   dy -= dy2;
 267   state->transformDelta(dx, dy, &w1, &h1);
 268   if (!globalParams->getTextKeepTinyChars() &&
 269       fabs(w1) < 3 && fabs(h1) < 3) {
 270     if (++nTinyChars > 20000) {
 271       return;
 272     }
 273   }
 274   n = curStr->len;
 275   if (n > 0 && x1 - curStr->xRight[n-1] >
 276                0.1 * (curStr->yMax - curStr->yMin)) {
 277     // large char spacing is sometimes used to move text around
 278     endString();
 279     beginString(state, x, y);
 280   }
 281   if (uLen == 1 && u[0] == (Unicode)0x20 &&
 282       w1 > 0.5 * (curStr->yMax - curStr->yMin)) {
 283     // large word spacing is sometimes used to move text around
 284     return;
 285   }
 286   if (uLen != 0) {
 287     w1 /= uLen;
 288     h1 /= uLen;
 289   }
 290   for (i = 0; i < uLen; ++i) {
 291     curStr->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, u[i]);
 292   }
 293 }
 294
 295 void TextPage::endString() {
 296   // This check is needed because Type 3 characters can contain
 297   // text-drawing operations.
 298   if (nest > 0) {
 299     --nest;
 300     return;
 301   }
 302
 303   addString(curStr);
 304   curStr = NULL;
 305 }
 306
 307 void TextPage::addString(TextString *str) {
 308   TextString *p1, *p2;
 309
 310   // throw away zero-length strings -- they don't have valid xMin/xMax
 311   // values, and they're useless anyway
 312   if (str->len == 0) {
 313     delete str;
 314     return;
 315   }
 316
 317   // insert string in xy list
 318   if (rawOrder) {
 319     p1 = xyCur1;
 320     p2 = NULL;
 321   } else if ((!xyCur1 || xyBefore(xyCur1, str)) &&
 322              (!xyCur2 || xyBefore(str, xyCur2))) {
 323     p1 = xyCur1;
 324     p2 = xyCur2;
 325   } else if (xyCur1 && xyBefore(xyCur1, str)) {
 326     for (p1 = xyCur1, p2 = xyCur2; p2; p1 = p2, p2 = p2->next) {
 327       if (xyBefore(str, p2)) {
 328         break;
 329       }
 330     }
 331     xyCur2 = p2;
 332   } else {
 333     for (p1 = NULL, p2 = xyStrings; p2; p1 = p2, p2 = p2->next) {
 334       if (xyBefore(str, p2)) {
 335         break;
 336       }
 337     }
 338     xyCur2 = p2;
 339   }
 340   xyCur1 = str;
 341   if (p1) {
 342     p1->next = str;
 343   } else {
 344     xyStrings = str;
 345   }
 346   str->next = p2;
 347 }
 348
 349 void TextPage::coalesce() {
 350   TextLine *line, *line0;
 351   TextBlock *yxBlocks, *xyBlocks, *blk, *blk0, *blk1, *blk2;
 352   TextString *str0, *str1, *str2, *str3, *str4;
 353   TextString *str1prev, *str2prev, *str3prev;
 354   TextOutColumnEdge *edges;
 355   UnicodeMap *uMap;
 356   GBool isUnicode;
 357   char buf[8];
 358   int edgesLength, edgesSize;
 359   double x, yMin, yMax;
 360   double space, fit1, fit2, h;
 361   int col1, col2, d;
 362   int i, j;
 363
 364 #if 0 //~ for debugging
 365   for (str1 = xyStrings; str1; str1 = str1->next) {
 366     printf("x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f '",
 367            str1->xMin, str1->xMax, str1->yMin, str1->yMax,
 368            (str1->yMax - str1->yMin));
 369     for (i = 0; i < str1->len; ++i) {
 370       fputc(str1->text[i] & 0xff, stdout);
 371     }
 372     printf("'\n");
 373   }
 374   printf("\n------------------------------------------------------------\n\n");
 375 #endif
 376
 377   // build the list of column edges
 378   edges = NULL;
 379   edgesLength = edgesSize = 0;
 380   if (!rawOrder) {
 381     for (str1prev = NULL, str1 = xyStrings;
 382          str1;
 383          str1prev = str1, str1 = str1->next) {
 384       if (str1->marked) {
 385         continue;
 386       }
 387       h = str1->yMax - str1->yMin;
 388       if (str1prev && (str1->xMin - str1prev->xMax) / h < textOutColSpace) {
 389         continue;
 390       }
 391       x = str1->xMin;
 392       yMin = str1->yMin;
 393       yMax = str1->yMax;
 394       for (str2prev = str1, str2 = str1->next;
 395            str2;
 396            str2prev = str2, str2 = str2->next) {
 397         h = str2->yMax - str2->yMin;
 398         if (!str2->marked &&
 399             (str2->xMin - str2prev->xMax) / h > textOutColSpace &&
 400             fabs(str2->xMin - x) < 0.5 &&
 401             str2->yMin - yMax < 0.3 * h &&
 402             yMin - str2->yMax < 0.3 * h) {
 403           break;
 404         }
 405       }
 406       if (str2) {
 407         if (str2->yMin < yMin) {
 408           yMin = str2->yMin;
 409         }
 410         if (str2->yMax > yMax) {
 411           yMax = str2->yMax;
 412         }
 413         str2->marked = gTrue;
 414         for (str3prev = str1, str3 = str1->next;
 415              str3;
 416              str3prev = str3, str3 = str3->next) {
 417           h = str3->yMax - str3->yMin;
 418           if (!str3->marked &&
 419               (str3->xMin - str3prev->xMax) / h > textOutColSpace &&
 420               fabs(str3->xMin - x) < 0.5 &&
 421               str3->yMin - yMax < 0.3 * h &&
 422               yMin - str3->yMax < 0.3 * h) {
 423             break;
 424           }
 425         }
 426         if (str3) {
 427           if (str3->yMin < yMin) {
 428             yMin = str3->yMin;
 429           }
 430           if (str3->yMax > yMax) {
 431             yMax = str3->yMax;
 432           }
 433           str3->marked = gTrue;
 434           do {
 435             for (str2prev = str1, str2 = str1->next;
 436                  str2;
 437                  str2prev = str2, str2 = str2->next) {
 438               h = str2->yMax - str2->yMin;
 439               if (!str2->marked &&
 440                   (str2->xMin - str2prev->xMax) / h > textOutColSpace &&
 441                   fabs(str2->xMin - x) < 0.5 &&
 442                   str2->yMin - yMax < 0.3 * h &&
 443                   yMin - str2->yMax < 0.3 * h) {
 444                 if (str2->yMin < yMin) {
 445                   yMin = str2->yMin;
 446                 }
 447                 if (str2->yMax > yMax) {
 448                   yMax = str2->yMax;
 449                 }
 450                 str2->marked = gTrue;
 451                 break;
 452               }
 453             }
 454           } while (str2);
 455           if (edgesLength == edgesSize) {
 456             edgesSize = edgesSize ? 2 * edgesSize : 16;
 457             edges = (TextOutColumnEdge *)
 458               grealloc(edges, edgesSize * sizeof(TextOutColumnEdge));
 459           }
 460           edges[edgesLength].x = x;
 461           edges[edgesLength].y0 = yMin;
 462           edges[edgesLength].y1 = yMax;
 463           ++edgesLength;
 464         } else {
 465           str2->marked = gFalse;
 466         }
 467       }
 468       str1->marked = gTrue;
 469     }
 470   }
 471
 472 #if 0 //~ for debugging
 473   printf("column edges:\n");
 474   for (i = 0; i < edgesLength; ++i) {
 475     printf("%d: x=%.2f y0=%.2f y1=%.2f\n",
 476            i, edges[i].x, edges[i].y0, edges[i].y1);
 477   }
 478   printf("\n------------------------------------------------------------\n\n");
 479 #endif
 480
 481   // build the blocks
 482   yxBlocks = NULL;
 483   blk1 = blk2 = NULL;
 484   while (xyStrings) {
 485
 486     // build the block
 487     str0 = xyStrings;
 488     xyStrings = xyStrings->next;
 489     str0->next = NULL;
 490     blk = new TextBlock();
 491     blk->strings = str0;
 492     blk->xMin = str0->xMin;
 493     blk->xMax = str0->xMax;
 494     blk->yMin = str0->yMin;
 495     blk->yMax = str0->yMax;
 496     while (xyStrings) {
 497       str1 = NULL;
 498       str2 = xyStrings;
 499       fit1 = coalesceFit(str0, str2);
 500       if (!rawOrder) {
 501         // look for best-fitting string
 502         space = str0->yMax - str0->yMin;
 503         for (str3 = xyStrings, str4 = xyStrings->next;
 504              str4 && str4->xMin - str0->xMax <= space;
 505              str3 = str4, str4 = str4->next) {
 506           fit2 = coalesceFit(str0, str4);
 507           if (fit2 < fit1) {
 508             str1 = str3;
 509             str2 = str4;
 510             fit1 = fit2;
 511           }
 512         }
 513       }
 514       if (fit1 > 1) {
 515         // no fit - we're done with this block
 516         break;
 517       }
 518
 519       // if we've hit a column edge we're done with this block
 520       if (fit1 > 0.2) {
 521         for (i = 0; i < edgesLength; ++i) {
 522           if (str0->xMax < edges[i].x + 0.5 && edges[i].x - 0.5 < str2->xMin &&
 523               str0->yMin < edges[i].y1 && str0->yMax > edges[i].y0 &&
 524               str2->yMin < edges[i].y1 && str2->yMax > edges[i].y0) {
 525             break;
 526           }
 527         }
 528         if (i < edgesLength) {
 529           break;
 530         }
 531       }
 532
 533       if (str1) {
 534         str1->next = str2->next;
 535       } else {
 536         xyStrings = str2->next;
 537       }
 538       str0->next = str2;
 539       str2->next = NULL;
 540       if (str2->xMax > blk->xMax) {
 541         blk->xMax = str2->xMax;
 542       }
 543       if (str2->yMin < blk->yMin) {
 544         blk->yMin = str2->yMin;
 545       }
 546       if (str2->yMax > blk->yMax) {
 547         blk->yMax = str2->yMax;
 548       }
 549       str0 = str2;
 550     }
 551
 552     // insert block on list
 553     if (!rawOrder) {
 554       // insert block on list in yx order
 555       for (blk1 = NULL, blk2 = yxBlocks;
 556            blk2 && !yxBefore(blk, blk2);
 557            blk1 = blk2, blk2 = blk2->next) ;
 558     }
 559     blk->next = blk2;
 560     if (blk1) {
 561       blk1->next = blk;
 562     } else {
 563       yxBlocks = blk;
 564     }
 565     blk1 = blk;
 566   }
 567
 568   gfree(edges);
 569
 570   // the strings are now owned by the lines/blocks tree
 571   xyStrings = NULL;
 572
 573   // build the block text
 574   uMap = globalParams->getTextEncoding();
 575   isUnicode = uMap ? uMap->isUnicode() : gFalse;
 576   for (blk = yxBlocks; blk; blk = blk->next) {
 577     blk->len = 0;
 578     for (str1 = blk->strings; str1; str1 = str1->next) {
 579       blk->len += str1->len;
 580       if (str1->next && str1->next->xMin - str1->xMax >
 581                         textOutSpace * (str1->yMax - str1->yMin)) {
 582         str1->spaceAfter = gTrue;
 583         ++blk->len;
 584       } else {
 585         str1->spaceAfter = gFalse;
 586       }
 587     }
 588     blk->text = (Unicode *)gmalloc(blk->len * sizeof(Unicode));
 589     blk->xRight = (double *)gmalloc(blk->len * sizeof(double));
 590     blk->col = (int *)gmalloc(blk->len * sizeof(int));
 591     i = 0;
 592     for (str1 = blk->strings; str1; str1 = str1->next) {
 593       for (j = 0; j < str1->len; ++j) {
 594         blk->text[i] = str1->text[j];
 595         blk->xRight[i] = str1->xRight[j];
 596         ++i;
 597       }
 598       if (str1->spaceAfter) {
 599         blk->text[i] = (Unicode)0x0020;
 600         blk->xRight[i] = str1->next->xMin;
 601         ++i;
 602       }
 603     }
 604     blk->convertedLen = 0;
 605     for (j = 0; j < blk->len; ++j) {
 606       blk->col[j] = blk->convertedLen;
 607       if (isUnicode) {
 608         ++blk->convertedLen;
 609       } else if (uMap) {
 610         blk->convertedLen += uMap->mapUnicode(blk->text[j], buf, sizeof(buf));
 611       }
 612     }
 613   }
 614   if (uMap) {
 615     uMap->decRefCnt();
 616   }
 617
 618 #if 0 //~ for debugging
 619   for (blk = yxBlocks; blk; blk = blk->next) {
 620     printf("[block: x=%.2f..%.2f y=%.2f..%.2f len=%d]\n",
 621            blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->len);
 622     TextString *str;
 623     for (str = blk->strings; str; str = str->next) {
 624       printf("    x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f'",
 625              str->xMin, str->xMax, str->yMin, str->yMax,
 626              (str->yMax - str->yMin));
 627       for (i = 0; i < str->len; ++i) {
 628         fputc(str->text[i] & 0xff, stdout);
 629       }
 630       if (str->spaceAfter) {
 631         fputc(' ', stdout);
 632       }
 633       printf("'\n");
 634     }
 635   }
 636   printf("\n------------------------------------------------------------\n\n");
 637 #endif
 638
 639   // build the lines
 640   lines = NULL;
 641   line0 = NULL;
 642   while (yxBlocks) {
 643     blk0 = yxBlocks;
 644     yxBlocks = yxBlocks->next;
 645     blk0->next = NULL;
 646     line = new TextLine();
 647     line->blocks = blk0;
 648     line->yMin = blk0->yMin;
 649     line->yMax = blk0->yMax;
 650     while (yxBlocks) {
 651
 652       // remove duplicated text (fake boldface, shadowed text)
 653       h = blk0->yMax - blk0->yMin;
 654       if (yxBlocks->len == blk0->len &&
 655           !memcmp(yxBlocks->text, blk0->text,
 656                   yxBlocks->len * sizeof(Unicode)) &&
 657           fabs(yxBlocks->yMin - blk0->yMin) / h < 0.2 &&
 658           fabs(yxBlocks->yMax - blk0->yMax) / h < 0.2 &&
 659           fabs(yxBlocks->xMin - blk0->xMin) / h < 0.2 &&
 660           fabs(yxBlocks->xMax - blk0->xMax) / h < 0.2) {
 661         blk1 = yxBlocks;
 662         yxBlocks = yxBlocks->next;
 663         delete blk1;
 664         continue;
 665       }
 666
 667       if (rawOrder && yxBlocks->yMax < blk0->yMin) {
 668         break;
 669       }
 670       if (yxBlocks->yMin > 0.2*blk0->yMin + 0.8*blk0->yMax ||
 671           yxBlocks->xMin < blk0->xMax) {
 672         break;
 673       }
 674       blk1 = yxBlocks;
 675       yxBlocks = yxBlocks->next;
 676       blk0->next = blk1;
 677       blk1->next = NULL;
 678       if (blk1->yMin < line->yMin) {
 679         line->yMin = blk1->yMin;
 680       }
 681       if (blk1->yMax > line->yMax) {
 682         line->yMax = blk1->yMax;
 683       }
 684       blk0 = blk1;
 685     }
 686     if (line0) {
 687       line0->next = line;
 688     } else {
 689       lines = line;
 690     }
 691     line->next = NULL;
 692     line0 = line;
 693   }
 694
 695
 696   // sort the blocks into xy order
 697   xyBlocks = NULL;
 698   for (line = lines; line; line = line->next) {
 699     for (blk = line->blocks; blk; blk = blk->next) {
 700       for (blk1 = NULL, blk2 = xyBlocks;
 701            blk2 && !xyBefore(blk, blk2);
 702            blk1 = blk2, blk2 = blk2->xyNext) ;
 703       blk->xyNext = blk2;
 704       if (blk1) {
 705         blk1->xyNext = blk;
 706       } else {
 707         xyBlocks = blk;
 708       }
 709     }
 710   }
 711
 712 #if 0 //~ for debugging
 713   for (blk = xyBlocks; blk; blk = blk->xyNext) {
 714     printf("[block: x=%.2f..%.2f y=%.2f..%.2f len=%d]\n",
 715            blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->len);
 716     TextString *str;
 717     for (str = blk->strings; str; str = str->next) {
 718       printf("    x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f '",
 719              str->xMin, str->xMax, str->yMin, str->yMax,
 720              (str->yMax - str->yMin));
 721       for (i = 0; i < str->len; ++i) {
 722         fputc(str->text[i] & 0xff, stdout);
 723       }
 724       printf("'\n");
 725     }
 726   }
 727   printf("\n------------------------------------------------------------\n\n");
 728 #endif
 729
 730   // do column assignment
 731   for (blk1 = xyBlocks; blk1; blk1 = blk1->xyNext) {
 732     col1 = 0;
 733     for (blk2 = xyBlocks; blk2 != blk1; blk2 = blk2->xyNext) {
 734       if (blk1->xMin >= blk2->xMax) {
 735         d = (int)((blk1->xMin - blk2->xMax) /
 736                   (0.4 * (blk1->yMax - blk1->yMin)));
 737         if (d > 4) {
 738           d = 4;
 739         }
 740         col2 = blk2->col[0] + blk2->convertedLen + d;
 741         if (col2 > col1) {
 742           col1 = col2;
 743         }
 744       } else if (blk1->xMin > blk2->xMin) {
 745         for (i = 0; i < blk2->len && blk1->xMin >= blk2->xRight[i]; ++i) ;
 746         col2 = blk2->col[i];
 747         if (col2 > col1) {
 748           col1 = col2;
 749         }
 750       }
 751     }
 752     for (j = 0; j < blk1->len; ++j) {
 753       blk1->col[j] += col1;
 754     }
 755   }
 756
 757 #if 0 //~ for debugging
 758   for (line = lines; line; line = line->next) {
 759     printf("[line]\n");
 760     for (blk = line->blocks; blk; blk = blk->next) {
 761       printf("[block: col=%d, len=%d]\n", blk->col[0], blk->len);
 762       TextString *str;
 763       for (str = blk->strings; str; str = str->next) {
 764         printf("    x=%.2f..%.2f  y=%.2f..%.2f  size=%.2f '",
 765                str->xMin, str->xMax, str->yMin, str->yMax,
 766                (str->yMax - str->yMin));
 767         for (i = 0; i < str->len; ++i) {
 768           fputc(str->text[i] & 0xff, stdout);
 769         }
 770         if (str->spaceAfter) {
 771           printf(" [space]\n");
 772         }
 773         printf("'\n");
 774       }
 775     }
 776   }
 777   printf("\n------------------------------------------------------------\n\n");
 778 #endif
 779 }
 780
 781
 782 GBool TextPage::findText(Unicode *s, int len,
 783                          GBool top, GBool bottom,
 784                          double *xMin, double *yMin,
 785                          double *xMax, double *yMax) {
 786   TextLine *line;
 787   TextBlock *blk;
 788   Unicode *p;
 789   Unicode u1, u2;
 790   int m, i, j;
 791   double x0, x1, x;
 792
 793   // scan all blocks on page
 794   for (line = lines; line; line = line->next) {
 795     for (blk = line->blocks; blk; blk = blk->next) {
 796
 797       // check: above top limit?
 798       if (!top && (blk->yMax < *yMin ||
 799                    (blk->yMin < *yMin && blk->xMax <= *xMin))) {
 800         continue;
 801       }
 802
 803       // check: below bottom limit?
 804       if (!bottom && (blk->yMin > *yMax ||
 805                       (blk->yMax > *yMax && blk->xMin >= *xMax))) {
 806         return gFalse;
 807       }
 808
 809       // search each position in this block
 810       m = blk->len;
 811       for (i = 0, p = blk->text; i <= m - len; ++i, ++p) {
 812
 813         x0 = (i == 0) ? blk->xMin : blk->xRight[i-1];
 814         x1 = blk->xRight[i];
 815         x = 0.5 * (x0 + x1);
 816
 817         // check: above top limit?
 818         if (!top && blk->yMin < *yMin) {
 819           if (x < *xMin) {
 820             continue;
 821           }
 822         }
 823
 824         // check: below bottom limit?
 825         if (!bottom && blk->yMax > *yMax) {
 826           if (x > *xMax) {
 827             return gFalse;
 828           }
 829         }
 830
 831         // compare the strings
 832         for (j = 0; j < len; ++j) {
 833 #if 1 //~ this lowercases Latin A-Z only -- this will eventually be
 834           //~ extended to handle other character sets
 835           if (p[j] >= 0x41 && p[j] <= 0x5a) {
 836             u1 = p[j] + 0x20;
 837           } else {
 838             u1 = p[j];
 839           }
 840           if (s[j] >= 0x41 && s[j] <= 0x5a) {
 841             u2 = s[j] + 0x20;
 842           } else {
 843             u2 = s[j];
 844           }
 845 #endif
 846           if (u1 != u2) {
 847             break;
 848           }
 849         }
 850
 851         // found it
 852         if (j == len) {
 853           *xMin = x0;
 854           *xMax = blk->xRight[i + len - 1];
 855           *yMin = blk->yMin;
 856           *yMax = blk->yMax;
 857           return gTrue;
 858         }
 859       }
 860     }
 861   }
 862
 863   return gFalse;
 864 }
 865
 866 GString *TextPage::getText(double xMin, double yMin,
 867                            double xMax, double yMax) {
 868   GString *s;
 869   UnicodeMap *uMap;
 870   GBool isUnicode;
 871   char space[8], eol[16], buf[8];
 872   int spaceLen, eolLen, len;
 873   TextLine *line;
 874   TextBlock *blk;
 875   double x0, x1, y;
 876   int firstCol, col, i;
 877   GBool multiLine;
 878
 879   s = new GString();
 880
 881   // get the output encoding
 882   if (!(uMap = globalParams->getTextEncoding())) {
 883     return s;
 884   }
 885   isUnicode = uMap->isUnicode();
 886   spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
 887   eolLen = 0; // make gcc happy
 888   switch (globalParams->getTextEOL()) {
 889   case eolUnix:
 890     eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
 891     break;
 892   case eolDOS:
 893     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
 894     eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
 895     break;
 896   case eolMac:
 897     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
 898     break;
 899   }
 900
 901   // find the leftmost column
 902   multiLine = gFalse;
 903   firstCol = -1;
 904   for (line = lines; line; line = line->next) {
 905     if (line->yMin > yMax) {
 906       break;
 907     }
 908     if (line->yMax < yMin) {
 909       continue;
 910     }
 911
 912     for (blk = line->blocks; blk && blk->xMax < xMin; blk = blk->next) ;
 913     if (!blk || blk->xMin > xMax) {
 914       continue;
 915     }
 916
 917     y = 0.5 * (blk->yMin + blk->yMax);
 918     if (y < yMin || y > yMax) {
 919       continue;
 920     }
 921
 922     if (firstCol >= 0) {
 923       multiLine = gTrue;
 924     }
 925
 926     i = 0;
 927     while (1) {
 928       x0 = (i==0) ? blk->xMin : blk->xRight[i-1];
 929       x1 = blk->xRight[i];
 930       if (0.5 * (x0 + x1) > xMin) {
 931         break;
 932       }
 933       ++i;
 934     }
 935     col = blk->col[i];
 936
 937     if (firstCol < 0 || col < firstCol) {
 938       firstCol = col;
 939     }
 940   }
 941
 942   // extract the text
 943   for (line = lines; line; line = line->next) {
 944     if (line->yMin > yMax) {
 945       break;
 946     }
 947     if (line->yMax < yMin) {
 948       continue;
 949     }
 950
 951     for (blk = line->blocks; blk && blk->xMax < xMin; blk = blk->next) ;
 952     if (!blk || blk->xMin > xMax) {
 953       continue;
 954     }
 955
 956     y = 0.5 * (blk->yMin + blk->yMax);
 957     if (y < yMin || y > yMax) {
 958       continue;
 959     }
 960
 961     i = 0;
 962     while (1) {
 963       x0 = (i==0) ? blk->xMin : blk->xRight[i-1];
 964       x1 = blk->xRight[i];
 965       if (0.5 * (x0 + x1) > xMin) {
 966         break;
 967       }
 968       ++i;
 969     }
 970
 971     col = firstCol;
 972
 973     do {
 974
 975       // line this block up with the correct column
 976       for (; col < blk->col[i]; ++col) {
 977         s->append(space, spaceLen);
 978       }
 979
 980       // print the block
 981       for (; i < blk->len; ++i) {
 982
 983         x0 = (i==0) ? blk->xMin : blk->xRight[i-1];
 984         x1 = blk->xRight[i];
 985         if (0.5 * (x0 + x1) > xMax) {
 986           break;
 987         }
 988
 989         len = uMap->mapUnicode(blk->text[i], buf, sizeof(buf));
 990         s->append(buf, len);
 991         col += isUnicode ? 1 : len;
 992       }
 993       if (i < blk->len) {
 994         break;
 995       }
 996
 997       // next block
 998       blk = blk->next;
 999       i = 0;
1000
1001     } while (blk && blk->xMin < xMax);
1002
1003     if (multiLine) {
1004       s->append(eol, eolLen);
1005     }
1006   }
1007
1008   uMap->decRefCnt();
1009
1010   return s;
1011 }
1012
1013 void TextPage::dump(void *outputStream, TextOutputFunc outputFunc) {
1014   UnicodeMap *uMap;
1015   char space[8], eol[16], eop[8], buf[8];
1016   int spaceLen, eolLen, eopLen, len;
1017   TextLine *line;
1018   TextBlock *blk;
1019   int col, d, i;
1020
1021   // get the output encoding
1022   if (!(uMap = globalParams->getTextEncoding())) {
1023     return;
1024   }
1025   spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
1026   eolLen = 0; // make gcc happy
1027   switch (globalParams->getTextEOL()) {
1028   case eolUnix:
1029     eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
1030     break;
1031   case eolDOS:
1032     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
1033     eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
1034     break;
1035   case eolMac:
1036     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
1037     break;
1038   }
1039   eopLen = uMap->mapUnicode(0x0c, eop, sizeof(eop));
1040
1041   // output
1042   for (line = lines; line; line = line->next) {
1043     col = 0;
1044     for (blk = line->blocks; blk; blk = blk->next) {
1045
1046       // line this block up with the correct column
1047       if (rawOrder && col == 0) {
1048         col = blk->col[0];
1049       } else {
1050         for (; col < blk->col[0]; ++col) {
1051           (*outputFunc)(outputStream, space, spaceLen);
1052         }
1053       }
1054
1055       // print the block
1056       for (i = 0; i < blk->len; ++i) {
1057         len = uMap->mapUnicode(blk->text[i], buf, sizeof(buf));
1058         (*outputFunc)(outputStream, buf, len);
1059       }
1060       col += blk->convertedLen;
1061     }
1062
1063     // print a return
1064     (*outputFunc)(outputStream, eol, eolLen);
1065
1066     // print extra vertical space if necessary
1067     if (line->next) {
1068       d = (int)((line->next->yMin - line->yMax) /
1069                 (line->blocks->strings->yMax - lines->blocks->strings->yMin)
1070                 + 0.5);
1071       // various things (weird font matrices) can result in bogus
1072       // values here, so do a sanity check
1073       if (rawOrder && d > 2) {
1074         d = 2;
1075       } else if (!rawOrder && d > 5) {
1076         d = 5;
1077       }
1078       for (; d > 0; --d) {
1079         (*outputFunc)(outputStream, eol, eolLen);
1080       }
1081     }
1082   }
1083
1084   // end of page
1085   (*outputFunc)(outputStream, eol, eolLen);
1086   (*outputFunc)(outputStream, eop, eopLen);
1087   (*outputFunc)(outputStream, eol, eolLen);
1088
1089   uMap->decRefCnt();
1090 }
1091
1092 // Returns true if <str1> should be inserted before <str2> in xy
1093 // order.
1094 GBool TextPage::xyBefore(TextString *str1, TextString *str2) {
1095   return str1->xMin < str2->xMin ||
1096          (str1->xMin == str2->xMin && str1->yMin < str2->yMin);
1097 }
1098
1099 // Returns true if <blk1> should be inserted before <blk2> in xy
1100 // order.
1101 GBool TextPage::xyBefore(TextBlock *blk1, TextBlock *blk2) {
1102   return blk1->xMin < blk2->xMin ||
1103          (blk1->xMin == blk2->xMin && blk1->yMin < blk2->yMin);
1104 }
1105
1106 // Returns true if <blk1> should be inserted before <blk2> in yx
1107 // order, allowing a little slack for vertically overlapping text.
1108 GBool TextPage::yxBefore(TextBlock *blk1, TextBlock *blk2) {
1109   double h1, h2, overlap;
1110
1111   h1 = blk1->yMax - blk1->yMin;
1112   h2 = blk2->yMax - blk2->yMin;
1113   overlap = ((blk1->yMax < blk2->yMax ? blk1->yMax : blk2->yMax) -
1114              (blk1->yMin > blk2->yMin ? blk1->yMin : blk2->yMin)) /
1115             (h1 < h2 ? h1 : h2);
1116   if (overlap > 0.6) {
1117     return blk1->xMin < blk2->xMin;
1118   }
1119   return blk1->yMin < blk2->yMin;
1120 }
1121
1122 double TextPage::coalesceFit(TextString *str1, TextString *str2) {
1123   double h1, h2, w1, w2, r, overlap, spacing;
1124
1125   h1 = str1->yMax - str1->yMin;
1126   h2 = str2->yMax - str2->yMin;
1127   w1 = str1->xMax - str1->xMin;
1128   w2 = str2->xMax - str2->xMin;
1129   r = h1 / h2;
1130   if (r < (1.0 / 3.0) || r > 3) {
1131     return 10;
1132   }
1133   overlap = ((str1->yMax < str2->yMax ? str1->yMax : str2->yMax) -
1134              (str1->yMin > str2->yMin ? str1->yMin : str2->yMin)) /
1135             (h1 < h2 ? h1 : h2);
1136   if (overlap < 0.5) {
1137     return 10;
1138   }
1139   spacing = (str2->xMin - str1->xMax) / (h1 > h2 ? h1 : h2);
1140   if (spacing < -0.5) {
1141     return 10;
1142   }
1143   // separate text that overlaps - duplicated text (so that fake
1144   // boldface and shadowed text can be cleanly removed)
1145   if ((str2->xMin - str1->xMax) / (w1 < w2 ? w1 : w2) < -0.7) {
1146     return 10;
1147   }
1148   return spacing;
1149 }
1150
1151 void TextPage::clear() {
1152   TextLine *p1, *p2;
1153   TextString *s1, *s2;
1154
1155   if (curStr) {
1156     delete curStr;
1157     curStr = NULL;
1158   }
1159   if (lines) {
1160     for (p1 = lines; p1; p1 = p2) {
1161       p2 = p1->next;
1162       delete p1;
1163     }
1164   } else if (xyStrings) {
1165     for (s1 = xyStrings; s1; s1 = s2) {
1166       s2 = s1->next;
1167       delete s1;
1168     }
1169   }
1170   xyStrings = NULL;
1171   xyCur1 = xyCur2 = NULL;
1172   lines = NULL;
1173   nest = 0;
1174   nTinyChars = 0;
1175 }
1176
1177 //------------------------------------------------------------------------
1178 // TextOutputDev
1179 //------------------------------------------------------------------------
1180
1181 static void outputToFile(void *stream, char *text, int len) {
1182   fwrite(text, 1, len, (FILE *)stream);
1183 }
1184
1185 TextOutputDev::TextOutputDev(char *fileName, GBool rawOrderA, GBool append) {
1186   text = NULL;
1187   rawOrder = rawOrderA;
1188   ok = gTrue;
1189
1190   // open file
1191   needClose = gFalse;
1192   if (fileName) {
1193     if (!strcmp(fileName, "-")) {
1194       outputStream = stdout;
1195     } else if ((outputStream = fopen(fileName, append ? "ab" : "wb"))) {
1196       needClose = gTrue;
1197     } else {
1198       error(-1, "Couldn't open text file '%s'", fileName);
1199       ok = gFalse;
1200       return;
1201     }
1202     outputFunc = &outputToFile;
1203   } else {
1204     outputStream = NULL;
1205   }
1206
1207   // set up text object
1208   text = new TextPage(rawOrder);
1209 }
1210
1211 TextOutputDev::TextOutputDev(TextOutputFunc func, void *stream,
1212                              GBool rawOrderA) {
1213   outputFunc = func;
1214   outputStream = stream;
1215   needClose = gFalse;
1216   rawOrder = rawOrderA;
1217   text = new TextPage(rawOrder);
1218   ok = gTrue;
1219 }
1220
1221 TextOutputDev::~TextOutputDev() {
1222   if (needClose) {
1223 #ifdef MACOS
1224     ICS_MapRefNumAndAssign((short)((FILE *)outputStream)->handle);
1225 #endif
1226     fclose((FILE *)outputStream);
1227   }
1228   if (text) {
1229     delete text;
1230   }
1231 }
1232
1233 void TextOutputDev::startPage(int pageNum, GfxState *state) {
1234   text->clear();
1235 }
1236
1237 void TextOutputDev::endPage() {
1238   text->coalesce();
1239   if (outputStream) {
1240     text->dump(outputStream, outputFunc);
1241   }
1242 }
1243
1244 void TextOutputDev::updateFont(GfxState *state) {
1245   text->updateFont(state);
1246 }
1247
1248 void TextOutputDev::beginString(GfxState *state, GString *s) {
1249   text->beginString(state, state->getCurX(), state->getCurY());
1250 }
1251
1252 void TextOutputDev::endString(GfxState *state) {
1253   text->endString();
1254 }
1255
1256 void TextOutputDev::drawChar(GfxState *state, double x, double y,
1257                              double dx, double dy,
1258                              double originX, double originY,
1259                              CharCode c, Unicode *u, int uLen) {
1260   text->addChar(state, x, y, dx, dy, u, uLen);
1261 }
1262
1263 GBool TextOutputDev::findText(Unicode *s, int len,
1264                               GBool top, GBool bottom,
1265                               double *xMin, double *yMin,
1266                               double *xMax, double *yMax) {
1267   return text->findText(s, len, top, bottom, xMin, yMin, xMax, yMax);
1268 }
1269
1270 GString *TextOutputDev::getText(double xMin, double yMin,
1271                                 double xMax, double yMax) {
1272   return text->getText(xMin, yMin, xMax, yMax);
1273 }
1274