1 // Copyright 2019 The libgav1 Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include <algorithm>
16 #include <cstdint>
17 #include <cstring>
18 
19 #include "src/dsp/constants.h"
20 #include "src/obu_parser.h"
21 #include "src/symbol_decoder_context.h"
22 #include "src/tile.h"
23 #include "src/utils/array_2d.h"
24 #include "src/utils/block_parameters_holder.h"
25 #include "src/utils/common.h"
26 #include "src/utils/constants.h"
27 #include "src/utils/entropy_decoder.h"
28 #include "src/utils/segmentation.h"
29 #include "src/utils/stack.h"
30 #include "src/utils/types.h"
31 
32 namespace libgav1 {
33 namespace {
34 
35 constexpr uint8_t kMaxVariableTransformTreeDepth = 2;
36 // Max_Tx_Depth array from section 5.11.5 in the spec with the following
37 // modification: If the element is not zero, it is subtracted by one. That is
38 // the only way in which this array is being used.
39 constexpr int kTxDepthCdfIndex[kMaxBlockSizes] = {
40     0, 0, 1, 0, 0, 1, 2, 1, 1, 1, 2, 3, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3};
41 
42 constexpr TransformSize kMaxTransformSizeRectangle[kMaxBlockSizes] = {
43     kTransformSize4x4,   kTransformSize4x8,   kTransformSize4x16,
44     kTransformSize8x4,   kTransformSize8x8,   kTransformSize8x16,
45     kTransformSize8x32,  kTransformSize16x4,  kTransformSize16x8,
46     kTransformSize16x16, kTransformSize16x32, kTransformSize16x64,
47     kTransformSize32x8,  kTransformSize32x16, kTransformSize32x32,
48     kTransformSize32x64, kTransformSize64x16, kTransformSize64x32,
49     kTransformSize64x64, kTransformSize64x64, kTransformSize64x64,
50     kTransformSize64x64};
51 
GetSquareTransformSize(uint8_t pixels)52 TransformSize GetSquareTransformSize(uint8_t pixels) {
53   switch (pixels) {
54     case 128:
55     case 64:
56       return kTransformSize64x64;
57     case 32:
58       return kTransformSize32x32;
59     case 16:
60       return kTransformSize16x16;
61     case 8:
62       return kTransformSize8x8;
63     default:
64       return kTransformSize4x4;
65   }
66 }
67 
68 }  // namespace
69 
GetTopTransformWidth(const Block & block,int row4x4,int column4x4,bool ignore_skip)70 int Tile::GetTopTransformWidth(const Block& block, int row4x4, int column4x4,
71                                bool ignore_skip) {
72   if (row4x4 == block.row4x4) {
73     if (!block.top_available[kPlaneY]) return 64;
74     const BlockParameters& bp_top =
75         *block_parameters_holder_.Find(row4x4 - 1, column4x4);
76     if ((ignore_skip || bp_top.skip) && bp_top.is_inter) {
77       return kBlockWidthPixels[bp_top.size];
78     }
79   }
80   return kTransformWidth[inter_transform_sizes_[row4x4 - 1][column4x4]];
81 }
82 
GetLeftTransformHeight(const Block & block,int row4x4,int column4x4,bool ignore_skip)83 int Tile::GetLeftTransformHeight(const Block& block, int row4x4, int column4x4,
84                                  bool ignore_skip) {
85   if (column4x4 == block.column4x4) {
86     if (!block.left_available[kPlaneY]) return 64;
87     const BlockParameters& bp_left =
88         *block_parameters_holder_.Find(row4x4, column4x4 - 1);
89     if ((ignore_skip || bp_left.skip) && bp_left.is_inter) {
90       return kBlockHeightPixels[bp_left.size];
91     }
92   }
93   return kTransformHeight[inter_transform_sizes_[row4x4][column4x4 - 1]];
94 }
95 
ReadFixedTransformSize(const Block & block)96 TransformSize Tile::ReadFixedTransformSize(const Block& block) {
97   BlockParameters& bp = *block.bp;
98   if (frame_header_.segmentation
99           .lossless[bp.prediction_parameters->segment_id]) {
100     return kTransformSize4x4;
101   }
102   const TransformSize max_rect_tx_size = kMaxTransformSizeRectangle[block.size];
103   const bool allow_select = !bp.skip || !bp.is_inter;
104   if (block.size == kBlock4x4 || !allow_select ||
105       frame_header_.tx_mode != kTxModeSelect) {
106     return max_rect_tx_size;
107   }
108   const int max_tx_width = kTransformWidth[max_rect_tx_size];
109   const int max_tx_height = kTransformHeight[max_rect_tx_size];
110   const int top_width =
111       block.top_available[kPlaneY]
112           ? GetTopTransformWidth(block, block.row4x4, block.column4x4, true)
113           : 0;
114   const int left_height =
115       block.left_available[kPlaneY]
116           ? GetLeftTransformHeight(block, block.row4x4, block.column4x4, true)
117           : 0;
118   const auto context = static_cast<int>(top_width >= max_tx_width) +
119                        static_cast<int>(left_height >= max_tx_height);
120   const int cdf_index = kTxDepthCdfIndex[block.size];
121   uint16_t* const cdf =
122       symbol_decoder_context_.tx_depth_cdf[cdf_index][context];
123   const int tx_depth = (cdf_index == 0)
124                            ? static_cast<int>(reader_.ReadSymbol(cdf))
125                            : reader_.ReadSymbol<3>(cdf);
126   assert(tx_depth < 3);
127   TransformSize tx_size = max_rect_tx_size;
128   if (tx_depth == 0) return tx_size;
129   tx_size = kSplitTransformSize[tx_size];
130   if (tx_depth == 1) return tx_size;
131   return kSplitTransformSize[tx_size];
132 }
133 
ReadVariableTransformTree(const Block & block,int row4x4,int column4x4,TransformSize tx_size)134 void Tile::ReadVariableTransformTree(const Block& block, int row4x4,
135                                      int column4x4, TransformSize tx_size) {
136   const uint8_t pixels = std::max(block.width, block.height);
137   const TransformSize max_tx_size = GetSquareTransformSize(pixels);
138   const int context_delta = (kNumSquareTransformSizes - 1 -
139                              TransformSizeToSquareTransformIndex(max_tx_size)) *
140                             6;
141 
142   // Branching factor is 4 and maximum depth is 2. So the maximum stack size
143   // necessary is (4 - 1) + 4 = 7.
144   Stack<TransformTreeNode, 7> stack;
145   stack.Push(TransformTreeNode(column4x4, row4x4, tx_size, 0));
146 
147   do {
148     TransformTreeNode node = stack.Pop();
149     const int tx_width4x4 = kTransformWidth4x4[node.tx_size];
150     const int tx_height4x4 = kTransformHeight4x4[node.tx_size];
151     if (node.tx_size != kTransformSize4x4 &&
152         node.depth != kMaxVariableTransformTreeDepth) {
153       const auto top =
154           static_cast<int>(GetTopTransformWidth(block, node.y, node.x, false) <
155                            kTransformWidth[node.tx_size]);
156       const auto left = static_cast<int>(
157           GetLeftTransformHeight(block, node.y, node.x, false) <
158           kTransformHeight[node.tx_size]);
159       const int context =
160           static_cast<int>(max_tx_size > kTransformSize8x8 &&
161                            kTransformSizeSquareMax[node.tx_size] !=
162                                max_tx_size) *
163               3 +
164           context_delta + top + left;
165       // tx_split.
166       if (reader_.ReadSymbol(symbol_decoder_context_.tx_split_cdf[context])) {
167         const TransformSize sub_tx_size = kSplitTransformSize[node.tx_size];
168         const int step_width4x4 = kTransformWidth4x4[sub_tx_size];
169         const int step_height4x4 = kTransformHeight4x4[sub_tx_size];
170         // The loops have to run in reverse order because we use a stack for
171         // DFS.
172         for (int i = tx_height4x4 - step_height4x4; i >= 0;
173              i -= step_height4x4) {
174           for (int j = tx_width4x4 - step_width4x4; j >= 0;
175                j -= step_width4x4) {
176             if (node.y + i >= frame_header_.rows4x4 ||
177                 node.x + j >= frame_header_.columns4x4) {
178               continue;
179             }
180             stack.Push(TransformTreeNode(node.x + j, node.y + i, sub_tx_size,
181                                          node.depth + 1));
182           }
183         }
184         continue;
185       }
186     }
187     // tx_split is false.
188     for (int i = 0; i < tx_height4x4; ++i) {
189       static_assert(sizeof(TransformSize) == 1, "");
190       memset(&inter_transform_sizes_[node.y + i][node.x], node.tx_size,
191              tx_width4x4);
192     }
193   } while (!stack.Empty());
194 }
195 
DecodeTransformSize(const Block & block)196 void Tile::DecodeTransformSize(const Block& block) {
197   BlockParameters& bp = *block.bp;
198   if (frame_header_.tx_mode == kTxModeSelect && block.size > kBlock4x4 &&
199       bp.is_inter && !bp.skip &&
200       !frame_header_.segmentation
201            .lossless[bp.prediction_parameters->segment_id]) {
202     const TransformSize max_tx_size = kMaxTransformSizeRectangle[block.size];
203     const int tx_width4x4 = kTransformWidth4x4[max_tx_size];
204     const int tx_height4x4 = kTransformHeight4x4[max_tx_size];
205     for (int row = block.row4x4; row < block.row4x4 + block.height4x4;
206          row += tx_height4x4) {
207       for (int column = block.column4x4;
208            column < block.column4x4 + block.width4x4; column += tx_width4x4) {
209         ReadVariableTransformTree(block, row, column, max_tx_size);
210       }
211     }
212   } else {
213     const TransformSize transform_size = ReadFixedTransformSize(block);
214     for (int row = block.row4x4; row < block.row4x4 + block.height4x4; ++row) {
215       static_assert(sizeof(TransformSize) == 1, "");
216       memset(&inter_transform_sizes_[row][block.column4x4], transform_size,
217              block.width4x4);
218     }
219   }
220 }
221 
222 }  // namespace libgav1
223