1 // Copyright 2018 Google LLC
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 // https://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 "src/decoder/integer_sequence_codec.h"
16 #include "src/base/math_utils.h"
17 #include "src/base/utils.h"
18
19 #include <algorithm>
20 #include <iostream>
21
22 namespace astc_codec {
23
24 namespace {
25
26 // Tables of trit and quint encodings generated by the implementation in
27 // http://cs/aosp-master/external/skia/src/utils/SkTextureCompressor_ASTC.cpp
28 //
29 // These tables are used to decode the blocks of values encoded using the ASTC
30 // integer sequence encoding. The theory is that five trits (values that can
31 // take any number in the range [0, 2]) can take on a total of 3^5 = 243 total
32 // values, which can be stored in eight bits. These eight bits are used to
33 // decode the five trits based on the ASTC specification in Section C.2.12.
34 // For simplicity, we have stored a look-up table here so that we don't need
35 // to implement the decoding logic. Similarly, seven bits are used to decode
36 // three quints (since 5^3 = 125 < 128).
37 static const std::array<int, 5> kTritEncodings[256] = {
38 {{ 0, 0, 0, 0, 0 }}, {{ 1, 0, 0, 0, 0 }}, {{ 2, 0, 0, 0, 0 }},
39 {{ 0, 0, 2, 0, 0 }}, {{ 0, 1, 0, 0, 0 }}, {{ 1, 1, 0, 0, 0 }},
40 {{ 2, 1, 0, 0, 0 }}, {{ 1, 0, 2, 0, 0 }}, {{ 0, 2, 0, 0, 0 }},
41 {{ 1, 2, 0, 0, 0 }}, {{ 2, 2, 0, 0, 0 }}, {{ 2, 0, 2, 0, 0 }},
42 {{ 0, 2, 2, 0, 0 }}, {{ 1, 2, 2, 0, 0 }}, {{ 2, 2, 2, 0, 0 }},
43 {{ 2, 0, 2, 0, 0 }}, {{ 0, 0, 1, 0, 0 }}, {{ 1, 0, 1, 0, 0 }},
44 {{ 2, 0, 1, 0, 0 }}, {{ 0, 1, 2, 0, 0 }}, {{ 0, 1, 1, 0, 0 }},
45 {{ 1, 1, 1, 0, 0 }}, {{ 2, 1, 1, 0, 0 }}, {{ 1, 1, 2, 0, 0 }},
46 {{ 0, 2, 1, 0, 0 }}, {{ 1, 2, 1, 0, 0 }}, {{ 2, 2, 1, 0, 0 }},
47 {{ 2, 1, 2, 0, 0 }}, {{ 0, 0, 0, 2, 2 }}, {{ 1, 0, 0, 2, 2 }},
48 {{ 2, 0, 0, 2, 2 }}, {{ 0, 0, 2, 2, 2 }}, {{ 0, 0, 0, 1, 0 }},
49 {{ 1, 0, 0, 1, 0 }}, {{ 2, 0, 0, 1, 0 }}, {{ 0, 0, 2, 1, 0 }},
50 {{ 0, 1, 0, 1, 0 }}, {{ 1, 1, 0, 1, 0 }}, {{ 2, 1, 0, 1, 0 }},
51 {{ 1, 0, 2, 1, 0 }}, {{ 0, 2, 0, 1, 0 }}, {{ 1, 2, 0, 1, 0 }},
52 {{ 2, 2, 0, 1, 0 }}, {{ 2, 0, 2, 1, 0 }}, {{ 0, 2, 2, 1, 0 }},
53 {{ 1, 2, 2, 1, 0 }}, {{ 2, 2, 2, 1, 0 }}, {{ 2, 0, 2, 1, 0 }},
54 {{ 0, 0, 1, 1, 0 }}, {{ 1, 0, 1, 1, 0 }}, {{ 2, 0, 1, 1, 0 }},
55 {{ 0, 1, 2, 1, 0 }}, {{ 0, 1, 1, 1, 0 }}, {{ 1, 1, 1, 1, 0 }},
56 {{ 2, 1, 1, 1, 0 }}, {{ 1, 1, 2, 1, 0 }}, {{ 0, 2, 1, 1, 0 }},
57 {{ 1, 2, 1, 1, 0 }}, {{ 2, 2, 1, 1, 0 }}, {{ 2, 1, 2, 1, 0 }},
58 {{ 0, 1, 0, 2, 2 }}, {{ 1, 1, 0, 2, 2 }}, {{ 2, 1, 0, 2, 2 }},
59 {{ 1, 0, 2, 2, 2 }}, {{ 0, 0, 0, 2, 0 }}, {{ 1, 0, 0, 2, 0 }},
60 {{ 2, 0, 0, 2, 0 }}, {{ 0, 0, 2, 2, 0 }}, {{ 0, 1, 0, 2, 0 }},
61 {{ 1, 1, 0, 2, 0 }}, {{ 2, 1, 0, 2, 0 }}, {{ 1, 0, 2, 2, 0 }},
62 {{ 0, 2, 0, 2, 0 }}, {{ 1, 2, 0, 2, 0 }}, {{ 2, 2, 0, 2, 0 }},
63 {{ 2, 0, 2, 2, 0 }}, {{ 0, 2, 2, 2, 0 }}, {{ 1, 2, 2, 2, 0 }},
64 {{ 2, 2, 2, 2, 0 }}, {{ 2, 0, 2, 2, 0 }}, {{ 0, 0, 1, 2, 0 }},
65 {{ 1, 0, 1, 2, 0 }}, {{ 2, 0, 1, 2, 0 }}, {{ 0, 1, 2, 2, 0 }},
66 {{ 0, 1, 1, 2, 0 }}, {{ 1, 1, 1, 2, 0 }}, {{ 2, 1, 1, 2, 0 }},
67 {{ 1, 1, 2, 2, 0 }}, {{ 0, 2, 1, 2, 0 }}, {{ 1, 2, 1, 2, 0 }},
68 {{ 2, 2, 1, 2, 0 }}, {{ 2, 1, 2, 2, 0 }}, {{ 0, 2, 0, 2, 2 }},
69 {{ 1, 2, 0, 2, 2 }}, {{ 2, 2, 0, 2, 2 }}, {{ 2, 0, 2, 2, 2 }},
70 {{ 0, 0, 0, 0, 2 }}, {{ 1, 0, 0, 0, 2 }}, {{ 2, 0, 0, 0, 2 }},
71 {{ 0, 0, 2, 0, 2 }}, {{ 0, 1, 0, 0, 2 }}, {{ 1, 1, 0, 0, 2 }},
72 {{ 2, 1, 0, 0, 2 }}, {{ 1, 0, 2, 0, 2 }}, {{ 0, 2, 0, 0, 2 }},
73 {{ 1, 2, 0, 0, 2 }}, {{ 2, 2, 0, 0, 2 }}, {{ 2, 0, 2, 0, 2 }},
74 {{ 0, 2, 2, 0, 2 }}, {{ 1, 2, 2, 0, 2 }}, {{ 2, 2, 2, 0, 2 }},
75 {{ 2, 0, 2, 0, 2 }}, {{ 0, 0, 1, 0, 2 }}, {{ 1, 0, 1, 0, 2 }},
76 {{ 2, 0, 1, 0, 2 }}, {{ 0, 1, 2, 0, 2 }}, {{ 0, 1, 1, 0, 2 }},
77 {{ 1, 1, 1, 0, 2 }}, {{ 2, 1, 1, 0, 2 }}, {{ 1, 1, 2, 0, 2 }},
78 {{ 0, 2, 1, 0, 2 }}, {{ 1, 2, 1, 0, 2 }}, {{ 2, 2, 1, 0, 2 }},
79 {{ 2, 1, 2, 0, 2 }}, {{ 0, 2, 2, 2, 2 }}, {{ 1, 2, 2, 2, 2 }},
80 {{ 2, 2, 2, 2, 2 }}, {{ 2, 0, 2, 2, 2 }}, {{ 0, 0, 0, 0, 1 }},
81 {{ 1, 0, 0, 0, 1 }}, {{ 2, 0, 0, 0, 1 }}, {{ 0, 0, 2, 0, 1 }},
82 {{ 0, 1, 0, 0, 1 }}, {{ 1, 1, 0, 0, 1 }}, {{ 2, 1, 0, 0, 1 }},
83 {{ 1, 0, 2, 0, 1 }}, {{ 0, 2, 0, 0, 1 }}, {{ 1, 2, 0, 0, 1 }},
84 {{ 2, 2, 0, 0, 1 }}, {{ 2, 0, 2, 0, 1 }}, {{ 0, 2, 2, 0, 1 }},
85 {{ 1, 2, 2, 0, 1 }}, {{ 2, 2, 2, 0, 1 }}, {{ 2, 0, 2, 0, 1 }},
86 {{ 0, 0, 1, 0, 1 }}, {{ 1, 0, 1, 0, 1 }}, {{ 2, 0, 1, 0, 1 }},
87 {{ 0, 1, 2, 0, 1 }}, {{ 0, 1, 1, 0, 1 }}, {{ 1, 1, 1, 0, 1 }},
88 {{ 2, 1, 1, 0, 1 }}, {{ 1, 1, 2, 0, 1 }}, {{ 0, 2, 1, 0, 1 }},
89 {{ 1, 2, 1, 0, 1 }}, {{ 2, 2, 1, 0, 1 }}, {{ 2, 1, 2, 0, 1 }},
90 {{ 0, 0, 1, 2, 2 }}, {{ 1, 0, 1, 2, 2 }}, {{ 2, 0, 1, 2, 2 }},
91 {{ 0, 1, 2, 2, 2 }}, {{ 0, 0, 0, 1, 1 }}, {{ 1, 0, 0, 1, 1 }},
92 {{ 2, 0, 0, 1, 1 }}, {{ 0, 0, 2, 1, 1 }}, {{ 0, 1, 0, 1, 1 }},
93 {{ 1, 1, 0, 1, 1 }}, {{ 2, 1, 0, 1, 1 }}, {{ 1, 0, 2, 1, 1 }},
94 {{ 0, 2, 0, 1, 1 }}, {{ 1, 2, 0, 1, 1 }}, {{ 2, 2, 0, 1, 1 }},
95 {{ 2, 0, 2, 1, 1 }}, {{ 0, 2, 2, 1, 1 }}, {{ 1, 2, 2, 1, 1 }},
96 {{ 2, 2, 2, 1, 1 }}, {{ 2, 0, 2, 1, 1 }}, {{ 0, 0, 1, 1, 1 }},
97 {{ 1, 0, 1, 1, 1 }}, {{ 2, 0, 1, 1, 1 }}, {{ 0, 1, 2, 1, 1 }},
98 {{ 0, 1, 1, 1, 1 }}, {{ 1, 1, 1, 1, 1 }}, {{ 2, 1, 1, 1, 1 }},
99 {{ 1, 1, 2, 1, 1 }}, {{ 0, 2, 1, 1, 1 }}, {{ 1, 2, 1, 1, 1 }},
100 {{ 2, 2, 1, 1, 1 }}, {{ 2, 1, 2, 1, 1 }}, {{ 0, 1, 1, 2, 2 }},
101 {{ 1, 1, 1, 2, 2 }}, {{ 2, 1, 1, 2, 2 }}, {{ 1, 1, 2, 2, 2 }},
102 {{ 0, 0, 0, 2, 1 }}, {{ 1, 0, 0, 2, 1 }}, {{ 2, 0, 0, 2, 1 }},
103 {{ 0, 0, 2, 2, 1 }}, {{ 0, 1, 0, 2, 1 }}, {{ 1, 1, 0, 2, 1 }},
104 {{ 2, 1, 0, 2, 1 }}, {{ 1, 0, 2, 2, 1 }}, {{ 0, 2, 0, 2, 1 }},
105 {{ 1, 2, 0, 2, 1 }}, {{ 2, 2, 0, 2, 1 }}, {{ 2, 0, 2, 2, 1 }},
106 {{ 0, 2, 2, 2, 1 }}, {{ 1, 2, 2, 2, 1 }}, {{ 2, 2, 2, 2, 1 }},
107 {{ 2, 0, 2, 2, 1 }}, {{ 0, 0, 1, 2, 1 }}, {{ 1, 0, 1, 2, 1 }},
108 {{ 2, 0, 1, 2, 1 }}, {{ 0, 1, 2, 2, 1 }}, {{ 0, 1, 1, 2, 1 }},
109 {{ 1, 1, 1, 2, 1 }}, {{ 2, 1, 1, 2, 1 }}, {{ 1, 1, 2, 2, 1 }},
110 {{ 0, 2, 1, 2, 1 }}, {{ 1, 2, 1, 2, 1 }}, {{ 2, 2, 1, 2, 1 }},
111 {{ 2, 1, 2, 2, 1 }}, {{ 0, 2, 1, 2, 2 }}, {{ 1, 2, 1, 2, 2 }},
112 {{ 2, 2, 1, 2, 2 }}, {{ 2, 1, 2, 2, 2 }}, {{ 0, 0, 0, 1, 2 }},
113 {{ 1, 0, 0, 1, 2 }}, {{ 2, 0, 0, 1, 2 }}, {{ 0, 0, 2, 1, 2 }},
114 {{ 0, 1, 0, 1, 2 }}, {{ 1, 1, 0, 1, 2 }}, {{ 2, 1, 0, 1, 2 }},
115 {{ 1, 0, 2, 1, 2 }}, {{ 0, 2, 0, 1, 2 }}, {{ 1, 2, 0, 1, 2 }},
116 {{ 2, 2, 0, 1, 2 }}, {{ 2, 0, 2, 1, 2 }}, {{ 0, 2, 2, 1, 2 }},
117 {{ 1, 2, 2, 1, 2 }}, {{ 2, 2, 2, 1, 2 }}, {{ 2, 0, 2, 1, 2 }},
118 {{ 0, 0, 1, 1, 2 }}, {{ 1, 0, 1, 1, 2 }}, {{ 2, 0, 1, 1, 2 }},
119 {{ 0, 1, 2, 1, 2 }}, {{ 0, 1, 1, 1, 2 }}, {{ 1, 1, 1, 1, 2 }},
120 {{ 2, 1, 1, 1, 2 }}, {{ 1, 1, 2, 1, 2 }}, {{ 0, 2, 1, 1, 2 }},
121 {{ 1, 2, 1, 1, 2 }}, {{ 2, 2, 1, 1, 2 }}, {{ 2, 1, 2, 1, 2 }},
122 {{ 0, 2, 2, 2, 2 }}, {{ 1, 2, 2, 2, 2 }}, {{ 2, 2, 2, 2, 2 }},
123 {{ 2, 1, 2, 2, 2 }}
124 };
125
126 static const std::array<int, 3> kQuintEncodings[128] = {
127 {{ 0, 0, 0 }}, {{ 1, 0, 0 }}, {{ 2, 0, 0 }}, {{ 3, 0, 0 }}, {{ 4, 0, 0 }},
128 {{ 0, 4, 0 }}, {{ 4, 4, 0 }}, {{ 4, 4, 4 }}, {{ 0, 1, 0 }}, {{ 1, 1, 0 }},
129 {{ 2, 1, 0 }}, {{ 3, 1, 0 }}, {{ 4, 1, 0 }}, {{ 1, 4, 0 }}, {{ 4, 4, 1 }},
130 {{ 4, 4, 4 }}, {{ 0, 2, 0 }}, {{ 1, 2, 0 }}, {{ 2, 2, 0 }}, {{ 3, 2, 0 }},
131 {{ 4, 2, 0 }}, {{ 2, 4, 0 }}, {{ 4, 4, 2 }}, {{ 4, 4, 4 }}, {{ 0, 3, 0 }},
132 {{ 1, 3, 0 }}, {{ 2, 3, 0 }}, {{ 3, 3, 0 }}, {{ 4, 3, 0 }}, {{ 3, 4, 0 }},
133 {{ 4, 4, 3 }}, {{ 4, 4, 4 }}, {{ 0, 0, 1 }}, {{ 1, 0, 1 }}, {{ 2, 0, 1 }},
134 {{ 3, 0, 1 }}, {{ 4, 0, 1 }}, {{ 0, 4, 1 }}, {{ 4, 0, 4 }}, {{ 0, 4, 4 }},
135 {{ 0, 1, 1 }}, {{ 1, 1, 1 }}, {{ 2, 1, 1 }}, {{ 3, 1, 1 }}, {{ 4, 1, 1 }},
136 {{ 1, 4, 1 }}, {{ 4, 1, 4 }}, {{ 1, 4, 4 }}, {{ 0, 2, 1 }}, {{ 1, 2, 1 }},
137 {{ 2, 2, 1 }}, {{ 3, 2, 1 }}, {{ 4, 2, 1 }}, {{ 2, 4, 1 }}, {{ 4, 2, 4 }},
138 {{ 2, 4, 4 }}, {{ 0, 3, 1 }}, {{ 1, 3, 1 }}, {{ 2, 3, 1 }}, {{ 3, 3, 1 }},
139 {{ 4, 3, 1 }}, {{ 3, 4, 1 }}, {{ 4, 3, 4 }}, {{ 3, 4, 4 }}, {{ 0, 0, 2 }},
140 {{ 1, 0, 2 }}, {{ 2, 0, 2 }}, {{ 3, 0, 2 }}, {{ 4, 0, 2 }}, {{ 0, 4, 2 }},
141 {{ 2, 0, 4 }}, {{ 3, 0, 4 }}, {{ 0, 1, 2 }}, {{ 1, 1, 2 }}, {{ 2, 1, 2 }},
142 {{ 3, 1, 2 }}, {{ 4, 1, 2 }}, {{ 1, 4, 2 }}, {{ 2, 1, 4 }}, {{ 3, 1, 4 }},
143 {{ 0, 2, 2 }}, {{ 1, 2, 2 }}, {{ 2, 2, 2 }}, {{ 3, 2, 2 }}, {{ 4, 2, 2 }},
144 {{ 2, 4, 2 }}, {{ 2, 2, 4 }}, {{ 3, 2, 4 }}, {{ 0, 3, 2 }}, {{ 1, 3, 2 }},
145 {{ 2, 3, 2 }}, {{ 3, 3, 2 }}, {{ 4, 3, 2 }}, {{ 3, 4, 2 }}, {{ 2, 3, 4 }},
146 {{ 3, 3, 4 }}, {{ 0, 0, 3 }}, {{ 1, 0, 3 }}, {{ 2, 0, 3 }}, {{ 3, 0, 3 }},
147 {{ 4, 0, 3 }}, {{ 0, 4, 3 }}, {{ 0, 0, 4 }}, {{ 1, 0, 4 }}, {{ 0, 1, 3 }},
148 {{ 1, 1, 3 }}, {{ 2, 1, 3 }}, {{ 3, 1, 3 }}, {{ 4, 1, 3 }}, {{ 1, 4, 3 }},
149 {{ 0, 1, 4 }}, {{ 1, 1, 4 }}, {{ 0, 2, 3 }}, {{ 1, 2, 3 }}, {{ 2, 2, 3 }},
150 {{ 3, 2, 3 }}, {{ 4, 2, 3 }}, {{ 2, 4, 3 }}, {{ 0, 2, 4 }}, {{ 1, 2, 4 }},
151 {{ 0, 3, 3 }}, {{ 1, 3, 3 }}, {{ 2, 3, 3 }}, {{ 3, 3, 3 }}, {{ 4, 3, 3 }},
152 {{ 3, 4, 3 }}, {{ 0, 3, 4 }}, {{ 1, 3, 4 }}
153 };
154
155 // A cached table containing the max ranges for values encoded using ASTC's
156 // Bounded Integer Sequence Encoding. These are the numbers between 1 and 255
157 // that can be represented exactly as a number in the ranges
158 // [0, 2^k), [0, 3 * 2^k), and [0, 5 * 2^k).
__anon209d7c200202() 159 static const std::array<int, kNumPossibleRanges> kMaxRanges = []() {
160 std::array<int, kNumPossibleRanges> ranges;
161
162 // Initialize the table that we need for determining value encodings.
163 auto next_max_range = ranges.begin();
164 auto add_val = [&next_max_range](int val) {
165 if (val <= 0 || (1 << kLog2MaxRangeForBits) <= val) {
166 return;
167 }
168
169 *(next_max_range++) = val;
170 };
171
172 for (int i = 0; i <= kLog2MaxRangeForBits; ++i) {
173 add_val(3 * (1 << i) - 1);
174 add_val(5 * (1 << i) - 1);
175 add_val((1 << i) - 1);
176 }
177
178 assert(std::distance(next_max_range, ranges.end()) == 0);
179 std::sort(ranges.begin(), ranges.end());
180 return ranges;
181 }();
182
183 // Returns true if x == 0 or if x is a power of two. This function is only used
184 // in the GetCountsForRange function, where we need to have it return true
185 // on zero since we can have single trit/quint ISE encodings according to
186 // Table C.2.7.
187 template<typename T,
188 typename std::enable_if<std::is_integral<T>::value, T>::type = 0>
IsPow2(T x)189 inline constexpr bool IsPow2(T x) { return (x & (x - 1)) == 0; }
190
191 // For the ISE block encoding, these arrays determine how many bits are
192 // used after each value to store the interleaved quint/trit block.
193 const int kInterleavedQuintBits[3] = { 3, 2, 2 };
194 const int kInterleavedTritBits[5] = { 2, 2, 1, 2, 1 };
195
196 // Some template meta programming to get around the fact that MSVC
197 // will not allow (ValRange == 5) ? 3 : 5 as a template parameter
198 template<int ValRange>
199 struct DecodeBlockSize {
200 enum { value = (ValRange == 5 ? 3 : 5) };
201 };
202
203 // Decodes either a trit or quint block using the BISE (Bounded Integer Sequence
204 // Encoding) defined in Section C.2.12 of the ASTC specification. ValRange is
205 // expected to be either 3 or 5 depending on whether or not we're encoding trits
206 // or quints respectively. In other words, it is the remaining factor in whether
207 // the passed blocks contain encoded values of the form 3*2^k or 5*2^k.
208 template<int ValRange>
DecodeISEBlock(uint64_t block_bits,int num_bits)209 std::array<int, /* kNumVals = */ DecodeBlockSize<ValRange>::value> DecodeISEBlock(
210 uint64_t block_bits, int num_bits) {
211 static_assert(ValRange == 3 || ValRange == 5,
212 "We only know about trits and quints");
213
214 // We either have three quints or five trits
215 constexpr const int kNumVals = (ValRange == 5) ? 3 : 5;
216
217 // Depending on whether or not we're using quints or trits will determine
218 // the positions of the interleaved bits in the encoded block.
219 constexpr const int* const kInterleavedBits =
220 (ValRange == 5) ? kInterleavedQuintBits : kInterleavedTritBits;
221
222 // Set up the bits for reading
223 base::BitStream<base::UInt128> block_bit_src(block_bits, sizeof(block_bits) * 8);
224
225 // Decode the block
226 std::array<int, kNumVals> m;
227 uint64_t encoded = 0;
228 uint32_t encoded_bits_read = 0;
229 for (int i = 0; i < kNumVals; ++i) {
230 {
231 uint64_t bits = 0;
232 const bool result = block_bit_src.GetBits(num_bits, &bits);
233 assert(result);
234 (void)result;
235
236 m[i] = static_cast<int>(bits);
237 }
238
239 uint64_t encoded_bits;
240 {
241 const bool result = block_bit_src.GetBits(kInterleavedBits[i], &encoded_bits);
242 assert(result);
243 (void)result;
244 }
245 encoded |= encoded_bits << encoded_bits_read;
246 encoded_bits_read += kInterleavedBits[i];
247 }
248
249 // Make sure that our encoded trit/quint doesn't exceed its bounds
250 assert(ValRange != 3 || encoded < 256);
251 assert(ValRange != 5 || encoded < 128);
252
253 const int* const kEncodings = (ValRange == 5) ?
254 kQuintEncodings[encoded].data() : kTritEncodings[encoded].data();
255
256 std::array<int, kNumVals> result;
257 for (int i = 0; i < kNumVals; ++i) {
258 assert(m[i] < 1 << num_bits);
259 result[i] = kEncodings[i] << num_bits | m[i];
260 }
261 return result;
262 }
263
264 // Encode a single trit or quint block using the BISE (Bounded Integer Sequence
265 // Encoding) defined in Section C.2.12 of the ASTC specification. ValRange is
266 // expected to be either 3 or 5 depending on whether or not we're encoding trits
267 // or quints respectively. In other words, it is the remaining factor in whether
268 // the passed blocks contain encoded values of the form 3*2^k or 5*2^k.
269 template <int ValRange>
EncodeISEBlock(const std::vector<int> & vals,int bits_per_val,base::BitStream<base::UInt128> * bit_sink)270 void EncodeISEBlock(const std::vector<int>& vals, int bits_per_val,
271 base::BitStream<base::UInt128>* bit_sink) {
272 static_assert(ValRange == 3 || ValRange == 5,
273 "We only know about trits and quints");
274
275 // We either have three quints or five trits
276 constexpr const int kNumVals = (ValRange == 5) ? 3 : 5;
277
278 // Three quints in seven bits or five trits in eight bits
279 constexpr const int kNumEncodedBitsPerBlock = (ValRange == 5) ? 7 : 8;
280
281 // Depending on whether or not we're using quints or trits will determine
282 // the positions of the interleaved bits in the encoding
283 constexpr const int* const kInterleavedBits =
284 (ValRange == 5) ? kInterleavedQuintBits : kInterleavedTritBits;
285
286 // ISE blocks can only have up to a specific number of values...
287 assert(vals.size() <= kNumVals);
288
289 // Split up into bits and non bits. Non bits are used to find the quint/trit
290 // encoding that we need.
291 std::array<int, kNumVals> non_bits = {{ 0 }};
292 std::array<int, kNumVals> bits = {{ 0 }};
293 for (size_t i = 0; i < vals.size(); ++i) {
294 bits[i] = vals[i] & ((1 << bits_per_val) - 1);
295 non_bits[i] = vals[i] >> bits_per_val;
296 assert(non_bits[i] < ValRange);
297 }
298
299 // We only need to add as many bits as necessary, so let's limit it based
300 // on the computation described in Section C.2.22 of the ASTC specification
301 const int total_num_bits =
302 int(((vals.size() * kNumEncodedBitsPerBlock + kNumVals - 1) / kNumVals)
303 + vals.size() * bits_per_val);
304 int bits_added = 0;
305
306 // The number of bits used for the quint/trit encoding is necessary to know
307 // in order to properly select the encoding we need to represent.
308 int num_encoded_bits = 0;
309 for (int i = 0; i < kNumVals; ++i) {
310 bits_added += bits_per_val;
311 if (bits_added >= total_num_bits) {
312 break;
313 }
314
315 num_encoded_bits += kInterleavedBits[i];
316 bits_added += kInterleavedBits[i];
317 if (bits_added >= total_num_bits) {
318 break;
319 }
320 }
321 bits_added = 0;
322 assert(num_encoded_bits <= kNumEncodedBitsPerBlock);
323
324 // TODO(google): The faster way to do this would be to construct trees out
325 // of the quint/trit encoding patterns, or just invert the decoding logic.
326 // Here we go from the end backwards because it makes our tests are more
327 // deterministic.
328 int non_bit_encoding = -1;
329 for (int j = (1 << num_encoded_bits) - 1; j >= 0; --j) {
330 bool matches = true;
331
332 // We don't need to match all trits here, just the ones that correspond
333 // to the values that we passed in
334 for (size_t i = 0; i < kNumVals; ++i) {
335 if ((ValRange == 5 && kQuintEncodings[j][i] != non_bits[i]) ||
336 (ValRange == 3 && kTritEncodings[j][i] != non_bits[i])) {
337 matches = false;
338 break;
339 }
340 }
341
342 if (matches) {
343 non_bit_encoding = j;
344 break;
345 }
346 }
347
348 assert(non_bit_encoding >= 0);
349
350 // Now pack the bits into the block
351 for (size_t i = 0; i < vals.size(); ++i) {
352 // First add the base bits for this value
353 if (bits_added + bits_per_val <= total_num_bits) {
354 bit_sink->PutBits(bits[i], bits_per_val);
355 bits_added += bits_per_val;
356 }
357
358 // Now add the interleaved bits from the quint/trit
359 int num_int_bits = kInterleavedBits[i];
360 int int_bits = non_bit_encoding & ((1 << num_int_bits) - 1);
361 if (bits_added + num_int_bits <= total_num_bits) {
362 bit_sink->PutBits(int_bits, num_int_bits);
363 bits_added += num_int_bits;
364 non_bit_encoding >>= num_int_bits;
365 }
366 }
367 }
368
CHECK_COUNTS(int trits,int quints)369 inline void CHECK_COUNTS(int trits, int quints) {
370 assert(trits == 0 || quints == 0); // Either trits or quints
371 assert(trits == 0 || trits == 1); // At most one trit
372 assert(quints == 0 || quints == 1); // At most one quint
373 (void)trits; (void)quints;
374 }
375
376 } // namespace
377
378 ////////////////////////////////////////////////////////////////////////////////
379
ISERangeBegin()380 std::array<int, kNumPossibleRanges>::const_iterator ISERangeBegin() {
381 return kMaxRanges.cbegin();
382 }
383
ISERangeEnd()384 std::array<int, kNumPossibleRanges>::const_iterator ISERangeEnd() {
385 return kMaxRanges.cend();
386 }
387
GetCountsForRange(int range,int * const trits,int * const quints,int * const bits)388 void IntegerSequenceCodec::GetCountsForRange(
389 int range, int* const trits, int* const quints, int* const bits) {
390 // Make sure the passed pointers are valid
391 assert(trits != nullptr);
392 assert(quints != nullptr);
393 assert(bits != nullptr);
394
395 // These are generally errors -- there should never be any ASTC values
396 // outside of this range
397 UTILS_RELEASE_ASSERT(range > 0);
398 UTILS_RELEASE_ASSERT(range < 1 << kLog2MaxRangeForBits);
399
400 *bits = 0;
401 *trits = 0;
402 *quints = 0;
403
404 // Search through the numbers of the form 2^n, 3 * 2^n and 5 * 2^n
405 const int max_vals_for_range =
406 *std::lower_bound(kMaxRanges.begin(), kMaxRanges.end(), range) + 1;
407
408 // Make sure we found something
409 assert(max_vals_for_range > 1);
410
411 // Find out what kind of range it is
412 if ((max_vals_for_range % 3 == 0) && IsPow2(max_vals_for_range / 3)) {
413 *bits = base::Log2Floor(max_vals_for_range / 3);
414 *trits = 1;
415 *quints = 0;
416 } else if ((max_vals_for_range % 5 == 0) && IsPow2(max_vals_for_range / 5)) {
417 *bits = base::Log2Floor(max_vals_for_range / 5);
418 *trits = 0;
419 *quints = 1;
420 } else if (IsPow2(max_vals_for_range)) {
421 *bits = base::Log2Floor(max_vals_for_range);
422 *trits = 0;
423 *quints = 0;
424 }
425
426 // If we set any of these values then we're done.
427 if ((*bits | *trits | *quints) != 0) {
428 CHECK_COUNTS(*trits, *quints);
429 }
430 }
431
432 // Returns the overall bit count for a range of val_count values encoded
433 // using the specified number of trits, quints and straight bits (respectively)
GetBitCount(int num_vals,int trits,int quints,int bits)434 int IntegerSequenceCodec::GetBitCount(int num_vals,
435 int trits, int quints, int bits) {
436 CHECK_COUNTS(trits, quints);
437
438 // See section C.2.22 for the formula used here.
439 const int trit_bit_count = ((num_vals * 8 * trits) + 4) / 5;
440 const int quint_bit_count = ((num_vals * 7 * quints) + 2) / 3;
441 const int base_bit_count = num_vals * bits;
442 return trit_bit_count + quint_bit_count + base_bit_count;
443 }
444
IntegerSequenceCodec(int range)445 IntegerSequenceCodec::IntegerSequenceCodec(int range) {
446 int trits, quints, bits;
447 GetCountsForRange(range, &trits, &quints, &bits);
448 InitializeWithCounts(trits, quints, bits);
449 }
450
IntegerSequenceCodec(int trits,int quints,int bits)451 IntegerSequenceCodec::IntegerSequenceCodec(
452 int trits, int quints, int bits) {
453 InitializeWithCounts(trits, quints, bits);
454 }
455
InitializeWithCounts(int trits,int quints,int bits)456 void IntegerSequenceCodec::InitializeWithCounts(
457 int trits, int quints, int bits) {
458 CHECK_COUNTS(trits, quints);
459
460 if (trits > 0) {
461 encoding_ = EncodingMode::kTritEncoding;
462 } else if (quints > 0) {
463 encoding_ = EncodingMode::kQuintEncoding;
464 } else {
465 encoding_ = EncodingMode::kBitEncoding;
466 }
467
468 bits_ = bits;
469 }
470
NumValsPerBlock() const471 int IntegerSequenceCodec::NumValsPerBlock() const {
472 const std::array<int, 3> kNumValsByEncoding = {{ 5, 3, 1 }};
473 return kNumValsByEncoding[static_cast<int>(encoding_)];
474 }
475
EncodedBlockSize() const476 int IntegerSequenceCodec::EncodedBlockSize() const {
477 const std::array<int, 3> kExtraBlockSizeByEncoding = {{ 8, 7, 0 }};
478 const int num_vals = NumValsPerBlock();
479 return kExtraBlockSizeByEncoding[static_cast<int>(encoding_)]
480 + num_vals * bits_;
481 }
482
Decode(int num_vals,base::BitStream<base::UInt128> * bit_src) const483 std::vector<int> IntegerSequenceDecoder::Decode(
484 int num_vals, base::BitStream<base::UInt128> *bit_src) const {
485 int trits = (encoding_ == kTritEncoding)? 1 : 0;
486 int quints = (encoding_ == kQuintEncoding)? 1 : 0;
487 const int total_num_bits = GetBitCount(num_vals, trits, quints, bits_);
488 const int bits_per_block = EncodedBlockSize();
489 assert(bits_per_block < 64);
490
491 int bits_left = total_num_bits;
492 std::vector<int> result;
493 while (bits_left > 0) {
494 uint64_t block_bits;
495 {
496 const bool result0 = bit_src->GetBits(std::min(bits_left, bits_per_block), &block_bits);
497 assert(result0);
498 (void)result0;
499 }
500
501 switch (encoding_) {
502 case kTritEncoding: {
503 auto trit_vals = DecodeISEBlock<3>(block_bits, bits_);
504 result.insert(result.end(), trit_vals.begin(), trit_vals.end());
505 }
506 break;
507
508 case kQuintEncoding: {
509 auto quint_vals = DecodeISEBlock<5>(block_bits, bits_);
510 result.insert(result.end(), quint_vals.begin(), quint_vals.end());
511 }
512 break;
513
514 case kBitEncoding:
515 result.push_back(static_cast<int>(block_bits));
516 break;
517 }
518
519 bits_left -= bits_per_block;
520 }
521
522 // Resize result to only contain as many values as requested
523 assert(result.size() >= static_cast<size_t>(num_vals));
524 result.resize(num_vals);
525
526 // Encoded all the values
527 return result;
528 }
529
Encode(base::BitStream<base::UInt128> * bit_sink) const530 void IntegerSequenceEncoder::Encode(base::BitStream<base::UInt128>* bit_sink) const {
531 // Go through all of the values and chop them up into blocks. The properties
532 // of the trit and quint encodings mean that if we need to encode fewer values
533 // in a block than the number of values encoded in the block then we need to
534 // consider the last few values to be zero.
535
536 auto next_val = vals_.begin();
537 while (next_val != vals_.end()) {
538 switch (encoding_) {
539 case kTritEncoding: {
540 std::vector<int> trit_vals;
541 for (int i = 0; i < 5; ++i) {
542 if (next_val != vals_.end()) {
543 trit_vals.push_back(*next_val);
544 ++next_val;
545 }
546 }
547
548 EncodeISEBlock<3>(trit_vals, bits_, bit_sink);
549 }
550 break;
551
552 case kQuintEncoding: {
553 std::vector<int> quint_vals;
554 for (int i = 0; i < 3; ++i) {
555 if (next_val != vals_.end()) {
556 quint_vals.push_back(*next_val);
557 ++next_val;
558 }
559 }
560
561 EncodeISEBlock<5>(quint_vals, bits_, bit_sink);
562 }
563 break;
564
565 case kBitEncoding: {
566 bit_sink->PutBits(*next_val, EncodedBlockSize());
567 ++next_val;
568 }
569 break;
570 }
571 }
572 }
573
574 } // namespace astc_codec
575