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).
__anon31dd9aee0202() 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
235 m[i] = static_cast<int>(bits);
236 }
237
238 uint64_t encoded_bits;
239 {
240 const bool result = block_bit_src.GetBits(kInterleavedBits[i], &encoded_bits);
241 assert(result);
242 }
243 encoded |= encoded_bits << encoded_bits_read;
244 encoded_bits_read += kInterleavedBits[i];
245 }
246
247 // Make sure that our encoded trit/quint doesn't exceed its bounds
248 assert(ValRange != 3 || encoded < 256);
249 assert(ValRange != 5 || encoded < 128);
250
251 const int* const kEncodings = (ValRange == 5) ?
252 kQuintEncodings[encoded].data() : kTritEncodings[encoded].data();
253
254 std::array<int, kNumVals> result;
255 for (int i = 0; i < kNumVals; ++i) {
256 assert(m[i] < 1 << num_bits);
257 result[i] = kEncodings[i] << num_bits | m[i];
258 }
259 return result;
260 }
261
262 // Encode a single trit or quint block using the BISE (Bounded Integer Sequence
263 // Encoding) defined in Section C.2.12 of the ASTC specification. ValRange is
264 // expected to be either 3 or 5 depending on whether or not we're encoding trits
265 // or quints respectively. In other words, it is the remaining factor in whether
266 // the passed blocks contain encoded values of the form 3*2^k or 5*2^k.
267 template <int ValRange>
EncodeISEBlock(const std::vector<int> & vals,int bits_per_val,base::BitStream<base::UInt128> * bit_sink)268 void EncodeISEBlock(const std::vector<int>& vals, int bits_per_val,
269 base::BitStream<base::UInt128>* bit_sink) {
270 static_assert(ValRange == 3 || ValRange == 5,
271 "We only know about trits and quints");
272
273 // We either have three quints or five trits
274 constexpr const int kNumVals = (ValRange == 5) ? 3 : 5;
275
276 // Three quints in seven bits or five trits in eight bits
277 constexpr const int kNumEncodedBitsPerBlock = (ValRange == 5) ? 7 : 8;
278
279 // Depending on whether or not we're using quints or trits will determine
280 // the positions of the interleaved bits in the encoding
281 constexpr const int* const kInterleavedBits =
282 (ValRange == 5) ? kInterleavedQuintBits : kInterleavedTritBits;
283
284 // ISE blocks can only have up to a specific number of values...
285 assert(vals.size() <= kNumVals);
286
287 // Split up into bits and non bits. Non bits are used to find the quint/trit
288 // encoding that we need.
289 std::array<int, kNumVals> non_bits = {{ 0 }};
290 std::array<int, kNumVals> bits = {{ 0 }};
291 for (size_t i = 0; i < vals.size(); ++i) {
292 bits[i] = vals[i] & ((1 << bits_per_val) - 1);
293 non_bits[i] = vals[i] >> bits_per_val;
294 assert(non_bits[i] < ValRange);
295 }
296
297 // We only need to add as many bits as necessary, so let's limit it based
298 // on the computation described in Section C.2.22 of the ASTC specification
299 const int total_num_bits =
300 ((vals.size() * kNumEncodedBitsPerBlock + kNumVals - 1) / kNumVals)
301 + vals.size() * bits_per_val;
302 int bits_added = 0;
303
304 // The number of bits used for the quint/trit encoding is necessary to know
305 // in order to properly select the encoding we need to represent.
306 int num_encoded_bits = 0;
307 for (int i = 0; i < kNumVals; ++i) {
308 bits_added += bits_per_val;
309 if (bits_added >= total_num_bits) {
310 break;
311 }
312
313 num_encoded_bits += kInterleavedBits[i];
314 bits_added += kInterleavedBits[i];
315 if (bits_added >= total_num_bits) {
316 break;
317 }
318 }
319 bits_added = 0;
320 assert(num_encoded_bits <= kNumEncodedBitsPerBlock);
321
322 // TODO(google): The faster way to do this would be to construct trees out
323 // of the quint/trit encoding patterns, or just invert the decoding logic.
324 // Here we go from the end backwards because it makes our tests are more
325 // deterministic.
326 int non_bit_encoding = -1;
327 for (int j = (1 << num_encoded_bits) - 1; j >= 0; --j) {
328 bool matches = true;
329
330 // We don't need to match all trits here, just the ones that correspond
331 // to the values that we passed in
332 for (size_t i = 0; i < kNumVals; ++i) {
333 if ((ValRange == 5 && kQuintEncodings[j][i] != non_bits[i]) ||
334 (ValRange == 3 && kTritEncodings[j][i] != non_bits[i])) {
335 matches = false;
336 break;
337 }
338 }
339
340 if (matches) {
341 non_bit_encoding = j;
342 break;
343 }
344 }
345
346 assert(non_bit_encoding >= 0);
347
348 // Now pack the bits into the block
349 for (int i = 0; i < vals.size(); ++i) {
350 // First add the base bits for this value
351 if (bits_added + bits_per_val <= total_num_bits) {
352 bit_sink->PutBits(bits[i], bits_per_val);
353 bits_added += bits_per_val;
354 }
355
356 // Now add the interleaved bits from the quint/trit
357 int num_int_bits = kInterleavedBits[i];
358 int int_bits = non_bit_encoding & ((1 << num_int_bits) - 1);
359 if (bits_added + num_int_bits <= total_num_bits) {
360 bit_sink->PutBits(int_bits, num_int_bits);
361 bits_added += num_int_bits;
362 non_bit_encoding >>= num_int_bits;
363 }
364 }
365 }
366
CHECK_COUNTS(int trits,int quints)367 inline void CHECK_COUNTS(int trits, int quints) {
368 assert(trits == 0 || quints == 0); // Either trits or quints
369 assert(trits == 0 || trits == 1); // At most one trit
370 assert(quints == 0 || quints == 1); // At most one quint
371 }
372
373 } // namespace
374
375 ////////////////////////////////////////////////////////////////////////////////
376
ISERangeBegin()377 std::array<int, kNumPossibleRanges>::const_iterator ISERangeBegin() {
378 return kMaxRanges.cbegin();
379 }
380
ISERangeEnd()381 std::array<int, kNumPossibleRanges>::const_iterator ISERangeEnd() {
382 return kMaxRanges.cend();
383 }
384
GetCountsForRange(int range,int * const trits,int * const quints,int * const bits)385 void IntegerSequenceCodec::GetCountsForRange(
386 int range, int* const trits, int* const quints, int* const bits) {
387 // Make sure the passed pointers are valid
388 assert(trits != nullptr);
389 assert(quints != nullptr);
390 assert(bits != nullptr);
391
392 // These are generally errors -- there should never be any ASTC values
393 // outside of this range
394 UTILS_RELEASE_ASSERT(range > 0);
395 UTILS_RELEASE_ASSERT(range < 1 << kLog2MaxRangeForBits);
396
397 *bits = 0;
398 *trits = 0;
399 *quints = 0;
400
401 // Search through the numbers of the form 2^n, 3 * 2^n and 5 * 2^n
402 const int max_vals_for_range =
403 *std::lower_bound(kMaxRanges.begin(), kMaxRanges.end(), range) + 1;
404
405 // Make sure we found something
406 assert(max_vals_for_range > 1);
407
408 // Find out what kind of range it is
409 if ((max_vals_for_range % 3 == 0) && IsPow2(max_vals_for_range / 3)) {
410 *bits = base::Log2Floor(max_vals_for_range / 3);
411 *trits = 1;
412 *quints = 0;
413 } else if ((max_vals_for_range % 5 == 0) && IsPow2(max_vals_for_range / 5)) {
414 *bits = base::Log2Floor(max_vals_for_range / 5);
415 *trits = 0;
416 *quints = 1;
417 } else if (IsPow2(max_vals_for_range)) {
418 *bits = base::Log2Floor(max_vals_for_range);
419 *trits = 0;
420 *quints = 0;
421 }
422
423 // If we set any of these values then we're done.
424 if ((*bits | *trits | *quints) != 0) {
425 CHECK_COUNTS(*trits, *quints);
426 }
427 }
428
429 // Returns the overall bit count for a range of val_count values encoded
430 // using the specified number of trits, quints and straight bits (respectively)
GetBitCount(int num_vals,int trits,int quints,int bits)431 int IntegerSequenceCodec::GetBitCount(int num_vals,
432 int trits, int quints, int bits) {
433 CHECK_COUNTS(trits, quints);
434
435 // See section C.2.22 for the formula used here.
436 const int trit_bit_count = ((num_vals * 8 * trits) + 4) / 5;
437 const int quint_bit_count = ((num_vals * 7 * quints) + 2) / 3;
438 const int base_bit_count = num_vals * bits;
439 return trit_bit_count + quint_bit_count + base_bit_count;
440 }
441
IntegerSequenceCodec(int range)442 IntegerSequenceCodec::IntegerSequenceCodec(int range) {
443 int trits, quints, bits;
444 GetCountsForRange(range, &trits, &quints, &bits);
445 InitializeWithCounts(trits, quints, bits);
446 }
447
IntegerSequenceCodec(int trits,int quints,int bits)448 IntegerSequenceCodec::IntegerSequenceCodec(
449 int trits, int quints, int bits) {
450 InitializeWithCounts(trits, quints, bits);
451 }
452
InitializeWithCounts(int trits,int quints,int bits)453 void IntegerSequenceCodec::InitializeWithCounts(
454 int trits, int quints, int bits) {
455 CHECK_COUNTS(trits, quints);
456
457 if (trits > 0) {
458 encoding_ = EncodingMode::kTritEncoding;
459 } else if (quints > 0) {
460 encoding_ = EncodingMode::kQuintEncoding;
461 } else {
462 encoding_ = EncodingMode::kBitEncoding;
463 }
464
465 bits_ = bits;
466 }
467
NumValsPerBlock() const468 int IntegerSequenceCodec::NumValsPerBlock() const {
469 const std::array<int, 3> kNumValsByEncoding = {{ 5, 3, 1 }};
470 return kNumValsByEncoding[static_cast<int>(encoding_)];
471 }
472
EncodedBlockSize() const473 int IntegerSequenceCodec::EncodedBlockSize() const {
474 const std::array<int, 3> kExtraBlockSizeByEncoding = {{ 8, 7, 0 }};
475 const int num_vals = NumValsPerBlock();
476 return kExtraBlockSizeByEncoding[static_cast<int>(encoding_)]
477 + num_vals * bits_;
478 }
479
Decode(int num_vals,base::BitStream<base::UInt128> * bit_src) const480 std::vector<int> IntegerSequenceDecoder::Decode(
481 int num_vals, base::BitStream<base::UInt128> *bit_src) const {
482 int trits = (encoding_ == kTritEncoding)? 1 : 0;
483 int quints = (encoding_ == kQuintEncoding)? 1 : 0;
484 const int total_num_bits = GetBitCount(num_vals, trits, quints, bits_);
485 const int bits_per_block = EncodedBlockSize();
486 assert(bits_per_block < 64);
487
488 int bits_left = total_num_bits;
489 std::vector<int> result;
490 while (bits_left > 0) {
491 uint64_t block_bits;
492 {
493 const bool result = bit_src->GetBits(std::min(bits_left, bits_per_block), &block_bits);
494 assert(result);
495 }
496
497 switch (encoding_) {
498 case kTritEncoding: {
499 auto trit_vals = DecodeISEBlock<3>(block_bits, bits_);
500 result.insert(result.end(), trit_vals.begin(), trit_vals.end());
501 }
502 break;
503
504 case kQuintEncoding: {
505 auto quint_vals = DecodeISEBlock<5>(block_bits, bits_);
506 result.insert(result.end(), quint_vals.begin(), quint_vals.end());
507 }
508 break;
509
510 case kBitEncoding:
511 result.push_back(static_cast<int>(block_bits));
512 break;
513 }
514
515 bits_left -= bits_per_block;
516 }
517
518 // Resize result to only contain as many values as requested
519 assert(result.size() >= static_cast<size_t>(num_vals));
520 result.resize(num_vals);
521
522 // Encoded all the values
523 return result;
524 }
525
Encode(base::BitStream<base::UInt128> * bit_sink) const526 void IntegerSequenceEncoder::Encode(base::BitStream<base::UInt128>* bit_sink) const {
527 // Go through all of the values and chop them up into blocks. The properties
528 // of the trit and quint encodings mean that if we need to encode fewer values
529 // in a block than the number of values encoded in the block then we need to
530 // consider the last few values to be zero.
531
532 auto next_val = vals_.begin();
533 while (next_val != vals_.end()) {
534 switch (encoding_) {
535 case kTritEncoding: {
536 std::vector<int> trit_vals;
537 for (int i = 0; i < 5; ++i) {
538 if (next_val != vals_.end()) {
539 trit_vals.push_back(*next_val);
540 ++next_val;
541 }
542 }
543
544 EncodeISEBlock<3>(trit_vals, bits_, bit_sink);
545 }
546 break;
547
548 case kQuintEncoding: {
549 std::vector<int> quint_vals;
550 for (int i = 0; i < 3; ++i) {
551 if (next_val != vals_.end()) {
552 quint_vals.push_back(*next_val);
553 ++next_val;
554 }
555 }
556
557 EncodeISEBlock<5>(quint_vals, bits_, bit_sink);
558 }
559 break;
560
561 case kBitEncoding: {
562 bit_sink->PutBits(*next_val, EncodedBlockSize());
563 ++next_val;
564 }
565 break;
566 }
567 }
568 }
569
570 } // namespace astc_codec
571