| //======================================================================== |
| // |
| // TextOutputDev.cc |
| // |
| // Copyright 1997-2003 Glyph & Cog, LLC |
| // |
| //======================================================================== |
| |
| //======================================================================== |
| // |
| // Modified under the Poppler project - http://poppler.freedesktop.org |
| // |
| // All changes made under the Poppler project to this file are licensed |
| // under GPL version 2 or later |
| // |
| // Copyright (C) 2005-2007 Kristian Høgsberg <krh@redhat.com> |
| // Copyright (C) 2005 Nickolay V. Shmyrev <nshmyrev@yandex.ru> |
| // Copyright (C) 2006-2008, 2011-2013 Carlos Garcia Campos <carlosgc@gnome.org> |
| // Copyright (C) 2006, 2007, 2013 Ed Catmur <ed@catmur.co.uk> |
| // Copyright (C) 2006 Jeff Muizelaar <jeff@infidigm.net> |
| // Copyright (C) 2007, 2008, 2012, 2017 Adrian Johnson <ajohnson@redneon.com> |
| // Copyright (C) 2008 Koji Otani <sho@bbr.jp> |
| // Copyright (C) 2008, 2010-2012, 2014-2022, 2024 Albert Astals Cid <aacid@kde.org> |
| // Copyright (C) 2008 Pino Toscano <pino@kde.org> |
| // Copyright (C) 2008, 2010 Hib Eris <hib@hiberis.nl> |
| // Copyright (C) 2009 Ross Moore <ross@maths.mq.edu.au> |
| // Copyright (C) 2009 Kovid Goyal <kovid@kovidgoyal.net> |
| // Copyright (C) 2010 Brian Ewins <brian.ewins@gmail.com> |
| // Copyright (C) 2010, 2021 Marek Kasik <mkasik@redhat.com> |
| // Copyright (C) 2010, 2020 Suzuki Toshiya <mpsuzuki@hiroshima-u.ac.jp> |
| // Copyright (C) 2011 Sam Liao <phyomh@gmail.com> |
| // Copyright (C) 2012 Horst Prote <prote@fmi.uni-stuttgart.de> |
| // Copyright (C) 2012, 2013-2018 Jason Crain <jason@aquaticape.us> |
| // Copyright (C) 2012 Peter Breitenlohner <peb@mppmu.mpg.de> |
| // Copyright (C) 2013 José Aliste <jaliste@src.gnome.org> |
| // Copyright (C) 2013 Thomas Freitag <Thomas.Freitag@alfa.de> |
| // Copyright (C) 2013 Ed Catmur <ed@catmur.co.uk> |
| // Copyright (C) 2016 Khaled Hosny <khaledhosny@eglug.org> |
| // Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, <info@kdab.com>. Work sponsored by the LiMux project of the city of Munich |
| // Copyright (C) 2018 Sanchit Anand <sanxchit@gmail.com> |
| // Copyright (C) 2018 Adam Reichold <adam.reichold@t-online.de> |
| // Copyright (C) 2018-2022, 2024 Nelson Benítez León <nbenitezl@gmail.com> |
| // Copyright (C) 2019 Christian Persch <chpe@src.gnome.org> |
| // Copyright (C) 2019, 2022 Oliver Sander <oliver.sander@tu-dresden.de> |
| // Copyright (C) 2019 Dan Shea <dan.shea@logical-innovations.com> |
| // Copyright (C) 2021 Peter Williams <peter@newton.cx> |
| // Copyright (C) 2024 Adam Sampson <ats@offog.org> |
| // Copyright (C) 2024 g10 Code GmbH, Author: Sune Stolborg Vuorela <sune@vuorela.dk> |
| // Copyright (C) 2024 Stefan Brüns <stefan.bruens@rwth-aachen.de> |
| // |
| // To see a description of the changes please see the Changelog file that |
| // came with your tarball or type make ChangeLog if you are building from git |
| // |
| //======================================================================== |
| |
| #include <config.h> |
| |
| #include <cstdio> |
| #include <cstdlib> |
| #include <cstddef> |
| #include <cmath> |
| #include <cfloat> |
| #include <cctype> |
| #include <algorithm> |
| #if defined(_WIN32) || defined(__CYGWIN__) |
| # include <fcntl.h> // for O_BINARY |
| # include <io.h> // for _setmode |
| #endif |
| #include "goo/gfile.h" |
| #include "goo/gmem.h" |
| #include "goo/GooString.h" |
| #include "poppler-config.h" |
| #include "Error.h" |
| #include "GlobalParams.h" |
| #include "UnicodeMap.h" |
| #include "UnicodeTypeTable.h" |
| #include "Link.h" |
| #include "TextOutputDev.h" |
| #include "Page.h" |
| #include "Annot.h" |
| #include "UTF.h" |
| |
| //------------------------------------------------------------------------ |
| // parameters |
| //------------------------------------------------------------------------ |
| |
| // Each bucket in a text pool includes baselines within a range of |
| // this many points. |
| #define textPoolStep 4 |
| |
| // Inter-character space width which will cause addChar to start a new |
| // word. |
| #define minWordBreakSpace 0.1 |
| |
| // Negative inter-character space width, i.e., overlap, which will |
| // cause addChar to start a new word. |
| #define minDupBreakOverlap 0.2 |
| |
| // Max distance between baselines of two lines within a block, as a |
| // fraction of the font size. |
| #define maxLineSpacingDelta 1.5 |
| |
| // Max difference in primary font sizes on two lines in the same |
| // block. Delta1 is used when examining new lines above and below the |
| // current block; delta2 is used when examining text that overlaps the |
| // current block; delta3 is used when examining text to the left and |
| // right of the current block. |
| #define maxBlockFontSizeDelta1 0.05 |
| #define maxBlockFontSizeDelta2 0.6 |
| #define maxBlockFontSizeDelta3 0.2 |
| |
| // Max difference in font sizes inside a word. |
| #define maxWordFontSizeDelta 0.05 |
| |
| // Maximum distance between baselines of two words on the same line, |
| // e.g., distance between subscript or superscript and the primary |
| // baseline, as a fraction of the font size. |
| #define maxIntraLineDelta 0.5 |
| |
| // Minimum inter-word spacing, as a fraction of the font size. (Only |
| // used for raw ordering.) |
| #define minWordSpacing 0.15 |
| |
| // Maximum inter-word spacing, as a fraction of the font size. |
| #define maxWordSpacing 1.5 |
| |
| // Maximum horizontal spacing which will allow a word to be pulled |
| // into a block, as a fraction of the font size. |
| // This default value can be tweaked via API. |
| double TextOutputDev::minColSpacing1_default = 0.7; |
| |
| // Minimum spacing between columns, as a fraction of the font size. |
| #define minColSpacing2 1.0 |
| |
| // Maximum vertical spacing between blocks within a flow, as a |
| // multiple of the font size. |
| #define maxBlockSpacing 2.5 |
| |
| // Minimum spacing between characters within a word, as a fraction of |
| // the font size. |
| #define minCharSpacing (-0.5) |
| |
| // Maximum spacing between characters within a word, as a fraction of |
| // the font size, when there is no obvious extra-wide character |
| // spacing. |
| #define maxCharSpacing 0.03 |
| |
| // When extra-wide character spacing is detected, the inter-character |
| // space threshold is set to the minimum inter-character space |
| // multiplied by this constant. |
| #define maxWideCharSpacingMul 1.3 |
| |
| // Upper limit on spacing between characters in a word. |
| #define maxWideCharSpacing 0.4 |
| |
| // Max difference in primary,secondary coordinates (as a fraction of |
| // the font size) allowed for duplicated text (fake boldface, drop |
| // shadows) which is to be discarded. |
| #define dupMaxPriDelta 0.1 |
| #define dupMaxSecDelta 0.2 |
| |
| // Max width of underlines (in points). |
| #define maxUnderlineWidth 3 |
| |
| // Min distance between baseline and underline (in points). |
| //~ this should be font-size-dependent |
| #define minUnderlineGap (-2) |
| |
| // Max distance between baseline and underline (in points). |
| //~ this should be font-size-dependent |
| #define maxUnderlineGap 4 |
| |
| // Max horizontal distance between edge of word and start of underline |
| // (in points). |
| //~ this should be font-size-dependent |
| #define underlineSlack 1 |
| |
| // Max distance between edge of text and edge of link border |
| #define hyperlinkSlack 2 |
| |
| // Max distance between characters when combining a base character and |
| // combining character |
| #define combMaxMidDelta 0.3 |
| #define combMaxBaseDelta 0.4 |
| |
| // Text is considered diagonal if abs(tan(angle)) > diagonalThreshold. |
| // (Or 1/tan(angle) for 90/270 degrees.) |
| #define diagonalThreshold 0.1 |
| |
| // How opaque a selection on a glyphless font should be. Since the font is |
| // glyphless and overlaid over text in image form, this must enable users |
| // to read the underlying image. Issue #157 |
| #define glyphlessSelectionOpacity 0.4 |
| |
| // Returns whether x is between a and b or equal to a or b. |
| // a and b don't need to be sorted. |
| #define XBetweenAB(x, a, b) (!(((x) > (a) && (x) > (b)) || ((x) < (a) && (x) < (b))) ? true : false) |
| |
| namespace { |
| |
| inline bool isAscii7(Unicode uchar) |
| { |
| return uchar < 128; |
| } |
| |
| } |
| |
| static int reorderText(const Unicode *text, int len, const UnicodeMap *uMap, bool primaryLR, GooString *s, Unicode *u) |
| { |
| char lre[8], rle[8], popdf[8], buf[8]; |
| int lreLen = 0, rleLen = 0, popdfLen = 0, n; |
| int nCols, i, j, k; |
| |
| nCols = 0; |
| |
| if (s) { |
| lreLen = uMap->mapUnicode(0x202a, lre, sizeof(lre)); |
| rleLen = uMap->mapUnicode(0x202b, rle, sizeof(rle)); |
| popdfLen = uMap->mapUnicode(0x202c, popdf, sizeof(popdf)); |
| } |
| |
| if (primaryLR) { |
| i = 0; |
| while (i < len) { |
| // output a left-to-right section |
| for (j = i; j < len && !unicodeTypeR(text[j]); ++j) { |
| ; |
| } |
| for (k = i; k < j; ++k) { |
| if (s) { |
| n = uMap->mapUnicode(text[k], buf, sizeof(buf)); |
| s->append(buf, n); |
| } |
| if (u) { |
| u[nCols] = text[k]; |
| } |
| ++nCols; |
| } |
| i = j; |
| // output a right-to-left section |
| for (j = i; j < len && !(unicodeTypeL(text[j]) || unicodeTypeNum(text[j])); ++j) { |
| ; |
| } |
| if (j > i) { |
| if (s) { |
| s->append(rle, rleLen); |
| } |
| for (k = j - 1; k >= i; --k) { |
| if (s) { |
| n = uMap->mapUnicode(text[k], buf, sizeof(buf)); |
| s->append(buf, n); |
| } |
| if (u) { |
| u[nCols] = text[k]; |
| } |
| ++nCols; |
| } |
| if (s) { |
| s->append(popdf, popdfLen); |
| } |
| i = j; |
| } |
| } |
| } else { |
| // Note: This code treats numeric characters (European and |
| // Arabic/Indic) as left-to-right, which isn't strictly correct |
| // (incurs extra LRE/POPDF pairs), but does produce correct |
| // visual formatting. |
| if (s) { |
| s->append(rle, rleLen); |
| } |
| i = len - 1; |
| while (i >= 0) { |
| // output a right-to-left section |
| for (j = i; j >= 0 && !(unicodeTypeL(text[j]) || unicodeTypeNum(text[j])); --j) { |
| ; |
| } |
| for (k = i; k > j; --k) { |
| if (s) { |
| n = uMap->mapUnicode(text[k], buf, sizeof(buf)); |
| s->append(buf, n); |
| } |
| if (u) { |
| u[nCols] = text[k]; |
| } |
| ++nCols; |
| } |
| i = j; |
| // output a left-to-right section |
| for (j = i; j >= 0 && !unicodeTypeR(text[j]); --j) { |
| ; |
| } |
| if (j < i) { |
| if (s) { |
| s->append(lre, lreLen); |
| } |
| for (k = j + 1; k <= i; ++k) { |
| if (s) { |
| n = uMap->mapUnicode(text[k], buf, sizeof(buf)); |
| s->append(buf, n); |
| } |
| if (u) { |
| u[nCols] = text[k]; |
| } |
| ++nCols; |
| } |
| if (s) { |
| s->append(popdf, popdfLen); |
| } |
| i = j; |
| } |
| } |
| if (s) { |
| s->append(popdf, popdfLen); |
| } |
| } |
| |
| return nCols; |
| } |
| |
| //------------------------------------------------------------------------ |
| // TextUnderline |
| //------------------------------------------------------------------------ |
| |
| class TextUnderline |
| { |
| public: |
| TextUnderline(double x0A, double y0A, double x1A, double y1A) |
| { |
| x0 = x0A; |
| y0 = y0A; |
| x1 = x1A; |
| y1 = y1A; |
| horiz = y0 == y1; |
| } |
| ~TextUnderline() { } |
| |
| double x0, y0, x1, y1; |
| bool horiz; |
| }; |
| |
| //------------------------------------------------------------------------ |
| // TextLink |
| //------------------------------------------------------------------------ |
| |
| class TextLink |
| { |
| public: |
| TextLink(int xMinA, int yMinA, int xMaxA, int yMaxA, AnnotLink *linkA) |
| { |
| xMin = xMinA; |
| yMin = yMinA; |
| xMax = xMaxA; |
| yMax = yMaxA; |
| link = linkA; |
| } |
| ~TextLink() { } |
| |
| int xMin, yMin, xMax, yMax; |
| AnnotLink *link; |
| }; |
| |
| //------------------------------------------------------------------------ |
| // TextFontInfo |
| //------------------------------------------------------------------------ |
| |
| TextFontInfo::TextFontInfo(const GfxState *state) |
| { |
| gfxFont = state->getFont(); |
| #ifdef TEXTOUT_WORD_LIST |
| fontName = (gfxFont && gfxFont->getName()) ? new GooString(*gfxFont->getName()) : nullptr; |
| flags = gfxFont ? gfxFont->getFlags() : 0; |
| #endif |
| } |
| |
| TextFontInfo::~TextFontInfo() |
| { |
| #ifdef TEXTOUT_WORD_LIST |
| delete fontName; |
| #endif |
| } |
| |
| bool TextFontInfo::matches(const GfxState *state) const |
| { |
| return state->getFont() == gfxFont; |
| } |
| |
| bool TextFontInfo::matches(const TextFontInfo *fontInfo) const |
| { |
| return gfxFont == fontInfo->gfxFont; |
| } |
| |
| bool TextFontInfo::matches(const Ref *ref) const |
| { |
| return gfxFont && (*(gfxFont->getID()) == *ref); |
| } |
| |
| double TextFontInfo::getAscent() const |
| { |
| return gfxFont ? gfxFont->getAscent() : 0.95; |
| } |
| |
| double TextFontInfo::getDescent() const |
| { |
| return gfxFont ? gfxFont->getDescent() : -0.35; |
| } |
| |
| int TextFontInfo::getWMode() const |
| { |
| return gfxFont ? gfxFont->getWMode() : 0; |
| } |
| |
| //------------------------------------------------------------------------ |
| // TextWord |
| //------------------------------------------------------------------------ |
| |
| TextWord::TextWord(const GfxState *state, int rotA, double fontSizeA) |
| { |
| rot = rotA; |
| fontSize = fontSizeA; |
| spaceAfter = false; |
| next = nullptr; |
| invisible = state->getRender() == 3; |
| |
| #ifdef TEXTOUT_WORD_LIST |
| GfxRGB rgb; |
| |
| if ((state->getRender() & 3) == 1) { |
| state->getStrokeRGB(&rgb); |
| } else { |
| state->getFillRGB(&rgb); |
| } |
| colorR = colToDbl(rgb.r); |
| colorG = colToDbl(rgb.g); |
| colorB = colToDbl(rgb.b); |
| #endif |
| |
| underlined = false; |
| link = nullptr; |
| } |
| |
| TextWord::~TextWord() { } |
| |
| void TextWord::addChar(const GfxState *state, TextFontInfo *fontA, double x, double y, double dx, double dy, int charPosA, int charLen, CharCode c, Unicode u, const Matrix &textMatA) |
| { |
| chars.push_back(CharInfo { u, c, charPosA, 0.0, fontA, textMatA }); |
| charPosEnd = charPosA + charLen; |
| |
| if (len() == 1) { |
| setInitialBounds(fontA, x, y); |
| } |
| |
| if (wMode) { // vertical writing mode |
| // NB: the rotation value has been incremented by 1 (in |
| // TextPage::beginWord()) for vertical writing mode |
| switch (rot) { |
| case 0: |
| chars.back().edge = x - fontSize; |
| xMax = edgeEnd = x; |
| break; |
| case 1: |
| chars.back().edge = y - fontSize; |
| yMax = edgeEnd = y; |
| break; |
| case 2: |
| chars.back().edge = x + fontSize; |
| xMin = edgeEnd = x; |
| break; |
| case 3: |
| chars.back().edge = y + fontSize; |
| yMin = edgeEnd = y; |
| break; |
| } |
| } else { // horizontal writing mode |
| switch (rot) { |
| case 0: |
| chars.back().edge = x; |
| xMax = edgeEnd = x + dx; |
| break; |
| case 1: |
| chars.back().edge = y; |
| yMax = edgeEnd = y + dy; |
| break; |
| case 2: |
| chars.back().edge = x; |
| xMin = edgeEnd = x + dx; |
| break; |
| case 3: |
| chars.back().edge = y; |
| yMin = edgeEnd = y + dy; |
| break; |
| } |
| } |
| } |
| |
| void TextWord::setInitialBounds(TextFontInfo *fontA, double x, double y) |
| { |
| double ascent = fontA->getAscent() * fontSize; |
| double descent = fontA->getDescent() * fontSize; |
| wMode = fontA->getWMode(); |
| |
| if (wMode) { // vertical writing mode |
| // NB: the rotation value has been incremented by 1 (in |
| // TextPage::beginWord()) for vertical writing mode |
| switch (rot) { |
| case 0: |
| xMin = x - fontSize; |
| yMin = y - fontSize; |
| yMax = y; |
| base = y; |
| break; |
| case 1: |
| xMin = x; |
| yMin = y - fontSize; |
| xMax = x + fontSize; |
| base = x; |
| break; |
| case 2: |
| yMin = y; |
| xMax = x + fontSize; |
| yMax = y + fontSize; |
| base = y; |
| break; |
| case 3: |
| xMin = x - fontSize; |
| xMax = x; |
| yMax = y + fontSize; |
| base = x; |
| break; |
| } |
| } else { // horizontal writing mode |
| switch (rot) { |
| case 0: |
| xMin = x; |
| yMin = y - ascent; |
| yMax = y - descent; |
| if (yMin == yMax) { |
| // this is a sanity check for a case that shouldn't happen -- but |
| // if it does happen, we want to avoid dividing by zero later |
| yMin = y; |
| yMax = y + 1; |
| } |
| base = y; |
| break; |
| case 1: |
| xMin = x + descent; |
| yMin = y; |
| xMax = x + ascent; |
| if (xMin == xMax) { |
| // this is a sanity check for a case that shouldn't happen -- but |
| // if it does happen, we want to avoid dividing by zero later |
| xMin = x; |
| xMax = x + 1; |
| } |
| base = x; |
| break; |
| case 2: |
| yMin = y + descent; |
| xMax = x; |
| yMax = y + ascent; |
| if (yMin == yMax) { |
| // this is a sanity check for a case that shouldn't happen -- but |
| // if it does happen, we want to avoid dividing by zero later |
| yMin = y; |
| yMax = y + 1; |
| } |
| base = y; |
| break; |
| case 3: |
| xMin = x - ascent; |
| xMax = x - descent; |
| yMax = y; |
| if (xMin == xMax) { |
| // this is a sanity check for a case that shouldn't happen -- but |
| // if it does happen, we want to avoid dividing by zero later |
| xMin = x; |
| xMax = x + 1; |
| } |
| base = x; |
| break; |
| } |
| } |
| } |
| |
| struct CombiningTable |
| { |
| Unicode base; |
| Unicode comb; |
| }; |
| |
| static const struct CombiningTable combiningTable[] = { |
| { 0x0060, 0x0300 }, // grave |
| { 0x00a8, 0x0308 }, // dieresis |
| { 0x00af, 0x0304 }, // macron |
| { 0x00b4, 0x0301 }, // acute |
| { 0x00b8, 0x0327 }, // cedilla |
| { 0x02c6, 0x0302 }, // circumflex |
| { 0x02c7, 0x030c }, // caron |
| { 0x02d8, 0x0306 }, // breve |
| { 0x02d9, 0x0307 }, // dotaccent |
| { 0x02da, 0x030a }, // ring |
| { 0x02dc, 0x0303 }, // tilde |
| { 0x02dd, 0x030b } // hungarumlaut (double acute accent) |
| }; |
| |
| // returning combining versions of characters |
| static Unicode getCombiningChar(Unicode u) |
| { |
| for (const CombiningTable &combining : combiningTable) { |
| if (u == combining.base) { |
| return combining.comb; |
| } |
| } |
| return 0; |
| } |
| |
| bool TextWord::addCombining(const GfxState *state, TextFontInfo *fontA, double fontSizeA, double x, double y, double dx, double dy, int charPosA, int charLen, CharCode c, Unicode u, const Matrix &textMatA) |
| { |
| if (chars.empty() || wMode != 0 || fontA->getWMode() != 0) { |
| return false; |
| } |
| |
| Unicode cCurrent = getCombiningChar(u); |
| if (cCurrent != 0 && unicodeTypeAlphaNum(chars.back().text)) { |
| // Current is a combining character, previous is base character |
| double maxScaledMidDelta = fabs(edgeEnd - chars.back().edge) * combMaxMidDelta; |
| double charMid, charBase, maxScaledBaseDelta; |
| |
| // Test if characters overlap |
| if (rot == 0 || rot == 2) { |
| charMid = x + (dx / 2); |
| charBase = y; |
| maxScaledBaseDelta = (yMax - yMin) * combMaxBaseDelta; |
| } else { |
| charMid = y + (dy / 2); |
| charBase = x; |
| maxScaledBaseDelta = (xMax - xMin) * combMaxBaseDelta; |
| } |
| |
| double edgeMid = (chars.back().edge + edgeEnd) / 2; |
| if (fabs(charMid - edgeMid) >= maxScaledMidDelta || fabs(charBase - base) >= maxScaledBaseDelta) { |
| return false; |
| } |
| |
| // Add character, but don't adjust edge / bounding box because |
| // combining character's positioning could be odd. |
| chars.emplace_back(CharInfo { cCurrent, c, charPosA, edgeMid, fontA, textMatA }); |
| charPosEnd = charPosA + charLen; |
| |
| return true; |
| } |
| |
| Unicode cPrev = getCombiningChar(chars.back().text); |
| if (cPrev != 0 && unicodeTypeAlphaNum(u)) { |
| // Previous is a combining character, current is base character |
| double maxScaledBaseDelta = (fontA->getAscent() - fontA->getDescent()) * fontSizeA * combMaxBaseDelta; |
| double charMid, charBase, maxScaledMidDelta; |
| |
| // Test if characters overlap |
| if (rot == 0 || rot == 2) { |
| charMid = x + (dx / 2); |
| charBase = y; |
| maxScaledMidDelta = fabs(dx * combMaxMidDelta); |
| } else { |
| charMid = y + (dy / 2); |
| charBase = x; |
| maxScaledMidDelta = fabs(dy * combMaxMidDelta); |
| } |
| |
| double edgeMid = (chars.back().edge + edgeEnd) / 2; |
| if (fabs(charMid - edgeMid) >= maxScaledMidDelta || fabs(charBase - base) >= maxScaledBaseDelta) { |
| return false; |
| } |
| |
| fontSize = fontSizeA; |
| // move combining character to after base character |
| chars.emplace_back(CharInfo { cPrev, chars.back().charcode, charPosA, edgeMid, chars.back().font, chars.back().textMat }); |
| |
| auto &lastChar = chars[chars.size() - 2]; |
| |
| charPosEnd = charPosA + charLen; |
| lastChar.text = u; |
| lastChar.charcode = c; |
| lastChar.font = fontA; |
| lastChar.textMat = textMatA; |
| |
| if (len() == 2) { |
| setInitialBounds(fontA, x, y); |
| } |
| |
| // Updated edges / bounding box because we changed the base |
| // character. |
| if (wMode) { |
| // FIXME unreachable, wMode == 0 |
| switch (rot) { |
| case 0: |
| lastChar.edge = x - fontSize; |
| xMax = edgeEnd = x; |
| break; |
| case 1: |
| lastChar.edge = y - fontSize; |
| yMax = edgeEnd = y; |
| break; |
| case 2: |
| lastChar.edge = x + fontSize; |
| xMin = edgeEnd = x; |
| break; |
| case 3: |
| lastChar.edge = y + fontSize; |
| yMin = edgeEnd = y; |
| break; |
| } |
| } else { |
| switch (rot) { |
| case 0: |
| lastChar.edge = x; |
| xMax = edgeEnd = x + dx; |
| break; |
| case 1: |
| lastChar.edge = y; |
| yMax = edgeEnd = y + dy; |
| break; |
| case 2: |
| lastChar.edge = x; |
| xMin = edgeEnd = x + dx; |
| break; |
| case 3: |
| lastChar.edge = y; |
| yMin = edgeEnd = y + dy; |
| break; |
| } |
| } |
| |
| chars.back().edge = (edgeEnd + lastChar.edge) / 2; |
| return true; |
| } |
| return false; |
| } |
| |
| void TextWord::merge(TextWord *word) |
| { |
| if (word->xMin < xMin) { |
| xMin = word->xMin; |
| } |
| if (word->yMin < yMin) { |
| yMin = word->yMin; |
| } |
| if (word->xMax > xMax) { |
| xMax = word->xMax; |
| } |
| if (word->yMax > yMax) { |
| yMax = word->yMax; |
| } |
| chars.insert(chars.end(), word->chars.begin(), word->chars.end()); |
| edgeEnd = word->edgeEnd; |
| charPosEnd = word->charPosEnd; |
| } |
| |
| inline int TextWord::primaryCmp(const TextWord *word) const |
| { |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| cmp = xMin - word->xMin; |
| break; |
| case 1: |
| cmp = yMin - word->yMin; |
| break; |
| case 2: |
| cmp = word->xMax - xMax; |
| break; |
| case 3: |
| cmp = word->yMax - yMax; |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| double TextWord::primaryDelta(const TextWord *word) const |
| { |
| double delta; |
| |
| delta = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| delta = word->xMin - xMax; |
| break; |
| case 1: |
| delta = word->yMin - yMax; |
| break; |
| case 2: |
| delta = xMin - word->xMax; |
| break; |
| case 3: |
| delta = yMin - word->yMax; |
| break; |
| } |
| return delta; |
| } |
| |
| int TextWord::cmpYX(const void *p1, const void *p2) |
| { |
| TextWord *word1 = *(TextWord **)p1; |
| TextWord *word2 = *(TextWord **)p2; |
| double cmp; |
| |
| cmp = word1->yMin - word2->yMin; |
| if (cmp == 0) { |
| cmp = word1->xMin - word2->xMin; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| #ifdef TEXTOUT_WORD_LIST |
| |
| GooString *TextWord::getText() const |
| { |
| GooString *s; |
| const UnicodeMap *uMap; |
| char buf[8]; |
| |
| s = new GooString(); |
| if (!(uMap = globalParams->getTextEncoding())) { |
| return s; |
| } |
| for (size_t i = 0; i < len(); ++i) { |
| auto n = uMap->mapUnicode(chars[i].text, buf, sizeof(buf)); |
| s->append(buf, n); |
| } |
| return s; |
| } |
| |
| void TextWord::getCharBBox(int charIdx, double *xMinA, double *yMinA, double *xMaxA, double *yMaxA) const |
| { |
| if (charIdx < 0) { |
| return; |
| } |
| size_t uCharIdx = charIdx; |
| if (uCharIdx >= len()) { |
| return; |
| } |
| auto startingEdge = chars[uCharIdx].edge; |
| auto endingEdge = (uCharIdx + 1 == len()) ? edgeEnd : chars[charIdx + 1].edge; |
| switch (rot) { |
| case 0: |
| *xMinA = startingEdge; |
| *xMaxA = endingEdge; |
| *yMinA = yMin; |
| *yMaxA = yMax; |
| break; |
| case 1: |
| *xMinA = xMin; |
| *xMaxA = xMax; |
| *yMinA = startingEdge; |
| *yMaxA = endingEdge; |
| break; |
| case 2: |
| *xMinA = endingEdge; |
| *xMaxA = startingEdge; |
| *yMinA = yMin; |
| *yMaxA = yMax; |
| break; |
| case 3: |
| *xMinA = xMin; |
| *xMaxA = xMax; |
| *yMinA = endingEdge; |
| *yMaxA = startingEdge; |
| break; |
| } |
| } |
| |
| #endif // TEXTOUT_WORD_LIST |
| |
| //------------------------------------------------------------------------ |
| // TextPool |
| //------------------------------------------------------------------------ |
| |
| TextPool::TextPool() |
| { |
| minBaseIdx = 0; |
| maxBaseIdx = -1; |
| pool = nullptr; |
| cursor = nullptr; |
| cursorBaseIdx = -1; |
| } |
| |
| TextPool::~TextPool() |
| { |
| int baseIdx; |
| TextWord *word, *word2; |
| |
| for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) { |
| for (word = pool[baseIdx - minBaseIdx]; word; word = word2) { |
| word2 = word->next; |
| delete word; |
| } |
| } |
| gfree(static_cast<void *>(pool)); |
| } |
| |
| int TextPool::getBaseIdx(double base) const |
| { |
| const double baseIdxDouble = base / textPoolStep; |
| if (std::isnan(baseIdxDouble) || baseIdxDouble < minBaseIdx) { |
| return minBaseIdx; |
| } |
| if (baseIdxDouble > maxBaseIdx) { |
| return maxBaseIdx; |
| } |
| return (int)baseIdxDouble; |
| } |
| |
| void TextPool::addWord(TextWord *word) |
| { |
| int wordBaseIdx, newMinBaseIdx, newMaxBaseIdx, baseIdx; |
| TextWord *w0, *w1; |
| |
| // expand the array if needed |
| wordBaseIdx = (int)(word->base / textPoolStep); |
| if (unlikely(wordBaseIdx <= INT_MIN + 128 || wordBaseIdx >= INT_MAX - 128)) { |
| error(errSyntaxWarning, -1, "wordBaseIdx out of range"); |
| delete word; |
| return; |
| } |
| if (minBaseIdx > maxBaseIdx) { |
| minBaseIdx = wordBaseIdx - 128; |
| maxBaseIdx = wordBaseIdx + 128; |
| pool = (TextWord **)gmallocn(maxBaseIdx - minBaseIdx + 1, sizeof(TextWord *)); |
| for (baseIdx = minBaseIdx; baseIdx <= maxBaseIdx; ++baseIdx) { |
| pool[baseIdx - minBaseIdx] = nullptr; |
| } |
| } else if (wordBaseIdx < minBaseIdx) { |
| newMinBaseIdx = wordBaseIdx - 128; |
| TextWord **newPool = (TextWord **)gmallocn_checkoverflow(maxBaseIdx - newMinBaseIdx + 1, sizeof(TextWord *)); |
| if (unlikely(!newPool)) { |
| error(errSyntaxWarning, -1, "newPool would overflow"); |
| delete word; |
| return; |
| } |
| for (baseIdx = newMinBaseIdx; baseIdx < minBaseIdx; ++baseIdx) { |
| newPool[baseIdx - newMinBaseIdx] = nullptr; |
| } |
| memcpy(static_cast<void *>(&newPool[minBaseIdx - newMinBaseIdx]), static_cast<void *>(pool), (maxBaseIdx - minBaseIdx + 1) * sizeof(TextWord *)); |
| gfree(static_cast<void *>(pool)); |
| pool = newPool; |
| minBaseIdx = newMinBaseIdx; |
| } else if (wordBaseIdx > maxBaseIdx) { |
| newMaxBaseIdx = wordBaseIdx + 128; |
| TextWord **reallocatedPool = (TextWord **)greallocn(static_cast<void *>(pool), newMaxBaseIdx - minBaseIdx + 1, sizeof(TextWord *), true /*checkoverflow*/, false /*free_pool*/); |
| if (!reallocatedPool) { |
| error(errSyntaxWarning, -1, "new pool size would overflow"); |
| delete word; |
| return; |
| } |
| pool = reallocatedPool; |
| for (baseIdx = maxBaseIdx + 1; baseIdx <= newMaxBaseIdx; ++baseIdx) { |
| pool[baseIdx - minBaseIdx] = nullptr; |
| } |
| maxBaseIdx = newMaxBaseIdx; |
| } |
| |
| // insert the new word |
| if (cursor && wordBaseIdx == cursorBaseIdx && word->primaryCmp(cursor) >= 0) { |
| w0 = cursor; |
| w1 = cursor->next; |
| } else { |
| w0 = nullptr; |
| w1 = pool[wordBaseIdx - minBaseIdx]; |
| } |
| for (; w1 && word->primaryCmp(w1) > 0; w0 = w1, w1 = w1->next) { |
| ; |
| } |
| word->next = w1; |
| if (w0) { |
| w0->next = word; |
| } else { |
| pool[wordBaseIdx - minBaseIdx] = word; |
| } |
| cursor = word; |
| cursorBaseIdx = wordBaseIdx; |
| } |
| |
| //------------------------------------------------------------------------ |
| // TextLine |
| //------------------------------------------------------------------------ |
| |
| TextLine::TextLine(TextBlock *blkA, int rotA, double baseA) |
| { |
| blk = blkA; |
| rot = rotA; |
| base = baseA; |
| words = lastWord = nullptr; |
| text = nullptr; |
| edge = nullptr; |
| col = nullptr; |
| len = 0; |
| convertedLen = 0; |
| hyphenated = false; |
| next = nullptr; |
| xMin = yMin = 0; |
| xMax = yMax = -1; |
| normalized = nullptr; |
| normalized_len = 0; |
| normalized_idx = nullptr; |
| ascii_translation = nullptr; |
| ascii_len = 0; |
| ascii_idx = nullptr; |
| } |
| |
| TextLine::~TextLine() |
| { |
| TextWord *word; |
| |
| while (words) { |
| word = words; |
| words = words->next; |
| delete word; |
| } |
| gfree(text); |
| gfree(edge); |
| gfree(col); |
| if (normalized) { |
| gfree(normalized); |
| gfree(normalized_idx); |
| } |
| if (ascii_translation) { |
| gfree(ascii_translation); |
| gfree(ascii_idx); |
| } |
| } |
| |
| void TextLine::addWord(TextWord *word) |
| { |
| if (lastWord) { |
| lastWord->next = word; |
| } else { |
| words = word; |
| } |
| lastWord = word; |
| |
| if (xMin > xMax) { |
| xMin = word->xMin; |
| xMax = word->xMax; |
| yMin = word->yMin; |
| yMax = word->yMax; |
| } else { |
| if (word->xMin < xMin) { |
| xMin = word->xMin; |
| } |
| if (word->xMax > xMax) { |
| xMax = word->xMax; |
| } |
| if (word->yMin < yMin) { |
| yMin = word->yMin; |
| } |
| if (word->yMax > yMax) { |
| yMax = word->yMax; |
| } |
| } |
| } |
| |
| double TextLine::primaryDelta(const TextLine *line) const |
| { |
| double delta; |
| |
| delta = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| delta = line->xMin - xMax; |
| break; |
| case 1: |
| delta = line->yMin - yMax; |
| break; |
| case 2: |
| delta = xMin - line->xMax; |
| break; |
| case 3: |
| delta = yMin - line->yMax; |
| break; |
| } |
| return delta; |
| } |
| |
| int TextLine::primaryCmp(const TextLine *line) const |
| { |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| cmp = xMin - line->xMin; |
| break; |
| case 1: |
| cmp = yMin - line->yMin; |
| break; |
| case 2: |
| cmp = line->xMax - xMax; |
| break; |
| case 3: |
| cmp = line->yMax - yMax; |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextLine::secondaryCmp(const TextLine *line) const |
| { |
| double cmp; |
| |
| cmp = (rot == 0 || rot == 3) ? base - line->base : line->base - base; |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextLine::cmpYX(const TextLine *line) const |
| { |
| int cmp; |
| |
| if ((cmp = secondaryCmp(line))) { |
| return cmp; |
| } |
| return primaryCmp(line); |
| } |
| |
| int TextLine::cmpXY(const void *p1, const void *p2) |
| { |
| TextLine *line1 = *(TextLine **)p1; |
| TextLine *line2 = *(TextLine **)p2; |
| int cmp; |
| |
| if ((cmp = line1->primaryCmp(line2))) { |
| return cmp; |
| } |
| return line1->secondaryCmp(line2); |
| } |
| |
| void TextLine::coalesce(const UnicodeMap *uMap) |
| { |
| double space, delta, minSpace; |
| bool isUnicode; |
| char buf[8]; |
| |
| if (words->next) { |
| |
| // compute the inter-word space threshold |
| if (words->len() > 1 || words->next->len() > 1) { |
| minSpace = 0; |
| } else { |
| minSpace = words->primaryDelta(words->next); |
| for (auto word0 = words->next, word1 = word0->next; word1 && minSpace > 0; word0 = word1, word1 = word0->next) { |
| if (word1->len() > 1) { |
| minSpace = 0; |
| } |
| delta = word0->primaryDelta(word1); |
| if (delta < minSpace) { |
| minSpace = delta; |
| } |
| } |
| } |
| if (minSpace <= 0) { |
| space = maxCharSpacing * words->fontSize; |
| } else { |
| space = maxWideCharSpacingMul * minSpace; |
| if (space > maxWideCharSpacing * words->fontSize) { |
| space = maxWideCharSpacing * words->fontSize; |
| } |
| } |
| |
| // merge words |
| auto word0 = words; |
| auto word1 = words->next; |
| while (word1) { |
| if (word0->primaryDelta(word1) >= space) { |
| word0->spaceAfter = true; |
| word0 = word1; |
| word1 = word1->next; |
| } else if (word0->chars.back().font == word1->chars.front().font // |
| && word0->underlined == word1->underlined // |
| && fabs(word0->fontSize - word1->fontSize) < maxWordFontSizeDelta * words->fontSize // |
| && word1->chars.front().charPos == word0->charPosEnd) { |
| word0->merge(word1); |
| word0->next = word1->next; |
| delete word1; |
| word1 = word0->next; |
| } else { |
| word0 = word1; |
| word1 = word1->next; |
| } |
| } |
| } |
| |
| // build the line text |
| isUnicode = uMap ? uMap->isUnicode() : false; |
| len = 0; |
| for (auto word1 = words; word1; word1 = word1->next) { |
| len += word1->len(); |
| if (word1->spaceAfter) { |
| ++len; |
| } |
| } |
| text = (Unicode *)gmallocn(len, sizeof(Unicode)); |
| edge = (double *)gmallocn(len + 1, sizeof(double)); |
| size_t i = 0; |
| for (auto word1 = words; word1; word1 = word1->next) { |
| for (size_t j = 0; j < word1->len(); ++j) { |
| text[i] = word1->chars[j].text; |
| edge[i] = word1->chars[j].edge; |
| ++i; |
| } |
| edge[i] = word1->edgeEnd; |
| if (word1->spaceAfter) { |
| text[i] = (Unicode)0x0020; |
| ++i; |
| } |
| } |
| |
| // compute convertedLen and set up the col array |
| col = (int *)gmallocn(len + 1, sizeof(int)); |
| convertedLen = 0; |
| for (int ci = 0; ci < len; ++ci) { |
| col[ci] = convertedLen; |
| if (isUnicode) { |
| ++convertedLen; |
| } else if (uMap) { |
| convertedLen += uMap->mapUnicode(text[ci], buf, sizeof(buf)); |
| } |
| } |
| col[len] = convertedLen; |
| |
| // check for hyphen at end of line |
| //~ need to check for other chars used as hyphens |
| hyphenated = text[len - 1] == (Unicode)'-'; |
| } |
| |
| //------------------------------------------------------------------------ |
| // TextLineFrag |
| //------------------------------------------------------------------------ |
| |
| class TextLineFrag |
| { |
| public: |
| TextLine *line; // the line object |
| int start, len; // offset and length of this fragment |
| // (in Unicode chars) |
| double xMin, xMax; // bounding box coordinates |
| double yMin, yMax; |
| double base; // baseline virtual coordinate |
| int col; // first column |
| |
| void init(TextLine *lineA, int startA, int lenA); |
| void computeCoords(bool oneRot); |
| |
| static int cmpYXPrimaryRot(const void *p1, const void *p2); |
| static int cmpYXLineRot(const void *p1, const void *p2); |
| static int cmpXYLineRot(const void *p1, const void *p2); |
| static int cmpXYColumnPrimaryRot(const void *p1, const void *p2); |
| static int cmpXYColumnLineRot(const void *p1, const void *p2); |
| }; |
| |
| void TextLineFrag::init(TextLine *lineA, int startA, int lenA) |
| { |
| line = lineA; |
| start = startA; |
| len = lenA; |
| col = line->col[start]; |
| } |
| |
| void TextLineFrag::computeCoords(bool oneRot) |
| { |
| TextBlock *blk; |
| double d0, d1, d2, d3, d4; |
| |
| if (oneRot) { |
| |
| switch (line->rot) { |
| case 0: |
| xMin = line->edge[start]; |
| xMax = line->edge[start + len]; |
| yMin = line->yMin; |
| yMax = line->yMax; |
| break; |
| case 1: |
| xMin = line->xMin; |
| xMax = line->xMax; |
| yMin = line->edge[start]; |
| yMax = line->edge[start + len]; |
| break; |
| case 2: |
| xMin = line->edge[start + len]; |
| xMax = line->edge[start]; |
| yMin = line->yMin; |
| yMax = line->yMax; |
| break; |
| case 3: |
| xMin = line->xMin; |
| xMax = line->xMax; |
| yMin = line->edge[start + len]; |
| yMax = line->edge[start]; |
| break; |
| } |
| base = line->base; |
| |
| } else { |
| |
| if (line->rot == 0 && line->blk->page->primaryRot == 0) { |
| |
| xMin = line->edge[start]; |
| xMax = line->edge[start + len]; |
| yMin = line->yMin; |
| yMax = line->yMax; |
| base = line->base; |
| |
| } else { |
| |
| blk = line->blk; |
| d0 = line->edge[start]; |
| d1 = line->edge[start + len]; |
| d2 = d3 = d4 = 0; // make gcc happy |
| |
| switch (line->rot) { |
| case 0: |
| d2 = line->yMin; |
| d3 = line->yMax; |
| d4 = line->base; |
| d0 = (d0 - blk->xMin) / (blk->xMax - blk->xMin); |
| d1 = (d1 - blk->xMin) / (blk->xMax - blk->xMin); |
| d2 = (d2 - blk->yMin) / (blk->yMax - blk->yMin); |
| d3 = (d3 - blk->yMin) / (blk->yMax - blk->yMin); |
| d4 = (d4 - blk->yMin) / (blk->yMax - blk->yMin); |
| break; |
| case 1: |
| d2 = line->xMax; |
| d3 = line->xMin; |
| d4 = line->base; |
| d0 = (d0 - blk->yMin) / (blk->yMax - blk->yMin); |
| d1 = (d1 - blk->yMin) / (blk->yMax - blk->yMin); |
| d2 = (blk->xMax - d2) / (blk->xMax - blk->xMin); |
| d3 = (blk->xMax - d3) / (blk->xMax - blk->xMin); |
| d4 = (blk->xMax - d4) / (blk->xMax - blk->xMin); |
| break; |
| case 2: |
| d2 = line->yMax; |
| d3 = line->yMin; |
| d4 = line->base; |
| d0 = (blk->xMax - d0) / (blk->xMax - blk->xMin); |
| d1 = (blk->xMax - d1) / (blk->xMax - blk->xMin); |
| d2 = (blk->yMax - d2) / (blk->yMax - blk->yMin); |
| d3 = (blk->yMax - d3) / (blk->yMax - blk->yMin); |
| d4 = (blk->yMax - d4) / (blk->yMax - blk->yMin); |
| break; |
| case 3: |
| d2 = line->xMin; |
| d3 = line->xMax; |
| d4 = line->base; |
| d0 = (blk->yMax - d0) / (blk->yMax - blk->yMin); |
| d1 = (blk->yMax - d1) / (blk->yMax - blk->yMin); |
| d2 = (d2 - blk->xMin) / (blk->xMax - blk->xMin); |
| d3 = (d3 - blk->xMin) / (blk->xMax - blk->xMin); |
| d4 = (d4 - blk->xMin) / (blk->xMax - blk->xMin); |
| break; |
| } |
| |
| switch (line->blk->page->primaryRot) { |
| case 0: |
| xMin = blk->xMin + d0 * (blk->xMax - blk->xMin); |
| xMax = blk->xMin + d1 * (blk->xMax - blk->xMin); |
| yMin = blk->yMin + d2 * (blk->yMax - blk->yMin); |
| yMax = blk->yMin + d3 * (blk->yMax - blk->yMin); |
| base = blk->yMin + d4 * (blk->yMax - blk->yMin); |
| break; |
| case 1: |
| xMin = blk->xMax - d3 * (blk->xMax - blk->xMin); |
| xMax = blk->xMax - d2 * (blk->xMax - blk->xMin); |
| yMin = blk->yMin + d0 * (blk->yMax - blk->yMin); |
| yMax = blk->yMin + d1 * (blk->yMax - blk->yMin); |
| base = blk->xMax - d4 * (blk->xMax - blk->xMin); |
| break; |
| case 2: |
| xMin = blk->xMax - d1 * (blk->xMax - blk->xMin); |
| xMax = blk->xMax - d0 * (blk->xMax - blk->xMin); |
| yMin = blk->yMax - d3 * (blk->yMax - blk->yMin); |
| yMax = blk->yMax - d2 * (blk->yMax - blk->yMin); |
| base = blk->yMax - d4 * (blk->yMax - blk->yMin); |
| break; |
| case 3: |
| xMin = blk->xMin + d2 * (blk->xMax - blk->xMin); |
| xMax = blk->xMin + d3 * (blk->xMax - blk->xMin); |
| yMin = blk->yMax - d1 * (blk->yMax - blk->yMin); |
| yMax = blk->yMax - d0 * (blk->yMax - blk->yMin); |
| base = blk->xMin + d4 * (blk->xMax - blk->xMin); |
| break; |
| } |
| } |
| } |
| } |
| |
| int TextLineFrag::cmpYXPrimaryRot(const void *p1, const void *p2) |
| { |
| TextLineFrag *frag1 = (TextLineFrag *)p1; |
| TextLineFrag *frag2 = (TextLineFrag *)p2; |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (frag1->line->blk->page->primaryRot) { |
| case 0: |
| if (fabs(cmp = frag1->yMin - frag2->yMin) < 0.01) { |
| cmp = frag1->xMin - frag2->xMin; |
| } |
| break; |
| case 1: |
| if (fabs(cmp = frag2->xMax - frag1->xMax) < 0.01) { |
| cmp = frag1->yMin - frag2->yMin; |
| } |
| break; |
| case 2: |
| if (fabs(cmp = frag2->yMin - frag1->yMin) < 0.01) { |
| cmp = frag2->xMax - frag1->xMax; |
| } |
| break; |
| case 3: |
| if (fabs(cmp = frag1->xMax - frag2->xMax) < 0.01) { |
| cmp = frag2->yMax - frag1->yMax; |
| } |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextLineFrag::cmpYXLineRot(const void *p1, const void *p2) |
| { |
| TextLineFrag *frag1 = (TextLineFrag *)p1; |
| TextLineFrag *frag2 = (TextLineFrag *)p2; |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (frag1->line->rot) { |
| case 0: |
| if ((cmp = frag1->yMin - frag2->yMin) == 0) { |
| cmp = frag1->xMin - frag2->xMin; |
| } |
| break; |
| case 1: |
| if ((cmp = frag2->xMax - frag1->xMax) == 0) { |
| cmp = frag1->yMin - frag2->yMin; |
| } |
| break; |
| case 2: |
| if ((cmp = frag2->yMin - frag1->yMin) == 0) { |
| cmp = frag2->xMax - frag1->xMax; |
| } |
| break; |
| case 3: |
| if ((cmp = frag1->xMax - frag2->xMax) == 0) { |
| cmp = frag2->yMax - frag1->yMax; |
| } |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextLineFrag::cmpXYLineRot(const void *p1, const void *p2) |
| { |
| TextLineFrag *frag1 = (TextLineFrag *)p1; |
| TextLineFrag *frag2 = (TextLineFrag *)p2; |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (frag1->line->rot) { |
| case 0: |
| if ((cmp = frag1->xMin - frag2->xMin) == 0) { |
| cmp = frag1->yMin - frag2->yMin; |
| } |
| break; |
| case 1: |
| if ((cmp = frag1->yMin - frag2->yMin) == 0) { |
| cmp = frag2->xMax - frag1->xMax; |
| } |
| break; |
| case 2: |
| if ((cmp = frag2->xMax - frag1->xMax) == 0) { |
| cmp = frag2->yMin - frag1->yMin; |
| } |
| break; |
| case 3: |
| if ((cmp = frag2->yMax - frag1->yMax) == 0) { |
| cmp = frag1->xMax - frag2->xMax; |
| } |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextLineFrag::cmpXYColumnPrimaryRot(const void *p1, const void *p2) |
| { |
| TextLineFrag *frag1 = (TextLineFrag *)p1; |
| TextLineFrag *frag2 = (TextLineFrag *)p2; |
| double cmp; |
| |
| // if columns overlap, compare y values |
| if (frag1->col < frag2->col + (frag2->line->col[frag2->start + frag2->len] - frag2->line->col[frag2->start]) && frag2->col < frag1->col + (frag1->line->col[frag1->start + frag1->len] - frag1->line->col[frag1->start])) { |
| cmp = 0; // make gcc happy |
| switch (frag1->line->blk->page->primaryRot) { |
| case 0: |
| cmp = frag1->yMin - frag2->yMin; |
| break; |
| case 1: |
| cmp = frag2->xMax - frag1->xMax; |
| break; |
| case 2: |
| cmp = frag2->yMin - frag1->yMin; |
| break; |
| case 3: |
| cmp = frag1->xMax - frag2->xMax; |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| // otherwise, compare starting column |
| return frag1->col - frag2->col; |
| } |
| |
| int TextLineFrag::cmpXYColumnLineRot(const void *p1, const void *p2) |
| { |
| TextLineFrag *frag1 = (TextLineFrag *)p1; |
| TextLineFrag *frag2 = (TextLineFrag *)p2; |
| double cmp; |
| |
| // if columns overlap, compare y values |
| if (frag1->col < frag2->col + (frag2->line->col[frag2->start + frag2->len] - frag2->line->col[frag2->start]) && frag2->col < frag1->col + (frag1->line->col[frag1->start + frag1->len] - frag1->line->col[frag1->start])) { |
| cmp = 0; // make gcc happy |
| switch (frag1->line->rot) { |
| case 0: |
| cmp = frag1->yMin - frag2->yMin; |
| break; |
| case 1: |
| cmp = frag2->xMax - frag1->xMax; |
| break; |
| case 2: |
| cmp = frag2->yMin - frag1->yMin; |
| break; |
| case 3: |
| cmp = frag1->xMax - frag2->xMax; |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| // otherwise, compare starting column |
| return frag1->col - frag2->col; |
| } |
| |
| //------------------------------------------------------------------------ |
| // TextBlock |
| //------------------------------------------------------------------------ |
| |
| TextBlock::TextBlock(TextPage *pageA, int rotA) |
| { |
| page = pageA; |
| rot = rotA; |
| xMin = yMin = 0; |
| xMax = yMax = -1; |
| priMin = 0; |
| priMax = page->pageWidth; |
| pool = new TextPool(); |
| lines = nullptr; |
| curLine = nullptr; |
| next = nullptr; |
| stackNext = nullptr; |
| tableId = -1; |
| tableEnd = false; |
| } |
| |
| TextBlock::~TextBlock() |
| { |
| TextLine *line; |
| |
| delete pool; |
| while (lines) { |
| line = lines; |
| lines = lines->next; |
| delete line; |
| } |
| } |
| |
| void TextBlock::addWord(TextWord *word) |
| { |
| pool->addWord(word); |
| if (xMin > xMax) { |
| xMin = word->xMin; |
| xMax = word->xMax; |
| yMin = word->yMin; |
| yMax = word->yMax; |
| } else { |
| if (word->xMin < xMin) { |
| xMin = word->xMin; |
| } |
| if (word->xMax > xMax) { |
| xMax = word->xMax; |
| } |
| if (word->yMin < yMin) { |
| yMin = word->yMin; |
| } |
| if (word->yMax > yMax) { |
| yMax = word->yMax; |
| } |
| } |
| } |
| |
| void TextBlock::coalesce(const UnicodeMap *uMap, double fixedPitch) |
| { |
| // discard duplicated text (fake boldface, drop shadows) |
| for (int idx0 = pool->minBaseIdx; idx0 <= pool->maxBaseIdx; ++idx0) { |
| // Get the first LHS word from the pool |
| TextWord *word0 = pool->getPool(idx0); |
| |
| while (word0) { |
| double priDelta = dupMaxPriDelta * word0->fontSize; |
| double secDelta = dupMaxSecDelta * word0->fontSize; |
| double xDelta = ((rot == 0) || (rot == 2)) ? priDelta : secDelta; |
| double yDelta = ((rot == 0) || (rot == 2)) ? secDelta : priDelta; |
| |
| int maxBaseIdx = pool->getBaseIdx(word0->base + secDelta); |
| |
| for (int idx1 = idx0; idx1 <= maxBaseIdx; idx1++) { |
| TextWord *prevWord; |
| /* In case the RHS word is from the same pool as the LHS word, |
| * start the inner loop with the word following the LHS word. |
| * Otherwise, start with the second word from the subsequent pools |
| * - the first word is compared at the end. |
| */ |
| if (idx0 == idx1) { |
| prevWord = word0; |
| } else { |
| prevWord = pool->getPool(idx1); |
| if (!prevWord) { |
| continue; |
| } |
| } |
| TextWord *word1 = prevWord->next; |
| |
| auto equalText = [](const TextWord &w1, const TextWord &w2) -> bool { // |
| return std::equal(w1.chars.begin(), w1.chars.end(), w2.chars.begin(), w2.chars.end(), // |
| [](auto c1, auto c2) { return c1.text == c2.text; }); |
| }; |
| auto match = [&equalText, xDelta, yDelta](const TextWord &w1, const TextWord &w2) -> bool { |
| if (!equalText(w1, w2)) { |
| return false; |
| } |
| return fabs(w1.xMin - w2.xMin) < xDelta && fabs(w1.xMax - w2.xMax) < xDelta // |
| && fabs(w1.yMin - w2.yMin) < yDelta && fabs(w1.yMax - w2.yMax) < yDelta; |
| }; |
| |
| while (word1) { |
| if (match(*word0, *word1)) { |
| prevWord->next = word1->next; |
| delete word1; |
| word1 = prevWord->next; |
| } else { |
| prevWord = word1; |
| word1 = word1->next; |
| } |
| } |
| |
| // Check the first word from each subsequent pool |
| if (idx0 != idx1) { |
| word1 = pool->getPool(idx1); |
| } |
| if (word1 && match(*word0, *word1)) { |
| pool->setPool(idx1, word1->next); |
| delete word1; |
| } |
| } |
| |
| word0 = word0->next; |
| } |
| } |
| |
| TextWord *word0, *word1; |
| TextWord *bestWord0, *bestWord1, *lastWord; |
| TextLine *line, *line0, *line1; |
| TextLine **lineArray; |
| int poolMinBaseIdx, startBaseIdx, minBaseIdx, maxBaseIdx; |
| int baseIdx, bestWordBaseIdx; |
| double minBase, maxBase; |
| double fontSize, wordSpacing, delta; |
| bool overlap; |
| int col1, col2; |
| int i, j, k; |
| |
| // build the lines |
| curLine = nullptr; |
| poolMinBaseIdx = pool->minBaseIdx; |
| charCount = 0; |
| nLines = 0; |
| while (true) { |
| |
| // find the first non-empty line in the pool |
| for (; poolMinBaseIdx <= pool->maxBaseIdx && !pool->getPool(poolMinBaseIdx); ++poolMinBaseIdx) { |
| ; |
| } |
| if (poolMinBaseIdx > pool->maxBaseIdx) { |
| break; |
| } |
| |
| // look for the left-most word in the first four lines of the |
| // pool -- this avoids starting with a superscript word |
| startBaseIdx = poolMinBaseIdx; |
| for (baseIdx = poolMinBaseIdx + 1; baseIdx < poolMinBaseIdx + 4 && baseIdx <= pool->maxBaseIdx; ++baseIdx) { |
| if (!pool->getPool(baseIdx)) { |
| continue; |
| } |
| if (pool->getPool(baseIdx)->primaryCmp(pool->getPool(startBaseIdx)) < 0) { |
| startBaseIdx = baseIdx; |
| } |
| } |
| |
| // create a new line |
| word0 = pool->getPool(startBaseIdx); |
| pool->setPool(startBaseIdx, word0->next); |
| word0->next = nullptr; |
| line = new TextLine(this, word0->rot, word0->base); |
| line->addWord(word0); |
| lastWord = word0; |
| |
| // compute the search range |
| fontSize = word0->fontSize; |
| minBase = word0->base - maxIntraLineDelta * fontSize; |
| maxBase = word0->base + maxIntraLineDelta * fontSize; |
| minBaseIdx = pool->getBaseIdx(minBase); |
| maxBaseIdx = pool->getBaseIdx(maxBase); |
| wordSpacing = fixedPitch ? fixedPitch : maxWordSpacing * fontSize; |
| |
| // find the rest of the words in this line |
| while (true) { |
| |
| // find the left-most word whose baseline is in the range for |
| // this line |
| bestWordBaseIdx = 0; |
| bestWord0 = bestWord1 = nullptr; |
| overlap = false; |
| for (baseIdx = minBaseIdx; !overlap && baseIdx <= maxBaseIdx; ++baseIdx) { |
| for (word0 = nullptr, word1 = pool->getPool(baseIdx); word1; word0 = word1, word1 = word1->next) { |
| if (word1->base >= minBase && word1->base <= maxBase) { |
| delta = lastWord->primaryDelta(word1); |
| if (delta < minCharSpacing * fontSize) { |
| overlap = true; |
| break; |
| } else { |
| if (delta < wordSpacing && (!bestWord1 || word1->primaryCmp(bestWord1) < 0)) { |
| bestWordBaseIdx = baseIdx; |
| bestWord0 = word0; |
| bestWord1 = word1; |
| } |
| break; |
| } |
| } |
| } |
| } |
| if (overlap || !bestWord1) { |
| break; |
| } |
| |
| // remove it from the pool, and add it to the line |
| if (bestWord0) { |
| bestWord0->next = bestWord1->next; |
| } else { |
| pool->setPool(bestWordBaseIdx, bestWord1->next); |
| } |
| bestWord1->next = nullptr; |
| line->addWord(bestWord1); |
| lastWord = bestWord1; |
| } |
| |
| // add the line |
| if (curLine && line->cmpYX(curLine) > 0) { |
| line0 = curLine; |
| line1 = curLine->next; |
| } else { |
| line0 = nullptr; |
| line1 = lines; |
| } |
| for (; line1 && line->cmpYX(line1) > 0; line0 = line1, line1 = line1->next) { |
| ; |
| } |
| if (line0) { |
| line0->next = line; |
| } else { |
| lines = line; |
| } |
| line->next = line1; |
| curLine = line; |
| line->coalesce(uMap); |
| charCount += line->len; |
| ++nLines; |
| } |
| |
| // sort lines into xy order for column assignment |
| lineArray = (TextLine **)gmallocn(nLines, sizeof(TextLine *)); |
| for (line = lines, i = 0; line; line = line->next, ++i) { |
| lineArray[i] = line; |
| } |
| qsort(static_cast<void *>(lineArray), nLines, sizeof(TextLine *), &TextLine::cmpXY); |
| |
| // column assignment |
| nColumns = 0; |
| if (fixedPitch) { |
| for (i = 0; i < nLines; ++i) { |
| line0 = lineArray[i]; |
| col1 = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| col1 = (int)((line0->xMin - xMin) / fixedPitch + 0.5); |
| break; |
| case 1: |
| col1 = (int)((line0->yMin - yMin) / fixedPitch + 0.5); |
| break; |
| case 2: |
| col1 = (int)((xMax - line0->xMax) / fixedPitch + 0.5); |
| break; |
| case 3: |
| col1 = (int)((yMax - line0->yMax) / fixedPitch + 0.5); |
| break; |
| } |
| for (k = 0; k <= line0->len; ++k) { |
| line0->col[k] += col1; |
| } |
| if (line0->col[line0->len] > nColumns) { |
| nColumns = line0->col[line0->len]; |
| } |
| } |
| } else { |
| for (i = 0; i < nLines; ++i) { |
| line0 = lineArray[i]; |
| col1 = 0; |
| for (j = 0; j < i; ++j) { |
| line1 = lineArray[j]; |
| if (line1->primaryDelta(line0) >= 0) { |
| col2 = line1->col[line1->len] + 1; |
| } else { |
| k = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| for (k = 0; k < line1->len && line0->xMin >= 0.5 * (line1->edge[k] + line1->edge[k + 1]); ++k) { |
| ; |
| } |
| break; |
| case 1: |
| for (k = 0; k < line1->len && line0->yMin >= 0.5 * (line1->edge[k] + line1->edge[k + 1]); ++k) { |
| ; |
| } |
| break; |
| case 2: |
| for (k = 0; k < line1->len && line0->xMax <= 0.5 * (line1->edge[k] + line1->edge[k + 1]); ++k) { |
| ; |
| } |
| break; |
| case 3: |
| for (k = 0; k < line1->len && line0->yMax <= 0.5 * (line1->edge[k] + line1->edge[k + 1]); ++k) { |
| ; |
| } |
| break; |
| } |
| col2 = line1->col[k]; |
| } |
| if (col2 > col1) { |
| col1 = col2; |
| } |
| } |
| for (k = 0; k <= line0->len; ++k) { |
| line0->col[k] += col1; |
| } |
| if (line0->col[line0->len] > nColumns) { |
| nColumns = line0->col[line0->len]; |
| } |
| } |
| } |
| gfree(static_cast<void *>(lineArray)); |
| } |
| |
| void TextBlock::updatePriMinMax(const TextBlock *blk) |
| { |
| double newPriMin, newPriMax; |
| bool gotPriMin, gotPriMax; |
| |
| gotPriMin = gotPriMax = false; |
| newPriMin = newPriMax = 0; // make gcc happy |
| switch (page->primaryRot) { |
| case 0: |
| case 2: |
| if (blk->yMin < yMax && blk->yMax > yMin) { |
| if (blk->xMin < xMin) { |
| newPriMin = blk->xMax; |
| gotPriMin = true; |
| } |
| if (blk->xMax > xMax) { |
| newPriMax = blk->xMin; |
| gotPriMax = true; |
| } |
| } |
| break; |
| case 1: |
| case 3: |
| if (blk->xMin < xMax && blk->xMax > xMin) { |
| if (blk->yMin < yMin) { |
| newPriMin = blk->yMax; |
| gotPriMin = true; |
| } |
| if (blk->yMax > yMax) { |
| newPriMax = blk->yMin; |
| gotPriMax = true; |
| } |
| } |
| break; |
| } |
| if (gotPriMin) { |
| if (newPriMin > xMin) { |
| newPriMin = xMin; |
| } |
| if (newPriMin > priMin) { |
| priMin = newPriMin; |
| } |
| } |
| if (gotPriMax) { |
| if (newPriMax < xMax) { |
| newPriMax = xMax; |
| } |
| if (newPriMax < priMax) { |
| priMax = newPriMax; |
| } |
| } |
| } |
| |
| int TextBlock::cmpXYPrimaryRot(const void *p1, const void *p2) |
| { |
| TextBlock *blk1 = *(TextBlock **)p1; |
| TextBlock *blk2 = *(TextBlock **)p2; |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (blk1->page->primaryRot) { |
| case 0: |
| if ((cmp = blk1->xMin - blk2->xMin) == 0) { |
| cmp = blk1->yMin - blk2->yMin; |
| } |
| break; |
| case 1: |
| if ((cmp = blk1->yMin - blk2->yMin) == 0) { |
| cmp = blk2->xMax - blk1->xMax; |
| } |
| break; |
| case 2: |
| if ((cmp = blk2->xMax - blk1->xMax) == 0) { |
| cmp = blk2->yMin - blk1->yMin; |
| } |
| break; |
| case 3: |
| if ((cmp = blk2->yMax - blk1->yMax) == 0) { |
| cmp = blk1->xMax - blk2->xMax; |
| } |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextBlock::cmpYXPrimaryRot(const void *p1, const void *p2) |
| { |
| TextBlock *blk1 = *(TextBlock **)p1; |
| TextBlock *blk2 = *(TextBlock **)p2; |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (blk1->page->primaryRot) { |
| case 0: |
| if ((cmp = blk1->yMin - blk2->yMin) == 0) { |
| cmp = blk1->xMin - blk2->xMin; |
| } |
| break; |
| case 1: |
| if ((cmp = blk2->xMax - blk1->xMax) == 0) { |
| cmp = blk1->yMin - blk2->yMin; |
| } |
| break; |
| case 2: |
| if ((cmp = blk2->yMin - blk1->yMin) == 0) { |
| cmp = blk2->xMax - blk1->xMax; |
| } |
| break; |
| case 3: |
| if ((cmp = blk1->xMax - blk2->xMax) == 0) { |
| cmp = blk2->yMax - blk1->yMax; |
| } |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| int TextBlock::primaryCmp(const TextBlock *blk) const |
| { |
| double cmp; |
| |
| cmp = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| cmp = xMin - blk->xMin; |
| break; |
| case 1: |
| cmp = yMin - blk->yMin; |
| break; |
| case 2: |
| cmp = blk->xMax - xMax; |
| break; |
| case 3: |
| cmp = blk->yMax - yMax; |
| break; |
| } |
| return cmp < 0 ? -1 : cmp > 0 ? 1 : 0; |
| } |
| |
| double TextBlock::secondaryDelta(const TextBlock *blk) const |
| { |
| double delta; |
| |
| delta = 0; // make gcc happy |
| switch (rot) { |
| case 0: |
| delta = blk->yMin - yMax; |
| break; |
| case 1: |
| delta = xMin - blk->xMax; |
| break; |
| case 2: |
| delta = yMin - blk->yMax; |
| break; |
| case 3: |
| delta = blk->xMin - xMax; |
| break; |
| } |
| return delta; |
| } |
| |
| bool TextBlock::isBelow(const TextBlock *blk) const |
| { |
| bool below; |
| |
| below = false; // make gcc happy |
| switch (page->primaryRot) { |
| case 0: |
| below = xMin >= blk->priMin && xMax <= blk->priMax && yMin > blk->yMin; |
| break; |
| case 1: |
| below = yMin >= blk->priMin && yMax <= blk->priMax && xMax < blk->xMax; |
| break; |
| case 2: |
| below = xMin >= blk->priMin && xMax <= blk->priMax && yMax < blk->yMax; |
| break; |
| case 3: |
| below = yMin >= blk->priMin && yMax <= blk->priMax && xMin > blk->xMin; |
| break; |
| } |
| |
| return below; |
| } |
| |
| bool TextBlock::isBeforeByRule1(const TextBlock *blk1) |
| { |
| bool before = false; |
| bool overlap = false; |
| |
| switch (this->page->primaryRot) { |
| case 0: |
| case 2: |
| overlap = ((this->ExMin <= blk1->ExMin) && (blk1->ExMin <= this->ExMax)) || ((blk1->ExMin <= this->ExMin) && (this->ExMin <= blk1->ExMax)); |
| break; |
| case 1: |
| case 3: |
| overlap = ((this->EyMin <= blk1->EyMin) && (blk1->EyMin <= this->EyMax)) || ((blk1->EyMin <= this->EyMin) && (this->EyMin <= blk1->EyMax)); |
| break; |
| } |
| switch (this->page->primaryRot) { |
| case 0: |
| before = overlap && this->EyMin < blk1->EyMin; |
| break; |
| case 1: |
| before = overlap && this->ExMax > blk1->ExMax; |
| break; |
| case 2: |
| before = overlap && this->EyMax > blk1->EyMax; |
| break; |
| case 3: |
| before = overlap && this->ExMin < blk1->ExMin; |
| break; |
| } |
| return before; |
| } |
| |
| bool TextBlock::isBeforeByRule2(const TextBlock *blk1) |
| { |
| double cmp = 0; |
| int rotLR = rot; |
| |
| if (!page->primaryLR) { |
| rotLR = (rotLR + 2) % 4; |
| } |
| |
| switch (rotLR) { |
| case 0: |
| cmp = ExMax - blk1->ExMin; |
| break; |
| case 1: |
| cmp = EyMin - blk1->EyMax; |
| break; |
| case 2: |
| cmp = blk1->ExMax - ExMin; |
| break; |
| case 3: |
| cmp = blk1->EyMin - EyMax; |
| break; |
| } |
| return cmp <= 0; |
| } |
| |
| // Sort into reading order by performing a topological sort using the rules |
| // given in "High Performance Document Layout Analysis", T.M. Breuel, 2003. |
| // See http://pubs.iupr.org/#2003-breuel-sdiut |
| // Topological sort is done by depth first search, see |
| // http://en.wikipedia.org/wiki/Topological_sorting |
| int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1, TextBlock **sorted, int sortPos, bool *visited, TextBlock **cache, int cacheSize) |
| { |
| int pos2; |
| TextBlock *blk1, *blk2, *blk3; |
| bool before; |
| |
| if (visited[pos1]) { |
| return sortPos; |
| } |
| |
| blk1 = this; |
| |
| #if 0 // for debugging |
| printf("visited: %d %.2f..%.2f %.2f..%.2f\n", |
| sortPos, blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax); |
| #endif |
| visited[pos1] = true; |
| pos2 = -1; |
| for (blk2 = blkList; blk2; blk2 = blk2->next) { |
| pos2++; |
| if (visited[pos2]) { |
| // skip visited nodes |
| continue; |
| } |
| before = false; |
| |
| // is blk2 before blk1? (for table entries) |
| if (blk1->tableId >= 0 && blk1->tableId == blk2->tableId) { |
| if (page->primaryLR) { |
| if (blk2->xMax <= blk1->xMin && blk2->yMin <= blk1->yMax && blk2->yMax >= blk1->yMin) { |
| before = true; |
| } |
| } else { |
| if (blk2->xMin >= blk1->xMax && blk2->yMin <= blk1->yMax && blk2->yMax >= blk1->yMin) { |
| before = true; |
| } |
| } |
| |
| if (blk2->yMax <= blk1->yMin) { |
| before = true; |
| } |
| } else { |
| if (blk2->isBeforeByRule1(blk1)) { |
| // Rule (1) blk1 and blk2 overlap, and blk2 is above blk1. |
| before = true; |
| #if 0 // for debugging |
| printf("rule1: %.2f..%.2f %.2f..%.2f %.2f..%.2f %.2f..%.2f\n", |
| blk2->ExMin, blk2->ExMax, blk2->EyMin, blk2->EyMax, |
| blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax); |
| #endif |
| } else if (blk2->isBeforeByRule2(blk1)) { |
| // Rule (2) blk2 left of blk1, and no intervening blk3 |
| // such that blk1 is before blk3 by rule 1, |
| // and blk3 is before blk2 by rule 1. |
| before = true; |
| for (int i = 0; i < cacheSize && cache[i]; ++i) { |
| if (blk1->isBeforeByRule1(cache[i]) && cache[i]->isBeforeByRule1(blk2)) { |
| before = false; |
| std::rotate(cache, cache + i, cache + i + 1); |
| break; |
| } |
| } |
| |
| if (before) { |
| for (blk3 = blkList; blk3; blk3 = blk3->next) { |
| if (blk3 == blk2 || blk3 == blk1) { |
| continue; |
| } |
| if (blk1->isBeforeByRule1(blk3) && blk3->isBeforeByRule1(blk2)) { |
| before = false; |
| std::copy_backward(cache, cache + cacheSize - 1, cache + cacheSize); |
| cache[0] = blk3; |
| break; |
| } |
| } |
| } |
| #if 0 // for debugging |
| if (before) { |
| printf("rule2: %.2f..%.2f %.2f..%.2f %.2f..%.2f %.2f..%.2f\n", |
| blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax, |
| blk2->ExMin, blk2->ExMax, blk2->EyMin, blk2->EyMax); |
| } |
| #endif |
| } |
| } |
| if (before) { |
| // blk2 is before blk1, so it needs to be visited |
| // before we can add blk1 to the sorted list. |
| sortPos = blk2->visitDepthFirst(blkList, pos2, sorted, sortPos, visited, cache, cacheSize); |
| } |
| } |
| #if 0 // for debugging |
| printf("sorted: %d %.2f..%.2f %.2f..%.2f\n", |
| sortPos, blk1->ExMin, blk1->ExMax, blk1->EyMin, blk1->EyMax); |
| #endif |
| sorted[sortPos++] = blk1; |
| return sortPos; |
| } |
| |
| int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1, TextBlock **sorted, int sortPos, bool *visited) |
| { |
| const int blockCacheSize = 4; |
| TextBlock *blockCache[blockCacheSize]; |
| std::fill(blockCache, blockCache + blockCacheSize, nullptr); |
| return visitDepthFirst(blkList, pos1, sorted, sortPos, visited, blockCache, blockCacheSize); |
| } |
| |
| //------------------------------------------------------------------------ |
| // TextFlow |
| //------------------------------------------------------------------------ |
| |
| TextFlow::TextFlow(TextPage *pageA, TextBlock *blk) |
| { |
| page = pageA; |
| xMin = blk->xMin; |
| xMax = blk->xMax; |
| yMin = blk->yMin; |
| yMax = blk->yMax; |
| priMin = blk->priMin; |
| priMax = blk->priMax; |
| blocks = lastBlk = blk; |
| next = nullptr; |
| } |
| |
| TextFlow::~TextFlow() |
| { |
| TextBlock *blk; |
| |
| while (blocks) { |
| blk = blocks; |
| blocks = blocks->next; |
| delete blk; |
| } |
| } |
| |
| void TextFlow::addBlock(TextBlock *blk) |
| { |
| if (lastBlk) { |
| lastBlk->next = blk; |
| } else { |
| blocks = blk; |
| } |
| lastBlk = blk; |
| if (blk->xMin < xMin) { |
| xMin = blk->xMin; |
| } |
| if (blk->xMax > xMax) { |
| xMax = blk->xMax; |
| } |
| if (blk->yMin < yMin) { |
| yMin = blk->yMin; |
| } |
| if (blk->yMax > yMax) { |
| yMax = blk->yMax; |
| } |
| } |
| |
| bool TextFlow::blockFits(const TextBlock *blk, const TextBlock *prevBlk) const |
| { |
| bool fits; |
| |
| // lower blocks must use smaller fonts |
| if (blk->lines->words->fontSize > lastBlk->lines->words->fontSize) { |
| return false; |
| } |
| |
| fits = false; // make gcc happy |
| switch (page->primaryRot) { |
| case 0: |
| fits = blk->xMin >= priMin && blk->xMax <= priMax; |
| break; |
| case 1: |
| fits = blk->yMin >= priMin && blk->yMax <= priMax; |
| break; |
| case 2: |
| fits = blk->xMin >= priMin && blk->xMax <= priMax; |
| break; |
| case 3: |
| fits = blk->yMin >= priMin && blk->yMax <= priMax; |
| break; |
| } |
| return fits; |
| } |
| |
| #ifdef TEXTOUT_WORD_LIST |
| |
| //------------------------------------------------------------------------ |
| // TextWordList |
| //------------------------------------------------------------------------ |
| |
| TextWordList::TextWordList(const TextPage *text, bool physLayout) |
| { |
| TextFlow *flow; |
| TextBlock *blk; |
| TextLine *line; |
| TextWord *word; |
| TextWord **wordArray; |
| int nWords, i; |
| |
| if (text->rawOrder) { |
| for (word = text->rawWords; word; word = word->next) { |
| words.push_back(word); |
| } |
| |
| } else if (physLayout) { |
| // this is inefficient, but it's also the least useful of these |
| // three cases |
| nWords = 0; |
| for (flow = text->flows; flow; flow = flow->next) { |
| for (blk = flow->blocks; blk; blk = blk->next) { |
| for (line = blk->lines; line; line = line->next) { |
| for (word = line->words; word; word = word->next) { |
| ++nWords; |
| } |
| } |
| } |
| } |
| wordArray = (TextWord **)gmallocn(nWords, sizeof(TextWord *)); |
| i = 0; |
| for (flow = text->flows; flow; flow = flow->next) { |
| for (blk = flow->blocks; blk; blk = blk->next) { |
| for (line = blk->lines; line; line = line->next) { |
| for (word = line->words; word; word = word->next) { |
| wordArray[i++] = word; |
| } |
| } |
| } |
| } |
| qsort(static_cast<void *>(wordArray), nWords, sizeof(TextWord *), &TextWord::cmpYX); |
| for (i = 0; i < nWords; ++i) { |
| words.push_back(wordArray[i]); |
| } |
| gfree(static_cast<void *>(wordArray)); |
| |
| } else { |
| for (flow = text->flows; flow; flow = flow->next) { |
| for (blk = flow->blocks; blk; blk = blk->next) { |
| for (line = blk->lines; line; line = line->next) { |
| for (word = line->words; word; word = word->next) { |
| words.push_back(word); |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| TextWordList::~TextWordList() { } |
| |
| int TextWordList::getLength() const |
| { |
| return words.size(); |
| } |
| |
| TextWord *TextWordList::get(int idx) |
| { |
| if (idx < 0 || idx >= (int)words.size()) { |
| return nullptr; |
| } |
| return words[idx]; |
| } |
| |
| #endif // TEXTOUT_WORD_LIST |
| |
| //------------------------------------------------------------------------ |
| // TextPage |
| //------------------------------------------------------------------------ |
| |
| TextPage::TextPage(bool rawOrderA, bool discardDiagA) |
| { |
| int rot; |
| |
| refCnt = 1; |
| rawOrder = rawOrderA; |
| discardDiag = discardDiagA; |
| curWord = nullptr; |
| charPos = 0; |
| curFont = nullptr; |
| curFontSize = 0; |
| nest = 0; |
| nTinyChars = 0; |
| lastCharOverlap = false; |
| if (!rawOrder) { |
| for (rot = 0; rot < 4; ++rot) { |
| pools[rot] = std::make_unique<TextPool>(); |
| } |
| } |
| flows = nullptr; |
| blocks = nullptr; |
| rawWords = nullptr; |
| rawLastWord = nullptr; |
| lastFindXMin = lastFindYMin = 0; |
| haveLastFind = false; |
| mergeCombining = true; |
| diagonal = false; |
| } |
| |
| TextPage::~TextPage() |
| { |
| clear(); |
| } |
| |
| void TextPage::incRefCnt() |
| { |
| refCnt++; |
| } |
| |
| void TextPage::decRefCnt() |
| { |
| if (--refCnt == 0) { |
| delete this; |
| } |
| } |
| |
| void TextPage::startPage(const GfxState *state) |
| { |
| clear(); |
| if (state) { |
| pageWidth = state->getPageWidth(); |
| pageHeight = state->getPageHeight(); |
| } else { |
| pageWidth = pageHeight = 0; |
| } |
| } |
| |
| void TextPage::endPage() |
| { |
| if (curWord) { |
| endWord(); |
| } |
| } |
| |
| void TextPage::clear() |
| { |
| int rot; |
| TextFlow *flow; |
| TextWord *word; |
| |
| if (curWord) { |
| delete curWord; |
| curWord = nullptr; |
| } |
| if (rawOrder) { |
| while (rawWords) { |
| word = rawWords; |
| rawWords = rawWords->next; |
| delete word; |
| } |
| } else { |
| for (rot = 0; rot < 4; ++rot) { |
| pools[rot] = std::make_unique<TextPool>(); |
| } |
| while (flows) { |
| flow = flows; |
| flows = flows->next; |
| delete flow; |
| } |
| gfree(static_cast<void *>(blocks)); |
| } |
| fonts.clear(); |
| underlines.clear(); |
| links.clear(); |
| |
| diagonal = false; |
| curWord = nullptr; |
| charPos = 0; |
| curFont = nullptr; |
| curFontSize = 0; |
| nest = 0; |
| nTinyChars = 0; |
| flows = nullptr; |
| blocks = nullptr; |
| rawWords = nullptr; |
| rawLastWord = nullptr; |
| } |
| |
| void TextPage::updateFont(const GfxState *state) |
| { |
| const double *fm; |
| const char *name; |
| int code, mCode, letterCode, anyCode; |
| double w; |
| |
| // get the font info object |
| curFont = nullptr; |
| for (const std::unique_ptr<TextFontInfo> &f : fonts) { |
| if (f->matches(state)) { |
| curFont = f.get(); |
| break; |
| } |
| } |
| if (!curFont) { |
| fonts.emplace_back(std::make_unique<TextFontInfo>(state)); |
| curFont = fonts.back().get(); |
| } |
| |
| // adjust the font size |
| GfxFont *const gfxFont = state->getFont().get(); |
| curFontSize = state->getTransformedFontSize(); |
| if (gfxFont && gfxFont->getType() == fontType3) { |
| // This is a hack which makes it possible to deal with some Type 3 |
| // fonts. The problem is that it's impossible to know what the |
| // base coordinate system used in the font is without actually |
| // rendering the font. This code tries to guess by looking at the |
| // width of the character 'm' (which breaks if the font is a |
| // subset that doesn't contain 'm'). |
| mCode = letterCode = anyCode = -1; |
| for (code = 0; code < 256; ++code) { |
| name = ((Gfx8BitFont *)gfxFont)->getCharName(code); |
| int nameLen = name ? strlen(name) : 0; |
| bool nameOneChar = nameLen == 1 || (nameLen > 1 && name[1] == '\0'); |
| if (nameOneChar && name[0] == 'm') { |
| mCode = code; |
| } |
| if (letterCode < 0 && nameOneChar && ((name[0] >= 'A' && name[0] <= 'Z') || (name[0] >= 'a' && name[0] <= 'z'))) { |
| letterCode = code; |
| } |
| if (anyCode < 0 && name && ((Gfx8BitFont *)gfxFont)->getWidth(code) > 0) { |
| anyCode = code; |
| } |
| } |
| if (mCode >= 0 && (w = ((Gfx8BitFont *)gfxFont)->getWidth(mCode)) > 0) { |
| // 0.6 is a generic average 'm' width -- yes, this is a hack |
| curFontSize *= w / 0.6; |
| } else if (letterCode >= 0 && (w = ((Gfx8BitFont *)gfxFont)->getWidth(letterCode)) > 0) { |
| // even more of a hack: 0.5 is a generic letter width |
| curFontSize *= w / 0.5; |
| } else if (anyCode >= 0 && (w = ((Gfx8BitFont *)gfxFont)->getWidth(anyCode)) > 0) { |
| // better than nothing: 0.5 is a generic character width |
| curFontSize *= w / 0.5; |
| } |
| fm = gfxFont->getFontMatrix(); |
| if (fm[0] != 0) { |
| curFontSize *= fabs(fm[3] / fm[0]); |
| } |
| } |
| } |
| |
| void TextPage::beginWord(const GfxState *state) |
| { |
| const double *fontm; |
| double m[4], m2[4]; |
| int rot; |
| |
| // This check is needed because Type 3 characters can contain |
| // text-drawing operations (when TextPage is being used via |
| // {X,Win}SplashOutputDev rather than TextOutputDev). |
| if (curWord) { |
| ++nest; |
| return; |
| } |
| |
| // compute the rotation |
| state->getFontTransMat(&m[0], &m[1], &m[2], &m[3]); |
| const std::shared_ptr<GfxFont> &gfxFont = state->getFont(); |
| if (gfxFont && gfxFont->getType() == fontType3) { |
| fontm = state->getFont()->getFontMatrix(); |
| m2[0] = fontm[0] * m[0] + fontm[1] * m[2]; |
| m2[1] = fontm[0] * m[1] + fontm[1] * m[3]; |
| m2[2] = fontm[2] * m[0] + fontm[3] * m[2]; |
| m2[3] = fontm[2] * m[1] + fontm[3] * m[3]; |
| m[0] = m2[0]; |
| m[1] = m2[1]; |
| m[2] = m2[2]; |
| m[3] = m2[3]; |
| } |
| if (fabs(m[0] * m[3]) > fabs(m[1] * m[2])) { |
| rot = (m[0] > 0 || m[3] < 0) ? 0 : 2; |
| } else { |
| rot = (m[2] > 0) ? 1 : 3; |
| } |
| if (fabs(m[0]) >= fabs(m[1])) { |
| diagonal = fabs(m[1]) > diagonalThreshold * fabs(m[0]); |
| } else { |
| diagonal = fabs(m[0]) > diagonalThreshold * fabs(m[1]); |
| } |
| |
| // for vertical writing mode, the lines are effectively rotated 90 |
| // degrees |
| if (gfxFont && gfxFont->getWMode()) { |
| rot = (rot + 1) & 3; |
| } |
| |
| curWord = new TextWord(state, rot, curFontSize); |
| } |
| |
| void TextPage::addChar(const GfxState *state, double x, double y, double dx, double dy, CharCode c, int nBytes, const Unicode *u, int uLen) |
| { |
| double x1, y1, w1, h1, dx2, dy2, base, sp, delta; |
| bool overlap; |
| int i; |
| int wMode; |
| Matrix mat; |
| |
| // subtract char and word spacing from the dx,dy values |
| sp = state->getCharSpace(); |
| if (c == (CharCode)0x20) { |
| sp += state->getWordSpace(); |
| } |
| state->textTransformDelta(sp * state->getHorizScaling(), 0, &dx2, &dy2); |
| dx -= dx2; |
| dy -= dy2; |
| state->transformDelta(dx, dy, &w1, &h1); |
| |
| // throw away chars that aren't inside the page bounds |
| // (and also do a sanity check on the character size) |
| state->transform(x, y, &x1, &y1); |
| if (x1 + w1 < 0 || x1 > pageWidth || y1 + h1 < 0 || y1 > pageHeight || std::isnan(x1) || std::isnan(y1) || std::isnan(w1) || std::isnan(h1)) { |
| charPos += nBytes; |
| return; |
| } |
| |
| // check the tiny chars limit |
| if (fabs(w1) < 3 && fabs(h1) < 3) { |
| if (++nTinyChars > 50000) { |
| charPos += nBytes; |
| return; |
| } |
| } |
| |
| // break words at space character |
| if (uLen == 1 && UnicodeIsWhitespace(u[0])) { |
| charPos += nBytes; |
| endWord(); |
| return; |
| } else if (uLen == 1 && u[0] == (Unicode)0x0) { |
| // ignore null characters |
| charPos += nBytes; |
| return; |
| } |
| |
| state->getFontTransMat(&mat.m[0], &mat.m[1], &mat.m[2], &mat.m[3]); |
| mat.m[0] *= state->getHorizScaling(); |
| mat.m[1] *= state->getHorizScaling(); |
| mat.m[4] = x1; |
| mat.m[5] = y1; |
| |
| if (mergeCombining && curWord && uLen == 1 && curWord->addCombining(state, curFont, curFontSize, x1, y1, w1, h1, charPos, nBytes, c, u[0], mat)) { |
| charPos += nBytes; |
| return; |
| } |
| |
| // start a new word if: |
| // (1) this character doesn't fall in the right place relative to |
| // the end of the previous word (this places upper and lower |
| // constraints on the position deltas along both the primary |
| // and secondary axes), or |
| // (2) this character overlaps the previous one (duplicated text), or |
| // (3) the previous character was an overlap (we want each duplicated |
| // character to be in a word by itself at this stage), |
| // (4) the font size has changed |
| // (5) the WMode changed |
| if (curWord && curWord->len() > 0) { |
| base = sp = delta = 0; // make gcc happy |
| switch (curWord->rot) { |
| case 0: |
| base = y1; |
| sp = x1 - curWord->xMax; |
| delta = x1 - curWord->chars.back().edge; |
| break; |
| case 1: |
| base = x1; |
| sp = y1 - curWord->yMax; |
| delta = y1 - curWord->chars.back().edge; |
| break; |
| case 2: |
| base = y1; |
| sp = curWord->xMin - x1; |
| delta = curWord->chars.back().edge - x1; |
| break; |
| case 3: |
| base = x1; |
| sp = curWord->yMin - y1; |
| delta = curWord->chars.back().edge - y1; |
| break; |
| } |
| overlap = fabs(delta) < dupMaxPriDelta * curWord->fontSize && fabs(base - curWord->base) < dupMaxSecDelta * curWord->fontSize; |
| wMode = curFont->getWMode(); |
| if (overlap || lastCharOverlap || sp < -minDupBreakOverlap * curWord->fontSize || sp > minWordBreakSpace * curWord->fontSize || fabs(base - curWord->base) > 0.5 || curFontSize != curWord->fontSize || wMode != curWord->wMode) { |
| endWord(); |
| } |
| lastCharOverlap = overlap; |
| } else { |
| lastCharOverlap = false; |
| } |
| |
| if (uLen != 0) { |
| // start a new word if needed |
| if (!curWord) { |
| beginWord(state); |
| } |
| |
| // throw away diagonal chars |
| if (discardDiag && diagonal) { |
| charPos += nBytes; |
| return; |
| } |
| |
| // page rotation and/or transform matrices can cause text to be |
| // drawn in reverse order -- in this case, swap the begin/end |
| // coordinates and break text into individual chars |
| if ((curWord->rot == 0 && w1 < 0) || (curWord->rot == 1 && h1 < 0) || (curWord->rot == 2 && w1 > 0) || (curWord->rot == 3 && h1 > 0)) { |
| endWord(); |
| beginWord(state); |
| |
| // throw away diagonal chars |
| if (discardDiag && diagonal) { |
| charPos += nBytes; |
| return; |
| } |
| |
| x1 += w1; |
| y1 += |