Coverage Report

Created: 2026-03-31 07:44

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