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 uint32_t kWindowSize = 58 static_cast<uint32_t>(sizeof(WindowSize)) * 8; 59 static_assert(kWindowSize >= 32, ""); 60 61 // Reads a symbol using the |cdf| table which contains the probabilities of 62 // each symbol. On a high level, this function does the following: 63 // 1) Scale the |cdf| values. 64 // 2) Find the index in the |cdf| array where the scaled CDF value crosses 65 // the modified |window_diff_| threshold. 66 // 3) That index is the symbol that has been decoded. 67 // 4) Update |window_diff_| and |values_in_range_| based on the symbol that 68 // has been decoded. 69 inline int ReadSymbolImpl(const uint16_t* cdf, int symbol_count); 70 // Similar to ReadSymbolImpl but it uses binary search to perform step 2 in 71 // the comment above. As of now, this function is called when |symbol_count| 72 // is greater than or equal to 8. 73 inline int ReadSymbolImplBinarySearch(const uint16_t* cdf, int symbol_count); 74 // Specialized implementation of ReadSymbolImpl based on the fact that 75 // symbol_count == 2. 76 inline int ReadSymbolImpl(const uint16_t* cdf); 77 // ReadSymbolN is a specialization of ReadSymbol for symbol_count == N. 78 int ReadSymbol4(uint16_t* cdf); 79 // ReadSymbolImplN is a specialization of ReadSymbolImpl for 80 // symbol_count == N. 81 LIBGAV1_ALWAYS_INLINE int ReadSymbolImpl8(const uint16_t* cdf); 82 inline void PopulateBits(); 83 // Normalizes the range so that 32768 <= |values_in_range_| < 65536. Also 84 // calls PopulateBits() if necessary. 85 inline void NormalizeRange(); 86 87 const uint8_t* const data_; 88 const size_t size_; 89 size_t data_index_; 90 const bool allow_update_cdf_; 91 // Number of bits of data in the current value. 92 int bits_; 93 // Number of values in the current range. Declared as uint32_t for better 94 // performance but only the lower 16 bits are used. 95 uint32_t values_in_range_; 96 // The difference between the high end of the current range and the coded 97 // value minus 1. The 16 most significant bits of this variable is used to 98 // decode the next symbol. It is filled in whenever |bits_| is less than 0. 99 WindowSize window_diff_; 100 }; 101 102 } // namespace libgav1 103 104 #endif // LIBGAV1_SRC_UTILS_ENTROPY_DECODER_H_ 105