From b56a50064caf2a590ba43699e0074690fcd431bf Mon Sep 17 00:00:00 2001 From: Jeff McGlynn Date: Wed, 20 Jun 2018 11:34:20 -0700 Subject: Initial version of astc-codec for open source release Contains an implementation of an ASTC decoder that is able to pass the dEQP ASTC LDR tests. astc-codec has no external dependencies for the main library, only for test code, and is licensed under the Apache license. Components: include/ - Public API that can decode ASTC LDR data into a RGBA UNORM8 buffer. src/base/ - Base library with common functionality not directly related to ASTC decoding. Contains a uint128 implementation, BitStream for reading/writing bits with a primitive (or uint128 type), Optional implementation (to not take a dependency on C++17), and more. src/decoder/ - Internal implementation of the ASTC decoder. src/base/test/, src/decoder/test/ - Unit tests (and a fuzzing test) for the astc decoder. src/decoder/testdata/ - Sample ASTC images and golden image results for testing. src/decoder/tools/ - A tool to inspect contents of an ASTC file. third_party/ - Third party libraries, only used for tests. Change-Id: Ia98e5a7dc847daa3d3a48c5e62d94b8fb1cb98bd --- src/decoder/quantization.cc | 462 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 462 insertions(+) create mode 100644 src/decoder/quantization.cc (limited to 'src/decoder/quantization.cc') diff --git a/src/decoder/quantization.cc b/src/decoder/quantization.cc new file mode 100644 index 0000000..db99682 --- /dev/null +++ b/src/decoder/quantization.cc @@ -0,0 +1,462 @@ +// 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 +#include +#include +#include +#include +#include + +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 {{ 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 {{ 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 quantization_map_; + std::vector 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 +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 +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 +class BitQuantizationMap : public QuantizationMap { + public: + explicit BitQuantizationMap(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; + +// 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 { + { 5, QMap(new TritQuantizationMap(5)) }, + { 7, QMap(new BitQuantizationMap<8>(7)) }, + { 9, QMap(new QuintQuantizationMap(9)) }, + { 11, QMap(new TritQuantizationMap(11)) }, + { 15, QMap(new BitQuantizationMap<8>(15)) }, + { 19, QMap(new QuintQuantizationMap(19)) }, + { 23, QMap(new TritQuantizationMap(23)) }, + { 31, QMap(new BitQuantizationMap<8>(31)) }, + { 39, QMap(new QuintQuantizationMap(39)) }, + { 47, QMap(new TritQuantizationMap(47)) }, + { 63, QMap(new BitQuantizationMap<8>(63)) }, + { 79, QMap(new QuintQuantizationMap(79)) }, + { 95, QMap(new TritQuantizationMap(95)) }, + { 127, QMap(new BitQuantizationMap<8>(127)) }, + { 159, QMap(new QuintQuantizationMap(159)) }, + { 191, QMap(new TritQuantizationMap(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 { + { 1, QMap(new BitQuantizationMap<6>(1)) }, + { 2, QMap(new TritQuantizationMap(2)) }, + { 3, QMap(new BitQuantizationMap<6>(3)) }, + { 4, QMap(new QuintQuantizationMap(4)) }, + { 5, QMap(new TritQuantizationMap(5)) }, + { 7, QMap(new BitQuantizationMap<6>(7)) }, + { 9, QMap(new QuintQuantizationMap(9)) }, + { 11, QMap(new TritQuantizationMap(11)) }, + { 15, QMap(new BitQuantizationMap<6>(15)) }, + { 19, QMap(new QuintQuantizationMap(19)) }, + { 23, QMap(new TritQuantizationMap(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 -- cgit v1.2.3