Add a small LRU cache for the JBIG2 symbol dictionary.

This reduces rendering time on my test document by over
10 seconds. It is super common for a JBIG2 dictionary to
span multiple pages, so we don't want to decode the same
dictionary over and over again.

Original patch from Jeff Breidenbach (breidenbach@gmail.com)

BUG=https://code.google.com/p/pdfium/issues/detail?id=85
R=bo_xu@foxitsoftware.com, thestig@chromium.org

Review URL: https://codereview.chromium.org/761313004

3 files changed, 72 insertions, 16 deletions

diff --git a/core/src/fxcodec/jbig2/JBig2_Context.cpp b/core/src/fxcodec/jbig2/JBig2_Context.cpp
index 83ded6fbe1..fec6b5fb68 100644
--- a/core/src/fxcodec/jbig2/JBig2_Context.cpp
+++ b/core/src/fxcodec/jbig2/JBig2_Context.cpp
@@ -4,7 +4,21 @@
  
 // 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 pages in a PDF file,
+// and we do not want to decode the same dictionary over and over
+// again. We key off of the memory location of the dictionary. The
+// list keeps track of the freshness of entries, with freshest ones
+// at the front. Even a tiny cache size like 2 makes a dramatic
+// difference for typical JBIG2 documents.
+const int kSymbolDictCacheMaxSize = 2;
+typedef std::pair<FX_BYTE*, CJBig2_SymbolDict*> CJBig2_CachePair;
+static std::list<CJBig2_CachePair> SymbolDictCache;
+
 void OutputBitmap(CJBig2_Image* pImage)
 {
     if(!pImage) {
@@ -614,6 +628,8 @@ FX_INT32 CJBig2_Context::parseSymbolDict(CJBig2_Segment *pSegment, IFX_Pause* pP
     JBig2ArithCtx *gbContext = NULL, *grContext = NULL;
     CJBig2_ArithDecoder *pArithDecoder;
     JBIG2_ALLOC(pSymbolDictDecoder, CJBig2_SDDProc());
+    FX_BYTE *key = pSegment->m_pData;
+    FX_BOOL cache_hit = false;
     if(m_pStream->readShortInteger(&wFlags) != 0) {
         m_pModule->JBig2_Error("symbol dictionary segment : data header too short.");
         nRet = JBIG2_ERROR_TOO_SHORT;
@@ -791,23 +807,43 @@ FX_INT32 CJBig2_Context::parseSymbolDict(CJBig2_Segment *pSegment, IFX_Pause* pP
         }
     }
     pSegment->m_nResultType = JBIG2_SYMBOL_DICT_POINTER;
-    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;
+    for(std::list<CJBig2_CachePair>::iterator it =
+            SymbolDictCache.begin(); it != SymbolDictCache.end(); ++it) {
+        if (it->first == key) {
+            pSegment->m_Result.sd = it->second->DeepCopy();
+            SymbolDictCache.push_front(*it);
+            SymbolDictCache.erase(it);
+            cache_hit = true;
+            break;
         }
-        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;
+    }
+    if (!cache_hit) {
+        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();
+        }
+        CJBig2_SymbolDict *value = pSegment->m_Result.sd->DeepCopy();
+        if (value) {
+            while (SymbolDictCache.size() >= kSymbolDictCacheMaxSize) {
+                delete SymbolDictCache.back().second;
+                SymbolDictCache.pop_back();
+            }
+            SymbolDictCache.push_front(CJBig2_CachePair(key, value));
         }
-        m_pStream->alignByte();
     }
     if(wFlags & 0x0200) {
         pSegment->m_Result.sd->m_bContextRetained = TRUE;
diff --git a/core/src/fxcodec/jbig2/JBig2_SymbolDict.cpp b/core/src/fxcodec/jbig2/JBig2_SymbolDict.cpp
index 67e54c0cea..bad2fc4bce 100644
--- a/core/src/fxcodec/jbig2/JBig2_SymbolDict.cpp
+++ b/core/src/fxcodec/jbig2/JBig2_SymbolDict.cpp
@@ -13,6 +13,26 @@ CJBig2_SymbolDict::CJBig2_SymbolDict()
     m_gbContext = m_grContext = NULL;
 }
 
+CJBig2_SymbolDict *CJBig2_SymbolDict::DeepCopy()
+{
+    CJBig2_SymbolDict *dst = NULL;
+    CJBig2_SymbolDict *src = this;
+    if (src->m_bContextRetained ||
+        src->m_gbContext ||
+        src->m_grContext) {
+        return NULL;
+    }
+    JBIG2_ALLOC(dst, CJBig2_SymbolDict());
+    dst->SDNUMEXSYMS = src->SDNUMEXSYMS;
+    dst->SDEXSYMS = (CJBig2_Image**)m_pModule->JBig2_Malloc2(
+        sizeof(CJBig2_Image*), src->SDNUMEXSYMS);
+    for(FX_DWORD i = 0; i < src->SDNUMEXSYMS; i++) {
+        JBIG2_ALLOC(dst->SDEXSYMS[i],
+                    CJBig2_Image(*(src->SDEXSYMS[i])));
+    }
+    return dst;
+}
+
 CJBig2_SymbolDict::~CJBig2_SymbolDict()
 {
     if(SDEXSYMS) {
diff --git a/core/src/fxcodec/jbig2/JBig2_SymbolDict.h b/core/src/fxcodec/jbig2/JBig2_SymbolDict.h
index cfe75db4c9..9156e30ea8 100644
--- a/core/src/fxcodec/jbig2/JBig2_SymbolDict.h
+++ b/core/src/fxcodec/jbig2/JBig2_SymbolDict.h
@@ -14,7 +14,7 @@ class CJBig2_SymbolDict : public CJBig2_Object
 public:
 
     CJBig2_SymbolDict();
-
+    CJBig2_SymbolDict *DeepCopy();
     ~CJBig2_SymbolDict();
 public:
     FX_DWORD SDNUMEXSYMS;