2 * Copyright 2014 Google Inc.
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
8 #ifndef skgpu_RectanizerPow2_DEFINED
9 #define skgpu_RectanizerPow2_DEFINED
11 #include "include/private/SkMalloc.h"
12 #include "src/core/SkIPoint16.h"
13 #include "src/core/SkMathPriv.h"
14 #include "src/gpu/Rectanizer.h"
18 // This Rectanizer quantizes the incoming rects to powers of 2. Each power
19 // of two can have, at most, one active row/shelf. Once a row/shelf for
20 // a particular power of two gets full its fRows entry is recycled to point
22 // The skyline algorithm almost always provides a better packing.
24 // Mark this class final in an effort to avoid the vtable when this subclass is used explicitly.
25 class RectanizerPow2 final : public Rectanizer {
27 RectanizerPow2(int w, int h) : Rectanizer(w, h) {
31 ~RectanizerPow2() final {}
36 sk_bzero(fRows, sizeof(fRows));
39 bool addRect(int w, int h, SkIPoint16* loc) final;
41 float percentFull() const final {
42 return fAreaSoFar / ((float)this->width() * this->height());
46 static const int kMIN_HEIGHT_POW2 = 2;
47 static const int kMaxExponent = 16;
51 // fRowHeight is actually known by this struct's position in fRows
52 // but it is used to signal if there exists an open row of this height
55 bool canAddWidth(int width, int containerWidth) const {
56 return fLoc.fX + width <= containerWidth;
60 Row fRows[kMaxExponent]; // 0-th entry will be unused
65 static int HeightToRowIndex(int height) {
66 SkASSERT(height >= kMIN_HEIGHT_POW2);
67 int index = 32 - SkCLZ(height - 1);
68 SkASSERT(index < kMaxExponent);
72 bool canAddStrip(int height) const {
73 return fNextStripY + height <= this->height();
76 void initRow(Row* row, int rowHeight) {
77 row->fLoc.set(0, fNextStripY);
78 row->fRowHeight = rowHeight;
79 fNextStripY += rowHeight;
83 } // End of namespace skgpu