michael@0: //
michael@0: // Copyright (c) 2002-2012 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: #include "compiler/VariablePacker.h"
michael@0: 
michael@0: #include <algorithm>
michael@0: #include "compiler/ShHandle.h"
michael@0: 
michael@0: namespace {
michael@0: int GetSortOrder(ShDataType type)
michael@0: {
michael@0:     switch (type) {
michael@0:         case SH_FLOAT_MAT4:
michael@0:             return 0;
michael@0:         case SH_FLOAT_MAT2:
michael@0:             return 1;
michael@0:         case SH_FLOAT_VEC4:
michael@0:         case SH_INT_VEC4:
michael@0:         case SH_BOOL_VEC4:
michael@0:             return 2;
michael@0:         case SH_FLOAT_MAT3:
michael@0:             return 3;
michael@0:         case SH_FLOAT_VEC3:
michael@0:         case SH_INT_VEC3:
michael@0:         case SH_BOOL_VEC3:
michael@0:             return 4;
michael@0:         case SH_FLOAT_VEC2:
michael@0:         case SH_INT_VEC2:
michael@0:         case SH_BOOL_VEC2:
michael@0:             return 5;
michael@0:         case SH_FLOAT:
michael@0:         case SH_INT:
michael@0:         case SH_BOOL:
michael@0:         case SH_SAMPLER_2D:
michael@0:         case SH_SAMPLER_CUBE:
michael@0:         case SH_SAMPLER_EXTERNAL_OES:
michael@0:         case SH_SAMPLER_2D_RECT_ARB:
michael@0:             return 6;
michael@0:         default:
michael@0:             ASSERT(false);
michael@0:             return 7;
michael@0:     }
michael@0: }
michael@0: }    // namespace
michael@0: 
michael@0: int VariablePacker::GetNumComponentsPerRow(ShDataType type)
michael@0: {
michael@0:     switch (type) {
michael@0:         case SH_FLOAT_MAT4:
michael@0:         case SH_FLOAT_MAT2:
michael@0:         case SH_FLOAT_VEC4:
michael@0:         case SH_INT_VEC4:
michael@0:         case SH_BOOL_VEC4:
michael@0:             return 4;
michael@0:         case SH_FLOAT_MAT3:
michael@0:         case SH_FLOAT_VEC3:
michael@0:         case SH_INT_VEC3:
michael@0:         case SH_BOOL_VEC3:
michael@0:             return 3;
michael@0:         case SH_FLOAT_VEC2:
michael@0:         case SH_INT_VEC2:
michael@0:         case SH_BOOL_VEC2:
michael@0:             return 2;
michael@0:         case SH_FLOAT:
michael@0:         case SH_INT:
michael@0:         case SH_BOOL:
michael@0:         case SH_SAMPLER_2D:
michael@0:         case SH_SAMPLER_CUBE:
michael@0:         case SH_SAMPLER_EXTERNAL_OES:
michael@0:         case SH_SAMPLER_2D_RECT_ARB:
michael@0:             return 1;
michael@0:         default:
michael@0:             ASSERT(false);
michael@0:             return 5;
michael@0:     }
michael@0: }
michael@0: 
michael@0: int VariablePacker::GetNumRows(ShDataType type)
michael@0: {
michael@0:     switch (type) {
michael@0:         case SH_FLOAT_MAT4:
michael@0:             return 4;
michael@0:         case SH_FLOAT_MAT3:
michael@0:             return 3;
michael@0:         case SH_FLOAT_MAT2:
michael@0:             return 2;
michael@0:         case SH_FLOAT_VEC4:
michael@0:         case SH_INT_VEC4:
michael@0:         case SH_BOOL_VEC4:
michael@0:         case SH_FLOAT_VEC3:
michael@0:         case SH_INT_VEC3:
michael@0:         case SH_BOOL_VEC3:
michael@0:         case SH_FLOAT_VEC2:
michael@0:         case SH_INT_VEC2:
michael@0:         case SH_BOOL_VEC2:
michael@0:         case SH_FLOAT:
michael@0:         case SH_INT:
michael@0:         case SH_BOOL:
michael@0:         case SH_SAMPLER_2D:
michael@0:         case SH_SAMPLER_CUBE:
michael@0:         case SH_SAMPLER_EXTERNAL_OES:
michael@0:         case SH_SAMPLER_2D_RECT_ARB:
michael@0:             return 1;
michael@0:         default:
michael@0:             ASSERT(false);
michael@0:             return 100000;
michael@0:     }
michael@0: }
michael@0: 
michael@0: struct TVariableInfoComparer {
michael@0:     bool operator()(const TVariableInfo& lhs, const TVariableInfo& rhs) const
michael@0:     {
michael@0:         int lhsSortOrder = GetSortOrder(lhs.type);
michael@0:         int rhsSortOrder = GetSortOrder(rhs.type);
michael@0:         if (lhsSortOrder != rhsSortOrder) {
michael@0:             return lhsSortOrder < rhsSortOrder;
michael@0:         }
michael@0:         // Sort by largest first.
michael@0:         return lhs.size > rhs.size;
michael@0:     }
michael@0: };
michael@0: 
michael@0: unsigned VariablePacker::makeColumnFlags(int column, int numComponentsPerRow)
michael@0: {
michael@0:     return ((kColumnMask << (kNumColumns - numComponentsPerRow)) &
michael@0:                     kColumnMask) >> column;
michael@0: }
michael@0: 
michael@0: void VariablePacker::fillColumns(int topRow, int numRows, int column, int numComponentsPerRow)
michael@0: {
michael@0:     unsigned columnFlags = makeColumnFlags(column, numComponentsPerRow);
michael@0:     for (int r = 0; r < numRows; ++r) {
michael@0:         int row = topRow + r;
michael@0:         ASSERT((rows_[row] & columnFlags) == 0);
michael@0:         rows_[row] |= columnFlags;
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool VariablePacker::searchColumn(int column, int numRows, int* destRow, int* destSize)
michael@0: {
michael@0:     ASSERT(destRow);
michael@0: 
michael@0:     for (; topNonFullRow_ < maxRows_ && rows_[topNonFullRow_] == kColumnMask;
michael@0:          ++topNonFullRow_) {
michael@0:     }
michael@0: 
michael@0:     for (; bottomNonFullRow_ >= 0 && rows_[bottomNonFullRow_] == kColumnMask;
michael@0:          --bottomNonFullRow_) {
michael@0:     }
michael@0: 
michael@0:     if (bottomNonFullRow_ - topNonFullRow_ + 1 < numRows) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     unsigned columnFlags = makeColumnFlags(column, 1);
michael@0:     int topGoodRow = 0;
michael@0:     int smallestGoodTop = -1;
michael@0:     int smallestGoodSize = maxRows_ + 1;
michael@0:     int bottomRow = bottomNonFullRow_ + 1;
michael@0:     bool found = false;
michael@0:     for (int row = topNonFullRow_; row <= bottomRow; ++row) {
michael@0:         bool rowEmpty = row < bottomRow ? ((rows_[row] & columnFlags) == 0) : false;
michael@0:         if (rowEmpty) {
michael@0:             if (!found) {
michael@0:                 topGoodRow = row;
michael@0:                 found = true;
michael@0:             }
michael@0:         } else {
michael@0:             if (found) {
michael@0:                 int size = row - topGoodRow;
michael@0:                 if (size >= numRows && size < smallestGoodSize) {
michael@0:                     smallestGoodSize = size;
michael@0:                     smallestGoodTop = topGoodRow;
michael@0:                 }
michael@0:             }
michael@0:             found = false;
michael@0:         }
michael@0:     }
michael@0:     if (smallestGoodTop < 0) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     *destRow = smallestGoodTop;
michael@0:     if (destSize) {
michael@0:         *destSize = smallestGoodSize;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool VariablePacker::CheckVariablesWithinPackingLimits(int maxVectors, const TVariableInfoList& in_variables)
michael@0: {
michael@0:     ASSERT(maxVectors > 0);
michael@0:     maxRows_ = maxVectors;
michael@0:     topNonFullRow_ = 0;
michael@0:     bottomNonFullRow_ = maxRows_ - 1;
michael@0:     TVariableInfoList variables(in_variables);
michael@0: 
michael@0:     // As per GLSL 1.017 Appendix A, Section 7 variables are packed in specific
michael@0:     // order by type, then by size of array, largest first.
michael@0:     std::sort(variables.begin(), variables.end(), TVariableInfoComparer());
michael@0:     rows_.clear();
michael@0:     rows_.resize(maxVectors, 0);
michael@0: 
michael@0:     // Packs the 4 column variables.
michael@0:     size_t ii = 0;
michael@0:     for (; ii < variables.size(); ++ii) {
michael@0:         const TVariableInfo& variable = variables[ii];
michael@0:         if (GetNumComponentsPerRow(variable.type) != 4) {
michael@0:             break;
michael@0:         }
michael@0:         topNonFullRow_ += GetNumRows(variable.type) * variable.size;
michael@0:     }
michael@0: 
michael@0:     if (topNonFullRow_ > maxRows_) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // Packs the 3 column variables.
michael@0:     int num3ColumnRows = 0;
michael@0:     for (; ii < variables.size(); ++ii) {
michael@0:         const TVariableInfo& variable = variables[ii];
michael@0:         if (GetNumComponentsPerRow(variable.type) != 3) {
michael@0:             break;
michael@0:         }
michael@0:         num3ColumnRows += GetNumRows(variable.type) * variable.size;
michael@0:     }
michael@0: 
michael@0:     if (topNonFullRow_ + num3ColumnRows > maxRows_) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     fillColumns(topNonFullRow_, num3ColumnRows, 0, 3);
michael@0: 
michael@0:     // Packs the 2 column variables.
michael@0:     int top2ColumnRow = topNonFullRow_ + num3ColumnRows;
michael@0:     int twoColumnRowsAvailable = maxRows_ - top2ColumnRow;
michael@0:     int rowsAvailableInColumns01 = twoColumnRowsAvailable;
michael@0:     int rowsAvailableInColumns23 = twoColumnRowsAvailable;
michael@0:     for (; ii < variables.size(); ++ii) {
michael@0:         const TVariableInfo& variable = variables[ii];
michael@0:         if (GetNumComponentsPerRow(variable.type) != 2) {
michael@0:             break;
michael@0:         }
michael@0:         int numRows = GetNumRows(variable.type) * variable.size;
michael@0:         if (numRows <= rowsAvailableInColumns01) {
michael@0:             rowsAvailableInColumns01 -= numRows;
michael@0:         } else if (numRows <= rowsAvailableInColumns23) {
michael@0:             rowsAvailableInColumns23 -= numRows;
michael@0:         } else {
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     int numRowsUsedInColumns01 =
michael@0:         twoColumnRowsAvailable - rowsAvailableInColumns01;
michael@0:     int numRowsUsedInColumns23 =
michael@0:         twoColumnRowsAvailable - rowsAvailableInColumns23;
michael@0:     fillColumns(top2ColumnRow, numRowsUsedInColumns01, 0, 2);
michael@0:     fillColumns(maxRows_ - numRowsUsedInColumns23, numRowsUsedInColumns23,
michael@0:                 2, 2);
michael@0: 
michael@0:     // Packs the 1 column variables.
michael@0:     for (; ii < variables.size(); ++ii) {
michael@0:         const TVariableInfo& variable = variables[ii];
michael@0:         ASSERT(1 == GetNumComponentsPerRow(variable.type));
michael@0:         int numRows = GetNumRows(variable.type) * variable.size;
michael@0:         int smallestColumn = -1;
michael@0:         int smallestSize = maxRows_ + 1;
michael@0:         int topRow = -1;
michael@0:         for (int column = 0; column < kNumColumns; ++column) {
michael@0:             int row = 0;
michael@0:             int size = 0;
michael@0:             if (searchColumn(column, numRows, &row, &size)) {
michael@0:                 if (size < smallestSize) {
michael@0:                     smallestSize = size;
michael@0:                     smallestColumn = column;
michael@0:                     topRow = row;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (smallestColumn < 0) {
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         fillColumns(topRow, numRows, smallestColumn, 1);
michael@0:     }
michael@0: 
michael@0:     ASSERT(variables.size() == ii);
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: 
michael@0: