1 /* 2 * Copyright 2014 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 GrRectanizerPow2_DEFINED 9 #define GrRectanizerPow2_DEFINED 10 11 #include "include/private/SkMalloc.h" 12 #include "src/core/SkIPoint16.h" 13 #include "src/core/SkMathPriv.h" 14 #include "src/gpu/GrRectanizer.h" 15 16 // This Rectanizer quantizes the incoming rects to powers of 2. Each power 17 // of two can have, at most, one active row/shelf. Once a row/shelf for 18 // a particular power of two gets full its fRows entry is recycled to point 19 // to a new row. 20 // The skyline algorithm almost always provides a better packing. 21 // 22 // Mark this class final in an effort to avoid the vtable when this subclass is used explicitly. 23 class GrRectanizerPow2 final : public GrRectanizer { 24 public: GrRectanizerPow2(int w,int h)25 GrRectanizerPow2(int w, int h) : INHERITED(w, h) { 26 this->reset(); 27 } 28 ~GrRectanizerPow2()29 ~GrRectanizerPow2() final {} 30 reset()31 void reset() final { 32 fNextStripY = 0; 33 fAreaSoFar = 0; 34 sk_bzero(fRows, sizeof(fRows)); 35 } 36 37 bool addRect(int w, int h, SkIPoint16* loc) final; 38 percentFull()39 float percentFull() const final { 40 return fAreaSoFar / ((float)this->width() * this->height()); 41 } 42 43 private: 44 static const int kMIN_HEIGHT_POW2 = 2; 45 static const int kMaxExponent = 16; 46 47 struct Row { 48 SkIPoint16 fLoc; 49 // fRowHeight is actually known by this struct's position in fRows 50 // but it is used to signal if there exists an open row of this height 51 int fRowHeight; 52 canAddWidthRow53 bool canAddWidth(int width, int containerWidth) const { 54 return fLoc.fX + width <= containerWidth; 55 } 56 }; 57 58 Row fRows[kMaxExponent]; // 0-th entry will be unused 59 60 int fNextStripY; 61 int32_t fAreaSoFar; 62 HeightToRowIndex(int height)63 static int HeightToRowIndex(int height) { 64 SkASSERT(height >= kMIN_HEIGHT_POW2); 65 int index = 32 - SkCLZ(height - 1); 66 SkASSERT(index < kMaxExponent); 67 return index; 68 } 69 canAddStrip(int height)70 bool canAddStrip(int height) const { 71 return fNextStripY + height <= this->height(); 72 } 73 initRow(Row * row,int rowHeight)74 void initRow(Row* row, int rowHeight) { 75 row->fLoc.set(0, fNextStripY); 76 row->fRowHeight = rowHeight; 77 fNextStripY += rowHeight; 78 } 79 80 using INHERITED = GrRectanizer; 81 }; 82 83 #endif 84