Debian Codegraph @

lib/jxl/modular/encoding/dec_ma.cc

raw
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 #include "lib/jxl/modular/encoding/dec_ma.h"
7
8 #include <jxl/memory_manager.h>
9
10 #include <limits>
11 #include <vector>
12
13 #include "lib/jxl/base/printf_macros.h"
14 #include "lib/jxl/base/status.h"
15 #include "lib/jxl/dec_ans.h"
16 #include "lib/jxl/modular/encoding/ma_common.h"
17 #include "lib/jxl/modular/modular_image.h"
18 #include "lib/jxl/pack_signed.h"
19
20 namespace jxl {
21
22 namespace {
23
24 Status ValidateTree(const Tree &tree) {
25 int num_properties = 0;
26 for (auto node : tree) {
27 if (node.property >= num_properties) {
28 num_properties = node.property + 1;
29 }
30 }
31 std::vector<int> height(tree.size());
32 std::vector<std::pair<pixel_type, pixel_type>> property_ranges(
33 num_properties * tree.size());
34 for (int i = 0; i < num_properties; i++) {
35 property_ranges[i].first = std::numeric_limits<pixel_type>::min();
36 property_ranges[i].second = std::numeric_limits<pixel_type>::max();
37 }
38 const int kHeightLimit = 2048;
39 for (size_t i = 0; i < tree.size(); i++) {
40 if (height[i] > kHeightLimit) {
41 return JXL_FAILURE("Tree too tall: %d", height[i]);
42 }
43 if (tree[i].property == -1) continue;
44 height[tree[i].lchild] = height[i] + 1;
45 height[tree[i].rchild] = height[i] + 1;
46 for (size_t p = 0; p < static_cast<size_t>(num_properties); p++) {
47 if (p == static_cast<size_t>(tree[i].property)) {
48 pixel_type l = property_ranges[i * num_properties + p].first;
49 pixel_type u = property_ranges[i * num_properties + p].second;
50 pixel_type val = tree[i].splitval;
51 if (l > val || u <= val) {
52 return JXL_FAILURE("Invalid tree");
53 }
54 property_ranges[tree[i].lchild * num_properties + p] =
55 std::make_pair(val + 1, u);
56 property_ranges[tree[i].rchild * num_properties + p] =
57 std::make_pair(l, val);
58 } else {
59 property_ranges[tree[i].lchild * num_properties + p] =
60 property_ranges[i * num_properties + p];
61 property_ranges[tree[i].rchild * num_properties + p] =
62 property_ranges[i * num_properties + p];
63 }
64 }
65 }
66 return true;
67 }
68
69 Status DecodeTree(BitReader *br, ANSSymbolReader *reader,
70 const std::vector<uint8_t> &context_map, Tree *tree,
71 size_t tree_size_limit) {
72 size_t leaf_id = 0;
73 size_t to_decode = 1;
74 tree->clear();
75 while (to_decode > 0) {
76 JXL_RETURN_IF_ERROR(br->AllReadsWithinBounds());
77 if (tree->size() > tree_size_limit) {
78 return JXL_FAILURE("Tree is too large: %" PRIuS " nodes vs %" PRIuS
79 " max nodes",
80 tree->size(), tree_size_limit);
81 }
82 to_decode--;
83 uint32_t prop1 = reader->ReadHybridUint(kPropertyContext, br, context_map);
84 if (prop1 > 256) return JXL_FAILURE("Invalid tree property value");
85 int property = prop1 - 1;
86 if (property == -1) {
87 size_t predictor =
88 reader->ReadHybridUint(kPredictorContext, br, context_map);
89 if (predictor >= kNumModularPredictors) {
90 return JXL_FAILURE("Invalid predictor");
91 }
92 int64_t predictor_offset =
93 UnpackSigned(reader->ReadHybridUint(kOffsetContext, br, context_map));
94 uint32_t mul_log =
95 reader->ReadHybridUint(kMultiplierLogContext, br, context_map);
96 if (mul_log >= 31) {
97 return JXL_FAILURE("Invalid multiplier logarithm");
98 }
99 uint32_t mul_bits =
100 reader->ReadHybridUint(kMultiplierBitsContext, br, context_map);
101 if (mul_bits >= (1u << (31u - mul_log)) - 1u) {
102 return JXL_FAILURE("Invalid multiplier");
103 }
104 uint32_t multiplier = (mul_bits + 1U) << mul_log;
105 tree->emplace_back(-1, 0, leaf_id++, 0, static_cast<Predictor>(predictor),
106 predictor_offset, multiplier);
107 continue;
108 }
109 int splitval =
110 UnpackSigned(reader->ReadHybridUint(kSplitValContext, br, context_map));
111 tree->emplace_back(property, splitval, tree->size() + to_decode + 1,
112 tree->size() + to_decode + 2, Predictor::Zero, 0, 1);
113 to_decode += 2;
114 }
115 return ValidateTree(*tree);
116 }
117 } // namespace
118
119 Status DecodeTree(JxlMemoryManager *memory_manager, BitReader *br, Tree *tree,
120 size_t tree_size_limit) {
121 std::vector<uint8_t> tree_context_map;
122 ANSCode tree_code;
123 JXL_RETURN_IF_ERROR(DecodeHistograms(memory_manager, br, kNumTreeContexts,
124 &tree_code, &tree_context_map));
125 // TODO(eustas): investigate more infinite tree cases.
126 if (tree_code.degenerate_symbols[tree_context_map[kPropertyContext]] > 0) {
127 return JXL_FAILURE("Infinite tree");
128 }
129 JXL_ASSIGN_OR_RETURN(ANSSymbolReader reader,
130 ANSSymbolReader::Create(&tree_code, br));
131 JXL_RETURN_IF_ERROR(DecodeTree(br, &reader, tree_context_map, tree,
132 std::min(tree_size_limit, kMaxTreeSize)));
133 if (!reader.CheckANSFinalState()) {
134 return JXL_FAILURE("ANS decode final state failed");
135 }
136 return true;
137 }
138
139 } // namespace jxl