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 #ifndef ASTC_CODEC_DECODER_PARTITION_H_ 16 #define ASTC_CODEC_DECODER_PARTITION_H_ 17 18 #include "src/base/optional.h" 19 #include "src/decoder/footprint.h" 20 21 #include <vector> 22 23 namespace astc_codec { 24 25 struct Partition; 26 27 // Determines the "difference" between any two partitions of the same size. 28 // This metric attempts to find the best one to one mapping from the labels in 29 // partition a against the labels in partition b. Once that mapping is found, it 30 // returns the number of pixels that are mismatched between the two. Each 31 // partition is expected to start in the upper left corner of the block and 32 // proceed in raster-scan order. Two partitions are equal if the mapping is 33 // bijective. This metric is a metric in the mathematical sense. In other words 34 // it has the following properties: 35 // 36 // 1) PartitionMetric(a, b) >= 0 37 // 2) PartitionMetric(a, b) == PartitionMetric(b, a) 38 // 3) PartitionMetric(a, b) == 0 iff a == b 39 // 4) PartitionMetric(a, b) + PartitionMetric(b, c) >= PartitionMetric(a, c) 40 // 41 // Throws an error if one partition's footprint is not equal to the other. 42 int PartitionMetric(const Partition& a, const Partition& b); 43 44 // A partition is a way to divide up an ASTC block into disjoint subsets such 45 // that each subset uses a different set of endpoints. This is used to increase 46 // the compression quality of blocks. One way to store such a partition is to 47 // assign an ID to use with a predetermined decoding method. Here we store the 48 // logical representation of partitions by keeping a per-pixel label. All pixels 49 // that share a label belong to the same subset. 50 struct Partition { 51 // The footprint width and height of this partition. This determines the size 52 // of the assignment array. 53 Footprint footprint; 54 55 // The number of subsets in this partition. The values in the partition 56 // assignment fall within the range [0, num_parts). The maximum number of 57 // parts supported is four. 58 int num_parts; 59 60 // The 10-bit partition ID as stored in bits 13-22 of multi-part ASTC blocks. 61 // (See Section C.2.9) If there is no guarantee that this partition is a valid 62 // ASTC partition, this should be set to absl::nullopt. 63 base::Optional<int> partition_id; 64 65 // A value in the range [0, num_parts) corresponding to the label for 66 // the given texel (x, y) in [0, footprint_width) x [0, footprint_height) 67 // using a raster-order layout. 68 std::vector<int> assignment; 69 70 // Returns true only if their "distance" is zero, i.e. if they have compatible 71 // subset assignments. 72 bool operator==(const Partition& other) const { 73 return PartitionMetric(*this, other) == 0; 74 } 75 }; 76 77 // Generates the ASTC partition assignment for the given block attributes. 78 Partition GetASTCPartition(const Footprint& footprint, int num_parts, 79 int partition_id); 80 81 // Returns the |k| valid ASTC partitions that are closest to the candidate based 82 // on the PartitionMetric defined above. 83 const std::vector<const Partition*> FindKClosestASTCPartitions( 84 const Partition& candidate, int k); 85 86 // Returns the valid ASTC partition closest to the candidate with at most as 87 // many subsets as the |candidate|. Note: this is not a deterministic function, 88 // as the underlying valid partitions are sorted using a hash map and a distance 89 // function whose range is the natural numbers. The chances that two or more 90 // partitions are equally 'closest' is possible, in which case this function 91 // makes no guarantees about which one it will return. For more control, use 92 // FindKClosestASTCPartitions above. 93 const Partition& FindClosestASTCPartition(const Partition& candidate); 94 95 } // namespace astc_codec 96 97 #endif // ASTC_CODEC_DECODER_PARTITION_H_ 98