blob: 1e48e90bf6c8b8ee7153744587d7f7505d2f2a11 [file] [log] [blame]
//========================================================================
//
// SplashXPathScanner.cc
//
//========================================================================
//========================================================================
//
// 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) 2008, 2010, 2014 Albert Astals Cid <aacid@kde.org>
// Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
// Copyright (C) 2013, 2014 Thomas Freitag <Thomas.Freitag@alfa.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>
#ifdef USE_GCC_PRAGMAS
#pragma implementation
#endif
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include "goo/gmem.h"
#include "SplashMath.h"
#include "SplashXPath.h"
#include "SplashBitmap.h"
#include "SplashXPathScanner.h"
//------------------------------------------------------------------------
struct SplashIntersect {
int y;
int x0, x1; // intersection of segment with [y, y+1)
int count; // EO/NZWN counter increment
};
struct cmpIntersectFunctor {
bool operator()(const SplashIntersect &i0, const SplashIntersect &i1) {
return (i0.y != i1.y) ? (i0.y < i1.y) : (i0.x0 < i1.x0);
}
};
//------------------------------------------------------------------------
// SplashXPathScanner
//------------------------------------------------------------------------
SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA,
int clipYMin, int clipYMax) {
SplashXPathSeg *seg;
SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
int i;
xPath = xPathA;
eo = eoA;
partialClip = gFalse;
// compute the bbox
if (xPath->length == 0) {
xMin = yMin = 1;
xMax = yMax = 0;
} else {
seg = &xPath->segs[0];
if (seg->x0 <= seg->x1) {
xMinFP = seg->x0;
xMaxFP = seg->x1;
} else {
xMinFP = seg->x1;
xMaxFP = seg->x0;
}
if (seg->flags & splashXPathFlip) {
yMinFP = seg->y1;
yMaxFP = seg->y0;
} else {
yMinFP = seg->y0;
yMaxFP = seg->y1;
}
for (i = 1; i < xPath->length; ++i) {
seg = &xPath->segs[i];
if (seg->x0 < xMinFP) {
xMinFP = seg->x0;
} else if (seg->x0 > xMaxFP) {
xMaxFP = seg->x0;
}
if (seg->x1 < xMinFP) {
xMinFP = seg->x1;
} else if (seg->x1 > xMaxFP) {
xMaxFP = seg->x1;
}
if (seg->flags & splashXPathFlip) {
if (seg->y0 > yMaxFP) {
yMaxFP = seg->y0;
}
} else {
if (seg->y1 > yMaxFP) {
yMaxFP = seg->y1;
}
}
}
xMin = splashFloor(xMinFP);
xMax = splashFloor(xMaxFP);
yMin = splashFloor(yMinFP);
yMax = splashFloor(yMaxFP);
if (clipYMin > yMin) {
yMin = clipYMin;
partialClip = gTrue;
}
if (clipYMax < yMax) {
yMax = clipYMax;
partialClip = gTrue;
}
}
allInter = nullptr;
inter = nullptr;
computeIntersections();
interY = yMin - 1;
}
SplashXPathScanner::~SplashXPathScanner() {
gfree(inter);
gfree(allInter);
}
void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA,
int *xMaxA, int *yMaxA) {
*xMinA = xMin / splashAASize;
*yMinA = yMin / splashAASize;
*xMaxA = xMax / splashAASize;
*yMaxA = yMax / splashAASize;
}
void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
int interBegin, interEnd, xx, i;
if (y < yMin || y > yMax) {
interBegin = interEnd = 0;
} else {
interBegin = inter[y - yMin];
interEnd = inter[y - yMin + 1];
}
if (interBegin < interEnd) {
*spanXMin = allInter[interBegin].x0;
xx = allInter[interBegin].x1;
for (i = interBegin + 1; i < interEnd; ++i) {
if (allInter[i].x1 > xx) {
xx = allInter[i].x1;
}
}
*spanXMax = xx;
} else {
*spanXMin = xMax + 1;
*spanXMax = xMax;
}
}
GBool SplashXPathScanner::test(int x, int y) {
int interBegin, interEnd, count, i;
if (y < yMin || y > yMax) {
return gFalse;
}
interBegin = inter[y - yMin];
interEnd = inter[y - yMin + 1];
count = 0;
for (i = interBegin; i < interEnd && allInter[i].x0 <= x; ++i) {
if (x <= allInter[i].x1) {
return gTrue;
}
count += allInter[i].count;
}
return eo ? (count & 1) : (count != 0);
}
GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
int interBegin, interEnd, count, xx1, i;
if (y < yMin || y > yMax) {
return gFalse;
}
interBegin = inter[y - yMin];
interEnd = inter[y - yMin + 1];
count = 0;
for (i = interBegin; i < interEnd && allInter[i].x1 < x0; ++i) {
count += allInter[i].count;
}
// invariant: the subspan [x0,xx1] is inside the path
xx1 = x0 - 1;
while (xx1 < x1) {
if (i >= interEnd) {
return gFalse;
}
if (allInter[i].x0 > xx1 + 1 &&
!(eo ? (count & 1) : (count != 0))) {
return gFalse;
}
if (allInter[i].x1 > xx1) {
xx1 = allInter[i].x1;
}
count += allInter[i].count;
++i;
}
return gTrue;
}
GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
int interEnd, xx0, xx1;
if (y < yMin || y > yMax) {
return gFalse;
}
if (interY != y) {
interY = y;
interIdx = inter[y - yMin];
interCount = 0;
}
interEnd = inter[y - yMin + 1];
if (interIdx >= interEnd) {
return gFalse;
}
xx0 = allInter[interIdx].x0;
xx1 = allInter[interIdx].x1;
interCount += allInter[interIdx].count;
++interIdx;
while (interIdx < interEnd &&
(allInter[interIdx].x0 <= xx1 ||
(eo ? (interCount & 1) : (interCount != 0)))) {
if (allInter[interIdx].x1 > xx1) {
xx1 = allInter[interIdx].x1;
}
interCount += allInter[interIdx].count;
++interIdx;
}
*x0 = xx0;
*x1 = xx1;
return gTrue;
}
void SplashXPathScanner::computeIntersections() {
SplashXPathSeg *seg;
SplashCoord segXMin, segXMax, segYMin, segYMax, xx0, xx1;
int x, y, y0, y1, i;
if (yMin > yMax) {
return;
}
// build the list of all intersections
allInterLen = 0;
allInterSize = 16;
allInter = (SplashIntersect *)gmallocn(allInterSize,
sizeof(SplashIntersect));
for (i = 0; i < xPath->length; ++i) {
seg = &xPath->segs[i];
if (seg->flags & splashXPathFlip) {
segYMin = seg->y1;
segYMax = seg->y0;
} else {
segYMin = seg->y0;
segYMax = seg->y1;
}
if (seg->flags & splashXPathHoriz) {
y = splashFloor(seg->y0);
if (y >= yMin && y <= yMax) {
if (!addIntersection(segYMin, segYMax, seg->flags,
y, splashFloor(seg->x0), splashFloor(seg->x1)))
break;
}
} else if (seg->flags & splashXPathVert) {
y0 = splashFloor(segYMin);
if (y0 < yMin) {
y0 = yMin;
}
y1 = splashFloor(segYMax);
if (y1 > yMax) {
y1 = yMax;
}
x = splashFloor(seg->x0);
for (y = y0; y <= y1; ++y) {
if (!addIntersection(segYMin, segYMax, seg->flags, y, x, x))
break;
}
} else {
if (seg->x0 < seg->x1) {
segXMin = seg->x0;
segXMax = seg->x1;
} else {
segXMin = seg->x1;
segXMax = seg->x0;
}
y0 = splashFloor(segYMin);
if (y0 < yMin) {
y0 = yMin;
}
y1 = splashFloor(segYMax);
if (y1 > yMax) {
y1 = yMax;
}
// this loop could just add seg->dxdy to xx1 on each iteration,
// but that introduces numerical accuracy problems
xx1 = seg->x0 + ((SplashCoord)y0 - seg->y0) * seg->dxdy;
for (y = y0; y <= y1; ++y) {
xx0 = xx1;
xx1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
// the segment may not actually extend to the top and/or bottom edges
if (xx0 < segXMin) {
xx0 = segXMin;
} else if (xx0 > segXMax) {
xx0 = segXMax;
}
if (xx1 < segXMin) {
xx1 = segXMin;
} else if (xx1 > segXMax) {
xx1 = segXMax;
}
if (!addIntersection(segYMin, segYMax, seg->flags, y,
splashFloor(xx0), splashFloor(xx1)))
break;
}
}
}
std::sort(allInter, allInter + allInterLen, cmpIntersectFunctor());
// build the list of y pointers
inter = (int *)gmallocn(yMax - yMin + 2, sizeof(int));
i = 0;
for (y = yMin; y <= yMax; ++y) {
inter[y - yMin] = i;
while (i < allInterLen && allInter[i].y <= y) {
++i;
}
}
inter[yMax - yMin + 1] = i;
}
GBool SplashXPathScanner::addIntersection(double segYMin, double segYMax,
Guint segFlags,
int y, int x0, int x1) {
if (allInterLen == allInterSize) {
unsigned int newInterSize = ((unsigned int) allInterSize * 2 > INT_MAX / sizeof(SplashIntersect)) ? allInterSize + 32768 : allInterSize * 2;
if (newInterSize >= INT_MAX / sizeof(SplashIntersect)) {
error(errInternal, -1, "Bogus memory allocation size in SplashXPathScanner::addIntersection {0:d}", newInterSize);
return gFalse;
}
allInterSize = newInterSize;
allInter = (SplashIntersect *)greallocn(allInter, newInterSize,
sizeof(SplashIntersect));
}
allInter[allInterLen].y = y;
if (x0 < x1) {
allInter[allInterLen].x0 = x0;
allInter[allInterLen].x1 = x1;
} else {
allInter[allInterLen].x0 = x1;
allInter[allInterLen].x1 = x0;
}
if (segYMin <= y &&
(SplashCoord)y < segYMax &&
!(segFlags & splashXPathHoriz)) {
allInter[allInterLen].count = eo ? 1
: (segFlags & splashXPathFlip) ? 1 : -1;
} else {
allInter[allInterLen].count = 0;
}
++allInterLen;
return gTrue;
}
void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
int *x0, int *x1, int y, GBool adjustVertLine) {
int xx0, xx1, xx, xxMin, xxMax, yy, interEnd;
Guchar mask;
SplashColorPtr p;
memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
xxMin = aaBuf->getWidth();
xxMax = -1;
if (yMin <= yMax) {
if (splashAASize * y < yMin) {
interIdx = inter[0];
} else if (splashAASize * y > yMax) {
interIdx = inter[yMax - yMin + 1];
} else {
interIdx = inter[splashAASize * y - yMin];
}
for (yy = 0; yy < splashAASize; ++yy) {
if (splashAASize * y + yy < yMin) {
interEnd = inter[0];
} else if (splashAASize * y + yy > yMax) {
interEnd = inter[yMax - yMin + 1];
} else {
interEnd = inter[splashAASize * y + yy - yMin + 1];
}
interCount = 0;
while (interIdx < interEnd) {
xx0 = allInter[interIdx].x0;
xx1 = allInter[interIdx].x1;
interCount += allInter[interIdx].count;
++interIdx;
while (interIdx < interEnd &&
(allInter[interIdx].x0 <= xx1 ||
(eo ? (interCount & 1) : (interCount != 0)))) {
if (allInter[interIdx].x1 > xx1) {
xx1 = allInter[interIdx].x1;
}
interCount += allInter[interIdx].count;
++interIdx;
}
if (xx0 < 0) {
xx0 = 0;
}
++xx1;
if (xx1 > aaBuf->getWidth()) {
xx1 = aaBuf->getWidth();
}
// set [xx0, xx1) to 1
if (xx0 < xx1) {
xx = xx0;
p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
if (xx & 7) {
mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
mask &= (Guchar)(0xff00 >> (xx1 & 7));
}
*p++ |= mask;
xx = (xx & ~7) + 8;
}
for (; xx + 7 < xx1; xx += 8) {
*p++ |= 0xff;
}
if (xx < xx1) {
*p |= adjustVertLine ? 0xff : (Guchar)(0xff00 >> (xx1 & 7));
}
}
if (xx0 < xxMin) {
xxMin = xx0;
}
if (xx1 > xxMax) {
xxMax = xx1;
}
}
}
}
if (xxMin > xxMax) {
xxMin = xxMax;
}
*x0 = xxMin / splashAASize;
*x1 = (xxMax - 1) / splashAASize;
}
void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
int *x0, int *x1, int y) {
int xx0, xx1, xx, yy, interEnd;
Guchar mask;
SplashColorPtr p;
for (yy = 0; yy < splashAASize; ++yy) {
xx = *x0 * splashAASize;
if (yMin <= yMax) {
if (splashAASize * y + yy < yMin) {
interIdx = interEnd = inter[0];
} else if (splashAASize * y + yy > yMax) {
interIdx = interEnd = inter[yMax - yMin + 1];
} else {
interIdx = inter[splashAASize * y + yy - yMin];
if (splashAASize * y + yy > yMax) {
interEnd = inter[yMax - yMin + 1];
} else {
interEnd = inter[splashAASize * y + yy - yMin + 1];
}
}
interCount = 0;
while (interIdx < interEnd && xx < (*x1 + 1) * splashAASize) {
xx0 = allInter[interIdx].x0;
xx1 = allInter[interIdx].x1;
interCount += allInter[interIdx].count;
++interIdx;
while (interIdx < interEnd &&
(allInter[interIdx].x0 <= xx1 ||
(eo ? (interCount & 1) : (interCount != 0)))) {
if (allInter[interIdx].x1 > xx1) {
xx1 = allInter[interIdx].x1;
}
interCount += allInter[interIdx].count;
++interIdx;
}
if (xx0 > aaBuf->getWidth()) {
xx0 = aaBuf->getWidth();
}
// set [xx, xx0) to 0
if (xx < xx0) {
p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
if (xx & 7) {
mask = (Guchar)(0xff00 >> (xx & 7));
if ((xx & ~7) == (xx0 & ~7)) {
mask |= 0xff >> (xx0 & 7);
}
*p++ &= mask;
xx = (xx & ~7) + 8;
}
for (; xx + 7 < xx0; xx += 8) {
*p++ = 0x00;
}
if (xx < xx0) {
*p &= 0xff >> (xx0 & 7);
}
}
if (xx1 >= xx) {
xx = xx1 + 1;
}
}
}
xx0 = (*x1 + 1) * splashAASize;
if (xx0 > aaBuf->getWidth()) xx0 = aaBuf->getWidth();
// set [xx, xx0) to 0
if (xx < xx0 && xx >= 0) {
p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
if (xx & 7) {
mask = (Guchar)(0xff00 >> (xx & 7));
if ((xx & ~7) == (xx0 & ~7)) {
mask &= 0xff >> (xx0 & 7);
}
*p++ &= mask;
xx = (xx & ~7) + 8;
}
for (; xx + 7 < xx0; xx += 8) {
*p++ = 0x00;
}
if (xx < xx0) {
*p &= 0xff >> (xx0 & 7);
}
}
}
}