tor-browser

VariablePacker.cpp (12126B)

---

//
// Copyright 2002 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// Check whether variables fit within packing limits according to the packing rules from the GLSL ES
// 1.00.17 spec, Appendix A, section 7.

#include <algorithm>

#include "angle_gl.h"

#include "common/utilities.h"
#include "compiler/translator/VariablePacker.h"

namespace sh
{

namespace
{

// Expand the variable so that struct variables are split into their individual fields.
// Will not set the mappedName or staticUse fields on the expanded variables.
void ExpandVariable(const ShaderVariable &variable,
                   const std::string &name,
                   std::vector<ShaderVariable> *expanded);

void ExpandStructVariable(const ShaderVariable &variable,
                         const std::string &name,
                         std::vector<ShaderVariable> *expanded)
{
   ASSERT(variable.isStruct());

   const std::vector<ShaderVariable> &fields = variable.fields;

   for (size_t fieldIndex = 0; fieldIndex < fields.size(); fieldIndex++)
   {
       const ShaderVariable &field = fields[fieldIndex];
       ExpandVariable(field, name + "." + field.name, expanded);
   }
}

void ExpandStructArrayVariable(const ShaderVariable &variable,
                              unsigned int arrayNestingIndex,
                              const std::string &name,
                              std::vector<ShaderVariable> *expanded)
{
   // Nested arrays are processed starting from outermost (arrayNestingIndex 0u) and ending at the
   // innermost.
   const unsigned int currentArraySize = variable.getNestedArraySize(arrayNestingIndex);
   for (unsigned int arrayElement = 0u; arrayElement < currentArraySize; ++arrayElement)
   {
       const std::string elementName = name + ArrayString(arrayElement);
       if (arrayNestingIndex + 1u < variable.arraySizes.size())
       {
           ExpandStructArrayVariable(variable, arrayNestingIndex + 1u, elementName, expanded);
       }
       else
       {
           ExpandStructVariable(variable, elementName, expanded);
       }
   }
}

void ExpandVariable(const ShaderVariable &variable,
                   const std::string &name,
                   std::vector<ShaderVariable> *expanded)
{
   if (variable.isStruct())
   {
       if (variable.isArray())
       {
           ExpandStructArrayVariable(variable, 0u, name, expanded);
       }
       else
       {
           ExpandStructVariable(variable, name, expanded);
       }
   }
   else
   {
       ShaderVariable expandedVar = variable;
       expandedVar.name           = name;

       expanded->push_back(expandedVar);
   }
}

int GetVariablePackingRows(const ShaderVariable &variable)
{
   return GetTypePackingRows(variable.type) * variable.getArraySizeProduct();
}

class VariablePacker
{
 public:
   bool checkExpandedVariablesWithinPackingLimits(unsigned int maxVectors,
                                                  std::vector<sh::ShaderVariable> *variables);

 private:
   static const int kNumColumns      = 4;
   static const unsigned kColumnMask = (1 << kNumColumns) - 1;

   unsigned makeColumnFlags(int column, int numComponentsPerRow);
   void fillColumns(int topRow, int numRows, int column, int numComponentsPerRow);
   bool searchColumn(int column, int numRows, int *destRow, int *destSize);

