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 <vector>
 #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
+// vector keeps track of when an entry should be deleted, to make space
+// for a new one. Even a tiny cache size like 2 makes a dramatic difference
+// for Google Books PDF files.
+const int kMaxCacheSize = 2;
+static std::map<FX_BYTE*, CJBig2_SymbolDict*> cache;
+static std::vector<FX_BYTE*> cache_keys;
+
+
 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::vector<FX_BYTE*>::iterator it = cache_keys.begin();
+            it != cache_keys.end(); ++it) {
+          if (*it == key) {
+            cache_keys.erase(cache_keys.begin());

[Bo Xu, 2014/12/06 05:59:43]

Should line 815 be: "cache_keys.erase(it);" ? I guess this will affect your test
timing?

Nit: The for loop could start from cache_keys.rbegin() as this is the most
recently used one.

[jab, 2014/12/08 21:00:02]

Done.

(I made the front hold the freshest entries)

+            break;

[Bo Xu, 2014/12/07 19:22:50]

Or can we use std:list to replace the std:vector here, so getting the key takes
const time.

[jab, 2014/12/08 21:00:02]

Done.

+          }
+        }
+        cache_keys.push_back(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();

[Bo Xu, 2014/12/06 05:59:43]

should |value| be deleted after use?

[jab, 2014/12/08 21:00:02]

That you. I think I need to free the memory when we remove the entry from the
cache. I am not sure how to do this. Help!

[Bo Xu, 2014/12/08 23:00:17]

How about making the cache member variable of the CJBig2_Context class and let
the destructor do the job?

[jab, 2014/12/08 23:21:04]

I made an explicit call to delete. Is that okay? I think
it is invoking the destructor and my memory checking tool
does not seem to get upset.

[Bo Xu, 2014/12/08 23:29:54]

Sure, the explicit delete is ok here. 
I am thinking moving the static variables into CJBig2_Context, would that be
sufficient to make them available for the whole document?

+        if (value) {
+            while (cache_keys.size() >= kMaxCacheSize) {
+                cache.erase(cache_keys[0]);
+                cache_keys.erase(cache_keys.begin());
+            }
+            cache.insert(std::pair<FX_BYTE*, CJBig2_SymbolDict*>(key, value));
+            cache_keys.push_back(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);
 }