1 /* 2 * Copyright 2019 The libgav1 Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef LIBGAV1_SRC_UTILS_ENTROPY_DECODER_H_ 18 #define LIBGAV1_SRC_UTILS_ENTROPY_DECODER_H_ 19 20 #include <cstddef> 21 #include <cstdint> 22 23 #include "src/utils/bit_reader.h" 24 #include "src/utils/compiler_attributes.h" 25 26 namespace libgav1 { 27 28 class EntropyDecoder final : public BitReader { 29 public: 30 // WindowSize must be an unsigned integer type with at least 32 bits. Use the 31 // largest type with fast arithmetic. size_t should meet these requirements. 32 using WindowSize = size_t; 33 34 EntropyDecoder(const uint8_t* data, size_t size, bool allow_update_cdf); 35 ~EntropyDecoder() override = default; 36 37 // Move only. 38 EntropyDecoder(EntropyDecoder&& rhs) noexcept; 39 EntropyDecoder& operator=(EntropyDecoder&& rhs) noexcept; 40 41 int ReadBit() override; 42 int64_t ReadLiteral(int num_bits) override; 43 // ReadSymbol() calls for which the |symbol_count| is only known at runtime 44 // will use this variant. 45 int ReadSymbol(uint16_t* cdf, int symbol_count); 46 // ReadSymbol() calls for which the |symbol_count| is equal to 2 (boolean 47 // symbols) will use this variant. 48 bool ReadSymbol(uint16_t* cdf); 49 bool ReadSymbolWithoutCdfUpdate(uint16_t cdf); 50 // Use either linear search or binary search for decoding the symbol depending 51 // on |symbol_count|. ReadSymbol calls for which the |symbol_count| is known 52 // at compile time will use this variant. 53 template <int symbol_count> 54 int ReadSymbol(uint16_t* cdf); 55 56 private: 57 static constexpr int kWindowSize = static_cast<int>(sizeof(WindowSize)) * 8; 58 static_assert(kWindowSize >= 32, ""); 59 60 // Reads a symbol using the |cdf| table which contains the probabilities of 61 // each symbol. On a high level, this function does the following: 62 // 1) Scale the |cdf| values. 63 // 2) Find the index in the |cdf| array where the scaled CDF value crosses 64 // the modified |window_diff_| threshold. 65 // 3) That index is the symbol that has been decoded. 66 // 4) Update |window_diff_| and |values_in_range_| based on the symbol that 67 // has been decoded. 68 inline int ReadSymbolImpl(const uint16_t* cdf, int symbol_count); 69 // Similar to ReadSymbolImpl but it uses binary search to perform step 2 in 70 // the comment above. As of now, this function is called when |symbol_count| 71 // is greater than or equal to 14. 72 inline int ReadSymbolImplBinarySearch(const uint16_t* cdf, int symbol_count); 73 // Specialized implementation of ReadSymbolImpl based on the fact that 74 // symbol_count == 2. 75 inline int ReadSymbolImpl(uint16_t cdf); 76 // ReadSymbolN is a specialization of ReadSymbol for symbol_count == N. 77 LIBGAV1_ALWAYS_INLINE int ReadSymbol3Or4(uint16_t* cdf, int symbol_count); 78 // ReadSymbolImplN is a specialization of ReadSymbolImpl for 79 // symbol_count == N. 80 LIBGAV1_ALWAYS_INLINE int ReadSymbolImpl8(const uint16_t* cdf); 81 inline void PopulateBits(); 82 // Normalizes the range so that 32768 <= |values_in_range_| < 65536. Also 83 // calls PopulateBits() if necessary. 84 inline void NormalizeRange(); 85 86 const uint8_t* data_; 87 const uint8_t* const data_end_; 88 // If |data_| < |data_memcpy_end_|, then we can read sizeof(WindowSize) bytes 89 // from |data_|. Note with sizeof(WindowSize) == 4 this is only used in the 90 // constructor, not PopulateBits(). 91 const uint8_t* const data_memcpy_end_; 92 const bool allow_update_cdf_; 93 // Number of cached bits of data in the current value. 94 int bits_; 95 // Number of values in the current range. Declared as uint32_t for better 96 // performance but only the lower 16 bits are used. 97 uint32_t values_in_range_; 98 // The difference between the high end of the current range and the coded 99 // value minus 1. The 16 bits above |bits_| of this variable are used to 100 // decode the next symbol. It is filled in whenever |bits_| is less than 0. 101 // Note this implementation differs from the spec as it trades the need to 102 // shift in 1s in NormalizeRange() with an extra shift in PopulateBits(), 103 // which occurs less frequently. 104 WindowSize window_diff_; 105 }; 106 107 extern template int EntropyDecoder::ReadSymbol<3>(uint16_t* cdf); 108 extern template int EntropyDecoder::ReadSymbol<4>(uint16_t* cdf); 109 extern template int EntropyDecoder::ReadSymbol<5>(uint16_t* cdf); 110 extern template int EntropyDecoder::ReadSymbol<6>(uint16_t* cdf); 111 extern template int EntropyDecoder::ReadSymbol<7>(uint16_t* cdf); 112 extern template int EntropyDecoder::ReadSymbol<8>(uint16_t* cdf); 113 extern template int EntropyDecoder::ReadSymbol<9>(uint16_t* cdf); 114 extern template int EntropyDecoder::ReadSymbol<10>(uint16_t* cdf); 115 extern template int EntropyDecoder::ReadSymbol<11>(uint16_t* cdf); 116 extern template int EntropyDecoder::ReadSymbol<12>(uint16_t* cdf); 117 extern template int EntropyDecoder::ReadSymbol<13>(uint16_t* cdf); 118 extern template int EntropyDecoder::ReadSymbol<14>(uint16_t* cdf); 119 extern template int EntropyDecoder::ReadSymbol<16>(uint16_t* cdf); 120 121 } // namespace libgav1 122 123 #endif // LIBGAV1_SRC_UTILS_ENTROPY_DECODER_H_ 124