Correct GIF frame dependencies and track alpha

Add SkCodec::FrameInfo::fAlphaType. The SkImageInfo for the SkCodec
specifies the SkAlphaType for the first frame, but the opacity can vary
from frame to frame.

When determining the required frame, also compute whether a frame has
alpha. Update how we determine the required frame, which had bugs.
(Update a test that had an incorrect required frame as a result.)

Add new test images covering cases that have been fixed:
- randPixelsAnim2.gif
It has the following frames:
A (keep)
B (keep) (subset)
C (disposePrevious) (covers B)
D (any) (does *not* cover B)

B and C depend on A, but D depends on B, since after disposing C, B
should be visible again.

- alphabetAnim.gif
Includes frames which fill the image size, with different disposal
methods and transparencies.

Change-Id: Ie086167711c4cac4931ed8c4ddaeb9c9b0b91fdb
Reviewed-on: https://skia-review.googlesource.com/9810
Commit-Queue: Leon Scroggins <scroggo@google.com>
Reviewed-by: Mike Reed <reed@google.com>
Reviewed-by: Matt Sarett <msarett@google.com>

2 files changed, 99 insertions, 39 deletions

diff --git a/third_party/gif/SkGifImageReader.cpp b/third_party/gif/SkGifImageReader.cpp
index f8a454a630..86768e301c 100644
--- a/third_party/gif/SkGifImageReader.cpp
+++ b/third_party/gif/SkGifImageReader.cpp
@@ -760,8 +760,8 @@ bool SkGifImageReader::parse(SkGifImageReader::SkGIFParseQuery query)
                     m_firstFrameSupportsIndex8 = true;
                 } else {
                     const bool frameIsSubset = xOffset > 0 || yOffset > 0
-                            || width < m_screenWidth
-                            || height < m_screenHeight;
+                            || xOffset + width < m_screenWidth
+                            || yOffset + height < m_screenHeight;
                     m_firstFrameHasAlpha = frameIsSubset;
                     m_firstFrameSupportsIndex8 = !frameIsSubset;
                 }
@@ -799,7 +799,7 @@ bool SkGifImageReader::parse(SkGifImageReader::SkGIFParseQuery query)
                 break;
             }
 
-            setRequiredFrame(currentFrame);
+            setAlphaAndRequiredFrame(currentFrame);
             GETN(1, SkGIFLZWStart);
             break;
         }
@@ -809,7 +809,7 @@ bool SkGifImageReader::parse(SkGifImageReader::SkGIFParseQuery query)
             auto* currentFrame = m_frames.back().get();
             auto& cmap = currentFrame->localColorMap();
             cmap.setTablePosition(m_streamBuffer.markPosition());
-            setRequiredFrame(currentFrame);
+            setAlphaAndRequiredFrame(currentFrame);
             GETN(1, SkGIFLZWStart);
             break;
         }
@@ -891,55 +891,107 @@ void SkGifImageReader::addFrameIfNecessary()
     }
 }
 
