GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/gif.c Lines: 219 289 75.8 %
Date: 2021-04-20 15:25:36 Branches: 131 218 60.1 %

Line Branch Exec Source
1
/*
2
 * Copyright (c) 2000 Fabrice Bellard
3
 * Copyright (c) 2002 Francois Revol
4
 * Copyright (c) 2006 Baptiste Coudurier
5
 * Copyright (c) 2018 Bjorn Roche
6
 * Copyright (c) 2018 Paul B Mahol
7
 *
8
 * first version by Francois Revol <revol@free.fr>
9
 *
10
 * This file is part of FFmpeg.
11
 *
12
 * FFmpeg is free software; you can redistribute it and/or
13
 * modify it under the terms of the GNU Lesser General Public
14
 * License as published by the Free Software Foundation; either
15
 * version 2.1 of the License, or (at your option) any later version.
16
 *
17
 * FFmpeg is distributed in the hope that it will be useful,
18
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
20
 * Lesser General Public License for more details.
21
 *
22
 * You should have received a copy of the GNU Lesser General Public
23
 * License along with FFmpeg; if not, write to the Free Software
24
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25
 */
26
27
/**
28
 * @file
29
 * GIF encoder
30
 * @see http://www.w3.org/Graphics/GIF/spec-gif89a.txt
31
 */
32
33
#define BITSTREAM_WRITER_LE
34
#include "libavutil/opt.h"
35
#include "libavutil/imgutils.h"
36
#include "avcodec.h"
37
#include "bytestream.h"
38
#include "internal.h"
39
#include "lzw.h"
40
#include "gif.h"
41
42
#include "put_bits.h"
43
44
#define DEFAULT_TRANSPARENCY_INDEX 0x1f
45
46
typedef struct GIFContext {
47
    const AVClass *class;
48
    LZWState *lzw;
49
    uint8_t *buf;
50
    uint8_t *shrunk_buf;
51
    int buf_size;
52
    AVFrame *last_frame;
53
    int flags;
54
    int image;
55
    int use_global_palette;
56
    uint32_t palette[AVPALETTE_COUNT];  ///< local reference palette for !pal8
57
    int palette_loaded;
58
    int transparent_index;
59
    uint8_t *tmpl;                      ///< temporary line buffer
60
} GIFContext;
61
62
enum {
63
    GF_OFFSETTING = 1<<0,
64
    GF_TRANSDIFF  = 1<<1,
65
};
66
67
1
static void shrink_palette(const uint32_t *src, uint8_t *map,
68
                           uint32_t *dst, size_t *palette_count)
69
{
70
1
    size_t colors_seen = 0;
71
72
257
    for (size_t i = 0; i < AVPALETTE_COUNT; i++) {
73
256
        int seen = 0;
74
32896
        for (size_t c = 0; c < colors_seen; c++) {
75
32640
            if (src[i] == dst[c]) {
76
                seen = 1;
77
                break;
78
            }
79
        }
80
256
        if (!seen) {
81
256
            dst[colors_seen] = src[i];
82
256
            map[i] = colors_seen;
83
256
            colors_seen++;
84
        }
85
    }
86
87
1
    *palette_count = colors_seen;
88
1
}
89
90
1
static void remap_frame_to_palette(const uint8_t *src, int src_linesize,
91
                                   uint8_t *dst, int dst_linesize,
92
                                   int w, int h, uint8_t *map)
93
{
94
218
    for (int i = 0; i < h; i++)
95
47306
        for (int j = 0; j < w; j++)
96
47089
            dst[i * dst_linesize + j] = map[src[i * src_linesize + j]];
97
1
}
98
99
1063
static int is_image_translucent(AVCodecContext *avctx,
100
                                const uint8_t *buf, const int linesize)
