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 DaalaBitReader : public BitReader { 29 public: 30 DaalaBitReader(const uint8_t* data, size_t size, bool allow_update_cdf); 31 ~DaalaBitReader() override = default; 32 33 // Move only. 34 DaalaBitReader(DaalaBitReader&& rhs) noexcept; 35 DaalaBitReader& operator=(DaalaBitReader&& rhs) noexcept; 36 37 int ReadBit() final; 38 int64_t ReadLiteral(int num_bits) override; 39 // ReadSymbol() calls for which the |symbol_count| is only known at runtime 40 // will use this variant. 41 int ReadSymbol(uint16_t* cdf, int symbol_count); 42 // ReadSymbol() calls for which the |symbol_count| is equal to 2 (boolean 43 // symbols) will use this variant. 44 bool ReadSymbol(uint16_t* cdf); 45 bool ReadSymbolWithoutCdfUpdate(uint16_t* cdf); 46 // Use either linear search or binary search for decoding the symbol depending 47 // on |symbol_count|. ReadSymbol calls for which the |symbol_count| is known 48 // at compile time will use this variant. 49 template <int symbol_count> 50 int ReadSymbol(uint16_t* cdf); 51 52 private: 53 // WindowSize must be an unsigned integer type with at least 32 bits. Use the 54 // largest type with fast arithmetic. size_t should meet these requirements. 55 static_assert(sizeof(size_t) == sizeof(void*), ""); 56 using WindowSize = size_t; 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(const uint16_t* cdf); 76 // ReadSymbolN is a specialization of ReadSymbol for symbol_count == N. 77 LIBGAV1_ALWAYS_INLINE int ReadSymbol4(uint16_t* cdf); 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* const data_; 87 const size_t size_; 88 size_t data_index_; 89 const bool allow_update_cdf_; 90 // Number of bits of data in the current value. 91 int bits_; 92 // Number of values in the current range. Declared as uint32_t for better 93 // performance but only the lower 16 bits are used. 94 uint32_t values_in_range_; 95 // The difference between the high end of the current range and the coded 96 // value minus 1. The 16 most significant bits of this variable is used to 97 // decode the next symbol. It is filled in whenever |bits_| is less than 0. 98 WindowSize window_diff_; 99 }; 100 101 extern template int DaalaBitReader::ReadSymbol<3>(uint16_t* cdf); 102 extern template int DaalaBitReader::ReadSymbol<4>(uint16_t* cdf); 103 extern template int DaalaBitReader::ReadSymbol<5>(uint16_t* cdf); 104 extern template int DaalaBitReader::ReadSymbol<7>(uint16_t* cdf); 105 extern template int DaalaBitReader::ReadSymbol<8>(uint16_t* cdf); 106 extern template int DaalaBitReader::ReadSymbol<10>(uint16_t* cdf); 107 extern template int DaalaBitReader::ReadSymbol<11>(uint16_t* cdf); 108 extern template int DaalaBitReader::ReadSymbol<13>(uint16_t* cdf); 109 extern template int DaalaBitReader::ReadSymbol<14>(uint16_t* cdf); 110 extern template int DaalaBitReader::ReadSymbol<16>(uint16_t* cdf); 111 112 } // namespace libgav1 113 114 #endif // LIBGAV1_SRC_UTILS_ENTROPY_DECODER_H_ 115