1
2/*
3 * Copyright 2010 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10
11#include "GrRectanizer.h"
12#include "GrTBSearch.h"
13
14#define MIN_HEIGHT_POW2     2
15
16class GrRectanizerPow2 : public GrRectanizer {
17public:
18    GrRectanizerPow2(int w, int h) : GrRectanizer(w, h) {
19        fNextStripY = 0;
20        fAreaSoFar = 0;
21        Gr_bzero(fRows, sizeof(fRows));
22    }
23
24    virtual ~GrRectanizerPow2() {
25    }
26
27    virtual bool addRect(int w, int h, GrIPoint16* loc);
28
29    virtual float percentFull() const {
30        return fAreaSoFar / ((float)this->width() * this->height());
31    }
32
33    virtual int stripToPurge(int height) const { return -1; }
34    virtual void purgeStripAtY(int yCoord) { }
35
36    ///////////////////////////////////////////////////////////////////////////
37
38    struct Row {
39        GrIPoint16  fLoc;
40        int         fRowHeight;
41
42        bool canAddWidth(int width, int containerWidth) const {
43            return fLoc.fX + width <= containerWidth;
44        }
45    };
46
47    Row fRows[16];
48
49    static int HeightToRowIndex(int height) {
50        GrAssert(height >= MIN_HEIGHT_POW2);
51        return 32 - Gr_clz(height - 1);
52    }
53
54    int fNextStripY;
55    int32_t fAreaSoFar;
56
57    bool canAddStrip(int height) const {
58        return fNextStripY + height <= this->height();
59    }
60
61    void initRow(Row* row, int rowHeight) {
62        row->fLoc.set(0, fNextStripY);
63        row->fRowHeight = rowHeight;
64        fNextStripY += rowHeight;
65    }
66};
67
68bool GrRectanizerPow2::addRect(int width, int height, GrIPoint16* loc) {
69    if ((unsigned)width > (unsigned)this->width() ||
70        (unsigned)height > (unsigned)this->height()) {
71        return false;
72    }
73
74    int32_t area = width * height;
75
76    /*
77        We use bsearch, but there may be more than one row with the same height,
78        so we actually search for height-1, which can only be a pow2 itself if
79        height == 2. Thus we set a minimum height.
80     */
81    height = GrNextPow2(height);
82    if (height < MIN_HEIGHT_POW2) {
83        height = MIN_HEIGHT_POW2;
84    }
85
86    Row* row = &fRows[HeightToRowIndex(height)];
87    GrAssert(row->fRowHeight == 0 || row->fRowHeight == height);
88
89    if (0 == row->fRowHeight) {
90        if (!this->canAddStrip(height)) {
91            return false;
92        }
93        this->initRow(row, height);
94    } else {
95        if (!row->canAddWidth(width, this->width())) {
96            if (!this->canAddStrip(height)) {
97                return false;
98            }
99            // that row is now "full", so retarget our Row record for
100            // another one
101            this->initRow(row, height);
102        }
103    }
104
105    GrAssert(row->fRowHeight == height);
106    GrAssert(row->canAddWidth(width, this->width()));
107    *loc = row->fLoc;
108    row->fLoc.fX += width;
109
110    GrAssert(row->fLoc.fX <= this->width());
111    GrAssert(row->fLoc.fY <= this->height());
112    GrAssert(fNextStripY <= this->height());
113    fAreaSoFar += area;
114    return true;
115}
116
117///////////////////////////////////////////////////////////////////////////////
118
119GrRectanizer* GrRectanizer::Factory(int width, int height) {
120    return new GrRectanizerPow2(width, height);
121}
122
123
124