enc_ans.h (4834B)
1 // Copyright (c) the JPEG XL Project Authors. All rights reserved. 2 // 3 // Use of this source code is governed by a BSD-style 4 // license that can be found in the LICENSE file. 5 6 #ifndef LIB_JXL_ENC_ANS_H_ 7 #define LIB_JXL_ENC_ANS_H_ 8 9 // Library to encode the ANS population counts to the bit-stream and encode 10 // symbols based on the respective distributions. 11 12 #include <cstddef> 13 #include <cstdint> 14 #include <vector> 15 16 #include "lib/jxl/ans_params.h" 17 #include "lib/jxl/dec_ans.h" 18 #include "lib/jxl/enc_ans_params.h" 19 #include "lib/jxl/enc_bit_writer.h" 20 21 namespace jxl { 22 23 struct AuxOut; 24 25 #define USE_MULT_BY_RECIPROCAL 26 27 // precision must be equal to: #bits(state_) + #bits(freq) 28 #define RECIPROCAL_PRECISION (32 + ANS_LOG_TAB_SIZE) 29 30 // Data structure representing one element of the encoding table built 31 // from a distribution. 32 // TODO(veluca): split this up, or use an union. 33 struct ANSEncSymbolInfo { 34 // ANS 35 uint16_t freq_; 36 std::vector<uint16_t> reverse_map_; 37 #ifdef USE_MULT_BY_RECIPROCAL 38 uint64_t ifreq_; 39 #endif 40 // Prefix coding. 41 uint8_t depth; 42 uint16_t bits; 43 }; 44 45 class ANSCoder { 46 public: 47 ANSCoder() : state_(ANS_SIGNATURE << 16) {} 48 49 uint32_t PutSymbol(const ANSEncSymbolInfo& t, uint8_t* nbits) { 50 uint32_t bits = 0; 51 *nbits = 0; 52 if ((state_ >> (32 - ANS_LOG_TAB_SIZE)) >= t.freq_) { 53 bits = state_ & 0xffff; 54 state_ >>= 16; 55 *nbits = 16; 56 } 57 #ifdef USE_MULT_BY_RECIPROCAL 58 // We use mult-by-reciprocal trick, but that requires 64b calc. 59 const uint32_t v = (state_ * t.ifreq_) >> RECIPROCAL_PRECISION; 60 const uint32_t offset = t.reverse_map_[state_ - v * t.freq_]; 61 state_ = (v << ANS_LOG_TAB_SIZE) + offset; 62 #else 63 state_ = ((state_ / t.freq_) << ANS_LOG_TAB_SIZE) + 64 t.reverse_map_[state_ % t.freq_]; 65 #endif 66 return bits; 67 } 68 69 uint32_t GetState() const { return state_; } 70 71 private: 72 uint32_t state_; 73 }; 74 75 static const int kNumFixedHistograms = 1; 76 77 struct EntropyEncodingData { 78 std::vector<std::vector<ANSEncSymbolInfo>> encoding_info; 79 bool use_prefix_code; 80 std::vector<HybridUintConfig> uint_config; 81 LZ77Params lz77; 82 std::vector<BitWriter> encoded_histograms; 83 }; 84 85 // Integer to be encoded by an entropy coder, either ANS or Huffman. 86 struct Token { 87 Token() = default; 88 Token(uint32_t c, uint32_t value) 89 : is_lz77_length(false), context(c), value(value) {} 90 uint32_t is_lz77_length : 1; 91 uint32_t context : 31; 92 uint32_t value; 93 }; 94 95 // Returns an estimate of the number of bits required to encode the given 96 // histogram (header bits plus data bits). 97 float ANSPopulationCost(const ANSHistBin* data, size_t alphabet_size); 98 99 // Writes the context map to the bitstream and concatenates the individual 100 // histogram bistreams in codes.encoded_histograms. Used in streaming mode. 101 void EncodeHistograms(const std::vector<uint8_t>& context_map, 102 const EntropyEncodingData& codes, BitWriter* writer, 103 size_t layer, AuxOut* aux_out); 104 105 // Apply context clustering, compute histograms and encode them. Returns an 106 // estimate of the total bits used for encoding the stream. If `writer` == 107 // nullptr, the bit estimate will not take into account the context map (which 108 // does not get written if `num_contexts` == 1). 109 size_t BuildAndEncodeHistograms(const HistogramParams& params, 110 size_t num_contexts, 111 std::vector<std::vector<Token>>& tokens, 112 EntropyEncodingData* codes, 113 std::vector<uint8_t>* context_map, 114 BitWriter* writer, size_t layer, 115 AuxOut* aux_out); 116 117 // Write the tokens to a string. 118 void WriteTokens(const std::vector<Token>& tokens, 119 const EntropyEncodingData& codes, 120 const std::vector<uint8_t>& context_map, size_t context_offset, 121 BitWriter* writer, size_t layer, AuxOut* aux_out); 122 123 // Same as above, but assumes allotment created by caller. 124 size_t WriteTokens(const std::vector<Token>& tokens, 125 const EntropyEncodingData& codes, 126 const std::vector<uint8_t>& context_map, 127 size_t context_offset, BitWriter* writer); 128 129 // Exposed for tests; to be used with Writer=BitWriter only. 130 template <typename Writer> 131 void EncodeUintConfigs(const std::vector<HybridUintConfig>& uint_config, 132 Writer* writer, size_t log_alpha_size); 133 extern template void EncodeUintConfigs(const std::vector<HybridUintConfig>&, 134 BitWriter*, size_t); 135 136 // Globally set the option to create fuzzer-friendly ANS streams. Negatively 137 // impacts compression. Not thread-safe. 138 void SetANSFuzzerFriendly(bool ans_fuzzer_friendly); 139 } // namespace jxl 140 141 #endif // LIB_JXL_ENC_ANS_H_