Add a small LRU cache for the JBIG2 symbol dictionary.

core/src/fxcodec/jbig2/JBig2_Context.cpp

Index: core/src/fxcodec/jbig2/JBig2_Context.cpp
diff --git a/core/src/fxcodec/jbig2/JBig2_Context.cpp b/core/src/fxcodec/jbig2/JBig2_Context.cpp
index 83ded6fbe18f15ac81bde0b7d0de95d9b25ad2be..d8e81540d8f3e0fca6384540cf3c0bcda1f60a56 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 page in a PDF file,

[Tom Sepez, 2014/12/15 19:58:14]

nit: pages

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

Done.

+// and we do not want to decode the same dictionary over an over

[Tom Sepez, 2014/12/15 19:58:14]

nit: over and over

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

Done.

+// again. We key off of the memory location of the dictionary. The
+// list keeps track of the freshness of enties, with freshest ones are

[Lei Zhang, 2014/12/15 19:28:09]

typo: enties -> entities
grammar: "with freshest ones are at the front"

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

Done.

+// 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*> cache_pair;

[Tom Sepez, 2014/12/15 19:58:14]

nit: to match up with the style conventions of this file, this would be called
CJBig2_CachePair.

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

Done.

+static std::list<cache_pair> symbol_dict_cache;

[Tom Sepez, 2014/12/15 19:58:14]

nit: they're less consistent about naming of globals, though SymbolDictCache
would be more consisitent.  Your call on either of these.

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

Done.

+
 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<cache_pair>::iterator it =

[Tom Sepez, 2014/12/15 19:58:14]

nit: auto& it = ..  would be more concise here.  Still, I'm not a fan of
explicit iteration any more when you can do things like

auto& it = std::find_if(symbol_dict_cache.begin(), symbol_dict_cache.end(),
[key](const cache_pair& element) { return element.first == key; });

 

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

I'm really sorry, but this code is too sophisticated for me. I don't feel
comfortable submitting something that I don't understand. I'm also not confident
in my ability to retain understanding over time even if it is clearly explained
to me.

I respectfully request that we reserve this for a future changelist, to be
written by a more sophisticated programmer than myself. 

[jab, 2014/12/16 07:30:57]

please let me know if there is a required change or not. if it is, i will need
some assistance.

+            symbol_dict_cache.begin(); it != symbol_dict_cache.end(); ++it) {
+        if (it->first == key) {
+            pSegment->m_Result.sd = it->second->DeepCopy();
+            symbol_dict_cache.erase(it);

[Lei Zhang, 2014/12/15 19:28:09]

Is |it| still valid after you call erase() on it?

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

I am not a C++ guru, but I can say that the code compiles and runs correctly on
my machine as is. However, I've swapped the two lines anyway.

symbol_dict_cache.push_front(*it);
symbol_dict_cache.erase(it);

[Lei Zhang, 2014/12/16 08:19:31]

I guess I should have said "|it| is not valid after calling erase()" If you look
up std::list::erase() it will say the iterator is invalidated.

As an example:

#include <stdio.h>

#include <list>
#include <string>

int main() {
  std::list<std::string> mylist;
  mylist.push_back("a");
  mylist.push_back("b");
  mylist.push_back("c");
  mylist.push_back("d");

  for (std::list<std::string>::iterator it = mylist.begin();
       it != mylist.end();
       ++it) {
    if (*it == "c") {
      mylist.erase(it);
      mylist.push_front(*it);
      break;
    }
  }
  for (std::list<std::string>::iterator it = mylist.begin();
       it != mylist.end();
       ++it) {
    printf("%s\n", it->c_str());
  }
  return 0;
}

Does not print out:
c
a
b
d

And if you build with: g++ -D_GLIBCXX_DEBUG=1, it will crash.

Swapping works here only because you break out of the loop. Otherwise you'll do
++it on an invalid iterator.

Oh, and you haven't actually swapped the two lines in patch set 7.

+            symbol_dict_cache.push_front(*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 (symbol_dict_cache.size() >= kSymbolDictCacheMaxSize) {
+                delete symbol_dict_cache.back().second;
+                symbol_dict_cache.pop_back();
+            }
+            symbol_dict_cache.push_front(cache_pair(key, value));
         }
-        m_pStream->alignByte();
     }
     if(wFlags & 0x0200) {
         pSegment->m_Result.sd->m_bContextRetained = TRUE;