tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

enc_ans.h (4869B)

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