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..b6aaa01dd35e5e14e3ca0c33addf5b5a209f90a5 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;
 
@@ -202,24 +202,12 @@ bool GIFLZWContext::outputRow()
 // Otherwise, decoding failed; returns false in this case, which will always cause the GIFImageReader to set the "decode failed" flag.
 bool GIFLZWContext::doLZW(const unsigned char* block, size_t bytesInBlock)
 {
-    int code;
-    int incode;
-    const unsigned char *ch;
+    const 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++) {
+    for (const unsigned char* ch = block; bytesInBlock-- > 0; ch++) {
         // Feed the next byte into the decoder's 32-bit input buffer.
         datum += ((int) *ch) << bits;
         bits += 8;
@@ -227,7 +215,7 @@ bool GIFLZWContext::doLZW(const unsigned char* block, size_t bytesInBlock)
         // Check for underflow of decoder's 32-bit input buffer.
         while (bits >= codesize) {
             // Get the leading variable-length symbol from the data stream.
-            code = datum & codemask;
+            int code = datum & codemask;
             datum >>= codesize;
             bits -= codesize;
 
@@ -248,66 +236,72 @@ bool GIFLZWContext::doLZW(const unsigned char* block, size_t bytesInBlock)
                 return false;
             }
 
-            if (oldcode == -1) {
-                *rowIter++ = suffix[code];
-                if (rowIter == rowBuffer.end())
-                    OUTPUT_ROW;
-
-                firstchar = oldcode = code;
-                continue;
-            }
-
-            incode = code;
-            if (code >= avail) {
-                stack[stackp++] = firstchar;
+            const int tempCode = code;
+            unsigned short codeLength = 0;
+            if (code < avail) {
+                // This is a pre-existing code, so we already know what it
+                // encodes.
+                codeLength = suffixLength[code];
+                rowIter += codeLength;
+            } else if (code >= avail && oldcode != -1) {

[Peter Kasting, 2013/09/03 18:49:45]

Why use >= here instead of ==?  This allows an attacker to introduce error to
the code table (because tempCode, and thus eventually oldcode down below, will
be set to the invalid code).

The new testcase I gave you won't catch this, but you could create one with the
invalid code after the beginning of the file that would.

[Alpha Left Google, 2013/09/04 23:47:28]

Nice catch. I didn't realize tempCode would mess up  things. I was planning to
handle bad code like the original but missed the tempCode. Let's make this
correct and if needed be more tolerant of bad data.

+                // 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.
+                codeLength = suffixLength[oldcode] + 1;
+                rowIter += codeLength;
+                *--rowIter = firstchar;

[Peter Kasting, 2013/09/03 18:49:45]

Nit: This subtraction isn't necessary... maybe

codeLength = suffixLength[oldcode];
rowIter += codeLength++;
*rowIter = firstchar;

or

const int length = suffixLength[oldcode];
rowIter += length;
*rowIter = firstchar;
codeLength += length + 1;

Probably the compiler optimizes all these to the same thing, though, so it
doesn't end up mattering.

[Alpha Left Google, 2013/09/04 23:47:28]

I think my original code was the second one but I decided that doesn't matter
performance. I'd like this to better reflect the comments.

[Peter Kasting, 2013/09/05 06:13:01]

OK.  I'm not sure how any of these reflect the comments better than any other,
but since they're probably all equivalent from a performance perspective, I
don't mind using whatever you like best.

                 code = oldcode;
-
-                if (stackp == MAX_BYTES)
-                    return false;
+            } else {
+                // This is an invalid code. The dictionary is just initialized
+                // and the code is incomplete. We don't know how to handle
+                // this case.
+                return false;
             }
 
             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];
+                *--rowIter = suffix[code];
                 code = prefix[code];
-
-                if (stackp == MAX_BYTES)
-                    return false;
             }
 
-            stack[stackp++] = firstchar = suffix[code];
+            *--rowIter = firstchar = suffix[code];
 
-            // Define a new codeword in the dictionary.
-            if (avail < 4096) {
+            // Define a new codeword in the dictionary only if the
+            // dictionary is not in initial state.

[Peter Kasting, 2013/09/03 18:49:45]

Nit: This comment isn't actually correct (checking for oldcode != -1 is not a
check for "the dictionary being in its initial state").  How about:

Define a new codeword in the dictionary as long as we've read more than one
value from the stream.

[Alpha Left Google, 2013/09/04 23:47:28]

Done.

+            if (avail < MAX_DICTIONARY_ENTRIES && oldcode != -1) {
                 prefix[avail] = oldcode;
                 suffix[avail] = firstchar;
-                avail++;
+                suffixLength[avail] = suffixLength[oldcode] + 1;
+                ++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++;
+                // exceed the specified maximum codeword size.
+                if ((!(avail & codemask)) && (avail < MAX_DICTIONARY_ENTRIES)) {

[Peter Kasting, 2013/09/03 18:49:45]

Nit: No parens necessary around unary operator.  I wouldn't put parens around
the binary op either since you're not doing it elsewhere in this function.

[Alpha Left Google, 2013/09/04 23:47:28]

Done.

+                    ++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);
+            oldcode = tempCode;
+            rowIter += codeLength;
+
+            // Output as many rows as possible.
+            GIFRow::iterator rowBegin = rowBuffer.begin();
+            for (; rowBegin + width <= rowIter; rowBegin += width) {
+                if (!outputRow(rowBegin))
+                    return false;
+                rowsRemaining--;
+                if (!rowsRemaining)
+                    return true;
+            }
+
+            if (rowBegin != rowBuffer.begin()) {
+                // Move the remaining bytes to the beginning of the buffer.
+                const size_t bytesToCopy = rowIter - rowBegin;
+                memcpy(rowBuffer.begin(), rowBegin, bytesToCopy);
+                rowIter = rowBuffer.begin() + bytesToCopy;
+            }
         }
     }
