1/*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkBuffer.h"
9#include "SkLazyPtr.h"
10#include "SkPath.h"
11#include "SkPathRef.h"
12
13//////////////////////////////////////////////////////////////////////////////
14SkPathRef::Editor::Editor(SkAutoTUnref<SkPathRef>* pathRef,
15                          int incReserveVerbs,
16                          int incReservePoints)
17{
18    if ((*pathRef)->unique()) {
19        (*pathRef)->incReserve(incReserveVerbs, incReservePoints);
20    } else {
21        SkPathRef* copy = SkNEW(SkPathRef);
22        copy->copy(**pathRef, incReserveVerbs, incReservePoints);
23        pathRef->reset(copy);
24    }
25    fPathRef = *pathRef;
26    fPathRef->fGenerationID = 0;
27    SkDEBUGCODE(sk_atomic_inc(&fPathRef->fEditorsAttached);)
28}
29
30//////////////////////////////////////////////////////////////////////////////
31
32SkPathRef* SkPathRef::CreateEmptyImpl() {
33    SkPathRef* empty = SkNEW(SkPathRef);
34    empty->computeBounds();   // Avoids races later to be the first to do this.
35    return empty;
36}
37
38SkPathRef* SkPathRef::CreateEmpty() {
39    SK_DECLARE_STATIC_LAZY_PTR(SkPathRef, empty, CreateEmptyImpl);
40    return SkRef(empty.get());
41}
42
43void SkPathRef::CreateTransformedCopy(SkAutoTUnref<SkPathRef>* dst,
44                                      const SkPathRef& src,
45                                      const SkMatrix& matrix) {
46    SkDEBUGCODE(src.validate();)
47    if (matrix.isIdentity()) {
48        if (*dst != &src) {
49            src.ref();
50            dst->reset(const_cast<SkPathRef*>(&src));
51            SkDEBUGCODE((*dst)->validate();)
52        }
53        return;
54    }
55
56    if (!(*dst)->unique()) {
57        dst->reset(SkNEW(SkPathRef));
58    }
59
60    if (*dst != &src) {
61        (*dst)->resetToSize(src.fVerbCnt, src.fPointCnt, src.fConicWeights.count());
62        memcpy((*dst)->verbsMemWritable(), src.verbsMemBegin(), src.fVerbCnt * sizeof(uint8_t));
63        (*dst)->fConicWeights = src.fConicWeights;
64    }
65
66    SkASSERT((*dst)->countPoints() == src.countPoints());
67    SkASSERT((*dst)->countVerbs() == src.countVerbs());
68    SkASSERT((*dst)->fConicWeights.count() == src.fConicWeights.count());
69
70    // Need to check this here in case (&src == dst)
71    bool canXformBounds = !src.fBoundsIsDirty && matrix.rectStaysRect() && src.countPoints() > 1;
72
73    matrix.mapPoints((*dst)->fPoints, src.points(), src.fPointCnt);
74
75    /*
76        *  Here we optimize the bounds computation, by noting if the bounds are
77        *  already known, and if so, we just transform those as well and mark
78        *  them as "known", rather than force the transformed path to have to
79        *  recompute them.
80        *
81        *  Special gotchas if the path is effectively empty (<= 1 point) or
82        *  if it is non-finite. In those cases bounds need to stay empty,
83        *  regardless of the matrix.
84        */
85    if (canXformBounds) {
86        (*dst)->fBoundsIsDirty = false;
87        if (src.fIsFinite) {
88            matrix.mapRect((*dst)->fBounds.get(), src.fBounds);
89            if (!((*dst)->fIsFinite = (*dst)->fBounds->isFinite())) {
90                (*dst)->fBounds->setEmpty();
91            }
92        } else {
93            (*dst)->fIsFinite = false;
94            (*dst)->fBounds->setEmpty();
95        }
96    } else {
97        (*dst)->fBoundsIsDirty = true;
98    }
99
100    (*dst)->fSegmentMask = src.fSegmentMask;
101
102    // It's an oval only if it stays a rect.
103    (*dst)->fIsOval = src.fIsOval && matrix.rectStaysRect();
104
105    SkDEBUGCODE((*dst)->validate();)
106}
107
108SkPathRef* SkPathRef::CreateFromBuffer(SkRBuffer* buffer) {
109    SkPathRef* ref = SkNEW(SkPathRef);
110    bool isOval;
111    uint8_t segmentMask;
112
113    int32_t packed;
114    if (!buffer->readS32(&packed)) {
115        SkDELETE(ref);
116        return NULL;
117    }
118
119    ref->fIsFinite = (packed >> kIsFinite_SerializationShift) & 1;
120    segmentMask = (packed >> kSegmentMask_SerializationShift) & 0xF;
121    isOval  = (packed >> kIsOval_SerializationShift) & 1;
122
123    int32_t verbCount, pointCount, conicCount;
124    if (!buffer->readU32(&(ref->fGenerationID)) ||
125        !buffer->readS32(&verbCount) ||
126        !buffer->readS32(&pointCount) ||
127        !buffer->readS32(&conicCount)) {
128        SkDELETE(ref);
129        return NULL;
130    }
131
132    ref->resetToSize(verbCount, pointCount, conicCount);
133    SkASSERT(verbCount == ref->countVerbs());
134    SkASSERT(pointCount == ref->countPoints());
135    SkASSERT(conicCount == ref->fConicWeights.count());
136
137    if (!buffer->read(ref->verbsMemWritable(), verbCount * sizeof(uint8_t)) ||
138        !buffer->read(ref->fPoints, pointCount * sizeof(SkPoint)) ||
139        !buffer->read(ref->fConicWeights.begin(), conicCount * sizeof(SkScalar)) ||
140        !buffer->read(&ref->fBounds, sizeof(SkRect))) {
141        SkDELETE(ref);
142        return NULL;
143    }
144    ref->fBoundsIsDirty = false;
145
146    // resetToSize clears fSegmentMask and fIsOval
147    ref->fSegmentMask = segmentMask;
148    ref->fIsOval = isOval;
149    return ref;
150}
151
152void SkPathRef::Rewind(SkAutoTUnref<SkPathRef>* pathRef) {
153    if ((*pathRef)->unique()) {
154        SkDEBUGCODE((*pathRef)->validate();)
155        (*pathRef)->fBoundsIsDirty = true;  // this also invalidates fIsFinite
156        (*pathRef)->fVerbCnt = 0;
157        (*pathRef)->fPointCnt = 0;
158        (*pathRef)->fFreeSpace = (*pathRef)->currSize();
159        (*pathRef)->fGenerationID = 0;
160        (*pathRef)->fConicWeights.rewind();
161        (*pathRef)->fSegmentMask = 0;
162        (*pathRef)->fIsOval = false;
163        SkDEBUGCODE((*pathRef)->validate();)
164    } else {
165        int oldVCnt = (*pathRef)->countVerbs();
166        int oldPCnt = (*pathRef)->countPoints();
167        pathRef->reset(SkNEW(SkPathRef));
168        (*pathRef)->resetToSize(0, 0, 0, oldVCnt, oldPCnt);
169    }
170}
171
172bool SkPathRef::operator== (const SkPathRef& ref) const {
173    SkDEBUGCODE(this->validate();)
174    SkDEBUGCODE(ref.validate();)
175
176    // We explicitly check fSegmentMask as a quick-reject. We could skip it,
177    // since it is only a cache of info in the fVerbs, but its a fast way to
178    // notice a difference
179    if (fSegmentMask != ref.fSegmentMask) {
180        return false;
181    }
182
183    bool genIDMatch = fGenerationID && fGenerationID == ref.fGenerationID;
184#ifdef SK_RELEASE
185    if (genIDMatch) {
186        return true;
187    }
188#endif
189    if (fPointCnt != ref.fPointCnt ||
190        fVerbCnt != ref.fVerbCnt) {
191        SkASSERT(!genIDMatch);
192        return false;
193    }
194    if (0 != memcmp(this->verbsMemBegin(),
195                    ref.verbsMemBegin(),
196                    ref.fVerbCnt * sizeof(uint8_t))) {
197        SkASSERT(!genIDMatch);
198        return false;
199    }
200    if (0 != memcmp(this->points(),
201                    ref.points(),
202                    ref.fPointCnt * sizeof(SkPoint))) {
203        SkASSERT(!genIDMatch);
204        return false;
205    }
206    if (fConicWeights != ref.fConicWeights) {
207        SkASSERT(!genIDMatch);
208        return false;
209    }
210    // We've done the work to determine that these are equal. If either has a zero genID, copy
211    // the other's. If both are 0 then genID() will compute the next ID.
212    if (0 == fGenerationID) {
213        fGenerationID = ref.genID();
214    } else if (0 == ref.fGenerationID) {
215        ref.fGenerationID = this->genID();
216    }
217    return true;
218}
219
220void SkPathRef::writeToBuffer(SkWBuffer* buffer) const {
221    SkDEBUGCODE(this->validate();)
222    SkDEBUGCODE(size_t beforePos = buffer->pos();)
223
224    // Call getBounds() to ensure (as a side-effect) that fBounds
225    // and fIsFinite are computed.
226    const SkRect& bounds = this->getBounds();
227
228    int32_t packed = ((fIsFinite & 1) << kIsFinite_SerializationShift) |
229                     ((fIsOval & 1) << kIsOval_SerializationShift) |
230                     (fSegmentMask << kSegmentMask_SerializationShift);
231    buffer->write32(packed);
232
233    // TODO: write gen ID here. Problem: We don't know if we're cross process or not from
234    // SkWBuffer. Until this is fixed we write 0.
235    buffer->write32(0);
236    buffer->write32(fVerbCnt);
237    buffer->write32(fPointCnt);
238    buffer->write32(fConicWeights.count());
239    buffer->write(verbsMemBegin(), fVerbCnt * sizeof(uint8_t));
240    buffer->write(fPoints, fPointCnt * sizeof(SkPoint));
241    buffer->write(fConicWeights.begin(), fConicWeights.bytes());
242    buffer->write(&bounds, sizeof(bounds));
243
244    SkASSERT(buffer->pos() - beforePos == (size_t) this->writeSize());
245}
246
247uint32_t SkPathRef::writeSize() const {
248    return uint32_t(5 * sizeof(uint32_t) +
249                    fVerbCnt * sizeof(uint8_t) +
250                    fPointCnt * sizeof(SkPoint) +
251                    fConicWeights.bytes() +
252                    sizeof(SkRect));
253}
254
255void SkPathRef::copy(const SkPathRef& ref,
256                     int additionalReserveVerbs,
257                     int additionalReservePoints) {
258    SkDEBUGCODE(this->validate();)
259    this->resetToSize(ref.fVerbCnt, ref.fPointCnt, ref.fConicWeights.count(),
260                        additionalReserveVerbs, additionalReservePoints);
261    memcpy(this->verbsMemWritable(), ref.verbsMemBegin(), ref.fVerbCnt * sizeof(uint8_t));
262    memcpy(this->fPoints, ref.fPoints, ref.fPointCnt * sizeof(SkPoint));
263    fConicWeights = ref.fConicWeights;
264    // We could call genID() here to force a real ID (instead of 0). However, if we're making
265    // a copy then presumably we intend to make a modification immediately afterwards.
266    fGenerationID = ref.fGenerationID;
267    fBoundsIsDirty = ref.fBoundsIsDirty;
268    if (!fBoundsIsDirty) {
269        fBounds = ref.fBounds;
270        fIsFinite = ref.fIsFinite;
271    }
272    fSegmentMask = ref.fSegmentMask;
273    fIsOval = ref.fIsOval;
274    SkDEBUGCODE(this->validate();)
275}
276
277SkPoint* SkPathRef::growForRepeatedVerb(int /*SkPath::Verb*/ verb,
278                                        int numVbs,
279                                        SkScalar** weights) {
280    // This value is just made-up for now. When count is 4, calling memset was much
281    // slower than just writing the loop. This seems odd, and hopefully in the
282    // future this will appear to have been a fluke...
283    static const unsigned int kMIN_COUNT_FOR_MEMSET_TO_BE_FAST = 16;
284
285    SkDEBUGCODE(this->validate();)
286    int pCnt;
287    bool dirtyAfterEdit = true;
288    switch (verb) {
289        case SkPath::kMove_Verb:
290            pCnt = numVbs;
291            dirtyAfterEdit = false;
292            break;
293        case SkPath::kLine_Verb:
294            fSegmentMask |= SkPath::kLine_SegmentMask;
295            pCnt = numVbs;
296            break;
297        case SkPath::kQuad_Verb:
298            fSegmentMask |= SkPath::kQuad_SegmentMask;
299            pCnt = 2 * numVbs;
300            break;
301        case SkPath::kConic_Verb:
302            fSegmentMask |= SkPath::kConic_SegmentMask;
303            pCnt = 2 * numVbs;
304            break;
305        case SkPath::kCubic_Verb:
306            fSegmentMask |= SkPath::kCubic_SegmentMask;
307            pCnt = 3 * numVbs;
308            break;
309        case SkPath::kClose_Verb:
310            SkDEBUGFAIL("growForRepeatedVerb called for kClose_Verb");
311            pCnt = 0;
312            dirtyAfterEdit = false;
313            break;
314        case SkPath::kDone_Verb:
315            SkDEBUGFAIL("growForRepeatedVerb called for kDone");
316            // fall through
317        default:
318            SkDEBUGFAIL("default should not be reached");
319            pCnt = 0;
320            dirtyAfterEdit = false;
321    }
322
323    size_t space = numVbs * sizeof(uint8_t) + pCnt * sizeof (SkPoint);
324    this->makeSpace(space);
325
326    SkPoint* ret = fPoints + fPointCnt;
327    uint8_t* vb = fVerbs - fVerbCnt;
328
329    // cast to unsigned, so if kMIN_COUNT_FOR_MEMSET_TO_BE_FAST is defined to
330    // be 0, the compiler will remove the test/branch entirely.
331    if ((unsigned)numVbs >= kMIN_COUNT_FOR_MEMSET_TO_BE_FAST) {
332        memset(vb - numVbs, verb, numVbs);
333    } else {
334        for (int i = 0; i < numVbs; ++i) {
335            vb[~i] = verb;
336        }
337    }
338
339    fVerbCnt += numVbs;
340    fPointCnt += pCnt;
341    fFreeSpace -= space;
342    fBoundsIsDirty = true;  // this also invalidates fIsFinite
343    if (dirtyAfterEdit) {
344        fIsOval = false;
345    }
346
347    if (SkPath::kConic_Verb == verb) {
348        SkASSERT(weights);
349        *weights = fConicWeights.append(numVbs);
350    }
351
352    SkDEBUGCODE(this->validate();)
353    return ret;
354}
355
356SkPoint* SkPathRef::growForVerb(int /* SkPath::Verb*/ verb, SkScalar weight) {
357    SkDEBUGCODE(this->validate();)
358    int pCnt;
359    bool dirtyAfterEdit = true;
360    switch (verb) {
361        case SkPath::kMove_Verb:
362            pCnt = 1;
363            dirtyAfterEdit = false;
364            break;
365        case SkPath::kLine_Verb:
366            fSegmentMask |= SkPath::kLine_SegmentMask;
367            pCnt = 1;
368            break;
369        case SkPath::kQuad_Verb:
370            fSegmentMask |= SkPath::kQuad_SegmentMask;
371            pCnt = 2;
372            break;
373        case SkPath::kConic_Verb:
374            fSegmentMask |= SkPath::kConic_SegmentMask;
375            pCnt = 2;
376            break;
377        case SkPath::kCubic_Verb:
378            fSegmentMask |= SkPath::kCubic_SegmentMask;
379            pCnt = 3;
380            break;
381        case SkPath::kClose_Verb:
382            pCnt = 0;
383            dirtyAfterEdit = false;
384            break;
385        case SkPath::kDone_Verb:
386            SkDEBUGFAIL("growForVerb called for kDone");
387            // fall through
388        default:
389            SkDEBUGFAIL("default is not reached");
390            dirtyAfterEdit = false;
391            pCnt = 0;
392    }
393    size_t space = sizeof(uint8_t) + pCnt * sizeof (SkPoint);
394    this->makeSpace(space);
395    this->fVerbs[~fVerbCnt] = verb;
396    SkPoint* ret = fPoints + fPointCnt;
397    fVerbCnt += 1;
398    fPointCnt += pCnt;
399    fFreeSpace -= space;
400    fBoundsIsDirty = true;  // this also invalidates fIsFinite
401    if (dirtyAfterEdit) {
402        fIsOval = false;
403    }
404
405    if (SkPath::kConic_Verb == verb) {
406        *fConicWeights.append() = weight;
407    }
408
409    SkDEBUGCODE(this->validate();)
410    return ret;
411}
412
413uint32_t SkPathRef::genID() const {
414    SkASSERT(!fEditorsAttached);
415    static const uint32_t kMask = (static_cast<int64_t>(1) << SkPath::kPathRefGenIDBitCnt) - 1;
416    if (!fGenerationID) {
417        if (0 == fPointCnt && 0 == fVerbCnt) {
418            fGenerationID = kEmptyGenID;
419        } else {
420            static int32_t  gPathRefGenerationID;
421            // do a loop in case our global wraps around, as we never want to return a 0 or the
422            // empty ID
423            do {
424                fGenerationID = (sk_atomic_inc(&gPathRefGenerationID) + 1) & kMask;
425            } while (fGenerationID <= kEmptyGenID);
426        }
427    }
428    return fGenerationID;
429}
430
431#ifdef SK_DEBUG
432void SkPathRef::validate() const {
433    this->INHERITED::validate();
434    SkASSERT(static_cast<ptrdiff_t>(fFreeSpace) >= 0);
435    SkASSERT(reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints) >= 0);
436    SkASSERT((NULL == fPoints) == (NULL == fVerbs));
437    SkASSERT(!(NULL == fPoints && 0 != fFreeSpace));
438    SkASSERT(!(NULL == fPoints && 0 != fFreeSpace));
439    SkASSERT(!(NULL == fPoints && fPointCnt));
440    SkASSERT(!(NULL == fVerbs && fVerbCnt));
441    SkASSERT(this->currSize() ==
442                fFreeSpace + sizeof(SkPoint) * fPointCnt + sizeof(uint8_t) * fVerbCnt);
443
444    if (!fBoundsIsDirty && !fBounds->isEmpty()) {
445        bool isFinite = true;
446        for (int i = 0; i < fPointCnt; ++i) {
447            SkASSERT(!fPoints[i].isFinite() || (
448                     fBounds->fLeft - fPoints[i].fX   < SK_ScalarNearlyZero &&
449                     fPoints[i].fX - fBounds->fRight  < SK_ScalarNearlyZero &&
450                     fBounds->fTop  - fPoints[i].fY   < SK_ScalarNearlyZero &&
451                     fPoints[i].fY - fBounds->fBottom < SK_ScalarNearlyZero));
452            if (!fPoints[i].isFinite()) {
453                isFinite = false;
454            }
455        }
456        SkASSERT(SkToBool(fIsFinite) == isFinite);
457    }
458
459#ifdef SK_DEBUG_PATH
460    uint32_t mask = 0;
461    for (int i = 0; i < fVerbCnt; ++i) {
462        switch (fVerbs[~i]) {
463            case SkPath::kMove_Verb:
464                break;
465            case SkPath::kLine_Verb:
466                mask |= SkPath::kLine_SegmentMask;
467                break;
468            case SkPath::kQuad_Verb:
469                mask |= SkPath::kQuad_SegmentMask;
470                break;
471            case SkPath::kConic_Verb:
472                mask |= SkPath::kConic_SegmentMask;
473                break;
474            case SkPath::kCubic_Verb:
475                mask |= SkPath::kCubic_SegmentMask;
476                break;
477            case SkPath::kClose_Verb:
478                break;
479            case SkPath::kDone_Verb:
480                SkDEBUGFAIL("Done verb shouldn't be recorded.");
481                break;
482            default:
483                SkDEBUGFAIL("Unknown Verb");
484                break;
485        }
486    }
487    SkASSERT(mask == fSegmentMask);
488#endif // SK_DEBUG_PATH
489}
490#endif
491