GIF decoding to Index8, unit tests and misusing unit test as benchmark

third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp

Index: third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp
diff --git a/third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp b/third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp
index cc5954edf9de97a6391a4c904dc4826cc341741d..298081f42d337afebc2ce6e53838240a413e1272 100644
--- a/third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp
+++ b/third_party/WebKit/Source/platform/image-decoders/gif/GIFImageDecoder.cpp
@@ -28,13 +28,13 @@
 #include <limits>
 #include "platform/image-decoders/gif/GIFImageReader.h"
 #include "wtf/NotFound.h"
-#include "wtf/PassOwnPtr.h"

[scroggo_chromium, 2016/04/29 19:48:14]

Unrelated change?

 
 namespace blink {
 
-GIFImageDecoder::GIFImageDecoder(AlphaOption alphaOption, GammaAndColorProfileOption colorOptions, size_t maxDecodedBytes)
+GIFImageDecoder::GIFImageDecoder(AlphaOption alphaOption, GammaAndColorProfileOption colorOptions, size_t maxDecodedBytes, ImageFrame::ColorType colorType)
     : ImageDecoder(alphaOption, colorOptions, maxDecodedBytes)
     , m_repetitionCount(cAnimationLoopOnce)
+    , m_requestedColorMode(colorType)
 {
 }
 
@@ -101,36 +101,51 @@ bool GIFImageDecoder::setFailed()
     return ImageDecoder::setFailed();
 }
 
-bool GIFImageDecoder::haveDecodedRow(size_t frameIndex, GIFRow::const_iterator rowBegin, size_t width, size_t rowNumber, unsigned repeatCount, bool writeTransparentPixels)
+static inline const GIFColorMap& getColorMap(const GIFFrameContext& frameContext, const GIFImageReader& reader)
+{
+    return (frameContext.localColorMap().isDefined() ? frameContext.localColorMap() : reader.globalColorMap());
+}
+
+void GIFImageDecoder::haveDecodedRow(const GIFFrameContext& frameContext, GIFRow::const_iterator rowBegin, 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
     // origin within the entire image size, i.e.
     // (frameContext->xOffset, frameContext->yOffset). There is no guarantee
     // that width == (size().width() - frameContext->xOffset), so
     // we must ensure we don't run off the end of either the source data or the
     // row's X-coordinates.
-    const int xBegin = frameContext->xOffset();
-    const int yBegin = frameContext->yOffset() + rowNumber;
-    const int xEnd = std::min(static_cast<int>(frameContext->xOffset() + width), size().width());
-    const int yEnd = std::min(static_cast<int>(frameContext->yOffset() + rowNumber + repeatCount), size().height());
+    const size_t width = frameContext.width();
+    const int xBegin = frameContext.xOffset();
+    const int yBegin = frameContext.yOffset() + rowNumber;
+    const int xEnd = std::min(static_cast<int>(xBegin + width), size().width());
+    const int yEnd = std::min(static_cast<int>(yBegin + repeatCount), size().height());
     if (!width || (xBegin < 0) || (yBegin < 0) || (xEnd <= xBegin) || (yEnd <= yBegin))
-        return true;
+        return;
 
-    const GIFColorMap::Table& colorTable = frameContext->localColorMap().isDefined() ? frameContext->localColorMap().table() : m_reader->globalColorMap().table();
+    const GIFColorTable& colorTable = getColorMap(frameContext, *m_reader).table();
 
     if (colorTable.isEmpty())
-        return true;
+        return;
 
-    GIFColorMap::Table::const_iterator colorTableIter = colorTable.begin();
+    ImageFrame& buffer = m_frameBufferCache[frameContext.frameId()];

[scroggo_chromium, 2016/04/29 19:48:15]

As I understand it, we will now have always initialized the frame already at
this point? Maybe add a comment, and/or ASSERT(buffer.status() != FrameEmpty).

More importantly, I think this change (calling initFrameBuffer before calling
haveDecodedRow) is a good change on its own, and doesn't really relate to the
rest of the change. Please remove this piece and submit it for review on its
own. This provides a number of benefits:

- we can weigh the benefit of the change on its own
- if it causes a problem, we can revert it, without affecting other changes
- if the rest of this change (which I think is more risky) needs to be reverted,
we won't revert this part
- it reduces the size of this issue, making it easier to review

+    GIFRow::const_iterator rowEnd = rowBegin + (xEnd - xBegin);
 
-    // Initialize the frame if necessary.
-    ImageFrame& buffer = m_frameBufferCache[frameIndex];
-    if ((buffer.status() == ImageFrame::FrameEmpty) && !initFrameBuffer(frameIndex))
-        return false;
+    (this->*m_writeRowFunction)(frameContext, buffer, colorTable, rowBegin, rowEnd, xBegin, yBegin, writeTransparentPixels);
 
-    const size_t transparentPixel = frameContext->transparentPixel();
-    GIFRow::const_iterator rowEnd = rowBegin + (xEnd - xBegin);
+    // Tell the frame to copy the row data if need be.
+    if (repeatCount > 1)
+        (*m_copyRowNTimesFunction)(buffer, xBegin, xEnd, yBegin, yEnd);

[scroggo_chromium, 2016/04/29 19:48:14]

I found it weird that this method does not take N / repeatCount as a parameter.
Digging further, yEnd was computed from repeatCount, which in turn was created
by subtracting a similar end and beginning. All of this precedes your change
though.

+
+    buffer.setPixelsChanged(true);
+}
+
+
+void GIFImageDecoder::writeRowN32(const GIFFrameContext& frameContext, ImageFrame& buffer, const GIFColorTable& colorTable, GIFRow::const_iterator rowBegin, GIFRow::const_iterator rowEnd, int xBegin, int yBegin, bool writeTransparentPixels)
+{
+    ASSERT(m_frameBufferCache[frameContext.frameId()].bitmap().colorType() == kN32_SkColorType);
+
+    GIFColorTable::const_iterator colorTableIter = colorTable.begin();
+    const size_t transparentPixel = frameContext.transparentPixel();
     ImageFrame::PixelData* currentAddress = buffer.getAddr(xBegin, yBegin);
 
     // We may or may not need to write transparent pixels to the buffer.
@@ -164,13 +179,72 @@ bool GIFImageDecoder::haveDecodedRow(size_t frameIndex, GIFRow::const_iterator r
                 m_currentBufferSawAlpha = true;
         }
     }
