Support various types of animation gif.

Original code only supports an animation gif whose frames are
all same size and all same color format. This modification supports
various type of animation gif specified in GIF89a.
<http://www.w3.org/Graphics/GIF/spec-gif89a.txt>

Change-Id: I517182d2d227c9330aaff1c4cebc6c02b31ff8a6

1 files changed, 295 insertions, 75 deletions

diff --git a/src/images/SkMovie_gif.cpp b/src/images/SkMovie_gif.cpp
index 1138044..0a85c2d 100644
--- a/src/images/SkMovie_gif.cpp
+++ b/src/images/SkMovie_gif.cpp
@@ -20,6 +20,7 @@
 #include "SkColorPriv.h"
 #include "SkStream.h"
 #include "SkTemplates.h"
+#include "SkUtils.h"
 
 #include "gif_lib.h"
 
@@ -35,7 +36,9 @@ protected:
     
 private:
     GifFileType* fGIF;
-    SavedImage* fCurrSavedImage;
+    int fCurrIndex;
+    int fLastDrawIndex;
+    SkBitmap fBackup;
 };
 
 static int Decode(GifFileType* fileType, GifByteType* out, int size) {
@@ -54,7 +57,8 @@ SkGIFMovie::SkGIFMovie(SkStream* stream)
         DGifCloseFile(fGIF);
         fGIF = NULL;
     }
-    fCurrSavedImage = NULL;
+    fCurrIndex = -1;
+    fLastDrawIndex = -1;
 }
 
 SkGIFMovie::~SkGIFMovie()
@@ -105,29 +109,242 @@ bool SkGIFMovie::onSetTime(SkMSec time)
         dur += savedimage_duration(&fGIF->SavedImages[i]);
         if (dur >= time)
         {
-            SavedImage* prev = fCurrSavedImage;
-            fCurrSavedImage = &fGIF->SavedImages[i];
-            return prev != fCurrSavedImage;
+            fCurrIndex = i;
+            return fLastDrawIndex != fCurrIndex;
         }
     }
-    fCurrSavedImage = &fGIF->SavedImages[fGIF->ImageCount - 1];
+    fCurrIndex = fGIF->ImageCount - 1;
     return true;
 }
 
