1 // Copyright 2016 PDFium Authors. All rights reserved.
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_nametree.h"
8
9 #include "core/fpdfapi/parser/cpdf_array.h"
10 #include "core/fpdfapi/parser/cpdf_dictionary.h"
11 #include "core/fpdfapi/parser/cpdf_document.h"
12
13 namespace {
14
15 const int nMaxRecursion = 32;
16
SearchNameNode(CPDF_Dictionary * pNode,const CFX_ByteString & csName,size_t & nIndex,CPDF_Array ** ppFind,int nLevel=0)17 CPDF_Object* SearchNameNode(CPDF_Dictionary* pNode,
18 const CFX_ByteString& csName,
19 size_t& nIndex,
20 CPDF_Array** ppFind,
21 int nLevel = 0) {
22 if (nLevel > nMaxRecursion)
23 return nullptr;
24
25 CPDF_Array* pLimits = pNode->GetArrayFor("Limits");
26 if (pLimits) {
27 CFX_ByteString csLeft = pLimits->GetStringAt(0);
28 CFX_ByteString csRight = pLimits->GetStringAt(1);
29 if (csLeft.Compare(csRight.AsStringC()) > 0) {
30 CFX_ByteString csTmp = csRight;
31 csRight = csLeft;
32 csLeft = csTmp;
33 }
34 if (csName.Compare(csLeft.AsStringC()) < 0 ||
35 csName.Compare(csRight.AsStringC()) > 0) {
36 return nullptr;
37 }
38 }
39
40 CPDF_Array* pNames = pNode->GetArrayFor("Names");
41 if (pNames) {
42 size_t dwCount = pNames->GetCount() / 2;
43 for (size_t i = 0; i < dwCount; i++) {
44 CFX_ByteString csValue = pNames->GetStringAt(i * 2);
45 int32_t iCompare = csValue.Compare(csName.AsStringC());
46 if (iCompare <= 0) {
47 if (ppFind)
48 *ppFind = pNames;
49 if (iCompare < 0)
50 continue;
51 } else {
52 break;
53 }
54 nIndex += i;
55 return pNames->GetDirectObjectAt(i * 2 + 1);
56 }
57 nIndex += dwCount;
58 return nullptr;
59 }
60
61 CPDF_Array* pKids = pNode->GetArrayFor("Kids");
62 if (!pKids)
63 return nullptr;
64
65 for (size_t i = 0; i < pKids->GetCount(); i++) {
66 CPDF_Dictionary* pKid = pKids->GetDictAt(i);
67 if (!pKid)
68 continue;
69
70 CPDF_Object* pFound =
71 SearchNameNode(pKid, csName, nIndex, ppFind, nLevel + 1);
72 if (pFound)
73 return pFound;
74 }
75 return nullptr;
76 }
77
SearchNameNode(CPDF_Dictionary * pNode,size_t nIndex,size_t & nCurIndex,CFX_ByteString & csName,CPDF_Array ** ppFind,int nLevel=0)78 CPDF_Object* SearchNameNode(CPDF_Dictionary* pNode,
79 size_t nIndex,
80 size_t& nCurIndex,
81 CFX_ByteString& csName,
82 CPDF_Array** ppFind,
83 int nLevel = 0) {
84 if (nLevel > nMaxRecursion)
85 return nullptr;
86
87 CPDF_Array* pNames = pNode->GetArrayFor("Names");
88 if (pNames) {
89 size_t nCount = pNames->GetCount() / 2;
90 if (nIndex >= nCurIndex + nCount) {
91 nCurIndex += nCount;
92 return nullptr;
93 }
94 if (ppFind)
95 *ppFind = pNames;
96 csName = pNames->GetStringAt((nIndex - nCurIndex) * 2);
97 return pNames->GetDirectObjectAt((nIndex - nCurIndex) * 2 + 1);
98 }
99 CPDF_Array* pKids = pNode->GetArrayFor("Kids");
100 if (!pKids)
101 return nullptr;
102 for (size_t i = 0; i < pKids->GetCount(); i++) {
103 CPDF_Dictionary* pKid = pKids->GetDictAt(i);
104 if (!pKid)
105 continue;
106 CPDF_Object* pFound =
107 SearchNameNode(pKid, nIndex, nCurIndex, csName, ppFind, nLevel + 1);
108 if (pFound)
109 return pFound;
110 }
111 return nullptr;
112 }
113
CountNames(CPDF_Dictionary * pNode,int nLevel=0)114 size_t CountNames(CPDF_Dictionary* pNode, int nLevel = 0) {
115 if (nLevel > nMaxRecursion)
116 return 0;
117
118 CPDF_Array* pNames = pNode->GetArrayFor("Names");
119 if (pNames)
120 return pNames->GetCount() / 2;
121
122 CPDF_Array* pKids = pNode->GetArrayFor("Kids");
123 if (!pKids)
124 return 0;
125
126 size_t nCount = 0;
127 for (size_t i = 0; i < pKids->GetCount(); i++) {
128 CPDF_Dictionary* pKid = pKids->GetDictAt(i);
129 if (!pKid)
130 continue;
131
132 nCount += CountNames(pKid, nLevel + 1);
133 }
134 return nCount;
135 }
136
137 } // namespace
138
CPDF_NameTree(CPDF_Document * pDoc,const CFX_ByteString & category)139 CPDF_NameTree::CPDF_NameTree(CPDF_Document* pDoc,
140 const CFX_ByteString& category)
141 : m_pRoot(nullptr) {
142 CPDF_Dictionary* pRoot = pDoc->GetRoot();
143 if (!pRoot)
144 return;
145
146 CPDF_Dictionary* pNames = pRoot->GetDictFor("Names");
147 if (!pNames)
148 return;
149
150 m_pRoot = pNames->GetDictFor(category);
151 }
152
GetCount() const153 size_t CPDF_NameTree::GetCount() const {
154 return m_pRoot ? ::CountNames(m_pRoot) : 0;
155 }
156
GetIndex(const CFX_ByteString & csName) const157 int CPDF_NameTree::GetIndex(const CFX_ByteString& csName) const {
158 if (!m_pRoot)
159 return -1;
160
161 size_t nIndex = 0;
162 if (!SearchNameNode(m_pRoot, csName, nIndex, nullptr))
163 return -1;
164 return nIndex;
165 }
166
LookupValue(int nIndex,CFX_ByteString & csName) const167 CPDF_Object* CPDF_NameTree::LookupValue(int nIndex,
168 CFX_ByteString& csName) const {
169 if (!m_pRoot)
170 return nullptr;
171 size_t nCurIndex = 0;
172 return SearchNameNode(m_pRoot, nIndex, nCurIndex, csName, nullptr);
173 }
174
LookupValue(const CFX_ByteString & csName) const175 CPDF_Object* CPDF_NameTree::LookupValue(const CFX_ByteString& csName) const {
176 if (!m_pRoot)
177 return nullptr;
178 size_t nIndex = 0;
179 return SearchNameNode(m_pRoot, csName, nIndex, nullptr);
180 }
181
LookupNamedDest(CPDF_Document * pDoc,const CFX_ByteString & sName)182 CPDF_Array* CPDF_NameTree::LookupNamedDest(CPDF_Document* pDoc,
183 const CFX_ByteString& sName) {
184 CPDF_Object* pValue = LookupValue(sName);
185 if (!pValue) {
186 CPDF_Dictionary* pDests = pDoc->GetRoot()->GetDictFor("Dests");
187 if (!pDests)
188 return nullptr;
189 pValue = pDests->GetDirectObjectFor(sName);
190 }
191 if (!pValue)
192 return nullptr;
193 if (CPDF_Array* pArray = pValue->AsArray())
194 return pArray;
195 if (CPDF_Dictionary* pDict = pValue->AsDictionary())
196 return pDict->GetArrayFor("D");
197 return nullptr;
198 }
199