+}
 
-    // Tell the frame to copy the row data if need be.
-    if (repeatCount > 1)
-        buffer.copyRowNTimes(xBegin, xEnd, yBegin, yEnd);
+void GIFImageDecoder::writeRowIndex8(const GIFFrameContext& frameContext, ImageFrame& buffer, const GIFColorTable& colorTable, GIFRow::const_iterator rowBegin, GIFRow::const_iterator rowEnd, int xBegin, int yBegin, bool writeTransparentPixels)
+{
+    ASSERT(m_frameBufferCache[frameContext.frameId()].bitmap().colorType() == kIndex_8_SkColorType);
+
+    const size_t transparentPixel = frameContext.transparentPixel();
+    ImageFrame::PixelData8* currentAddress = buffer.getAddr8(xBegin, yBegin);
+
+    bool opaque = true;
+    // writeTransparentPixels is writing without check, but calculates if there

[scroggo_chromium, 2016/04/29 19:48:15]

What does this mean? It sure looks like if (writeTransparentPixels) we check for
opacity (line 199)

+    // is transparency (m_currentBufferSawAlpha). If transparency was found in
+    // previous rows, no need to calculate here.

[scroggo_chromium, 2016/04/29 19:48:15]

Would writeRowN32 benefit from this optimization? (i.e.Don't check for
transparency if m_currentBufferSawAlpha is already true.) (If so I think it
should be its own change.)

+    writeTransparentPixels = writeTransparentPixels || buffer.requiredPreviousFrameIndex() == kNotFound;
+    if (transparentPixel < colorTable.size() && !(writeTransparentPixels && m_currentBufferSawAlpha)) {
+        if (writeTransparentPixels) {
+            while (rowBegin != rowEnd) {
+                opaque = opaque && (*rowBegin ^ transparentPixel);
+                *currentAddress++ = *rowBegin++;
+            }
+        } else {
+            for (; rowBegin != rowEnd; ++rowBegin, ++currentAddress) {
+                size_t index = *rowBegin;
+                if (index == transparentPixel) {

[scroggo_chromium, 2016/04/29 19:48:15]

I personally prefer braces here, but the style guide suggests no braces for a
one line if block.

+                    opaque = false;
+                } else {
+                    *currentAddress = index;
+                }
+            }
+        }
+    } else {
+        // No transparency to deal with.

[scroggo_chromium, 2016/04/29 19:48:15]

I think this comment is misleading. We're not keeping track of whether there is
transparency, but there still might be transparency. It might be clearer to say
something like:

Either there is no transparency, or the buffer has already seen alpha. No need
to check for transparency.

+        if (rowEnd - rowBegin == size().width()) {
+            size_t* destination = (size_t*)currentAddress;
+            const size_t* source = (const size_t*)rowBegin;
+            const size_t count = (rowEnd - rowBegin + sizeof(size_t) - 1) / sizeof(size_t);
+            const size_t* sourceEnd = source + count;
+            while (source != sourceEnd)

[scroggo_chromium, 2016/04/29 19:48:14]

Why is this not a memcpy?

+                *destination++ = *source++;
+        } else {
+            while (rowBegin != rowEnd)

[scroggo_chromium, 2016/04/29 19:48:15]

Can this be a memcpy?

+                *currentAddress++ = *rowBegin++;
+        }
+    }
 
-    buffer.setPixelsChanged(true);
-    return true;
+    if (!opaque)
+        m_currentBufferSawAlpha = true;
+}
+
+// Copies the pixel data at [(xBegin, yBegin), (xEnd, yEnd)) to the

