Decode GIF image frames on demand.

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

Index: Source/core/platform/image-decoders/gif/GIFImageDecoder.cpp
diff --git a/Source/core/platform/image-decoders/gif/GIFImageDecoder.cpp b/Source/core/platform/image-decoders/gif/GIFImageDecoder.cpp
index d785aec0341c6f5f782e4ffe3b97e4b74b001224..e1da525fdc0550e987c48b1e9ebc68df3e389660 100644
--- a/Source/core/platform/image-decoders/gif/GIFImageDecoder.cpp
+++ b/Source/core/platform/image-decoders/gif/GIFImageDecoder.cpp
@@ -57,7 +57,7 @@ void GIFImageDecoder::setData(SharedBuffer* data, bool allDataReceived)
 bool GIFImageDecoder::isSizeAvailable()
 {
     if (!ImageDecoder::isSizeAvailable())
-         decode(0, GIFSizeQuery);
+        parse(GIFSizeQuery);
 
     return ImageDecoder::isSizeAvailable();
 }
@@ -76,7 +76,7 @@ bool GIFImageDecoder::setSize(unsigned width, unsigned height)
 
 size_t GIFImageDecoder::frameCount()
 {
-    decode(std::numeric_limits<unsigned>::max(), GIFFrameCountQuery);
+    parse(GIFFrameCountQuery);
     return m_frameBufferCache.size();
 }
 
@@ -121,7 +121,7 @@ ImageFrame* GIFImageDecoder::frameBufferAtIndex(size_t index)
     ImageFrame& frame = m_frameBufferCache[index];
     if (frame.status() != ImageFrame::FrameComplete) {
         PlatformInstrumentation::willDecodeImage("GIF");
-        decode(index + 1, GIFFullQuery);
+        decode(index);
         PlatformInstrumentation::didDecodeImage();
     }
     return &frame;
@@ -195,7 +195,7 @@ void GIFImageDecoder::clearFrameBufferCache(size_t clearBeforeFrame)
     }
 }
 
-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
@@ -258,7 +258,7 @@ bool GIFImageDecoder::haveDecodedRow(unsigned frameIndex, const Vector<unsigned
     return true;
 }
 
-bool GIFImageDecoder::frameComplete(unsigned frameIndex, unsigned frameDuration, ImageFrame::FrameDisposalMethod disposalMethod)
+bool GIFImageDecoder::frameComplete(size_t frameIndex, unsigned frameDuration, ImageFrame::FrameDisposalMethod disposalMethod)
 {
     // Initialize the frame if necessary.  Some GIFs insert do-nothing frames,
     // in which case we never reach haveDecodedRow() before getting here.
@@ -311,7 +311,7 @@ void GIFImageDecoder::gifComplete()
     repetitionCount();
 }
 
-void GIFImageDecoder::decode(unsigned haltAtFrame, GIFQuery query)
+void GIFImageDecoder::parse(GIFParseQuery query)
 {
     if (failed())
         return;
@@ -321,13 +321,7 @@ void GIFImageDecoder::decode(unsigned haltAtFrame, GIFQuery query)
         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;
     }
@@ -336,22 +330,82 @@ void GIFImageDecoder::decode(unsigned haltAtFrame, GIFQuery query)
     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)
+void GIFImageDecoder::decode(size_t frameIndex)
+{
+    parse(GIFFrameCountQuery);
+
+    if (failed())
         return;
 
-    if (!m_reader->decode(GIFFullQuery, haltAtFrame)) {
+    BitVector frames(frameIndex);

[Alpha Left Google, 2013/05/18 00:39:35]

Instead of a BitVector what about a vector of frame indices? This way you can
call m_reader->decode(...) with those indices in order.

[Xianzhu, 2013/05/20 04:30:59]

Done.

+    getFramesToDecode(frameIndex, &frames);
+
+    if (!m_reader->decode(frames)) {

[Alpha Left Google, 2013/05/18 00:39:35]

I'd prefer to call m_reader->decode(...) multiple times to decode all the
necessary frames.

[Xianzhu, 2013/05/20 04:30:59]

Done.

         setFailed();
         return;
     }
 
     // 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();

[Alpha Left Google, 2013/05/18 00:39:35]

The reason for calling setFailed() here is to stop animation such that for
truncated GIF files we only animate once.

I think this will look much simpler if we intead do a condition in
repetitionCount() that:
if (isAllDataReceived() && m_reader && !m_reader->parseCompleted())
  return cAnimationLoopOnce;
It's not necessary to do this change now though.

 }
 
-bool GIFImageDecoder::initFrameBuffer(unsigned frameIndex)
+void GIFImageDecoder::getFramesToDecode(size_t frameIndex, BitVector* frames)
+{
+    while (m_frameBufferCache[frameIndex].status() != ImageFrame::FrameComplete) {
+        frames->set(frameIndex);
+        frameIndex = getPreviousRequiredFrame(frameIndex);
+        if (frameIndex == notFound)
+            break;
+    }
+}
+
+size_t GIFImageDecoder::getPreviousRequiredFrame(size_t frameIndex)

[Alpha Left Google, 2013/05/18 00:39:35]

I see this method will be called multiple times for the same |frameIndex|. Can
you make an optimization here by caching the |previousRequiredFrame|? In fact
after each frame count query you can go over the new frames and compute each
|previousRequiredFrame| quickly.

The current algorithm is to scan backward for each frame and in the worst case
this is O(n^2).

[Xianzhu, 2013/05/20 04:30:59]

Done.

+{
+    if (!frameIndex) {
+        // The first frame doesn't rely on any previous data.
+        return notFound;
+    }
+
+    // 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.)
+    size_t prevFrame = frameIndex - 1;
+    const ImageFrame* prevBuffer = &m_frameBufferCache[prevFrame];
+    ImageFrame::FrameDisposalMethod prevMethod = prevBuffer->disposalMethod();
+    while (prevFrame && (prevMethod == ImageFrame::DisposeOverwritePrevious)) {
+        prevBuffer = &m_frameBufferCache[--prevFrame];
+        prevMethod = prevBuffer->disposalMethod();
+    }
+
+    if (prevMethod == ImageFrame::DisposeNotSpecified || prevMethod == ImageFrame::DisposeKeep) {
+        // prevFrame will be used as the starting state for this frame.
+        return prevFrame;
+    }
+
+    ASSERT(prevMethod == ImageFrame::DisposeOverwriteBgcolor);
+    const IntRect& prevRect = prevBuffer->originalFrameRect();
+    const IntSize& bufferSize = scaledSize();
+    if (!frameIndex || prevRect.contains(IntRect(IntPoint(), scaledSize()))) {
+        // The first frame or a frame covering the whole image will be cleared
+        // to background, so this frame doesn't rely on any previous data.
+        return notFound;
+    }
+
+    // prevFrame only clears part of the image to background, so it contributes
+    // to the starting state of this frame.
+    return prevFrame;
+}
+
+bool GIFImageDecoder::initFrameBuffer(size_t frameIndex)
 {
     // Initialize the frame rect in our buffer.
     const GIFFrameContext* frameContext = m_reader->frameContext(frameIndex);
@@ -369,53 +423,30 @@ bool GIFImageDecoder::initFrameBuffer(unsigned frameIndex)
     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 previousRequiredFrame = getPreviousRequiredFrame(frameIndex);
+    if (previousRequiredFrame == 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[previousRequiredFrame];
         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);
         }
     }