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++) {
         // 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) {
-                *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;
+            oldcode = tempCode;
+            rowIter += codeLength;
 
-            // Copy the decoded data out to the scanline buffer.
-            do {
-                *rowIter++ = stack[--stackp];
-                if (rowIter == rowBuffer.end())
-                    OUTPUT_ROW;
-            } while (stackp > 0);
+            // 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;
 }
 
 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.
-    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;
 }