arospdf/splash/SplashXPathScanner.cc

   1 //========================================================================
   2 //
   3 // SplashXPathScanner.cc
   4 //
   5 //========================================================================
   6
   7 #include <aconf.h>
   8
   9 #ifdef USE_GCC_PRAGMAS
  10 #pragma implementation
  11 #endif
  12
  13 #include <stdlib.h>
  14 #include <string.h>
  15 #include "gmem.h"
  16 #include "SplashMath.h"
  17 #include "SplashXPath.h"
  18 #include "SplashBitmap.h"
  19 #include "SplashXPathScanner.h"
  20
  21 //------------------------------------------------------------------------
  22
  23 struct SplashIntersect {
  24   int x0, x1;                   // intersection of segment with [y, y+1)
  25   int count;                    // EO/NZWN counter increment
  26 };
  27
  28 static int cmpIntersect(const void *p0, const void *p1) {
  29   return ((SplashIntersect *)p0)->x0 - ((SplashIntersect *)p1)->x0;
  30 }
  31
  32 //------------------------------------------------------------------------
  33 // SplashXPathScanner
  34 //------------------------------------------------------------------------
  35
  36 SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA) {
  37   SplashXPathSeg *seg;
  38   SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
  39   int i;
  40
  41   xPath = xPathA;
  42   eo = eoA;
  43
  44   // compute the bbox
  45   if (xPath->length == 0) {
  46     xMin = yMin = 1;
  47     xMax = yMax = 0;
  48   } else {
  49     seg = &xPath->segs[0];
  50     if (seg->x0 <= seg->x1) {
  51       xMinFP = seg->x0;
  52       xMaxFP = seg->x1;
  53     } else {
  54       xMinFP = seg->x1;
  55       xMaxFP = seg->x0;
  56     }
  57     if (seg->flags & splashXPathFlip) {
  58       yMinFP = seg->y1;
  59       yMaxFP = seg->y0;
  60     } else {
  61       yMinFP = seg->y0;
  62       yMaxFP = seg->y1;
  63     }
  64     for (i = 1; i < xPath->length; ++i) {
  65       seg = &xPath->segs[i];
  66       if (seg->x0 < xMinFP) {
  67         xMinFP = seg->x0;
  68       } else if (seg->x0 > xMaxFP) {
  69         xMaxFP = seg->x0;
  70       }
  71       if (seg->x1 < xMinFP) {
  72         xMinFP = seg->x1;
  73       } else if (seg->x1 > xMaxFP) {
  74         xMaxFP = seg->x1;
  75       }
  76       if (seg->flags & splashXPathFlip) {
  77         if (seg->y0 > yMaxFP) {
  78           yMaxFP = seg->y0;
  79         }
  80       } else {
  81         if (seg->y1 > yMaxFP) {
  82           yMaxFP = seg->y1;
  83         }
  84       }
  85     }
  86     xMin = splashFloor(xMinFP);
  87     xMax = splashFloor(xMaxFP);
  88     yMin = splashFloor(yMinFP);
  89     yMax = splashFloor(yMaxFP);
  90   }
  91
  92   interY = yMin - 1;
  93   xPathIdx = 0;
  94   inter = NULL;
  95   interLen = interSize = 0;
  96 }
  97
  98 SplashXPathScanner::~SplashXPathScanner() {
  99   gfree(inter);
 100 }
 101
 102 void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA,
 103                                    int *xMaxA, int *yMaxA) {
 104   *xMinA = xMin / splashAASize;
 105   *yMinA = yMin / splashAASize;
 106   *xMaxA = xMax / splashAASize;
 107   *yMaxA = yMax / splashAASize;
 108 }
 109
 110 void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
 111   if (interY != y) {
 112     computeIntersections(y);
 113   }
 114   if (interLen > 0) {
 115     *spanXMin = inter[0].x0;
 116     *spanXMax = inter[interLen - 1].x1;
 117   } else {
 118     *spanXMin = xMax + 1;
 119     *spanXMax = xMax;
 120   }
 121 }
 122
 123 GBool SplashXPathScanner::test(int x, int y) {
 124   int count, i;
 125
 126   if (interY != y) {
 127     computeIntersections(y);
 128   }
 129   count = 0;
 130   for (i = 0; i < interLen && inter[i].x0 <= x; ++i) {
 131     if (x <= inter[i].x1) {
 132       return gTrue;
 133     }
 134     count += inter[i].count;
 135   }
 136   return eo ? (count & 1) : (count != 0);
 137 }
 138
 139 GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
 140   int count, xx1, i;
 141
 142   if (interY != y) {
 143     computeIntersections(y);
 144   }
 145
 146   count = 0;
 147   for (i = 0; i < interLen && inter[i].x1 < x0; ++i) {
 148     count += inter[i].count;
 149   }
 150
 151   // invariant: the subspan [x0,xx1] is inside the path
 152   xx1 = x0 - 1;
 153   while (xx1 < x1) {
 154     if (i >= interLen) {
 155       return gFalse;
 156     }
 157     if (inter[i].x0 > xx1 + 1 &&
 158         !(eo ? (count & 1) : (count != 0))) {
 159       return gFalse;
 160     }
 161     if (inter[i].x1 > xx1) {
 162       xx1 = inter[i].x1;
 163     }
 164     count += inter[i].count;
 165     ++i;
 166   }
 167
 168   return gTrue;
 169 }
 170
 171 GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
 172   int xx0, xx1;
 173
 174   if (interY != y) {
 175     computeIntersections(y);
 176   }
 177   if (interIdx >= interLen) {
 178     return gFalse;
 179   }
 180   xx0 = inter[interIdx].x0;
 181   xx1 = inter[interIdx].x1;
 182   interCount += inter[interIdx].count;
 183   ++interIdx;
 184   while (interIdx < interLen &&
 185          (inter[interIdx].x0 <= xx1 ||
 186           (eo ? (interCount & 1) : (interCount != 0)))) {
 187     if (inter[interIdx].x1 > xx1) {
 188       xx1 = inter[interIdx].x1;
 189     }
 190     interCount += inter[interIdx].count;
 191     ++interIdx;
 192   }
 193   *x0 = xx0;
 194   *x1 = xx1;
 195   return gTrue;
 196 }
 197
 198 void SplashXPathScanner::computeIntersections(int y) {
 199   SplashCoord xSegMin, xSegMax, ySegMin, ySegMax, xx0, xx1;
 200   SplashXPathSeg *seg;
 201   int i, j;
 202
 203   // find the first segment that intersects [y, y+1)
 204   i = (y >= interY) ? xPathIdx : 0;
 205   while (i < xPath->length &&
 206          xPath->segs[i].y0 < y && xPath->segs[i].y1 < y) {
 207     ++i;
 208   }
 209   xPathIdx = i;
 210
 211   // find all of the segments that intersect [y, y+1) and create an
 212   // Intersect element for each one
 213   interLen = 0;
 214   for (j = i; j < xPath->length; ++j) {
 215     seg = &xPath->segs[j];
 216     if (seg->flags & splashXPathFlip) {
 217       ySegMin = seg->y1;
 218       ySegMax = seg->y0;
 219     } else {
 220       ySegMin = seg->y0;
 221       ySegMax = seg->y1;
 222     }
 223
 224     // ensure that:      ySegMin < y+1
 225     //              y <= ySegMax
 226     if (ySegMin >= y + 1) {
 227       break;
 228     }
 229     if (ySegMax < y) {
 230       continue;
 231     }
 232
 233     if (interLen == interSize) {
 234       if (interSize == 0) {
 235         interSize = 16;
 236       } else {
 237         interSize *= 2;
 238       }
 239       inter = (SplashIntersect *)greallocn(inter, interSize,
 240                                            sizeof(SplashIntersect));
 241     }
 242
 243     if (seg->flags & splashXPathHoriz) {
 244       xx0 = seg->x0;
 245       xx1 = seg->x1;
 246     } else if (seg->flags & splashXPathVert) {
 247       xx0 = xx1 = seg->x0;
 248     } else {
 249       if (seg->x0 < seg->x1) {
 250         xSegMin = seg->x0;
 251         xSegMax = seg->x1;
 252       } else {
 253         xSegMin = seg->x1;
 254         xSegMax = seg->x0;
 255       }
 256       // intersection with top edge
 257       xx0 = seg->x0 + ((SplashCoord)y - seg->y0) * seg->dxdy;
 258       // intersection with bottom edge
 259       xx1 = seg->x0 + ((SplashCoord)y + 1 - seg->y0) * seg->dxdy;
 260       // the segment may not actually extend to the top and/or bottom edges
 261       if (xx0 < xSegMin) {
 262         xx0 = xSegMin;
 263       } else if (xx0 > xSegMax) {
 264         xx0 = xSegMax;
 265       }
 266       if (xx1 < xSegMin) {
 267         xx1 = xSegMin;
 268       } else if (xx1 > xSegMax) {
 269         xx1 = xSegMax;
 270       }
 271     }
 272     if (xx0 < xx1) {
 273       inter[interLen].x0 = splashFloor(xx0);
 274       inter[interLen].x1 = splashFloor(xx1);
 275     } else {
 276       inter[interLen].x0 = splashFloor(xx1);
 277       inter[interLen].x1 = splashFloor(xx0);
 278     }
 279     if (ySegMin <= y &&
 280         (SplashCoord)y < ySegMax &&
 281         !(seg->flags & splashXPathHoriz)) {
 282       inter[interLen].count = eo ? 1
 283                                  : (seg->flags & splashXPathFlip) ? 1 : -1;
 284     } else {
 285       inter[interLen].count = 0;
 286     }
 287     ++interLen;
 288   }
 289
 290   qsort(inter, interLen, sizeof(SplashIntersect), &cmpIntersect);
 291
 292   interY = y;
 293   interIdx = 0;
 294   interCount = 0;
 295 }
 296
 297 void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
 298                                       int *x0, int *x1, int y) {
 299   int xx0, xx1, xx, xxMin, xxMax, yy;
 300   Guchar mask;
 301   SplashColorPtr p;
 302
 303   memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
 304   xxMin = aaBuf->getWidth();
 305   xxMax = -1;
 306   for (yy = 0; yy < splashAASize; ++yy) {
 307     computeIntersections(splashAASize * y + yy);
 308     while (interIdx < interLen) {
 309       xx0 = inter[interIdx].x0;
 310       xx1 = inter[interIdx].x1;
 311       interCount += inter[interIdx].count;
 312       ++interIdx;
 313       while (interIdx < interLen &&
 314              (inter[interIdx].x0 <= xx1 ||
 315               (eo ? (interCount & 1) : (interCount != 0)))) {
 316         if (inter[interIdx].x1 > xx1) {
 317           xx1 = inter[interIdx].x1;
 318         }
 319         interCount += inter[interIdx].count;
 320         ++interIdx;
 321       }
 322       if (xx0 < 0) {
 323         xx0 = 0;
 324       }
 325       ++xx1;
 326       if (xx1 > aaBuf->getWidth()) {
 327         xx1 = aaBuf->getWidth();
 328       }
 329       // set [xx0, xx1) to 1
 330       if (xx0 < xx1) {
 331         xx = xx0;
 332         p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 333         if (xx & 7) {
 334           mask = 0xff >> (xx & 7);
 335           if ((xx & ~7) == (xx1 & ~7)) {
 336             mask &= (Guchar)(0xff00 >> (xx1 & 7));
 337           }
 338           *p++ |= mask;
 339           xx = (xx & ~7) + 8;
 340         }
 341         for (; xx + 7 < xx1; xx += 8) {
 342           *p++ |= 0xff;
 343         }
 344         if (xx < xx1) {
 345           *p |= (Guchar)(0xff00 >> (xx1 & 7));
 346         }
 347       }
 348       if (xx0 < xxMin) {
 349         xxMin = xx0;
 350       }
 351       if (xx1 > xxMax) {
 352         xxMax = xx1;
 353       }
 354     }
 355   }
 356   *x0 = xxMin / splashAASize;
 357   *x1 = (xxMax - 1) / splashAASize;
 358 }
 359
 360 void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
 361                                     int *x0, int *x1, int y) {
 362   int xx0, xx1, xx, yy;
 363   Guchar mask;
 364   SplashColorPtr p;
 365
 366   for (yy = 0; yy < splashAASize; ++yy) {
 367     xx = *x0 * splashAASize;
 368     computeIntersections(splashAASize * y + yy);
 369     while (interIdx < interLen && xx < (*x1 + 1) * splashAASize) {
 370       xx0 = inter[interIdx].x0;
 371       xx1 = inter[interIdx].x1;
 372       interCount += inter[interIdx].count;
 373       ++interIdx;
 374       while (interIdx < interLen &&
 375              (inter[interIdx].x0 <= xx1 ||
 376               (eo ? (interCount & 1) : (interCount != 0)))) {
 377         if (inter[interIdx].x1 > xx1) {
 378           xx1 = inter[interIdx].x1;
 379         }
 380         interCount += inter[interIdx].count;
 381         ++interIdx;
 382       }
 383       if (xx0 > aaBuf->getWidth()) {
 384         xx0 = aaBuf->getWidth();
 385       }
 386       // set [xx, xx0) to 0
 387       if (xx < xx0) {
 388         p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 389         if (xx & 7) {
 390           mask = (Guchar)(0xff00 >> (xx & 7));
 391           if ((xx & ~7) == (xx0 & ~7)) {
 392             mask |= 0xff >> (xx0 & 7);
 393           }
 394           *p++ &= mask;
 395           xx = (xx & ~7) + 8;
 396         }
 397         for (; xx + 7 <= xx0; xx += 8) {
 398           *p++ = 0x00;
 399         }
 400         if (xx <= xx0) {
 401           *p &= 0xff >> (xx0 & 7);
 402         }
 403       }
 404       if (xx1 >= xx) {
 405         xx = xx1 + 1;
 406       }
 407     }
 408     xx0 = (*x1 + 1) * splashAASize;
 409     // set [xx, xx0) to 0
 410     if (xx < xx0) {
 411       p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 412       if (xx & 7) {
 413         mask = (Guchar)(0xff00 >> (xx & 7));
 414         if ((xx & ~7) == (xx0 & ~7)) {
 415           mask &= 0xff >> (xx0 & 7);
 416         }
 417         *p++ &= mask;
 418         xx = (xx & ~7) + 8;
 419       }
 420       for (; xx + 7 <= xx0; xx += 8) {
 421         *p++ = 0x00;
 422       }
 423       if (xx <= xx0) {
 424         *p &= 0xff >> (xx0 & 7);
 425       }
 426     }
 427   }
 428 }