1 // Copyright 2016 The PDFium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7 #include "core/fpdfdoc/cpdf_numbertree.h"
8
9 #include <optional>
10 #include <utility>
11
12 #include "core/fpdfapi/parser/cpdf_array.h"
13 #include "core/fpdfapi/parser/cpdf_dictionary.h"
14
15 namespace {
16
FindNumberNode(const CPDF_Dictionary * node_dict,int num)17 RetainPtr<const CPDF_Object> FindNumberNode(const CPDF_Dictionary* node_dict,
18 int num) {
19 RetainPtr<const CPDF_Array> limits_array = node_dict->GetArrayFor("Limits");
20 if (limits_array && (num < limits_array->GetIntegerAt(0) ||
21 num > limits_array->GetIntegerAt(1))) {
22 return nullptr;
23 }
24 RetainPtr<const CPDF_Array> numbers_array = node_dict->GetArrayFor("Nums");
25 if (numbers_array) {
26 for (size_t i = 0; i < numbers_array->size() / 2; i++) {
27 int index = numbers_array->GetIntegerAt(i * 2);
28 if (num == index) {
29 return numbers_array->GetDirectObjectAt(i * 2 + 1);
30 }
31 if (index > num) {
32 break;
33 }
34 }
35 return nullptr;
36 }
37
38 RetainPtr<const CPDF_Array> kids_array = node_dict->GetArrayFor("Kids");
39 if (!kids_array) {
40 return nullptr;
41 }
42
43 for (size_t i = 0; i < kids_array->size(); i++) {
44 RetainPtr<const CPDF_Dictionary> kid_dict = kids_array->GetDictAt(i);
45 if (!kid_dict) {
46 continue;
47 }
48
49 RetainPtr<const CPDF_Object> result = FindNumberNode(kid_dict.Get(), num);
50 if (result) {
51 return result;
52 }
53 }
54 return nullptr;
55 }
56
FindLowerBound(const CPDF_Dictionary * node_dict,int num)57 std::optional<CPDF_NumberTree::KeyValue> FindLowerBound(
58 const CPDF_Dictionary* node_dict,
59 int num) {
60 RetainPtr<const CPDF_Array> limits_array = node_dict->GetArrayFor("Limits");
61 if (limits_array) {
62 if (num < limits_array->GetIntegerAt(0)) {
63 return std::nullopt;
64 }
65 const int max_value = limits_array->GetIntegerAt(1);
66 if (num >= max_value) {
67 return CPDF_NumberTree::KeyValue(max_value,
68 FindNumberNode(node_dict, max_value));
69 }
70 }
71
72 RetainPtr<const CPDF_Array> numbers_array = node_dict->GetArrayFor("Nums");
73 if (numbers_array) {
74 for (size_t i = numbers_array->size() / 2; i > 0; --i) {
75 const size_t key_index = (i - 1) * 2;
76 const int key = numbers_array->GetIntegerAt(key_index);
77 if (num >= key) {
78 const size_t value_index = key_index + 1;
79 return CPDF_NumberTree::KeyValue(
80 key, numbers_array->GetDirectObjectAt(value_index));
81 }
82 }
83 return std::nullopt;
84 }
85
86 RetainPtr<const CPDF_Array> kids_array = node_dict->GetArrayFor("Kids");
87 if (!kids_array) {
88 return std::nullopt;
89 }
90
91 for (size_t i = kids_array->size(); i > 0; --i) {
92 RetainPtr<const CPDF_Dictionary> kid_dict = kids_array->GetDictAt(i - 1);
93 if (!kid_dict) {
94 continue;
95 }
96
97 std::optional<CPDF_NumberTree::KeyValue> result =
98 FindLowerBound(kid_dict.Get(), num);
99 if (result.has_value()) {
100 return result;
101 }
102 }
103 return std::nullopt;
104 }
105
106 } // namespace
107
CPDF_NumberTree(RetainPtr<const CPDF_Dictionary> root)108 CPDF_NumberTree::CPDF_NumberTree(RetainPtr<const CPDF_Dictionary> root)
109 : root_(std::move(root)) {}
110
111 CPDF_NumberTree::~CPDF_NumberTree() = default;
112
LookupValue(int num) const113 RetainPtr<const CPDF_Object> CPDF_NumberTree::LookupValue(int num) const {
114 return FindNumberNode(root_.Get(), num);
115 }
116
GetLowerBound(int num) const117 std::optional<CPDF_NumberTree::KeyValue> CPDF_NumberTree::GetLowerBound(
118 int num) const {
119 return FindLowerBound(root_.Get(), num);
120 }
121
KeyValue(int key,RetainPtr<const CPDF_Object> value)122 CPDF_NumberTree::KeyValue::KeyValue(int key, RetainPtr<const CPDF_Object> value)
123 : key(key), value(std::move(value)) {}
124
125 CPDF_NumberTree::KeyValue::KeyValue(CPDF_NumberTree::KeyValue&&) noexcept =
126 default;
127
128 CPDF_NumberTree::KeyValue& CPDF_NumberTree::KeyValue::operator=(
129 CPDF_NumberTree::KeyValue&&) noexcept = default;
130
131 CPDF_NumberTree::KeyValue::~KeyValue() = default;
132