Remove CFX_FileSizeArray.

core/src/fpdfapi/fpdf_parser/fpdf_parser_parser.cpp

 // Copyright 2014 PDFium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
 
 #include "core/include/fpdfapi/fpdf_parser.h"
 
 #include <algorithm>
 #include <memory>
@@ skipping 18 matching lines @@
 // A limit on the maximum object number in the xref table. Theoretical limits
 // are higher, but this may be large enough in practice.
 const FX_DWORD kMaxObjectNumber = 1048576;
 
 struct SearchTagRecord {
   const char* m_pTag;
   FX_DWORD m_Len;
   FX_DWORD m_Offset;
 };
 
-int CompareFileSize(const void* p1, const void* p2) {
-  return *(FX_FILESIZE*)p1 - *(FX_FILESIZE*)p2;
-}
-
 int32_t GetHeaderOffset(IFX_FileRead* pFile) {
   const FX_DWORD tag = FXDWORD_FROM_LSBFIRST(0x46445025);
   const size_t kBufSize = 4;
   uint8_t buf[kBufSize];
   int32_t offset = 0;
   while (offset <= 1024) {
     if (!pFile->ReadBlock(buf, offset, kBufSize))
       return -1;
 
     if (*(FX_DWORD*)buf == tag)
@@ skipping 119 matching lines @@
   }
   ReleaseEncryptHandler();
   SetEncryptDictionary(nullptr);
   if (m_bOwnFileRead && m_Syntax.m_pFileAccess) {
     m_Syntax.m_pFileAccess->Release();
     m_Syntax.m_pFileAccess = nullptr;
   }
   m_ObjectStreamMap.clear();
   m_ObjCache.clear();
 
-  m_SortedOffset.RemoveAll();
+  m_SortedOffset.clear();
   m_ObjectInfo.clear();
   int32_t iLen = m_Trailers.GetSize();
   for (int32_t i = 0; i < iLen; ++i) {
     if (CPDF_Dictionary* trailer = m_Trailers.GetAt(i))
       trailer->Release();
   }
   m_Trailers.RemoveAll();
   if (m_pLinearized) {
     m_pLinearized->Release();
     m_pLinearized = nullptr;
@@ skipping 26 matching lines @@
     m_FileVersion += FXSYS_toDecimalDigit(ch);
 
   if (m_Syntax.m_FileLen < m_Syntax.m_HeaderOffset + 9)
     return FORMAT_ERROR;
 
   m_Syntax.RestorePos(m_Syntax.m_FileLen - m_Syntax.m_HeaderOffset - 9);
   m_pDocument = new CPDF_Document(this);
 
   FX_BOOL bXRefRebuilt = FALSE;
   if (m_Syntax.SearchWord("startxref", TRUE, FALSE, 4096)) {
-    FX_FILESIZE startxref_offset = m_Syntax.SavePos();
-    void* pResult = FXSYS_bsearch(&startxref_offset, m_SortedOffset.GetData(),
-                                  m_SortedOffset.GetSize(), sizeof(FX_FILESIZE),
-                                  CompareFileSize);
-    if (!pResult)
-      m_SortedOffset.Add(startxref_offset);
-
+    m_SortedOffset.insert(m_Syntax.SavePos());
     m_Syntax.GetKeyword();
     bool bNumber;
     CFX_ByteString xrefpos_str = m_Syntax.GetNextWord(&bNumber);
     if (!bNumber)
       return FORMAT_ERROR;
 
     m_LastXRefOffset = (FX_FILESIZE)FXSYS_atoi64(xrefpos_str);
     if (!LoadAllCrossRefV4(m_LastXRefOffset) &&
         !LoadAllCrossRefV5(m_LastXRefOffset)) {
       if (!RebuildCrossRef())
@@ skipping 22 matching lines @@
       return FORMAT_ERROR;
 
     eRet = SetEncryptHandler();
     if (eRet != SUCCESS)
       return eRet;
 
     m_pDocument->LoadDoc();
     if (!m_pDocument->GetRoot())
       return FORMAT_ERROR;
   }
-  FXSYS_qsort(m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-              sizeof(FX_FILESIZE), CompareFileSize);
   if (GetRootObjNum() == 0) {
     ReleaseEncryptHandler();
     if (!RebuildCrossRef() || GetRootObjNum() == 0)
       return FORMAT_ERROR;
 
     eRet = SetEncryptHandler();
     if (eRet != SUCCESS)
       return eRet;
   }
   if (m_pSecurityHandler && !m_pSecurityHandler->IsMetadataEncrypted()) {
@@ skipping 69 matching lines @@
   }
   m_pTrailer = LoadTrailerV4();
   if (!m_pTrailer) {
     return FALSE;
   }
 
   int32_t xrefsize = GetDirectInteger(m_pTrailer, "Size");
   if (xrefsize > 0 && xrefsize <= kMaxXRefSize)
     ShrinkObjectMap(xrefsize);
 
-  CFX_FileSizeArray CrossRefList;
-  CFX_FileSizeArray XRefStreamList;
-  CrossRefList.Add(xrefpos);
-  XRefStreamList.Add(GetDirectInteger(m_pTrailer, "XRefStm"));
+  std::vector<FX_FILESIZE> CrossRefList;
+  std::vector<FX_FILESIZE> XRefStreamList;
+  std::set<FX_FILESIZE> seen_xrefpos;
+  CrossRefList.push_back(xrefpos);
+  XRefStreamList.push_back(GetDirectInteger(m_pTrailer, "XRefStm"));
+  seen_xrefpos.insert(xrefpos);
 
-  std::set<FX_FILESIZE> seen_xrefpos;
-  seen_xrefpos.insert(xrefpos);
   // When |m_pTrailer| doesn't have Prev entry or Prev entry value is not
   // numerical, GetDirectInteger() returns 0. Loading will end.
   xrefpos = GetDirectInteger(m_pTrailer, "Prev");
   while (xrefpos) {
     // Check for circular references.
     if (pdfium::ContainsKey(seen_xrefpos, xrefpos))
       return FALSE;
     seen_xrefpos.insert(xrefpos);
-    CrossRefList.InsertAt(0, xrefpos);
+    // SLOW ...

[Lei Zhang, 2016/02/05 19:22:20]

You could push_back() and then iterate through the vector in reverse?

[Tom Sepez, 2016/02/05 21:03:02]

Nah, the fix is to make it a deque, if I can prove the underlying data need not
be contiguous

[Lei Zhang, 2016/02/05 21:09:56]

I was thinking about a deque too, but I realized we are always inserting at the
beginning. In practice, contiguous memory may be good for locality / caching, or
maybe this doesn't really matter in the larger scheme of things.

+    CrossRefList.insert(CrossRefList.begin(), xrefpos);
     LoadCrossRefV4(xrefpos, 0, TRUE);
     std::unique_ptr<CPDF_Dictionary, ReleaseDeleter<CPDF_Dictionary>> pDict(
         LoadTrailerV4());
     if (!pDict)
       return FALSE;
     xrefpos = GetDirectInteger(pDict.get(), "Prev");
-
-    XRefStreamList.InsertAt(0, pDict->GetIntegerBy("XRefStm"));
+    // SLOW ...
+    XRefStreamList.insert(XRefStreamList.begin(),
+                          pDict->GetIntegerBy("XRefStm"));
     m_Trailers.Add(pDict.release());
   }
-  for (int32_t i = 0; i < CrossRefList.GetSize(); i++) {
+  for (size_t i = 0; i < CrossRefList.size(); ++i) {
     if (!LoadCrossRefV4(CrossRefList[i], XRefStreamList[i], FALSE))
       return FALSE;
   }
   return TRUE;
 }
 FX_BOOL CPDF_Parser::LoadLinearizedAllCrossRefV4(FX_FILESIZE xrefpos,
                                                  FX_DWORD dwObjCount) {
   if (!LoadLinearizedCrossRefV4(xrefpos, dwObjCount)) {
     return FALSE;
   }
   m_pTrailer = LoadTrailerV4();
   if (!m_pTrailer) {
     return FALSE;
   }
   int32_t xrefsize = GetDirectInteger(m_pTrailer, "Size");
   if (xrefsize == 0) {
     return FALSE;
   }
-  CFX_FileSizeArray CrossRefList, XRefStreamList;
-  CrossRefList.Add(xrefpos);
-  XRefStreamList.Add(GetDirectInteger(m_pTrailer, "XRefStm"));
 
+  std::vector<FX_FILESIZE> CrossRefList;
+  std::vector<FX_FILESIZE> XRefStreamList;
   std::set<FX_FILESIZE> seen_xrefpos;
+  CrossRefList.push_back(xrefpos);
+  XRefStreamList.push_back(GetDirectInteger(m_pTrailer, "XRefStm"));
   seen_xrefpos.insert(xrefpos);
+
   xrefpos = GetDirectInteger(m_pTrailer, "Prev");
   while (xrefpos) {
     // Check for circular references.
     if (pdfium::ContainsKey(seen_xrefpos, xrefpos))
       return FALSE;
     seen_xrefpos.insert(xrefpos);
-    CrossRefList.InsertAt(0, xrefpos);
+    // SLOW ...
+    CrossRefList.insert(CrossRefList.begin(), xrefpos);
     LoadCrossRefV4(xrefpos, 0, TRUE);
     std::unique_ptr<CPDF_Dictionary, ReleaseDeleter<CPDF_Dictionary>> pDict(
         LoadTrailerV4());
     if (!pDict) {
       return FALSE;
     }
     xrefpos = GetDirectInteger(pDict.get(), "Prev");
-
-    XRefStreamList.InsertAt(0, pDict->GetIntegerBy("XRefStm"));
+    // SLOW ...
+    XRefStreamList.insert(XRefStreamList.begin(),
+                          pDict->GetIntegerBy("XRefStm"));
     m_Trailers.Add(pDict.release());
   }
-  for (int32_t i = 1; i < CrossRefList.GetSize(); i++)
+  for (size_t i = 1; i < CrossRefList.size(); ++i)
     if (!LoadCrossRefV4(CrossRefList[i], XRefStreamList[i], FALSE)) {
       return FALSE;
     }
   return TRUE;
 }
 FX_BOOL CPDF_Parser::LoadLinearizedCrossRefV4(FX_FILESIZE pos,
                                               FX_DWORD dwObjCount) {
   FX_FILESIZE dwStartPos = pos - m_Syntax.m_HeaderOffset;
   m_Syntax.RestorePos(dwStartPos);
-  void* pResult =
-      FXSYS_bsearch(&pos, m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-                    sizeof(FX_FILESIZE), CompareFileSize);
-  if (!pResult) {
-    m_SortedOffset.Add(pos);
-  }
+  m_SortedOffset.insert(pos);
   FX_DWORD start_objnum = 0;
   FX_DWORD count = dwObjCount;
   FX_FILESIZE SavedPos = m_Syntax.SavePos();
   const int32_t recordsize = 20;
   std::vector<char> buf(1024 * recordsize + 1);
   buf[1024 * recordsize] = '\0';
   int32_t nBlocks = count / 1024 + 1;
   for (int32_t block = 0; block < nBlocks; block++) {
     int32_t block_size = block == nBlocks - 1 ? count % 1024 : 1024;
     FX_DWORD dwReadSize = block_size * recordsize;
@@ skipping 18 matching lines @@
               return FALSE;
           }
         }
         m_ObjectInfo[objnum].pos = offset;
         int32_t version = FXSYS_atoi(pEntry + 11);
         if (version >= 1) {
           m_bVersionUpdated = TRUE;
         }
         m_ObjectInfo[objnum].gennum = version;
         if (m_ObjectInfo[objnum].pos < m_Syntax.m_FileLen) {
-          void* pResult = FXSYS_bsearch(
-              &m_ObjectInfo[objnum].pos, m_SortedOffset.GetData(),
-              m_SortedOffset.GetSize(), sizeof(FX_FILESIZE), CompareFileSize);
-          if (!pResult) {
-            m_SortedOffset.Add(m_ObjectInfo[objnum].pos);
-          }
+          m_SortedOffset.insert(m_ObjectInfo[objnum].pos);
         }
         m_ObjectInfo[objnum].type = 1;
       }
     }
   }
   m_Syntax.RestorePos(SavedPos + count * recordsize);
   return TRUE;
 }
 
