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.
23class GrRectanizerPow2 final : public GrRectanizer {
24public:
25 GrRectanizerPow2(int w, int h) : INHERITED(w, h) {
26 this->reset();
27 }
28
29 ~GrRectanizerPow2() final {}
30
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
39 float percentFull() const final {
40 return fAreaSoFar / ((float)this->width() * this->height());
41 }
42
43private:
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
53 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
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
70 bool canAddStrip(int height) const {
71 return fNextStripY + height <= this->height();
72 }
73
74 void initRow(Row* row, int rowHeight) {
75 row->fLoc.set(0, fNextStripY);
76 row->fRowHeight = rowHeight;
77 fNextStripY += rowHeight;
78 }
79
80 typedef GrRectanizer INHERITED;
81};
82
83#endif
84