GIF Animations "clear from cache related glitch" fix

third_party/WebKit/Source/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 209 matching lines @@
 
 size_t GIFImageDecoder::clearCacheExceptFrame(size_t clearExceptFrame)
 {
     // We need to preserve frames such that:
     //  1. We don't clear |clearExceptFrame|;
     //  2. We don't clear any frame from which a future initFrameBuffer() call
     //     will copy bitmap data.
     // All other frames can be cleared.
     while ((clearExceptFrame < m_frameBufferCache.size()) && (m_frameBufferCache[clearExceptFrame].status() == ImageFrame::FrameEmpty))
         clearExceptFrame = m_frameBufferCache[clearExceptFrame].requiredPreviousFrameIndex();
+    if ((clearExceptFrame < m_frameBufferCache.size()) && (m_frameBufferCache.size() > 1)
+        && (m_frameBufferCache[clearExceptFrame].disposalMethod() == ImageFrame::DisposeOverwritePrevious))
+        return clearCacheExceptTwoFrames(clearExceptFrame, m_frameBufferCache[clearExceptFrame].requiredPreviousFrameIndex());

[Peter Kasting, 2016/01/14 00:17:29]

I don't think this is as correct as the algorithm I proposed.

Let's say we have a GIF with four frames:

0: Nonempty, DisposeNotSpecified
1: Empty, DisposeNotSpecified
2: Nonempty, DisposeOverwritePrevious
3: Empty, DisposeNotSpecified

Now we call this method with clearExceptFrame == 2.

With your code, the while loop terminates immediately because frame 2 is
nonempty.  The conditional then fires, and we calculate frame 2's required
previous frame as frame 1.  So we end up asking to save frames 1 and 2.  Frame 0
is cleared (as is frame 3, which doesn't have any effect).

With my code, the initial conditional fires and we set frame2 = 2.  Then we set
clearExceptFrame = 1 and run the while loop.  This traverses back to frame 0,
and we end up asking to save frames 0 and 2.  Frames 1 and 3 are cleared, which
have no effect.

Now the decoder attempts to decode frame 3.  Frame 3's required previous frame
is frame 1, which is empty, so we have to look at its required previous frame,
which is frame 0.

In my code, frame 0 has been preserved, so all we need do is decode frame 1, and
we're ready to decode frame 3.  In your code, we need to decode frame 0, then
frame 1, then frame 3.

The key here is that we want to do the "traverse past empty frames" after the
DisposeOverwritePrevious check, not before.

[aleksandar.stojiljkovic, 2016/01/14 11:32:53]

I should have explained for not doing as you suggested.
Let's follow your example. Dependencies:
0<-1<-2
1<-3
The case above cannot happen with current ImageFrameGenerator::decode - it is
always calling clear all except currently decoded frames.
Fair enough, need to cover potential future changes for the sake of algorithm
correctness.
However, the case that needs to be handled is:

0: Empty, DisposeNotSpecified
1: Nonempty, DisposeNotSpecified
2: Nonempty, DisposeOverwritePrevious
3: Empty, DisposeNotSpecified

and then call to clearexceptframe == 3.
This could happen with partial decoding (when all data is not yet received) -
that is why existing code was traversing from current frame back to first
available nonempty (in this case 2) and keeping it.

The change I proposed was handling this case.
To handle the case you specified, I have now introduced another loop after
reaching 2 - for DisposeOverwritePrevious, find the closest previous required
frame that is not empty (0 in your example). 

[Peter Kasting, 2016/01/14 22:58:39]

I think you're mistaken about how both the existing code and my proposal handle
this.

In the case you describe, the requiredPreviousFrameIndex() for frame 3 will be
frame 1 -- not frame 2.  The existing code (without either of our changes)
already handles this case correctly: the initial loop sees that frame 3 is
empty, traverses directly to frame 1, sees that that is nonempty, and clears
everything but that.  The key here is that the loop goes back using
requiredPreviousFrameIndex() rather than just by subtracting one from
|clearExceptFrame|.

The case that needs to be handled better is the case where we're asked to
preserve frame _2_ in the example you give above, where the existing code will
preserve only frame 2, but we need to preserve both 1 and 2.  Both my proposal
and yours achieve this goal, but mine is simpler.

(To think about this another way, note that in the newest code you propose,
either the while loop must terminate immediately, or the following conditional
can never succeed, because no frame marked DisposeOverwritePrevious can ever be
the requiredPreviousFrameIndex() of a subsequent frame; see 
ImageDecoder::findRequiredPreviousFrame().)

+    return ImageDecoder::clearCacheExceptFrame(clearExceptFrame);
+}
 
-    return ImageDecoder::clearCacheExceptFrame(clearExceptFrame);
+
+size_t GIFImageDecoder::clearCacheExceptTwoFrames(size_t dontClearFrame1, size_t dontClearFrame2)
+{
+    size_t frameBytesCleared = 0;
+    for (size_t i = 0; i < m_frameBufferCache.size(); ++i) {
+        if (m_frameBufferCache[i].status() != ImageFrame::FrameEmpty && i != dontClearFrame1 && i != dontClearFrame2) {
+            frameBytesCleared += frameBytesAtIndex(i);
+            clearFrameBuffer(i);
+        }
+    }
+    return frameBytesCleared;
 }
 
 void GIFImageDecoder::clearFrameBuffer(size_t frameIndex)
 {
     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);
@@ skipping 93 matching lines @@
 
     // 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 blink