GrRectanizer_pow2.h revision b549cc38c8404c58642ada75c0b24907702cc005 
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 "SkMathPriv.h"
13#include "SkMalloc.h"
14#include "SkPoint.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.
21class GrRectanizerPow2 : public GrRectanizer {
22public:
23    GrRectanizerPow2(int w, int h) : INHERITED(w, h) {
24        this->reset();
25    }
26
27    ~GrRectanizerPow2() override {}
28
29    void reset() override {
30        fNextStripY = 0;
31        fAreaSoFar = 0;
32        sk_bzero(fRows, sizeof(fRows));
33    }
34
35    bool addRect(int w, int h, SkIPoint16* loc) override;
36
37    float percentFull() const override {
38        return fAreaSoFar / ((float)this->width() * this->height());
39    }
40
41private:
42    static const int kMIN_HEIGHT_POW2 = 2;
43    static const int kMaxExponent = 16;
44
45    struct Row {
46        SkIPoint16  fLoc;
47        // fRowHeight is actually known by this struct's position in fRows
48        // but it is used to signal if there exists an open row of this height
49        int         fRowHeight;
50
51        bool canAddWidth(int width, int containerWidth) const {
52            return fLoc.fX + width <= containerWidth;
53        }
54    };
55
56    Row fRows[kMaxExponent];    // 0-th entry will be unused
57
58    int fNextStripY;
59    int32_t fAreaSoFar;
60
61    static int HeightToRowIndex(int height) {
62        SkASSERT(height >= kMIN_HEIGHT_POW2);
63        int index = 32 - SkCLZ(height - 1);
64        SkASSERT(index < kMaxExponent);
65        return index;
66    }
67
68    bool canAddStrip(int height) const {
69        return fNextStripY + height <= this->height();
70    }
71
72    void initRow(Row* row, int rowHeight) {
73        row->fLoc.set(0, fNextStripY);
74        row->fRowHeight = rowHeight;
75        fNextStripY += rowHeight;
76    }
77
78    typedef GrRectanizer INHERITED;
79};
80
81#endif
82