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();
 }
 
 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 = frameContext->xOffset;
     int yBegin = 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::parseCompleted() const
+{
+    return m_reader && m_reader->parseCompleted();
+}
+
+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(), size())))
+        if (buffer.originalFrameRect().contains(IntRect(IntPoint(), size()))) {
             buffer.setHasAlpha(false);
-        else if (frameIndex) {
+            buffer.setRequiredPreviousFrameIndex(notFound);
+        } 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()
+void GIFImageDecoder::clearFrameBuffer(size_t frameIndex)
 {
-    // Cache the repetition count, which is now as authoritative as it's ever
-    // going to be.
-    repetitionCount();
+    if (m_reader && m_frameBufferCache[frameIndex].status() == ImageFrame::FramePartial) {
+        // Reset the state of the partial frame in the reader so that the frame
+        // can be decoded again when requested.
+        m_reader->clearDecodeState(frameIndex);
+    }
+    ImageDecoder::clearFrameBuffer(frameIndex);
 }
 
-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)
+    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));
+        buffer.setDuration(frameContext->delayTime);
+        buffer.setDisposalMethod(frameContext->disposalMethod);
+
+        // Initialize the frame rect in our buffer.
+        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);
+
+        buffer.setOriginalFrameRect(frameRect);
+    }
+}
+
+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 (Vector<size_t>::const_reverse_iterator iter = framesToDecode.rbegin(); iter != framesToDecode.rend(); ++iter) {
+        size_t frameIndex = *iter;
+        if (!m_reader->decode(frameIndex)) {
+            setFailed();
+            return;
+        }
+
+        // We need more data to continue decoding.
+        if (m_frameBufferCache[frameIndex].status() != ImageFrame::FrameComplete)
+            break;
     }
 
     // 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];
-    buffer->setOriginalFrameRect(frameRect);
     
-    if (!frameIndex) {
-        // This is the first frame, so we're not relying on any previous data.
+    size_t requiredPreviousFrameIndex = buffer->requiredPreviousFrameIndex();
+    if (requiredPreviousFrameIndex == notFound) {
+        // This frame doesn't rely on any previous data.
         if (!buffer->setSize(size().width(), size().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 = size();
-            if (!frameIndex || prevRect.contains(IntRect(IntPoint(), size()))) {
-                // 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);
+            ASSERT(!prevRect.contains(IntRect(IntPoint(), size())));
+            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