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