101
{
102
1063
    GIFContext *s = avctx->priv_data;
103
1063
    int trans = s->transparent_index;
104
105
1063
    if (trans < 0)
106
1063
        return 0;
107
108
    for (int y = 0; y < avctx->height; y++) {
109
        for (int x = 0; x < avctx->width; x++) {
110
            if (buf[x] == trans) {
111
                return 1;
112
            }
113
        }
114
        buf += linesize;
115
    }
116
117
    return 0;
118
}
119
120
39
static int get_palette_transparency_index(const uint32_t *palette)
121
{
122
39
    int transparent_color_index = -1;
123
39
    unsigned i, smallest_alpha = 0xff;
124
125
39
    if (!palette)
126
30
        return -1;
127
128
2313
    for (i = 0; i < AVPALETTE_COUNT; i++) {
129
2304
        const uint32_t v = palette[i];
130
2304
        if (v >> 24 < smallest_alpha) {
131
2
            smallest_alpha = v >> 24;
132
2
            transparent_color_index = i;
133
        }
134
    }
135
9
    return smallest_alpha < 128 ? transparent_color_index : -1;
136
}
137
138
1056
static int pick_palette_entry(const uint8_t *buf, int linesize, int w, int h)
139
{
140
1056
    int histogram[AVPALETTE_COUNT] = {0};
141
    int x, y, i;
142
143
33543
    for (y = 0; y < h; y++) {
144
3190262
        for (x = 0; x < w; x++)
145
3157775
            histogram[buf[x]]++;
146
32487
        buf += linesize;
147
    }
148
7312
    for (i = 0; i < FF_ARRAY_ELEMS(histogram); i++)
149
7288
        if (!histogram[i])
150
1032
            return i;
151
24
    return -1;
152
}
153
154
static void gif_crop_translucent(AVCodecContext *avctx,
155
                                 const uint8_t *buf, const int linesize,
156
                                 int *width, int *height,
157
                                 int *x_start, int *y_start)
158
{
159
    GIFContext *s = avctx->priv_data;
160
    int trans = s->transparent_index;
161
162
    /* Crop image */
163
    if ((s->flags & GF_OFFSETTING) && trans >= 0) {
164
        const int w = avctx->width;
165
        const int h = avctx->height;
166
        int x_end = w - 1,
167
            y_end = h - 1;
168
169
        // crop top
170
        while (*y_start < y_end) {
171
            int is_trans = 1;
172
            for (int i = 0; i < w; i++) {
173
                if (buf[linesize * *y_start + i] != trans) {
174
                    is_trans = 0;
175
                    break;
176
                }
177
            }
178
179
            if (!is_trans)
180
                break;
181
            (*y_start)++;
182
        }
183
184
        // crop bottom
185
        while (y_end > *y_start) {
186
            int is_trans = 1;
187
            for (int i = 0; i < w; i++) {
188
                if (buf[linesize * y_end + i] != trans) {
189
                    is_trans = 0;
190
                    break;
191
                }
192
            }
193
            if (!is_trans)
194
                break;
195
            y_end--;
196
        }
197
198
        // crop left
199
        while (*x_start < x_end) {
200
            int is_trans = 1;
201
            for (int i = *y_start; i < y_end; i++) {
202
                if (buf[linesize * i + *x_start] != trans) {
203
                    is_trans = 0;
204
                    break;
205
                }
206
            }
207
            if (!is_trans)
208
                break;
209
            (*x_start)++;
210
        }
211
212
        // crop right
213
        while (x_end > *x_start) {
214
            int is_trans = 1;
215
            for (int i = *y_start; i < y_end; i++) {
216
                if (buf[linesize * i + x_end] != trans) {
217
                    is_trans = 0;
218
                    break;
219
                }
220
            }
221
            if (!is_trans)
222
                break;
223
            x_end--;
224
        }
225
226
        *height = y_end + 1 - *y_start;
227
        *width  = x_end + 1 - *x_start;
228
        av_log(avctx, AV_LOG_DEBUG,"%dx%d image at pos (%d;%d) [area:%dx%d]\n",
229
               *width, *height, *x_start, *y_start, avctx->width, avctx->height);
230
    }
231
}
232
233
1063
static void gif_crop_opaque(AVCodecContext *avctx,
234
                            const uint32_t *palette,
235
                            const uint8_t *buf, const int linesize,
236
                            int *width, int *height, int *x_start, int *y_start)
