lib/jxl/enc_context_map.cc

   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 // Library to encode the context map.
   7
   8 #include "lib/jxl/enc_context_map.h"
   9
  10 #include <stdint.h>
  11
  12 #include <algorithm>
  13 #include <cstddef>
  14 #include <vector>
  15
  16 #include "lib/jxl/base/bits.h"
  17 #include "lib/jxl/base/status.h"
  18 #include "lib/jxl/enc_ans.h"
  19 #include "lib/jxl/enc_aux_out.h"
  20 #include "lib/jxl/entropy_coder.h"
  21 #include "lib/jxl/pack_signed.h"
  22
  23 namespace jxl {
  24
  25 namespace {
  26
  27 size_t IndexOf(const std::vector<uint8_t>& v, uint8_t value) {
  28   size_t i = 0;
  29   for (; i < v.size(); ++i) {
  30     if (v[i] == value) return i;
  31   }
  32   return i;
  33 }
  34
  35 void MoveToFront(std::vector<uint8_t>* v, size_t index) {
  36   uint8_t value = (*v)[index];
  37   for (size_t i = index; i != 0; --i) {
  38     (*v)[i] = (*v)[i - 1];
  39   }
  40   (*v)[0] = value;
  41 }
  42
  43 std::vector<uint8_t> MoveToFrontTransform(const std::vector<uint8_t>& v) {
  44   if (v.empty()) return v;
  45   uint8_t max_value = *std::max_element(v.begin(), v.end());
  46   std::vector<uint8_t> mtf(max_value + 1);
  47   for (size_t i = 0; i <= max_value; ++i) mtf[i] = i;
  48   std::vector<uint8_t> result(v.size());
  49   for (size_t i = 0; i < v.size(); ++i) {
  50     size_t index = IndexOf(mtf, v[i]);
  51     JXL_ASSERT(index < mtf.size());
  52     result[i] = static_cast<uint8_t>(index);
  53     MoveToFront(&mtf, index);
  54   }
  55   return result;
  56 }
  57
  58 }  // namespace
  59
  60 void EncodeContextMap(const std::vector<uint8_t>& context_map,
  61                       size_t num_histograms, BitWriter* writer, size_t layer,
  62                       AuxOut* aux_out) {
  63   if (num_histograms == 1) {
  64     // Simple code
  65     writer->Write(1, 1);
  66     // 0 bits per entry.
  67     writer->Write(2, 0);
  68     return;
  69   }
  70
  71   std::vector<uint8_t> transformed_symbols = MoveToFrontTransform(context_map);
  72   std::vector<std::vector<Token>> tokens(1), mtf_tokens(1);
  73   EntropyEncodingData codes;
  74   std::vector<uint8_t> sink_context_map;
  75   for (size_t i = 0; i < context_map.size(); i++) {
  76     tokens[0].emplace_back(0, context_map[i]);
  77   }
  78   for (size_t i = 0; i < transformed_symbols.size(); i++) {
  79     mtf_tokens[0].emplace_back(0, transformed_symbols[i]);
  80   }
  81   HistogramParams params;
  82   params.uint_method = HistogramParams::HybridUintMethod::kContextMap;
  83   size_t ans_cost = BuildAndEncodeHistograms(
  84       params, 1, tokens, &codes, &sink_context_map, nullptr, 0, nullptr);
  85   size_t mtf_cost = BuildAndEncodeHistograms(
  86       params, 1, mtf_tokens, &codes, &sink_context_map, nullptr, 0, nullptr);
  87   bool use_mtf = mtf_cost < ans_cost;
  88   // Rebuild token list.
  89   tokens[0].clear();
  90   for (size_t i = 0; i < transformed_symbols.size(); i++) {
  91     tokens[0].emplace_back(0,
  92                            use_mtf ? transformed_symbols[i] : context_map[i]);
  93   }
  94   size_t entry_bits = CeilLog2Nonzero(num_histograms);
  95   size_t simple_cost = entry_bits * context_map.size();
  96   if (entry_bits < 4 && simple_cost < ans_cost && simple_cost < mtf_cost) {
  97     writer->Write(1, 1);
  98     writer->Write(2, entry_bits);
  99     for (size_t i = 0; i < context_map.size(); i++) {
 100       writer->Write(entry_bits, context_map[i]);
 101     }
 102   } else {
 103     writer->Write(1, 0);
 104     writer->Write(1, use_mtf);  // Use/don't use MTF.
 105     BuildAndEncodeHistograms(params, 1, tokens, &codes, &sink_context_map,
 106                              writer, layer, aux_out);
 107     WriteTokens(tokens[0], codes, sink_context_map, writer);
 108   }
 109 }
 110
 111 void EncodeBlockCtxMap(const BlockCtxMap& block_ctx_map, BitWriter* writer,
 112                        AuxOut* aux_out) {
 113   auto& dct = block_ctx_map.dc_thresholds;
 114   auto& qft = block_ctx_map.qf_thresholds;
 115   auto& ctx_map = block_ctx_map.ctx_map;
 116   BitWriter::Allotment allotment(
 117       writer,
 118       (dct[0].size() + dct[1].size() + dct[2].size() + qft.size()) * 34 + 1 +
 119           4 + 4 + ctx_map.size() * 10 + 1024);
 120   if (dct[0].empty() && dct[1].empty() && dct[2].empty() && qft.empty() &&
 121       ctx_map.size() == 21 &&
 122       std::equal(ctx_map.begin(), ctx_map.end(), BlockCtxMap::kDefaultCtxMap)) {
 123     writer->Write(1, 1);  // default
 124     allotment.ReclaimAndCharge(writer, kLayerAC, aux_out);
 125     return;
 126   }
 127   writer->Write(1, 0);
 128   for (int j : {0, 1, 2}) {
 129     writer->Write(4, dct[j].size());
 130     for (int i : dct[j]) {
 131       JXL_CHECK(U32Coder::Write(kDCThresholdDist, PackSigned(i), writer));
 132     }
 133   }
 134   writer->Write(4, qft.size());
 135   for (uint32_t i : qft) {
 136     JXL_CHECK(U32Coder::Write(kQFThresholdDist, i - 1, writer));
 137   }
 138   EncodeContextMap(ctx_map, block_ctx_map.num_ctxs, writer, kLayerAC, aux_out);
 139   allotment.ReclaimAndCharge(writer, kLayerAC, aux_out);
 140 }
 141
 142 }  // namespace jxl