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;

[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;
         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;
             datum >>= codesize;
@@ skipping 10 matching lines @@
 
             // 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) {
+                // 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;
 
-                firstchar = oldcode = code;
-                continue;
+                    // 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;
+                }
+
+                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;
+
+                    // 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];
+                }
+
+                *--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;
             }
 
-            incode = code;
-            if (code >= avail) {
-                stack[stackp++] = firstchar;
-                code = oldcode;
+            // 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;
             }
 
-            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;
-            }
-
-            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;
 }
 
 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);
     const unsigned char* srcColormap = data + m_position;
@@ skipping 431 matching lines @@
         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.

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

Nit: Remove last sentence, and remove "(12)" from previous sentence.

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

Done.

     if (m_frameContext->dataSize() >= MAX_LZW_BITS)
         return false;
     clearCode = 1 << m_frameContext->dataSize();
     if (clearCode >= MAX_BYTES)

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

This conditional cannot fail given the previous conditional; remove it.

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

Done.

         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());
+    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;
 }