-bool CPDF_Parser::FindPosInOffsets(FX_FILESIZE pos) const {
-  return FXSYS_bsearch(&pos, m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-                       sizeof(FX_FILESIZE), CompareFileSize);
-}
-
 bool CPDF_Parser::LoadCrossRefV4(FX_FILESIZE pos,
                                  FX_FILESIZE streampos,
                                  FX_BOOL bSkip) {
   m_Syntax.RestorePos(pos);
   if (m_Syntax.GetKeyword() != "xref")
     return false;
 
-  if (!FindPosInOffsets(pos))
-    m_SortedOffset.Add(pos);
-
-  if (streampos && !FindPosInOffsets(streampos))
-      m_SortedOffset.Add(streampos);
+  m_SortedOffset.insert(pos);
+  if (streampos)
+    m_SortedOffset.insert(streampos);
 
   while (1) {
     FX_FILESIZE SavedPos = m_Syntax.SavePos();
     bool bIsNumber;
     CFX_ByteString word = m_Syntax.GetNextWord(&bIsNumber);
     if (word.IsEmpty())
       return false;
 
     if (!bIsNumber) {
       m_Syntax.RestorePos(SavedPos);
@@ skipping 29 matching lines @@
                 if (!std::isdigit(pEntry[c]))
                   return false;
               }
             }
             m_ObjectInfo[objnum].pos = offset;
             int32_t version = FXSYS_atoi(pEntry + 11);
             if (version >= 1) {
               m_bVersionUpdated = TRUE;
             }
             m_ObjectInfo[objnum].gennum = version;
-            if (m_ObjectInfo[objnum].pos < m_Syntax.m_FileLen &&
-                !FindPosInOffsets(m_ObjectInfo[objnum].pos)) {
-              m_SortedOffset.Add(m_ObjectInfo[objnum].pos);
+            if (m_ObjectInfo[objnum].pos < m_Syntax.m_FileLen) {
+              m_SortedOffset.insert(m_ObjectInfo[objnum].pos);
             }
             m_ObjectInfo[objnum].type = 1;
           }
         }
       }
     }
     m_Syntax.RestorePos(SavedPos + count * recordsize);
   }
   return !streampos || LoadCrossRefV5(&streampos, FALSE);
 }
