Decode GIF image frames on demand.

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

 /*
  * Copyright (C) 2006 Apple Computer, Inc.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 11 matching lines @@
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
 #include "config.h"
 #include "core/platform/image-decoders/gif/GIFImageDecoder.h"
 
 #include <limits>
 #include "core/platform/PlatformInstrumentation.h"
 #include "core/platform/image-decoders/gif/GIFImageReader.h"
-#include <wtf/PassOwnPtr.h>
+#include "wtf/NotFound.h"
+#include "wtf/PassOwnPtr.h"
 
 namespace WebCore {
 
 GIFImageDecoder::GIFImageDecoder(ImageSource::AlphaOption alphaOption,
                                  ImageSource::GammaAndColorProfileOption gammaAndColorProfileOption)
     : ImageDecoder(alphaOption, gammaAndColorProfileOption)
     , m_repetitionCount(cAnimationLoopOnce)
 {
 }
 
 GIFImageDecoder::~GIFImageDecoder()
 {
 }
 
 void GIFImageDecoder::setData(SharedBuffer* data, bool allDataReceived)
 {
     if (failed())
         return;
 
     ImageDecoder::setData(data, allDataReceived);
     if (m_reader)
         m_reader->setData(data);
 }
 
 bool GIFImageDecoder::isSizeAvailable()
 {
     if (!ImageDecoder::isSizeAvailable())
-         decode(0, GIFSizeQuery);
+        parse(GIFSizeQuery);
 
     return ImageDecoder::isSizeAvailable();
 }
 
 bool GIFImageDecoder::setSize(unsigned width, unsigned height)
 {
     if (ImageDecoder::isSizeAvailable() && size() == IntSize(width, height))
         return true;
 
     if (!ImageDecoder::setSize(width, height))
         return false;
 
     prepareScaleDataIfNecessary();
     return true;
 }
 
 size_t GIFImageDecoder::frameCount()
 {
-    decode(std::numeric_limits<unsigned>::max(), GIFFrameCountQuery);
+    parse(GIFFrameCountQuery);
     return m_frameBufferCache.size();
 }
 
 int GIFImageDecoder::repetitionCount() const
 {
     // This value can arrive at any point in the image data stream.  Most GIFs
     // in the wild declare it near the beginning of the file, so it usually is
     // set by the time we've decoded the size, but (depending on the GIF and the
     // packets sent back by the webserver) not always.  If the reader hasn't
     // seen a loop count yet, it will return cLoopCountNotSeen, in which case we
@@ skipping 24 matching lines @@
 }
 
 ImageFrame* GIFImageDecoder::frameBufferAtIndex(size_t index)
 {
     if (index >= frameCount())
         return 0;
 
     ImageFrame& frame = m_frameBufferCache[index];
     if (frame.status() != ImageFrame::FrameComplete) {
         PlatformInstrumentation::willDecodeImage("GIF");
-        decode(index + 1, GIFFullQuery);
+        decode(index);
         PlatformInstrumentation::didDecodeImage();
     }
     return &frame;
 }
 
 bool GIFImageDecoder::frameIsCompleteAtIndex(size_t index) const
 {
     return m_reader && (index < m_reader->imagesCount()) && m_reader->frameContext(index)->isComplete();
 }
 
 float GIFImageDecoder::frameDurationAtIndex(size_t index) const
 {
     return (m_reader && (index < m_reader->imagesCount()) &&
         m_reader->frameContext(index)->isHeaderDefined()) ?
         m_reader->frameContext(index)->delayTime : 0;
 }
 
 bool GIFImageDecoder::setFailed()
 {
     m_reader.clear();
     return ImageDecoder::setFailed();
 }
 
-void GIFImageDecoder::clearFrameBufferCache(size_t clearBeforeFrame)
-{
-    // In some cases, like if the decoder was destroyed while animating, we
-    // can be asked to clear more frames than we currently have.
-    if (m_frameBufferCache.isEmpty())
-        return; // Nothing to do.
-
-    // The "-1" here is tricky.  It does not mean that |clearBeforeFrame| is the
-    // last frame we wish to preserve, but rather that we never want to clear
-    // the very last frame in the cache: it's empty (so clearing it is
-    // pointless), it's partial (so we don't want to clear it anyway), or the
-    // cache could be enlarged with a future setData() call and it could be
-    // needed to construct the next frame (see comments below).  Callers can
-    // always use ImageSource::clear(true, ...) to completely free the memory in
-    // this case.
-    clearBeforeFrame = std::min(clearBeforeFrame, m_frameBufferCache.size() - 1);
-    const Vector<ImageFrame>::iterator end(m_frameBufferCache.begin() + clearBeforeFrame);
-
-    // We need to preserve frames such that:
-    //   * We don't clear |end|
-    //   * We don't clear the frame we're currently decoding
-    //   * We don't clear any frame from which a future initFrameBuffer() call
-    //     will copy bitmap data
-    // All other frames can be cleared.  Because of the constraints on when
-    // ImageSource::clear() can be called (see ImageSource.h), we're guaranteed
-    // not to have non-empty frames after the frame we're currently decoding.
-    // So, scan backwards from |end| as follows:
-    //   * If the frame is empty, we're still past any frames we care about.
-    //   * If the frame is complete, but is DisposeOverwritePrevious, we'll
-    //     skip over it in future initFrameBuffer() calls.  We can clear it
-    //     unless it's |end|, and keep scanning.  For any other disposal method,
-    //     stop scanning, as we've found the frame initFrameBuffer() will need
-    //     next.
-    //   * If the frame is partial, we're decoding it, so don't clear it; if it
-    //     has a disposal method other than DisposeOverwritePrevious, stop
-    //     scanning, as we'll only need this frame when decoding the next one.
-    Vector<ImageFrame>::iterator i(end);
-    for (; (i != m_frameBufferCache.begin()) && ((i->status() == ImageFrame::FrameEmpty) || (i->disposalMethod() == ImageFrame::DisposeOverwritePrevious)); --i) {
-        if ((i->status() == ImageFrame::FrameComplete) && (i != end))
-            i->clearPixelData();
-    }
-
-    // Now |i| holds the last frame we need to preserve; clear prior frames.
-    for (Vector<ImageFrame>::iterator j(m_frameBufferCache.begin()); j != i; ++j) {
-        ASSERT(j->status() != ImageFrame::FramePartial);
-        if (j->status() != ImageFrame::FrameEmpty)
-            j->clearPixelData();
-    }
-}
-
-bool GIFImageDecoder::haveDecodedRow(unsigned frameIndex, const Vector<unsigned char>& rowBuffer, size_t width, size_t rowNumber, unsigned repeatCount, bool writeTransparentPixels)
+bool GIFImageDecoder::haveDecodedRow(size_t frameIndex, const Vector<unsigned char>& rowBuffer, size_t width, size_t rowNumber, unsigned repeatCount, bool writeTransparentPixels)
 {
     const GIFFrameContext* frameContext = m_reader->frameContext(frameIndex);
     // The pixel data and coordinates supplied to us are relative to the frame's
     // origin within the entire image size, i.e.
     // (frameContext->xOffset, frameContext->yOffset). There is no guarantee
     // that width == (size().width() - frameContext->xOffset), so
     // we must ensure we don't run off the end of either the source data or the
     // row's X-coordinates.
     int xBegin = upperBoundScaledX(frameContext->xOffset);
     int yBegin = upperBoundScaledY(frameContext->yOffset + rowNumber);
@@ skipping 42 matching lines @@
         ++currentAddress;
     }
 
     // Tell the frame to copy the row data if need be.
     if (repeatCount > 1)
         buffer.copyRowNTimes(xBegin, xEnd, yBegin, yEnd);
 
     return true;
 }
 
-bool GIFImageDecoder::frameComplete(unsigned frameIndex, unsigned frameDuration, ImageFrame::FrameDisposalMethod disposalMethod)
+bool GIFImageDecoder::frameComplete(size_t frameIndex)
 {
     // Initialize the frame if necessary.  Some GIFs insert do-nothing frames,
     // in which case we never reach haveDecodedRow() before getting here.
     ImageFrame& buffer = m_frameBufferCache[frameIndex];
     if ((buffer.status() == ImageFrame::FrameEmpty) && !initFrameBuffer(frameIndex))
         return false; // initFrameBuffer() has already called setFailed().
 
     buffer.setStatus(ImageFrame::FrameComplete);
-    buffer.setDuration(frameDuration);
-    buffer.setDisposalMethod(disposalMethod);
 
     if (!m_currentBufferSawAlpha) {
         // The whole frame was non-transparent, so it's possible that the entire
         // resulting buffer was non-transparent, and we can setHasAlpha(false).
-        if (buffer.originalFrameRect().contains(IntRect(IntPoint(), scaledSize())))
+        if (buffer.originalFrameRect().contains(IntRect(IntPoint(), scaledSize()))) {
             buffer.setHasAlpha(false);
-        else if (frameIndex) {
+            buffer.setRequiredPreviousFrameIndex(notFound);

[Alpha Left Google, 2013/05/22 20:18:09]

Knowing this frame doesn't depend on any previous frame we should update the
dependency of subsequent frames.

[Xianzhu, 2013/05/22 23:43:29]

That seems unnecessary. Whether this frame resets starting state of itself
should not affect the starting state assumptions of subsequent frames which were
based on the disposal methods and geometry of their previous frames.

To be more specific, a subsequent frame's requiredPreviousFrameIndexd may have
the following values:
1. notFound or >frameIndex: the subsequent frame is independent to this frame;
2. <frameIndex: the frameIndex frame must be DisposeOverwritePrevious so its
contents don't affect subsequent frames' dependencies)
4. ==frameIndex: the subsequent frame should still depend on this frame.

For all the cases, the dependency seems not to need updating.

+        } else if (buffer.requiredPreviousFrameIndex() != notFound) {
             // Tricky case.  This frame does not have alpha only if everywhere
             // outside its rect doesn't have alpha.  To know whether this is
             // true, we check the start state of the frame -- if it doesn't have
             // alpha, we're safe.
-            //
-            // First skip over prior DisposeOverwritePrevious frames (since they
-            // don't affect the start state of this frame) the same way we do in
-            // initFrameBuffer().
-            const ImageFrame* prevBuffer = &m_frameBufferCache[--frameIndex];
-            while (frameIndex && (prevBuffer->disposalMethod() == ImageFrame::DisposeOverwritePrevious))
-                prevBuffer = &m_frameBufferCache[--frameIndex];
+            const ImageFrame* prevBuffer = &m_frameBufferCache[buffer.requiredPreviousFrameIndex()];
+            ASSERT(prevBuffer->disposalMethod() != ImageFrame::DisposeOverwritePrevious);
 
             // Now, if we're at a DisposeNotSpecified or DisposeKeep frame, then
             // we can say we have no alpha if that frame had no alpha.  But
             // since in initFrameBuffer() we already copied that frame's alpha
             // state into the current frame's, we need do nothing at all here.
             //
             // The only remaining case is a DisposeOverwriteBgcolor frame.  If
             // it had no alpha, and its rect is contained in the current frame's
             // rect, we know the current frame has no alpha.
             if ((prevBuffer->disposalMethod() == ImageFrame::DisposeOverwriteBgcolor) && !prevBuffer->hasAlpha() && buffer.originalFrameRect().contains(prevBuffer->originalFrameRect()))
                 buffer.setHasAlpha(false);
         }
     }
 
     return true;
 }
 
-void GIFImageDecoder::gifComplete()
-{
-    // Cache the repetition count, which is now as authoritative as it's ever
-    // going to be.
-    repetitionCount();
-}
-
-void GIFImageDecoder::decode(unsigned haltAtFrame, GIFQuery query)
+void GIFImageDecoder::parse(GIFParseQuery query)
 {
     if (failed())
         return;
 
     if (!m_reader) {
         m_reader = adoptPtr(new GIFImageReader(this));
         m_reader->setData(m_data);
     }
 
-    if (query == GIFSizeQuery) {
-        if (!m_reader->decode(GIFSizeQuery, haltAtFrame))
-            setFailed();
-        return;
-    }
-
-    if (!m_reader->decode(GIFFrameCountQuery, haltAtFrame)) {
+    if (!m_reader->parse(query)) {
         setFailed();
         return;
     }
 
     const size_t oldSize = m_frameBufferCache.size();
     m_frameBufferCache.resize(m_reader->imagesCount());
-    for (size_t i = oldSize; i < m_reader->imagesCount(); ++i)
-        m_frameBufferCache[i].setPremultiplyAlpha(m_premultiplyAlpha);
 
-    if (query == GIFFrameCountQuery)
+    // The old last frame buffer may have not been completely parsed last time.
+    if (oldSize) {
+        ImageFrame& buffer = m_frameBufferCache[oldSize - 1];
+        const GIFFrameContext* frameContext = m_reader->frameContext(oldSize - 1);
+        buffer.setDuration(frameContext->delayTime);
+        buffer.setDisposalMethod(frameContext->disposalMethod);
+    }
+
+    for (size_t i = oldSize; i < m_reader->imagesCount(); ++i) {
+        ImageFrame& buffer = m_frameBufferCache[i];
+        const GIFFrameContext* frameContext = m_reader->frameContext(i);
+        buffer.setPremultiplyAlpha(m_premultiplyAlpha);
+        buffer.setRequiredPreviousFrameIndex(findRequiredPreviousFrame(i));
+        // For the last parsed frame, the following information may be incomplete
+        // at this time. Will be refreshed later.
+        buffer.setDuration(frameContext->delayTime);

[Alpha Left Google, 2013/05/22 20:18:09]

This information should always be there for each new frame. Because we increment
the image count only when a control extension or image block is scanned. Control
extensions contains duration and disposal method and appears before the image
block in the stream.

[Xianzhu, 2013/05/22 23:43:29]

Done.

+        buffer.setDisposalMethod(frameContext->disposalMethod);
+    }
+}
+
+void GIFImageDecoder::decode(size_t frameIndex)
+{
+    parse(GIFFrameCountQuery);
+
+    if (failed())
         return;
 
-    if (!m_reader->decode(GIFFullQuery, haltAtFrame)) {
-        setFailed();
-        return;
+    Vector<size_t> framesToDecode;
+    size_t frameToDecode = frameIndex;
+    do {
+        framesToDecode.append(frameToDecode);
+        frameToDecode = m_frameBufferCache[frameToDecode].requiredPreviousFrameIndex();
+    } while (frameToDecode != notFound && m_frameBufferCache[frameToDecode].status() != ImageFrame::FrameComplete);
+
+    for (size_t i = framesToDecode.size(); i; --i) {
+        if (!m_reader->decode(framesToDecode[i - 1])) {
+            setFailed();
+            return;
+        }

[Xianzhu, 2013/05/22 23:43:29]

Just noticed I missed the case of not enough data.
Added bool* frameDecoded parameter to GIFImageReader::decode() to check it here.

     }
 
     // It is also a fatal error if all data is received and we have decoded all
     // frames available but the file is truncated.
-    if (haltAtFrame >= m_frameBufferCache.size() && isAllDataReceived() && m_reader && !m_reader->parseCompleted())
+    if (frameIndex >= m_frameBufferCache.size() - 1 && isAllDataReceived() && m_reader && !m_reader->parseCompleted())
         setFailed();
 }
 
-bool GIFImageDecoder::initFrameBuffer(unsigned frameIndex)
+bool GIFImageDecoder::initFrameBuffer(size_t frameIndex)
 {
     // Initialize the frame rect in our buffer.
     const GIFFrameContext* frameContext = m_reader->frameContext(frameIndex);
     IntRect frameRect(frameContext->xOffset, frameContext->yOffset, frameContext->width, frameContext->height);
 
     // Make sure the frameRect doesn't extend outside the buffer.
     if (frameRect.maxX() > size().width())
         frameRect.setWidth(size().width() - frameContext->xOffset);
     if (frameRect.maxY() > size().height())
         frameRect.setHeight(size().height() - frameContext->yOffset);
 
     ImageFrame* const buffer = &m_frameBufferCache[frameIndex];
     int left = upperBoundScaledX(frameRect.x());
     int right = lowerBoundScaledX(frameRect.maxX(), left);
     int top = upperBoundScaledY(frameRect.y());
     int bottom = lowerBoundScaledY(frameRect.maxY(), top);
     buffer->setOriginalFrameRect(IntRect(left, top, right - left, bottom - top));
-    
-    if (!frameIndex) {
-        // This is the first frame, so we're not relying on any previous data.
+
+    size_t requiredPreviousFrameIndex = m_frameBufferCache[frameIndex].requiredPreviousFrameIndex();
+    if (requiredPreviousFrameIndex == notFound) {
+        // This frame doesn't rely on any previous data.
         if (!buffer->setSize(scaledSize().width(), scaledSize().height()))
             return setFailed();
     } else {
-        // The starting state for this frame depends on the previous frame's
-        // disposal method.
-        //
-        // Frames that use the DisposeOverwritePrevious method are effectively
-        // no-ops in terms of changing the starting state of a frame compared to
-        // the starting state of the previous frame, so skip over them.  (If the
-        // first frame specifies this method, it will get treated like
-        // DisposeOverwriteBgcolor below and reset to a completely empty image.)
-        const ImageFrame* prevBuffer = &m_frameBufferCache[--frameIndex];
-        ImageFrame::FrameDisposalMethod prevMethod = prevBuffer->disposalMethod();
-        while (frameIndex && (prevMethod == ImageFrame::DisposeOverwritePrevious)) {
-            prevBuffer = &m_frameBufferCache[--frameIndex];
-            prevMethod = prevBuffer->disposalMethod();
-        }
+        const ImageFrame* prevBuffer = &m_frameBufferCache[requiredPreviousFrameIndex];
         ASSERT(prevBuffer->status() == ImageFrame::FrameComplete);
 
-        if ((prevMethod == ImageFrame::DisposeNotSpecified) || (prevMethod == ImageFrame::DisposeKeep)) {
-            // Preserve the last frame as the starting state for this frame.
-            if (!buffer->copyBitmapData(*prevBuffer))
-                return setFailed();
-        } else {
+        // Preserve the last frame as the starting state for this frame.
+        if (!buffer->copyBitmapData(*prevBuffer))
+            return setFailed();
+
+        if (prevBuffer->disposalMethod() == ImageFrame::DisposeOverwriteBgcolor) {
             // We want to clear the previous frame to transparent, without
             // affecting pixels in the image outside of the frame.
             const IntRect& prevRect = prevBuffer->originalFrameRect();
-            const IntSize& bufferSize = scaledSize();
-            if (!frameIndex || prevRect.contains(IntRect(IntPoint(), scaledSize()))) {
-                // Clearing the first frame, or a frame the size of the whole
-                // image, results in a completely empty image.
-                if (!buffer->setSize(bufferSize.width(), bufferSize.height()))
-                    return setFailed();
-            } else {
-              // Copy the whole previous buffer, then clear just its frame.
-              if (!buffer->copyBitmapData(*prevBuffer))
-                  return setFailed();
-              for (int y = prevRect.y(); y < prevRect.maxY(); ++y) {
-                  for (int x = prevRect.x(); x < prevRect.maxX(); ++x)
-                      buffer->setRGBA(x, y, 0, 0, 0, 0);
-              }
-              if ((prevRect.width() > 0) && (prevRect.height() > 0))
-                  buffer->setHasAlpha(true);
+            for (int y = prevRect.y(); y < prevRect.maxY(); ++y) {
+                for (int x = prevRect.x(); x < prevRect.maxX(); ++x)
+                    buffer->setRGBA(x, y, 0, 0, 0, 0);
             }
+            if ((prevRect.width() > 0) && (prevRect.height() > 0))
+                buffer->setHasAlpha(true);
         }
     }
 
     // Update our status to be partially complete.
     buffer->setStatus(ImageFrame::FramePartial);
 
     // Reset the alpha pixel tracker for this frame.
     m_currentBufferSawAlpha = false;
     return true;
 }
 
 } // namespace WebCore