source/libs/poppler/poppler-src/splash/SplashXPathScanner.cc

   1 //========================================================================
   2 //
   3 // SplashXPathScanner.cc
   4 //
   5 //========================================================================
   6
   7 //========================================================================
   8 //
   9 // Modified under the Poppler project - http://poppler.freedesktop.org
  10 //
  11 // All changes made under the Poppler project to this file are licensed
  12 // under GPL version 2 or later
  13 //
  14 // Copyright (C) 2008, 2010, 2014 Albert Astals Cid <aacid@kde.org>
  15 // Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
  16 // Copyright (C) 2013, 2014 Thomas Freitag <Thomas.Freitag@alfa.de>
  17 //
  18 // To see a description of the changes please see the Changelog file that
  19 // came with your tarball or type make ChangeLog if you are building from git
  20 //
  21 //========================================================================
  22
  23 #include <config.h>
  24
  25 #ifdef USE_GCC_PRAGMAS
  26 #pragma implementation
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <algorithm>
  32 #include "goo/gmem.h"
  33 #include "SplashMath.h"
  34 #include "SplashXPath.h"
  35 #include "SplashBitmap.h"
  36 #include "SplashXPathScanner.h"
  37
  38 //------------------------------------------------------------------------
  39
  40 struct SplashIntersect {
  41   int y;
  42   int x0, x1;                   // intersection of segment with [y, y+1)
  43   int count;                    // EO/NZWN counter increment
  44 };
  45
  46 struct cmpIntersectFunctor {
  47   bool operator()(const SplashIntersect &i0, const SplashIntersect &i1) {
  48     return (i0.y != i1.y) ? (i0.y < i1.y) : (i0.x0 < i1.x0);
  49   }
  50 };
  51
  52 //------------------------------------------------------------------------
  53 // SplashXPathScanner
  54 //------------------------------------------------------------------------
  55
  56 SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA,
  57                                        int clipYMin, int clipYMax) {
  58   SplashXPathSeg *seg;
  59   SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
  60   int i;
  61
  62   xPath = xPathA;
  63   eo = eoA;
  64   partialClip = gFalse;
  65
  66   // compute the bbox
  67   if (xPath->length == 0) {
  68     xMin = yMin = 1;
  69     xMax = yMax = 0;
  70   } else {
  71     seg = &xPath->segs[0];
  72     if (seg->x0 <= seg->x1) {
  73       xMinFP = seg->x0;
  74       xMaxFP = seg->x1;
  75     } else {
  76       xMinFP = seg->x1;
  77       xMaxFP = seg->x0;
  78     }
  79     if (seg->flags & splashXPathFlip) {
  80       yMinFP = seg->y1;
  81       yMaxFP = seg->y0;
  82     } else {
  83       yMinFP = seg->y0;
  84       yMaxFP = seg->y1;
  85     }
  86     for (i = 1; i < xPath->length; ++i) {
  87       seg = &xPath->segs[i];
  88       if (seg->x0 < xMinFP) {
  89         xMinFP = seg->x0;
  90       } else if (seg->x0 > xMaxFP) {
  91         xMaxFP = seg->x0;
  92       }
  93       if (seg->x1 < xMinFP) {
  94         xMinFP = seg->x1;
  95       } else if (seg->x1 > xMaxFP) {
  96         xMaxFP = seg->x1;
  97       }
  98       if (seg->flags & splashXPathFlip) {
  99         if (seg->y0 > yMaxFP) {
 100           yMaxFP = seg->y0;
 101         }
 102       } else {
 103         if (seg->y1 > yMaxFP) {
 104           yMaxFP = seg->y1;
 105         }
 106       }
 107     }
 108     xMin = splashFloor(xMinFP);
 109     xMax = splashFloor(xMaxFP);
 110     yMin = splashFloor(yMinFP);
 111     yMax = splashFloor(yMaxFP);
 112     if (clipYMin > yMin) {
 113       yMin = clipYMin;
 114       partialClip = gTrue;
 115     }
 116     if (clipYMax < yMax) {
 117       yMax = clipYMax;
 118       partialClip = gTrue;
 119     }
 120   }
 121
 122   allInter = NULL;
 123   inter = NULL;
 124   computeIntersections();
 125   interY = yMin - 1;
 126 }
 127
 128 SplashXPathScanner::~SplashXPathScanner() {
 129   gfree(inter);
 130   gfree(allInter);
 131 }
 132
 133 void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA,
 134                                    int *xMaxA, int *yMaxA) {
 135   *xMinA = xMin / splashAASize;
 136   *yMinA = yMin / splashAASize;
 137   *xMaxA = xMax / splashAASize;
 138   *yMaxA = yMax / splashAASize;
 139 }
 140
 141 void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
 142   int interBegin, interEnd, xx, i;
 143
 144   if (y < yMin || y > yMax) {
 145     interBegin = interEnd = 0;
 146   } else {
 147     interBegin = inter[y - yMin];
 148     interEnd = inter[y - yMin + 1];
 149   }
 150   if (interBegin < interEnd) {
 151     *spanXMin = allInter[interBegin].x0;
 152     xx = allInter[interBegin].x1;
 153     for (i = interBegin + 1; i < interEnd; ++i) {
 154       if (allInter[i].x1 > xx) {
 155         xx = allInter[i].x1;
 156       }
 157     }
 158     *spanXMax = xx;
 159   } else {
 160     *spanXMin = xMax + 1;
 161     *spanXMax = xMax;
 162   }
 163 }
 164
 165 GBool SplashXPathScanner::test(int x, int y) {
 166   int interBegin, interEnd, count, i;
 167
 168   if (y < yMin || y > yMax) {
 169     return gFalse;
 170   }
 171   interBegin = inter[y - yMin];
 172   interEnd = inter[y - yMin + 1];
 173   count = 0;
 174   for (i = interBegin; i < interEnd && allInter[i].x0 <= x; ++i) {
 175     if (x <= allInter[i].x1) {
 176       return gTrue;
 177     }
 178     count += allInter[i].count;
 179   }
 180   return eo ? (count & 1) : (count != 0);
 181 }
 182
 183 GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
 184   int interBegin, interEnd, count, xx1, i;
 185
 186   if (y < yMin || y > yMax) {
 187     return gFalse;
 188   }
 189   interBegin = inter[y - yMin];
 190   interEnd = inter[y - yMin + 1];
 191   count = 0;
 192   for (i = interBegin; i < interEnd && allInter[i].x1 < x0; ++i) {
 193     count += allInter[i].count;
 194   }
 195
 196   // invariant: the subspan [x0,xx1] is inside the path
 197   xx1 = x0 - 1;
 198   while (xx1 < x1) {
 199     if (i >= interEnd) {
 200       return gFalse;
 201     }
 202     if (allInter[i].x0 > xx1 + 1 &&
 203         !(eo ? (count & 1) : (count != 0))) {
 204       return gFalse;
 205     }
 206     if (allInter[i].x1 > xx1) {
 207       xx1 = allInter[i].x1;
 208     }
 209     count += allInter[i].count;
 210     ++i;
 211   }
 212
 213   return gTrue;
 214 }
 215
 216 GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
 217   int interEnd, xx0, xx1;
 218
 219   if (y < yMin || y > yMax) {
 220     return gFalse;
 221   }
 222   if (interY != y) {
 223     interY = y;
 224     interIdx = inter[y - yMin];
 225     interCount = 0;
 226   }
 227   interEnd = inter[y - yMin + 1];
 228   if (interIdx >= interEnd) {
 229     return gFalse;
 230   }
 231   xx0 = allInter[interIdx].x0;
 232   xx1 = allInter[interIdx].x1;
 233   interCount += allInter[interIdx].count;
 234   ++interIdx;
 235   while (interIdx < interEnd &&
 236          (allInter[interIdx].x0 <= xx1 ||
 237           (eo ? (interCount & 1) : (interCount != 0)))) {
 238     if (allInter[interIdx].x1 > xx1) {
 239       xx1 = allInter[interIdx].x1;
 240     }
 241     interCount += allInter[interIdx].count;
 242     ++interIdx;
 243   }
 244   *x0 = xx0;
 245   *x1 = xx1;
 246   return gTrue;
 247 }
 248
 249 void SplashXPathScanner::computeIntersections() {
 250   SplashXPathSeg *seg;
 251   SplashCoord segXMin, segXMax, segYMin, segYMax, xx0, xx1;
 252   int x, y, y0, y1, i;
 253
 254   if (yMin > yMax) {
 255     return;
 256   }
 257
 258   // build the list of all intersections
 259   allInterLen = 0;
 260   allInterSize = 16;
 261   allInter = (SplashIntersect *)gmallocn(allInterSize,
 262                                          sizeof(SplashIntersect));
 263   for (i = 0; i < xPath->length; ++i) {
 264     seg = &xPath->segs[i];
 265     if (seg->flags & splashXPathFlip) {
 266       segYMin = seg->y1;
 267       segYMax = seg->y0;
 268     } else {
 269       segYMin = seg->y0;
 270       segYMax = seg->y1;
 271     }
 272     if (seg->flags & splashXPathHoriz) {
 273       y = splashFloor(seg->y0);
 274       if (y >= yMin && y <= yMax) {
 275         if (!addIntersection(segYMin, segYMax, seg->flags,
 276                         y, splashFloor(seg->x0), splashFloor(seg->x1)))
 277           break;
 278       }
 279     } else if (seg->flags & splashXPathVert) {
 280       y0 = splashFloor(segYMin);
 281       if (y0 < yMin) {
 282         y0 = yMin;
 283       }
 284       y1 = splashFloor(segYMax);
 285       if (y1 > yMax) {
 286         y1 = yMax;
 287       }
 288       x = splashFloor(seg->x0);
 289       for (y = y0; y <= y1; ++y) {
 290         if (!addIntersection(segYMin, segYMax, seg->flags, y, x, x))
 291           break;
 292       }
 293     } else {
 294       if (seg->x0 < seg->x1) {
 295         segXMin = seg->x0;
 296         segXMax = seg->x1;
 297       } else {
 298         segXMin = seg->x1;
 299         segXMax = seg->x0;
 300       }
 301       y0 = splashFloor(segYMin);
 302       if (y0 < yMin) {
 303         y0 = yMin;
 304       }
 305       y1 = splashFloor(segYMax);
 306       if (y1 > yMax) {
 307         y1 = yMax;
 308       }
 309       // this loop could just add seg->dxdy to xx1 on each iteration,
 310       // but that introduces numerical accuracy problems
 311       xx1 = seg->x0 + ((SplashCoord)y0 - seg->y0) * seg->dxdy;
 312       for (y = y0; y <= y1; ++y) {
 313         xx0 = xx1;
 314         xx1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
 315         // the segment may not actually extend to the top and/or bottom edges
 316         if (xx0 < segXMin) {
 317           xx0 = segXMin;
 318         } else if (xx0 > segXMax) {
 319           xx0 = segXMax;
 320         }
 321         if (xx1 < segXMin) {
 322           xx1 = segXMin;
 323         } else if (xx1 > segXMax) {
 324           xx1 = segXMax;
 325         }
 326         if (!addIntersection(segYMin, segYMax, seg->flags, y,
 327                         splashFloor(xx0), splashFloor(xx1)))
 328           break;
 329       }
 330     }
 331   }
 332   std::sort(allInter, allInter + allInterLen, cmpIntersectFunctor());
 333
 334   // build the list of y pointers
 335   inter = (int *)gmallocn(yMax - yMin + 2, sizeof(int));
 336   i = 0;
 337   for (y = yMin; y <= yMax; ++y) {
 338     inter[y - yMin] = i;
 339     while (i < allInterLen && allInter[i].y <= y) {
 340       ++i;
 341     }
 342   }
 343   inter[yMax - yMin + 1] = i;
 344 }
 345
 346 GBool SplashXPathScanner::addIntersection(double segYMin, double segYMax,
 347                                          Guint segFlags,
 348                                          int y, int x0, int x1) {
 349   if (allInterLen == allInterSize) {
 350     unsigned int newInterSize = ((unsigned int) allInterSize * 2 > INT_MAX / sizeof(SplashIntersect)) ? allInterSize + 32768 : allInterSize * 2;
 351     if (newInterSize >= INT_MAX / sizeof(SplashIntersect)) {
 352       error(errInternal, -1, "Bogus memory allocation size in SplashXPathScanner::addIntersection {0:d}", newInterSize);
 353       return gFalse;
 354     }
 355     allInterSize = newInterSize;
 356     allInter = (SplashIntersect *)greallocn(allInter, newInterSize,
 357                                             sizeof(SplashIntersect));
 358   }
 359   allInter[allInterLen].y = y;
 360   if (x0 < x1) {
 361     allInter[allInterLen].x0 = x0;
 362     allInter[allInterLen].x1 = x1;
 363   } else {
 364     allInter[allInterLen].x0 = x1;
 365     allInter[allInterLen].x1 = x0;
 366   }
 367   if (segYMin <= y &&
 368       (SplashCoord)y < segYMax &&
 369       !(segFlags & splashXPathHoriz)) {
 370     allInter[allInterLen].count = eo ? 1
 371                                      : (segFlags & splashXPathFlip) ? 1 : -1;
 372   } else {
 373     allInter[allInterLen].count = 0;
 374   }
 375   ++allInterLen;
 376   return gTrue;
 377 }
 378
 379 void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
 380                                       int *x0, int *x1, int y, GBool adjustVertLine) {
 381   int xx0, xx1, xx, xxMin, xxMax, yy, interEnd;
 382   Guchar mask;
 383   SplashColorPtr p;
 384
 385   memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
 386   xxMin = aaBuf->getWidth();
 387   xxMax = -1;
 388   if (yMin <= yMax) {
 389     if (splashAASize * y < yMin) {
 390       interIdx = inter[0];
 391     } else if (splashAASize * y > yMax) {
 392       interIdx = inter[yMax - yMin + 1];
 393     } else {
 394       interIdx = inter[splashAASize * y - yMin];
 395     }
 396     for (yy = 0; yy < splashAASize; ++yy) {
 397       if (splashAASize * y + yy < yMin) {
 398         interEnd = inter[0];
 399       } else if (splashAASize * y + yy > yMax) {
 400         interEnd = inter[yMax - yMin + 1];
 401       } else {
 402         interEnd = inter[splashAASize * y + yy - yMin + 1];
 403       }
 404       interCount = 0;
 405       while (interIdx < interEnd) {
 406         xx0 = allInter[interIdx].x0;
 407         xx1 = allInter[interIdx].x1;
 408         interCount += allInter[interIdx].count;
 409         ++interIdx;
 410         while (interIdx < interEnd &&
 411                (allInter[interIdx].x0 <= xx1 ||
 412                 (eo ? (interCount & 1) : (interCount != 0)))) {
 413           if (allInter[interIdx].x1 > xx1) {
 414             xx1 = allInter[interIdx].x1;
 415           }
 416           interCount += allInter[interIdx].count;
 417           ++interIdx;
 418         }
 419         if (xx0 < 0) {
 420           xx0 = 0;
 421         }
 422         ++xx1;
 423         if (xx1 > aaBuf->getWidth()) {
 424           xx1 = aaBuf->getWidth();
 425         }
 426         // set [xx0, xx1) to 1
 427         if (xx0 < xx1) {
 428           xx = xx0;
 429           p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 430           if (xx & 7) {
 431             mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
 432             if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
 433               mask &= (Guchar)(0xff00 >> (xx1 & 7));
 434             }
 435             *p++ |= mask;
 436             xx = (xx & ~7) + 8;
 437           }
 438           for (; xx + 7 < xx1; xx += 8) {
 439             *p++ |= 0xff;
 440           }
 441           if (xx < xx1) {
 442             *p |= adjustVertLine ? 0xff : (Guchar)(0xff00 >> (xx1 & 7));
 443           }
 444         }
 445         if (xx0 < xxMin) {
 446           xxMin = xx0;
 447         }
 448         if (xx1 > xxMax) {
 449           xxMax = xx1;
 450         }
 451       }
 452     }
 453   }
 454   if (xxMin > xxMax) {
 455     xxMin = xxMax;
 456   }
 457   *x0 = xxMin / splashAASize;
 458   *x1 = (xxMax - 1) / splashAASize;
 459 }
 460
 461 void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
 462                                     int *x0, int *x1, int y) {
 463   int xx0, xx1, xx, yy, interEnd;
 464   Guchar mask;
 465   SplashColorPtr p;
 466
 467   for (yy = 0; yy < splashAASize; ++yy) {
 468     xx = *x0 * splashAASize;
 469     if (yMin <= yMax) {
 470       if (splashAASize * y + yy < yMin) {
 471         interIdx = interEnd = inter[0];
 472       } else if (splashAASize * y + yy > yMax) {
 473         interIdx = interEnd = inter[yMax - yMin + 1];
 474       } else {
 475         interIdx = inter[splashAASize * y + yy - yMin];
 476         if (splashAASize * y + yy > yMax) {
 477           interEnd = inter[yMax - yMin + 1];
 478         } else {
 479           interEnd = inter[splashAASize * y + yy - yMin + 1];
 480         }
 481       }
 482       interCount = 0;
 483       while (interIdx < interEnd && xx < (*x1 + 1) * splashAASize) {
 484         xx0 = allInter[interIdx].x0;
 485         xx1 = allInter[interIdx].x1;
 486         interCount += allInter[interIdx].count;
 487         ++interIdx;
 488         while (interIdx < interEnd &&
 489                (allInter[interIdx].x0 <= xx1 ||
 490                 (eo ? (interCount & 1) : (interCount != 0)))) {
 491           if (allInter[interIdx].x1 > xx1) {
 492             xx1 = allInter[interIdx].x1;
 493           }
 494           interCount += allInter[interIdx].count;
 495           ++interIdx;
 496         }
 497         if (xx0 > aaBuf->getWidth()) {
 498           xx0 = aaBuf->getWidth();
 499         }
 500         // set [xx, xx0) to 0
 501         if (xx < xx0) {
 502           p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 503           if (xx & 7) {
 504             mask = (Guchar)(0xff00 >> (xx & 7));
 505             if ((xx & ~7) == (xx0 & ~7)) {
 506               mask |= 0xff >> (xx0 & 7);
 507             }
 508             *p++ &= mask;
 509             xx = (xx & ~7) + 8;
 510           }
 511           for (; xx + 7 < xx0; xx += 8) {
 512             *p++ = 0x00;
 513           }
 514           if (xx < xx0) {
 515             *p &= 0xff >> (xx0 & 7);
 516           }
 517         }
 518         if (xx1 >= xx) {
 519           xx = xx1 + 1;
 520         }
 521       }
 522     }
 523     xx0 = (*x1 + 1) * splashAASize;
 524     if (xx0 > aaBuf->getWidth()) xx0 = aaBuf->getWidth();
 525     // set [xx, xx0) to 0
 526     if (xx < xx0 && xx >= 0) {
 527       p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 528       if (xx & 7) {
 529         mask = (Guchar)(0xff00 >> (xx & 7));
 530         if ((xx & ~7) == (xx0 & ~7)) {
 531           mask &= 0xff >> (xx0 & 7);
 532         }
 533         *p++ &= mask;
 534         xx = (xx & ~7) + 8;
 535       }
 536       for (; xx + 7 < xx0; xx += 8) {
 537         *p++ = 0x00;
 538       }
 539       if (xx < xx0) {
 540         *p &= 0xff >> (xx0 & 7);
 541       }
 542     }
 543   }
 544 }