237
{
238
1063
    GIFContext *s = avctx->priv_data;
239
240
    /* Crop image */
241

1063
    if ((s->flags & GF_OFFSETTING) && s->last_frame && !palette) {
242
1056
        const uint8_t *ref = s->last_frame->data[0];
243
1056
        const int ref_linesize = s->last_frame->linesize[0];
244
1056
        int x_end = avctx->width  - 1,
245
1056
            y_end = avctx->height - 1;
246
247
        /* skip common lines */
248
100704
        while (*y_start < y_end) {
249
100704
            if (memcmp(ref + *y_start*ref_linesize, buf + *y_start*linesize, *width))
250
1056
                break;
251
99648
            (*y_start)++;
252
        }
253
99777
        while (y_end > *y_start) {
254
99777
            if (memcmp(ref + y_end*ref_linesize, buf + y_end*linesize, *width))
255
1056
                break;
256
98721
            y_end--;
257
        }
258
1056
        *height = y_end + 1 - *y_start;
259
260
        /* skip common columns */
261
96923
        while (*x_start < x_end) {
262
96923
            int same_column = 1;
263
2498501
            for (int y = *y_start; y <= y_end; y++) {
264
2402634
                if (ref[y*ref_linesize + *x_start] != buf[y*linesize + *x_start]) {
265
1056
                    same_column = 0;
266
1056
                    break;
267
                }
268
            }
269
96923
            if (!same_column)
270
1056
                break;
271
95867
            (*x_start)++;
272
        }
273
104460
        while (x_end > *x_start) {
274
104460
            int same_column = 1;
275
2546113
            for (int y = *y_start; y <= y_end; y++) {
276
2442709
                if (ref[y*ref_linesize + x_end] != buf[y*linesize + x_end]) {
277
1056
                    same_column = 0;
278
1056
                    break;
279
                }
280
            }
281
104460
            if (!same_column)
282
1056
                break;
283
103404
            x_end--;
284
        }
285
1056
        *width = x_end + 1 - *x_start;
286
287
1056
        av_log(avctx, AV_LOG_DEBUG,"%dx%d image at pos (%d;%d) [area:%dx%d]\n",
288
               *width, *height, *x_start, *y_start, avctx->width, avctx->height);
289
    }
290
1063
}
291
292
1063
static int gif_image_write_image(AVCodecContext *avctx,
293
                                 uint8_t **bytestream, uint8_t *end,
294
                                 const uint32_t *palette,
295
                                 const uint8_t *buf, const int linesize,
296
                                 AVPacket *pkt)
297
{
298
1063
    GIFContext *s = avctx->priv_data;
299
1063
    int disposal, len = 0, height = avctx->height, width = avctx->width, x, y;
300
1063
    int x_start = 0, y_start = 0, trans = s->transparent_index;
301

1063
    int bcid = -1, honor_transparency = (s->flags & GF_TRANSDIFF) && s->last_frame && !palette;
302
    const uint8_t *ptr;
303
    uint32_t shrunk_palette[AVPALETTE_COUNT];
304
1063
    uint8_t map[AVPALETTE_COUNT] = { 0 };
305
1063
    size_t shrunk_palette_count = 0;
306
307
    /*
308
     * We memset to 0xff instead of 0x00 so that the transparency detection
309
     * doesn't pick anything after the palette entries as the transparency
310
     * index, and because GIF89a requires us to always write a power-of-2
311
     * number of palette entries.
312
     */
313
1063
    memset(shrunk_palette, 0xff, AVPALETTE_SIZE);
314
315

1063
    if (!s->image && is_image_translucent(avctx, buf, linesize)) {
316
        gif_crop_translucent(avctx, buf, linesize, &width, &height, &x_start, &y_start);
317
        honor_transparency = 0;
318
        disposal = GCE_DISPOSAL_BACKGROUND;
319
    } else {
320
1063
        gif_crop_opaque(avctx, palette, buf, linesize, &width, &height, &x_start, &y_start);
321
1063
        disposal = GCE_DISPOSAL_INPLACE;
322
    }
323
324

1063
    if (s->image || !avctx->frame_number) { /* GIF header */
325
7
        const uint32_t *global_palette = palette ? palette : s->palette;
326
7
        const AVRational sar = avctx->sample_aspect_ratio;
327
7
        int64_t aspect = 0;
328
329

7
        if (sar.num > 0 && sar.den > 0) {
330
            aspect = sar.num * 64LL / sar.den - 15;
331
            if (aspect < 0 || aspect > 255)
332
                aspect = 0;
333
        }
334
335
7
        bytestream_put_buffer(bytestream, gif89a_sig, sizeof(gif89a_sig));
336
7
        bytestream_put_le16(bytestream, avctx->width);
337
7
        bytestream_put_le16(bytestream, avctx->height);
338
339
7
        bcid = get_palette_transparency_index(global_palette);
340
341
7
        bytestream_put_byte(bytestream, ((uint8_t) s->use_global_palette << 7) | 0x70 | (s->use_global_palette ? 7 : 0)); /* flags: global clut, 256 entries */
342
7
        bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : bcid); /* background color index */
343
7
        bytestream_put_byte(bytestream, aspect);
344
7
        if (s->use_global_palette) {
345
1799
            for (int i = 0; i < 256; i++) {
346
1792
                const uint32_t v = global_palette[i] & 0xffffff;
347
1792
                bytestream_put_be24(bytestream, v);
348
            }
349
        }
350
    }
