The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkRegion_path.cpp

gfx/skia/trunk/src/core/SkRegion_path.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:5b83c2413162
1
2 /*
3 * Copyright 2006 The Android Open Source Project
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10 #include "SkRegionPriv.h"
11 #include "SkBlitter.h"
12 #include "SkScan.h"
13 #include "SkTDArray.h"
14 #include "SkPath.h"
15
16 class SkRgnBuilder : public SkBlitter {
17 public:
18 SkRgnBuilder();
19 virtual ~SkRgnBuilder();
20
21 // returns true if it could allocate the working storage needed
22 bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
23
24 void done() {
25 if (fCurrScanline != NULL) {
26 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
27 if (!this->collapsWithPrev()) { // flush the last line
28 fCurrScanline = fCurrScanline->nextScanline();
29 }
30 }
31 }
32
33 int computeRunCount() const;
34 void copyToRect(SkIRect*) const;
35 void copyToRgn(SkRegion::RunType runs[]) const;
36
37 virtual void blitH(int x, int y, int width);
38
39 #ifdef SK_DEBUG
40 void dump() const {
41 SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
42 const Scanline* line = (Scanline*)fStorage;
43 while (line < fCurrScanline) {
44 SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
45 for (int i = 0; i < line->fXCount; i++) {
46 SkDebugf(" %d", line->firstX()[i]);
47 }
48 SkDebugf("\n");
49
50 line = line->nextScanline();
51 }
52 }
53 #endif
54 private:
55 /*
56 * Scanline mimics a row in the region, nearly. A row in a region is:
57 * [Bottom IntervalCount [L R]... Sentinel]
58 * while a Scanline is
59 * [LastY XCount [L R]... uninitialized]
60 * The two are the same length (which is good), but we have to transmute
61 * the scanline a little when we convert it to a region-row.
62 *
63 * Potentially we could recode this to exactly match the row format, in
64 * which case copyToRgn() could be a single memcpy. Not sure that is worth
65 * the effort.
66 */
67 struct Scanline {
68 SkRegion::RunType fLastY;
69 SkRegion::RunType fXCount;
70
71 SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
72 Scanline* nextScanline() const {
73 // add final +1 for the x-sentinel
74 return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
75 }
76 };
77 SkRegion::RunType* fStorage;
78 Scanline* fCurrScanline;
79 Scanline* fPrevScanline;
80 // points at next avialable x[] in fCurrScanline
81 SkRegion::RunType* fCurrXPtr;
82 SkRegion::RunType fTop; // first Y value
83
84 int fStorageCount;
85
86 bool collapsWithPrev() {
87 if (fPrevScanline != NULL &&
88 fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
89 fPrevScanline->fXCount == fCurrScanline->fXCount &&
90 !memcmp(fPrevScanline->firstX(),
91 fCurrScanline->firstX(),
92 fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
93 {
94 // update the height of fPrevScanline
95 fPrevScanline->fLastY = fCurrScanline->fLastY;
96 return true;
97 }
98 return false;
99 }
100 };
101
102 SkRgnBuilder::SkRgnBuilder()
103 : fStorage(NULL) {
104 }
105
106 SkRgnBuilder::~SkRgnBuilder() {
107 sk_free(fStorage);
108 }
109
110 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
111 if ((maxHeight | maxTransitions) < 0) {
112 return false;
113 }
114
115 if (pathIsInverse) {
116 // allow for additional X transitions to "invert" each scanline
117 // [ L' ... normal transitions ... R' ]
118 //
119 maxTransitions += 2;
120 }
121
122 // compute the count with +1 and +3 slop for the working buffer
123 int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
124
125 if (pathIsInverse) {
126 // allow for two "empty" rows for the top and bottom
127 // [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
128 count += 10;
129 }
130
131 if (count < 0 || !sk_64_isS32(count)) {
132 return false;
133 }
134 fStorageCount = sk_64_asS32(count);
135
136 int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
137 if (size < 0 || !sk_64_isS32(size)) {
138 return false;
139 }
140
141 fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
142 if (NULL == fStorage) {
143 return false;
144 }
145
146 fCurrScanline = NULL; // signal empty collection
147 fPrevScanline = NULL; // signal first scanline
148 return true;
149 }
150
151 void SkRgnBuilder::blitH(int x, int y, int width) {
152 if (fCurrScanline == NULL) { // first time
153 fTop = (SkRegion::RunType)(y);
154 fCurrScanline = (Scanline*)fStorage;
155 fCurrScanline->fLastY = (SkRegion::RunType)(y);
156 fCurrXPtr = fCurrScanline->firstX();
157 } else {
158 SkASSERT(y >= fCurrScanline->fLastY);
159
160 if (y > fCurrScanline->fLastY) {
161 // if we get here, we're done with fCurrScanline
162 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
163
164 int prevLastY = fCurrScanline->fLastY;
165 if (!this->collapsWithPrev()) {
166 fPrevScanline = fCurrScanline;
167 fCurrScanline = fCurrScanline->nextScanline();
168
169 }
170 if (y - 1 > prevLastY) { // insert empty run
171 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
172 fCurrScanline->fXCount = 0;
173 fCurrScanline = fCurrScanline->nextScanline();
174 }
175 // setup for the new curr line
176 fCurrScanline->fLastY = (SkRegion::RunType)(y);
177 fCurrXPtr = fCurrScanline->firstX();
178 }
179 }
180 // check if we should extend the current run, or add a new one
181 if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
182 fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
183 } else {
184 fCurrXPtr[0] = (SkRegion::RunType)(x);
185 fCurrXPtr[1] = (SkRegion::RunType)(x + width);
186 fCurrXPtr += 2;
187 }
188 SkASSERT(fCurrXPtr - fStorage < fStorageCount);
189 }
190
191 int SkRgnBuilder::computeRunCount() const {
192 if (fCurrScanline == NULL) {
193 return 0;
194 }
195
196 const SkRegion::RunType* line = fStorage;
197 const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
198
199 return 2 + (int)(stop - line);
200 }
201
202 void SkRgnBuilder::copyToRect(SkIRect* r) const {
203 SkASSERT(fCurrScanline != NULL);
204 // A rect's scanline is [bottom intervals left right sentinel] == 5
205 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
206
207 const Scanline* line = (const Scanline*)fStorage;
208 SkASSERT(line->fXCount == 2);
209
210 r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
211 }
212
213 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
214 SkASSERT(fCurrScanline != NULL);
215 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
216
217 const Scanline* line = (const Scanline*)fStorage;
218 const Scanline* stop = fCurrScanline;
219
220 *runs++ = fTop;
221 do {
222 *runs++ = (SkRegion::RunType)(line->fLastY + 1);
223 int count = line->fXCount;
224 *runs++ = count >> 1; // intervalCount
225 if (count) {
226 memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
227 runs += count;
228 }
229 *runs++ = SkRegion::kRunTypeSentinel;
230 line = line->nextScanline();
231 } while (line < stop);
232 SkASSERT(line == stop);
233 *runs = SkRegion::kRunTypeSentinel;
234 }
235
236 static unsigned verb_to_initial_last_index(unsigned verb) {
237 static const uint8_t gPathVerbToInitialLastIndex[] = {
238 0, // kMove_Verb
239 1, // kLine_Verb
240 2, // kQuad_Verb
241 2, // kConic_Verb
242 3, // kCubic_Verb
243 0, // kClose_Verb
244 0 // kDone_Verb
245 };
246 SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
247 return gPathVerbToInitialLastIndex[verb];
248 }
249
250 static unsigned verb_to_max_edges(unsigned verb) {
251 static const uint8_t gPathVerbToMaxEdges[] = {
252 0, // kMove_Verb
253 1, // kLine_Verb
254 2, // kQuad_VerbB
255 2, // kConic_VerbB
256 3, // kCubic_Verb
257 0, // kClose_Verb
258 0 // kDone_Verb
259 };
260 SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
261 return gPathVerbToMaxEdges[verb];
262 }
263
264
265 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
266 SkPath::Iter iter(path, true);
267 SkPoint pts[4];
268 SkPath::Verb verb;
269
270 int maxEdges = 0;
271 SkScalar top = SkIntToScalar(SK_MaxS16);
272 SkScalar bot = SkIntToScalar(SK_MinS16);
273
274 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
275 maxEdges += verb_to_max_edges(verb);
276
277 int lastIndex = verb_to_initial_last_index(verb);
278 if (lastIndex > 0) {
279 for (int i = 1; i <= lastIndex; i++) {
280 if (top > pts[i].fY) {
281 top = pts[i].fY;
282 } else if (bot < pts[i].fY) {
283 bot = pts[i].fY;
284 }
285 }
286 } else if (SkPath::kMove_Verb == verb) {
287 if (top > pts[0].fY) {
288 top = pts[0].fY;
289 } else if (bot < pts[0].fY) {
290 bot = pts[0].fY;
291 }
292 }
293 }
294 SkASSERT(top <= bot);
295
296 *itop = SkScalarRoundToInt(top);
297 *ibot = SkScalarRoundToInt(bot);
298 return maxEdges;
299 }
300
301 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
302 SkDEBUGCODE(this->validate();)
303
304 if (clip.isEmpty()) {
305 return this->setEmpty();
306 }
307
308 if (path.isEmpty()) {
309 if (path.isInverseFillType()) {
310 return this->set(clip);
311 } else {
312 return this->setEmpty();
313 }
314 }
315
316 // compute worst-case rgn-size for the path
317 int pathTop, pathBot;
318 int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
319 int clipTop, clipBot;
320 int clipTransitions;
321
322 clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
323
324 int top = SkMax32(pathTop, clipTop);
325 int bot = SkMin32(pathBot, clipBot);
326
327 if (top >= bot)
328 return this->setEmpty();
329
330 SkRgnBuilder builder;
331
332 if (!builder.init(bot - top,
333 SkMax32(pathTransitions, clipTransitions),
334 path.isInverseFillType())) {
335 // can't allocate working space, so return false
336 return this->setEmpty();
337 }
338
339 SkScan::FillPath(path, clip, &builder);
340 builder.done();
341
342 int count = builder.computeRunCount();
343 if (count == 0) {
344 return this->setEmpty();
345 } else if (count == kRectRegionRuns) {
346 builder.copyToRect(&fBounds);
347 this->setRect(fBounds);
348 } else {
349 SkRegion tmp;
350
351 tmp.fRunHead = RunHead::Alloc(count);
352 builder.copyToRgn(tmp.fRunHead->writable_runs());
353 tmp.fRunHead->computeRunBounds(&tmp.fBounds);
354 this->swap(tmp);
355 }
356 SkDEBUGCODE(this->validate();)
357 return true;
358 }
359
360 /////////////////////////////////////////////////////////////////////////////////////////////////
361 /////////////////////////////////////////////////////////////////////////////////////////////////
362
363 struct Edge {
364 enum {
365 kY0Link = 0x01,
366 kY1Link = 0x02,
367
368 kCompleteLink = (kY0Link | kY1Link)
369 };
370
371 SkRegion::RunType fX;
372 SkRegion::RunType fY0, fY1;
373 uint8_t fFlags;
374 Edge* fNext;
375
376 void set(int x, int y0, int y1) {
377 SkASSERT(y0 != y1);
378
379 fX = (SkRegion::RunType)(x);
380 fY0 = (SkRegion::RunType)(y0);
381 fY1 = (SkRegion::RunType)(y1);
382 fFlags = 0;
383 SkDEBUGCODE(fNext = NULL;)
384 }
385
386 int top() const {
387 return SkFastMin32(fY0, fY1);
388 }
389 };
390
391 static void find_link(Edge* base, Edge* stop) {
392 SkASSERT(base < stop);
393
394 if (base->fFlags == Edge::kCompleteLink) {
395 SkASSERT(base->fNext);
396 return;
397 }
398
399 SkASSERT(base + 1 < stop);
400
401 int y0 = base->fY0;
402 int y1 = base->fY1;
403
404 Edge* e = base;
405 if ((base->fFlags & Edge::kY0Link) == 0) {
406 for (;;) {
407 e += 1;
408 if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
409 SkASSERT(NULL == e->fNext);
410 e->fNext = base;
411 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
412 break;
413 }
414 }
415 }
416
417 e = base;
418 if ((base->fFlags & Edge::kY1Link) == 0) {
419 for (;;) {
420 e += 1;
421 if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
422 SkASSERT(NULL == base->fNext);
423 base->fNext = e;
424 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
425 break;
426 }
427 }
428 }
429
430 base->fFlags = Edge::kCompleteLink;
431 }
432
433 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
434 while (0 == edge->fFlags) {
435 edge++; // skip over "used" edges
436 }
437
438 SkASSERT(edge < stop);
439
440 Edge* base = edge;
441 Edge* prev = edge;
442 edge = edge->fNext;
443 SkASSERT(edge != base);
444
445 int count = 1;
446 path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
447 prev->fFlags = 0;
448 do {
449 if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
450 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
451 path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
452 }
453 prev = edge;
454 edge = edge->fNext;
455 count += 1;
456 prev->fFlags = 0;
457 } while (edge != base);
458 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
459 path->close();
460 return count;
461 }
462
463 #include "SkTSearch.h"
464
465 static int EdgeProc(const Edge* a, const Edge* b) {
466 return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
467 }
468
469 bool SkRegion::getBoundaryPath(SkPath* path) const {
470 // path could safely be NULL if we're empty, but the caller shouldn't
471 // *know* that
472 SkASSERT(path);
473
474 if (this->isEmpty()) {
475 return false;
476 }
477
478 const SkIRect& bounds = this->getBounds();
479
480 if (this->isRect()) {
481 SkRect r;
482 r.set(bounds); // this converts the ints to scalars
483 path->addRect(r);
484 return true;
485 }
486
487 SkRegion::Iterator iter(*this);
488 SkTDArray<Edge> edges;
489
490 for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
491 Edge* edge = edges.append(2);
492 edge[0].set(r.fLeft, r.fBottom, r.fTop);
493 edge[1].set(r.fRight, r.fTop, r.fBottom);
494 }
495 qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
496
497 int count = edges.count();
498 Edge* start = edges.begin();
499 Edge* stop = start + count;
500 Edge* e;
501
502 for (e = start; e != stop; e++) {
503 find_link(e, stop);
504 }
505
506 #ifdef SK_DEBUG
507 for (e = start; e != stop; e++) {
508 SkASSERT(e->fNext != NULL);
509 SkASSERT(e->fFlags == Edge::kCompleteLink);
510 }
511 #endif
512
513 path->incReserve(count << 1);
514 do {
515 SkASSERT(count > 1);
516 count -= extract_path(start, stop, path);
517 } while (count > 0);
518
519 return true;
520 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial