Add a small LRU cache for the JBIG2 symbol dictionary.

core/src/fxcodec/jbig2/JBig2_Context.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 <map>
+#include <list>
 #include "JBig2_Context.h"
+
+// Implement a very small least recently used (LRU) cache. It is very
+// common for a JBIG2 dictionary to span multiple page in a PDF file,
+// and we do not want to decode the same dictionary over an over
+// again. We key off of the memory location of the dictionary. The
+// list keeps track of the freshness of enties, with freshest ones are
+// at the front. Even a tiny cache size like 2 makes a dramatic
+// difference for Google Books PDF files.
+const int kMaxCacheSize = 2;

[Tom Sepez, 2014/12/10 00:14:46]

nit: Let's rename this something like kMaxKBIG2DictionaryCacheSize, since the
name "cache" isn't very specific.

[jab, 2014/12/11 04:40:46]

Done.

+static std::map<FX_BYTE*, CJBig2_SymbolDict*> cache;

[Tom Sepez, 2014/12/10 00:14:46]

Others have mentioned it, but let's not add any static memory.  We really need
to find an object to own this.

[jab, 2014/12/10 07:16:17]

Based on Bo's comment, this requires refactoring beyond my 
capability as a PDFium beginner. Can I either have a whole 
bunch of hand holding, or would someone experienced be 
willing to complete the work?

I'm worried that if the answer is no to both questions, then
the problem will never be fixed. That's bad because this is a 
user visible, major performance problem for a certain class of
documents.

+static list<FX_BYTE*> cache_keys;

[Tom Sepez, 2014/12/10 00:14:46]

why do we need both a map and a list if there's only going to be a few of these?
 Having a std::list<std::pair<FX_BYTE*, CJBig2_SymbolDict*>> should be
sufficient, since you've indicated that we don't have to crank the size up to
get the benefit.  This would avoid trying to keep the two data structures in
sync with each other.

[jab, 2014/12/11 04:40:46]

Done.

+
 void OutputBitmap(CJBig2_Image* pImage)
 {
     if(!pImage) {
         return;
     }
 }
 CJBig2_Context *CJBig2_Context::CreateContext(CJBig2_Module *pModule, FX_BYTE *pGlobalData, FX_DWORD dwGlobalLength,
         FX_BYTE *pData, FX_DWORD dwLength, FX_INT32 nStreamType, IFX_Pause* pPause)
 {
     return new(pModule) CJBig2_Context(pGlobalData, dwGlobalLength, pData, dwLength, nStreamType, pPause);
@@ skipping 589 matching lines @@
     FX_BYTE cSDHUFFDH, cSDHUFFDW, cSDHUFFBMSIZE, cSDHUFFAGGINST;
     CJBig2_HuffmanTable *Table_B1 = NULL, *Table_B2 = NULL, *Table_B3 = NULL, *Table_B4 = NULL, *Table_B5 = NULL;
     FX_INT32 i, nIndex, nRet;
     CJBig2_Segment *pSeg = NULL, *pLRSeg = NULL;
     FX_BOOL bUsed;
     CJBig2_Image ** SDINSYMS = NULL;
     CJBig2_SDDProc *pSymbolDictDecoder;
     JBig2ArithCtx *gbContext = NULL, *grContext = NULL;
     CJBig2_ArithDecoder *pArithDecoder;
     JBIG2_ALLOC(pSymbolDictDecoder, CJBig2_SDDProc());
+    FX_BYTE *key = pSegment->m_pData;
     if(m_pStream->readShortInteger(&wFlags) != 0) {
         m_pModule->JBig2_Error("symbol dictionary segment : data header too short.");
         nRet = JBIG2_ERROR_TOO_SHORT;
         goto failed;
     }
     pSymbolDictDecoder->SDHUFF = wFlags & 0x0001;
     pSymbolDictDecoder->SDREFAGG = (wFlags >> 1) & 0x0001;
     pSymbolDictDecoder->SDTEMPLATE = (wFlags >> 10) & 0x0003;
     pSymbolDictDecoder->SDRTEMPLATE = (wFlags >> 12) & 0x0003;
     cSDHUFFDH = (wFlags >> 2) & 0x0003;
@@ skipping 157 matching lines @@
             gbContext = (JBig2ArithCtx*)m_pModule->JBig2_Malloc2(sizeof(JBig2ArithCtx), dwTemp);
             JBIG2_memset(gbContext, 0, sizeof(JBig2ArithCtx)*dwTemp);
         }
         if (pSymbolDictDecoder->SDREFAGG == 1) {
             dwTemp = pSymbolDictDecoder->SDRTEMPLATE ? 1 << 10 : 1 << 13;
             grContext = (JBig2ArithCtx*)m_pModule->JBig2_Malloc2(sizeof(JBig2ArithCtx), dwTemp);
             JBIG2_memset(grContext, 0, sizeof(JBig2ArithCtx)*dwTemp);
         }
     }
     pSegment->m_nResultType = JBIG2_SYMBOL_DICT_POINTER;
-    if(pSymbolDictDecoder->SDHUFF == 0) {
+    if (cache.find(key) != cache.end()) {
+        pSegment->m_Result.sd = cache[key]->DeepCopy();
+        for(std::list<FX_BYTE*>::iterator it = cache_keys.begin();
+            it != cache_keys.end(); ++it) {
+            if (*it == key) {
+                cache_keys.erase(it);
+                break;
+            }
+        }
+        cache_keys.push_front(key);
+    } else if(pSymbolDictDecoder->SDHUFF == 0) {
         JBIG2_ALLOC(pArithDecoder, CJBig2_ArithDecoder(m_pStream));
         pSegment->m_Result.sd = pSymbolDictDecoder->decode_Arith(pArithDecoder, gbContext, grContext);
         delete pArithDecoder;
         if(pSegment->m_Result.sd == NULL) {
             nRet = JBIG2_ERROR_FETAL;
             goto failed;
         }
         m_pStream->alignByte();
         m_pStream->offset(2);
     } else {
         pSegment->m_Result.sd = pSymbolDictDecoder->decode_Huffman(m_pStream, gbContext, grContext, pPause);
         if(pSegment->m_Result.sd == NULL) {
             nRet = JBIG2_ERROR_FETAL;
             goto failed;
         }
         m_pStream->alignByte();
     }
+    if (cache.find(key) == cache.end()) {
+        CJBig2_SymbolDict *value = pSegment->m_Result.sd->DeepCopy();
+        if (value) {
+            while (cache_keys.size() >= kMaxCacheSize) {
+                delete cache[cache_keys.back()];
+                cache.erase(cache_keys.back());
+                cache_keys.pop_back();
+            }
+            cache.insert(std::pair<FX_BYTE*, CJBig2_SymbolDict*>(key, value));
+            cache_keys.push_front(key);
+        }
+    }
     if(wFlags & 0x0200) {
         pSegment->m_Result.sd->m_bContextRetained = TRUE;
         if(pSymbolDictDecoder->SDHUFF == 0) {
             pSegment->m_Result.sd->m_gbContext = gbContext;
         }
         if(pSymbolDictDecoder->SDREFAGG == 1) {
             pSegment->m_Result.sd->m_grContext = grContext;
         }
         bUsed = TRUE;
     } else {
@@ skipping 981 matching lines @@
                 SBSYMCODES[CURTEMP].code = CURCODE;
                 CURCODE = CURCODE + 1;
             }
             CURTEMP = CURTEMP + 1;
         }
         CURLEN = CURLEN + 1;
     }
     m_pModule->JBig2_Free(LENCOUNT);
     m_pModule->JBig2_Free(FIRSTCODE);
 }