[scroggo_chromium, 2016/04/29 19:48:15]

Don't these actually copy the data from [(xBegin, yBegin), (xEnd, yBegin)]?

+// same X-coordinates on each subsequent row up to but not including
+// yEnd.
+static void copyRowNTimesFunctionN32(ImageFrame& buffer, int xBegin, int xEnd, int yBegin, int yEnd)
+{
+    const int rowBytes = (xEnd - xBegin) * sizeof(ImageFrame::PixelData);

[scroggo_chromium, 2016/04/29 19:48:15]

I'm not sure "rowBytes" is the correct name here. That usually refers to the
distance from the start of one row to the start of the next (which may be larger
than the width of the pixels * number of pixels, if there's padding). But that's
not the case here. This is the size of the data to copy.

Maybe this should be something like "bytesToCopy"?

+    const ImageFrame::PixelData* const startAddr = buffer.getAddr(xBegin, yBegin);
+    for (int destY = yBegin + 1; destY < yEnd; ++destY)
+        memcpy(buffer.getAddr(xBegin, destY), startAddr, rowBytes);
+}
+
+static void copyRowNTimesFunctionIndex8(ImageFrame& buffer, int xBegin, int xEnd, int yBegin, int yEnd)
+{
+    const int rowBytes = (xEnd - xBegin) * sizeof(ImageFrame::PixelData8);
+    const ImageFrame::PixelData8* const startAddr = buffer.getAddr8(xBegin, yBegin);
+    for (int destY = yBegin + 1; destY < yEnd; ++destY)
+        memcpy(buffer.getAddr8(xBegin, destY), startAddr, rowBytes);
 }
 
 bool GIFImageDecoder::parseCompleted() const
@@ -292,6 +366,17 @@ void GIFImageDecoder::decode(size_t index)
         setFailed();
 }
 
