Home | History | Annotate | Download | only in gpu 
      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 
     16 class GrRectanizerFIFO : public GrRectanizer {
     17 public:
     18     GrRectanizerFIFO(int w, int h) : GrRectanizer(w, h) {
     19         fNextStripY = 0;
     20         fAreaSoFar = 0;
     21         Gr_bzero(fRows, sizeof(fRows));
     22     }
     23 
     24     virtual ~GrRectanizerFIFO() {
     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 
     68 bool GrRectanizerFIFO::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 
    119 GrRectanizer* GrRectanizer::Factory(int width, int height) {
    120     return SkNEW_ARGS(GrRectanizerFIFO, (width, height));
    121 }
    122