| // Copyright 2018 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "src/decoder/quantization.h" |
| #include "src/base/math_utils.h" |
| |
| #include <algorithm> |
| #include <array> |
| #include <cassert> |
| #include <map> |
| #include <memory> |
| #include <vector> |
| |
| namespace astc_codec { |
| |
| namespace { |
| |
| // Trit unquantization procedure as described in Section C.2.13 |
| int GetUnquantizedTritValue(int trit, int bits, int range) { |
| int a = (bits & 1) ? 0x1FF : 0; |
| int b = 0, c = 0; |
| switch (range) { |
| case 5: { |
| b = 0; |
| c = 204; |
| } |
| break; |
| |
| case 11: { |
| int x = (bits >> 1) & 0x1; |
| b = (x << 1) | (x << 2) | (x << 4) | (x << 8); |
| c = 93; |
| } |
| break; |
| |
| case 23: { |
| int x = (bits >> 1) & 0x3; |
| b = x | (x << 2) | (x << 7); |
| c = 44; |
| } |
| break; |
| |
| case 47: { |
| int x = (bits >> 1) & 0x7; |
| b = x | (x << 6); |
| c = 22; |
| } |
| break; |
| |
| case 95: { |
| int x = (bits >> 1) & 0xF; |
| b = (x >> 2) | (x << 5); |
| c = 11; |
| } |
| break; |
| |
| case 191: { |
| int x = (bits >> 1) & 0x1F; |
| b = (x >> 4) | (x << 4); |
| c = 5; |
| } |
| break; |
| |
| default: |
| assert(false && "Illegal trit encoding"); |
| break; |
| } |
| |
| int t = trit * c + b; |
| t ^= a; |
| t = (a & 0x80) | (t >> 2); |
| return t; |
| } |
| |
| // Quint unquantization procedure as described in Section C.2.13 |
| int GetUnquantizedQuintValue(int quint, int bits, int range) { |
| int a = (bits & 1) ? 0x1FF : 0; |
| int b = 0, c = 0; |
| switch (range) { |
| case 9: { |
| b = 0; |
| c = 113; |
| } |
| break; |
| |
| case 19: { |
| int x = (bits >> 1) & 0x1; |
| b = (x << 2) | (x << 3) | (x << 8); |
| c = 54; |
| } |
| break; |
| |
| case 39: { |
| int x = (bits >> 1) & 0x3; |
| b = (x >> 1) | (x << 1) | (x << 7); |
| c = 26; |
| } |
| break; |
| |
| case 79: { |
| int x = (bits >> 1) & 0x7; |
| b = (x >> 1) | (x << 6); |
| c = 13; |
| } |
| break; |
| |
| case 159: { |
| int x = (bits >> 1) & 0xF; |
| b = (x >> 3) | (x << 5); |
| c = 6; |
| } |
| break; |
| |
| default: |
| assert(false && "Illegal quint encoding"); |
| break; |
| } |
| |
| int t = quint * c + b; |
| t ^= a; |
| t = (a & 0x80) | (t >> 2); |
| return t; |
| } |
| |
| // Trit unquantization procedure as described in Section C.2.17. In the code |
| // below, the variables a, b, and c correspond to the columns A, B, and C in |
| // the specification. |
| int GetUnquantizedTritWeight(int trit, int bits, int range) { |
| int a = (bits & 1) ? 0x7F : 0; |
| int b = 0, c = 0; |
| switch (range) { |
| case 2: |
| return (std::array<int, 3> {{ 0, 32, 63 }})[trit]; |
| |
| case 5: |
| c = 50; |
| b = 0; |
| break; |
| |
| case 11: { |
| c = 23; |
| b = (bits >> 1) & 1; |
| b |= (b << 2) | (b << 6); |
| } |
| break; |
| |
| case 23: { |
| c = 11; |
| b = (bits >> 1) & 0x3; |
| b |= (b << 5); |
| } |
| break; |
| |
| default: |
| assert(false && "Illegal trit encoding"); |
| break; |
| } |
| |
| int t = trit * c + b; |
| t ^= a; |
| t = (a & 0x20) | (t >> 2); |
| return t; |
| } |
| |
| // Quint unquantization procedure as described in Section C.2.17. In the code |
| // below, the variables a, b, and c correspond to the columns A, B, and C in |
| // the specification. |
| int GetUnquantizedQuintWeight(int quint, int bits, int range) { |
| int a = (bits & 1) ? 0x7F : 0; |
| int b = 0, c = 0; |
| switch (range) { |
| case 4: |
| return (std::array<int, 5> {{ 0, 16, 32, 47, 63 }})[quint]; |
| |
| case 9: |
| c = 28; |
| b = 0; |
| break; |
| |
| case 19: { |
| c = 13; |
| b = (bits >> 1) & 0x1; |
| b = (b << 1) | (b << 6); |
| } |
| break; |
| |
| default: |
| assert(false && "Illegal quint encoding"); |
| break; |
| } |
| |
| int t = quint * c + b; |
| t ^= a; |
| t = (a & 0x20) | (t >> 2); |
| return t; |
| } |
| |
| // A Quantization map allows us to convert to/from values that are quantized |
| // according to the ASTC spec. |
| class QuantizationMap { |
| public: |
| int Quantize(int x) const { |
| return x < quantization_map_.size() ? quantization_map_.at(x) : 0; |
| } |
| |
| int Unquantize(int x) const { |
| return x < unquantization_map_.size() ? unquantization_map_.at(x) : 0; |
| } |
| |
| protected: |
| QuantizationMap() { } |
| std::vector<int> quantization_map_; |
| std::vector<int> unquantization_map_; |
| |
| void GenerateQuantizationMap() { |
| assert(unquantization_map_.size() > 1); |
| quantization_map_.clear(); |
| |
| // TODO(google) For weights, we don't need quantization values all the |
| // way up to 256, but it doesn't hurt -- just wastes memory, but the code |
| // is much cleaner this way |
| for (int i = 0; i < 256; ++i) { |
| int best_idx = 0; |
| int best_idx_score = 256; |
| int idx = 0; |
| for (int unquantized_val : unquantization_map_) { |
| const int diff = i - unquantized_val; |
| const int idx_score = diff * diff; |
| if (idx_score < best_idx_score) { |
| best_idx = idx; |
| best_idx_score = idx_score; |
| } |
| idx++; |
| } |
| |
| quantization_map_.push_back(best_idx); |
| } |
| } |
| }; |
| |
| template<int (*UnquantizationFunc)(int, int, int)> |
| class TritQuantizationMap : public QuantizationMap { |
| public: |
| explicit TritQuantizationMap(int range) : QuantizationMap() { |
| assert((range + 1) % 3 == 0); |
| const int num_bits_pow_2 = (range + 1) / 3; |
| const int num_bits = |
| num_bits_pow_2 == 0 ? 0 : base::Log2Floor(num_bits_pow_2); |
| |
| for (int trit = 0; trit < 3; ++trit) { |
| for (int bits = 0; bits < (1 << num_bits); ++bits) { |
| unquantization_map_.push_back(UnquantizationFunc(trit, bits, range)); |
| } |
| } |
| |
| GenerateQuantizationMap(); |
| } |
| }; |
| |
| template<int (*UnquantizationFunc)(int, int, int)> |
| class QuintQuantizationMap : public QuantizationMap { |
| public: |
| explicit QuintQuantizationMap(int range) : QuantizationMap() { |
| assert((range + 1) % 5 == 0); |
| const int num_bits_pow_2 = (range + 1) / 5; |
| const int num_bits = |
| num_bits_pow_2 == 0 ? 0 : base::Log2Floor(num_bits_pow_2); |
| |
| for (int quint = 0; quint < 5; ++quint) { |
| for (int bits = 0; bits < (1 << num_bits); ++bits) { |
| unquantization_map_.push_back(UnquantizationFunc(quint, bits, range)); |
| } |
| } |
| |
| GenerateQuantizationMap(); |
| } |
| }; |
| |
| template<int TotalUnquantizedBits> |
| class BitQuantizationMap : public QuantizationMap { |
| public: |
| explicit BitQuantizationMap<TotalUnquantizedBits>(int range) |
| : QuantizationMap() { |
| // Make sure that if we're using bits then we have a positive power of two. |
| assert(base::CountOnes(range + 1) == 1); |
| |
| const int num_bits = base::Log2Floor(range + 1); |
| for (int bits = 0; bits <= range; ++bits) { |
| // Need to replicate bits until we fill up the bits |
| int unquantized = bits; |
| int num_unquantized_bits = num_bits; |
| while (num_unquantized_bits < TotalUnquantizedBits) { |
| const int num_dst_bits_to_shift_up = |
| std::min(num_bits, TotalUnquantizedBits - num_unquantized_bits); |
| const int num_src_bits_to_shift_down = |
| num_bits - num_dst_bits_to_shift_up; |
| unquantized <<= num_dst_bits_to_shift_up; |
| unquantized |= bits >> num_src_bits_to_shift_down; |
| num_unquantized_bits += num_dst_bits_to_shift_up; |
| } |
| assert(num_unquantized_bits == TotalUnquantizedBits); |
| |
| unquantization_map_.push_back(unquantized); |
| |
| // Fill half of the quantization map with the previous value for bits |
| // and the other half with the current value for bits |
| if (bits > 0) { |
| const int prev_unquant = unquantization_map_.at(bits - 1); |
| while (quantization_map_.size() <= (prev_unquant + unquantized) / 2) { |
| quantization_map_.push_back(bits - 1); |
| } |
| } |
| while (quantization_map_.size() <= unquantized) { |
| quantization_map_.push_back(bits); |
| } |
| } |
| |
| assert(quantization_map_.size() == 1 << TotalUnquantizedBits); |
| } |
| }; |
| |
| using QMap = std::shared_ptr<QuantizationMap>; |
| |
| // Returns the quantization map for quantizing color values in [0, 255] with the |
| // smallest range that can accommodate |r| |
| static const QuantizationMap* GetQuantMapForValueRange(int r) { |
| // Endpoint values can be quantized using bits, trits, or quints. Here we |
| // store the quantization maps for each of the ranges that are supported by |
| // such an encoding. That way we can choose the proper quantization procedure |
| // based on the range of values rather than by having complicated switches and |
| // logic. We must use a std::map here instead of a std::unordered_map because |
| // of the assumption made in std::upper_bound about the iterators being from a |
| // poset. |
| static const auto* const kASTCEndpointQuantization = new std::map<int, QMap> { |
| { 5, QMap(new TritQuantizationMap<GetUnquantizedTritValue>(5)) }, |
| { 7, QMap(new BitQuantizationMap<8>(7)) }, |
| { 9, QMap(new QuintQuantizationMap<GetUnquantizedQuintValue>(9)) }, |
| { 11, QMap(new TritQuantizationMap<GetUnquantizedTritValue>(11)) }, |
| { 15, QMap(new BitQuantizationMap<8>(15)) }, |
| { 19, QMap(new QuintQuantizationMap<GetUnquantizedQuintValue>(19)) }, |
| { 23, QMap(new TritQuantizationMap<GetUnquantizedTritValue>(23)) }, |
| { 31, QMap(new BitQuantizationMap<8>(31)) }, |
| { 39, QMap(new QuintQuantizationMap<GetUnquantizedQuintValue>(39)) }, |
| { 47, QMap(new TritQuantizationMap<GetUnquantizedTritValue>(47)) }, |
| { 63, QMap(new BitQuantizationMap<8>(63)) }, |
| { 79, QMap(new QuintQuantizationMap<GetUnquantizedQuintValue>(79)) }, |
| { 95, QMap(new TritQuantizationMap<GetUnquantizedTritValue>(95)) }, |
| { 127, QMap(new BitQuantizationMap<8>(127)) }, |
| { 159, QMap(new QuintQuantizationMap<GetUnquantizedQuintValue>(159)) }, |
| { 191, QMap(new TritQuantizationMap<GetUnquantizedTritValue>(191)) }, |
| { 255, QMap(new BitQuantizationMap<8>(255)) }, |
| }; |
| |
| assert(r < 256); |
| auto itr = kASTCEndpointQuantization->upper_bound(r); |
| if (itr != kASTCEndpointQuantization->begin()) { |
| return (--itr)->second.get(); |
| } |
| return nullptr; |
| } |
| |
| // Returns the quantization map for weight values in [0, 63] with the smallest |
| // range that can accommodate |r| |
| static const QuantizationMap* GetQuantMapForWeightRange(int r) { |
| // Similar to endpoint quantization, weights can also be stored using trits, |
| // quints, or bits. Here we store the quantization maps for each of the ranges |
| // that are supported by such an encoding. |
| static const auto* const kASTCWeightQuantization = new std::map<int, QMap> { |
| { 1, QMap(new BitQuantizationMap<6>(1)) }, |
| { 2, QMap(new TritQuantizationMap<GetUnquantizedTritWeight>(2)) }, |
| { 3, QMap(new BitQuantizationMap<6>(3)) }, |
| { 4, QMap(new QuintQuantizationMap<GetUnquantizedQuintWeight>(4)) }, |
| { 5, QMap(new TritQuantizationMap<GetUnquantizedTritWeight>(5)) }, |
| { 7, QMap(new BitQuantizationMap<6>(7)) }, |
| { 9, QMap(new QuintQuantizationMap<GetUnquantizedQuintWeight>(9)) }, |
| { 11, QMap(new TritQuantizationMap<GetUnquantizedTritWeight>(11)) }, |
| { 15, QMap(new BitQuantizationMap<6>(15)) }, |
| { 19, QMap(new QuintQuantizationMap<GetUnquantizedQuintWeight>(19)) }, |
| { 23, QMap(new TritQuantizationMap<GetUnquantizedTritWeight>(23)) }, |
| { 31, QMap(new BitQuantizationMap<6>(31)) }, |
| }; |
| |
| assert(r < 32); |
| auto itr = kASTCWeightQuantization->upper_bound(r); |
| if (itr != kASTCWeightQuantization->begin()) { |
| return (--itr)->second.get(); |
| } |
| return nullptr; |
| } |
| |
| } // namespace |
| |
| //////////////////////////////////////////////////////////////////////////////// |
| |
| int QuantizeCEValueToRange(int value, int range_max_value) { |
| assert(range_max_value >= kEndpointRangeMinValue); |
| assert(range_max_value <= 255); |
| assert(value >= 0); |
| assert(value <= 255); |
| |
| const QuantizationMap* map = GetQuantMapForValueRange(range_max_value); |
| return map ? map->Quantize(value) : 0; |
| } |
| |
| int UnquantizeCEValueFromRange(int value, int range_max_value) { |
| assert(range_max_value >= kEndpointRangeMinValue); |
| assert(range_max_value <= 255); |
| assert(value >= 0); |
| assert(value <= range_max_value); |
| |
| const QuantizationMap* map = GetQuantMapForValueRange(range_max_value); |
| return map ? map->Unquantize(value) : 0; |
| } |
| |
| int QuantizeWeightToRange(int weight, int range_max_value) { |
| assert(range_max_value >= 1); |
| assert(range_max_value <= kWeightRangeMaxValue); |
| assert(weight >= 0); |
| assert(weight <= 64); |
| |
| // The quantization maps that define weight unquantization expect values in |
| // the range [0, 64), but the specification quantizes them to the range |
| // [0, 64] according to C.2.17. This is a slight hack similar to the one in |
| // the unquantization procedure to return the passed in unquantized value to |
| // [0, 64) prior to running it through the quantization procedure. |
| if (weight > 33) { |
| weight -= 1; |
| } |
| const QuantizationMap* map = GetQuantMapForWeightRange(range_max_value); |
| return map ? map->Quantize(weight) : 0; |
| } |
| |
| int UnquantizeWeightFromRange(int weight, int range_max_value) { |
| assert(range_max_value >= 1); |
| assert(range_max_value <= kWeightRangeMaxValue); |
| assert(weight >= 0); |
| assert(weight <= range_max_value); |
| const QuantizationMap* map = GetQuantMapForWeightRange(range_max_value); |
| int dq = map ? map->Unquantize(weight) : 0; |
| |
| // Quantized weights are returned in the range [0, 64), but they should be |
| // returned in the range [0, 64], so according to C.2.17 we need to add one |
| // to the result. |
| assert(dq < 64); |
| if (dq > 32) { |
| dq += 1; |
| } |
| return dq; |
| } |
| |
| } // namespace astc_codec |