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