← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/poppler/splash/SplashXPathScanner.cc

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

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