Improve GIF decoding performance

Source/core/platform/image-decoders/gif/GIFImageReader.cpp

Index: Source/core/platform/image-decoders/gif/GIFImageReader.cpp
diff --git a/Source/core/platform/image-decoders/gif/GIFImageReader.cpp b/Source/core/platform/image-decoders/gif/GIFImageReader.cpp
index 7716cedef363aebbee4eca7cfb9af0389a219161..fba6228e96bdf38f5eafd74a39baf0602f225aff 100644
--- a/Source/core/platform/image-decoders/gif/GIFImageReader.cpp
+++ b/Source/core/platform/image-decoders/gif/GIFImageReader.cpp
@@ -98,7 +98,7 @@ using WebCore::GIFImageDecoder;
 #define GETINT16(p)   ((p)[1]<<8|(p)[0])
 
 // Send the data to the display front-end.
-bool GIFLZWContext::outputRow()
+bool GIFLZWContext::outputRow(GIFRow::const_iterator rowBegin)
 {
     int drowStart = irow;
     int drowEnd = irow;
@@ -148,7 +148,7 @@ bool GIFLZWContext::outputRow()
         return true;
 
     // CALLBACK: Let the client know we have decoded a row.
-    if (!m_client->haveDecodedRow(m_frameContext->frameId(), rowBuffer, m_frameContext->width(),
+    if (!m_client->haveDecodedRow(m_frameContext->frameId(), rowBegin, m_frameContext->width(),
         drowStart, drowEnd - drowStart + 1, m_frameContext->progressiveDisplay() && m_frameContext->interlaced() && ipass > 1))
         return false;
 
@@ -205,20 +205,11 @@ bool GIFLZWContext::doLZW(const unsigned char* block, size_t bytesInBlock)
     int code;

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Declare these first three where they are first used.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

     int incode;
     const unsigned char *ch;
+    size_t width = m_frameContext->width();
 
     if (rowIter == rowBuffer.end())
         return true;
 
-#define OUTPUT_ROW \
-    do { \
-        if (!outputRow()) \
-            return false; \
-        rowsRemaining--; \
-        rowIter = rowBuffer.begin(); \
-        if (!rowsRemaining) \
-            return true; \
-    } while (0)
-
     for (ch = block; bytesInBlock-- > 0; ch++) {
         // Feed the next byte into the decoder's 32-bit input buffer.
         datum += ((int) *ch) << bits;
@@ -249,65 +240,95 @@ bool GIFLZWContext::doLZW(const unsigned char* block, size_t bytesInBlock)
             }
 
             if (oldcode == -1) {
+                // The previous code is not available either because this is the first

[Peter Kasting, 2013/08/29 23:46:25]

Tiny nit: It seems like your comments in this section are "almost less than 80
chars, but not quite" and the code actually managed to fit in 80 chars.

While Blink code has no line length restriction, if you're already close to
fitting in 80 chars anyway, I might go ahead and wrap the comments so that they
do fit inside that.  Makes Rietveld reviews a little easier to read, at least...

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                // code in the stream or the dictionary was reset. We'll write the
+                // current code to stream. The code will have only one character.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Maybe better second sentence:

This code must therefore just be a single character, which we can write directly
to the stream.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                firstchar = oldcode = code;
+                if (rowIter >= rowBuffer.end())
+                    return false;
                 *rowIter++ = suffix[code];
-                if (rowIter == rowBuffer.end())
-                    OUTPUT_ROW;
+            } else {
+                incode = code;
+                unsigned short codeLength = 0;
+                if (code < avail) {
+                    // This is a complete code. Code length and code content are known.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: How about just:

This is a pre-existing code, so we already know what it encodes.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                    codeLength = suffixLength[code];
+                    rowIter += codeLength;
+                    if (rowIter >= rowBuffer.end())

[Peter Kasting, 2013/08/29 23:46:25]

Shouldn't this be '>', not ">=", since the row iterator currently points to one
past where we're going to write?  (Also in the block below)

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                        return false;
+                } else if (code == avail) {
+                    // This is an incomplete code. Code length is the length of previous
+                    // code plus one. Code content is that of previous code concatenated
+                    // by the first character of previous code.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: How about:

This is a new code just being added to the dictionary.  It must encode the
contents of the previous code, plus the first character of the previous code
again.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                    codeLength = suffixLength[oldcode] + 1;
+                    rowIter += codeLength;
+                    if (rowIter >= rowBuffer.end())
+                        return false;
+
+                    // The last character of this code is the first character of the
+                    // previous code. Write it to output and then write the previous code.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: This comment seems unnecessary given the above comment.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                    *--rowIter = firstchar;
+                    code = oldcode;
+                } else {
+                    // Bad code received. Complete and incomplete codes are defined up
+                    // to |avail|.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: How about just:

This is an invalid code.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                    return false;
+                }
 
-                firstchar = oldcode = code;
-                continue;
-            }
+                while (code >= clearCode) {
+                    if (code >= MAX_BYTES || code == prefix[code])

[Peter Kasting, 2013/08/29 23:46:25]

|code| must be less than MAX_BYTES, given how it was initialized (i.e. by
masking against codemask).

|code| also cannot be equal to prefix[code].  For this to occur we would have
had to have oldcode == avail at the beginning of this loop iteration, which can
never happen since that would mean that during the previous loop iteration, code
== avail + 1, which would result in bailing out of the function in the
conditionals above.

Therefore, this conditional should be removed entirely, and the comment below
adjusted to note that "Since |code| is guaranteed to be smaller than
sizeof(suffix), ..."

[Alpha Left Google, 2013/08/30 23:25:36]

I removed this block of comments entirely. Having code >= avail actually has
unintended behavior which is prevented by the added check above.

+                        return false;
 
-            incode = code;
-            if (code >= avail) {
-                stack[stackp++] = firstchar;
-                code = oldcode;
+                    // Even though suffix[] only holds characters through suffix[avail - 1],
+                    // allowing code >= avail here lets us be more tolerant of malformed
+                    // data. As long as code < MAX_BYTES, the only risk is a garbled image,
+                    // which is no worse than refusing to display it.
+                    *--rowIter = suffix[code];
+                    code = prefix[code];
+                }
 
-                if (stackp == MAX_BYTES)
-                    return false;
+                *--rowIter = firstchar = suffix[code];
+
+                // Define a new codeword in the dictionary.
+                if (avail < 4096) {

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Use MAX_DICTIONARY_ENTRIES here in place of 4096 (see comments in header
file)

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                    prefix[avail] = oldcode;
+                    suffix[avail] = firstchar;
+                    suffixLength[avail] = suffixLength[oldcode] + 1;
+                    avail++;

[Peter Kasting, 2013/08/29 23:46:25]

Nit: I suggest using preincrement form wherever postincrement is not needed
(looks like 3 more spots in this patch?).  It doesn't really matter with
integral types but it's a good habit to be in for consistency with iterators and
such.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+
+                    // If we've used up all the codewords of a given length
+                    // increase the length of codewords by one bit, but don't
+                    // exceed the specified maximum codeword size of 12 bits.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Remove "of 12 bits".  Here and elsewhere, I'd rather avoid recopying the
constant value into comments.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                    if ((!(avail & codemask)) && (avail < 4096)) {

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Instead of "(avail < 4096)", the equivalent "(codesize <
MAX_DICTIONARY_ENTRY_BITS)" (see comments in header file) would be clearer.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                        codesize++;
+                        codemask += avail;
+                    }
+                }
+                oldcode = incode;
+                rowIter += codeLength;
             }
 
-            while (code >= clearCode) {
-                if (code >= MAX_BYTES || code == prefix[code])
-                    return false;
-
-                // Even though suffix[] only holds characters through suffix[avail - 1],
-                // allowing code >= avail here lets us be more tolerant of malformed
-                // data. As long as code < MAX_BYTES, the only risk is a garbled image,
-                // which is no worse than refusing to display it.
-                stack[stackp++] = suffix[code];
-                code = prefix[code];
+            // Not enough bytes to output row.
+            if (rowIter < rowBuffer.begin() + width)
+                continue;

[Peter Kasting, 2013/08/29 23:46:25]

Nit: It seems slightly clearer to me to skip this, and then below the subsequent
loop, insert a conditional:

if (rowBegin != rowBuffer.begin()) {
  ... memcpy ...

But I suppose in theory this could hurt perf.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

 
-                if (stackp == MAX_BYTES)
+            // There's enough data to output. Output as many rows as possible.
+            GIFRow::iterator rowBegin = rowBuffer.begin();
+            for (;rowBegin + width <= rowIter; rowBegin += width) {

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Space after first semicolon.

If you don't take the previous nit about nuking the conditional above, then this
loop could be converted to "do { ... } while" format and save a comparison.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+                if (!outputRow(rowBegin))
                     return false;
+                rowsRemaining--;
+                if (!rowsRemaining)
+                    return true;
             }
 
-            stack[stackp++] = firstchar = suffix[code];
-
-            // Define a new codeword in the dictionary.
-            if (avail < 4096) {
-                prefix[avail] = oldcode;
-                suffix[avail] = firstchar;
-                avail++;
-
-                // If we've used up all the codewords of a given length
-                // increase the length of codewords by one bit, but don't
-                // exceed the specified maximum codeword size of 12 bits.
-                if ((!(avail & codemask)) && (avail < 4096)) {
-                    codesize++;
-                    codemask += avail;
-                }
-            }
-            oldcode = incode;
-
-            // Copy the decoded data out to the scanline buffer.
-            do {
-                *rowIter++ = stack[--stackp];
-                if (rowIter == rowBuffer.end())
-                    OUTPUT_ROW;
-            } while (stackp > 0);
+            // These bytes cannot make up a full row. Move them to the beginning
+            // of buffer.

[Peter Kasting, 2013/08/29 23:46:25]

Nit: How about just:

Move the remaining bytes to the beginning of the buffer.

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+            size_t bytesToCopy = rowIter - rowBegin;
+            memcpy(rowBuffer.begin(), rowBegin, bytesToCopy);
+            rowIter = rowBuffer.begin() + bytesToCopy;
         }
     }
-
     return true;
 }
 
@@ -775,17 +796,18 @@ bool GIFLZWContext::prepareToDecode()
     irow = 0;
 
     // Initialize output row buffer.
-    rowBuffer.resize(m_frameContext->width());
+    rowBuffer.resize(m_frameContext->width() + MAX_BYTES);

[Peter Kasting, 2013/08/29 23:46:25]

(See my comment atop GIFImageReader.h as to why I want to nuke MAX_BYTES and
introduce MAX_DICTIONARY_ENTRIES.)

Use the correct value here, and add comments:

    // We want to know the longest sequence encodable by a dictionary with
    // MAX_DICTIONARY_ENTRIES entries.  If we ignore the need to encode the base
    // values themselves at the beginning of the dictionary, as well as the need
    // for a clear code or a termination code, we could use every entry to
    // encode a series of multiple values.  If the input value stream looked
    // like "AAAAA..." (a long string of just one value), the first dictionary
    // entry would encode AA, the next AAA, the next AAAA, and so forth.  Thus
    // the longest sequence would be MAX_DICTIONARY_ENTRIES + 1 values.
    //
    // However, we have to account for reserved entries.  The first |datasize|
    // bits are reserved for the base values, and the next two entries are
    // reserved for the clear code and termination code.  In theory a GIF can
    // set the datasize to 0, meaning we have just two reserved entries, making
    // the longest sequence (MAX_DICTIONARY_ENTIRES + 1) - 2 values long.  Since
    // each value is a byte, this is also the number of bytes in the longest
    // encodable sequence.
    const size_t maxBytes = MAX_DICTIONARY_ENTRIES - 1;

    // Now allocate the output buffer.  We decode directly into this buffer
    // until we have at least one row worth of data, then call outputRow().
    // This means worst case we may have (row width - 1) bytes in the buffer and
    // then decode a sequence |maxBytes| long to append.
    rowBuffer.resize(m_frameContext->width() - 1 + maxBytes);

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

     rowIter = rowBuffer.begin();
     rowsRemaining = m_frameContext->height();
 
     // Clearing the whole suffix table lets us be more tolerant of bad data.
     memset(suffix, 0, sizeof(suffix));

[Peter Kasting, 2013/08/29 23:46:25]

Nit: Seems like we could save a little time on the memset and be clearer to boot
by doing:

  for (int i = 0; i < clearCode; ++i)
    suffix[i] = i;
  // Clearing the remainder of the suffix table lets us be more tolerant of bad
data.
   memset(suffix + clearCode, 0, sizeof(suffix) - clearCode);

[Alpha Left Google, 2013/08/30 23:25:36]

Done.

+    for (int i = 0; i < clearCode; ++i)
+        suffix[i] = i;
+    for (int i = 0; i < MAX_BYTES; i++)
+        suffixLength[i] = 1;
 
     // Clearing the whole prefix table to prevent uninitialized access.
     memset(prefix, 0, sizeof(prefix));
-    for (int i = 0; i < clearCode; i++)
-        suffix[i] = i;
-    stackp = 0;
     return true;
 }