pdf/xpdf/TextOutputDev.cc

   1 //========================================================================
   2 //
   3 // TextOutputDev.cc
   4 //
   5 // Copyright 1997-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 <stdio.h>
  16 #include <stdlib.h>
  17 #include <stddef.h>
  18 #include <math.h>
  19 #include <ctype.h>
  20 #ifdef WIN32
  21 #include <fcntl.h> // for O_BINARY
  22 #include <io.h>    // for setmode
  23 #endif
  24 #include "gmem.h"
  25 #include "GString.h"
  26 #include "GList.h"
  27 #include "config.h"
  28 #include "Error.h"
  29 #include "GlobalParams.h"
  30 #include "UnicodeMap.h"
  31 #include "UnicodeTypeTable.h"
  32 #include "GfxState.h"
  33 #include "TextOutputDev.h"
  34
  35 #ifdef MACOS
  36 // needed for setting type/creator of MacOS files
  37 #include "ICSupport.h"
  38 #endif
  39
  40 //------------------------------------------------------------------------
  41 // parameters
  42 //------------------------------------------------------------------------
  43
  44 // Each bucket in a text pool includes baselines within a range of
  45 // this many points.
  46 #define textPoolStep 4
  47
  48 // Inter-character space width which will cause addChar to break up a
  49 // text string.
  50 #define defaultSpaceWidth 0.25
  51
  52 // Max distance between baselines of two lines within a block, as a
  53 // fraction of the font size.
  54 #define maxLineSpacingDelta 1.5
  55
  56 // Max difference in primary font sizes on two lines in the same
  57 // block.  Delta1 is used when examining new lines above and below the
  58 // current block; delta2 is used when examining text that overlaps the
  59 // current block; delta3 is used when examining text to the left and
  60 // right of the current block.
  61 #define maxBlockFontSizeDelta1 0.05
  62 #define maxBlockFontSizeDelta2 0.6
  63 #define maxBlockFontSizeDelta3 0.2
  64
  65 // Max difference in font sizes inside a word.
  66 #define maxWordFontSizeDelta 0.05
  67
  68 // Maximum distance between baselines of two words on the same line,
  69 // e.g., distance between subscript or superscript and the primary
  70 // baseline, as a fraction of the font size.
  71 #define maxIntraLineDelta 0.5
  72
  73 // Minimum inter-word spacing, as a fraction of the font size.  (Only
  74 // used for raw ordering.)
  75 #define minWordSpacing 0.2
  76
  77 // Maximum inter-word spacing, as a fraction of the font size.
  78 #define maxWordSpacing 1.5
  79
  80 // Minimum spacing between columns, as a fraction of the font size.
  81 #define minColSpacing 1.0
  82
  83 // Maximum vertical spacing between blocks within a flow, as a
  84 // multiple of the font size.
  85 #define maxBlockSpacing 2.5
  86
  87 // Minimum spacing between characters within a word, as a fraction of
  88 // the font size.
  89 #define minCharSpacing -0.2
  90
  91 // Maximum spacing between characters within a word, as a fraction of
  92 // the font size, when there is no obvious extra-wide character
  93 // spacing.
  94 #define maxCharSpacing 0.03
  95
  96 // When extra-wide character spacing is detected, the inter-character
  97 // space threshold is set to the minimum inter-character space
  98 // multiplied by this constant.
  99 #define maxWideCharSpacingMul 1.3
 100
 101 // Max difference in primary,secondary coordinates (as a fraction of
 102 // the font size) allowed for duplicated text (fake boldface, drop
 103 // shadows) which is to be discarded.
 104 #define dupMaxPriDelta 0.1
 105 #define dupMaxSecDelta 0.2
 106
 107 //------------------------------------------------------------------------
 108 // TextFontInfo
 109 //------------------------------------------------------------------------
 110
 111 TextFontInfo::TextFontInfo(GfxState *state) {
 112   gfxFont = state->getFont();
 113 #if TEXTOUT_WORD_LIST
 114   fontName = (gfxFont && gfxFont->getOrigName())
 115                  ? gfxFont->getOrigName()->copy()
 116                  : (GString *)NULL;
 117 #endif
 118 }
 119
 120 TextFontInfo::~TextFontInfo() {
 121 #if TEXTOUT_WORD_LIST
 122   if (fontName) {
 123     delete fontName;
 124   }
 125 #endif
 126 }
 127
 128 GBool TextFontInfo::matches(GfxState *state) {
 129   return state->getFont() == gfxFont;
 130 }
 131
 132 //------------------------------------------------------------------------
 133 // TextWord
 134 //------------------------------------------------------------------------
 135
 136 TextWord::TextWord(GfxState *state, int rotA, double x0, double y0,
 137                    int charPosA, TextFontInfo *fontA, double fontSizeA) {
 138   GfxFont *gfxFont;
 139   double x, y, ascent, descent;
 140
 141   rot = rotA;
 142   charPos = charPosA;
 143   charLen = 0;
 144   font = fontA;
 145   fontSize = fontSizeA;
 146   state->transform(x0, y0, &x, &y);
 147   if ((gfxFont = font->gfxFont)) {
 148     ascent = gfxFont->getAscent() * fontSize;
 149     descent = gfxFont->getDescent() * fontSize;
 150   } else {
 151     // this means that the PDF file draws text without a current font,
 152     // which should never happen
 153     ascent = 0.95 * fontSize;
 154     descent = -0.35 * fontSize;
 155   }
 156   switch (rot) {
 157   case 0:
 158     yMin = y - ascent;
 159     yMax = y - descent;
 160     if (yMin == yMax) {
 161       // this is a sanity check for a case that shouldn't happen -- but
 162       // if it does happen, we want to avoid dividing by zero later
 163       yMin = y;
 164       yMax = y + 1;
 165     }
 166     base = y;
 167     break;
 168   case 1:
 169     xMin = x + descent;
 170     xMax = x + ascent;
 171     if (xMin == xMax) {
 172       // this is a sanity check for a case that shouldn't happen -- but
 173       // if it does happen, we want to avoid dividing by zero later
 174       xMin = x;
 175       xMax = x + 1;
 176     }
 177     base = x;
 178     break;
 179   case 2:
 180     yMin = y + descent;
 181     yMax = y + ascent;
 182     if (yMin == yMax) {
 183       // this is a sanity check for a case that shouldn't happen -- but
 184       // if it does happen, we want to avoid dividing by zero later
 185       yMin = y;
 186       yMax = y + 1;
 187     }
 188     base = y;
 189     break;
 190   case 3:
 191     xMin = x - ascent;
 192     xMax = x - descent;
 193     if (xMin == xMax) {
 194       // this is a sanity check for a case that shouldn't happen -- but
 195       // if it does happen, we want to avoid dividing by zero later
 196       xMin = x;
 197       xMax = x + 1;
 198     }
 199     base = x;
 200     break;
 201   }
 202   text = NULL;
 203   edge = NULL;
 204   len = size = 0;
 205   spaceAfter = gFalse;
 206   next = NULL;
 207
 208 #if TEXTOUT_WORD_LIST
 209   GfxRGB rgb;
 210
 211   if ((state->getRender() & 3) == 1) {
 212     state->getStrokeRGB(&rgb);
 213   } else {
 214     state->getFillRGB(&rgb);
 215   }
 216   colorR = rgb.r;
 217   colorG = rgb.g;
 218   colorB = rgb.b;
 219 #endif
 220 }
 221
 222 TextWord::~TextWord() {
 223   gfree(text);
 224   gfree(edge);
 225 }
 226
 227 void TextWord::addChar(GfxState *state, double x, double y,
 228                        double dx, double dy, Unicode u) {
 229   if (len == size) {
 230     size += 16;
 231     text = (Unicode *)grealloc(text, size * sizeof(Unicode));
 232     edge = (double *)grealloc(edge, (size + 1) * sizeof(double));
 233   }
 234   text[len] = u;
 235   switch (rot) {
 236   case 0:
 237     if (len == 0) {
 238       xMin = x;
 239     }
 240     edge[len] = x;
 241     xMax = edge[len+1] = x + dx;
 242     break;
 243   case 1:
 244     if (len == 0) {
 245       yMin = y;
 246     }
 247     edge[len] = y;
 248     yMax = edge[len+1] = y + dy;
 249     break;
 250   case 2:
 251     if (len == 0) {
 252       xMax = x;
 253     }
 254     edge[len] = x;
 255     xMin = edge[len+1] = x + dx;
 256     break;
 257   case 3:
 258     if (len == 0) {
 259       yMax = y;
 260     }
 261     edge[len] = y;
 262     yMin = edge[len+1] = y + dy;
 263     break;
 264   }
 265   ++len;
 266 }
 267
 268 void TextWord::merge(TextWord *word) {
 269   int i;
 270
 271   if (word->xMin < xMin) {
 272     xMin = word->xMin;
 273   }
 274   if (word->yMin < yMin) {
 275     yMin = word->yMin;
 276   }
 277   if (word->xMax > xMax) {
 278     xMax = word->xMax;
 279   }
 280   if (word->yMax > yMax) {
 281     yMax = word->yMax;
 282   }
 283   if (len + word->len > size) {
 284     size = len + word->len;
 285     text = (Unicode *)grealloc(text, size * sizeof(Unicode));
 286     edge = (double *)grealloc(edge, (size + 1) * sizeof(double));
 287   }
 288   for (i = 0; i < word->len; ++i) {
 289     text[len + i] = word->text[i];
 290     edge[len + i] = word->edge[i];
 291   }
 292   edge[len + word->len] = word->edge[word->len];
 293   len += word->len;
 294   charLen += word->charLen;
 295 }
 296
 297 inline int TextWord::primaryCmp(TextWord *word) {
 298   double cmp;
 299
 300   cmp = 0; // make gcc happy
 301   switch (rot) {
 302   case 0:
 303     cmp = xMin - word->xMin;
 304     break;
 305   case 1:
 306     cmp = yMin - word->yMin;
 307     break;
 308   case 2:
 309     cmp = word->xMax - xMax;
 310     break;
 311   case 3:
 312     cmp = word->yMax - yMax;
 313     break;
 314   }
 315   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 316 }
 317
 318 double TextWord::primaryDelta(TextWord *word) {
 319   double delta;
 320
 321   delta = 0; // make gcc happy
 322   switch (rot) {
 323   case 0:
 324     delta = word->xMin - xMax;
 325     break;
 326   case 1:
 327     delta = word->yMin - yMax;
 328     break;
 329   case 2:
 330     delta = xMin - word->xMax;
 331     break;
 332   case 3:
 333     delta = yMin - word->yMax;
 334     break;
 335   }
 336   return delta;
 337 }
 338
 339 int TextWord::cmpYX(const void *p1, const void *p2) {
 340   TextWord *word1 = *(TextWord **)p1;
 341   TextWord *word2 = *(TextWord **)p2;
 342   double cmp;
 343
 344   cmp = word1->yMin - word2->yMin;
 345   if (cmp == 0) {
 346     cmp = word1->xMin - word2->xMin;
 347   }
 348   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 349 }
 350
 351 #if TEXTOUT_WORD_LIST
 352
 353 GString *TextWord::getText() {
 354   GString *s;
 355   UnicodeMap *uMap;
 356   char buf[8];
 357   int n, i;
 358
 359   s = new GString();
 360   if (!(uMap = globalParams->getTextEncoding())) {
 361     return s;
 362   }
 363   for (i = 0; i < len; ++i) {
 364     n = uMap->mapUnicode(text[i], buf, sizeof(buf));
 365     s->append(buf, n);
 366   }
 367   uMap->decRefCnt();
 368   return s;
 369 }
 370
 371 #endif // TEXTOUT_WORD_LIST
 372
 373 //------------------------------------------------------------------------
 374 // TextPool
 375 //------------------------------------------------------------------------
 376
 377 TextPool::TextPool() {
 378   minBaseIdx = 0;
 379   maxBaseIdx = -1;
 380   pool = NULL;
 381   cursor = NULL;
 382   cursorBaseIdx = -1;
 383 }
 384
 385 TextPool::~TextPool() {
 386   int baseIdx;
 387   TextWord *word, *word2;
 388
 389   for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
 390     for (word = pool[baseIdx - minBaseIdx]; word; word = word2) {
 391       word2 = word->next;
 392       delete word;
 393     }
 394   }
 395   gfree(pool);
 396 }
 397
 398 int TextPool::getBaseIdx(double base) {
 399   int baseIdx;
 400
 401   baseIdx = (int)(base / textPoolStep);
 402   if (baseIdx < minBaseIdx) {
 403     return minBaseIdx;
 404   }
 405   if (baseIdx > maxBaseIdx) {
 406     return maxBaseIdx;
 407   }
 408   return baseIdx;
 409 }
 410
 411 void TextPool::addWord(TextWord *word) {
 412   TextWord **newPool;
 413   int wordBaseIdx, newMinBaseIdx, newMaxBaseIdx, baseIdx;
 414   TextWord *w0, *w1;
 415
 416   // expand the array if needed
 417   wordBaseIdx = (int)(word->base / textPoolStep);
 418   if (minBaseIdx > maxBaseIdx) {
 419     minBaseIdx = wordBaseIdx - 128;
 420     maxBaseIdx = wordBaseIdx + 128;
 421     pool = (TextWord **)gmalloc((maxBaseIdx - minBaseIdx + 1) *
 422                                 sizeof(TextWord *));
 423     for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
 424       pool[baseIdx - minBaseIdx] = NULL;
 425     }
 426   } else if (wordBaseIdx < minBaseIdx) {
 427     newMinBaseIdx = wordBaseIdx - 128;
 428     newPool = (TextWord **)gmalloc((maxBaseIdx - newMinBaseIdx + 1) *
 429                                    sizeof(TextWord *));
 430     for (baseIdx = newMinBaseIdx; baseIdx < minBaseIdx; ++baseIdx) {
 431       newPool[baseIdx - newMinBaseIdx] = NULL;
 432     }
 433     memcpy(&newPool[minBaseIdx - newMinBaseIdx], pool,
 434            (maxBaseIdx - minBaseIdx + 1) * sizeof(TextWord *));
 435     gfree(pool);
 436     pool = newPool;
 437     minBaseIdx = newMinBaseIdx;
 438   } else if (wordBaseIdx > maxBaseIdx) {
 439     newMaxBaseIdx = wordBaseIdx + 128;
 440     pool = (TextWord **)grealloc(pool, (newMaxBaseIdx - minBaseIdx + 1) *
 441                                          sizeof(TextWord *));
 442     for (baseIdx = maxBaseIdx + 1; baseIdx <= newMaxBaseIdx; ++baseIdx) {
 443       pool[baseIdx - minBaseIdx] = NULL;
 444     }
 445     maxBaseIdx = newMaxBaseIdx;
 446   }
 447
 448   // insert the new word
 449   if (cursor && wordBaseIdx == cursorBaseIdx &&
 450       word->primaryCmp(cursor) > 0) {
 451     w0 = cursor;
 452     w1 = cursor->next;
 453   } else {
 454     w0 = NULL;
 455     w1 = pool[wordBaseIdx - minBaseIdx];
 456   }
 457   for (; w1 && word->primaryCmp(w1) > 0; w0 = w1, w1 = w1->next) ;
 458   word->next = w1;
 459   if (w0) {
 460     w0->next = word;
 461   } else {
 462     pool[wordBaseIdx - minBaseIdx] = word;
 463   }
 464   cursor = word;
 465   cursorBaseIdx = wordBaseIdx;
 466 }
 467
 468 //------------------------------------------------------------------------
 469 // TextLine
 470 //------------------------------------------------------------------------
 471
 472 TextLine::TextLine(TextBlock *blkA, int rotA, double baseA) {
 473   blk = blkA;
 474   rot = rotA;
 475   xMin = yMin = 0;
 476   xMax = yMax = -1;
 477   base = baseA;
 478   words = lastWord = NULL;
 479   text = NULL;
 480   edge = NULL;
 481   col = NULL;
 482   len = 0;
 483   convertedLen = 0;
 484   hyphenated = gFalse;
 485   next = NULL;
 486 }
 487
 488 TextLine::~TextLine() {
 489   TextWord *word;
 490
 491   while (words) {
 492     word = words;
 493     words = words->next;
 494     delete word;
 495   }
 496   gfree(text);
 497   gfree(edge);
 498   gfree(col);
 499 }
 500
 501 void TextLine::addWord(TextWord *word) {
 502   if (lastWord) {
 503     lastWord->next = word;
 504   } else {
 505     words = word;
 506   }
 507   lastWord = word;
 508
 509   if (xMin > xMax) {
 510     xMin = word->xMin;
 511     xMax = word->xMax;
 512     yMin = word->yMin;
 513     yMax = word->yMax;
 514   } else {
 515     if (word->xMin < xMin) {
 516       xMin = word->xMin;
 517     }
 518     if (word->xMax > xMax) {
 519       xMax = word->xMax;
 520     }
 521     if (word->yMin < yMin) {
 522       yMin = word->yMin;
 523     }
 524     if (word->yMax > yMax) {
 525       yMax = word->yMax;
 526     }
 527   }
 528 }
 529
 530 double TextLine::primaryDelta(TextLine *line) {
 531   double delta;
 532
 533   delta = 0; // make gcc happy
 534   switch (rot) {
 535   case 0:
 536     delta = line->xMin - xMax;
 537     break;
 538   case 1:
 539     delta = line->yMin - yMax;
 540     break;
 541   case 2:
 542     delta = xMin - line->xMax;
 543     break;
 544   case 3:
 545     delta = yMin - line->yMax;
 546     break;
 547   }
 548   return delta;
 549 }
 550
 551 int TextLine::primaryCmp(TextLine *line) {
 552   double cmp;
 553
 554   cmp = 0; // make gcc happy
 555   switch (rot) {
 556   case 0:
 557     cmp = xMin - line->xMin;
 558     break;
 559   case 1:
 560     cmp = yMin - line->yMin;
 561     break;
 562   case 2:
 563     cmp = line->xMax - xMax;
 564     break;
 565   case 3:
 566     cmp = line->yMax - yMax;
 567     break;
 568   }
 569   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 570 }
 571
 572 int TextLine::secondaryCmp(TextLine *line) {
 573   double cmp;
 574
 575   cmp = (rot == 0 || rot == 3) ? base - line->base : line->base - base;
 576   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 577 }
 578
 579 int TextLine::cmpYX(TextLine *line) {
 580   int cmp;
 581
 582   if ((cmp = secondaryCmp(line))) {
 583     return cmp;
 584   }
 585   return primaryCmp(line);
 586 }
 587
 588 int TextLine::cmpXY(const void *p1, const void *p2) {
 589   TextLine *line1 = *(TextLine **)p1;
 590   TextLine *line2 = *(TextLine **)p2;
 591   int cmp;
 592
 593   if ((cmp = line1->primaryCmp(line2))) {
 594     return cmp;
 595   }
 596   return line1->secondaryCmp(line2);
 597 }
 598
 599 void TextLine::coalesce(UnicodeMap *uMap) {
 600   TextWord *word0, *word1;
 601   double space, delta, minSpace;
 602   GBool isUnicode;
 603   char buf[8];
 604   int i, j;
 605
 606   if (words->next) {
 607
 608     // compute the inter-word space threshold
 609     if (words->len > 1 || words->next->len > 1) {
 610       minSpace = 0;
 611     } else {
 612       minSpace = words->primaryDelta(words->next);
 613       for (word0 = words->next, word1 = word0->next;
 614            word1 && minSpace > 0;
 615            word0 = word1, word1 = word0->next) {
 616         if (word1->len > 1) {
 617           minSpace = 0;
 618         }
 619         delta = word0->primaryDelta(word1);
 620         if (delta < minSpace) {
 621           minSpace = delta;
 622         }
 623       }
 624     }
 625     if (minSpace <= 0) {
 626       space = maxCharSpacing * words->fontSize;
 627     } else {
 628       space = maxWideCharSpacingMul * minSpace;
 629     }
 630
 631     // merge words
 632     word0 = words;
 633     word1 = words->next;
 634     while (word1) {
 635       if (word0->primaryDelta(word1) >= space) {
 636         word0->spaceAfter = gTrue;
 637         word0 = word1;
 638         word1 = word1->next;
 639       } else if (word0->font == word1->font &&
 640                  fabs(word0->fontSize - word1->fontSize) <
 641                  maxWordFontSizeDelta * words->fontSize &&
 642                  word1->charPos == word0->charPos + word0->charLen) {
 643         word0->merge(word1);
 644         word0->next = word1->next;
 645         delete word1;
 646         word1 = word0->next;
 647       } else {
 648         word0 = word1;
 649         word1 = word1->next;
 650       }
 651     }
 652   }
 653
 654   // build the line text
 655   isUnicode = uMap ? uMap->isUnicode() : gFalse;
 656   len = 0;
 657   for (word1 = words; word1; word1 = word1->next) {
 658     len += word1->len;
 659     if (word1->spaceAfter) {
 660       ++len;
 661     }
 662   }
 663   text = (Unicode *)gmalloc(len * sizeof(Unicode));
 664   edge = (double *)gmalloc((len + 1) * sizeof(double));
 665   i = 0;
 666   for (word1 = words; word1; word1 = word1->next) {
 667     for (j = 0; j < word1->len; ++j) {
 668       text[i] = word1->text[j];
 669       edge[i] = word1->edge[j];
 670       ++i;
 671     }
 672     edge[i] = word1->edge[word1->len];
 673     if (word1->spaceAfter) {
 674       text[i] = (Unicode)0x0020;
 675       ++i;
 676     }
 677   }
 678
 679   // compute convertedLen and set up the col array
 680   col = (int *)gmalloc((len + 1) * sizeof(int));
 681   convertedLen = 0;
 682   for (i = 0; i < len; ++i) {
 683     col[i] = convertedLen;
 684     if (isUnicode) {
 685       ++convertedLen;
 686     } else if (uMap) {
 687       convertedLen += uMap->mapUnicode(text[i], buf, sizeof(buf));
 688     }
 689   }
 690   col[len] = convertedLen;
 691
 692   // check for hyphen at end of line
 693   //~ need to check for other chars used as hyphens
 694   hyphenated = text[len - 1] == (Unicode)'-';
 695 }
 696
 697 //------------------------------------------------------------------------
 698 // TextLineFrag
 699 //------------------------------------------------------------------------
 700
 701 class TextLineFrag {
 702 public:
 703
 704   TextLine *line;               // the line object
 705   int start, len;               // offset and length of this fragment
 706                                 //   (in Unicode chars)
 707   double xMin, xMax;            // bounding box coordinates
 708   double yMin, yMax;
 709   double base;                  // baseline virtual coordinate
 710   int col;                      // first column
 711
 712   void init(TextLine *lineA, int startA, int lenA);
 713   void computeCoords(GBool oneRot);
 714
 715   static int cmpYXPrimaryRot(const void *p1, const void *p2);
 716   static int cmpYXLineRot(const void *p1, const void *p2);
 717   static int cmpXYLineRot(const void *p1, const void *p2);
 718 };
 719
 720 void TextLineFrag::init(TextLine *lineA, int startA, int lenA) {
 721   line = lineA;
 722   start = startA;
 723   len = lenA;
 724   col = line->col[start];
 725 }
 726
 727 void TextLineFrag::computeCoords(GBool oneRot) {
 728   TextBlock *blk;
 729   double d0, d1, d2, d3, d4;
 730
 731   if (oneRot) {
 732
 733     switch (line->rot) {
 734     case 0:
 735       xMin = line->edge[start];
 736       xMax = line->edge[start + len];
 737       yMin = line->yMin;
 738       yMax = line->yMax;
 739       break;
 740     case 1:
 741       xMin = line->xMin;
 742       xMax = line->xMax;
 743       yMin = line->edge[start];
 744       yMax = line->edge[start + len];
 745       break;
 746     case 2:
 747       xMin = line->edge[start + len];
 748       xMax = line->edge[start];
 749       yMin = line->yMin;
 750       yMax = line->yMax;
 751       break;
 752     case 3:
 753       xMin = line->xMin;
 754       xMax = line->xMax;
 755       yMin = line->edge[start + len];
 756       yMax = line->edge[start];
 757       break;
 758     }
 759     base = line->base;
 760
 761   } else {
 762
 763     if (line->rot == 0 && line->blk->page->primaryRot == 0) {
 764
 765       xMin = line->edge[start];
 766       xMax = line->edge[start + len];
 767       yMin = line->yMin;
 768       yMax = line->yMax;
 769       base = line->base;
 770
 771     } else {
 772
 773       blk = line->blk;
 774       d0 = line->edge[start];
 775       d1 = line->edge[start + len];
 776       d2 = d3 = d4 = 0; // make gcc happy
 777
 778       switch (line->rot) {
 779       case 0:
 780         d2 = line->yMin;
 781         d3 = line->yMax;
 782         d4 = line->base;
 783         d0 = (d0 - blk->xMin) / (blk->xMax - blk->xMin);
 784         d1 = (d1 - blk->xMin) / (blk->xMax - blk->xMin);
 785         d2 = (d2 - blk->yMin) / (blk->yMax - blk->yMin);
 786         d3 = (d3 - blk->yMin) / (blk->yMax - blk->yMin);
 787         d4 = (d4 - blk->yMin) / (blk->yMax - blk->yMin);
 788         break;
 789       case 1:
 790         d2 = line->xMax;
 791         d3 = line->xMin;
 792         d4 = line->base;
 793         d0 = (d0 - blk->yMin) / (blk->yMax - blk->yMin);
 794         d1 = (d1 - blk->yMin) / (blk->yMax - blk->yMin);
 795         d2 = (blk->xMax - d2) / (blk->xMax - blk->xMin);
 796         d3 = (blk->xMax - d3) / (blk->xMax - blk->xMin);
 797         d4 = (blk->xMax - d4) / (blk->xMax - blk->xMin);
 798         break;
 799       case 2:
 800         d2 = line->yMax;
 801         d3 = line->yMin;
 802         d4 = line->base;
 803         d0 = (blk->xMax - d0) / (blk->xMax - blk->xMin);
 804         d1 = (blk->xMax - d1) / (blk->xMax - blk->xMin);
 805         d2 = (blk->yMax - d2) / (blk->yMax - blk->yMin);
 806         d3 = (blk->yMax - d3) / (blk->yMax - blk->yMin);
 807         d4 = (blk->yMax - d4) / (blk->yMax - blk->yMin);
 808         break;
 809       case 3:
 810         d2 = line->xMin;
 811         d3 = line->xMax;
 812         d4 = line->base;
 813         d0 = (blk->yMax - d0) / (blk->yMax - blk->yMin);
 814         d1 = (blk->yMax - d1) / (blk->yMax - blk->yMin);
 815         d2 = (d2 - blk->xMin) / (blk->xMax - blk->xMin);
 816         d3 = (d3 - blk->xMin) / (blk->xMax - blk->xMin);
 817         d4 = (d4 - blk->xMin) / (blk->xMax - blk->xMin);
 818         break;
 819       }
 820
 821       switch (line->blk->page->primaryRot) {
 822       case 0:
 823         xMin = blk->xMin + d0 * (blk->xMax - blk->xMin);
 824         xMax = blk->xMin + d1 * (blk->xMax - blk->xMin);
 825         yMin = blk->yMin + d2 * (blk->yMax - blk->yMin);
 826         yMax = blk->yMin + d3 * (blk->yMax - blk->yMin);
 827         base = blk->yMin + base * (blk->yMax - blk->yMin);
 828         break;
 829       case 1:
 830         xMin = blk->xMax - d3 * (blk->xMax - blk->xMin);
 831         xMax = blk->xMax - d2 * (blk->xMax - blk->xMin);
 832         yMin = blk->yMin + d0 * (blk->yMax - blk->yMin);
 833         yMax = blk->yMin + d1 * (blk->yMax - blk->yMin);
 834         base = blk->xMax - d4 * (blk->xMax - blk->xMin);
 835         break;
 836       case 2:
 837         xMin = blk->xMax - d1 * (blk->xMax - blk->xMin);
 838         xMax = blk->xMax - d0 * (blk->xMax - blk->xMin);
 839         yMin = blk->yMax - d3 * (blk->yMax - blk->yMin);
 840         yMax = blk->yMax - d2 * (blk->yMax - blk->yMin);
 841         base = blk->yMax - d4 * (blk->yMax - blk->yMin);
 842         break;
 843       case 3:
 844         xMin = blk->xMin + d2 * (blk->xMax - blk->xMin);
 845         xMax = blk->xMin + d3 * (blk->xMax - blk->xMin);
 846         yMin = blk->yMax - d1 * (blk->yMax - blk->yMin);
 847         yMax = blk->yMax - d0 * (blk->yMax - blk->yMin);
 848         base = blk->xMin + d4 * (blk->xMax - blk->xMin);
 849         break;
 850       }
 851
 852     }
 853   }
 854 }
 855
 856 int TextLineFrag::cmpYXPrimaryRot(const void *p1, const void *p2) {
 857   TextLineFrag *frag1 = (TextLineFrag *)p1;
 858   TextLineFrag *frag2 = (TextLineFrag *)p2;
 859   double cmp;
 860
 861   cmp = 0; // make gcc happy
 862   switch (frag1->line->blk->page->primaryRot) {
 863   case 0:
 864     if ((cmp = frag1->yMin - frag2->yMin) == 0) {
 865       cmp = frag1->xMin - frag2->xMin;
 866     }
 867     break;
 868   case 1:
 869     if ((cmp = frag2->xMax - frag1->xMax) == 0) {
 870       cmp = frag1->yMin - frag2->yMin;
 871     }
 872     break;
 873   case 2:
 874     if ((cmp = frag2->yMin - frag1->yMin) == 0) {
 875       cmp = frag2->xMax - frag1->xMax;
 876     }
 877     break;
 878   case 3:
 879     if ((cmp = frag1->xMax - frag2->xMax) == 0) {
 880       cmp = frag2->yMax - frag1->yMax;
 881     }
 882     break;
 883   }
 884   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 885 }
 886
 887 int TextLineFrag::cmpYXLineRot(const void *p1, const void *p2) {
 888   TextLineFrag *frag1 = (TextLineFrag *)p1;
 889   TextLineFrag *frag2 = (TextLineFrag *)p2;
 890   double cmp;
 891
 892   cmp = 0; // make gcc happy
 893   switch (frag1->line->rot) {
 894   case 0:
 895     if ((cmp = frag1->yMin - frag2->yMin) == 0) {
 896       cmp = frag1->xMin - frag2->xMin;
 897     }
 898     break;
 899   case 1:
 900     if ((cmp = frag2->xMax - frag1->xMax) == 0) {
 901       cmp = frag1->yMin - frag2->yMin;
 902     }
 903     break;
 904   case 2:
 905     if ((cmp = frag2->yMin - frag1->yMin) == 0) {
 906       cmp = frag2->xMax - frag1->xMax;
 907     }
 908     break;
 909   case 3:
 910     if ((cmp = frag1->xMax - frag2->xMax) == 0) {
 911       cmp = frag2->yMax - frag1->yMax;
 912     }
 913     break;
 914   }
 915   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 916 }
 917
 918 int TextLineFrag::cmpXYLineRot(const void *p1, const void *p2) {
 919   TextLineFrag *frag1 = (TextLineFrag *)p1;
 920   TextLineFrag *frag2 = (TextLineFrag *)p2;
 921   double cmp;
 922
 923   cmp = 0; // make gcc happy
 924   switch (frag1->line->rot) {
 925   case 0:
 926     if ((cmp = frag1->xMin - frag2->xMin) == 0) {
 927       cmp = frag1->yMin - frag2->yMin;
 928     }
 929     break;
 930   case 1:
 931     if ((cmp = frag1->yMin - frag2->yMin) == 0) {
 932       cmp = frag2->xMax - frag1->xMax;
 933     }
 934     break;
 935   case 2:
 936     if ((cmp = frag2->xMax - frag1->xMax) == 0) {
 937       cmp = frag2->yMin - frag1->yMin;
 938     }
 939     break;
 940   case 3:
 941     if ((cmp = frag2->yMax - frag1->yMax) == 0) {
 942       cmp = frag1->xMax - frag2->xMax;
 943     }
 944     break;
 945   }
 946   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
 947 }
 948
 949 //------------------------------------------------------------------------
 950 // TextBlock
 951 //------------------------------------------------------------------------
 952
 953 TextBlock::TextBlock(TextPage *pageA, int rotA) {
 954   page = pageA;
 955   rot = rotA;
 956   xMin = yMin = 0;
 957   xMax = yMax = -1;
 958   priMin = 0;
 959   priMax = page->pageWidth;
 960   pool = new TextPool();
 961   lines = NULL;
 962   curLine = NULL;
 963   next = NULL;
 964   stackNext = NULL;
 965 }
 966
 967 TextBlock::~TextBlock() {
 968   TextLine *line;
 969
 970   delete pool;
 971   while (lines) {
 972     line = lines;
 973     lines = lines->next;
 974     delete line;
 975   }
 976 }
 977
 978 void TextBlock::addWord(TextWord *word) {
 979   pool->addWord(word);
 980   if (xMin > xMax) {
 981     xMin = word->xMin;
 982     xMax = word->xMax;
 983     yMin = word->yMin;
 984     yMax = word->yMax;
 985   } else {
 986     if (word->xMin < xMin) {
 987       xMin = word->xMin;
 988     }
 989     if (word->xMax > xMax) {
 990       xMax = word->xMax;
 991     }
 992     if (word->yMin < yMin) {
 993       yMin = word->yMin;
 994     }
 995     if (word->yMax > yMax) {
 996       yMax = word->yMax;
 997     }
 998   }
 999 }