-void SkGifImageReader::setRequiredFrame(SkGIFFrameContext* frame) {
+static SkIRect frame_rect_on_screen(SkIRect frameRect,
+                                    const SkIRect& screenRect) {
+    if (!frameRect.intersect(screenRect)) {
+        return SkIRect::MakeEmpty();
+    }
+
+    return frameRect;
+}
+
+static bool independent(const SkGIFFrameContext& frame) {
+    return frame.getRequiredFrame() == SkCodec::kNone;
+}
+
+static bool restore_bg(const SkGIFFrameContext& frame) {
+    return frame.getDisposalMethod() == SkCodecAnimation::RestoreBGColor_DisposalMethod;
+}
+
+void SkGifImageReader::setAlphaAndRequiredFrame(SkGIFFrameContext* frame) {
     const size_t i = frame->frameId();
     if (0 == i) {
+        frame->setHasAlpha(m_firstFrameHasAlpha);
         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.
+    // independent and opaque if they do not use the transparent pixel, but that would require
+    // checking whether each pixel used the transparent index.
     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);
+    const auto screenRect = SkIRect::MakeWH(m_screenWidth, m_screenHeight);
+    const auto frameRect = frame_rect_on_screen(frame->frameRect(), screenRect);
 
-    if (!transValid && frameCoversPriorFrame) {
-        frame->setRequiredFrame(prevFrame->getRequiredFrame());
+    if (!transValid && frameRect == screenRect) {
+        frame->setHasAlpha(false);
+        frame->setRequiredFrame(SkCodec::kNone);
         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;
+    const SkGIFFrameContext* prevFrame = m_frames[i - 1].get();
+    while (prevFrame->getDisposalMethod() == SkCodecAnimation::RestorePrevious_DisposalMethod) {
+        const size_t prevId = prevFrame->frameId();
+        if (0 == prevId) {
+            frame->setHasAlpha(true);
+            frame->setRequiredFrame(SkCodec::kNone);
+            return;
+        }
+
+        prevFrame = m_frames[prevId - 1].get();
+    }
+
+    const bool clearPrevFrame = restore_bg(*prevFrame);
+    auto prevFrameRect = frame_rect_on_screen(prevFrame->frameRect(), screenRect);
+
+    if (clearPrevFrame) {
+        if (prevFrameRect == screenRect || independent(*prevFrame)) {
+            frame->setHasAlpha(true);
+            frame->setRequiredFrame(SkCodec::kNone);
+            return;
+        }
     }
+
+    if (transValid) {
+        // Note: We could be more aggressive here. If prevFrame clears
+        // to background color and covers its required frame (and that
+        // frame is independent), prevFrame could be marked independent.
+        // Would this extra complexity be worth it?
+        frame->setRequiredFrame(prevFrame->frameId());
+        frame->setHasAlpha(prevFrame->hasAlpha() || clearPrevFrame);
+        return;
+    }
+
+    while (frameRect.contains(prevFrameRect)) {
+        const size_t prevRequiredFrame = prevFrame->getRequiredFrame();
+        if (prevRequiredFrame == SkCodec::kNone) {
+            frame->setRequiredFrame(SkCodec::kNone);
+            frame->setHasAlpha(true);
+            return;
+        }
+
+        prevFrame = m_frames[prevRequiredFrame].get();
+        prevFrameRect = frame_rect_on_screen(prevFrame->frameRect(), screenRect);
+    }
+
+    if (restore_bg(*prevFrame)) {
+        frame->setHasAlpha(true);
+        if (prevFrameRect == screenRect || independent(*prevFrame)) {
+            frame->setRequiredFrame(SkCodec::kNone);
+        } else {
+            // Note: As above, frame could still be independent, e.g. if
+            // prevFrame covers its required frame and that frame is
+            // independent.
+            frame->setRequiredFrame(prevFrame->frameId());
+        }
+        return;
+    }
+
+    SkASSERT(prevFrame->getDisposalMethod() == SkCodecAnimation::Keep_DisposalMethod);
+    frame->setRequiredFrame(prevFrame->frameId());
+    frame->setHasAlpha(prevFrame->hasAlpha());
 }
 
 // FIXME: Move this method to close to doLZW().
diff --git a/third_party/gif/SkGifImageReader.h b/third_party/gif/SkGifImageReader.h
index 24c917af2a..9d69e48823 100644
--- a/third_party/gif/SkGifImageReader.h
+++ b/third_party/gif/SkGifImageReader.h
@@ -201,6 +201,7 @@ public:
         , m_width(0)
         , m_height(0)
         , m_transparentPixel(SkGIFColorMap::kNotFound)
+        , m_hasAlpha(false)
         , m_disposalMethod(SkCodecAnimation::Keep_DisposalMethod)
         , m_requiredFrame(kUninitialized)
         , m_dataSize(0)
@@ -240,6 +241,8 @@ public:
     unsigned height() const { return m_height; }
     size_t transparentPixel() const { return m_transparentPixel; }
     void setTransparentPixel(size_t pixel) { m_transparentPixel = pixel; }
+    bool hasAlpha() const { return m_hasAlpha; }
+    void setHasAlpha(bool alpha) { m_hasAlpha = alpha; }
     SkCodecAnimation::DisposalMethod getDisposalMethod() const { return m_disposalMethod; }
     void setDisposalMethod(SkCodecAnimation::DisposalMethod disposalMethod) { m_disposalMethod = disposalMethod; }
 
@@ -282,6 +285,11 @@ private:
     unsigned m_width;
     unsigned m_height;
     size_t m_transparentPixel; // Index of transparent pixel. Value is kNotFound if there is no transparent pixel.
+    // Cached value, taking into account:
+    // - m_transparentPixel
+    // - frameRect
+    // - previous required frame
+    bool m_hasAlpha;
     SkCodecAnimation::DisposalMethod m_disposalMethod; // Restore to background, leave in place, etc.
     size_t m_requiredFrame;
     int m_dataSize;
@@ -407,7 +415,7 @@ private:
 
     void addFrameIfNecessary();
     // Must be called *after* the SkGIFFrameContext's color table (if any) has been parsed.
-    void setRequiredFrame(SkGIFFrameContext*);
+    void setAlphaAndRequiredFrame(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);