• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2012 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 #ifndef SkPathRef_DEFINED
9 #define SkPathRef_DEFINED
10 
11 #include "SkMatrix.h"
12 #include "SkMutex.h"
13 #include "SkPoint.h"
14 #include "SkRRect.h"
15 #include "SkRect.h"
16 #include "SkRefCnt.h"
17 #include "SkTDArray.h"
18 #include "SkTemplates.h"
19 #include "SkTo.h"
20 #include <atomic>
21 #include <limits>
22 
23 class SkRBuffer;
24 class SkWBuffer;
25 
26 /**
27  * Holds the path verbs and points. It is versioned by a generation ID. None of its public methods
28  * modify the contents. To modify or append to the verbs/points wrap the SkPathRef in an
29  * SkPathRef::Editor object. Installing the editor resets the generation ID. It also performs
30  * copy-on-write if the SkPathRef is shared by multiple SkPaths. The caller passes the Editor's
31  * constructor a pointer to a sk_sp<SkPathRef>, which may be updated to point to a new SkPathRef
32  * after the editor's constructor returns.
33  *
34  * The points and verbs are stored in a single allocation. The points are at the begining of the
35  * allocation while the verbs are stored at end of the allocation, in reverse order. Thus the points
36  * and verbs both grow into the middle of the allocation until the meet. To access verb i in the
37  * verb array use ref.verbs()[~i] (because verbs() returns a pointer just beyond the first
38  * logical verb or the last verb in memory).
39  */
40 
41 class SK_API SkPathRef final : public SkNVRefCnt<SkPathRef> {
42 public:
43     class Editor {
44     public:
45         Editor(sk_sp<SkPathRef>* pathRef,
46                int incReserveVerbs = 0,
47                int incReservePoints = 0);
48 
~Editor()49         ~Editor() { SkDEBUGCODE(fPathRef->fEditorsAttached--;) }
50 
51         /**
52          * Returns the array of points.
53          */
points()54         SkPoint* points() { return fPathRef->getPoints(); }
points()55         const SkPoint* points() const { return fPathRef->points(); }
56 
57         /**
58          * Gets the ith point. Shortcut for this->points() + i
59          */
atPoint(int i)60         SkPoint* atPoint(int i) {
61             SkASSERT((unsigned) i < (unsigned) fPathRef->fPointCnt);
62             return this->points() + i;
63         }
atPoint(int i)64         const SkPoint* atPoint(int i) const {
65             SkASSERT((unsigned) i < (unsigned) fPathRef->fPointCnt);
66             return this->points() + i;
67         }
68 
69         /**
70          * Adds the verb and allocates space for the number of points indicated by the verb. The
71          * return value is a pointer to where the points for the verb should be written.
72          * 'weight' is only used if 'verb' is kConic_Verb
73          */
74         SkPoint* growForVerb(int /*SkPath::Verb*/ verb, SkScalar weight = 0) {
75             SkDEBUGCODE(fPathRef->validate();)
76             return fPathRef->growForVerb(verb, weight);
77         }
78 
79         /**
80          * Allocates space for multiple instances of a particular verb and the
81          * requisite points & weights.
82          * The return pointer points at the first new point (indexed normally [<i>]).
83          * If 'verb' is kConic_Verb, 'weights' will return a pointer to the
84          * space for the conic weights (indexed normally).
85          */
86         SkPoint* growForRepeatedVerb(int /*SkPath::Verb*/ verb,
87                                      int numVbs,
88                                      SkScalar** weights = nullptr) {
89             return fPathRef->growForRepeatedVerb(verb, numVbs, weights);
90         }
91 
92         /**
93          * Resets the path ref to a new verb and point count. The new verbs and points are
94          * uninitialized.
95          */
resetToSize(int newVerbCnt,int newPointCnt,int newConicCount)96         void resetToSize(int newVerbCnt, int newPointCnt, int newConicCount) {
97             fPathRef->resetToSize(newVerbCnt, newPointCnt, newConicCount);
98         }
99 
100         /**
101          * Gets the path ref that is wrapped in the Editor.
102          */
pathRef()103         SkPathRef* pathRef() { return fPathRef; }
104 
setIsOval(bool isOval,bool isCCW,unsigned start)105         void setIsOval(bool isOval, bool isCCW, unsigned start) {
106             fPathRef->setIsOval(isOval, isCCW, start);
107         }
108 
setIsRRect(bool isRRect,bool isCCW,unsigned start)109         void setIsRRect(bool isRRect, bool isCCW, unsigned start) {
110             fPathRef->setIsRRect(isRRect, isCCW, start);
111         }
112 
setBounds(const SkRect & rect)113         void setBounds(const SkRect& rect) { fPathRef->setBounds(rect); }
114 
115     private:
116         SkPathRef* fPathRef;
117     };
118 
119     class SK_API Iter {
120     public:
121         Iter();
122         Iter(const SkPathRef&);
123 
124         void setPathRef(const SkPathRef&);
125 
126         /** Return the next verb in this iteration of the path. When all
127             segments have been visited, return kDone_Verb.
128 
129             If any point in the path is non-finite, return kDone_Verb immediately.
130 
131             @param  pts The points representing the current verb and/or segment
132                         This must not be NULL.
133             @return The verb for the current segment
134         */
135         uint8_t next(SkPoint pts[4]);
136         uint8_t peek() const;
137 
conicWeight()138         SkScalar conicWeight() const { return *fConicWeights; }
139 
140     private:
141         const SkPoint*  fPts;
142         const uint8_t*  fVerbs;
143         const uint8_t*  fVerbStop;
144         const SkScalar* fConicWeights;
145     };
146 
147 public:
148     /**
149      * Gets a path ref with no verbs or points.
150      */
151     static SkPathRef* CreateEmpty();
152 
153     /**
154      *  Returns true if all of the points in this path are finite, meaning there
155      *  are no infinities and no NaNs.
156      */
isFinite()157     bool isFinite() const {
158         if (fBoundsIsDirty) {
159             this->computeBounds();
160         }
161         return SkToBool(fIsFinite);
162     }
163 
164     /**
165      *  Returns a mask, where each bit corresponding to a SegmentMask is
166      *  set if the path contains 1 or more segments of that type.
167      *  Returns 0 for an empty path (no segments).
168      */
getSegmentMasks()169     uint32_t getSegmentMasks() const { return fSegmentMask; }
170 
171     /** Returns true if the path is an oval.
172      *
173      * @param rect      returns the bounding rect of this oval. It's a circle
174      *                  if the height and width are the same.
175      * @param isCCW     is the oval CCW (or CW if false).
176      * @param start     indicates where the contour starts on the oval (see
177      *                  SkPath::addOval for intepretation of the index).
178      *
179      * @return true if this path is an oval.
180      *              Tracking whether a path is an oval is considered an
181      *              optimization for performance and so some paths that are in
182      *              fact ovals can report false.
183      */
isOval(SkRect * rect,bool * isCCW,unsigned * start)184     bool isOval(SkRect* rect, bool* isCCW, unsigned* start) const {
185         if (fIsOval) {
186             if (rect) {
187                 *rect = this->getBounds();
188             }
189             if (isCCW) {
190                 *isCCW = SkToBool(fRRectOrOvalIsCCW);
191             }
192             if (start) {
193                 *start = fRRectOrOvalStartIdx;
194             }
195         }
196 
197         return SkToBool(fIsOval);
198     }
199 
isRRect(SkRRect * rrect,bool * isCCW,unsigned * start)200     bool isRRect(SkRRect* rrect, bool* isCCW, unsigned* start) const {
201         if (fIsRRect) {
202             if (rrect) {
203                 *rrect = this->getRRect();
204             }
205             if (isCCW) {
206                 *isCCW = SkToBool(fRRectOrOvalIsCCW);
207             }
208             if (start) {
209                 *start = fRRectOrOvalStartIdx;
210             }
211         }
212         return SkToBool(fIsRRect);
213     }
214 
215 
hasComputedBounds()216     bool hasComputedBounds() const {
217         return !fBoundsIsDirty;
218     }
219 
220     /** Returns the bounds of the path's points. If the path contains 0 or 1
221         points, the bounds is set to (0,0,0,0), and isEmpty() will return true.
222         Note: this bounds may be larger than the actual shape, since curves
223         do not extend as far as their control points.
224     */
getBounds()225     const SkRect& getBounds() const {
226         if (fBoundsIsDirty) {
227             this->computeBounds();
228         }
229         return fBounds;
230     }
231 
232     SkRRect getRRect() const;
233 
234     /**
235      * Transforms a path ref by a matrix, allocating a new one only if necessary.
236      */
237     static void CreateTransformedCopy(sk_sp<SkPathRef>* dst,
238                                       const SkPathRef& src,
239                                       const SkMatrix& matrix);
240 
241     static SkPathRef* CreateFromBuffer(SkRBuffer* buffer);
242 
243     /**
244      * Rollsback a path ref to zero verbs and points with the assumption that the path ref will be
245      * repopulated with approximately the same number of verbs and points. A new path ref is created
246      * only if necessary.
247      */
248     static void Rewind(sk_sp<SkPathRef>* pathRef);
249 
250     ~SkPathRef();
countPoints()251     int countPoints() const { return fPointCnt; }
countVerbs()252     int countVerbs() const { return fVerbCnt; }
countWeights()253     int countWeights() const { return fConicWeights.count(); }
254 
255     /**
256      * Returns a pointer one beyond the first logical verb (last verb in memory order).
257      */
verbs()258     const uint8_t* verbs() const { return fVerbs; }
259 
260     /**
261      * Returns a const pointer to the first verb in memory (which is the last logical verb).
262      */
verbsMemBegin()263     const uint8_t* verbsMemBegin() const { return this->verbs() - fVerbCnt; }
264 
265     /**
266      * Returns a const pointer to the first point.
267      */
points()268     const SkPoint* points() const { return fPoints; }
269 
270     /**
271      * Shortcut for this->points() + this->countPoints()
272      */
pointsEnd()273     const SkPoint* pointsEnd() const { return this->points() + this->countPoints(); }
274 
conicWeights()275     const SkScalar* conicWeights() const { return fConicWeights.begin(); }
conicWeightsEnd()276     const SkScalar* conicWeightsEnd() const { return fConicWeights.end(); }
277 
278     /**
279      * Convenience methods for getting to a verb or point by index.
280      */
atVerb(int index)281     uint8_t atVerb(int index) const {
282         SkASSERT((unsigned) index < (unsigned) fVerbCnt);
283         return this->verbs()[~index];
284     }
atPoint(int index)285     const SkPoint& atPoint(int index) const {
286         SkASSERT((unsigned) index < (unsigned) fPointCnt);
287         return this->points()[index];
288     }
289 
290     bool operator== (const SkPathRef& ref) const;
291 
292     /**
293      * Writes the path points and verbs to a buffer.
294      */
295     void writeToBuffer(SkWBuffer* buffer) const;
296 
297     /**
298      * Gets the number of bytes that would be written in writeBuffer()
299      */
300     uint32_t writeSize() const;
301 
302     void interpolate(const SkPathRef& ending, SkScalar weight, SkPathRef* out) const;
303 
304     /**
305      * Gets an ID that uniquely identifies the contents of the path ref. If two path refs have the
306      * same ID then they have the same verbs and points. However, two path refs may have the same
307      * contents but different genIDs.
308      */
309     uint32_t genID() const;
310 
311     class GenIDChangeListener : public SkRefCnt {
312     public:
GenIDChangeListener()313         GenIDChangeListener() : fShouldUnregisterFromPath(false) {}
~GenIDChangeListener()314         virtual ~GenIDChangeListener() {}
315 
316         virtual void onChange() = 0;
317 
318         // The caller can use this method to notify the path that it no longer needs to listen. Once
319         // called, the path will remove this listener from the list at some future point.
markShouldUnregisterFromPath()320         void markShouldUnregisterFromPath() {
321             fShouldUnregisterFromPath.store(true, std::memory_order_relaxed);
322         }
shouldUnregisterFromPath()323         bool shouldUnregisterFromPath() {
324             return fShouldUnregisterFromPath.load(std::memory_order_acquire);
325         }
326 
327     private:
328         std::atomic<bool> fShouldUnregisterFromPath;
329     };
330 
331     void addGenIDChangeListener(sk_sp<GenIDChangeListener>);  // Threadsafe.
332 
333     bool isValid() const;
334     SkDEBUGCODE(void validate() const { SkASSERT(this->isValid()); } )
335 
336 private:
337     enum SerializationOffsets {
338         kLegacyRRectOrOvalStartIdx_SerializationShift = 28, // requires 3 bits, ignored.
339         kLegacyRRectOrOvalIsCCW_SerializationShift = 27,    // requires 1 bit, ignored.
340         kLegacyIsRRect_SerializationShift = 26,             // requires 1 bit, ignored.
341         kIsFinite_SerializationShift = 25,                  // requires 1 bit
342         kLegacyIsOval_SerializationShift = 24,              // requires 1 bit, ignored.
343         kSegmentMask_SerializationShift = 0                 // requires 4 bits (deprecated)
344     };
345 
SkPathRef()346     SkPathRef() {
347         fBoundsIsDirty = true;    // this also invalidates fIsFinite
348         fPointCnt = 0;
349         fVerbCnt = 0;
350         fVerbs = nullptr;
351         fPoints = nullptr;
352         fFreeSpace = 0;
353         fGenerationID = kEmptyGenID;
354         fSegmentMask = 0;
355         fIsOval = false;
356         fIsRRect = false;
357         // The next two values don't matter unless fIsOval or fIsRRect are true.
358         fRRectOrOvalIsCCW = false;
359         fRRectOrOvalStartIdx = 0xAC;
360         SkDEBUGCODE(fEditorsAttached.store(0);)
361         SkDEBUGCODE(this->validate();)
362     }
363 
364     void copy(const SkPathRef& ref, int additionalReserveVerbs, int additionalReservePoints);
365 
366     // Doesn't read fSegmentMask, but (re)computes it from the verbs array
367     unsigned computeSegmentMask() const;
368 
369     // Return true if the computed bounds are finite.
ComputePtBounds(SkRect * bounds,const SkPathRef & ref)370     static bool ComputePtBounds(SkRect* bounds, const SkPathRef& ref) {
371         return bounds->setBoundsCheck(ref.points(), ref.countPoints());
372     }
373 
374     // called, if dirty, by getBounds()
computeBounds()375     void computeBounds() const {
376         SkDEBUGCODE(this->validate();)
377         // TODO(mtklein): remove fBoundsIsDirty and fIsFinite,
378         // using an inverted rect instead of fBoundsIsDirty and always recalculating fIsFinite.
379         SkASSERT(fBoundsIsDirty);
380 
381         fIsFinite = ComputePtBounds(&fBounds, *this);
382         fBoundsIsDirty = false;
383     }
384 
setBounds(const SkRect & rect)385     void setBounds(const SkRect& rect) {
386         SkASSERT(rect.fLeft <= rect.fRight && rect.fTop <= rect.fBottom);
387         fBounds = rect;
388         fBoundsIsDirty = false;
389         fIsFinite = fBounds.isFinite();
390     }
391 
392     /** Makes additional room but does not change the counts or change the genID */
incReserve(int additionalVerbs,int additionalPoints)393     void incReserve(int additionalVerbs, int additionalPoints) {
394         SkDEBUGCODE(this->validate();)
395         size_t space = additionalVerbs * sizeof(uint8_t) + additionalPoints * sizeof (SkPoint);
396         this->makeSpace(space);
397         SkDEBUGCODE(this->validate();)
398     }
399 
400     /** Resets the path ref with verbCount verbs and pointCount points, all uninitialized. Also
401      *  allocates space for reserveVerb additional verbs and reservePoints additional points.*/
402     void resetToSize(int verbCount, int pointCount, int conicCount,
403                      int reserveVerbs = 0, int reservePoints = 0) {
404         SkDEBUGCODE(this->validate();)
405         fBoundsIsDirty = true;      // this also invalidates fIsFinite
406         fGenerationID = 0;
407 
408         fSegmentMask = 0;
409         fIsOval = false;
410         fIsRRect = false;
411 
412         size_t newSize = sizeof(uint8_t) * verbCount + sizeof(SkPoint) * pointCount;
413         size_t newReserve = sizeof(uint8_t) * reserveVerbs + sizeof(SkPoint) * reservePoints;
414         size_t minSize = newSize + newReserve;
415 
416         ptrdiff_t sizeDelta = this->currSize() - minSize;
417 
418         if (sizeDelta < 0 || static_cast<size_t>(sizeDelta) >= 3 * minSize) {
419             sk_free(fPoints);
420             fPoints = nullptr;
421             fVerbs = nullptr;
422             fFreeSpace = 0;
423             fVerbCnt = 0;
424             fPointCnt = 0;
425             this->makeSpace(minSize, true);
426             fVerbCnt = verbCount;
427             fPointCnt = pointCount;
428             fFreeSpace -= newSize;
429         } else {
430             fPointCnt = pointCount;
431             fVerbCnt = verbCount;
432             fFreeSpace = this->currSize() - minSize;
433         }
434         fConicWeights.setCount(conicCount);
435         SkDEBUGCODE(this->validate();)
436     }
437 
438     /**
439      * Increases the verb count by numVbs and point count by the required amount.
440      * The new points are uninitialized. All the new verbs are set to the specified
441      * verb. If 'verb' is kConic_Verb, 'weights' will return a pointer to the
442      * uninitialized conic weights.
443      */
444     SkPoint* growForRepeatedVerb(int /*SkPath::Verb*/ verb, int numVbs, SkScalar** weights);
445 
446     /**
447      * Increases the verb count 1, records the new verb, and creates room for the requisite number
448      * of additional points. A pointer to the first point is returned. Any new points are
449      * uninitialized.
450      */
451     SkPoint* growForVerb(int /*SkPath::Verb*/ verb, SkScalar weight);
452 
453     /**
454      * Ensures that the free space available in the path ref is >= size. The verb and point counts
455      * are not changed. May allocate extra capacity, unless |exact| is true.
456      */
457     void makeSpace(size_t size, bool exact = false) {
458         SkDEBUGCODE(this->validate();)
459         if (size <= fFreeSpace) {
460             return;
461         }
462         size_t growSize = size - fFreeSpace;
463         size_t oldSize = this->currSize();
464 
465         if (!exact) {
466             // round to next multiple of 8 bytes
467             growSize = (growSize + 7) & ~static_cast<size_t>(7);
468             // we always at least double the allocation
469             if (growSize < oldSize) {
470                 growSize = oldSize;
471             }
472             if (growSize < kMinSize) {
473                 growSize = kMinSize;
474             }
475         }
476 
477         constexpr size_t maxSize = std::numeric_limits<size_t>::max();
478         size_t newSize;
479         if (growSize <= maxSize - oldSize) {
480             newSize = oldSize + growSize;
481         } else {
482             SK_ABORT("Path too big.");
483         }
484         // Note that realloc could memcpy more than we need. It seems to be a win anyway. TODO:
485         // encapsulate this.
486         fPoints = reinterpret_cast<SkPoint*>(sk_realloc_throw(fPoints, newSize));
487         size_t oldVerbSize = fVerbCnt * sizeof(uint8_t);
488         void* newVerbsDst = SkTAddOffset<void>(fPoints, newSize - oldVerbSize);
489         void* oldVerbsSrc = SkTAddOffset<void>(fPoints, oldSize - oldVerbSize);
490         memmove(newVerbsDst, oldVerbsSrc, oldVerbSize);
491         fVerbs = SkTAddOffset<uint8_t>(fPoints, newSize);
492         fFreeSpace += growSize;
493         SkDEBUGCODE(this->validate();)
494     }
495 
496     /**
497      * Private, non-const-ptr version of the public function verbsMemBegin().
498      */
verbsMemWritable()499     uint8_t* verbsMemWritable() {
500         SkDEBUGCODE(this->validate();)
501         return fVerbs - fVerbCnt;
502     }
503 
504     /**
505      * Gets the total amount of space allocated for verbs, points, and reserve.
506      */
currSize()507     size_t currSize() const {
508         return reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints);
509     }
510 
511     /**
512      * Called the first time someone calls CreateEmpty to actually create the singleton.
513      */
514     friend SkPathRef* sk_create_empty_pathref();
515 
setIsOval(bool isOval,bool isCCW,unsigned start)516     void setIsOval(bool isOval, bool isCCW, unsigned start) {
517         fIsOval = isOval;
518         fRRectOrOvalIsCCW = isCCW;
519         fRRectOrOvalStartIdx = SkToU8(start);
520     }
521 
setIsRRect(bool isRRect,bool isCCW,unsigned start)522     void setIsRRect(bool isRRect, bool isCCW, unsigned start) {
523         fIsRRect = isRRect;
524         fRRectOrOvalIsCCW = isCCW;
525         fRRectOrOvalStartIdx = SkToU8(start);
526     }
527 
528     // called only by the editor. Note that this is not a const function.
getPoints()529     SkPoint* getPoints() {
530         SkDEBUGCODE(this->validate();)
531         fIsOval = false;
532         fIsRRect = false;
533         return fPoints;
534     }
535 
getPoints()536     const SkPoint* getPoints() const {
537         SkDEBUGCODE(this->validate();)
538         return fPoints;
539     }
540 
541     void callGenIDChangeListeners();
542 
543     enum {
544         kMinSize = 256,
545     };
546 
547     mutable SkRect   fBounds;
548 
549     SkPoint*            fPoints; // points to begining of the allocation
550     uint8_t*            fVerbs; // points just past the end of the allocation (verbs grow backwards)
551     int                 fVerbCnt;
552     int                 fPointCnt;
553     size_t              fFreeSpace; // redundant but saves computation
554     SkTDArray<SkScalar> fConicWeights;
555 
556     enum {
557         kEmptyGenID = 1, // GenID reserved for path ref with zero points and zero verbs.
558     };
559     mutable uint32_t    fGenerationID;
560     SkDEBUGCODE(std::atomic<int> fEditorsAttached;) // assert only one editor in use at any time.
561 
562     SkMutex                         fGenIDChangeListenersMutex;
563     SkTDArray<GenIDChangeListener*> fGenIDChangeListeners;  // pointers are reffed
564 
565     mutable uint8_t  fBoundsIsDirty;
566     mutable bool     fIsFinite;    // only meaningful if bounds are valid
567 
568     bool     fIsOval;
569     bool     fIsRRect;
570     // Both the circle and rrect special cases have a notion of direction and starting point
571     // The next two variables store that information for either.
572     bool     fRRectOrOvalIsCCW;
573     uint8_t  fRRectOrOvalStartIdx;
574     uint8_t  fSegmentMask;
575 
576     friend class PathRefTest_Private;
577     friend class ForceIsRRect_Private; // unit test isRRect
578     friend class SkPath;
579     friend class SkPathPriv;
580 };
581 
582 #endif
583