@@ skipping 13 matching lines @@
       return FALSE;
     }
   }
   m_ObjectStreamMap.clear();
   m_bXRefStream = TRUE;
   return TRUE;
 }
 
 FX_BOOL CPDF_Parser::RebuildCrossRef() {
   m_ObjectInfo.clear();
-  m_SortedOffset.RemoveAll();
+  m_SortedOffset.clear();
   if (m_pTrailer) {
     m_pTrailer->Release();
     m_pTrailer = NULL;
   }
   int32_t status = 0;
   int32_t inside_index = 0;
   FX_DWORD objnum = 0;
   FX_DWORD gennum = 0;
   int32_t depth = 0;
   const FX_DWORD kBufferSize = 4096;
@@ skipping 140 matching lines @@
                 inside_index++;
               }
               break;
             case 3:
               if (PDFCharIsWhitespace(byte) || PDFCharIsDelimiter(byte)) {
                 if (objnum > 0x1000000) {
                   status = 0;
                   break;
                 }
                 FX_FILESIZE obj_pos = start_pos - m_Syntax.m_HeaderOffset;
+                m_SortedOffset.insert(obj_pos);
                 last_obj = start_pos;
-                void* pResult =
-                    FXSYS_bsearch(&obj_pos, m_SortedOffset.GetData(),
-                                  m_SortedOffset.GetSize(), sizeof(FX_FILESIZE),
-                                  CompareFileSize);
-                if (!pResult) {
-                  m_SortedOffset.Add(obj_pos);
-                }
                 FX_FILESIZE obj_end = 0;
                 CPDF_Object* pObject = ParseIndirectObjectAtByStrict(
                     m_pDocument, obj_pos, objnum, &obj_end);
                 if (CPDF_Stream* pStream = ToStream(pObject)) {
                   if (CPDF_Dictionary* pDict = pStream->GetDict()) {
                     if ((pDict->KeyExist("Type")) &&
                         (pDict->GetStringBy("Type") == "XRef" &&
                          pDict->KeyExist("Size"))) {
                       CPDF_Object* pRoot = pDict->GetElement("Root");
                       if (pRoot && pRoot->GetDict() &&
@@ skipping 179 matching lines @@
     // If the position has not changed at all in a loop iteration, then break
     // out to prevent infinite looping.
     if (pos == saved_pos)
       break;
   }
   if (last_xref != -1 && last_xref > last_obj) {
     last_trailer = last_xref;
   } else if (last_trailer == -1 || last_xref < last_obj) {
     last_trailer = m_Syntax.m_FileLen;
   }
-  FX_FILESIZE offset = last_trailer - m_Syntax.m_HeaderOffset;
-  void* pResult =
-      FXSYS_bsearch(&offset, m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-                    sizeof(FX_FILESIZE), CompareFileSize);
-  if (!pResult) {
-    m_SortedOffset.Add(offset);
-  }
+  m_SortedOffset.insert(last_trailer - m_Syntax.m_HeaderOffset);
   return m_pTrailer && !m_ObjectInfo.empty();
 }
 
 FX_BOOL CPDF_Parser::LoadCrossRefV5(FX_FILESIZE* pos, FX_BOOL bMainXRef) {
   CPDF_Object* pObject = ParseIndirectObjectAt(m_pDocument, *pos, 0);
   if (!pObject)
     return FALSE;
   if (m_pDocument) {
     FX_BOOL bInserted = FALSE;
     CPDF_Dictionary* pDict = m_pDocument->GetRoot();
@@ skipping 91 matching lines @@
     for (FX_DWORD j = 0; j < count; j++) {
       int32_t type = 1;
       const uint8_t* entrystart = segstart + j * totalWidth;
       if (WidthArray[0]) {
         type = GetVarInt(entrystart, WidthArray[0]);
       }
       if (GetObjectType(startnum + j) == 255) {
         FX_FILESIZE offset =
             GetVarInt(entrystart + WidthArray[0], WidthArray[1]);
         m_ObjectInfo[startnum + j].pos = offset;
-        void* pResult = FXSYS_bsearch(&offset, m_SortedOffset.GetData(),
-                                      m_SortedOffset.GetSize(),
-                                      sizeof(FX_FILESIZE), CompareFileSize);
-        if (!pResult) {
-          m_SortedOffset.Add(offset);
-        }
+        m_SortedOffset.insert(offset);
         continue;
       }
       if (GetObjectType(startnum + j)) {
         continue;
       }
       m_ObjectInfo[startnum + j].type = type;
       if (type == 0) {
         m_ObjectInfo[startnum + j].pos = 0;
       } else {
         FX_FILESIZE offset =
             GetVarInt(entrystart + WidthArray[0], WidthArray[1]);
         m_ObjectInfo[startnum + j].pos = offset;
         if (type == 1) {
-          void* pResult = FXSYS_bsearch(&offset, m_SortedOffset.GetData(),
-                                        m_SortedOffset.GetSize(),
-                                        sizeof(FX_FILESIZE), CompareFileSize);
-          if (!pResult) {
-            m_SortedOffset.Add(offset);
-          }
+          m_SortedOffset.insert(offset);
         } else {
           if (offset < 0 || !IsValidObjectNumber(offset)) {
             pStream->Release();
             return FALSE;
           }
           m_ObjectInfo[offset].type = 255;
         }
       }
     }
     segindex += count;
@@ skipping 24 matching lines @@
 }
 FX_BOOL CPDF_Parser::IsFormStream(FX_DWORD objnum, FX_BOOL& bForm) {
   bForm = FALSE;
   if (!IsValidObjectNumber(objnum))
     return TRUE;
   if (GetObjectType(objnum) == 0)
     return TRUE;
   if (GetObjectType(objnum) == 2)
     return TRUE;
   FX_FILESIZE pos = m_ObjectInfo[objnum].pos;
-  void* pResult =
-      FXSYS_bsearch(&pos, m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-                    sizeof(FX_FILESIZE), CompareFileSize);
-  if (!pResult) {
+  auto it = m_SortedOffset.find(pos);
+  if (it == m_SortedOffset.end())
     return TRUE;
-  }
-  if ((FX_FILESIZE*)pResult - (FX_FILESIZE*)m_SortedOffset.GetData() ==
-      m_SortedOffset.GetSize() - 1) {
+  if (++it == m_SortedOffset.end())
     return FALSE;
-  }
-  FX_FILESIZE size = ((FX_FILESIZE*)pResult)[1] - pos;
+  FX_FILESIZE size = *it - pos;
   FX_FILESIZE SavedPos = m_Syntax.SavePos();
   m_Syntax.RestorePos(pos);
   const char kFormStream[] = "/Form\0stream";
   const CFX_ByteStringC kFormStreamStr(kFormStream, sizeof(kFormStream) - 1);
   bForm = m_Syntax.SearchMultiWord(kFormStreamStr, TRUE, size) == 0;
   m_Syntax.RestorePos(SavedPos);
   return TRUE;
 }
 
 CPDF_Object* CPDF_Parser::ParseIndirectObject(
@@ skipping 61 matching lines @@
   return pStreamAcc;
 }
 
 FX_FILESIZE CPDF_Parser::GetObjectSize(FX_DWORD objnum) const {
   if (!IsValidObjectNumber(objnum))
     return 0;
 
   if (GetObjectType(objnum) == 2)
     objnum = GetObjectPositionOrZero(objnum);
 
-  if (GetObjectType(objnum) == 1 || GetObjectType(objnum) == 255) {
-    FX_FILESIZE offset = GetObjectPositionOrZero(objnum);
-    if (offset == 0)
-      return 0;
+  if (GetObjectType(objnum) != 1 && GetObjectType(objnum) != 255)
+    return 0;
 
-    FX_FILESIZE* pResult = static_cast<FX_FILESIZE*>(FXSYS_bsearch(
-        &offset, m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-        sizeof(FX_FILESIZE), CompareFileSize));
-    if (!pResult)
-      return 0;
+  FX_FILESIZE offset = GetObjectPositionOrZero(objnum);
+  if (offset == 0)
+    return 0;
 
-    if (pResult - m_SortedOffset.GetData() == m_SortedOffset.GetSize() - 1)
-      return 0;
+  auto it = m_SortedOffset.find(offset);
+  if (it == m_SortedOffset.end() || ++it == m_SortedOffset.end())
+    return 0;
 
-    return pResult[1] - offset;
-  }
-  return 0;
+  return *it - offset;
 }
 
 void CPDF_Parser::GetIndirectBinary(FX_DWORD objnum,
                                     uint8_t*& pBuffer,
                                     FX_DWORD& size) {
   pBuffer = NULL;
   size = 0;
   if (!IsValidObjectNumber(objnum))
     return;
 
@@ skipping 51 matching lines @@
   }
   word = m_Syntax.GetNextWord(&bIsNumber);
   if (!bIsNumber) {
     m_Syntax.RestorePos(SavedPos);
     return;
   }
   if (m_Syntax.GetKeyword() != "obj") {
     m_Syntax.RestorePos(SavedPos);
     return;
   }
-  void* pResult =
-      FXSYS_bsearch(&pos, m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-                    sizeof(FX_FILESIZE), CompareFileSize);
-  if (!pResult) {
+  auto it = m_SortedOffset.find(pos);
+  if (it == m_SortedOffset.end() || ++it == m_SortedOffset.end()) {
     m_Syntax.RestorePos(SavedPos);
     return;
   }
-  FX_FILESIZE nextoff = ((FX_FILESIZE*)pResult)[1];
+  FX_FILESIZE nextoff = *it;
   FX_BOOL bNextOffValid = FALSE;
   if (nextoff != pos) {
     m_Syntax.RestorePos(nextoff);
     word = m_Syntax.GetNextWord(&bIsNumber);
     if (word == "xref") {
       bNextOffValid = TRUE;
     } else if (bIsNumber) {
       word = m_Syntax.GetNextWord(&bIsNumber);
       if (bIsNumber && m_Syntax.GetKeyword() == "obj") {
         bNextOffValid = TRUE;
@@ skipping 225 matching lines @@
     }
     eRet = SetEncryptHandler();
     if (eRet != SUCCESS) {
       return eRet;
     }
     m_pDocument->LoadAsynDoc(m_pLinearized->GetDict());
     if (!m_pDocument->GetRoot()) {
       return FORMAT_ERROR;
     }
   }
-  FXSYS_qsort(m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-              sizeof(FX_FILESIZE), CompareFileSize);
   if (GetRootObjNum() == 0) {
     ReleaseEncryptHandler();
     if (!RebuildCrossRef() || GetRootObjNum() == 0)
       return FORMAT_ERROR;
 
     eRet = SetEncryptHandler();
     if (eRet != SUCCESS) {
       return eRet;
     }
   }
@@ skipping 47 matching lines @@
   m_LastXRefOffset += dwCount;
   m_ObjectStreamMap.clear();
   m_ObjCache.clear();
 
   if (!LoadLinearizedAllCrossRefV4(m_LastXRefOffset, m_dwXrefStartObjNum) &&
       !LoadLinearizedAllCrossRefV5(m_LastXRefOffset)) {
     m_LastXRefOffset = 0;
     m_Syntax.m_MetadataObjnum = dwSaveMetadataObjnum;
     return FORMAT_ERROR;
   }
-  FXSYS_qsort(m_SortedOffset.GetData(), m_SortedOffset.GetSize(),
-              sizeof(FX_FILESIZE), CompareFileSize);
   m_Syntax.m_MetadataObjnum = dwSaveMetadataObjnum;
   return SUCCESS;
 }
 
 // static
 int CPDF_SyntaxParser::s_CurrentRecursionDepth = 0;
 
 CPDF_SyntaxParser::CPDF_SyntaxParser() {
   m_pFileAccess = NULL;
   m_pFileBuf = NULL;
@@ skipping 979 matching lines @@
                              CPDF_PageNode* pPageNode,
                              IFX_DownloadHints* pHints);
   FX_BOOL CheckPageCount(IFX_DownloadHints* pHints);
   bool IsFirstCheck(int iPage);
   void ResetFirstCheck(int iPage);
   FX_BOOL IsDataAvail(FX_FILESIZE offset,
                       FX_DWORD size,
                       IFX_DownloadHints* pHints);
 
   CPDF_Parser m_parser;
-
   CPDF_SyntaxParser m_syntaxParser;
-
   CPDF_Object* m_pRoot;
-
   FX_DWORD m_dwRootObjNum;
-
   FX_DWORD m_dwInfoObjNum;
-
   CPDF_Object* m_pLinearized;
-
   CPDF_Object* m_pTrailer;
-
   FX_BOOL m_bDocAvail;
-
   FX_FILESIZE m_dwHeaderOffset;
-
   FX_FILESIZE m_dwLastXRefOffset;
-
   FX_FILESIZE m_dwXRefOffset;
-
   FX_FILESIZE m_dwTrailerOffset;
-
   FX_FILESIZE m_dwCurrentOffset;
-
   PDF_DATAAVAIL_STATUS m_docStatus;
-
   FX_FILESIZE m_dwFileLen;
-
   CPDF_Document* m_pDocument;
-
   std::set<FX_DWORD> m_ObjectSet;
-
   CFX_ArrayTemplate<CPDF_Object*> m_objs_array;
-
   FX_FILESIZE m_Pos;
-
   FX_FILESIZE m_bufferOffset;
-
   FX_DWORD m_bufferSize;
-
   CFX_ByteString m_WordBuf;
-
   uint8_t m_bufferData[512];
-
-  CFX_FileSizeArray m_CrossOffset;
-
+  std::vector<FX_FILESIZE> m_CrossOffset;
   CFX_DWordArray m_XRefStreamList;
-
   CFX_DWordArray m_PageObjList;
-
   FX_DWORD m_PagesObjNum;
-
   FX_BOOL m_bLinearized;
-
   FX_DWORD m_dwFirstPageNo;
-
   FX_BOOL m_bLinearedDataOK;
-
   FX_BOOL m_bMainXRefLoadTried;
-
   FX_BOOL m_bMainXRefLoadedOK;
-
   FX_BOOL m_bPagesTreeLoad;
-
   FX_BOOL m_bPagesLoad;
-
   CPDF_Parser* m_pCurrentParser;
-
   FX_FILESIZE m_dwCurrentXRefSteam;
-
   FX_BOOL m_bAnnotsLoad;
-
   FX_BOOL m_bHaveAcroForm;
-
   FX_DWORD m_dwAcroFormObjNum;
-
   FX_BOOL m_bAcroFormLoad;
-
   CPDF_Object* m_pAcroForm;
-
   CFX_ArrayTemplate<CPDF_Object*> m_arrayAcroforms;
-
   CPDF_Dictionary* m_pPageDict;
-
   CPDF_Object* m_pPageResource;
-
   FX_BOOL m_bNeedDownLoadResource;
-
   FX_BOOL m_bPageLoadedOK;
-
   FX_BOOL m_bLinearizedFormParamLoad;
-
   CFX_ArrayTemplate<CPDF_Object*> m_PagesArray;
-
   FX_DWORD m_dwEncryptObjNum;
-
   FX_FILESIZE m_dwPrevXRefOffset;
-
   FX_BOOL m_bTotalLoadPageTree;
-
   FX_BOOL m_bCurPageDictLoadOK;
-
   CPDF_PageNode m_pageNodes;
-
   std::set<FX_DWORD> m_pageMapCheckState;
   std::set<FX_DWORD> m_pagesLoadState;
-
   std::unique_ptr<CPDF_HintTables> m_pHintTables;
   FX_BOOL m_bSupportHintTable;
 };
 
 IPDF_DataAvail::IPDF_DataAvail(IFX_FileAvail* pFileAvail,
                                IFX_FileRead* pFileRead)
     : m_pFileAvail(pFileAvail), m_pFileRead(pFileRead) {}
 
 // static
 IPDF_DataAvail* IPDF_DataAvail::Create(IFX_FileAvail* pFileAvail,
@@ skipping 73 matching lines @@
   m_pDocument = pDoc;
 }
 FX_DWORD CPDF_DataAvail::GetObjectSize(FX_DWORD objnum, FX_FILESIZE& offset) {
   CPDF_Parser* pParser = m_pDocument->GetParser();
   if (!pParser || !pParser->IsValidObjectNumber(objnum))
     return 0;
 
   if (pParser->GetObjectType(objnum) == 2)
     objnum = pParser->GetObjectPositionOrZero(objnum);
 
-  if (pParser->GetObjectType(objnum) == 1 ||
-      pParser->GetObjectType(objnum) == 255) {
-    offset = pParser->GetObjectPositionOrZero(objnum);
-    if (offset == 0) {
-      return 0;
-    }
-    void* pResult = FXSYS_bsearch(&offset, pParser->m_SortedOffset.GetData(),
-                                  pParser->m_SortedOffset.GetSize(),
-                                  sizeof(FX_FILESIZE), CompareFileSize);
-    if (!pResult) {
-      return 0;
-    }
-    if ((FX_FILESIZE*)pResult -
-            (FX_FILESIZE*)pParser->m_SortedOffset.GetData() ==
-        pParser->m_SortedOffset.GetSize() - 1) {
-      return 0;
-    }
-    return (FX_DWORD)(((FX_FILESIZE*)pResult)[1] - offset);
+  if (pParser->GetObjectType(objnum) != 1 &&
+      pParser->GetObjectType(objnum) != 255) {
+    return 0;
   }
-  return 0;
+
+  offset = pParser->GetObjectPositionOrZero(objnum);
+  if (offset == 0)
+    return 0;
+
+  auto it = pParser->m_SortedOffset.find(offset);
+  if (it == pParser->m_SortedOffset.end() ||
+      ++it == pParser->m_SortedOffset.end()) {
+    return 0;
+  }
+  return *it - offset;
 }
 FX_BOOL CPDF_DataAvail::IsObjectsAvail(
     CFX_ArrayTemplate<CPDF_Object*>& obj_array,
     FX_BOOL bParsePage,
     IFX_DownloadHints* pHints,
     CFX_ArrayTemplate<CPDF_Object*>& ret_array) {
   if (!obj_array.GetSize()) {
     return TRUE;
   }
   FX_DWORD count = 0;
@@ skipping 202 matching lines @@
   return FALSE;
 }
 FX_BOOL CPDF_DataAvail::LoadAllXref(IFX_DownloadHints* pHints) {
   m_parser.m_Syntax.InitParser(m_pFileRead, (FX_DWORD)m_dwHeaderOffset);
   m_parser.m_bOwnFileRead = false;
   if (!m_parser.LoadAllCrossRefV4(m_dwLastXRefOffset) &&
       !m_parser.LoadAllCrossRefV5(m_dwLastXRefOffset)) {
     m_docStatus = PDF_DATAAVAIL_LOADALLFILE;
     return FALSE;
   }
-  FXSYS_qsort(m_parser.m_SortedOffset.GetData(),
-              m_parser.m_SortedOffset.GetSize(), sizeof(FX_FILESIZE),
-              CompareFileSize);
   m_dwRootObjNum = m_parser.GetRootObjNum();
   m_dwInfoObjNum = m_parser.GetInfoObjNum();
   m_pCurrentParser = &m_parser;
   m_docStatus = PDF_DATAAVAIL_ROOT;
   return TRUE;
 }
 CPDF_Object* CPDF_DataAvail::GetObject(FX_DWORD objnum,
                                        IFX_DownloadHints* pHints,
                                        FX_BOOL* pExistInFile) {
   CPDF_Object* pRet = nullptr;
@@ skipping 680 matching lines @@
 }
 FX_BOOL CPDF_DataAvail::CheckCrossRef(IFX_DownloadHints* pHints) {
   int32_t iSize = 0;
   CFX_ByteString token;
   if (!GetNextToken(token)) {
     iSize = (int32_t)(m_Pos + 512 > m_dwFileLen ? m_dwFileLen - m_Pos : 512);
     pHints->AddSegment(m_Pos, iSize);
     return FALSE;
   }
   if (token == "xref") {
-    m_CrossOffset.InsertAt(0, m_dwXRefOffset);
+    // SLOW ...
+    m_CrossOffset.insert(m_CrossOffset.begin(), m_dwXRefOffset);

[Lei Zhang, 2016/02/05 19:22:20]

BTW, we insert into |m_crossoffset| but never read from it.

[Tom Sepez, 2016/02/05 21:03:02]

Removed.

     while (1) {
       if (!GetNextToken(token)) {
         iSize =
             (int32_t)(m_Pos + 512 > m_dwFileLen ? m_dwFileLen - m_Pos : 512);
         pHints->AddSegment(m_Pos, iSize);
         m_docStatus = PDF_DATAAVAIL_CROSSREF_ITEM;
         return FALSE;
       }
       if (token == "trailer") {
         m_dwTrailerOffset = m_Pos;
@@ skipping 655 matching lines @@
   for (int32_t i = 0; i < m_childNode.GetSize(); ++i) {
     delete m_childNode[i];
   }
   m_childNode.RemoveAll();
 }
 CPDF_HintTables::~CPDF_HintTables() {
   m_dwDeltaNObjsArray.RemoveAll();
   m_dwNSharedObjsArray.RemoveAll();
   m_dwSharedObjNumArray.RemoveAll();
   m_dwIdentifierArray.RemoveAll();
-  m_szPageOffsetArray.RemoveAll();
-  m_szSharedObjOffsetArray.RemoveAll();
 }
-FX_DWORD CPDF_HintTables::GetItemLength(int index,
-                                        const CFX_FileSizeArray& szArray) {
-  if (index < 0 || szArray.GetSize() < 2 || index > szArray.GetSize() - 2 ||
-      szArray[index] > szArray[index + 1])
+FX_DWORD CPDF_HintTables::GetItemLength(
+    int index,
+    const std::vector<FX_FILESIZE>& szArray) {
+  if (index < 0 || szArray.size() < 2 || index > szArray.size() - 2 ||
+      szArray[index] > szArray[index + 1]) {
     return 0;
+  }
   return szArray[index + 1] - szArray[index];
 }
 FX_BOOL CPDF_HintTables::ReadPageHintTable(CFX_BitStream* hStream) {
   if (!hStream || hStream->IsEOF())
     return FALSE;
   int nStreamOffset = ReadPrimaryHintStreamOffset();
   int nStreamLen = ReadPrimaryHintStreamLength();
   if (nStreamOffset < 0 || nStreamLen < 1)
     return FALSE;
 
@@ skipping 69 matching lines @@
     dwPageLenArray.Add(safePageLen.ValueOrDie());
   }
   CPDF_Object* pOffsetE = m_pLinearizedDict->GetElementValue("E");
   int nOffsetE = pOffsetE ? pOffsetE->GetInteger() : -1;
   if (nOffsetE < 0)
     return FALSE;
   CPDF_Object* pFirstPageNum = m_pLinearizedDict->GetElementValue("P");
   int nFirstPageNum = pFirstPageNum ? pFirstPageNum->GetInteger() : 0;
   for (int i = 0; i < nPages; ++i) {
     if (i == nFirstPageNum) {
-      m_szPageOffsetArray.Add(m_szFirstPageObjOffset);
+      m_szPageOffsetArray.push_back(m_szFirstPageObjOffset);
     } else if (i == nFirstPageNum + 1) {
       if (i == 1) {
-        m_szPageOffsetArray.Add(nOffsetE);
+        m_szPageOffsetArray.push_back(nOffsetE);
       } else {
-        m_szPageOffsetArray.Add(m_szPageOffsetArray[i - 2] +
-                                dwPageLenArray[i - 2]);
+        m_szPageOffsetArray.push_back(m_szPageOffsetArray[i - 2] +
+                                      dwPageLenArray[i - 2]);
       }
     } else {
       if (i == 0) {
-        m_szPageOffsetArray.Add(nOffsetE);
+        m_szPageOffsetArray.push_back(nOffsetE);
       } else {
-        m_szPageOffsetArray.Add(m_szPageOffsetArray[i - 1] +
-                                dwPageLenArray[i - 1]);
+        m_szPageOffsetArray.push_back(m_szPageOffsetArray[i - 1] +
+                                      dwPageLenArray[i - 1]);
       }
     }
   }
   if (nPages > 0) {
-    m_szPageOffsetArray.Add(m_szPageOffsetArray[nPages - 1] +
-                            dwPageLenArray[nPages - 1]);
+    m_szPageOffsetArray.push_back(m_szPageOffsetArray[nPages - 1] +
+                                  dwPageLenArray[nPages - 1]);
   }
   hStream->ByteAlign();
 
   // number of shared objects
   required_bits = dwSharedObjBits;
   required_bits *= pdfium::base::checked_cast<FX_DWORD>(nPages);
   if (!CanReadFromBitStream(hStream, required_bits))
     return FALSE;
   for (int i = 0; i < nPages; i++) {
     m_dwNSharedObjsArray.Add(hStream->GetBits(dwSharedObjBits));
@@ skipping 81 matching lines @@
   for (int i = 0; i < dwSharedObjTotal; ++i) {
     dwPrevObjLen = dwCurObjLen;
     FX_SAFE_DWORD safeObjLen = hStream->GetBits(dwDeltaGroupLen);
     safeObjLen += dwGroupLeastLen;
     if (!safeObjLen.IsValid())
       return FALSE;
     dwCurObjLen = safeObjLen.ValueOrDie();
     if (i < m_nFirstPageSharedObjs) {
       m_dwSharedObjNumArray.Add(nFirstPageObjNum + i);
       if (i == 0)
-        m_szSharedObjOffsetArray.Add(m_szFirstPageObjOffset);
+        m_szSharedObjOffsetArray.push_back(m_szFirstPageObjOffset);
     } else {
       FX_SAFE_DWORD safeObjNum = dwFirstSharedObjNum;
       safeObjNum += i - m_nFirstPageSharedObjs;
       if (!safeObjNum.IsValid())
         return FALSE;
       m_dwSharedObjNumArray.Add(safeObjNum.ValueOrDie());
       if (i == m_nFirstPageSharedObjs)
-        m_szSharedObjOffsetArray.Add(
+        m_szSharedObjOffsetArray.push_back(
             pdfium::base::checked_cast<int32_t>(dwFirstSharedObjLoc));
     }
     if (i != 0 && i != m_nFirstPageSharedObjs) {
       FX_SAFE_INT32 safeLoc = pdfium::base::checked_cast<int32_t>(dwPrevObjLen);
       safeLoc += m_szSharedObjOffsetArray[i - 1];
       if (!safeLoc.IsValid())
         return FALSE;
-      m_szSharedObjOffsetArray.Add(safeLoc.ValueOrDie());
+      m_szSharedObjOffsetArray.push_back(safeLoc.ValueOrDie());
     }
   }
   if (dwSharedObjTotal > 0) {
     FX_SAFE_INT32 safeLoc = pdfium::base::checked_cast<int32_t>(dwCurObjLen);
     safeLoc += m_szSharedObjOffsetArray[dwSharedObjTotal - 1];
     if (!safeLoc.IsValid())
       return FALSE;
-    m_szSharedObjOffsetArray.Add(safeLoc.ValueOrDie());
+    m_szSharedObjOffsetArray.push_back(safeLoc.ValueOrDie());
   }
   hStream->ByteAlign();
   if (hStream->BitsRemaining() < dwSharedObjTotal)
     return FALSE;
   hStream->SkipBits(dwSharedObjTotal);
   hStream->ByteAlign();
   return TRUE;
 }
 FX_BOOL CPDF_HintTables::GetPagePos(int index,
                                     FX_FILESIZE& szPageStartPos,
@@ skipping 110 matching lines @@
   if (!m_pLinearizedDict)
     return -1;
   CPDF_Array* pRange = m_pLinearizedDict->GetArrayBy("H");
   if (!pRange)
     return -1;
   CPDF_Object* pStreamLen = pRange->GetElementValue(1);
   if (!pStreamLen)
     return -1;
   return pStreamLen->GetInteger();
 }