   int topNonFullRow_;
   int bottomNonFullRow_;
   int maxRows_;
   std::vector<unsigned> rows_;
};

struct TVariableInfoComparer
{
   bool operator()(const sh::ShaderVariable &lhs, const sh::ShaderVariable &rhs) const
   {
       int lhsSortOrder = gl::VariableSortOrder(lhs.type);
       int rhsSortOrder = gl::VariableSortOrder(rhs.type);
       if (lhsSortOrder != rhsSortOrder)
       {
           return lhsSortOrder < rhsSortOrder;
       }
       // Sort by largest first.
       return lhs.getArraySizeProduct() > rhs.getArraySizeProduct();
   }
};

unsigned VariablePacker::makeColumnFlags(int column, int numComponentsPerRow)
{
   return ((kColumnMask << (kNumColumns - numComponentsPerRow)) & kColumnMask) >> column;
}

void VariablePacker::fillColumns(int topRow, int numRows, int column, int numComponentsPerRow)
{
   unsigned columnFlags = makeColumnFlags(column, numComponentsPerRow);
   for (int r = 0; r < numRows; ++r)
   {
       int row = topRow + r;
       ASSERT((rows_[row] & columnFlags) == 0);
       rows_[row] |= columnFlags;
   }
}

bool VariablePacker::searchColumn(int column, int numRows, int *destRow, int *destSize)
{
   ASSERT(destRow);

   for (; topNonFullRow_ < maxRows_ && rows_[topNonFullRow_] == kColumnMask; ++topNonFullRow_)
   {
   }

   for (; bottomNonFullRow_ >= 0 && rows_[bottomNonFullRow_] == kColumnMask; --bottomNonFullRow_)
   {
   }

   if (bottomNonFullRow_ - topNonFullRow_ + 1 < numRows)
   {
       return false;
   }

   unsigned columnFlags = makeColumnFlags(column, 1);
   int topGoodRow       = 0;
   int smallestGoodTop  = -1;
   int smallestGoodSize = maxRows_ + 1;
   int bottomRow        = bottomNonFullRow_ + 1;
   bool found           = false;
   for (int row = topNonFullRow_; row <= bottomRow; ++row)
   {
       bool rowEmpty = row < bottomRow ? ((rows_[row] & columnFlags) == 0) : false;
       if (rowEmpty)
       {
           if (!found)
           {
               topGoodRow = row;
               found      = true;
           }
       }
       else
       {
           if (found)
           {
               int size = row - topGoodRow;
               if (size >= numRows && size < smallestGoodSize)
               {
                   smallestGoodSize = size;
                   smallestGoodTop  = topGoodRow;
               }
           }
           found = false;
       }
   }
   if (smallestGoodTop < 0)
   {
       return false;
   }

   *destRow = smallestGoodTop;
   if (destSize)
   {
       *destSize = smallestGoodSize;
   }
   return true;
}

bool VariablePacker::checkExpandedVariablesWithinPackingLimits(
   unsigned int maxVectors,
   std::vector<sh::ShaderVariable> *variables)
{
   ASSERT(maxVectors > 0);
   maxRows_          = maxVectors;
   topNonFullRow_    = 0;
   bottomNonFullRow_ = maxRows_ - 1;

   // Check whether each variable fits in the available vectors.
   for (const sh::ShaderVariable &variable : *variables)
   {
       // Structs should have been expanded before reaching here.
       ASSERT(!variable.isStruct());
       if (variable.getArraySizeProduct() > maxVectors / GetTypePackingRows(variable.type))
       {
           return false;
       }
   }

   // As per GLSL 1.017 Appendix A, Section 7 variables are packed in specific
   // order by type, then by size of array, largest first.
   std::sort(variables->begin(), variables->end(), TVariableInfoComparer());
   rows_.clear();
   rows_.resize(maxVectors, 0);

   // Packs the 4 column variables.
   size_t ii = 0;
   for (; ii < variables->size(); ++ii)
   {
       const sh::ShaderVariable &variable = (*variables)[ii];
       if (GetTypePackingComponentsPerRow(variable.type) != 4)
       {
           break;
       }
       topNonFullRow_ += GetVariablePackingRows(variable);
       if (topNonFullRow_ > maxRows_)
       {
           return false;
       }
   }

   // Packs the 3 column variables.
   int num3ColumnRows = 0;
   for (; ii < variables->size(); ++ii)
   {
       const sh::ShaderVariable &variable = (*variables)[ii];
       if (GetTypePackingComponentsPerRow(variable.type) != 3)
       {
           break;
       }

       num3ColumnRows += GetVariablePackingRows(variable);
       if (topNonFullRow_ + num3ColumnRows > maxRows_)
       {
           return false;
       }
   }

   fillColumns(topNonFullRow_, num3ColumnRows, 0, 3);

   // Packs the 2 column variables.
   int top2ColumnRow            = topNonFullRow_ + num3ColumnRows;
   int twoColumnRowsAvailable   = maxRows_ - top2ColumnRow;
   int rowsAvailableInColumns01 = twoColumnRowsAvailable;
   int rowsAvailableInColumns23 = twoColumnRowsAvailable;
   for (; ii < variables->size(); ++ii)
   {
       const sh::ShaderVariable &variable = (*variables)[ii];
       if (GetTypePackingComponentsPerRow(variable.type) != 2)
       {
           break;
       }
       int numRows = GetVariablePackingRows(variable);
       if (numRows <= rowsAvailableInColumns01)
       {
           rowsAvailableInColumns01 -= numRows;
       }
       else if (numRows <= rowsAvailableInColumns23)
       {
           rowsAvailableInColumns23 -= numRows;
       }
       else
       {
           return false;
       }
   }

   int numRowsUsedInColumns01 = twoColumnRowsAvailable - rowsAvailableInColumns01;
   int numRowsUsedInColumns23 = twoColumnRowsAvailable - rowsAvailableInColumns23;
   fillColumns(top2ColumnRow, numRowsUsedInColumns01, 0, 2);
   fillColumns(maxRows_ - numRowsUsedInColumns23, numRowsUsedInColumns23, 2, 2);

   // Packs the 1 column variables.
   for (; ii < variables->size(); ++ii)
   {
       const sh::ShaderVariable &variable = (*variables)[ii];
       ASSERT(1 == GetTypePackingComponentsPerRow(variable.type));
       int numRows        = GetVariablePackingRows(variable);
       int smallestColumn = -1;
       int smallestSize   = maxRows_ + 1;
       int topRow         = -1;
       for (int column = 0; column < kNumColumns; ++column)
       {
           int row  = 0;
           int size = 0;
           if (searchColumn(column, numRows, &row, &size))
           {
               if (size < smallestSize)
               {
                   smallestSize   = size;
                   smallestColumn = column;
                   topRow         = row;
               }
           }
       }

       if (smallestColumn < 0)
       {
           return false;
       }

       fillColumns(topRow, numRows, smallestColumn, 1);
   }

   ASSERT(variables->size() == ii);

   return true;
}

}  // anonymous namespace

int GetTypePackingComponentsPerRow(sh::GLenum type)
{
   switch (type)
   {
       case GL_FLOAT_MAT4:
       case GL_FLOAT_MAT2:
       case GL_FLOAT_MAT2x4:
       case GL_FLOAT_MAT3x4:
       case GL_FLOAT_MAT4x2:
       case GL_FLOAT_MAT4x3:
       case GL_FLOAT_VEC4:
       case GL_INT_VEC4:
       case GL_BOOL_VEC4:
       case GL_UNSIGNED_INT_VEC4:
           return 4;
       case GL_FLOAT_MAT3:
       case GL_FLOAT_MAT2x3:
       case GL_FLOAT_MAT3x2:
       case GL_FLOAT_VEC3:
       case GL_INT_VEC3:
       case GL_BOOL_VEC3:
       case GL_UNSIGNED_INT_VEC3:
           return 3;
       case GL_FLOAT_VEC2:
       case GL_INT_VEC2:
       case GL_BOOL_VEC2:
       case GL_UNSIGNED_INT_VEC2:
           return 2;
       default:
           ASSERT(gl::VariableComponentCount(type) == 1);
           return 1;
   }
}

int GetTypePackingRows(sh::GLenum type)
{
   switch (type)
   {
       case GL_FLOAT_MAT4:
       case GL_FLOAT_MAT2x4:
       case GL_FLOAT_MAT3x4:
       case GL_FLOAT_MAT4x3:
       case GL_FLOAT_MAT4x2:
           return 4;
       case GL_FLOAT_MAT3:
       case GL_FLOAT_MAT2x3:
       case GL_FLOAT_MAT3x2:
           return 3;
       case GL_FLOAT_MAT2:
           return 2;
       default:
           ASSERT(gl::VariableRowCount(type) == 1);
           return 1;
   }
}

bool CheckVariablesInPackingLimits(unsigned int maxVectors,
                                  const std::vector<ShaderVariable> &variables)
{
   VariablePacker packer;
   std::vector<sh::ShaderVariable> expandedVariables;
   for (const ShaderVariable &variable : variables)
   {
       ExpandVariable(variable, variable.name, &expandedVariables);
   }
   return packer.checkExpandedVariablesWithinPackingLimits(maxVectors, &expandedVariables);
}

bool CheckVariablesInPackingLimits(unsigned int maxVectors,
                                  const std::vector<ShaderVariable> &variables);

}  // namespace sh