+static void copyLine(uint32_t* dst, const unsigned char* src, const ColorMapObject* cmap,
+                     int transparent, int width)
+{
+    for (; width > 0; width--, src++, dst++) {
+        if (*src != transparent) {
+            const GifColorType& col = cmap->Colors[*src];
+            *dst = SkPackARGB32(0xFF, col.Red, col.Green, col.Blue);
+        }
+    }
+}
+
+static void copyInterlaceGroup(SkBitmap* bm, const unsigned char*& src,
+                               const ColorMapObject* cmap, int transparent, int copyWidth,
+                               int copyHeight, const GifImageDesc& imageDesc, int rowStep,
+                               int startRow)
+{
+    int row;
+    // every 'rowStep'th row, starting with row 'startRow'
+    for (row = startRow; row < copyHeight; row += rowStep) {
+        uint32_t* dst = bm->getAddr32(imageDesc.Left, imageDesc.Top + row);
+        copyLine(dst, src, cmap, transparent, copyWidth);
+        src += imageDesc.Width;
+    }
+
+    // pad for rest height
+    src += imageDesc.Width * ((imageDesc.Height - row + rowStep - 1) / rowStep);
+}
+
+static void blitInterlace(SkBitmap* bm, const SavedImage* frame, const ColorMapObject* cmap,
+                          int transparent)
+{
+    int width = bm->width();
+    int height = bm->height();
+    GifWord copyWidth = frame->ImageDesc.Width;
+    if (frame->ImageDesc.Left + copyWidth > width) {
+        copyWidth = width - frame->ImageDesc.Left;
+    }
+
+    GifWord copyHeight = frame->ImageDesc.Height;
+    if (frame->ImageDesc.Top + copyHeight > height) {
+        copyHeight = height - frame->ImageDesc.Top;
+    }
+
+    // deinterlace
+    const unsigned char* src = (unsigned char*)frame->RasterBits;
+
+    // group 1 - every 8th row, starting with row 0
+    copyInterlaceGroup(bm, src, cmap, transparent, copyWidth, copyHeight, frame->ImageDesc, 8, 0);
+
+    // group 2 - every 8th row, starting with row 4
+    copyInterlaceGroup(bm, src, cmap, transparent, copyWidth, copyHeight, frame->ImageDesc, 8, 4);
+
+    // group 3 - every 4th row, starting with row 2
+    copyInterlaceGroup(bm, src, cmap, transparent, copyWidth, copyHeight, frame->ImageDesc, 4, 2);
+
+    copyInterlaceGroup(bm, src, cmap, transparent, copyWidth, copyHeight, frame->ImageDesc, 2, 1);
+}
+
+static void blitNormal(SkBitmap* bm, const SavedImage* frame, const ColorMapObject* cmap,
+                       int transparent)
+{
+    int width = bm->width();
+    int height = bm->height();
+    const unsigned char* src = (unsigned char*)frame->RasterBits;
+    uint32_t* dst = bm->getAddr32(frame->ImageDesc.Left, frame->ImageDesc.Top);
+    GifWord copyWidth = frame->ImageDesc.Width;
+    if (frame->ImageDesc.Left + copyWidth > width) {
+        copyWidth = width - frame->ImageDesc.Left;
+    }
+
+    GifWord copyHeight = frame->ImageDesc.Height;
+    if (frame->ImageDesc.Top + copyHeight > height) {
+        copyHeight = height - frame->ImageDesc.Top;
+    }
+
+    int srcPad, dstPad;
+    dstPad = width - copyWidth;
+    srcPad = frame->ImageDesc.Width - copyWidth;
+    for (; copyHeight > 0; copyHeight--) {
+        copyLine(dst, src, cmap, transparent, copyWidth);
+        src += frame->ImageDesc.Width;
+        dst += width;
+    }
+}
+
+static void fillRect(SkBitmap* bm, GifWord left, GifWord top, GifWord width, GifWord height,
+                     uint32_t col)
+{
+    int bmWidth = bm->width();
+    int bmHeight = bm->height();
+    uint32_t* dst = bm->getAddr32(left, top);
+    GifWord copyWidth = width;
+    if (left + copyWidth > bmWidth) {
+        copyWidth = bmWidth - left;
+    }
+
+    GifWord copyHeight = height;
+    if (top + copyHeight > bmHeight) {
+        copyHeight = bmHeight - top;
+    }
+
+    for (; copyHeight > 0; copyHeight--) {
+        sk_memset32(dst, col, copyWidth);
+        dst += bmWidth;
+    }
+}
+
+static void drawFrame(SkBitmap* bm, const SavedImage* frame, const ColorMapObject* cmap)
+{
+    int transparent = -1;
+
+    for (int i = 0; i < frame->ExtensionBlockCount; ++i) {
+        ExtensionBlock* eb = frame->ExtensionBlocks + i;
+        if (eb->Function == GRAPHICS_EXT_FUNC_CODE &&
+            eb->ByteCount == 4) {
+            bool has_transparency = ((eb->Bytes[0] & 1) == 1);
+            if (has_transparency) {
+                transparent = (unsigned char)eb->Bytes[3];
+            }
+        }
+    }
+
+    if (frame->ImageDesc.ColorMap != NULL) {
+        // use local color table
+        cmap = frame->ImageDesc.ColorMap;
+    }
+
+    if (cmap == NULL || cmap->ColorCount != (1 << cmap->BitsPerPixel)) {
+        SkASSERT(!"bad colortable setup");
+        return;
+    }
+
+    if (frame->ImageDesc.Interlace) {
+        blitInterlace(bm, frame, cmap, transparent);
+    } else {
+        blitNormal(bm, frame, cmap, transparent);
+    }
+}
+
+static bool checkIfWillBeCleared(const SavedImage* frame)
+{
+    for (int i = 0; i < frame->ExtensionBlockCount; ++i) {
+        ExtensionBlock* eb = frame->ExtensionBlocks + i;
+        if (eb->Function == GRAPHICS_EXT_FUNC_CODE &&
+            eb->ByteCount == 4) {
+            // check disposal method
+            int disposal = ((eb->Bytes[0] >> 2) & 7);
+            if (disposal == 2 || disposal == 3) {
+                return true;
+            }
+        }
+    }
+    return false;
+}
+
+static void getTransparencyAndDisposalMethod(const SavedImage* frame, bool* trans, int* disposal)
+{
+    *trans = false;
+    *disposal = 0;
+    for (int i = 0; i < frame->ExtensionBlockCount; ++i) {
+        ExtensionBlock* eb = frame->ExtensionBlocks + i;
+        if (eb->Function == GRAPHICS_EXT_FUNC_CODE &&
+            eb->ByteCount == 4) {
+            *trans = ((eb->Bytes[0] & 1) == 1);
+            *disposal = ((eb->Bytes[0] >> 2) & 7);
+        }
+    }
+}
+
+// return true if area of 'target' is completely covers area of 'covered'
+static bool checkIfCover(const SavedImage* target, const SavedImage* covered)
+{
+    if (target->ImageDesc.Left <= covered->ImageDesc.Left
+        && covered->ImageDesc.Left + covered->ImageDesc.Width <=
+               target->ImageDesc.Left + target->ImageDesc.Width
+        && target->ImageDesc.Top <= covered->ImageDesc.Top
+        && covered->ImageDesc.Top + covered->ImageDesc.Height <=
+               target->ImageDesc.Top + target->ImageDesc.Height) {
+        return true;
+    }
+    return false;
+}
+
+static void disposeFrameIfNeeded(SkBitmap* bm, const SavedImage* cur, const SavedImage* next,
+                                 SkBitmap* backup, SkColor color)
+{
+    // We can skip disposal process if next frame is not transparent
+    // and completely covers current area
+    bool curTrans;
+    int curDisposal;
+    getTransparencyAndDisposalMethod(cur, &curTrans, &curDisposal);
+    bool nextTrans;
+    int nextDisposal;
+    getTransparencyAndDisposalMethod(next, &nextTrans, &nextDisposal);
+    if ((curDisposal == 2 || curDisposal == 3)
+        && (nextTrans || !checkIfCover(next, cur))) {
+        switch (curDisposal) {
+        // restore to background color
+        // -> 'background' means background under this image.
+        case 2:
+            fillRect(bm, cur->ImageDesc.Left, cur->ImageDesc.Top,
+                     cur->ImageDesc.Width, cur->ImageDesc.Height,
+                     color);
+            break;
+
+        // restore to previous
+        case 3:
+            bm->swap(*backup);
+            break;
+        }
+    }
+
+    // Save current image if next frame's disposal method == 3
+    if (nextDisposal == 3) {
+        const uint32_t* src = bm->getAddr32(0, 0);
+        uint32_t* dst = backup->getAddr32(0, 0);
+        int cnt = bm->width() * bm->height();
+        memcpy(dst, src, cnt*sizeof(uint32_t));
+    }
+}
+
 bool SkGIFMovie::onGetBitmap(SkBitmap* bm)
 {
-    GifFileType* gif = fGIF;
+    const GifFileType* gif = fGIF;
     if (NULL == gif)
         return false;
 
-    // should we check for the Image cmap or the global (SColorMap) first? 
-    ColorMapObject* cmap = gif->SColorMap;
-    if (cmap == NULL)
-        cmap = gif->Image.ColorMap;
-
-    if (cmap == NULL || gif->ImageCount < 1 || cmap->ColorCount != (1 << cmap->BitsPerPixel))
-    {
-        SkASSERT(!"bad colortable setup");
+    if (gif->ImageCount < 1) {
         return false;
     }
 
@@ -137,76 +354,79 @@ bool SkGIFMovie::onGetBitmap(SkBitmap* bm)
         return false;
     }
 
-    SavedImage*      gif_image = fCurrSavedImage;
-    SkBitmap::Config config = SkBitmap::kIndex8_Config;
+    // no need to draw
+    if (fLastDrawIndex >= 0 && fLastDrawIndex == fCurrIndex) {
+        return true;
+    }
 
-    SkColorTable* colorTable = SkNEW_ARGS(SkColorTable, (cmap->ColorCount));
-    SkAutoUnref aur(colorTable);
+    int startIndex = fLastDrawIndex + 1;
+    if (fLastDrawIndex < 0 || !bm->readyToDraw()) {
+        // first time
 
-    bm->setConfig(config, width, height, 0);
-    if (!bm->allocPixels(colorTable)) {
-        return false;
-    }
+        startIndex = 0;
 
-    int transparent = -1;
-    for (int i = 0; i < gif_image->ExtensionBlockCount; ++i) {
-      ExtensionBlock* eb = gif_image->ExtensionBlocks + i;
-      if (eb->Function == 0xF9 && 
-          eb->ByteCount == 4) {
-        bool has_transparency = ((eb->Bytes[0] & 1) == 1);
-        if (has_transparency) {
-          transparent = (unsigned char)eb->Bytes[3];
+        // create bitmap
+        bm->setConfig(SkBitmap::kARGB_8888_Config, width, height, 0);
+        if (!bm->allocPixels(NULL)) {
+            return false;
         }
-      }
+        // create bitmap for backup
+        fBackup.setConfig(SkBitmap::kARGB_8888_Config, width, height, 0);
+        if (!fBackup.allocPixels(NULL)) {
+            return false;
+        }
+    } else if (startIndex > fCurrIndex) {
+        // rewind to 1st frame for repeat
+        startIndex = 0;
     }
 
-    SkPMColor* colorPtr = colorTable->lockColors();
+    int lastIndex = fCurrIndex;
+    if (lastIndex < 0) {
+        // first time
+        lastIndex = 0;
+    } else if (lastIndex > fGIF->ImageCount - 1) {
+        // this block must not be reached.
+        lastIndex = fGIF->ImageCount - 1;
+    }
 
-    if (transparent >= 0)
-        memset(colorPtr, 0, cmap->ColorCount * 4);
-    else
-        colorTable->setFlags(colorTable->getFlags() | SkColorTable::kColorsAreOpaque_Flag);
+    SkColor bgColor = SkPackARGB32(0, 0, 0, 0);
+    if (gif->SColorMap != NULL) {
+        const GifColorType& col = gif->SColorMap->Colors[fGIF->SBackGroundColor];
+        bgColor = SkColorSetARGB(0xFF, col.Red, col.Green, col.Blue);
+    }
 
-    for (int index = 0; index < cmap->ColorCount; index++)
-    {
-        if (transparent != index)
-            colorPtr[index] = SkPackARGB32(0xFF, cmap->Colors[index].Red, 
-                cmap->Colors[index].Green, cmap->Colors[index].Blue);
-    }
-    colorTable->unlockColors(true);
-
-    unsigned char* in = (unsigned char*)gif_image->RasterBits;
-    unsigned char* out = bm->getAddr8(0, 0);
-    if (gif->Image.Interlace) {
-
-      // deinterlace
-        int row;
-      // group 1 - every 8th row, starting with row 0
-      for (row = 0; row < height; row += 8) {
-        memcpy(out + width * row, in, width);
-        in += width;
-      }
-
-      // group 2 - every 8th row, starting with row 4
-      for (row = 4; row < height; row += 8) {
-        memcpy(out + width * row, in, width);
-        in += width;
-      }
-
-      // group 3 - every 4th row, starting with row 2
-      for (row = 2; row < height; row += 4) {
-        memcpy(out + width * row, in, width);
-        in += width;
-      }
-
-      for (row = 1; row < height; row += 2) {
-        memcpy(out + width * row, in, width);
-        in += width;
-      }
+    static SkColor paintingColor = SkPackARGB32(0, 0, 0, 0);
+    // draw each frames - not intelligent way
+    for (int i = startIndex; i <= lastIndex; i++) {
+        const SavedImage* cur = &fGIF->SavedImages[i];
+        if (i == 0) {
+            bool trans;
+            int disposal;
+            getTransparencyAndDisposalMethod(cur, &trans, &disposal);
+            if (!trans && gif->SColorMap != NULL) {
+                paintingColor = bgColor;
+            } else {
+                paintingColor = SkColorSetARGB(0, 0, 0, 0);
+            }
+
+            bm->eraseColor(paintingColor);
+            fBackup.eraseColor(paintingColor);
+        } else {
+            // Dispose previous frame before move to next frame.
+            const SavedImage* prev = &fGIF->SavedImages[i-1];
+            disposeFrameIfNeeded(bm, prev, cur, &fBackup, paintingColor);
+        }
 
-    } else {
-      memcpy(out, in, width * height);
+        // Draw frame
+        // We can skip this process if this index is not last and disposal
+        // method == 2 or method == 3
+        if (i == lastIndex || !checkIfWillBeCleared(cur)) {
+            drawFrame(bm, cur, gif->SColorMap);
+        }
     }
+
+    // save index
+    fLastDrawIndex = lastIndex;
     return true;
 }