351
352

1063
    if (honor_transparency && trans < 0) {
353
1056
        trans = pick_palette_entry(buf + y_start*linesize + x_start,
354
                                   linesize, width, height);
355
1056
        if (trans < 0) // TODO, patch welcome
356
24
            av_log(avctx, AV_LOG_DEBUG, "No available color, can not use transparency\n");
357
    }
358
359
1063
    if (trans < 0)
360
31
        honor_transparency = 0;
361
362

1063
    if (palette || !s->use_global_palette) {
363
1
        const uint32_t *pal = palette ? palette : s->palette;
364
1
        shrink_palette(pal, map, shrunk_palette, &shrunk_palette_count);
365
    }
366
367

1063
    bcid = honor_transparency || disposal == GCE_DISPOSAL_BACKGROUND ? trans : get_palette_transparency_index(palette);
368
369
    /* graphic control extension */
370
1063
    bytestream_put_byte(bytestream, GIF_EXTENSION_INTRODUCER);
371
1063
    bytestream_put_byte(bytestream, GIF_GCE_EXT_LABEL);
372
1063
    bytestream_put_byte(bytestream, 0x04); /* block size */
373
1063
    bytestream_put_byte(bytestream, disposal<<2 | (bcid >= 0));
374
1063
    bytestream_put_le16(bytestream, 5); // default delay
375

1063
    bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : (shrunk_palette_count ? map[bcid] : bcid));
376
1063
    bytestream_put_byte(bytestream, 0x00);
377
378
    /* image block */
379
1063
    bytestream_put_byte(bytestream, GIF_IMAGE_SEPARATOR);
380
1063
    bytestream_put_le16(bytestream, x_start);
381
1063
    bytestream_put_le16(bytestream, y_start);
382
1063
    bytestream_put_le16(bytestream, width);
383
1063
    bytestream_put_le16(bytestream, height);
384
385

1064
    if (palette || !s->use_global_palette) {
386
1
        unsigned pow2_count = av_log2(shrunk_palette_count - 1);
387
        unsigned i;
388
389
1
        bytestream_put_byte(bytestream, 1<<7 | pow2_count); /* flags */
390
257
        for (i = 0; i < 1 << (pow2_count + 1); i++) {
391
256
            const uint32_t v = shrunk_palette[i];
392
256
            bytestream_put_be24(bytestream, v);
393
        }
394
    } else {
395
1062
        bytestream_put_byte(bytestream, 0x00); /* flags */
396
    }
397
398
1063
    bytestream_put_byte(bytestream, 0x08);
399
400
1063
    ff_lzw_encode_init(s->lzw, s->buf, s->buf_size,
401
                       12, FF_LZW_GIF, 1);