+void GIFImageDecoder::setupHaveDecodedRowCallbacks(bool isIndex8)
+{
+    if (isIndex8) {
+        m_writeRowFunction = &GIFImageDecoder::writeRowIndex8;
+        m_copyRowNTimesFunction = &copyRowNTimesFunctionIndex8;
+    } else {
+        m_writeRowFunction = &GIFImageDecoder::writeRowN32;
+        m_copyRowNTimesFunction = &copyRowNTimesFunctionN32;
+    }
+}
+
 void GIFImageDecoder::parse(GIFParseQuery query)
 {
     if (failed())
@@ -306,32 +391,169 @@ void GIFImageDecoder::parse(GIFParseQuery query)
         setFailed();
 }
 
-bool GIFImageDecoder::initFrameBuffer(size_t frameIndex)
+bool GIFImageDecoder::initFrameBufferFromPrevious(ImageFrame* buffer, const ImageFrame& previousBuffer, ImageFrame::ColorType targetType, size_t transparentIndex)
+{
+    // Preserve the last frame as the starting state for this frame.
+    if (!buffer->copyBitmapData(previousBuffer, targetType))
+        return false;
+
+    if (previousBuffer.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 = previousBuffer.originalFrameRect();
+        ASSERT(!prevRect.contains(IntRect(IntPoint(), size())));
+        if (targetType == ImageFrame::Index8)
+            buffer->zeroFillFrameRectIndex8(prevRect, (transparentIndex > 255) ? 255 : transparentIndex);

[scroggo_chromium, 2016/04/29 19:48:14]

I think I've brought this up before - this looks like we might "zeroFill" with
255, which may not be transparent.

(That said, the implementation ignores this parameter...)

+        else
+            buffer->zeroFillFrameRect(prevRect);
+    }
+    return true;
+}
+
+bool GIFImageDecoder::initFrameBufferN32(size_t frameIndex)
 {
+    setupHaveDecodedRowCallbacks(false);
+
     // Initialize the frame rect in our buffer.
-    ImageFrame* const buffer = &m_frameBufferCache[frameIndex];
+    ImageFrame* buffer = &m_frameBufferCache[frameIndex];
 
     size_t requiredPreviousFrameIndex = buffer->requiredPreviousFrameIndex();
     if (requiredPreviousFrameIndex == kNotFound) {
         // This frame doesn't rely on any previous data.

[scroggo_chromium, 2016/04/29 19:48:15]

If it does not rely on previous data, can we not start with index8?

-        if (!buffer->setSize(size().width(), size().height()))
+        if (!buffer->setSize(size().width(), size().height(), getBackgroundColor(frameIndex)))
             return setFailed();
     } else {
         const ImageFrame* prevBuffer = &m_frameBufferCache[requiredPreviousFrameIndex];
         ASSERT(prevBuffer->status() == ImageFrame::FrameComplete);
-
-        // Preserve the last frame as the starting state for this frame.
-        if (!buffer->copyBitmapData(*prevBuffer))
+        if (!initFrameBufferFromPrevious(buffer, *prevBuffer, ImageFrame::N32))
             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();
-            ASSERT(!prevRect.contains(IntRect(IntPoint(), size())));
-            buffer->zeroFillFrameRect(prevRect);
+    // Update our status to be partially complete.
+    buffer->setStatus(ImageFrame::FramePartial);
+
+    // Reset the alpha pixel tracker for this frame.
+    m_currentBufferSawAlpha = false;
+    return true;
+}
+
+bool GIFImageDecoder::isIndex8Applicable(const GIFFrameContext& frame, size_t requiredPreviousFrameIndex) const
+{
+    const GIFColorMap& colorMap = getColorMap(frame, *m_reader);
+    const bool useGlobalColorMap = !frame.localColorMap().isDefined();
+    const bool transparencySupported = colorMap.getTableSize() < 256 || frame.transparentPixel() >= colorMap.getTableSize();
+
+    if (requiredPreviousFrameIndex == kNotFound) {
+        if (!transparencySupported

[scroggo_chromium, 2016/04/29 19:48:14]

Why not switch this from:

if (condition) {
  return false;
}
return true;

to

return !condition;

?

+            && useGlobalColorMap && m_reader->backgroundIndex() >= colorMap.getTableSize()
+            && (!isAllDataReceived() || !frame.frameRect().contains(IntRect(IntPoint(), size())))) {
+            // Background is filled with transparency or with background color -
+            // background color is used for opaque gifs.
+            // Return false when there is a need for transparency and no space
+            // in colormap for it; when colormap is opaque and full (it has 256
+            // entries) and at the same time
+            // - image is not fully received, so missing part would need to be
+            //   presented as transparent, or
+            // - the frame is not fullscreen, i.e. it would be decoded to a sub
+            //   rectangle of the image rectangle.
+            return false;
+        }
+        return true;
+    }
+
+    const GIFFrameContext& previousFrame(*(m_reader->frameContext(requiredPreviousFrameIndex)));
+
+    // Skip Index8 for DisposeOverwriteBgcolor disposal method if there is no transparency.
+    if (previousFrame.disposalMethod() == ImageFrame::DisposeOverwriteBgcolor && !transparencySupported)
+        return false;
+
+    // If frame shares colormap with required previous frame, it is possible to keep using Index8.
+    const GIFColorMap& previousColorMap = getColorMap(previousFrame, *m_reader);
+    return ((colorMap.getPosition() == previousColorMap.getPosition()) && (frame.transparentPixel() == previousFrame.transparentPixel()));
+}
+
+// Helper method to check if a previous frame dependency can be removed.
+void GIFImageDecoder::updateRequiredPreviousFrame(ImageFrame* buffer, const GIFFrameContext& frameContext)
+{
+    ASSERT(m_requestedColorMode == ImageFrame::Index8);
+    if (buffer->requiredPreviousFrameIndex() == kNotFound)
+        return;
+
+    bool isFullScreen = frameContext.frameRect().contains(IntRect(IntPoint(), size()));
+
+    // If fullscreen and opaque, the frame is independent of previous frame.

[scroggo_chromium, 2016/04/29 19:48:15]

This comment seems a little out of place to me. How about:

// If the frame is not full screen, it cannot be independent.

You talk below about opacity.

+    if (!isFullScreen)
+        return;
+
+    // If transparent pixel is outside color table, there is no transparent
+    // pixel, e.g. color table in some of the GIFs has 40 elements and
+    // transparentPixel value is 0xFF.
+    if (frameContext.transparentPixel() >= getColorMap(frameContext, *m_reader).getTableSize())
+        buffer->setRequiredPreviousFrameIndex(kNotFound);
+}
+
+// Returns transparent index or background index.
+unsigned GIFImageDecoder::getBackgroundIndex(const GIFFrameContext& frameContext) const
+{
+    const size_t background = frameContext.transparentPixel();
+    const GIFColorMap& colorMap = getColorMap(frameContext, *m_reader);
+    if (background < colorMap.getTableSize())
+        return background;
+
+    if (!frameContext.localColorMap().isDefined() && m_reader->backgroundIndex() < colorMap.getTableSize())
+        return m_reader->backgroundIndex();
+    return -1;

[scroggo_chromium, 2016/04/29 19:48:15]

Again, I think it's weird to return -1 as an unsigned.

+}
+
+SkColor GIFImageDecoder::getBackgroundColor(size_t frameIndex) const
+{
+    const GIFFrameContext* frameContext = m_reader->frameContext(frameIndex);
+    unsigned backgroundIndex = getBackgroundIndex(*frameContext);
+    if (frameContext->transparentPixel() == backgroundIndex)
+        return SK_ColorTRANSPARENT;
+    const GIFColorTable& table = getColorMap(*frameContext, *m_reader).table();
+    return (backgroundIndex < table.size() ? table[backgroundIndex]: SK_ColorTRANSPARENT);

[scroggo_chromium, 2016/04/29 19:48:15]

How does this fall back to transparent? It seems like we have to use a color
that's in some color table, right?

+}
+
+bool GIFImageDecoder::initFrameBuffer(size_t frameIndex)
+{
+    ImageFrame* buffer = &m_frameBufferCache[frameIndex];
+    if (buffer->status() != ImageFrame::FrameEmpty) {
+        // If it is partial, decode to the same bitmap.
+        setupHaveDecodedRowCallbacks(buffer->getSkBitmap().colorType() == kIndex_8_SkColorType);
+        return true;
+    }
+
+    if (m_requestedColorMode == ImageFrame::N32) {
+        return initFrameBufferN32(frameIndex);
+    }
+    const GIFFrameContext* frameContext = m_reader->frameContext(frameIndex);
+    updateRequiredPreviousFrame(buffer, *frameContext);
+    const size_t requiredPreviousFrameIndex = buffer->requiredPreviousFrameIndex();
+
+    bool useIndex8 = true;
+    if (requiredPreviousFrameIndex == kNotFound) {
+        if (isIndex8Applicable(*frameContext, requiredPreviousFrameIndex)) {
+            const unsigned backgroundIndex = getBackgroundIndex(*frameContext);
+            if (!buffer->setSizeIndex8(
+                size().width(), size().height(),
+                getColorMap(*frameContext, *m_reader).table(), backgroundIndex,
+                backgroundIndex == frameContext->transparentPixel()))
+                return setFailed();
+        } else {
+            return initFrameBufferN32(frameIndex);
         }
+    } else {
+        const ImageFrame* prevBuffer = &m_frameBufferCache[requiredPreviousFrameIndex];
+        ASSERT(prevBuffer->status() == ImageFrame::FrameComplete);
+
+        // Copy the required completed frame as the starting state for this frame.
+        useIndex8 = (prevBuffer->getSkBitmap().colorType() == kIndex_8_SkColorType) && isIndex8Applicable(*frameContext, requiredPreviousFrameIndex);
+        if (!initFrameBufferFromPrevious(buffer, *prevBuffer, useIndex8 ? ImageFrame::Index8 : ImageFrame::N32, frameContext->transparentPixel()))
+            return setFailed();
+        ASSERT(useIndex8 == (buffer->getSkBitmap().colorType() == kIndex_8_SkColorType));
     }
+    setupHaveDecodedRowCallbacks(useIndex8);
 
     // Update our status to be partially complete.
     buffer->setStatus(ImageFrame::FramePartial);
@@ -341,4 +563,30 @@ bool GIFImageDecoder::initFrameBuffer(size_t frameIndex)
     return true;
 }
 
+bool GIFImageDecoder::canDecodeTo(size_t index, ImageFrame::ColorType outputType)
+{
+    if ((index >= frameCount()) || (m_requestedColorMode == ImageFrame::N32) || failed())

[scroggo_chromium, 2016/04/29 19:48:15]

if (failed()), should this just return false? Otherwise we may report that we
canDecodeTo a type when we cannot decode at all.

+        return (outputType == m_requestedColorMode);
+
+    // Go from one to previous to calculate if Index8 is supported.
+    size_t frameToDecode = index;
+    ImageFrame::ColorType calculatedOutput = ImageFrame::Index8;
+    while (frameToDecode != kNotFound) {
+        ImageFrame* buffer = &m_frameBufferCache[frameToDecode];
+        if (buffer->status() == ImageFrame::FrameComplete) {
+            // In this case, color type from complete frame is kept.
+            calculatedOutput = static_cast<ImageFrame::ColorType>(buffer->getSkBitmap().colorType());
+            break;
+        }
+        const GIFFrameContext* frameContext = m_reader->frameContext(frameToDecode);
+        updateRequiredPreviousFrame(buffer, *frameContext);
+        if (!isIndex8Applicable(*frameContext, buffer->requiredPreviousFrameIndex())) {
+            calculatedOutput = ImageFrame::N32;
+            break;
+        }
+        frameToDecode = buffer->requiredPreviousFrameIndex();
+    }
+    return (calculatedOutput == outputType);
+}
+
 } // namespace blink