submodule/skia/src/gpu/RectanizerPow2.h

   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 skgpu_RectanizerPow2_DEFINED
   9 #define skgpu_RectanizerPow2_DEFINED
  10
  11 #include "include/private/SkMalloc.h"
  12 #include "src/core/SkIPoint16.h"
  13 #include "src/core/SkMathPriv.h"
  14 #include "src/gpu/Rectanizer.h"
  15
  16 namespace skgpu {
  17
  18 // This Rectanizer quantizes the incoming rects to powers of 2. Each power
  19 // of two can have, at most, one active row/shelf. Once a row/shelf for
  20 // a particular power of two gets full its fRows entry is recycled to point
  21 // to a new row.
  22 // The skyline algorithm almost always provides a better packing.
  23 //
  24 // Mark this class final in an effort to avoid the vtable when this subclass is used explicitly.
  25 class RectanizerPow2 final : public Rectanizer {
  26 public:
  27     RectanizerPow2(int w, int h) : Rectanizer(w, h) {
  28         this->reset();
  29     }
  30
  31     ~RectanizerPow2() final {}
  32
  33     void reset() final {
  34         fNextStripY = 0;
  35         fAreaSoFar = 0;
  36         sk_bzero(fRows, sizeof(fRows));
  37     }
  38
  39     bool addRect(int w, int h, SkIPoint16* loc) final;
  40
  41     float percentFull() const final {
  42         return fAreaSoFar / ((float)this->width() * this->height());
  43     }
  44
  45 private:
  46     static const int kMIN_HEIGHT_POW2 = 2;
  47     static const int kMaxExponent = 16;
  48
  49     struct Row {
  50         SkIPoint16  fLoc;
  51         // fRowHeight is actually known by this struct's position in fRows
  52         // but it is used to signal if there exists an open row of this height
  53         int         fRowHeight;
  54
  55         bool canAddWidth(int width, int containerWidth) const {
  56             return fLoc.fX + width <= containerWidth;
  57         }
  58     };
  59
  60     Row fRows[kMaxExponent];    // 0-th entry will be unused
  61
  62     int fNextStripY;
  63     int32_t fAreaSoFar;
  64
  65     static int HeightToRowIndex(int height) {
  66         SkASSERT(height >= kMIN_HEIGHT_POW2);
  67         int index = 32 - SkCLZ(height - 1);
  68         SkASSERT(index < kMaxExponent);
  69         return index;
  70     }
  71
  72     bool canAddStrip(int height) const {
  73         return fNextStripY + height <= this->height();
  74     }
  75
  76     void initRow(Row* row, int rowHeight) {
  77         row->fLoc.set(0, fNextStripY);
  78         row->fRowHeight = rowHeight;
  79         fNextStripY += rowHeight;
  80     }
  81 };
  82
  83 } // End of namespace skgpu
  84
  85 #endif