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_INTEGER_SEQUENCE_CODEC_H_ 16 #define ASTC_CODEC_DECODER_INTEGER_SEQUENCE_CODEC_H_ 17 18 #include "src/base/bit_stream.h" 19 #include "src/base/uint128.h" 20 21 #include <array> 22 #include <string> 23 #include <vector> 24 25 namespace astc_codec { 26 27 // The maximum number of bits that we would need to encode an ISE value. The 28 // ASTC specification does not give a maximum number, however unquantized color 29 // values have a maximum range of 255, meaning that we can't feasibly have more 30 // than eight bits per value. 31 constexpr int kLog2MaxRangeForBits = 8; 32 33 // Ranges can take any of the the forms 2^k, 3*2^k, or 5*2^k for k up to 34 // kLog2MaxRangeForBits. Hence we have three types of ranges. Since the 35 // maximum encoded value is 255, k won't go larger than 8. We don't have quints 36 // that accompany [6, 8]-bits, as (5 * 2^6 = 320 > 255) and we don't have trits 37 // that accompany [7, 8]-bits, as (3 * 2^7 = 384 > 255). But we do have trits 38 // and quints that accompany no bits. Hence we have a total of 39 // 3 * kLog2MaxRangeForBits - 3 - 2 + 2 total ranges. 40 constexpr int kNumPossibleRanges = 3 * kLog2MaxRangeForBits - 3; 41 42 // Returns an iterator through the available ASTC ranges. 43 std::array<int, kNumPossibleRanges>::const_iterator ISERangeBegin(); 44 std::array<int, kNumPossibleRanges>::const_iterator ISERangeEnd(); 45 46 // Base class for ASTC integer sequence encoders and decoders. These codecs 47 // operate on sequences of integers and produce bit patterns that pack the 48 // integers based on the encoding scheme specified in the ASTC specification 49 // Section C.2.12. The resulting bit pattern is a sequence of encoded blocks. 50 // All blocks in a sequence are one of the following encodings: 51 // 52 // (1 -- bit encoding) one encoded value of the form 2^k 53 // (2 -- trit encoding) five encoded values of the form 3*2^k 54 // (3 -- quint encoding) three encoded values of the form 5*2^k 55 // 56 // The layouts of each block are designed such that the blocks can be truncated 57 // during encoding in order to support variable length input sequences (i.e. a 58 // sequence of values that are encoded using trit encoded blocks does not 59 // need to have a multiple-of-five length). 60 class IntegerSequenceCodec { 61 public: 62 // Returns the number of trits, quints, and bits needed to encode values in 63 // [0, range]. This is used to determine the layout of ISE encoded bit 64 // streams. The returned array holds the number of trits, quints, and bits 65 // respectively. range is expected to be within the interval [1, 5242879] 66 static void GetCountsForRange(int range, int* trits, int* quints, int* bits); 67 68 // Returns the number of bits needed to encode the given number of values with 69 // respect to the number of trits, quints, and bits specified in ise_counts 70 // (in that order). It is expected that either trits or quints can be 71 // nonzero, but not both, and neither can be larger than one. Anything else is 72 // undefined. 73 static int GetBitCount(int num_vals, int trits, int quints, int bits); 74 75 // Convenience function that returns the number of bits needed to encoded 76 // num_vals within the range [0, range] (inclusive). GetBitCountForRange(int num_vals,int range)77 static inline int GetBitCountForRange(int num_vals, int range) { 78 int trits, quints, bits; 79 GetCountsForRange(range, &trits, &quints, &bits); 80 return GetBitCount(num_vals, trits, quints, bits); 81 } 82 83 protected: 84 explicit IntegerSequenceCodec(int range); 85 IntegerSequenceCodec(int trits, int quints, int bits); 86 87 // The encoding mode -- since having trits and quints are mutually exclusive, 88 // we can store the encoding we decide on in this enum. 89 enum EncodingMode { 90 kTritEncoding = 0, 91 kQuintEncoding, 92 kBitEncoding, 93 }; 94 95 EncodingMode encoding_; 96 int bits_; 97 98 // Returns the number of values stored in a single ISE block. Since quints and 99 // trits are packed three/five to a bit pattern (respectively), each sequence 100 // is chunked into blocks in order to encode it. For only bit-encodings, the 101 // block size is one. 102 int NumValsPerBlock() const; 103 104 // Returns the size of a single ISE block in bits (see NumValsPerBlock). 105 int EncodedBlockSize() const; 106 107 private: 108 // Determines the encoding mode. 109 void InitializeWithCounts(int trits, int quints, int bits); 110 }; 111 112 // The integer sequence decoder. The decoder only remembers the given encoding 113 // but each invocation of Decode operates independently on the input bits. 114 class IntegerSequenceDecoder : public IntegerSequenceCodec { 115 public: 116 // Creates a decoder that decodes values within [0, range] (inclusive). IntegerSequenceDecoder(int range)117 explicit IntegerSequenceDecoder(int range) 118 : IntegerSequenceCodec(range) { } 119 120 // Creates a decoder based on the number of trits, quints, and bits expected 121 // in the bit stream passed to Decode. IntegerSequenceDecoder(int trits,int quints,int bits)122 IntegerSequenceDecoder(int trits, int quints, int bits) 123 : IntegerSequenceCodec(trits, quints, bits) { } 124 125 // Decodes num_vals from the bit_src. The number of bits read is dependent 126 // on the number of bits required to encode num_vals based on the calculation 127 // provided in Section C.2.22 of the ASTC specification. The return value 128 // always contains exactly num_vals. 129 std::vector<int> Decode(int num_vals, 130 base::BitStream<base::UInt128>* bit_src) const; 131 }; 132 133 // The integer sequence encoder. The encoder accepts values one by one and 134 // places them into a temporary array that it holds. When needed the user 135 // may call Encode to produce an encoded bit stream of the associated values. 136 class IntegerSequenceEncoder : public IntegerSequenceCodec { 137 public: 138 // Creates an encoder that encodes values within [0, range] (inclusive). IntegerSequenceEncoder(int range)139 explicit IntegerSequenceEncoder(int range) 140 : IntegerSequenceCodec(range) { } 141 142 // Creates an encoder based on the number of trits, quints, and bits for 143 // the bit stream produced by Encode. IntegerSequenceEncoder(int trits,int quints,int bits)144 IntegerSequenceEncoder(int trits, int quints, int bits) 145 : IntegerSequenceCodec(trits, quints, bits) { } 146 147 // Adds a value to the encoding sequence. AddValue(int val)148 void AddValue(int val) { 149 // Make sure it's within bounds 150 assert(encoding_ != EncodingMode::kTritEncoding || val < 3 * (1 << bits_)); 151 assert(encoding_ != EncodingMode::kQuintEncoding || val < 5 * (1 << bits_)); 152 assert(encoding_ != EncodingMode::kBitEncoding || val < (1 << bits_)); 153 vals_.push_back(val); 154 } 155 156 // Writes the encoding for vals_ to the bit_sink. Multiple calls to Encode 157 // will produce the same result. 158 void Encode(base::BitStream<base::UInt128>* bit_sink) const; 159 160 // Removes all of the previously added values to the encoder. Reset()161 void Reset() { vals_.clear(); } 162 163 private: 164 std::vector<int> vals_; 165 }; 166 167 } // namespace astc_codec 168 169 #endif // ASTC_CODEC_DECODER_INTEGER_SEQUENCE_CODEC_H_ 170