1//
2// Copyright (c) 2002-2012 The ANGLE Project Authors. All rights reserved.
3// Use of this source code is governed by a BSD-style license that can be
4// found in the LICENSE file.
5//
6#include "compiler/VariablePacker.h"
7
8#include <algorithm>
9#include "compiler/ShHandle.h"
10
11namespace {
12int GetSortOrder(ShDataType type)
13{
14    switch (type) {
15        case SH_FLOAT_MAT4:
16            return 0;
17        case SH_FLOAT_MAT2:
18            return 1;
19        case SH_FLOAT_VEC4:
20        case SH_INT_VEC4:
21        case SH_BOOL_VEC4:
22            return 2;
23        case SH_FLOAT_MAT3:
24            return 3;
25        case SH_FLOAT_VEC3:
26        case SH_INT_VEC3:
27        case SH_BOOL_VEC3:
28            return 4;
29        case SH_FLOAT_VEC2:
30        case SH_INT_VEC2:
31        case SH_BOOL_VEC2:
32            return 5;
33        case SH_FLOAT:
34        case SH_INT:
35        case SH_BOOL:
36        case SH_SAMPLER_2D:
37        case SH_SAMPLER_CUBE:
38        case SH_SAMPLER_EXTERNAL_OES:
39        case SH_SAMPLER_2D_RECT_ARB:
40            return 6;
41        default:
42            ASSERT(false);
43            return 7;
44    }
45}
46}    // namespace
47
48int VariablePacker::GetNumComponentsPerRow(ShDataType type)
49{
50    switch (type) {
51        case SH_FLOAT_MAT4:
52        case SH_FLOAT_MAT2:
53        case SH_FLOAT_VEC4:
54        case SH_INT_VEC4:
55        case SH_BOOL_VEC4:
56            return 4;
57        case SH_FLOAT_MAT3:
58        case SH_FLOAT_VEC3:
59        case SH_INT_VEC3:
60        case SH_BOOL_VEC3:
61            return 3;
62        case SH_FLOAT_VEC2:
63        case SH_INT_VEC2:
64        case SH_BOOL_VEC2:
65            return 2;
66        case SH_FLOAT:
67        case SH_INT:
68        case SH_BOOL:
69        case SH_SAMPLER_2D:
70        case SH_SAMPLER_CUBE:
71        case SH_SAMPLER_EXTERNAL_OES:
72        case SH_SAMPLER_2D_RECT_ARB:
73            return 1;
74        default:
75            ASSERT(false);
76            return 5;
77    }
78}
79
80int VariablePacker::GetNumRows(ShDataType type)
81{
82    switch (type) {
83        case SH_FLOAT_MAT4:
84            return 4;
85        case SH_FLOAT_MAT3:
86            return 3;
87        case SH_FLOAT_MAT2:
88            return 2;
89        case SH_FLOAT_VEC4:
90        case SH_INT_VEC4:
91        case SH_BOOL_VEC4:
92        case SH_FLOAT_VEC3:
93        case SH_INT_VEC3:
94        case SH_BOOL_VEC3:
95        case SH_FLOAT_VEC2:
96        case SH_INT_VEC2:
97        case SH_BOOL_VEC2:
98        case SH_FLOAT:
99        case SH_INT:
100        case SH_BOOL:
101        case SH_SAMPLER_2D:
102        case SH_SAMPLER_CUBE:
103        case SH_SAMPLER_EXTERNAL_OES:
104        case SH_SAMPLER_2D_RECT_ARB:
105            return 1;
106        default:
107            ASSERT(false);
108            return 100000;
109    }
110}
111
112struct TVariableInfoComparer {
113    bool operator()(const TVariableInfo& lhs, const TVariableInfo& rhs) const
114    {
115        int lhsSortOrder = GetSortOrder(lhs.type);
116        int rhsSortOrder = GetSortOrder(rhs.type);
117        if (lhsSortOrder != rhsSortOrder) {
118            return lhsSortOrder < rhsSortOrder;
119        }
120        // Sort by largest first.
121        return lhs.size > rhs.size;
122    }
123};
124
125unsigned VariablePacker::makeColumnFlags(int column, int numComponentsPerRow)
126{
127    return ((kColumnMask << (kNumColumns - numComponentsPerRow)) &
128                    kColumnMask) >> column;
129}
130
131void VariablePacker::fillColumns(int topRow, int numRows, int column, int numComponentsPerRow)
132{
133    unsigned columnFlags = makeColumnFlags(column, numComponentsPerRow);
134    for (int r = 0; r < numRows; ++r) {
135        int row = topRow + r;
136        ASSERT((rows_[row] & columnFlags) == 0);
137        rows_[row] |= columnFlags;
138    }
139}
140
141bool VariablePacker::searchColumn(int column, int numRows, int* destRow, int* destSize)
142{
143    ASSERT(destRow);
144
145    for (; topNonFullRow_ < maxRows_ && rows_[topNonFullRow_] == kColumnMask;
146         ++topNonFullRow_) {
147    }
148
149    for (; bottomNonFullRow_ >= 0 && rows_[bottomNonFullRow_] == kColumnMask;
150         --bottomNonFullRow_) {
151    }
152
153    if (bottomNonFullRow_ - topNonFullRow_ + 1 < numRows) {
154        return false;
155    }
156
157    unsigned columnFlags = makeColumnFlags(column, 1);
158    int topGoodRow = 0;
159    int smallestGoodTop = -1;
160    int smallestGoodSize = maxRows_ + 1;
161    int bottomRow = bottomNonFullRow_ + 1;
162    bool found = false;
163    for (int row = topNonFullRow_; row <= bottomRow; ++row) {
164        bool rowEmpty = row < bottomRow ? ((rows_[row] & columnFlags) == 0) : false;
165        if (rowEmpty) {
166            if (!found) {
167                topGoodRow = row;
168                found = true;
169            }
170        } else {
171            if (found) {
172                int size = row - topGoodRow;
173                if (size >= numRows && size < smallestGoodSize) {
174                    smallestGoodSize = size;
175                    smallestGoodTop = topGoodRow;
176                }
177            }
178            found = false;
179        }
180    }
181    if (smallestGoodTop < 0) {
182        return false;
183    }
184
185    *destRow = smallestGoodTop;
186    if (destSize) {
187        *destSize = smallestGoodSize;
188    }
189    return true;
190}
191
192bool VariablePacker::CheckVariablesWithinPackingLimits(int maxVectors, const TVariableInfoList& in_variables)
193{
194    ASSERT(maxVectors > 0);
195    maxRows_ = maxVectors;
196    topNonFullRow_ = 0;
197    bottomNonFullRow_ = maxRows_ - 1;
198    TVariableInfoList variables(in_variables);
199
200    // As per GLSL 1.017 Appendix A, Section 7 variables are packed in specific
201    // order by type, then by size of array, largest first.
202    std::sort(variables.begin(), variables.end(), TVariableInfoComparer());
203    rows_.clear();
204    rows_.resize(maxVectors, 0);
205
206    // Packs the 4 column variables.
207    size_t ii = 0;
208    for (; ii < variables.size(); ++ii) {
209        const TVariableInfo& variable = variables[ii];
210        if (GetNumComponentsPerRow(variable.type) != 4) {
211            break;
212        }
213        topNonFullRow_ += GetNumRows(variable.type) * variable.size;
214    }
215
216    if (topNonFullRow_ > maxRows_) {
217        return false;
218    }
219
220    // Packs the 3 column variables.
221    int num3ColumnRows = 0;
222    for (; ii < variables.size(); ++ii) {
223        const TVariableInfo& variable = variables[ii];
224        if (GetNumComponentsPerRow(variable.type) != 3) {
225            break;
226        }
227        num3ColumnRows += GetNumRows(variable.type) * variable.size;
228    }
229
230    if (topNonFullRow_ + num3ColumnRows > maxRows_) {
231        return false;
232    }
233
234    fillColumns(topNonFullRow_, num3ColumnRows, 0, 3);
235
236    // Packs the 2 column variables.
237    int top2ColumnRow = topNonFullRow_ + num3ColumnRows;
238    int twoColumnRowsAvailable = maxRows_ - top2ColumnRow;
239    int rowsAvailableInColumns01 = twoColumnRowsAvailable;
240    int rowsAvailableInColumns23 = twoColumnRowsAvailable;
241    for (; ii < variables.size(); ++ii) {
242        const TVariableInfo& variable = variables[ii];
243        if (GetNumComponentsPerRow(variable.type) != 2) {
244            break;
245        }
246        int numRows = GetNumRows(variable.type) * variable.size;
247        if (numRows <= rowsAvailableInColumns01) {
248            rowsAvailableInColumns01 -= numRows;
249        } else if (numRows <= rowsAvailableInColumns23) {
250            rowsAvailableInColumns23 -= numRows;
251        } else {
252            return false;
253        }
254    }
255
256    int numRowsUsedInColumns01 =
257        twoColumnRowsAvailable - rowsAvailableInColumns01;
258    int numRowsUsedInColumns23 =
259        twoColumnRowsAvailable - rowsAvailableInColumns23;
260    fillColumns(top2ColumnRow, numRowsUsedInColumns01, 0, 2);
261    fillColumns(maxRows_ - numRowsUsedInColumns23, numRowsUsedInColumns23,
262                2, 2);
263
264    // Packs the 1 column variables.
265    for (; ii < variables.size(); ++ii) {
266        const TVariableInfo& variable = variables[ii];
267        ASSERT(1 == GetNumComponentsPerRow(variable.type));
268        int numRows = GetNumRows(variable.type) * variable.size;
269        int smallestColumn = -1;
270        int smallestSize = maxRows_ + 1;
271        int topRow = -1;
272        for (int column = 0; column < kNumColumns; ++column) {
273            int row = 0;
274            int size = 0;
275            if (searchColumn(column, numRows, &row, &size)) {
276                if (size < smallestSize) {
277                    smallestSize = size;
278                    smallestColumn = column;
279                    topRow = row;
280                }
281            }
282        }
283
284        if (smallestColumn < 0) {
285            return false;
286        }
287
288        fillColumns(topRow, numRows, smallestColumn, 1);
289    }
290
291    ASSERT(variables.size() == ii);
292
293    return true;
294}
295
296
297
298