402
403
1063
    if (shrunk_palette_count) {
404
1
        if (!s->shrunk_buf) {
405
1
            s->shrunk_buf = av_malloc(avctx->height * linesize);
406
1
            if (!s->shrunk_buf) {
407
                av_log(avctx, AV_LOG_ERROR, "Could not allocated remapped frame buffer.\n");
408
                return AVERROR(ENOMEM);
409
            }
410
        }
411
1
        remap_frame_to_palette(buf, linesize, s->shrunk_buf, linesize, avctx->width, avctx->height, map);
412
1
        ptr = s->shrunk_buf + y_start*linesize + x_start;
413
    } else {
414
1062
        ptr = buf + y_start*linesize + x_start;
415
    }
416
1063
    if (honor_transparency) {
417
1032
        const int ref_linesize = s->last_frame->linesize[0];
418
1032
        const uint8_t *ref = s->last_frame->data[0] + y_start*ref_linesize + x_start;
419
420
26607
        for (y = 0; y < height; y++) {
421
25575
            memcpy(s->tmpl, ptr, width);
422
750326
            for (x = 0; x < width; x++)
423
724751
                if (ref[x] == ptr[x])
424
367271
                    s->tmpl[x] = trans;
425
25575
            len += ff_lzw_encode(s->lzw, s->tmpl, width);
426
25575
            ptr += linesize;
427
25575
            ref += ref_linesize;
428
        }
429
    } else {
430
8533
        for (y = 0; y < height; y++) {
431
8502
            len += ff_lzw_encode(s->lzw, ptr, width);
432
8502
            ptr += linesize;
433
        }
434
    }
435
1063
    len += ff_lzw_encode_flush(s->lzw);
436
437
1063
    ptr = s->buf;
438
10314
    while (len > 0) {
439
9251
        int size = FFMIN(255, len);
440
9251
        bytestream_put_byte(bytestream, size);
441
9251
        if (end - *bytestream < size)
442
            return -1;
443
9251
        bytestream_put_buffer(bytestream, ptr, size);
444
9251
        ptr += size;
445
9251
        len -= size;
446
    }
447
1063
    bytestream_put_byte(bytestream, 0x00); /* end of image block */
448
1063
    return 0;
449
}
450
451
7
static av_cold int gif_encode_init(AVCodecContext *avctx)
452
{
453
7
    GIFContext *s = avctx->priv_data;
454
455

7
    if (avctx->width > 65535 || avctx->height > 65535) {
456
        av_log(avctx, AV_LOG_ERROR, "GIF does not support resolutions above 65535x65535\n");
457
        return AVERROR(EINVAL);
458
    }
459
460
7
    s->transparent_index = -1;
461
462
7
    s->lzw = av_mallocz(ff_lzw_encode_state_size);
463
7
    s->buf_size = avctx->width*avctx->height*2 + 1000;
464
7
    s->buf = av_malloc(s->buf_size);
465
7
    s->tmpl = av_malloc(avctx->width);
466

7
    if (!s->tmpl || !s->buf || !s->lzw)
467
        return AVERROR(ENOMEM);
468
469
7
    if (avpriv_set_systematic_pal2(s->palette, avctx->pix_fmt) < 0)
470
1
        av_assert0(avctx->pix_fmt == AV_PIX_FMT_PAL8);
471
472
7
    return 0;
473
}
474
475
1063
static int gif_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
476
                            const AVFrame *pict, int *got_packet)
