1/*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkColor.h"
9#include "SkColorPriv.h"
10#include "SkColorTable.h"
11#include "SkImageDecoder.h"
12#include "SkRTConf.h"
13#include "SkScaledBitmapSampler.h"
14#include "SkStream.h"
15#include "SkTemplates.h"
16#include "SkUtils.h"
17
18#include "gif_lib.h"
19
20class SkGIFImageDecoder : public SkImageDecoder {
21public:
22    virtual Format getFormat() const SK_OVERRIDE {
23        return kGIF_Format;
24    }
25
26protected:
27    virtual Result onDecode(SkStream* stream, SkBitmap* bm, Mode mode) SK_OVERRIDE;
28
29private:
30    typedef SkImageDecoder INHERITED;
31};
32
33static const uint8_t gStartingIterlaceYValue[] = {
34    0, 4, 2, 1
35};
36static const uint8_t gDeltaIterlaceYValue[] = {
37    8, 8, 4, 2
38};
39
40SK_CONF_DECLARE(bool, c_suppressGIFImageDecoderWarnings,
41                "images.gif.suppressDecoderWarnings", true,
42                "Suppress GIF warnings and errors when calling image decode "
43                "functions.");
44
45
46/*  Implement the GIF interlace algorithm in an iterator.
47    1) grab every 8th line beginning at 0
48    2) grab every 8th line beginning at 4
49    3) grab every 4th line beginning at 2
50    4) grab every 2nd line beginning at 1
51*/
52class GifInterlaceIter {
53public:
54    GifInterlaceIter(int height) : fHeight(height) {
55        fStartYPtr = gStartingIterlaceYValue;
56        fDeltaYPtr = gDeltaIterlaceYValue;
57
58        fCurrY = *fStartYPtr++;
59        fDeltaY = *fDeltaYPtr++;
60    }
61
62    int currY() const {
63        SkASSERT(fStartYPtr);
64        SkASSERT(fDeltaYPtr);
65        return fCurrY;
66    }
67
68    void next() {
69        SkASSERT(fStartYPtr);
70        SkASSERT(fDeltaYPtr);
71
72        int y = fCurrY + fDeltaY;
73        // We went from an if statement to a while loop so that we iterate
74        // through fStartYPtr until a valid row is found. This is so that images
75        // that are smaller than 5x5 will not trash memory.
76        while (y >= fHeight) {
77            if (gStartingIterlaceYValue +
78                    SK_ARRAY_COUNT(gStartingIterlaceYValue) == fStartYPtr) {
79                // we done
80                SkDEBUGCODE(fStartYPtr = NULL;)
81                SkDEBUGCODE(fDeltaYPtr = NULL;)
82                y = 0;
83            } else {
84                y = *fStartYPtr++;
85                fDeltaY = *fDeltaYPtr++;
86            }
87        }
88        fCurrY = y;
89    }
90
91private:
92    const int fHeight;
93    int fCurrY;
94    int fDeltaY;
95    const uint8_t* fStartYPtr;
96    const uint8_t* fDeltaYPtr;
97};
98
99///////////////////////////////////////////////////////////////////////////////
100
101static int DecodeCallBackProc(GifFileType* fileType, GifByteType* out,
102                              int size) {
103    SkStream* stream = (SkStream*) fileType->UserData;
104    return (int) stream->read(out, size);
105}
106
107void CheckFreeExtension(SavedImage* Image) {
108    if (Image->ExtensionBlocks) {
109#if GIFLIB_MAJOR < 5
110        FreeExtension(Image);
111#else
112        GifFreeExtensions(&Image->ExtensionBlockCount, &Image->ExtensionBlocks);
113#endif
114    }
115}
116
117// return NULL on failure
118static const ColorMapObject* find_colormap(const GifFileType* gif) {
119    const ColorMapObject* cmap = gif->Image.ColorMap;
120    if (NULL == cmap) {
121        cmap = gif->SColorMap;
122    }
123
124    if (NULL == cmap) {
125        // no colormap found
126        return NULL;
127    }
128    // some sanity checks
129    if (cmap && ((unsigned)cmap->ColorCount > 256 ||
130                 cmap->ColorCount != (1 << cmap->BitsPerPixel))) {
131        cmap = NULL;
132    }
133    return cmap;
134}
135
136// return -1 if not found (i.e. we're completely opaque)
137static int find_transpIndex(const SavedImage& image, int colorCount) {
138    int transpIndex = -1;
139    for (int i = 0; i < image.ExtensionBlockCount; ++i) {
140        const ExtensionBlock* eb = image.ExtensionBlocks + i;
141        if (eb->Function == 0xF9 && eb->ByteCount == 4) {
142            if (eb->Bytes[0] & 1) {
143                transpIndex = (unsigned char)eb->Bytes[3];
144                // check for valid transpIndex
145                if (transpIndex >= colorCount) {
146                    transpIndex = -1;
147                }
148                break;
149            }
150        }
151    }
152    return transpIndex;
153}
154
155static SkImageDecoder::Result error_return(const SkBitmap& bm, const char msg[]) {
156    if (!c_suppressGIFImageDecoderWarnings) {
157        SkDebugf("libgif error [%s] bitmap [%d %d] pixels %p colortable %p\n",
158                 msg, bm.width(), bm.height(), bm.getPixels(),
159                 bm.getColorTable());
160    }
161    return SkImageDecoder::kFailure;
162}
163
164static void gif_warning(const SkBitmap& bm, const char msg[]) {
165    if (!c_suppressGIFImageDecoderWarnings) {
166        SkDebugf("libgif warning [%s] bitmap [%d %d] pixels %p colortable %p\n",
167                 msg, bm.width(), bm.height(), bm.getPixels(),
168                 bm.getColorTable());
169    }
170}
171
172/**
173 *  Skip rows in the source gif image.
174 *  @param gif Source image.
175 *  @param dst Scratch output needed by gif library call. Must be >= width bytes.
176 *  @param width Bytes per row in the source image.
177 *  @param rowsToSkip Number of rows to skip.
178 *  @return True on success, false on GIF_ERROR.
179 */
180static bool skip_src_rows(GifFileType* gif, uint8_t* dst, int width, int rowsToSkip) {
181    for (int i = 0; i < rowsToSkip; i++) {
182        if (DGifGetLine(gif, dst, width) == GIF_ERROR) {
183            return false;
184        }
185    }
186    return true;
187}
188
189/**
190 *  GIFs with fewer then 256 color entries will sometimes index out of
191 *  bounds of the color table (this is malformed, but libgif does not
192 *  check sicne it is rare).  This function checks for this error and
193 *  fixes it.  This makes the output image consistantly deterministic.
194 */
195static void sanitize_indexed_bitmap(SkBitmap* bm) {
196    if ((kIndex_8_SkColorType == bm->colorType()) && !(bm->empty())) {
197        SkAutoLockPixels alp(*bm);
198        if (NULL != bm->getPixels()) {
199            SkColorTable* ct = bm->getColorTable();  // Index8 must have it.
200            SkASSERT(ct != NULL);
201            uint32_t count = ct->count();
202            SkASSERT(count > 0);
203            SkASSERT(count <= 0x100);
204            if (count != 0x100) {  // Full colortables can't go wrong.
205                // Count is a power of 2; asserted elsewhere.
206                uint8_t byteMask = (~(count - 1));
207                bool warning = false;
208                uint8_t* addr = static_cast<uint8_t*>(bm->getPixels());
209                int height = bm->height();
210                int width = bm->width();
211                size_t rowBytes = bm->rowBytes();
212                while (--height >= 0) {
213                    uint8_t* ptr = addr;
214                    int x = width;
215                    while (--x >= 0) {
216                        if (0 != ((*ptr) & byteMask)) {
217                            warning = true;
218                            *ptr = 0;
219                        }
220                        ++ptr;
221                    }
222                    addr += rowBytes;
223                }
224                if (warning) {
225                    gif_warning(*bm, "Index out of bounds.");
226                }
227            }
228        }
229    }
230}
231
232SkImageDecoder::Result SkGIFImageDecoder::onDecode(SkStream* sk_stream, SkBitmap* bm, Mode mode) {
233#if GIFLIB_MAJOR < 5
234    GifFileType* gif = DGifOpen(sk_stream, DecodeCallBackProc);
235#else
236    GifFileType* gif = DGifOpen(sk_stream, DecodeCallBackProc, NULL);
237#endif
238    if (NULL == gif) {
239        return error_return(*bm, "DGifOpen");
240    }
241
242    SkAutoTCallIProc<GifFileType, DGifCloseFile> acp(gif);
243
244    SavedImage temp_save;
245    temp_save.ExtensionBlocks=NULL;
246    temp_save.ExtensionBlockCount=0;
247    SkAutoTCallVProc<SavedImage, CheckFreeExtension> acp2(&temp_save);
248
249    int width, height;
250    GifRecordType recType;
251    GifByteType *extData;
252#if GIFLIB_MAJOR >= 5
253    int extFunction;
254#endif
255    int transpIndex = -1;   // -1 means we don't have it (yet)
256    int fillIndex = gif->SBackGroundColor;
257
258    do {
259        if (DGifGetRecordType(gif, &recType) == GIF_ERROR) {
260            return error_return(*bm, "DGifGetRecordType");
261        }
262
263        switch (recType) {
264        case IMAGE_DESC_RECORD_TYPE: {
265            if (DGifGetImageDesc(gif) == GIF_ERROR) {
266                return error_return(*bm, "IMAGE_DESC_RECORD_TYPE");
267            }
268
269            if (gif->ImageCount < 1) {    // sanity check
270                return error_return(*bm, "ImageCount < 1");
271            }
272
273            width = gif->SWidth;
274            height = gif->SHeight;
275
276            SavedImage* image = &gif->SavedImages[gif->ImageCount-1];
277            const GifImageDesc& desc = image->ImageDesc;
278
279            int imageLeft = desc.Left;
280            int imageTop = desc.Top;
281            const int innerWidth = desc.Width;
282            const int innerHeight = desc.Height;
283            if (innerWidth <= 0 || innerHeight <= 0) {
284                return error_return(*bm, "invalid dimensions");
285            }
286
287            // check for valid descriptor
288            if (innerWidth > width) {
289                gif_warning(*bm, "image too wide, expanding output to size");
290                width = innerWidth;
291                imageLeft = 0;
292            } else if (imageLeft + innerWidth > width) {
293                gif_warning(*bm, "shifting image left to fit");
294                imageLeft = width - innerWidth;
295            } else if (imageLeft < 0) {
296                gif_warning(*bm, "shifting image right to fit");
297                imageLeft = 0;
298            }
299
300
301            if (innerHeight > height) {
302                gif_warning(*bm, "image too tall,  expanding output to size");
303                height = innerHeight;
304                imageTop = 0;
305            } else if (imageTop + innerHeight > height) {
306                gif_warning(*bm, "shifting image up to fit");
307                imageTop = height - innerHeight;
308            } else if (imageTop < 0) {
309                gif_warning(*bm, "shifting image down to fit");
310                imageTop = 0;
311            }
312
313#ifdef SK_SUPPORT_LEGACY_IMAGEDECODER_CHOOSER
314            // FIXME: We could give the caller a choice of images or configs.
315            if (!this->chooseFromOneChoice(kIndex_8_SkColorType, width, height)) {
316                return error_return(*bm, "chooseFromOneChoice");
317            }
318#endif
319
320            SkScaledBitmapSampler sampler(width, height, this->getSampleSize());
321
322            bm->setInfo(SkImageInfo::Make(sampler.scaledWidth(), sampler.scaledHeight(),
323                                          kIndex_8_SkColorType, kPremul_SkAlphaType));
324
325            if (SkImageDecoder::kDecodeBounds_Mode == mode) {
326                return kSuccess;
327            }
328
329
330            // now we decode the colortable
331            int colorCount = 0;
332            {
333                // Declare colorPtr here for scope.
334                SkPMColor colorPtr[256]; // storage for worst-case
335                const ColorMapObject* cmap = find_colormap(gif);
336                SkAlphaType alphaType = kOpaque_SkAlphaType;
337                if (cmap != NULL) {
338                    SkASSERT(cmap->ColorCount == (1 << (cmap->BitsPerPixel)));
339                    colorCount = cmap->ColorCount;
340                    if (colorCount > 256) {
341                        colorCount = 256;  // our kIndex8 can't support more
342                    }
343                    for (int index = 0; index < colorCount; index++) {
344                        colorPtr[index] = SkPackARGB32(0xFF,
345                                                       cmap->Colors[index].Red,
346                                                       cmap->Colors[index].Green,
347                                                       cmap->Colors[index].Blue);
348                    }
349                } else {
350                    // find_colormap() returned NULL.  Some (rare, broken)
351                    // GIFs don't have a color table, so we force one.
352                    gif_warning(*bm, "missing colormap");
353                    colorCount = 256;
354                    sk_memset32(colorPtr, SK_ColorWHITE, colorCount);
355                }
356                transpIndex = find_transpIndex(temp_save, colorCount);
357                if (transpIndex >= 0) {
358                    colorPtr[transpIndex] = SK_ColorTRANSPARENT; // ram in a transparent SkPMColor
359                    alphaType = kPremul_SkAlphaType;
360                    fillIndex = transpIndex;
361                } else if (fillIndex >= colorCount) {
362                    // gif->SBackGroundColor should be less than colorCount.
363                    fillIndex = 0;  // If not, fix it.
364                }
365
366                SkAutoTUnref<SkColorTable> ctable(SkNEW_ARGS(SkColorTable,
367                                                  (colorPtr, colorCount,
368                                                   alphaType)));
369                if (!this->allocPixelRef(bm, ctable)) {
370                    return error_return(*bm, "allocPixelRef");
371                }
372            }
373
374            // abort if either inner dimension is <= 0
375            if (innerWidth <= 0 || innerHeight <= 0) {
376                return error_return(*bm, "non-pos inner width/height");
377            }
378
379            SkAutoLockPixels alp(*bm);
380
381            SkAutoMalloc storage(innerWidth);
382            uint8_t* scanline = (uint8_t*) storage.get();
383
384            // GIF has an option to store the scanlines of an image, plus a larger background,
385            // filled by a fill color. In this case, we will use a subset of the larger bitmap
386            // for sampling.
387            SkBitmap subset;
388            SkBitmap* workingBitmap;
389            // are we only a subset of the total bounds?
390            if ((imageTop | imageLeft) > 0 ||
391                 innerWidth < width || innerHeight < height) {
392                // Fill the background.
393                memset(bm->getPixels(), fillIndex, bm->getSize());
394
395                // Create a subset of the bitmap.
396                SkIRect subsetRect(SkIRect::MakeXYWH(imageLeft / sampler.srcDX(),
397                                                     imageTop / sampler.srcDY(),
398                                                     innerWidth / sampler.srcDX(),
399                                                     innerHeight / sampler.srcDY()));
400                if (!bm->extractSubset(&subset, subsetRect)) {
401                    return error_return(*bm, "Extract failed.");
402                }
403                // Update the sampler. We'll now be only sampling into the subset.
404                sampler = SkScaledBitmapSampler(innerWidth, innerHeight, this->getSampleSize());
405                workingBitmap = &subset;
406            } else {
407                workingBitmap = bm;
408            }
409
410            // bm is already locked, but if we had to take a subset, it must be locked also,
411            // so that getPixels() will point to its pixels.
412            SkAutoLockPixels alpWorking(*workingBitmap);
413
414            if (!sampler.begin(workingBitmap, SkScaledBitmapSampler::kIndex, *this)) {
415                return error_return(*bm, "Sampler failed to begin.");
416            }
417
418            // now decode each scanline
419            if (gif->Image.Interlace) {
420                // Iterate over the height of the source data. The sampler will
421                // take care of skipping unneeded rows.
422                GifInterlaceIter iter(innerHeight);
423                for (int y = 0; y < innerHeight; y++) {
424                    if (DGifGetLine(gif, scanline, innerWidth) == GIF_ERROR) {
425                        gif_warning(*bm, "interlace DGifGetLine");
426                        memset(scanline, fillIndex, innerWidth);
427                        for (; y < innerHeight; y++) {
428                            sampler.sampleInterlaced(scanline, iter.currY());
429                            iter.next();
430                        }
431                        return kPartialSuccess;
432                    }
433                    sampler.sampleInterlaced(scanline, iter.currY());
434                    iter.next();
435                }
436            } else {
437                // easy, non-interlace case
438                const int outHeight = workingBitmap->height();
439                skip_src_rows(gif, scanline, innerWidth, sampler.srcY0());
440                for (int y = 0; y < outHeight; y++) {
441                    if (DGifGetLine(gif, scanline, innerWidth) == GIF_ERROR) {
442                        gif_warning(*bm, "DGifGetLine");
443                        memset(scanline, fillIndex, innerWidth);
444                        for (; y < outHeight; y++) {
445                            sampler.next(scanline);
446                        }
447                        return kPartialSuccess;
448                    }
449                    // scanline now contains the raw data. Sample it.
450                    sampler.next(scanline);
451                    if (y < outHeight - 1) {
452                        skip_src_rows(gif, scanline, innerWidth, sampler.srcDY() - 1);
453                    }
454                }
455                // skip the rest of the rows (if any)
456                int read = (outHeight - 1) * sampler.srcDY() + sampler.srcY0() + 1;
457                SkASSERT(read <= innerHeight);
458                skip_src_rows(gif, scanline, innerWidth, innerHeight - read);
459            }
460            sanitize_indexed_bitmap(bm);
461            return kSuccess;
462            } break;
463
464        case EXTENSION_RECORD_TYPE:
465#if GIFLIB_MAJOR < 5
466            if (DGifGetExtension(gif, &temp_save.Function,
467                                 &extData) == GIF_ERROR) {
468#else
469            if (DGifGetExtension(gif, &extFunction, &extData) == GIF_ERROR) {
470#endif
471                return error_return(*bm, "DGifGetExtension");
472            }
473
474            while (extData != NULL) {
475                /* Create an extension block with our data */
476#if GIFLIB_MAJOR < 5
477                if (AddExtensionBlock(&temp_save, extData[0],
478                                      &extData[1]) == GIF_ERROR) {
479#else
480                if (GifAddExtensionBlock(&gif->ExtensionBlockCount,
481                                         &gif->ExtensionBlocks,
482                                         extFunction,
483                                         extData[0],
484                                         &extData[1]) == GIF_ERROR) {
485#endif
486                    return error_return(*bm, "AddExtensionBlock");
487                }
488                if (DGifGetExtensionNext(gif, &extData) == GIF_ERROR) {
489                    return error_return(*bm, "DGifGetExtensionNext");
490                }
491#if GIFLIB_MAJOR < 5
492                temp_save.Function = 0;
493#endif
494            }
495            break;
496
497        case TERMINATE_RECORD_TYPE:
498            break;
499
500        default:    /* Should be trapped by DGifGetRecordType */
501            break;
502        }
503    } while (recType != TERMINATE_RECORD_TYPE);
504
505    sanitize_indexed_bitmap(bm);
506    return kSuccess;
507}
508
509///////////////////////////////////////////////////////////////////////////////
510DEFINE_DECODER_CREATOR(GIFImageDecoder);
511///////////////////////////////////////////////////////////////////////////////
512
513static bool is_gif(SkStreamRewindable* stream) {
514    char buf[GIF_STAMP_LEN];
515    if (stream->read(buf, GIF_STAMP_LEN) == GIF_STAMP_LEN) {
516        if (memcmp(GIF_STAMP,   buf, GIF_STAMP_LEN) == 0 ||
517                memcmp(GIF87_STAMP, buf, GIF_STAMP_LEN) == 0 ||
518                memcmp(GIF89_STAMP, buf, GIF_STAMP_LEN) == 0) {
519            return true;
520        }
521    }
522    return false;
523}
524
525static SkImageDecoder* sk_libgif_dfactory(SkStreamRewindable* stream) {
526    if (is_gif(stream)) {
527        return SkNEW(SkGIFImageDecoder);
528    }
529    return NULL;
530}
531
532static SkImageDecoder_DecodeReg gReg(sk_libgif_dfactory);
533
534static SkImageDecoder::Format get_format_gif(SkStreamRewindable* stream) {
535    if (is_gif(stream)) {
536        return SkImageDecoder::kGIF_Format;
537    }
538    return SkImageDecoder::kUnknown_Format;
539}
540
541static SkImageDecoder_FormatReg gFormatReg(get_format_gif);
542