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>

7 files changed, 168 insertions, 57 deletions

diff --git a/include/codec/SkCodec.h b/include/codec/SkCodec.h
index 11d28ea8f2..6d4352214c 100644
--- a/include/codec/SkCodec.h
+++ b/include/codec/SkCodec.h
@@ -619,6 +619,12 @@ public:
          *  There could be an error in the stream.
          */
         bool fFullyReceived;
+
+        /**
+         *  This is conservative; it will still return non-opaque if e.g. a
+         *  color index-based frame has a color with alpha but does not use it.
+         */
+        SkAlphaType fAlphaType;
     };
 
     /**
diff --git a/resources/alphabetAnim.gif b/resources/alphabetAnim.gif
new file mode 100644
index 0000000000..d6b7d85b0e
--- /dev/null
+++ b/resources/alphabetAnim.gif
diff --git a/resources/randPixelsAnim2.gif b/resources/randPixelsAnim2.gif
new file mode 100644
index 0000000000..2b2b456155
--- /dev/null
+++ b/resources/randPixelsAnim2.gif
diff --git a/src/codec/SkGifCodec.cpp b/src/codec/SkGifCodec.cpp
index 40339b52c6..06c0803136 100644
--- a/src/codec/SkGifCodec.cpp
+++ b/src/codec/SkGifCodec.cpp
@@ -141,6 +141,8 @@ std::vector<SkCodec::FrameInfo> SkGifCodec::onGetFrameInfo() {
         result[i].fDuration = frameContext->delayTime();
         result[i].fRequiredFrame = frameContext->getRequiredFrame();
         result[i].fFullyReceived = frameContext->isComplete();
+        result[i].fAlphaType = frameContext->hasAlpha() ? kUnpremul_SkAlphaType
+                                                        : kOpaque_SkAlphaType;
     }
     return result;
 }
diff --git a/tests/CodecAnimTest.cpp b/tests/CodecAnimTest.cpp
index 9f9a160bbb..dea4adbfd2 100644
--- a/tests/CodecAnimTest.cpp
+++ b/tests/CodecAnimTest.cpp
@@ -32,42 +32,68 @@ static void write_bm(const char* name, const SkBitmap& bm) {
 }
 
 DEF_TEST(Codec_frames, r) {
+    #define kOpaque     kOpaque_SkAlphaType
+    #define kUnpremul   kUnpremul_SkAlphaType
     static const struct {
-        const char*         fName;
-        size_t              fFrameCount;
+        const char*              fName;
+        size_t                   fFrameCount;
         // One less than fFramecount, since the first frame is always
         // independent.
-        std::vector<size_t> fRequiredFrames;
+        std::vector<size_t>      fRequiredFrames;
+        // Same, since the first frame should match getInfo.
+        std::vector<SkAlphaType> fAlphaTypes;
         // The size of this one should match fFrameCount for animated, empty
         // otherwise.
-        std::vector<size_t> fDurations;
-        int                 fRepetitionCount;
+        std::vector<size_t>      fDurations;
+        int                      fRepetitionCount;
     } gRecs[] = {
+        { "alphabetAnim.gif", 13,
+            { SkCodec::kNone, 0, 0, 0, 0, 5, 6, SkCodec::kNone,
+              SkCodec::kNone, SkCodec::kNone, 10, 11 },
+            { kUnpremul, kUnpremul, kUnpremul, kUnpremul, kUnpremul, kUnpremul,
+              kUnpremul, kUnpremul, kUnpremul, kOpaque, kOpaque, kUnpremul },
+            { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 },
+            0 },
+        { "randPixelsAnim2.gif", 4,
+            // required frames
+            { 0, 0, 1 },
+            // alphas
+            { kOpaque, kOpaque, kOpaque },
+            // durations
+            { 0, 1000, 170, 40 },
+            // repetition count
+            0 },
         { "randPixelsAnim.gif", 13,
             // required frames
-            { SkCodec::kNone, 1, 2, 3, 4, 4, 6, 7, 7, 7, 7, 7 },
+            { SkCodec::kNone, 1, 2, 3, 4, 3, 6, 7, 7, 7, 9, 9 },
+            { kUnpremul, kUnpremul, kUnpremul, kUnpremul, kUnpremul, kUnpremul,
+              kUnpremul, kUnpremul, kUnpremul, kUnpremul, kUnpremul, kUnpremul },
             // durations
             { 0, 1000, 170, 40, 220, 7770, 90, 90, 90, 90, 90, 90, 90 },
             // repetition count
             0 },
-        { "box.gif", 1, {}, {}, 0 },
-        { "color_wheel.gif", 1, {}, {}, 0 },
-        { "test640x479.gif", 4, { 0, 1, 2 }, { 200, 200, 200, 200 },
+        { "box.gif", 1, {}, {}, {}, 0 },
+        { "color_wheel.gif", 1, {}, {}, {}, 0 },
+        { "test640x479.gif", 4, { 0, 1, 2 },
+                { kOpaque, kOpaque, kOpaque },
+                { 200, 200, 200, 200 },
                 SkCodec::kRepetitionCountInfinite },
-        { "colorTables.gif", 2, { 0 }, { 1000, 1000 }, 5 },
+        { "colorTables.gif", 2, { 0 }, { kOpaque }, { 1000, 1000 }, 5 },
 
-        { "arrow.png",  1, {}, {}, 0 },
-        { "google_chrome.ico", 1, {}, {}, 0 },
-        { "brickwork-texture.jpg", 1, {}, {}, 0 },
+        { "arrow.png",  1, {}, {}, {}, 0 },
+        { "google_chrome.ico", 1, {}, {}, {}, 0 },
+        { "brickwork-texture.jpg", 1, {}, {}, {}, 0 },
 #if defined(SK_CODEC_DECODES_RAW) && (!defined(_WIN32))
-        { "dng_with_preview.dng", 1, {}, {}, 0 },
+        { "dng_with_preview.dng", 1, {}, {}, {}, 0 },
 #endif
-        { "mandrill.wbmp", 1, {}, {}, 0 },
-        { "randPixels.bmp", 1, {}, {}, 0 },
-        { "yellow_rose.webp", 1, {}, {}, 0 },
+        { "mandrill.wbmp", 1, {}, {}, {}, 0 },
+        { "randPixels.bmp", 1, {}, {}, {}, 0 },
+        { "yellow_rose.webp", 1, {}, {}, {}, 0 },
     };
+    #undef kOpaque
+    #undef kUnpremul
 
-    for (auto rec : gRecs) {
+    for (const auto& rec : gRecs) {
         std::unique_ptr<SkStream> stream(GetResourceAsStream(rec.fName));
         if (!stream) {
             // Useful error statement, but sometimes people run tests without
@@ -107,13 +133,30 @@ DEF_TEST(Codec_frames, r) {
             continue;
         }
 
+        auto to_string = [](SkAlphaType type) {
+            switch (type) {
+                case kUnpremul_SkAlphaType:
+                    return "unpremul";
+                case kOpaque_SkAlphaType:
+                    return "opaque";
+                default:
+                    return "other";
+            }
+        };
         // From here on, we are only concerned with animated images.
         REPORTER_ASSERT(r, frameInfos[0].fRequiredFrame == SkCodec::kNone);
+        REPORTER_ASSERT(r, frameInfos[0].fAlphaType == codec->getInfo().alphaType());
         for (size_t i = 1; i < frameCount; i++) {
             if (rec.fRequiredFrames[i-1] != frameInfos[i].fRequiredFrame) {
                 ERRORF(r, "%s's frame %i has wrong dependency! expected: %i\tactual: %i",
                        rec.fName, i, rec.fRequiredFrames[i-1], frameInfos[i].fRequiredFrame);
             }
+            auto expectedAlpha = rec.fAlphaTypes[i-1];
+            auto alpha = frameInfos[i].fAlphaType;
+            if (expectedAlpha != alpha) {
+                ERRORF(r, "%s's frame %i has wrong alpha type! expected: %s\tactual: %s",
+                       rec.fName, i, to_string(expectedAlpha), to_string(alpha));
+            }
         }
 
         // Compare decoding in two ways:
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);