1000
1001 void TextBlock::coalesce(UnicodeMap *uMap) {
1002   TextWord *word0, *word1, *word2, *bestWord0, *bestWord1, *lastWord;
1003   TextLine *line, *line0, *line1;
1004   int poolMinBaseIdx, startBaseIdx, minBaseIdx, maxBaseIdx;
1005   int baseIdx, bestWordBaseIdx, idx0, idx1;
1006   double minBase, maxBase;
1007   double fontSize, delta, priDelta, secDelta;
1008   TextLine **lineArray;
1009   GBool found;
1010   int col1, col2;
1011   int i, j, k;
1012
1013   // discard duplicated text (fake boldface, drop shadows)
1014   for (idx0 = pool->minBaseIdx; idx0 <= pool->maxBaseIdx; ++idx0) {
1015     word0 = pool->getPool(idx0);
1016     while (word0) {
1017       priDelta = dupMaxPriDelta * word0->fontSize;
1018       secDelta = dupMaxSecDelta * word0->fontSize;
1019       if (rot == 0 || rot == 3) {
1020         maxBaseIdx = pool->getBaseIdx(word0->base + secDelta);
1021       } else {
1022         maxBaseIdx = pool->getBaseIdx(word0->base - secDelta);
1023       }
1024       found = gFalse;
1025       word1 = word2 = NULL; // make gcc happy
1026       for (idx1 = idx0; idx1 <= maxBaseIdx; ++idx1) {
1027         if (idx1 == idx0) {
1028           word1 = word0;
1029           word2 = word0->next;
1030         } else {
1031           word1 = NULL;
1032           word2 = pool->getPool(idx1);
1033         }
1034         for (; word2; word1 = word2, word2 = word2->next) {
1035           if (word2->len == word0->len &&
1036               !memcmp(word2->text, word0->text,
1037                       word0->len * sizeof(Unicode))) {
1038             switch (rot) {
1039             case 0:
1040             case 2:
1041               found = fabs(word0->xMin - word2->xMin) < priDelta &&
1042                       fabs(word0->xMax - word2->xMax) < priDelta &&
1043                       fabs(word0->yMin - word2->yMin) < secDelta &&
1044                       fabs(word0->yMax - word2->yMax) < secDelta;
1045               break;
1046             case 1:
1047             case 3:
1048               found = fabs(word0->xMin - word2->xMin) < secDelta &&
1049                       fabs(word0->xMax - word2->xMax) < secDelta &&
1050                       fabs(word0->yMin - word2->yMin) < priDelta &&
1051                       fabs(word0->yMax - word2->yMax) < priDelta;
1052               break;
1053             }
1054           }
1055           if (found) {
1056             break;
1057           }
1058         }
1059         if (found) {
1060           break;
1061         }
1062       }
1063       if (found) {
1064         if (word1) {
1065           word1->next = word2->next;
1066         } else {
1067           pool->setPool(idx1, word2->next);
1068         }
1069         delete word2;
1070       } else {
1071         word0 = word0->next;
1072       }
1073     }
1074   }
1075
1076   // build the lines
1077   curLine = NULL;
1078   poolMinBaseIdx = pool->minBaseIdx;
1079   charCount = 0;
1080   nLines = 0;
1081   while (1) {
1082
1083     // find the first non-empty line in the pool
1084     for (;
1085          poolMinBaseIdx <= pool->maxBaseIdx && !pool->getPool(poolMinBaseIdx);
1086          ++poolMinBaseIdx) ;
1087     if (poolMinBaseIdx > pool->maxBaseIdx) {
1088       break;
1089     }
1090
1091     // look for the left-most word in the first four lines of the
1092     // pool -- this avoids starting with a superscript word
1093     startBaseIdx = poolMinBaseIdx;
1094     for (baseIdx = poolMinBaseIdx + 1;
1095          baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
1096          ++baseIdx) {
1097       if (!pool->getPool(baseIdx)) {
1098         continue;
1099       }
1100       if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
1101           < 0) {
1102         startBaseIdx = baseIdx;
1103       }
1104     }
1105
1106     // create a new line
1107     word0 = pool->getPool(startBaseIdx);
1108     pool->setPool(startBaseIdx, word0->next);
1109     word0->next = NULL;
1110     line = new TextLine(this, word0->rot, word0->base);
1111     line->addWord(word0);
1112     lastWord = word0;
1113
1114     // compute the search range
1115     fontSize = word0->fontSize;
1116     minBase = word0->base - maxIntraLineDelta * fontSize;
1117     maxBase = word0->base + maxIntraLineDelta * fontSize;
1118     minBaseIdx = pool->getBaseIdx(minBase);
1119     maxBaseIdx = pool->getBaseIdx(maxBase);
1120
1121     // find the rest of the words in this line
1122     while (1) {
1123
1124       // find the left-most word whose baseline is in the range for
1125       // this line
1126       bestWordBaseIdx = 0;
1127       bestWord0 = bestWord1 = NULL;
1128       for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) {
1129         for (word0 = NULL, word1 = pool->getPool(baseIdx);
1130              word1;
1131              word0 = word1, word1 = word1->next) {
1132           if (word1->base >= minBase &&
1133               word1->base <= maxBase &&
1134               (delta = lastWord->primaryDelta(word1)) >=
1135                 minCharSpacing * fontSize) {
1136             if (delta < maxWordSpacing * fontSize &&
1137                 (!bestWord1 || word1->primaryCmp(bestWord1) < 0)) {
1138               bestWordBaseIdx = baseIdx;
1139               bestWord0 = word0;
1140               bestWord1 = word1;
1141             }
1142             break;
1143           }
1144         }
1145       }
1146       if (!bestWord1) {
1147         break;
1148       }
1149
1150       // remove it from the pool, and add it to the line
1151       if (bestWord0) {
1152         bestWord0->next = bestWord1->next;
1153       } else {
1154         pool->setPool(bestWordBaseIdx, bestWord1->next);
1155       }
1156       bestWord1->next = NULL;
1157       line->addWord(bestWord1);
1158       lastWord = bestWord1;
1159     }
1160
1161     // add the line
1162     if (curLine && line->cmpYX(curLine) > 0) {
1163       line0 = curLine;
1164       line1 = curLine->next;
1165     } else {
1166       line0 = NULL;
1167       line1 = lines;
1168     }
1169     for (;
1170          line1 && line->cmpYX(line1) > 0;
1171          line0 = line1, line1 = line1->next) ;
1172     if (line0) {
1173       line0->next = line;
1174     } else {
1175       lines = line;
1176     }
1177     line->next = line1;
1178     curLine = line;
1179     line->coalesce(uMap);
1180     charCount += line->len;
1181     ++nLines;
1182   }
1183
1184   // sort lines into xy order for column assignment
1185   lineArray = (TextLine **)gmalloc(nLines * sizeof(TextLine *));
1186   for (line = lines, i = 0; line; line = line->next, ++i) {
1187     lineArray[i] = line;
1188   }
1189   qsort(lineArray, nLines, sizeof(TextLine *), &TextLine::cmpXY);
1190
1191   // column assignment
1192   nColumns = 0;
1193   for (i = 0; i < nLines; ++i) {
1194     line0 = lineArray[i];
1195     col1 = 0;
1196     for (j = 0; j < i; ++j) {
1197       line1 = lineArray[j];
1198       if (line1->primaryDelta(line0) >= 0) {
1199         col2 = line1->col[line1->len] + 1;
1200       } else {
1201         k = 0; // make gcc happy
1202         switch (rot) {
1203         case 0:
1204           for (k = 0;
1205                k < line1->len &&
1206                  line0->xMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1207                ++k) ;
1208           break;
1209         case 1:
1210           for (k = 0;
1211                k < line1->len &&
1212                  line0->yMin >= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1213                ++k) ;
1214           break;
1215         case 2:
1216           for (k = 0;
1217                k < line1->len &&
1218                  line0->xMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1219                ++k) ;
1220           break;
1221         case 3:
1222           for (k = 0;
1223                k < line1->len &&
1224                  line0->yMax <= 0.5 * (line1->edge[k] + line1->edge[k+1]);
1225                ++k) ;
1226           break;
1227         }
1228         col2 = line1->col[k];
1229       }
1230       if (col2 > col1) {
1231         col1 = col2;
1232       }
1233     }
1234     for (k = 0; k <= line0->len; ++k) {
1235       line0->col[k] += col1;
1236     }
1237     if (line0->col[line0->len] > nColumns) {
1238       nColumns = line0->col[line0->len];
1239     }
1240   }
1241   gfree(lineArray);
1242 }
1243
1244 void TextBlock::updatePriMinMax(TextBlock *blk) {
1245   double newPriMin, newPriMax;
1246   GBool gotPriMin, gotPriMax;
1247
1248   gotPriMin = gotPriMax = gFalse;
1249   newPriMin = newPriMax = 0; // make gcc happy
1250   switch (page->primaryRot) {
1251   case 0:
1252   case 2:
1253     if (blk->yMin < yMax && blk->yMax > yMin) {
1254       if (blk->xMin < xMin) {
1255         newPriMin = blk->xMax;
1256         gotPriMin = gTrue;
1257       }
1258       if (blk->xMax > xMax) {
1259         newPriMax = blk->xMin;
1260         gotPriMax = gTrue;
1261       }
1262     }
1263     break;
1264   case 1:
1265   case 3:
1266     if (blk->xMin < xMax && blk->xMax > xMin) {
1267       if (blk->yMin < yMin) {
1268         newPriMin = blk->yMax;
1269         gotPriMin = gTrue;
1270       }
1271       if (blk->yMax > yMax) {
1272         newPriMax = blk->yMin;
1273         gotPriMax = gTrue;
1274       }
1275     }
1276     break;
1277   }
1278   if (gotPriMin) {
1279     if (newPriMin > xMin) {
1280       newPriMin = xMin;
1281     }
1282     if (newPriMin > priMin) {
1283       priMin = newPriMin;
1284     }
1285   }
1286   if (gotPriMax) {
1287     if (newPriMax < xMax) {
1288       newPriMax = xMax;
1289     }
1290     if (newPriMax < priMax) {
1291       priMax = newPriMax;
1292     }
1293   }
1294 }
1295
1296 int TextBlock::cmpXYPrimaryRot(const void *p1, const void *p2) {
1297   TextBlock *blk1 = *(TextBlock **)p1;
1298   TextBlock *blk2 = *(TextBlock **)p2;
1299   double cmp;
1300
1301   cmp = 0; // make gcc happy
1302   switch (blk1->page->primaryRot) {
1303   case 0:
1304     if ((cmp = blk1->xMin - blk2->xMin) == 0) {
1305       cmp = blk1->yMin - blk2->yMin;
1306     }
1307     break;
1308   case 1:
1309     if ((cmp = blk1->yMin - blk2->yMin) == 0) {
1310       cmp = blk2->xMax - blk1->xMax;
1311     }
1312     break;
1313   case 2:
1314     if ((cmp = blk2->xMax - blk1->xMax) == 0) {
1315       cmp = blk2->yMin - blk1->yMin;
1316     }
1317     break;
1318   case 3:
1319     if ((cmp = blk2->yMax - blk1->yMax) == 0) {
1320       cmp = blk1->xMax - blk2->xMax;
1321     }
1322     break;
1323   }
1324   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1325 }
1326
1327 int TextBlock::cmpYXPrimaryRot(const void *p1, const void *p2) {
1328   TextBlock *blk1 = *(TextBlock **)p1;
1329   TextBlock *blk2 = *(TextBlock **)p2;
1330   double cmp;
1331
1332   cmp = 0; // make gcc happy
1333   switch (blk1->page->primaryRot) {
1334   case 0:
1335     if ((cmp = blk1->yMin - blk2->yMin) == 0) {
1336       cmp = blk1->xMin - blk2->xMin;
1337     }
1338     break;
1339   case 1:
1340     if ((cmp = blk2->xMax - blk1->xMax) == 0) {
1341       cmp = blk1->yMin - blk2->yMin;
1342     }
1343     break;
1344   case 2:
1345     if ((cmp = blk2->yMin - blk1->yMin) == 0) {
1346       cmp = blk2->xMax - blk1->xMax;
1347     }
1348     break;
1349   case 3:
1350     if ((cmp = blk1->xMax - blk2->xMax) == 0) {
1351       cmp = blk2->yMax - blk1->yMax;
1352     }
1353     break;
1354   }
1355   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1356 }
1357
1358 int TextBlock::primaryCmp(TextBlock *blk) {
1359   double cmp;
1360
1361   cmp = 0; // make gcc happy
1362   switch (rot) {
1363   case 0:
1364     cmp = xMin - blk->xMin;
1365     break;
1366   case 1:
1367     cmp = yMin - blk->yMin;
1368     break;
1369   case 2:
1370     cmp = blk->xMax - xMax;
1371     break;
1372   case 3:
1373     cmp = blk->yMax - yMax;
1374     break;
1375   }
1376   return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
1377 }
1378
1379 double TextBlock::secondaryDelta(TextBlock *blk) {
1380   double delta;
1381
1382   delta = 0; // make gcc happy
1383   switch (rot) {
1384   case 0:
1385     delta = blk->yMin - yMax;
1386     break;
1387   case 1:
1388     delta = xMin - blk->xMax;
1389     break;
1390   case 2:
1391     delta = yMin - blk->yMax;
1392     break;
1393   case 3:
1394     delta = blk->xMin - xMax;
1395     break;
1396   }
1397   return delta;
1398 }
1399
1400 GBool TextBlock::isBelow(TextBlock *blk) {
1401   GBool below;
1402
1403   below = gFalse; // make gcc happy
1404   switch (page->primaryRot) {
1405   case 0:
1406     below = xMin >= blk->priMin && xMax <= blk->priMax &&
1407             yMin > blk->yMin;
1408     break;
1409   case 1:
1410     below = yMin >= blk->priMin && yMax <= blk->priMax &&
1411             xMax < blk->xMax;
1412     break;
1413   case 2:
1414     below = xMin >= blk->priMin && xMax <= blk->priMax &&
1415             yMax < blk->yMax;
1416     break;
1417   case 3:
1418     below = yMin >= blk->priMin && yMax <= blk->priMax &&
1419             xMin > blk->xMin;
1420     break;
1421   }
1422
1423   return below;
1424 }
1425
1426 //------------------------------------------------------------------------
1427 // TextFlow
1428 //------------------------------------------------------------------------
1429
1430 TextFlow::TextFlow(TextPage *pageA, TextBlock *blk) {
1431   page = pageA;
1432   xMin = blk->xMin;
1433   xMax = blk->xMax;
1434   yMin = blk->yMin;
1435   yMax = blk->yMax;
1436   priMin = blk->priMin;
1437   priMax = blk->priMax;
1438   blocks = lastBlk = blk;
1439   next = NULL;
1440 }
1441
1442 TextFlow::~TextFlow() {
1443   TextBlock *blk;
1444
1445   while (blocks) {
1446     blk = blocks;
1447     blocks = blocks->next;
1448     delete blk;
1449   }
1450 }
1451
1452 void TextFlow::addBlock(TextBlock *blk) {
1453   if (lastBlk) {
1454     lastBlk->next = blk;
1455   } else {
1456     blocks = blk;
1457   }
1458   lastBlk = blk;
1459   if (blk->xMin < xMin) {
1460     xMin = blk->xMin;
1461   }
1462   if (blk->xMax > xMax) {
1463     xMax = blk->xMax;
1464   }
1465   if (blk->yMin < yMin) {
1466     yMin = blk->yMin;
1467   }
1468   if (blk->yMax > yMax) {
1469     yMax = blk->yMax;
1470   }
1471 }
1472
1473 GBool TextFlow::blockFits(TextBlock *blk, TextBlock *prevBlk) {
1474   GBool fits;
1475
1476   // lower blocks must use smaller fonts
1477   if (blk->lines->words->fontSize > lastBlk->lines->words->fontSize) {
1478     return gFalse;
1479   }
1480
1481   fits = gFalse; // make gcc happy
1482   switch (page->primaryRot) {
1483   case 0:
1484     fits = blk->xMin >= priMin && blk->xMax <= priMax;
1485     break;
1486   case 1:
1487     fits = blk->yMin >= priMin && blk->yMax <= priMax;
1488     break;
1489   case 2:
1490     fits = blk->xMin >= priMin && blk->xMax <= priMax;
1491     break;
1492   case 3:
1493     fits = blk->yMin >= priMin && blk->yMax <= priMax;
1494     break;
1495   }
1496   return fits;
1497 }
1498
1499 #if TEXTOUT_WORD_LIST
1500
1501 //------------------------------------------------------------------------
1502 // TextWordList
1503 //------------------------------------------------------------------------
1504
1505 TextWordList::TextWordList(TextPage *text, GBool physLayout) {
1506   TextFlow *flow;
1507   TextBlock *blk;
1508   TextLine *line;
1509   TextWord *word;
1510   TextWord **wordArray;
1511   int nWords, i;
1512
1513   words = new GList();
1514
1515   if (text->rawOrder) {
1516     for (word = text->rawWords; word; word = word->next) {
1517       words->append(word);
1518     }
1519
1520   } else if (physLayout) {
1521     // this is inefficient, but it's also the least useful of these
1522     // three cases
1523     nWords = 0;
1524     for (flow = text->flows; flow; flow = flow->next) {
1525       for (blk = flow->blocks; blk; blk = blk->next) {
1526         for (line = blk->lines; line; line = line->next) {
1527           for (word = line->words; word; word = word->next) {
1528             ++nWords;
1529           }
1530         }
1531       }
1532     }
1533     wordArray = (TextWord **)gmalloc(nWords * sizeof(TextWord *));
1534     i = 0;
1535     for (flow = text->flows; flow; flow = flow->next) {
1536       for (blk = flow->blocks; blk; blk = blk->next) {
1537         for (line = blk->lines; line; line = line->next) {
1538           for (word = line->words; word; word = word->next) {
1539             wordArray[i++] = word;
1540           }
1541         }
1542       }
1543     }
1544     qsort(wordArray, nWords, sizeof(TextWord *), &TextWord::cmpYX);
1545     for (i = 0; i < nWords; ++i) {
1546       words->append(wordArray[i]);
1547     }
1548     gfree(wordArray);
1549
1550   } else {
1551     for (flow = text->flows; flow; flow = flow->next) {
1552       for (blk = flow->blocks; blk; blk = blk->next) {
1553         for (line = blk->lines; line; line = line->next) {
1554           for (word = line->words; word; word = word->next) {
1555             words->append(word);
1556           }
1557         }
1558       }
1559     }
1560   }
1561 }
1562
1563 TextWordList::~TextWordList() {
1564   delete words;
1565 }
1566
1567 int TextWordList::getLength() {
1568   return words->getLength();
1569 }
1570
1571 TextWord *TextWordList::get(int idx) {
1572   if (idx < 0 || idx >= words->getLength()) {
1573     return NULL;
1574   }
1575   return (TextWord *)words->get(idx);
1576 }
1577
1578 #endif // TEXTOUT_WORD_LIST
1579
1580 //------------------------------------------------------------------------
1581 // TextPage
1582 //------------------------------------------------------------------------
1583
1584 TextPage::TextPage(GBool rawOrderA) {
1585   int rot;
1586
1587   rawOrder = rawOrderA;
1588   curWord = NULL;
1589   charPos = 0;
1590   curFont = NULL;
1591   curFontSize = 0;
1592   nest = 0;
1593   nTinyChars = 0;
1594   if (!rawOrder) {
1595     for (rot = 0; rot < 4; ++rot) {
1596       pools[rot] = new TextPool();
1597     }
1598   }
1599   flows = NULL;
1600   blocks = NULL;
1601   rawWords = NULL;
1602   rawLastWord = NULL;
1603   fonts = new GList();
1604   lastFindXMin = lastFindYMin = 0;
1605   haveLastFind = gFalse;
1606 }
1607
1608 TextPage::~TextPage() {
1609   int rot;
1610
1611   clear();
1612   if (!rawOrder) {
1613     for (rot = 0; rot < 4; ++rot) {
1614       delete pools[rot];
1615     }
1616   }
1617   delete fonts;
1618 }
1619
1620 void TextPage::startPage(GfxState *state) {
1621   clear();
1622   if (state) {
1623     pageWidth = state->getPageWidth();
1624     pageHeight = state->getPageHeight();
1625   } else {
1626     pageWidth = pageHeight = 0;
1627   }
1628 }
1629
1630 void TextPage::clear() {
1631   int rot;
1632   TextFlow *flow;
1633   TextWord *word;
1634
1635   if (curWord) {
1636     delete curWord;
1637     curWord = NULL;
1638   }
1639   if (rawOrder) {
1640     while (rawWords) {
1641       word = rawWords;
1642       rawWords = rawWords->next;
1643       delete word;
1644     }
1645   } else {
1646     for (rot = 0; rot < 4; ++rot) {
1647       delete pools[rot];
1648     }
1649     while (flows) {
1650       flow = flows;
1651       flows = flows->next;
1652       delete flow;
1653     }
1654     gfree(blocks);
1655   }
1656   deleteGList(fonts, TextFontInfo);
1657
1658   curWord = NULL;
1659   charPos = 0;
1660   curFont = NULL;
1661   curFontSize = 0;
1662   nest = 0;
1663   nTinyChars = 0;
1664   if (!rawOrder) {
1665     for (rot = 0; rot < 4; ++rot) {
1666       pools[rot] = new TextPool();
1667     }
1668   }
1669   flows = NULL;
1670   blocks = NULL;
1671   rawWords = NULL;
1672   rawLastWord = NULL;
1673   fonts = new GList();
1674 }
1675
1676 void TextPage::updateFont(GfxState *state) {
1677   GfxFont *gfxFont;
1678   double *fm;
1679   char *name;
1680   int code, mCode, letterCode, anyCode;
1681   double w;
1682   int i;
1683
1684   // get the font info object
1685   curFont = NULL;
1686   for (i = 0; i < fonts->getLength(); ++i) {
1687     curFont = (TextFontInfo *)fonts->get(i);
1688     if (curFont->matches(state)) {
1689       break;
1690     }
1691     curFont = NULL;
1692   }
1693   if (!curFont) {
1694     curFont = new TextFontInfo(state);
1695     fonts->append(curFont);
1696   }
1697
1698   // adjust the font size
1699   gfxFont = state->getFont();
1700   curFontSize = state->getTransformedFontSize();
1701   if (gfxFont && gfxFont->getType() == fontType3) {
1702     // This is a hack which makes it possible to deal with some Type 3
1703     // fonts.  The problem is that it's impossible to know what the
1704     // base coordinate system used in the font is without actually
1705     // rendering the font.  This code tries to guess by looking at the
1706     // width of the character 'm' (which breaks if the font is a
1707     // subset that doesn't contain 'm').
1708     mCode = letterCode = anyCode = -1;
1709     for (code = 0; code < 256; ++code) {
1710       name = ((Gfx8BitFont *)gfxFont)->getCharName(code);
1711       if (name && name[0] == 'm' && name[1] == '\0') {
1712         mCode = code;
1713       }
1714       if (letterCode < 0 && name && name[1] == '\0' &&
1715           ((name[0] >= 'A' && name[0] <= 'Z') ||
1716            (name[0] >= 'a' && name[0] <= 'z'))) {
1717         letterCode = code;
1718       }
1719       if (anyCode < 0 && name &&
1720           ((Gfx8BitFont *)gfxFont)->getWidth(code) > 0) {
1721         anyCode = code;
1722       }
1723     }
1724     if (mCode >= 0 &&
1725         (w = ((Gfx8BitFont *)gfxFont)->getWidth(mCode)) > 0) {
1726       // 0.6 is a generic average 'm' width -- yes, this is a hack
1727       curFontSize *= w / 0.6;
1728     } else if (letterCode >= 0 &&
1729                (w = ((Gfx8BitFont *)gfxFont)->getWidth(letterCode)) > 0) {
1730       // even more of a hack: 0.5 is a generic letter width
1731       curFontSize *= w / 0.5;
1732     } else if (anyCode >= 0 &&
1733                (w = ((Gfx8BitFont *)gfxFont)->getWidth(anyCode)) > 0) {
1734       // better than nothing: 0.5 is a generic character width
1735       curFontSize *= w / 0.5;
1736     }
1737     fm = gfxFont->getFontMatrix();
1738     if (fm[0] != 0) {
1739       curFontSize *= fabs(fm[3] / fm[0]);
1740     }
1741   }
1742 }
1743
1744 void TextPage::beginWord(GfxState *state, double x0, double y0) {
1745   double *txtm, *ctm, *fontm;
1746   double m[4], m2[4];
1747   int rot;
1748
1749   // This check is needed because Type 3 characters can contain
1750   // text-drawing operations (when TextPage is being used via
1751   // XOutputDev rather than TextOutputDev).
1752   if (curWord) {
1753     ++nest;
1754     return;
1755   }
1756
1757   // compute the rotation
1758   txtm = state->getTextMat();
1759   ctm = state->getCTM();
1760   m[0] = txtm[0] * ctm[0] + txtm[1] * ctm[2];
1761   m[1] = txtm[0] * ctm[1] + txtm[1] * ctm[3];
1762   m[2] = txtm[2] * ctm[0] + txtm[3] * ctm[2];
1763   m[3] = txtm[2] * ctm[1] + txtm[3] * ctm[3];
1764   if (state->getFont()->getType() == fontType3) {
1765     fontm = state->getFont()->getFontMatrix();
1766     m2[0] = fontm[0] * m[0] + fontm[1] * m[2];
1767     m2[1] = fontm[0] * m[1] + fontm[1] * m[3];
1768     m2[2] = fontm[2] * m[0] + fontm[3] * m[2];
1769     m2[3] = fontm[2] * m[1] + fontm[3] * m[3];
1770     m[0] = m2[0];
1771     m[1] = m2[1];
1772     m[2] = m2[2];
1773     m[3] = m2[3];
1774   }
1775   if (fabs(m[0] * m[3]) > fabs(m[1] * m[2])) {
1776     rot = (m[3] < 0) ? 0 : 2;
1777   } else {
1778     rot = (m[2] > 0) ? 1 : 3;
1779   }
1780
1781   curWord = new TextWord(state, rot, x0, y0, charPos, curFont, curFontSize);
1782 }
1783
1784 void TextPage::addChar(GfxState *state, double x, double y,
1785                        double dx, double dy,
1786                        CharCode c, Unicode *u, int uLen) {
1787   double x1, y1, w1, h1, dx2, dy2, sp;
1788   int n, i;
1789
1790   // if the previous char was a space, addChar will have called
1791   // endWord, so we need to start a new word
1792   if (!curWord) {
1793     beginWord(state, x, y);
1794   }
1795
1796   // throw away chars that aren't inside the page bounds
1797   state->transform(x, y, &x1, &y1);
1798   if (x1 < 0 || x1 > pageWidth ||
1799       y1 < 0 || y1 > pageHeight) {
1800     return;
1801   }
1802
1803   // subtract char and word spacing from the dx,dy values
1804   sp = state->getCharSpace();
1805   if (c == (CharCode)0x20) {
1806     sp += state->getWordSpace();
1807   }
1808   state->textTransformDelta(sp * state->getHorizScaling(), 0, &dx2, &dy2);
1809   dx -= dx2;
1810   dy -= dy2;
1811   state->transformDelta(dx, dy, &w1, &h1);
1812
1813   // check the tiny chars limit
1814   if (!globalParams->getTextKeepTinyChars() &&
1815       fabs(w1) < 3 && fabs(h1) < 3) {
1816     if (++nTinyChars > 50000) {
1817       return;
1818     }
1819   }
1820
1821   // break words at space character
1822   if (uLen == 1 && u[0] == (Unicode)0x20) {
1823     ++curWord->charLen;
1824     ++charPos;
1825     endWord();
1826     return;
1827   }
1828
1829   // large char spacing is sometimes used to move text around -- in
1830   // this case, break text into individual chars and let the coalesce
1831   // function deal with it later
1832   n = curWord->len;
1833   if (n > 0) {
1834     switch (curWord->rot) {
1835     case 0: sp = x1 - curWord->xMax; break;
1836     case 1: sp = y1 - curWord->yMax; break;
1837     case 2: sp = curWord->xMin - x1; break;
1838     case 3: sp = curWord->yMin - y1; break;
1839     }
1840     if (sp > defaultSpaceWidth * curWord->fontSize) {
1841       endWord();
1842       beginWord(state, x, y);
1843     }
1844   }
1845
1846   // page rotation and/or transform matrices can cause text to be
1847   // drawn in reverse order -- in this case, swap the begin/end
1848   // coordinates and break text into individual chars
1849   if ((curWord->rot == 0 && w1 < 0) ||
1850       (curWord->rot == 1 && h1 < 0) ||
1851       (curWord->rot == 2 && w1 > 0) ||
1852       (curWord->rot == 3 && h1 > 0)) {
1853     endWord();
1854     beginWord(state, x + dx, y + dy);
1855     x1 += w1;
1856     y1 += h1;
1857     w1 = -w1;
1858     h1 = -h1;
1859   }
1860
1861   // add the characters to the current word
1862   if (uLen != 0) {
1863     w1 /= uLen;
1864     h1 /= uLen;
1865   }
1866   for (i = 0; i < uLen; ++i) {
1867     curWord->addChar(state, x1 + i*w1, y1 + i*h1, w1, h1, u[i]);
1868   }
1869   ++curWord->charLen;
1870   ++charPos;
1871 }
1872
1873 void TextPage::endWord() {
1874   // This check is needed because Type 3 characters can contain
1875   // text-drawing operations (when TextPage is being used via
1876   // XOutputDev rather than TextOutputDev).
1877   if (nest > 0) {
1878     --nest;
1879     return;
1880   }
1881
1882   if (curWord) {
1883     addWord(curWord);
1884     curWord = NULL;
1885   }
1886 }
1887
1888 void TextPage::addWord(TextWord *word) {
1889   // throw away zero-length words -- they don't have valid xMin/xMax
1890   // values, and they're useless anyway
1891   if (word->len == 0) {
1892     delete word;
1893     return;
1894   }
1895
1896   if (rawOrder) {
1897     if (rawLastWord) {
1898       rawLastWord->next = word;
1899     } else {
1900       rawWords = word;
1901     }
1902     rawLastWord = word;
1903   } else {
1904     pools[word->rot]->addWord(word);
1905   }
1906 }
1907
1908 void TextPage::coalesce(GBool physLayout) {
1909   UnicodeMap *uMap;
1910   TextPool *pool;
1911   TextWord *word0, *word1, *word2;
1912   TextLine *line;
1913   TextBlock *blkList, *blkStack, *blk, *lastBlk, *blk0, *blk1;
1914   TextBlock **blkArray;
1915   TextFlow *flow, *lastFlow;
1916   int rot, poolMinBaseIdx, baseIdx, startBaseIdx;
1917   double minBase, maxBase, newMinBase, newMaxBase;
1918   double fontSize, colSpace, lineSpace, intraLineSpace, blkSpace;
1919   GBool found;
1920   int count[4];
1921   int lrCount;
1922   int firstBlkIdx, nBlocksLeft;
1923   int col1, col2;
1924   int i, j, n;
1925
1926   if (rawOrder) {
1927     primaryRot = 0;
1928     primaryLR = gTrue;
1929     return;
1930   }
1931
1932   uMap = globalParams->getTextEncoding();
1933   blkList = NULL;
1934   lastBlk = NULL;
1935   nBlocks = 0;
1936   primaryRot = -1;
1937
1938 #if 0 // for debugging
1939   printf("*** initial words ***\n");
1940   for (rot = 0; rot < 4; ++rot) {
1941     pool = pools[rot];
1942     for (baseIdx = pool->minBaseIdx; baseIdx <= pool->maxBaseIdx; ++baseIdx) {
1943       for (word0 = pool->getPool(baseIdx); word0; word0 = word0->next) {
1944         printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f '",
1945                word0->xMin, word0->xMax, word0->yMin, word0->yMax,
1946                word0->base, word0->fontSize);
1947         for (i = 0; i < word0->len; ++i) {
1948           fputc(word0->text[i] & 0xff, stdout);
1949         }
1950         printf("'\n");
1951       }
1952     }
1953   }
1954   printf("\n");
1955 #endif
1956
1957   //----- assemble the blocks
1958
1959   //~ add an outer loop for writing mode (vertical text)
1960
1961   // build blocks for each rotation value
1962   for (rot = 0; rot < 4; ++rot) {
1963     pool = pools[rot];
1964     poolMinBaseIdx = pool->minBaseIdx;
1965     count[rot] = 0;
1966
1967     // add blocks until no more words are left
1968     while (1) {
1969
1970       // find the first non-empty line in the pool
1971       for (;
1972            poolMinBaseIdx <= pool->maxBaseIdx &&
1973              !pool->getPool(poolMinBaseIdx);
1974            ++poolMinBaseIdx) ;
1975       if (poolMinBaseIdx > pool->maxBaseIdx) {
1976         break;
1977       }
1978
1979       // look for the left-most word in the first four lines of the
1980       // pool -- this avoids starting with a superscript word
1981       startBaseIdx = poolMinBaseIdx;
1982       for (baseIdx = poolMinBaseIdx + 1;
1983            baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx;
1984            ++baseIdx) {
1985         if (!pool->getPool(baseIdx)) {
1986           continue;
1987         }
1988         if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx))
1989             < 0) {
1990           startBaseIdx = baseIdx;
1991         }
1992       }
1993
1994       // create a new block
1995       word0 = pool->getPool(startBaseIdx);
1996       pool->setPool(startBaseIdx, word0->next);
1997       word0->next = NULL;
1998       blk = new TextBlock(this, rot);
1999       blk->addWord(word0);
2000
2001       fontSize = word0->fontSize;
2002       minBase = maxBase = word0->base;
2003       colSpace = minColSpacing * fontSize;
2004       lineSpace = maxLineSpacingDelta * fontSize;
2005       intraLineSpace = maxIntraLineDelta * fontSize;
2006
2007       // add words to the block
2008       do {
2009         found = gFalse;
2010
2011         // look for words on the line above the current top edge of
2012         // the block
2013         newMinBase = minBase;
2014         for (baseIdx = pool->getBaseIdx(minBase);
2015              baseIdx >= pool->getBaseIdx(minBase - lineSpace);
2016              --baseIdx) {
2017           word0 = NULL;
2018           word1 = pool->getPool(baseIdx);
2019           while (word1) {
2020             if (word1->base < minBase &&
2021                 word1->base >= minBase - lineSpace &&
2022                 ((rot == 0 || rot == 2)
2023                  ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2024                  : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2025                 fabs(word1->fontSize - fontSize) <
2026                   maxBlockFontSizeDelta1 * fontSize) {
2027               word2 = word1;
2028               if (word0) {
2029                 word0->next = word1->next;
2030               } else {
2031                 pool->setPool(baseIdx, word1->next);
2032               }
2033               word1 = word1->next;
2034               word2->next = NULL;
2035               blk->addWord(word2);
2036               found = gTrue;
2037               newMinBase = word2->base;
2038             } else {
2039               word0 = word1;
2040               word1 = word1->next;
2041             }
2042           }
2043         }
2044         minBase = newMinBase;
2045
2046         // look for words on the line below the current bottom edge of
2047         // the block
2048         newMaxBase = maxBase;
2049         for (baseIdx = pool->getBaseIdx(maxBase);
2050              baseIdx <= pool->getBaseIdx(maxBase + lineSpace);
2051              ++baseIdx) {
2052           word0 = NULL;
2053           word1 = pool->getPool(baseIdx);
2054           while (word1) {
2055             if (word1->base > maxBase &&
2056                 word1->base <= maxBase + lineSpace &&
2057                 ((rot == 0 || rot == 2)
2058                  ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2059                  : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2060                 fabs(word1->fontSize - fontSize) <
2061                   maxBlockFontSizeDelta1 * fontSize) {
2062               word2 = word1;
2063               if (word0) {
2064                 word0->next = word1->next;
2065               } else {
2066                 pool->setPool(baseIdx, word1->next);
2067               }
2068               word1 = word1->next;
2069               word2->next = NULL;
2070               blk->addWord(word2);
2071               found = gTrue;
2072               newMaxBase = word2->base;
2073             } else {
2074               word0 = word1;
2075               word1 = word1->next;
2076             }
2077           }
2078         }
2079         maxBase = newMaxBase;
2080
2081         // look for words that are on lines already in the block, and
2082         // that overlap the block horizontally
2083         for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2084              baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2085              ++baseIdx) {
2086           word0 = NULL;
2087           word1 = pool->getPool(baseIdx);
2088           while (word1) {
2089             if (word1->base >= minBase - intraLineSpace &&
2090                 word1->base <= maxBase + intraLineSpace &&
2091                 ((rot == 0 || rot == 2)
2092                  ? (word1->xMin < blk->xMax && word1->xMax > blk->xMin)
2093                  : (word1->yMin < blk->yMax && word1->yMax > blk->yMin)) &&
2094                 fabs(word1->fontSize - fontSize) <
2095                   maxBlockFontSizeDelta2 * fontSize) {
2096               word2 = word1;
2097               if (word0) {
2098                 word0->next = word1->next;
2099               } else {
2100                 pool->setPool(baseIdx, word1->next);
2101               }
2102               word1 = word1->next;
2103               word2->next = NULL;
2104               blk->addWord(word2);
2105               found = gTrue;
2106             } else {
2107               word0 = word1;
2108               word1 = word1->next;
2109             }
2110           }
2111         }
2112
2113         // only check for outlying words (the next two chunks of code)
2114         // if we didn't find anything else
2115         if (found) {
2116           continue;
2117         }
2118
2119         // scan down the left side of the block, looking for words
2120         // that are near (but not overlapping) the block; if there are
2121         // three or fewer, add them to the block
2122         n = 0;
2123         for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2124              baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2125              ++baseIdx) {
2126           word1 = pool->getPool(baseIdx);
2127           while (word1) {
2128             if (word1->base >= minBase - intraLineSpace &&
2129                 word1->base <= maxBase + intraLineSpace &&
2130                 ((rot == 0 || rot == 2)
2131                  ? (word1->xMax <= blk->xMin &&
2132                     word1->xMax > blk->xMin - colSpace)
2133                  : (word1->yMax <= blk->yMin &&
2134                     word1->yMax > blk->yMin - colSpace)) &&
2135                 fabs(word1->fontSize - fontSize) <
2136                   maxBlockFontSizeDelta3 * fontSize) {
2137               ++n;
2138               break;
2139             }
2140             word1 = word1->next;
2141           }
2142         }
2143         if (n > 0 && n <= 3) {
2144           for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2145                baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2146                ++baseIdx) {
2147             word0 = NULL;
2148             word1 = pool->getPool(baseIdx);
2149             while (word1) {
2150               if (word1->base >= minBase - intraLineSpace &&
2151                   word1->base <= maxBase + intraLineSpace &&
2152                   ((rot == 0 || rot == 2)
2153                    ? (word1->xMax <= blk->xMin &&
2154                       word1->xMax > blk->xMin - colSpace)
2155                    : (word1->yMax <= blk->yMin &&
2156                       word1->yMax > blk->yMin - colSpace)) &&
2157                   fabs(word1->fontSize - fontSize) <
2158                     maxBlockFontSizeDelta3 * fontSize) {
2159                 word2 = word1;
2160                 if (word0) {
2161                   word0->next = word1->next;
2162                 } else {
2163                   pool->setPool(baseIdx, word1->next);
2164                 }
2165                 word1 = word1->next;
2166                 word2->next = NULL;
2167                 blk->addWord(word2);
2168                 if (word2->base < minBase) {
2169                   minBase = word2->base;
2170                 } else if (word2->base > maxBase) {
2171                   maxBase = word2->base;
2172                 }
2173                 found = gTrue;
2174                 break;
2175               } else {
2176                 word0 = word1;
2177                 word1 = word1->next;
2178               }
2179             }
2180           }
2181         }
2182
2183         // scan down the right side of the block, looking for words
2184         // that are near (but not overlapping) the block; if there are
2185         // three or fewer, add them to the block
2186         n = 0;
2187         for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2188              baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2189              ++baseIdx) {
2190           word1 = pool->getPool(baseIdx);
2191           while (word1) {
2192             if (word1->base >= minBase - intraLineSpace &&
2193                 word1->base <= maxBase + intraLineSpace &&
2194                 ((rot == 0 || rot == 2)
2195                  ? (word1->xMin >= blk->xMax &&
2196                     word1->xMin < blk->xMax + colSpace)
2197                  : (word1->yMin >= blk->yMax &&
2198                     word1->yMin < blk->yMax + colSpace)) &&
2199                 fabs(word1->fontSize - fontSize) <
2200                   maxBlockFontSizeDelta3 * fontSize) {
2201               ++n;
2202               break;
2203             }
2204             word1 = word1->next;
2205           }
2206         }
2207         if (n > 0 && n <= 3) {
2208           for (baseIdx = pool->getBaseIdx(minBase - intraLineSpace);
2209                baseIdx <= pool->getBaseIdx(maxBase + intraLineSpace);
2210                ++baseIdx) {
2211             word0 = NULL;
2212             word1 = pool->getPool(baseIdx);
2213             while (word1) {
2214               if (word1->base >= minBase - intraLineSpace &&
2215                   word1->base <= maxBase + intraLineSpace &&
2216                   ((rot == 0 || rot == 2)
2217                    ? (word1->xMin >= blk->xMax &&
2218                       word1->xMin < blk->xMax + colSpace)
2219                    : (word1->yMin >= blk->yMax &&
2220                       word1->yMin < blk->yMax + colSpace)) &&
2221                   fabs(word1->fontSize - fontSize) <
2222                     maxBlockFontSizeDelta3 * fontSize) {
2223                 word2 = word1;
2224                 if (word0) {
2225                   word0->next = word1->next;
2226                 } else {
2227                   pool->setPool(baseIdx, word1->next);
2228                 }
2229                 word1 = word1->next;
2230                 word2->next = NULL;
2231                 blk->addWord(word2);
2232                 if (word2->base < minBase) {
2233                   minBase = word2->base;
2234                 } else if (word2->base > maxBase) {
2235                   maxBase = word2->base;
2236                 }
2237                 found = gTrue;
2238                 break;
2239               } else {
2240                 word0 = word1;
2241                 word1 = word1->next;
2242               }
2243             }
2244           }
2245         }
2246
2247       } while (found);
2248
2249       //~ need to compute the primary writing mode (horiz/vert) in
2250       //~ addition to primary rotation
2251
2252       // coalesce the block, and add it to the list
2253       blk->coalesce(uMap);
2254       if (lastBlk) {
2255         lastBlk->next = blk;
2256       } else {
2257         blkList = blk;
2258       }
2259       lastBlk = blk;
2260       count[rot] += blk->charCount;
2261       if (primaryRot < 0 || count[rot] > count[primaryRot]) {
2262         primaryRot = rot;
2263       }
2264       ++nBlocks;
2265     }
2266   }
2267
2268 #if 0 // for debugging
2269   printf("*** rotation ***\n");
2270   for (rot = 0; rot < 4; ++rot) {
2271     printf("  %d: %6d\n", rot, count[rot]);
2272   }
2273   printf("  primary rot = %d\n", primaryRot);
2274   printf("\n");
2275 #endif
2276
2277 #if 0 // for debugging
2278   printf("*** blocks ***\n");
2279   for (blk = blkList; blk; blk = blk->next) {
2280     printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f\n",
2281            blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax);
2282     for (line = blk->lines; line; line = line->next) {
2283       printf("  line: x=%.2f..%.2f y=%.2f..%.2f base=%.2f\n",
2284              line->xMin, line->xMax, line->yMin, line->yMax, line->base);
2285       for (word0 = line->words; word0; word0 = word0->next) {
2286         printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2287                word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2288                word0->base, word0->fontSize, word0->spaceAfter);
2289         for (i = 0; i < word0->len; ++i) {
2290           fputc(word0->text[i] & 0xff, stdout);
2291         }
2292         printf("'\n");
2293       }
2294     }
2295   }
2296   printf("\n");
2297 #endif
2298
2299   // determine the primary direction
2300   lrCount = 0;
2301   for (blk = blkList; blk; blk = blk->next) {
2302     for (line = blk->lines; line; line = line->next) {
2303       for (word0 = line->words; word0; word0 = word0->next) {
2304         for (i = 0; i < word0->len; ++i) {
2305           if (unicodeTypeL(word0->text[i])) {
2306             ++lrCount;
2307           } else if (unicodeTypeR(word0->text[i])) {
2308             --lrCount;
2309           }
2310         }
2311       }
2312     }
2313   }
2314   primaryLR = lrCount >= 0;
2315
2316 #if 0 // for debugging
2317   printf("*** direction ***\n");
2318   printf("lrCount = %d\n", lrCount);
2319   printf("primaryLR = %d\n", primaryLR);
2320 #endif
2321
2322   //----- column assignment
2323
2324   // sort blocks into xy order for column assignment
2325   blocks = (TextBlock **)gmalloc(nBlocks * sizeof(TextBlock *));
2326   for (blk = blkList, i = 0; blk; blk = blk->next, ++i) {
2327     blocks[i] = blk;
2328   }
2329   qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpXYPrimaryRot);
2330
2331   // column assignment
2332   for (i = 0; i < nBlocks; ++i) {
2333     blk0 = blocks[i];
2334     col1 = 0;
2335     for (j = 0; j < i; ++j) {
2336       blk1 = blocks[j];
2337       col2 = 0; // make gcc happy
2338       switch (primaryRot) {
2339       case 0:
2340         if (blk0->xMin > blk1->xMax) {
2341           col2 = blk1->col + blk1->nColumns + 3;
2342         } else {
2343           col2 = blk1->col + (int)(((blk0->xMin - blk1->xMin) /
2344                                     (blk1->xMax - blk1->xMin)) *
2345                                    blk1->nColumns);
2346         }
2347         break;
2348       case 1:
2349         if (blk0->yMin > blk1->yMax) {
2350           col2 = blk1->col + blk1->nColumns + 3;
2351         } else {
2352           col2 = blk1->col + (int)(((blk0->yMin - blk1->yMin) /
2353                                     (blk1->yMax - blk1->yMin)) *
2354                                    blk1->nColumns);
2355         }
2356         break;
2357       case 2:
2358         if (blk0->xMax < blk1->xMin) {
2359           col2 = blk1->col + blk1->nColumns + 3;
2360         } else {
2361           col2 = blk1->col + (int)(((blk0->xMax - blk1->xMax) /
2362                                     (blk1->xMin - blk1->xMax)) *
2363                                    blk1->nColumns);
2364         }
2365         break;
2366       case 3:
2367         if (blk0->yMax < blk1->yMin) {
2368           col2 = blk1->col + blk1->nColumns + 3;
2369         } else {
2370           col2 = blk1->col + (int)(((blk0->yMax - blk1->yMax) /
2371                                     (blk1->yMin - blk1->yMax)) *
2372                                    blk1->nColumns);
2373         }
2374         break;
2375       }
2376       if (col2 > col1) {
2377         col1 = col2;
2378       }
2379     }
2380     blk0->col = col1;
2381     for (line = blk0->lines; line; line = line->next) {
2382       for (j = 0; j <= line->len; ++j) {
2383         line->col[j] += col1;
2384       }
2385     }
2386   }
2387
2388 #if 0 // for debugging
2389   printf("*** blocks, after column assignment ***\n");
2390   for (blk = blkList; blk; blk = blk->next) {
2391     printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f col=%d nCols=%d\n",
2392            blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax, blk->col,
2393            blk->nColumns);
2394     for (line = blk->lines; line; line = line->next) {
2395       printf("  line:\n");
2396       for (word0 = line->words; word0; word0 = word0->next) {
2397         printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2398                word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2399                word0->base, word0->fontSize, word0->spaceAfter);
2400         for (i = 0; i < word0->len; ++i) {
2401           fputc(word0->text[i] & 0xff, stdout);
2402         }
2403         printf("'\n");
2404       }
2405     }
2406   }
2407   printf("\n");
2408 #endif
2409
2410   //----- reading order sort
2411
2412   // sort blocks into yx order (in preparation for reading order sort)
2413   qsort(blocks, nBlocks, sizeof(TextBlock *), &TextBlock::cmpYXPrimaryRot);
2414
2415   // compute space on left and right sides of each block
2416   for (i = 0; i < nBlocks; ++i) {
2417     blk0 = blocks[i];
2418     for (j = 0; j < nBlocks; ++j) {
2419       blk1 = blocks[j];
2420       if (blk1 != blk0) {
2421         blk0->updatePriMinMax(blk1);
2422       }
2423     }
2424   }
2425
2426 #if 0 // for debugging
2427   printf("*** blocks, after yx sort ***\n");
2428   for (i = 0; i < nBlocks; ++i) {
2429     blk = blocks[i];
2430     printf("block: rot=%d x=%.2f..%.2f y=%.2f..%.2f space=%.2f..%.2f\n",
2431            blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
2432            blk->priMin, blk->priMax);
2433     for (line = blk->lines; line; line = line->next) {
2434       printf("  line:\n");
2435       for (word0 = line->words; word0; word0 = word0->next) {
2436         printf("    word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2437                word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2438                word0->base, word0->fontSize, word0->spaceAfter);
2439         for (j = 0; j < word0->len; ++j) {
2440           fputc(word0->text[j] & 0xff, stdout);
2441         }
2442         printf("'\n");
2443       }
2444     }
2445   }
2446   printf("\n");
2447 #endif
2448
2449   // build the flows
2450   //~ this needs to be adjusted for writing mode (vertical text)
2451   //~ this also needs to account for right-to-left column ordering
2452   blkArray = (TextBlock **)gmalloc(nBlocks * sizeof(TextBlock *));
2453   memcpy(blkArray, blocks, nBlocks * sizeof(TextBlock *));
2454   flows = lastFlow = NULL;
2455   firstBlkIdx = 0;
2456   nBlocksLeft = nBlocks;
2457   while (nBlocksLeft > 0) {
2458
2459     // find the upper-left-most block
2460     for (; !blkArray[firstBlkIdx]; ++firstBlkIdx) ;
2461     i = firstBlkIdx;
2462     blk = blkArray[i];
2463     for (j = firstBlkIdx + 1; j < nBlocks; ++j) {
2464       blk1 = blkArray[j];
2465       if (blk1) {
2466         if (blk && blk->secondaryDelta(blk1) > 0) {
2467           break;
2468         }
2469         if (blk1->primaryCmp(blk) < 0) {
2470           i = j;
2471           blk = blk1;
2472         }
2473       }
2474     }
2475     blkArray[i] = NULL;
2476     --nBlocksLeft;
2477     blk->next = NULL;
2478
2479     // create a new flow, starting with the upper-left-most block
2480     flow = new TextFlow(this, blk);
2481     if (lastFlow) {
2482       lastFlow->next = flow;
2483     } else {
2484       flows = flow;
2485     }
2486     lastFlow = flow;
2487     fontSize = blk->lines->words->fontSize;
2488
2489     // push the upper-left-most block on the stack
2490     blk->stackNext = NULL;
2491     blkStack = blk;
2492
2493     // find the other blocks in this flow
2494     while (blkStack) {
2495
2496       // find the upper-left-most block under (but within
2497       // maxBlockSpacing of) the top block on the stack
2498       blkSpace = maxBlockSpacing * blkStack->lines->words->fontSize;
2499       blk = NULL;
2500       i = -1;
2501       for (j = firstBlkIdx; j < nBlocks; ++j) {
2502         blk1 = blkArray[j];
2503         if (blk1) {
2504           if (blkStack->secondaryDelta(blk1) > blkSpace) {
2505             break;
2506           }
2507           if (blk && blk->secondaryDelta(blk1) > 0) {
2508             break;
2509           }
2510           if (blk1->isBelow(blkStack) &&
2511               (!blk || blk1->primaryCmp(blk) < 0)) {
2512             i = j;
2513             blk = blk1;
2514           }
2515         }
2516       }
2517
2518       // if a suitable block was found, add it to the flow and push it
2519       // onto the stack
2520       if (blk && flow->blockFits(blk, blkStack)) {
2521         blkArray[i] = NULL;
2522         --nBlocksLeft;
2523         blk->next = NULL;
2524         flow->addBlock(blk);
2525         fontSize = blk->lines->words->fontSize;
2526         blk->stackNext = blkStack;
2527         blkStack = blk;
2528
2529       // otherwise (if there is no block under the top block or the
2530       // block is not suitable), pop the stack
2531       } else {
2532         blkStack = blkStack->stackNext;
2533       }
2534     }
2535   }
2536   gfree(blkArray);
2537
2538 #if 0 // for debugging
2539   printf("*** flows ***\n");
2540   for (flow = flows; flow; flow = flow->next) {
2541     printf("flow: x=%.2f..%.2f y=%.2f..%.2f pri:%.2f..%.2f\n",
2542            flow->xMin, flow->xMax, flow->yMin, flow->yMax,
2543            flow->priMin, flow->priMax);
2544     for (blk = flow->blocks; blk; blk = blk->next) {
2545       printf("  block: rot=%d x=%.2f..%.2f y=%.2f..%.2f pri=%.2f..%.2f\n",
2546              blk->rot, blk->xMin, blk->xMax, blk->yMin, blk->yMax,
2547              blk->priMin, blk->priMax);
2548       for (line = blk->lines; line; line = line->next) {
2549         printf("    line:\n");
2550         for (word0 = line->words; word0; word0 = word0->next) {
2551           printf("      word: x=%.2f..%.2f y=%.2f..%.2f base=%.2f fontSize=%.2f space=%d: '",
2552                  word0->xMin, word0->xMax, word0->yMin, word0->yMax,
2553                  word0->base, word0->fontSize, word0->spaceAfter);
2554           for (i = 0; i < word0->len; ++i) {
2555             fputc(word0->text[i] & 0xff, stdout);
2556           }
2557           printf("'\n");
2558         }
2559       }
2560     }
2561   }
2562   printf("\n");
2563 #endif
2564
2565   if (uMap) {
2566     uMap->decRefCnt();
2567   }
2568 }
2569
2570 GBool TextPage::findText(Unicode *s, int len,
2571                          GBool startAtTop, GBool stopAtBottom,
2572                          GBool startAtLast, GBool stopAtLast,
2573                          double *xMin, double *yMin,
2574                          double *xMax, double *yMax) {
2575   TextBlock *blk;
2576   TextLine *line;
2577   Unicode *p;
2578   Unicode u1, u2;
2579   int m, i, j, k;
2580   double xStart, yStart, xStop, yStop;
2581   double xMin0, yMin0, xMax0, yMax0;
2582   double xMin1, yMin1, xMax1, yMax1;
2583   GBool found;
2584
2585   //~ needs to handle right-to-left text
2586
2587   if (rawOrder) {
2588     return gFalse;
2589   }
2590
2591   xStart = yStart = xStop = yStop = 0;
2592   if (startAtLast && haveLastFind) {
2593     xStart = lastFindXMin;
2594     yStart = lastFindYMin;
2595   } else if (!startAtTop) {
2596     xStart = *xMin;
2597     yStart = *yMin;
2598   }
2599   if (stopAtLast && haveLastFind) {
2600     xStop = lastFindXMin;
2601     yStop = lastFindYMin;
2602   } else if (!stopAtBottom) {
2603     xStop = *xMax;
2604     yStop = *yMax;
2605   }
2606
2607   found = gFalse;
2608   xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
2609   xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
2610
2611   for (i = 0; i < nBlocks; ++i) {
2612     blk = blocks[i];
2613
2614     // check: is the block above the top limit?
2615     if (!startAtTop && blk->yMax < yStart) {
2616       continue;
2617     }
2618
2619     // check: is the block below the bottom limit?
2620     if (!stopAtBottom && blk->yMin > yStop) {
2621       break;
2622     }
2623
2624     for (line = blk->lines; line; line = line->next) {
2625
2626       // check: is the line above the top limit?
2627       if (!startAtTop && line->yMin < yStart) {
2628         continue;
2629       }
2630
2631       // check: is the line below the bottom limit?
2632       if (!stopAtBottom && line->yMin > yStop) {
2633         continue;
2634       }
2635
2636       // search each position in this line
2637       m = line->len;
2638       for (j = 0, p = line->text; j <= m - len; ++j, ++p) {
2639
2640         // compare the strings
2641         for (k = 0; k < len; ++k) {
2642 #if 1 //~ this lowercases Latin A-Z only -- this will eventually be
2643       //~ extended to handle other character sets
2644           if (p[k] >= 0x41 && p[k] <= 0x5a) {
2645             u1 = p[k] + 0x20;
2646           } else {
2647             u1 = p[k];
2648           }
2649           if (s[k] >= 0x41 && s[k] <= 0x5a) {
2650             u2 = s[k] + 0x20;
2651           } else {
2652             u2 = s[k];
2653           }
2654 #endif
2655           if (u1 != u2) {
2656             break;
2657           }
2658         }
2659
2660         // found it
2661         if (k == len) {
2662           switch (line->rot) {
2663           case 0:
2664             xMin1 = line->edge[j];
2665             xMax1 = line->edge[j + len];
2666             yMin1 = line->yMin;
2667             yMax1 = line->yMax;
2668             break;
2669           case 1:
2670             xMin1 = line->xMin;
2671             xMax1 = line->xMax;
2672             yMin1 = line->edge[j];
2673             yMax1 = line->edge[j + len];
2674             break;
2675           case 2:
2676             xMin1 = line->edge[j + len];
2677             xMax1 = line->edge[j];
2678             yMin1 = line->yMin;
2679             yMax1 = line->yMax;
2680             break;
2681           case 3:
2682             xMin1 = line->xMin;
2683             xMax1 = line->xMax;
2684             yMin1 = line->edge[j + len];
2685             yMax1 = line->edge[j];
2686             break;
2687           }
2688           if ((startAtTop ||
2689                yMin1 > yStart || (yMin1 == yStart && xMin1 > xStart)) &&
2690               (stopAtBottom ||
2691                yMin1 < yStop || (yMin1 == yStop && xMin1 < yStop))) {
2692             if (!found || yMin1 < yMin0 || (yMin1 == yMin0 && xMin1 < xMin0)) {
2693               xMin0 = xMin1;
2694               xMax0 = xMax1;
2695               yMin0 = yMin1;
2696               yMax0 = yMax1;
2697               found = gTrue;
2698             }
2699           }
2700         }
2701       }
2702     }
2703   }
2704
2705   if (found) {
2706     *xMin = xMin0;
2707     *xMax = xMax0;
2708     *yMin = yMin0;
2709     *yMax = yMax0;
2710     lastFindXMin = xMin0;
2711     lastFindYMin = yMin0;
2712     haveLastFind = gTrue;
2713     return gTrue;
2714   }
2715
2716   return gFalse;
2717 }
2718
2719 GString *TextPage::getText(double xMin, double yMin,
2720                            double xMax, double yMax) {
2721   GString *s;
2722   UnicodeMap *uMap;
2723   GBool isUnicode;
2724   TextBlock *blk;
2725   TextLine *line;
2726   TextLineFrag *frags;
2727   int nFrags, fragsSize;
2728   TextLineFrag *frag;
2729   char space[8], eol[16];
2730   int spaceLen, eolLen;
2731   int lastRot;
2732   double x, y;
2733   int col, idx0, idx1, i, j;
2734   GBool multiLine, oneRot;
2735
2736   s = new GString();
2737
2738   if (rawOrder) {
2739     return s;
2740   }
2741
2742   // get the output encoding
2743   if (!(uMap = globalParams->getTextEncoding())) {
2744     return s;
2745   }
2746   isUnicode = uMap->isUnicode();
2747   spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
2748   eolLen = 0; // make gcc happy
2749   switch (globalParams->getTextEOL()) {
2750   case eolUnix:
2751     eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
2752     break;
2753   case eolDOS:
2754     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
2755     eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
2756     break;
2757   case eolMac:
2758     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
2759     break;
2760   }
2761
2762   //~ writing mode (horiz/vert)
2763
2764   // collect the line fragments that are in the rectangle
2765   fragsSize = 256;
2766   frags = (TextLineFrag *)gmalloc(fragsSize * sizeof(TextLineFrag));
2767   nFrags = 0;
2768   lastRot = -1;
2769   oneRot = gTrue;
2770   for (i = 0; i < nBlocks; ++i) {
2771     blk = blocks[i];
2772     if (xMin < blk->xMax && blk->xMin < xMax &&
2773         yMin < blk->yMax && blk->yMin < yMax) {
2774       for (line = blk->lines; line; line = line->next) {
2775         if (xMin < line->xMax && line->xMin < xMax &&
2776             yMin < line->yMax && line->yMin < yMax) {
2777           idx0 = idx1 = -1;
2778           switch (line->rot) {
2779           case 0:
2780             y = 0.5 * (line->yMin + line->yMax);
2781             if (yMin < y && y < yMax) {
2782               j = 0;
2783               while (j < line->len) {
2784                 if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
2785                   idx0 = j;
2786                   break;
2787                 }
2788                 ++j;
2789               }
2790               j = line->len - 1;
2791               while (j >= 0) {
2792                 if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
2793                   idx1 = j;
2794                   break;
2795                 }
2796                 --j;
2797               }
2798             }
2799             break;
2800           case 1:
2801             x = 0.5 * (line->xMin + line->xMax);
2802             if (xMin < x && x < xMax) {
2803               j = 0;
2804               while (j < line->len) {
2805                 if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
2806                   idx0 = j;
2807                   break;
2808                 }
2809                 ++j;
2810               }
2811               j = line->len - 1;
2812               while (j >= 0) {
2813                 if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
2814                   idx1 = j;
2815                   break;
2816                 }
2817                 --j;
2818               }
2819             }
2820             break;
2821           case 2:
2822             y = 0.5 * (line->yMin + line->yMax);
2823             if (yMin < y && y < yMax) {
2824               j = 0;
2825               while (j < line->len) {
2826                 if (0.5 * (line->edge[j] + line->edge[j+1]) < xMax) {
2827                   idx0 = j;
2828                   break;
2829                 }
2830                 ++j;
2831               }
2832               j = line->len - 1;
2833               while (j >= 0) {
2834                 if (0.5 * (line->edge[j] + line->edge[j+1]) > xMin) {
2835                   idx1 = j;
2836                   break;
2837                 }
2838                 --j;
2839               }
2840             }
2841             break;
2842           case 3:
2843             x = 0.5 * (line->xMin + line->xMax);
2844             if (xMin < x && x < xMax) {
2845               j = 0;
2846               while (j < line->len) {
2847                 if (0.5 * (line->edge[j] + line->edge[j+1]) < yMax) {
2848                   idx0 = j;
2849                   break;
2850                 }
2851                 ++j;
2852               }
2853               j = line->len - 1;
2854               while (j >= 0) {
2855                 if (0.5 * (line->edge[j] + line->edge[j+1]) > yMin) {
2856                   idx1 = j;
2857                   break;
2858                 }
2859                 --j;
2860               }
2861             }
2862             break;
2863           }
2864           if (idx0 >= 0 && idx1 >= 0) {
2865             if (nFrags == fragsSize) {
2866               fragsSize *= 2;
2867               frags = (TextLineFrag *)
2868                           grealloc(frags, fragsSize * sizeof(TextLineFrag));
2869             }
2870             frags[nFrags].init(line, idx0, idx1 - idx0 + 1);
2871             ++nFrags;
2872             if (lastRot >= 0 && line->rot != lastRot) {
2873               oneRot = gFalse;
2874             }
2875             lastRot = line->rot;
2876           }
2877         }
2878       }
2879     }
2880   }
2881
2882   // sort the fragments and generate the string
2883   if (nFrags > 0) {
2884
2885     for (i = 0; i < nFrags; ++i) {
2886       frags[i].computeCoords(oneRot);
2887     }
2888     assignColumns(frags, nFrags, oneRot);
2889
2890     // if all lines in the region have the same rotation, use it;
2891     // otherwise, use the page's primary rotation
2892     if (oneRot) {
2893       qsort(frags, nFrags, sizeof(TextLineFrag),
2894             &TextLineFrag::cmpYXLineRot);
2895     } else {
2896       qsort(frags, nFrags, sizeof(TextLineFrag),
2897             &TextLineFrag::cmpYXPrimaryRot);
2898     }
2899
2900     col = 0;
2901     multiLine = gFalse;
2902     for (i = 0; i < nFrags; ++i) {
2903       frag = &frags[i];
2904
2905       // insert a return
2906       if (frag->col < col ||
2907           (i > 0 && fabs(frag->base - frags[i-1].base) >
2908                       maxIntraLineDelta * frags[i-1].line->words->fontSize)) {
2909         s->append(eol, eolLen);
2910         col = 0;
2911         multiLine = gTrue;
2912       }
2913
2914       // column alignment
2915       for (; col < frag->col; ++col) {
2916         s->append(space, spaceLen);
2917       }
2918
2919       // get the fragment text
2920       col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
2921     }
2922
2923     if (multiLine) {
2924       s->append(eol, eolLen);
2925     }
2926   }
2927
2928   gfree(frags);
2929   uMap->decRefCnt();
2930
2931   return s;
2932 }
2933
2934 GBool TextPage::findCharRange(int pos, int length,
2935                               double *xMin, double *yMin,
2936                               double *xMax, double *yMax) {
2937   TextBlock *blk;
2938   TextLine *line;
2939   TextWord *word;
2940   double xMin0, xMax0, yMin0, yMax0;
2941   double xMin1, xMax1, yMin1, yMax1;
2942   GBool first;
2943   int i, j0, j1;
2944
2945   if (rawOrder) {
2946     return gFalse;
2947   }
2948
2949   //~ this doesn't correctly handle:
2950   //~ - ranges split across multiple lines (the highlighted region
2951   //~   is the bounding box of all the parts of the range)
2952   //~ - cases where characters don't convert one-to-one into Unicode
2953   first = gTrue;
2954   xMin0 = xMax0 = yMin0 = yMax0 = 0; // make gcc happy
2955   xMin1 = xMax1 = yMin1 = yMax1 = 0; // make gcc happy
2956   for (i = 0; i < nBlocks; ++i) {
2957     blk = blocks[i];
2958     for (line = blk->lines; line; line = line->next) {
2959       for (word = line->words; word; word = word->next) {
2960         if (pos < word->charPos + word->charLen &&
2961             word->charPos < pos + length) {
2962           j0 = pos - word->charPos;
2963           if (j0 < 0) {
2964             j0 = 0;
2965           }
2966           j1 = pos + length - 1 - word->charPos;
2967           if (j1 >= word->len) {
2968             j1 = word->len - 1;
2969           }
2970           switch (line->rot) {
2971           case 0:
2972             xMin1 = word->edge[j0];
2973             xMax1 = word->edge[j1 + 1];
2974             yMin1 = word->yMin;
2975             yMax1 = word->yMax;
2976             break;
2977           case 1:
2978             xMin1 = word->xMin;
2979             xMax1 = word->xMax;
2980             yMin1 = word->edge[j0];
2981             yMax1 = word->edge[j1 + 1];
2982             break;
2983           case 2:
2984             xMin1 = word->edge[j1 + 1];
2985             xMax1 = word->edge[j0];
2986             yMin1 = word->yMin;
2987             yMax1 = word->yMax;
2988             break;
2989           case 3:
2990             xMin1 = word->xMin;
2991             xMax1 = word->xMax;
2992             yMin1 = word->edge[j1 + 1];
2993             yMax1 = word->edge[j0];
2994             break;
2995           }
2996           if (first || xMin1 < xMin0) {
2997             xMin0 = xMin1;
2998           }
2999           if (first || xMax1 > xMax0) {
3000             xMax0 = xMax1;
3001           }
3002           if (first || yMin1 < yMin0) {
3003             yMin0 = yMin1;
3004           }
3005           if (first || yMax1 > yMax0) {
3006             yMax0 = yMax1;
3007           }
3008           first = gFalse;
3009         }
3010       }
3011     }
3012   }
3013   if (!first) {
3014     *xMin = xMin0;
3015     *xMax = xMax0;
3016     *yMin = yMin0;
3017     *yMax = yMax0;
3018     return gTrue;
3019   }
3020   return gFalse;
3021 }
3022
3023 void TextPage::dump(void *outputStream, TextOutputFunc outputFunc,
3024                     GBool physLayout) {
3025   UnicodeMap *uMap;
3026   TextFlow *flow;
3027   TextBlock *blk;
3028   TextLine *line;
3029   TextLineFrag *frags;
3030   TextWord *word;
3031   int nFrags, fragsSize;
3032   TextLineFrag *frag;
3033   char space[8], eol[16], eop[8];
3034   int spaceLen, eolLen, eopLen;
3035   GBool pageBreaks;
3036   GString *s;
3037   int col, i, d, n;
3038
3039   // get the output encoding
3040   if (!(uMap = globalParams->getTextEncoding())) {
3041     return;
3042   }
3043   spaceLen = uMap->mapUnicode(0x20, space, sizeof(space));
3044   eolLen = 0; // make gcc happy
3045   switch (globalParams->getTextEOL()) {
3046   case eolUnix:
3047     eolLen = uMap->mapUnicode(0x0a, eol, sizeof(eol));
3048     break;
3049   case eolDOS:
3050     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3051     eolLen += uMap->mapUnicode(0x0a, eol + eolLen, sizeof(eol) - eolLen);
3052     break;
3053   case eolMac:
3054     eolLen = uMap->mapUnicode(0x0d, eol, sizeof(eol));
3055     break;
3056   }
3057   eopLen = uMap->mapUnicode(0x0c, eop, sizeof(eop));
3058   pageBreaks = globalParams->getTextPageBreaks();
3059
3060   //~ writing mode (horiz/vert)
3061
3062   // output the page in raw (content stream) order
3063   if (rawOrder) {
3064
3065     for (word = rawWords; word; word = word->next) {
3066       s = new GString();
3067       dumpFragment(word->text, word->len, uMap, s);
3068       (*outputFunc)(outputStream, s->getCString(), s->getLength());
3069       delete s;
3070       if (word->next &&
3071           fabs(word->next->base - word->base) <
3072             maxIntraLineDelta * word->fontSize) {
3073         if (word->next->xMin > word->xMax + minWordSpacing * word->fontSize) {
3074           (*outputFunc)(outputStream, space, spaceLen);
3075         }
3076       } else {
3077         (*outputFunc)(outputStream, eol, eolLen);
3078       }
3079     }
3080
3081   // output the page, maintaining the original physical layout
3082   } else if (physLayout) {
3083
3084     // collect the line fragments for the page and sort them
3085     fragsSize = 256;
3086     frags = (TextLineFrag *)gmalloc(fragsSize * sizeof(TextLineFrag));
3087     nFrags = 0;
3088     for (i = 0; i < nBlocks; ++i) {
3089       blk = blocks[i];
3090       for (line = blk->lines; line; line = line->next) {
3091         if (nFrags == fragsSize) {
3092           fragsSize *= 2;
3093           frags = (TextLineFrag *)grealloc(frags,
3094                                            fragsSize * sizeof(TextLineFrag));
3095         }
3096         frags[nFrags].init(line, 0, line->len);
3097         frags[nFrags].computeCoords(gTrue);
3098         ++nFrags;
3099       }
3100     }
3101     qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpYXPrimaryRot);
3102
3103     // generate output
3104     col = 0;
3105     for (i = 0; i < nFrags; ++i) {
3106       frag = &frags[i];
3107
3108       // column alignment
3109       for (; col < frag->col; ++col) {
3110         (*outputFunc)(outputStream, space, spaceLen);
3111       }
3112
3113       // print the line
3114       s = new GString();
3115       col += dumpFragment(frag->line->text + frag->start, frag->len, uMap, s);
3116       (*outputFunc)(outputStream, s->getCString(), s->getLength());
3117       delete s;
3118
3119       // print one or more returns if necessary
3120       if (i == nFrags - 1 ||
3121           frags[i+1].col < col ||
3122           fabs(frags[i+1].base - frag->base) >
3123             maxIntraLineDelta * frag->line->words->fontSize) {
3124         if (i < nFrags - 1) {
3125           d = (int)((frags[i+1].base - frag->base) /
3126                     frag->line->words->fontSize);
3127           if (d < 1) {
3128             d = 1;
3129           } else if (d > 5) {
3130             d = 5;
3131           }
3132         } else {
3133           d = 1;
3134         }
3135         for (; d > 0; --d) {
3136           (*outputFunc)(outputStream, eol, eolLen);
3137         }
3138         col = 0;
3139       }
3140     }
3141
3142     gfree(frags);
3143
3144   // output the page, "undoing" the layout
3145   } else {
3146     for (flow = flows; flow; flow = flow->next) {
3147       for (blk = flow->blocks; blk; blk = blk->next) {
3148         for (line = blk->lines; line; line = line->next) {
3149           n = line->len;
3150           if (line->hyphenated && (line->next || blk->next)) {
3151             --n;
3152           }
3153           s = new GString();
3154           dumpFragment(line->text, n, uMap, s);
3155           (*outputFunc)(outputStream, s->getCString(), s->getLength());
3156           delete s;
3157           if (!line->hyphenated) {
3158             if (line->next) {
3159               (*outputFunc)(outputStream, space, spaceLen);
3160             } else if (blk->next) {
3161               //~ this is a bit of a kludge - we should really do a more
3162               //~ intelligent determination of paragraphs
3163               if (blk->next->lines->words->fontSize ==
3164                   blk->lines->words->fontSize) {
3165                 (*outputFunc)(outputStream, space, spaceLen);
3166               } else {
3167                 (*outputFunc)(outputStream, eol, eolLen);
3168               }
3169             }
3170           }
3171         }
3172       }
3173       (*outputFunc)(outputStream, eol, eolLen);
3174       (*outputFunc)(outputStream, eol, eolLen);
3175     }
3176   }
3177
3178   // end of page
3179   if (pageBreaks) {
3180     (*outputFunc)(outputStream, eop, eopLen);
3181     (*outputFunc)(outputStream, eol, eolLen);
3182   }
3183
3184   uMap->decRefCnt();
3185 }
3186
3187 void TextPage::assignColumns(TextLineFrag *frags, int nFrags, GBool oneRot) {
3188   TextLineFrag *frag0, *frag1;
3189   int rot, col1, col2, i, j, k;
3190
3191   // all text in the region has the same rotation -- recompute the
3192   // column numbers based only on the text in the region
3193   if (oneRot) {
3194     qsort(frags, nFrags, sizeof(TextLineFrag), &TextLineFrag::cmpXYLineRot);
3195     rot = frags[0].line->rot;
3196     for (i = 0; i < nFrags; ++i) {
3197       frag0 = &frags[i];
3198       col1 = 0;
3199       for (j = 0; j < i; ++j) {
3200         frag1 = &frags[j];
3201         col2 = 0; // make gcc happy
3202         switch (rot) {
3203         case 0:
3204           if (frag0->xMin >= frag1->xMax) {
3205             col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
3206                                  frag1->line->col[frag1->start]) + 1;
3207           } else {
3208             for (k = frag1->start;
3209                  k < frag1->start + frag1->len &&
3210                    frag0->xMin >= 0.5 * (frag1->line->edge[k] +
3211                                          frag1->line->edge[k+1]);
3212                  ++k) ;
3213             col2 = frag1->col +
3214                    frag1->line->col[k] - frag1->line->col[frag1->start];
3215           }
3216           break;
3217         case 1:
3218           if (frag0->yMin >= frag1->yMax) {
3219             col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
3220                                  frag1->line->col[frag1->start]) + 1;
3221           } else {
3222             for (k = frag1->start;
3223                  k < frag1->start + frag1->len &&
3224                    frag0->yMin >= 0.5 * (frag1->line->edge[k] +
3225                                          frag1->line->edge[k+1]);
3226                  ++k) ;
3227             col2 = frag1->col +
3228                    frag1->line->col[k] - frag1->line->col[frag1->start];
3229           }
3230           break;
3231         case 2:
3232           if (frag0->xMax <= frag1->xMin) {
3233             col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
3234                                  frag1->line->col[frag1->start]) + 1;
3235           } else {
3236             for (k = frag1->start;
3237                  k < frag1->start + frag1->len &&
3238                    frag0->xMax <= 0.5 * (frag1->line->edge[k] +
3239                                          frag1->line->edge[k+1]);
3240                  ++k) ;
3241             col2 = frag1->col +
3242                    frag1->line->col[k] - frag1->line->col[frag1->start];
3243           }
3244           break;
3245         case 3:
3246           if (frag0->yMax <= frag1->yMin) {
3247             col2 = frag1->col + (frag1->line->col[frag1->start + frag1->len] -
3248                                  frag1->line->col[frag1->start]) + 1;
3249           } else {
3250             for (k = frag1->start;
3251                  k < frag1->start + frag1->len &&
3252                    frag0->yMax <= 0.5 * (frag1->line->edge[k] +
3253                                          frag1->line->edge[k+1]);
3254                  ++k) ;
3255             col2 = frag1->col +
3256                    frag1->line->col[k] - frag1->line->col[frag1->start];
3257           }
3258           break;
3259         }
3260         if (col2 > col1) {
3261           col1 = col2;
3262         }
3263       }
3264       frag0->col = col1;
3265     }
3266
3267   // the region includes text at different rotations -- use the
3268   // globally assigned column numbers, offset by the minimum column
3269   // number (i.e., shift everything over to column 0)
3270   } else {
3271     col1 = frags[0].col;
3272     for (i = 1; i < nFrags; ++i) {
3273       if (frags[i].col < col1) {
3274         col1 = frags[i].col;
3275       }
3276     }
3277     for (i = 0; i < nFrags; ++i) {
3278       frags[i].col -= col1;
3279     }
3280   }
3281 }
3282
3283 int TextPage::dumpFragment(Unicode *text, int len, UnicodeMap *uMap,
3284                            GString *s) {
3285   char lre[8], rle[8], popdf[8], buf[8];
3286   int lreLen, rleLen, popdfLen, n;
3287   int nCols, i, j, k;
3288
3289   nCols = 0;
3290
3291   if (uMap->isUnicode()) {
3292
3293     lreLen = uMap->mapUnicode(0x202a, lre, sizeof(lre));
3294     rleLen = uMap->mapUnicode(0x202b, rle, sizeof(rle));
3295     popdfLen = uMap->mapUnicode(0x202c, popdf, sizeof(popdf));
3296
3297     if (primaryLR) {
3298
3299       i = 0;
3300       while (i < len) {
3301         // output a left-to-right section
3302         for (j = i; j < len && !unicodeTypeR(text[j]); ++j) ;
3303         for (k = i; k < j; ++k) {
3304           n = uMap->mapUnicode(text[k], buf, sizeof(buf));
3305           s->append(buf, n);
3306           ++nCols;
3307         }
3308         i = j;
3309         // output a right-to-left section
3310         for (j = i; j < len && !unicodeTypeL(text[j]); ++j) ;
3311         if (j > i) {
3312           s->append(rle, rleLen);
3313           for (k = j - 1; k >= i; --k) {
3314             n = uMap->mapUnicode(text[k], buf, sizeof(buf));
3315             s->append(buf, n);
3316             ++nCols;
3317           }
3318           s->append(popdf, popdfLen);
3319           i = j;
3320         }
3321       }
3322
3323     } else {
3324
3325       s->append(rle, rleLen);
3326       i = len - 1;
3327       while (i >= 0) {
3328         // output a right-to-left section
3329         for (j = i; j >= 0 && !unicodeTypeL(text[j]); --j) ;
3330         for (k = i; k > j; --k) {
3331           n = uMap->mapUnicode(text[k], buf, sizeof(buf));
3332           s->append(buf, n);
3333           ++nCols;
3334         }
3335         i = j;
3336         // output a left-to-right section
3337         for (j = i; j >= 0 && !unicodeTypeR(text[j]); --j) ;
3338         if (j < i) {
3339           s->append(lre, lreLen);
3340           for (k = j + 1; k <= i; ++k) {
3341             n = uMap->mapUnicode(text[k], buf, sizeof(buf));
3342             s->append(buf, n);
3343             ++nCols;
3344           }
3345           s->append(popdf, popdfLen);
3346           i = j;
3347         }
3348       }
3349       s->append(popdf, popdfLen);
3350
3351     }
3352
3353   } else {
3354     for (i = 0; i < len; ++i) {
3355       n = uMap->mapUnicode(text[i], buf, sizeof(buf));
3356       s->append(buf, n);
3357       nCols += n;
3358     }
3359   }
3360
3361   return nCols;
3362 }
3363
3364 #if TEXTOUT_WORD_LIST
3365 TextWordList *TextPage::makeWordList(GBool physLayout) {
3366   return new TextWordList(this, physLayout);
3367 }
3368 #endif
3369
3370 //------------------------------------------------------------------------
3371 // TextOutputDev
3372 //------------------------------------------------------------------------
3373
3374 static void outputToFile(void *stream, char *text, int len) {
3375   fwrite(text, 1, len, (FILE *)stream);
3376 }
3377
3378 TextOutputDev::TextOutputDev(char *fileName, GBool physLayoutA,
3379                              GBool rawOrderA, GBool append) {
3380   text = NULL;
3381   physLayout = physLayoutA;
3382   rawOrder = rawOrderA;
3383   ok = gTrue;
3384
3385   // open file
3386   needClose = gFalse;
3387   if (fileName) {
3388     if (!strcmp(fileName, "-")) {
3389       outputStream = stdout;
3390 #ifdef WIN32
3391       // keep DOS from munging the end-of-line characters
3392       setmode(fileno(stdout), O_BINARY);
3393 #endif
3394     } else if ((outputStream = fopen(fileName, append ? "ab" : "wb"))) {
3395       needClose = gTrue;
3396     } else {
3397       error(-1, "Couldn't open text file '%s'", fileName);
3398       ok = gFalse;
3399       return;
3400     }
3401     outputFunc = &outputToFile;
3402   } else {
3403     outputStream = NULL;
3404   }
3405
3406   // set up text object
3407   text = new TextPage(rawOrderA);
3408 }
3409
3410 TextOutputDev::TextOutputDev(TextOutputFunc func, void *stream,
3411                              GBool physLayoutA, GBool rawOrderA) {
3412   outputFunc = func;
3413   outputStream = stream;
3414   needClose = gFalse;
3415   physLayout = physLayoutA;
3416   rawOrder = rawOrderA;
3417   text = new TextPage(rawOrderA);
3418   ok = gTrue;
3419 }
3420
3421 TextOutputDev::~TextOutputDev() {
3422   if (needClose) {
3423 #ifdef MACOS
3424     ICS_MapRefNumAndAssign((short)((FILE *)outputStream)->handle);
3425 #endif
3426     fclose((FILE *)outputStream);
3427   }
3428   if (text) {
3429     delete text;
3430   }
3431 }
3432
3433 void TextOutputDev::startPage(int pageNum, GfxState *state) {
3434   text->startPage(state);
3435 }
3436
3437 void TextOutputDev::endPage() {
3438   text->coalesce(physLayout);
3439   if (outputStream) {
3440     text->dump(outputStream, outputFunc, physLayout);
3441   }
3442 }
3443
3444 void TextOutputDev::updateFont(GfxState *state) {
3445   text->updateFont(state);
3446 }
3447
3448 void TextOutputDev::beginString(GfxState *state, GString *s) {
3449   text->beginWord(state, state->getCurX(), state->getCurY());
3450 }
3451
3452 void TextOutputDev::endString(GfxState *state) {
3453   text->endWord();
3454 }
3455
3456 void TextOutputDev::drawChar(GfxState *state, double x, double y,
3457                              double dx, double dy,
3458                              double originX, double originY,
3459                              CharCode c, Unicode *u, int uLen) {
3460   text->addChar(state, x, y, dx, dy, c, u, uLen);
3461 }
3462
3463 GBool TextOutputDev::findText(Unicode *s, int len,
3464                               GBool startAtTop, GBool stopAtBottom,
3465                               GBool startAtLast, GBool stopAtLast,
3466                               double *xMin, double *yMin,
3467                               double *xMax, double *yMax) {
3468   return text->findText(s, len, startAtTop, stopAtBottom,
3469                         startAtLast, stopAtLast, xMin, yMin, xMax, yMax);
3470 }
3471
3472 GString *TextOutputDev::getText(double xMin, double yMin,
3473                                 double xMax, double yMax) {
3474   return text->getText(xMin, yMin, xMax, yMax);
3475 }
3476
3477 GBool TextOutputDev::findCharRange(int pos, int length,
3478                                    double *xMin, double *yMin,
3479                                    double *xMax, double *yMax) {
3480   return text->findCharRange(pos, length, xMin, yMin, xMax, yMax);
3481 }
3482
3483 #if TEXTOUT_WORD_LIST
3484 TextWordList *TextOutputDev::makeWordList() {
3485   return text->makeWordList(physLayout);
3486 }
3487 #endif