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