GIF: Better check for frame dependency

If a frame does not have a valid transparent index and it covers the
prior frame, it does not really depend on that frame. Instead, it
depends on the frame that the prior frame depends on.

Determine this once we have parsed the local color map (if any), so a
transparent index out of range of the color map is not considered
valid.

Share code that determines whether a frame has a transparent pixel.

Add a test that we compute the dependencies correctly. randPixelsAnim.gif
has 13 frames. After the first, the frames cover all combinations of

- Whether the prior frame was keep, restoreBG or restoreToPrevious
- Whether the new frame covers the prior frame
- Whether the new frame has a transparent pixel

(It only does so when using a global color table. It may make sense to
expand the test to also cover using local color tables.)

The test caught a bug where we incorrectly reused an existing
SkColorTable for a different frame. Fix that bug by keeping track of
the transparent index associated with the current SkColorTable.

Change-Id: I3cf6be7f612990fa7a00d9e74d116d31bd227526
Reviewed-on: https://skia-review.googlesource.com/6402
Reviewed-by: Matt Sarett <msarett@google.com>
Commit-Queue: Leon Scroggins <scroggo@google.com>

2 files changed, 105 insertions, 69 deletions

diff --git a/third_party/gif/SkGifImageReader.cpp b/third_party/gif/SkGifImageReader.cpp
index ae5663f651..2603807cb3 100644
--- a/third_party/gif/SkGifImageReader.cpp
+++ b/third_party/gif/SkGifImageReader.cpp
@@ -312,17 +312,15 @@ sk_sp<SkColorTable> SkGIFColorMap::buildTable(SkStreamBuffer* streamBuffer, SkCo
         return nullptr;
 
     const PackColorProc proc = choose_pack_color_proc(false, colorType);
-    if (m_table) {
-        if (transparentPixel > (unsigned) m_table->count()
-                || m_table->operator[](transparentPixel) == SK_ColorTRANSPARENT) {
-            if (proc == m_packColorProc) {
-                // This SkColorTable has already been built with the same transparent color and
-                // packing proc. Reuse it.
-                return m_table;
-            }
-        }
+    if (m_table && proc == m_packColorProc && m_transPixel == transparentPixel) {
+        SkASSERT(transparentPixel > (unsigned) m_table->count()
+                || m_table->operator[](transparentPixel) == SK_ColorTRANSPARENT);
+        // This SkColorTable has already been built with the same transparent color and
+        // packing proc. Reuse it.
+        return m_table;
     }
     m_packColorProc = proc;
+    m_transPixel = transparentPixel;
 
     const size_t bytes = m_colors * SK_BYTES_PER_COLORMAP_ENTRY;
     sk_sp<SkData> rawData(streamBuffer->getDataAtPosition(m_position, bytes));
@@ -458,7 +456,10 @@ bool SkGifImageReader::parse(SkGifImageReader::SkGIFParseQuery query)
         }
         case SkGIFLZWStart: {
             SkASSERT(!m_frames.empty());
-            m_frames.back()->setDataSize(this->getOneByte());
+            auto* currentFrame = m_frames.back().get();
+            setRequiredFrame(currentFrame);
+
+            currentFrame->setDataSize(this->getOneByte());
             GETN(1, SkGIFSubBlock);
             break;
         }
@@ -755,33 +756,7 @@ bool SkGifImageReader::parse(SkGifImageReader::SkGIFParseQuery query)
             // The three low-order bits of currentComponent[8] specify the bits per pixel.
             const size_t numColors = 2 << (currentComponent[8] & 0x7);
             if (currentFrameIsFirstFrame()) {
-                bool hasTransparentPixel;
-                if (m_frames.size() == 0) {
-                    // We did not see a Graphics Control Extension, so no transparent
-                    // pixel was specified. But if there is no color table, this frame is
-                    // still transparent.
-                    hasTransparentPixel = !isLocalColormapDefined
-                                          && m_globalColorMap.numColors() == 0;
-                } else {
-                    // This means we did see a Graphics Control Extension, which specifies
-                    // the transparent pixel
-                    const size_t transparentPixel = m_frames[0]->transparentPixel();
-                    if (isLocalColormapDefined) {
-                        hasTransparentPixel = transparentPixel < numColors;
-                    } else {
-                        const size_t globalColors = m_globalColorMap.numColors();
-                        if (!globalColors) {
-                            // No color table for this frame, so the frame is empty.
-                            // This is technically different from having a transparent
-                            // pixel, but we'll treat it the same - nothing to draw here.
-                            hasTransparentPixel = true;
-                        } else {
-                            hasTransparentPixel = transparentPixel < globalColors;
-                        }
-                    }
-                }
-
-                if (hasTransparentPixel) {
+                if (hasTransparentPixel(0, isLocalColormapDefined, numColors)) {
                     m_firstFrameHasAlpha = true;
                     m_firstFrameSupportsIndex8 = true;
                 } else {
@@ -874,44 +849,97 @@ bool SkGifImageReader::parse(SkGifImageReader::SkGIFParseQuery query)
     return true;
 }
 
+bool SkGifImageReader::hasTransparentPixel(size_t i, bool isLocalColormapDefined,
+                                           size_t localColors) {
+    if (m_frames.size() <= i) {
+        // This should only happen when parsing the first frame.
+        SkASSERT(0 == i);
+
+        // We did not see a Graphics Control Extension, so no transparent
+        // pixel was specified. But if there is no color table, this frame is
+        // still transparent.
+        return !isLocalColormapDefined && m_globalColorMap.numColors() == 0;
+    }
+
+    const size_t transparentPixel = m_frames[i]->transparentPixel();
+    if (isLocalColormapDefined) {
+        return transparentPixel < localColors;
+    }
+
+    const size_t globalColors = m_globalColorMap.numColors();
+    if (!globalColors) {
+        // No color table for this frame, so the frame is empty.
+        // This is technically different from having a transparent
+        // pixel, but we'll treat it the same - nothing to draw here.
+        return true;
+    }
+
+    // If there is a global color table, it will be parsed before reaching
+    // here. If its numColors is set, it will be defined.
+    SkASSERT(m_globalColorMap.isDefined());
+    return transparentPixel < globalColors;
+}
+
 void SkGifImageReader::addFrameIfNecessary()
 {
     if (m_frames.empty() || m_frames.back()->isComplete()) {
         const size_t i = m_frames.size();
         std::unique_ptr<SkGIFFrameContext> frame(new SkGIFFrameContext(i));
-        if (0 == i) {
-            frame->setRequiredFrame(SkCodec::kNone);
-        } else {
-            // FIXME: We could correct these after decoding (i.e. some frames may turn out to be
-            // independent although we did not determine that here).
-            const SkGIFFrameContext* prevFrameContext = m_frames[i - 1].get();
-            switch (prevFrameContext->getDisposalMethod()) {
-                case SkCodecAnimation::Keep_DisposalMethod:
-                    frame->setRequiredFrame(i - 1);
-                    break;
-                case SkCodecAnimation::RestorePrevious_DisposalMethod:
-                    frame->setRequiredFrame(prevFrameContext->getRequiredFrame());
-                    break;
-                case SkCodecAnimation::RestoreBGColor_DisposalMethod:
-                    // If the prior frame covers the whole image
-                    if (prevFrameContext->frameRect() == SkIRect::MakeWH(m_screenWidth,
-                                                                         m_screenHeight)
-                            // Or the prior frame was independent
-                            || prevFrameContext->getRequiredFrame() == SkCodec::kNone)
-                    {
-                        // This frame is independent, since we clear everything
-                        // prior frame to the BG color
-                        frame->setRequiredFrame(SkCodec::kNone);
-                    } else {
-                        frame->setRequiredFrame(i - 1);
-                    }
-                    break;
-            }
-        }
         m_frames.push_back(std::move(frame));
     }
 }
 
+void SkGifImageReader::setRequiredFrame(SkGIFFrameContext* frame) {
+    const size_t i = frame->frameId();
+    if (0 == i) {
+        frame->setRequiredFrame(SkCodec::kNone);
+        return;
+    }
+
+    const SkGIFFrameContext* prevFrame = m_frames[i - 1].get();
+    if (prevFrame->getDisposalMethod() == SkCodecAnimation::RestorePrevious_DisposalMethod) {
+        frame->setRequiredFrame(prevFrame->getRequiredFrame());
+        return;
+    }
+
+    // Note: We could correct these after decoding - i.e. some frames may turn out to be
+    // independent if they do not use the transparent pixel, but that would require
+    // checking whether each pixel used the transparent pixel.
+    const SkGIFColorMap& localMap = frame->localColorMap();
+    const bool transValid = hasTransparentPixel(i, localMap.isDefined(), localMap.numColors());
+
+    const SkIRect prevFrameRect = prevFrame->frameRect();
+    const bool frameCoversPriorFrame = frame->frameRect().contains(prevFrameRect);
+
+    if (!transValid && frameCoversPriorFrame) {
+        frame->setRequiredFrame(prevFrame->getRequiredFrame());
+        return;
+    }
+
+    switch (prevFrame->getDisposalMethod()) {
+        case SkCodecAnimation::Keep_DisposalMethod:
+            frame->setRequiredFrame(i - 1);
+            break;
+        case SkCodecAnimation::RestorePrevious_DisposalMethod:
+            // This was already handled above.
+            SkASSERT(false);
+            break;
+        case SkCodecAnimation::RestoreBGColor_DisposalMethod:
+            // If the prior frame covers the whole image
+            if (prevFrameRect == SkIRect::MakeWH(m_screenWidth, m_screenHeight)
+                    // Or the prior frame was independent
+                    || prevFrame->getRequiredFrame() == SkCodec::kNone)
+            {
+                // This frame is independent, since we clear everything in the
+                // prior frame to the BG color
+                frame->setRequiredFrame(SkCodec::kNone);
+            } else {
+                frame->setRequiredFrame(i - 1);
+            }
+            break;
+    }
+}
+
 // FIXME: Move this method to close to doLZW().
 bool SkGIFLZWContext::prepareToDecode()
 {
diff --git a/third_party/gif/SkGifImageReader.h b/third_party/gif/SkGifImageReader.h
index ddfd2cef03..c51f4a8983 100644
--- a/third_party/gif/SkGifImageReader.h
+++ b/third_party/gif/SkGifImageReader.h
@@ -148,10 +148,13 @@ struct SkGIFLZWBlock {
 
 class SkGIFColorMap final {
 public:
+    static constexpr size_t kNotFound = static_cast<size_t>(-1);
+
     SkGIFColorMap()
         : m_isDefined(false)
         , m_position(0)
         , m_colors(0)
+        , m_transPixel(kNotFound)
         , m_packColorProc(nullptr)
     {
     }
@@ -182,6 +185,8 @@ private:
     bool m_isDefined;
     size_t m_position;
     size_t m_colors;
+    // Cached values. If these match on a new request, we can reuse m_table.
+    mutable size_t m_transPixel;
     mutable PackColorProc m_packColorProc;
     mutable sk_sp<SkColorTable> m_table;
 };
@@ -195,7 +200,7 @@ public:
         , m_yOffset(0)
         , m_width(0)
         , m_height(0)
-        , m_transparentPixel(kNotFound)
+        , m_transparentPixel(SkGIFColorMap::kNotFound)
         , m_disposalMethod(SkCodecAnimation::Keep_DisposalMethod)
         , m_requiredFrame(SkCodec::kNone)
         , m_dataSize(0)
@@ -209,8 +214,6 @@ public:
     {
     }
 
-    static constexpr size_t kNotFound = static_cast<size_t>(-1);
-
     ~SkGIFFrameContext()
     {
     }
@@ -388,6 +391,11 @@ private:
     }
 
     void addFrameIfNecessary();
+    // Must be called *after* the SkGIFFrameContext's color table (if any) has been parsed.
+    void setRequiredFrame(SkGIFFrameContext*);
+    // This method is sometimes called before creating a SkGIFFrameContext, so it cannot rely
+    // on SkGIFFrameContext::localColorMap().
+    bool hasTransparentPixel(size_t frameIndex, bool hasLocalColorMap, size_t localMapColors);
     bool currentFrameIsFirstFrame() const
     {
         return m_frames.empty() || (m_frames.size() == 1u && !m_frames[0]->isComplete());