477
{
478
1063
    GIFContext *s = avctx->priv_data;
479
    uint8_t *outbuf_ptr, *end;
480
1063
    const uint32_t *palette = NULL;
481
    int ret;
482
483
1063
    if ((ret = ff_alloc_packet2(avctx, pkt, avctx->width*avctx->height*7/5 + AV_INPUT_BUFFER_MIN_SIZE, 0)) < 0)
484
        return ret;
485
1063
    outbuf_ptr = pkt->data;
486
1063
    end        = pkt->data + pkt->size;
487
488
1063
    if (avctx->pix_fmt == AV_PIX_FMT_PAL8) {
489
173
        palette = (uint32_t*)pict->data[1];
490
491
173
        if (!s->palette_loaded) {
492
1
            memcpy(s->palette, palette, AVPALETTE_SIZE);
493
1
            s->transparent_index = get_palette_transparency_index(palette);
494
1
            s->palette_loaded = 1;
495
172
        } else if (!memcmp(s->palette, palette, AVPALETTE_SIZE)) {
496
172
            palette = NULL;
497
        }
498
    }
499
500
1063
    gif_image_write_image(avctx, &outbuf_ptr, end, palette,
501
1063
                          pict->data[0], pict->linesize[0], pkt);
502

1063
    if (!s->last_frame && !s->image) {
503
7
        s->last_frame = av_frame_alloc();
504
7
        if (!s->last_frame)
505
            return AVERROR(ENOMEM);
506
    }
507
508
1063
    if (!s->image) {
509
1063
        av_frame_unref(s->last_frame);
510
1063
        ret = av_frame_ref(s->last_frame, (AVFrame*)pict);
511
1063
        if (ret < 0)
512
            return ret;
513
    }
514
515
1063
    pkt->size   = outbuf_ptr - pkt->data;
516

1063
    if (s->image || !avctx->frame_number)
517
7
        pkt->flags |= AV_PKT_FLAG_KEY;
518
1063
    *got_packet = 1;
519
520
1063
    return 0;
521
}
522
523
7
static int gif_encode_close(AVCodecContext *avctx)
524
{
525
7
    GIFContext *s = avctx->priv_data;
526
527
7
    av_freep(&s->lzw);
528
7
    av_freep(&s->buf);
529
7
    av_freep(&s->shrunk_buf);
530
7
    s->buf_size = 0;
531
7
    av_frame_free(&s->last_frame);
532
7
    av_freep(&s->tmpl);
533
7
    return 0;
534
}
535
536
#define OFFSET(x) offsetof(GIFContext, x)
537
#define FLAGS AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM
538
static const AVOption gif_options[] = {
539
    { "gifflags", "set GIF flags", OFFSET(flags), AV_OPT_TYPE_FLAGS, {.i64 = GF_OFFSETTING|GF_TRANSDIFF}, 0, INT_MAX, FLAGS, "flags" },
540
        { "offsetting", "enable picture offsetting", 0, AV_OPT_TYPE_CONST, {.i64=GF_OFFSETTING}, INT_MIN, INT_MAX, FLAGS, "flags" },
541
        { "transdiff", "enable transparency detection between frames", 0, AV_OPT_TYPE_CONST, {.i64=GF_TRANSDIFF}, INT_MIN, INT_MAX, FLAGS, "flags" },
542
    { "gifimage", "enable encoding only images per frame", OFFSET(image), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
543
    { "global_palette", "write a palette to the global gif header where feasible", OFFSET(use_global_palette), AV_OPT_TYPE_BOOL, {.i64=1}, 0, 1, FLAGS },
544
    { NULL }
545
};
546
547
static const AVClass gif_class = {
548
    .class_name = "GIF encoder",
549
    .item_name  = av_default_item_name,
550
    .option     = gif_options,
551
    .version    = LIBAVUTIL_VERSION_INT,
552
};
553
554
AVCodec ff_gif_encoder = {
555
    .name           = "gif",
556
    .long_name      = NULL_IF_CONFIG_SMALL("GIF (Graphics Interchange Format)"),
557
    .type           = AVMEDIA_TYPE_VIDEO,
558
    .id             = AV_CODEC_ID_GIF,
559
    .priv_data_size = sizeof(GIFContext),
560
    .init           = gif_encode_init,
561
    .encode2        = gif_encode_frame,
562
    .close          = gif_encode_close,
563
    .pix_fmts       = (const enum AVPixelFormat[]){
564
        AV_PIX_FMT_RGB8, AV_PIX_FMT_BGR8, AV_PIX_FMT_RGB4_BYTE, AV_PIX_FMT_BGR4_BYTE,
565
        AV_PIX_FMT_GRAY8, AV_PIX_FMT_PAL8, AV_PIX_FMT_NONE
566
    },
567
    .priv_class     = &gif_class,
568
    .caps_internal  = FF_CODEC_CAP_INIT_CLEANUP,
569
};