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.
19class GrRectanizerPow2 : public GrRectanizer {
20public:
21    GrRectanizerPow2(int w, int h) : INHERITED(w, h) {
22        this->reset();
23    }
24
25    virtual ~GrRectanizerPow2() { }
26
27    virtual void reset() SK_OVERRIDE {
28        fNextStripY = 0;
29        fAreaSoFar = 0;
30        sk_bzero(fRows, sizeof(fRows));
31    }
32
33    virtual bool addRect(int w, int h, SkIPoint16* loc) SK_OVERRIDE;
34
35    virtual float percentFull() const SK_OVERRIDE {
36        return fAreaSoFar / ((float)this->width() * this->height());
37    }
38
39private:
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
49        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
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
66    bool canAddStrip(int height) const {
67        return fNextStripY + height <= this->height();
68    }
69
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