dec_ma.cc (5192B)
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