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