Improve GIF decoding performance

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

 /* -*- Mode: C; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 /* ***** BEGIN LICENSE BLOCK *****
  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  *
  * The contents of this file are subject to the Mozilla Public License Version
  * 1.1 (the "License"); you may not use this file except in compliance with
  * the License. You may obtain a copy of the License at
  * http://www.mozilla.org/MPL/
  *
  * Software distributed under the License is distributed on an "AS IS" basis,
@@ skipping 80 matching lines @@
 #define GETN(n, s) \
     do { \
         m_bytesToConsume = (n); \
         m_state = (s); \
     } while (0)
 
 // Get a 16-bit value stored in little-endian format.
 #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;
 
     // Haeberli-inspired hack for interlaced GIFs: Replicate lines while
     // displaying to diminish the "venetian-blind" effect as the image is
     // loaded. Adjust pixel vertical positions to avoid the appearance of the
     // image crawling up the screen as successive passes are drawn.
     if (m_frameContext->progressiveDisplay() && m_frameContext->interlaced() && ipass < 4) {
         unsigned rowDup = 0;
@@ skipping 29 matching lines @@
 
         if ((unsigned)drowEnd >= m_frameContext->height())
             drowEnd = m_frameContext->height() - 1;
     }
 
     // Protect against too much image data.
     if ((unsigned)drowStart >= m_frameContext->height())
         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;
 
     if (!m_frameContext->interlaced())
         irow++;
     else {
         do {
             switch (ipass) {
             case 1:
                 irow += 8;
@@ skipping 33 matching lines @@
         } while (irow > (m_frameContext->height() - 1));
     }
     return true;
 }
 
 // Perform Lempel-Ziv-Welch decoding.
 // Returns true if decoding was successful. In this case the block will have been completely consumed and/or rowsRemaining will be 0.
 // 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++) {

[Peter Kasting, 2013/08/31 00:08:49]

Nit: Put * on typename

[Alpha Left Google, 2013/09/01 01:40:21]

Done.

         // Feed the next byte into the decoder's 32-bit input buffer.
         datum += ((int) *ch) << bits;
         bits += 8;
 
         // 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;
 
             // Reset the dictionary to its original state, if requested.
             if (code == clearCode) {
                 codesize = m_frameContext->dataSize() + 1;
                 codemask = (1 << codesize) - 1;
                 avail = clearCode + 2;
                 oldcode = -1;
                 continue;
             }
 
             // Check for explicit end-of-stream code.
             if (code == (clearCode + 1)) {
                 // end-of-stream should only appear after all image data.
                 if (!rowsRemaining)
                     return true;
                 return false;
             }
 
             if (oldcode == -1) {

[Peter Kasting, 2013/08/31 00:08:49]

I just realized that because we don't check that (code < avail) here, an
attacker can sneak a bad code into the beginning of the dictionary  and cause
bad behavior later.  This was a problem with the old code as well.  (For
example, by carefully picking the first couple of codes, I think an attacker can
cause the decoder to infinite loop.  I plan to create a test GIF and check to
see who's vulnerable.)

I think the right solution is to eliminate this block; instead unconditionally
go to what's currently in the other conditional arm.  There, modify the "} else
if (code == avail) {" to be "} else if ((code == avail) && (oldcode != -1)) {".

Added bonus: shorter code.

[Peter Kasting, 2013/08/31 02:07:20]

Update: The old code defended against this with the "if (stackp == MAX_BYTES)"
check inside the while loop, so it would eventually catch the loop and bail.

[Alpha Left Google, 2013/09/01 01:40:21]

I removed this branch and let the other branch handle the initial code. The only
change is we need to have:

if (avail < MAX_DICTIONARY_ENTRIES && oldcode != -1)

Such that he dictionary doesn't reference the invalid code -1.

+                // The previous code is not available either because this is the
+                // first code in the stream or the dictionary was reset.
+                // This code must therefore just be a single character, which we
+                // can write directly to the stream.
+                firstchar = oldcode = code;
+                if (rowIter >= rowBuffer.end())

[Peter Kasting, 2013/08/31 02:07:20]

How can this condition or either of the ones below fail, once the above issue is
addressed?  The comment in prepareToDecode already explained why rowBuffer
should have as many bytes as we can conceivably need.

It seems like we can just nuke all three of these and buy a little more speed.

[Alpha Left Google, 2013/09/01 01:40:21]

That is true. Since we can be sure there's no cycles in the dictionary we won't
be writing outside of the row buffer.

+                    return false;
                 *rowIter++ = suffix[code];
-                if (rowIter == rowBuffer.end())
-                    OUTPUT_ROW;
+            } else {
+                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;
+                    if (rowIter > rowBuffer.end())
+                        return false;
+                } else if (code == avail) {
+                    // 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;
+                    if (rowIter > rowBuffer.end())
+                        return false;
+                    *--rowIter = firstchar;
+                    code = oldcode;
+                } else {
+                    // This is an invalid code.
+                    return false;
+                }
 
-                firstchar = oldcode = code;
-                continue;
+                while (code >= clearCode) {
+                    *--rowIter = suffix[code];
+                    code = prefix[code];
+                }
+
+                *--rowIter = firstchar = suffix[code];
+
+                // Define a new codeword in the dictionary.
+                if (avail < MAX_DICTIONARY_ENTRIES) {
+                    prefix[avail] = oldcode;
+                    suffix[avail] = firstchar;
+                    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.
+                    if ((!(avail & codemask)) && (avail < MAX_DICTIONARY_ENTRIES)) {
+                        ++codesize;
+                        codemask += avail;
+                    }
+                }
+                oldcode = tempCode;
+                rowIter += codeLength;
             }
 
-            incode = code;
-            if (code >= avail) {
-                stack[stackp++] = firstchar;
-                code = oldcode;
-
-                if (stackp == MAX_BYTES)
+            // 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;
             }
 
-            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];
-
-                if (stackp == MAX_BYTES)
-                    return false;
+            if (rowBegin != rowBuffer.begin()) {
+                // Move the remaining bytes to the beginning of buffer.

[Peter Kasting, 2013/08/31 00:08:49]

Nit: buffer -> the buffer

[Alpha Left Google, 2013/09/01 01:40:21]

Done.

+                size_t bytesToCopy = rowIter - rowBegin;

[Peter Kasting, 2013/08/31 00:08:49]

Nit: Can be const (since you seem to be willing to use local const elsewhere
around here)

[Alpha Left Google, 2013/09/01 01:40:21]

Done.

+                memcpy(rowBuffer.begin(), rowBegin, bytesToCopy);
+                rowIter = rowBuffer.begin() + bytesToCopy;
             }
-
-            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);
         }
     }
-
     return true;
 }
 
 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;
     }
 }
 
 // Perform decoding for this frame. frameDecoded will be true if the entire frame is decoded.
 // Returns false if a decoding error occurred. This is a fatal error and causes the GIFImageReader to set the "decode failed" flag.
 // Otherwise, either not enough data is available to decode further than before, or the new data has been decoded successfully; returns true in this case.
 bool GIFFrameContext::decode(const unsigned char* data, size_t length, WebCore::GIFImageDecoder* client, bool* frameDecoded)
 {
     m_localColorMap.buildTable(data, length);
 
@@ skipping 114 matching lines @@
 
             // CALLBACK: Inform the decoderplugin of our size.
             // Note: A subsequent frame might have dimensions larger than the "screen" dimensions.
             if (m_client && !m_client->setSize(m_screenWidth, m_screenHeight))
                 return false;
 
             const size_t globalColorMapColors = 2 << (currentComponent[4] & 0x07);
 
             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;
             }
 
             GETN(1, GIFImageStart);
             break;
         }
 
         case GIFGlobalColormap: {
             m_globalColorMap.setDefined();
             GETN(1, GIFImageStart);
@@ skipping 217 matching lines @@
             // frame can be progressively displayed.
             // FIXME: It is possible that a non-transparent frame
             // can be interlaced and progressively displayed.
             currentFrame->setProgressiveDisplay(currentFrameIsFirstFrame());
 
             const bool isLocalColormapDefined = currentComponent[8] & 0x80;
             if (isLocalColormapDefined) {
                 // 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;
             }
 
             GETN(1, GIFLZWStart);
             break;
         }
 
         case GIFImageColormap: {
             ASSERT(!m_frames.isEmpty());
             m_frames.last()->localColorMap().setDefined();
@@ skipping 43 matching lines @@
     if (m_frames.isEmpty() || m_frames.last()->isComplete())
         m_frames.append(adoptPtr(new GIFFrameContext(m_frames.size())));
 }
 
 // FIXME: Move this method to close to doLZW().
 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;
     codemask = (1 << codesize) - 1;
     datum = bits = 0;
     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.

[Peter Kasting, 2013/08/31 00:08:49]

I think this comment and the memset can just be nuked.  Assuming you follow my
bugfix comment above, I don't think we ever read from the unset portion of the
suffix table even in the case of bad data.

[Alpha Left Google, 2013/09/01 01:40:21]

Thinking about this a bit more since we're now more strict about the code and
have established that a new code always references a defined and smaller code it
is not necessary to clear the entire suffixLength as well.

Clearing prefix is also not necessary. 

-    memset(suffix, 0, sizeof(suffix));
+    for (int i = 0; i < clearCode; ++i)
+        suffix[i] = i;
+    memset(suffix + clearCode, 0, sizeof(suffix) - clearCode);
+
+    for (int i = 0; i < MAX_DICTIONARY_ENTRIES; 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;
 }