-
     return true;
 }
 
@@ -316,12 +310,12 @@ void GIFColorMap::buildTable(const unsigned char* data, size_t length)
     if (!m_isDefined || !m_table.isEmpty())
         return;
 
-    RELEASE_ASSERT(m_position + m_colors * GIF_COLORS <= length);
+    RELEASE_ASSERT(m_position + m_colors * BYTES_PER_COLORMAP_ENTRY <= length);
     const unsigned char* srcColormap = data + m_position;
     m_table.resize(m_colors);
     for (Table::iterator iter = m_table.begin(); iter != m_table.end(); ++iter) {
         *iter = SkPackARGB32NoCheck(255, srcColormap[0], srcColormap[1], srcColormap[2]);
-        srcColormap += GIF_COLORS;
+        srcColormap += BYTES_PER_COLORMAP_ENTRY;
     }
 }
 
@@ -456,7 +450,7 @@ bool GIFImageReader::parseData(size_t dataPosition, size_t len, GIFImageDecoder:
 
             if ((currentComponent[4] & 0x80) && globalColorMapColors > 0) { /* global map */
                 m_globalColorMap.setTablePositionAndSize(dataPosition, globalColorMapColors);
-                GETN(GIF_COLORS * globalColorMapColors, GIFGlobalColormap);
+                GETN(BYTES_PER_COLORMAP_ENTRY * globalColorMapColors, GIFGlobalColormap);
                 break;
             }
 
@@ -694,7 +688,7 @@ bool GIFImageReader::parseData(size_t dataPosition, size_t len, GIFImageDecoder:
                 // The three low-order bits of currentComponent[8] specify the bits per pixel.
                 const size_t numColors = 2 << (currentComponent[8] & 0x7);
                 currentFrame->localColorMap().setTablePositionAndSize(dataPosition, numColors);
-                GETN(GIF_COLORS * numColors, GIFImageColormap);
+                GETN(BYTES_PER_COLORMAP_ENTRY * numColors, GIFImageColormap);
                 break;
             }
 
@@ -758,14 +752,10 @@ bool GIFLZWContext::prepareToDecode()
     ASSERT(m_frameContext->isDataSizeDefined() && m_frameContext->isHeaderDefined());
 
     // Since we use a codesize of 1 more than the datasize, we need to ensure
-    // that our datasize is strictly less than the MAX_LZW_BITS value (12).
-    // This sets the largest possible codemask correctly at 4095.
-    if (m_frameContext->dataSize() >= MAX_LZW_BITS)
+    // that our datasize is strictly less than the MAX_DICTIONARY_ENTRY_BITS.
+    if (m_frameContext->dataSize() >= MAX_DICTIONARY_ENTRY_BITS)
         return false;
     clearCode = 1 << m_frameContext->dataSize();
-    if (clearCode >= MAX_BYTES)
-        return false;
-
     avail = clearCode + 2;
     oldcode = -1;
     codesize = m_frameContext->dataSize() + 1;
@@ -774,18 +764,36 @@ bool GIFLZWContext::prepareToDecode()
     ipass = m_frameContext->interlaced() ? 1 : 0;
     irow = 0;
 
-    // Initialize output row buffer.
-    rowBuffer.resize(m_frameContext->width());
+    // 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);
     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));
-
-    // Clearing the whole prefix table to prevent uninitialized access.
-    memset(prefix, 0, sizeof(prefix));
-    for (int i = 0; i < clearCode; i++)
+    for (int i = 0; i < clearCode; ++i) {
         suffix[i] = i;
-    stackp = 0;
+        suffixLength[i] = 1;
+    }
     return true;
 }