enc_context_map.cc (6058B)
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 <jxl/memory_manager.h> 11 #include <jxl/types.h> 12 13 #include <algorithm> 14 #include <cstddef> 15 #include <cstdint> 16 #include <vector> 17 18 #include "lib/jxl/base/bits.h" 19 #include "lib/jxl/base/status.h" 20 #include "lib/jxl/enc_ans.h" 21 #include "lib/jxl/enc_aux_out.h" 22 #include "lib/jxl/entropy_coder.h" 23 #include "lib/jxl/fields.h" 24 #include "lib/jxl/pack_signed.h" 25 26 namespace jxl { 27 28 namespace { 29 30 size_t IndexOf(const std::vector<uint8_t>& v, uint8_t value) { 31 size_t i = 0; 32 for (; i < v.size(); ++i) { 33 if (v[i] == value) return i; 34 } 35 return i; 36 } 37 38 void MoveToFront(std::vector<uint8_t>* v, size_t index) { 39 uint8_t value = (*v)[index]; 40 for (size_t i = index; i != 0; --i) { 41 (*v)[i] = (*v)[i - 1]; 42 } 43 (*v)[0] = value; 44 } 45 46 std::vector<uint8_t> MoveToFrontTransform(const std::vector<uint8_t>& v) { 47 if (v.empty()) return v; 48 uint8_t max_value = *std::max_element(v.begin(), v.end()); 49 std::vector<uint8_t> mtf(max_value + 1); 50 for (size_t i = 0; i <= max_value; ++i) mtf[i] = i; 51 std::vector<uint8_t> result(v.size()); 52 for (size_t i = 0; i < v.size(); ++i) { 53 size_t index = IndexOf(mtf, v[i]); 54 JXL_DASSERT(index < mtf.size()); 55 result[i] = static_cast<uint8_t>(index); 56 MoveToFront(&mtf, index); 57 } 58 return result; 59 } 60 61 } // namespace 62 63 Status EncodeContextMap(const std::vector<uint8_t>& context_map, 64 size_t num_histograms, BitWriter* writer, 65 LayerType layer, AuxOut* aux_out) { 66 if (num_histograms == 1) { 67 // Simple code 68 writer->Write(1, 1); 69 // 0 bits per entry. 70 writer->Write(2, 0); 71 return true; 72 } 73 74 JxlMemoryManager* memory_manager = writer->memory_manager(); 75 std::vector<uint8_t> transformed_symbols = MoveToFrontTransform(context_map); 76 std::vector<std::vector<Token>> tokens(1); 77 std::vector<std::vector<Token>> mtf_tokens(1); 78 for (const uint8_t& ctx : context_map) { 79 tokens[0].emplace_back(0, ctx); 80 } 81 for (const uint8_t& sym : transformed_symbols) { 82 mtf_tokens[0].emplace_back(0, sym); 83 } 84 HistogramParams params; 85 params.uint_method = HistogramParams::HybridUintMethod::kContextMap; 86 size_t ans_cost; 87 size_t mtf_cost; 88 { 89 EntropyEncodingData codes; 90 std::vector<uint8_t> sink_context_map; 91 JXL_ASSIGN_OR_RETURN(ans_cost, BuildAndEncodeHistograms( 92 memory_manager, params, 1, tokens, 93 &codes, &sink_context_map, nullptr, 94 LayerType::Header, /*aux_out*/ nullptr)); 95 } 96 { 97 EntropyEncodingData codes; 98 std::vector<uint8_t> sink_context_map; 99 JXL_ASSIGN_OR_RETURN(mtf_cost, BuildAndEncodeHistograms( 100 memory_manager, params, 1, mtf_tokens, 101 &codes, &sink_context_map, nullptr, 102 LayerType::Header, /*aux_out*/ nullptr)); 103 } 104 bool use_mtf = mtf_cost < ans_cost; 105 // Rebuild token list. 106 tokens[0].clear(); 107 for (size_t i = 0; i < transformed_symbols.size(); i++) { 108 tokens[0].emplace_back(0, 109 use_mtf ? transformed_symbols[i] : context_map[i]); 110 } 111 size_t entry_bits = CeilLog2Nonzero(num_histograms); 112 size_t simple_cost = entry_bits * context_map.size(); 113 if (entry_bits < 4 && simple_cost < ans_cost && simple_cost < mtf_cost) { 114 JXL_RETURN_IF_ERROR(writer->WithMaxBits( 115 3 + entry_bits * context_map.size(), layer, aux_out, [&] { 116 writer->Write(1, 1); 117 writer->Write(2, entry_bits); 118 for (uint8_t entry : context_map) { 119 writer->Write(entry_bits, entry); 120 } 121 return true; 122 })); 123 } else { 124 JXL_RETURN_IF_ERROR(writer->WithMaxBits( 125 2 + tokens[0].size() * 24, layer, aux_out, [&]() -> Status { 126 writer->Write(1, 0); 127 writer->Write(1, TO_JXL_BOOL(use_mtf)); // Use/don't use MTF. 128 EntropyEncodingData codes; 129 std::vector<uint8_t> sink_context_map; 130 JXL_ASSIGN_OR_RETURN(size_t cost, 131 BuildAndEncodeHistograms( 132 memory_manager, params, 1, tokens, &codes, 133 &sink_context_map, writer, layer, aux_out)); 134 (void)cost; 135 WriteTokens(tokens[0], codes, sink_context_map, 0, writer); 136 return true; 137 })); 138 } 139 return true; 140 } 141 142 Status EncodeBlockCtxMap(const BlockCtxMap& block_ctx_map, BitWriter* writer, 143 AuxOut* aux_out) { 144 const auto& dct = block_ctx_map.dc_thresholds; 145 const auto& qft = block_ctx_map.qf_thresholds; 146 const auto& ctx_map = block_ctx_map.ctx_map; 147 return writer->WithMaxBits( 148 (dct[0].size() + dct[1].size() + dct[2].size() + qft.size()) * 34 + 1 + 149 4 + 4 + ctx_map.size() * 10 + 1024, 150 LayerType::Ac, aux_out, [&]() -> Status { 151 if (dct[0].empty() && dct[1].empty() && dct[2].empty() && qft.empty() && 152 ctx_map.size() == 21 && 153 std::equal(ctx_map.begin(), ctx_map.end(), 154 BlockCtxMap::kDefaultCtxMap)) { 155 writer->Write(1, 1); // default 156 return true; 157 } 158 writer->Write(1, 0); 159 for (int j : {0, 1, 2}) { 160 writer->Write(4, dct[j].size()); 161 for (int i : dct[j]) { 162 JXL_RETURN_IF_ERROR( 163 U32Coder::Write(kDCThresholdDist, PackSigned(i), writer)); 164 } 165 } 166 writer->Write(4, qft.size()); 167 for (uint32_t i : qft) { 168 JXL_RETURN_IF_ERROR(U32Coder::Write(kQFThresholdDist, i - 1, writer)); 169 } 170 JXL_RETURN_IF_ERROR(EncodeContextMap(ctx_map, block_ctx_map.num_ctxs, 171 writer, LayerType::Ac, aux_out)); 172 return true; 173 }); 174 } 175 176 } // namespace jxl