cpdf_nametree.cpp revision 4d3acf4ec42bf6e838f9060103aff98fbf170794 
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
13namespace {
14
15const int nMaxRecursion = 32;
16
17CPDF_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
78CPDF_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
114size_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
139CPDF_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
153size_t CPDF_NameTree::GetCount() const {
154  return m_pRoot ? ::CountNames(m_pRoot) : 0;
155}
156
157int 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
167CPDF_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
175CPDF_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
182CPDF_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