Home | History | Annotate | Download | only in gpu 
      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.
     21 class GrRectanizerPow2 : public GrRectanizer {
     22 public:
     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 
     41 private:
     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