gif.c 15.8 KB
Newer Older
1
/*
2 3 4
 * Copyright (c) 2000 Fabrice Bellard
 * Copyright (c) 2002 Francois Revol
 * Copyright (c) 2006 Baptiste Coudurier
5 6
 * Copyright (c) 2018 Bjorn Roche
 * Copyright (c) 2018 Paul B Mahol
7
 *
8 9
 * first version by Francois Revol <revol@free.fr>
 *
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

27 28 29 30
/**
 * @file
 * GIF encoder
 * @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 37
#include "avcodec.h"
#include "bytestream.h"
38
#include "internal.h"
39
#include "lzw.h"
40
#include "gif.h"
41

42
#include "put_bits.h"
43

44 45
#define DEFAULT_TRANSPARENCY_INDEX 0x1f

46
typedef struct GIFContext {
47
    const AVClass *class;
48 49
    LZWState *lzw;
    uint8_t *buf;
50
    int buf_size;
51
    AVFrame *last_frame;
52
    int flags;
53
    int image;
54
    uint32_t palette[AVPALETTE_COUNT];  ///< local reference palette for !pal8
55 56
    int palette_loaded;
    int transparent_index;
57
    uint8_t *tmpl;                      ///< temporary line buffer
58 59
} GIFContext;

60 61
enum {
    GF_OFFSETTING = 1<<0,
62
    GF_TRANSDIFF  = 1<<1,
63 64
};

65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
static int is_image_translucent(AVCodecContext *avctx,
                                const uint8_t *buf, const int linesize)
{
    GIFContext *s = avctx->priv_data;
    int trans = s->transparent_index;

    if (trans < 0)
        return 0;

    for (int y = 0; y < avctx->height; y++) {
        for (int x = 0; x < avctx->width; x++) {
            if (buf[x] == trans) {
                return 1;
            }
        }
        buf += linesize;
    }

    return 0;
}

86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
static int get_palette_transparency_index(const uint32_t *palette)
{
    int transparent_color_index = -1;
    unsigned i, smallest_alpha = 0xff;

    if (!palette)
        return -1;

    for (i = 0; i < AVPALETTE_COUNT; i++) {
        const uint32_t v = palette[i];
        if (v >> 24 < smallest_alpha) {
            smallest_alpha = v >> 24;
            transparent_color_index = i;
        }
    }
    return smallest_alpha < 128 ? transparent_color_index : -1;
}

104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
static int pick_palette_entry(const uint8_t *buf, int linesize, int w, int h)
{
    int histogram[AVPALETTE_COUNT] = {0};
    int x, y, i;

    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++)
            histogram[buf[x]]++;
        buf += linesize;
    }
    for (i = 0; i < FF_ARRAY_ELEMS(histogram); i++)
        if (!histogram[i])
            return i;
    return -1;
}

120
static void gif_crop_translucent(AVCodecContext *avctx,
121
                                 const uint8_t *buf, const int linesize,
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
                                 int *width, int *height,
                                 int *x_start, int *y_start)
{
    GIFContext *s = avctx->priv_data;
    int trans = s->transparent_index;

    /* Crop image */
    if ((s->flags & GF_OFFSETTING) && trans >= 0) {
        const int w = avctx->width;
        const int h = avctx->height;
        int x_end = w - 1,
            y_end = h - 1;

        // crop top
        while (*y_start < y_end) {
            int is_trans = 1;
            for (int i = 0; i < w; i++) {
139
                if (buf[linesize * *y_start + i] != trans) {
140 141 142 143 144 145 146 147 148 149 150
                    is_trans = 0;
                    break;
                }
            }

            if (!is_trans)
                break;
            (*y_start)++;
        }

        // crop bottom
151
        while (y_end > *y_start) {
152 153
            int is_trans = 1;
            for (int i = 0; i < w; i++) {
154
                if (buf[linesize * y_end + i] != trans) {
155 156 157 158 159 160 161 162 163 164 165 166 167
                    is_trans = 0;
                    break;
                }
            }
            if (!is_trans)
                break;
            y_end--;
        }

        // crop left
        while (*x_start < x_end) {
            int is_trans = 1;
            for (int i = *y_start; i < y_end; i++) {
168
                if (buf[linesize * i + *x_start] != trans) {
169 170 171 172 173 174 175 176 177 178
                    is_trans = 0;
                    break;
                }
            }
            if (!is_trans)
                break;
            (*x_start)++;
        }

        // crop right
179
        while (x_end > *x_start) {
180 181
            int is_trans = 1;
            for (int i = *y_start; i < y_end; i++) {
182
                if (buf[linesize * i + x_end] != trans) {
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
                    is_trans = 0;
                    break;
                }
            }
            if (!is_trans)
                break;
            x_end--;
        }

        *height = y_end + 1 - *y_start;
        *width  = x_end + 1 - *x_start;
        av_log(avctx, AV_LOG_DEBUG,"%dx%d image at pos (%d;%d) [area:%dx%d]\n",
               *width, *height, *x_start, *y_start, avctx->width, avctx->height);
    }
}

static void gif_crop_opaque(AVCodecContext *avctx,
                            const uint32_t *palette,
                            const uint8_t *buf, const int linesize,
                            int *width, int *height, int *x_start, int *y_start)
203
{
204
    GIFContext *s = avctx->priv_data;
205

206
    /* Crop image */
207
    if ((s->flags & GF_OFFSETTING) && s->last_frame && !palette) {
208 209 210 211 212 213
        const uint8_t *ref = s->last_frame->data[0];
        const int ref_linesize = s->last_frame->linesize[0];
        int x_end = avctx->width  - 1,
            y_end = avctx->height - 1;

        /* skip common lines */
214 215
        while (*y_start < y_end) {
            if (memcmp(ref + *y_start*ref_linesize, buf + *y_start*linesize, *width))
216
                break;
217
            (*y_start)++;
218
        }
219 220
        while (y_end > *y_start) {
            if (memcmp(ref + y_end*ref_linesize, buf + y_end*linesize, *width))
221 222 223
                break;
            y_end--;
        }
224
        *height = y_end + 1 - *y_start;
225 226

        /* skip common columns */
227
        while (*x_start < x_end) {
228
            int same_column = 1;
229 230
            for (int y = *y_start; y <= y_end; y++) {
                if (ref[y*ref_linesize + *x_start] != buf[y*linesize + *x_start]) {
231 232 233 234 235 236
                    same_column = 0;
                    break;
                }
            }
            if (!same_column)
                break;
237
            (*x_start)++;
238
        }
239
        while (x_end > *x_start) {
240
            int same_column = 1;
241
            for (int y = *y_start; y <= y_end; y++) {
242 243 244 245 246 247 248 249 250
                if (ref[y*ref_linesize + x_end] != buf[y*linesize + x_end]) {
                    same_column = 0;
                    break;
                }
            }
            if (!same_column)
                break;
            x_end--;
        }
251
        *width = x_end + 1 - *x_start;
252 253

        av_log(avctx, AV_LOG_DEBUG,"%dx%d image at pos (%d;%d) [area:%dx%d]\n",
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
               *width, *height, *x_start, *y_start, avctx->width, avctx->height);
    }
}

static int gif_image_write_image(AVCodecContext *avctx,
                                 uint8_t **bytestream, uint8_t *end,
                                 const uint32_t *palette,
                                 const uint8_t *buf, const int linesize,
                                 AVPacket *pkt)
{
    GIFContext *s = avctx->priv_data;
    int disposal, len = 0, height = avctx->height, width = avctx->width, x, y;
    int x_start = 0, y_start = 0, trans = s->transparent_index;
    int bcid = -1, honor_transparency = (s->flags & GF_TRANSDIFF) && s->last_frame && !palette;
    const uint8_t *ptr;

270
    if (!s->image && avctx->frame_number && is_image_translucent(avctx, buf, linesize)) {
271 272 273 274 275 276
        gif_crop_translucent(avctx, buf, linesize, &width, &height, &x_start, &y_start);
        honor_transparency = 0;
        disposal = GCE_DISPOSAL_BACKGROUND;
    } else {
        gif_crop_opaque(avctx, palette, buf, linesize, &width, &height, &x_start, &y_start);
        disposal = GCE_DISPOSAL_INPLACE;
277 278
    }

279
    if (s->image || !avctx->frame_number) { /* GIF header */
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
        const uint32_t *global_palette = palette ? palette : s->palette;
        const AVRational sar = avctx->sample_aspect_ratio;
        int64_t aspect = 0;

        if (sar.num > 0 && sar.den > 0) {
            aspect = sar.num * 64LL / sar.den - 15;
            if (aspect < 0 || aspect > 255)
                aspect = 0;
        }

        bytestream_put_buffer(bytestream, gif89a_sig, sizeof(gif89a_sig));
        bytestream_put_le16(bytestream, avctx->width);
        bytestream_put_le16(bytestream, avctx->height);

        bcid = get_palette_transparency_index(global_palette);

        bytestream_put_byte(bytestream, 0xf7); /* flags: global clut, 256 entries */
        bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : bcid); /* background color index */
        bytestream_put_byte(bytestream, aspect);
        for (int i = 0; i < 256; i++) {
            const uint32_t v = global_palette[i] & 0xffffff;
            bytestream_put_be24(bytestream, v);
        }
    }

    if (honor_transparency && trans < 0) {
        trans = pick_palette_entry(buf + y_start*linesize + x_start,
                                   linesize, width, height);
        if (trans < 0) // TODO, patch welcome
            av_log(avctx, AV_LOG_DEBUG, "No available color, can not use transparency\n");
    }
311

312 313 314
    if (trans < 0)
        honor_transparency = 0;

315
    bcid = honor_transparency || disposal == GCE_DISPOSAL_BACKGROUND ? trans : get_palette_transparency_index(palette);
316 317 318 319 320

    /* graphic control extension */
    bytestream_put_byte(bytestream, GIF_EXTENSION_INTRODUCER);
    bytestream_put_byte(bytestream, GIF_GCE_EXT_LABEL);
    bytestream_put_byte(bytestream, 0x04); /* block size */
321
    bytestream_put_byte(bytestream, disposal<<2 | (bcid >= 0));
322 323 324 325
    bytestream_put_le16(bytestream, 5); // default delay
    bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : bcid);
    bytestream_put_byte(bytestream, 0x00);

326
    /* image block */
327
    bytestream_put_byte(bytestream, GIF_IMAGE_SEPARATOR);
328 329 330 331
    bytestream_put_le16(bytestream, x_start);
    bytestream_put_le16(bytestream, y_start);
    bytestream_put_le16(bytestream, width);
    bytestream_put_le16(bytestream, height);
332 333

    if (!palette) {
334
        bytestream_put_byte(bytestream, 0x00); /* flags */
335 336 337 338 339 340 341 342
    } else {
        unsigned i;
        bytestream_put_byte(bytestream, 1<<7 | 0x7); /* flags */
        for (i = 0; i < AVPALETTE_COUNT; i++) {
            const uint32_t v = palette[i];
            bytestream_put_be24(bytestream, v);
        }
    }
343 344 345

    bytestream_put_byte(bytestream, 0x08);

346
    ff_lzw_encode_init(s->lzw, s->buf, s->buf_size,
347
                       12, FF_LZW_GIF, put_bits);
348

349
    ptr = buf + y_start*linesize + x_start;
350
    if (honor_transparency) {
351 352 353 354 355 356 357 358 359 360 361 362 363
        const int ref_linesize = s->last_frame->linesize[0];
        const uint8_t *ref = s->last_frame->data[0] + y_start*ref_linesize + x_start;

        for (y = 0; y < height; y++) {
            memcpy(s->tmpl, ptr, width);
            for (x = 0; x < width; x++)
                if (ref[x] == ptr[x])
                    s->tmpl[x] = trans;
            len += ff_lzw_encode(s->lzw, s->tmpl, width);
            ptr += linesize;
            ref += ref_linesize;
        }
    } else {
364 365 366 367
        for (y = 0; y < height; y++) {
            len += ff_lzw_encode(s->lzw, ptr, width);
            ptr += linesize;
        }
368
    }
369 370 371 372 373 374 375 376 377 378 379
    len += ff_lzw_encode_flush(s->lzw, flush_put_bits);

    ptr = s->buf;
    while (len > 0) {
        int size = FFMIN(255, len);
        bytestream_put_byte(bytestream, size);
        if (end - *bytestream < size)
            return -1;
        bytestream_put_buffer(bytestream, ptr, size);
        ptr += size;
        len -= size;
380 381 382 383 384
    }
    bytestream_put_byte(bytestream, 0x00); /* end of image block */
    return 0;
}

385
static av_cold int gif_encode_init(AVCodecContext *avctx)
386 387 388
{
    GIFContext *s = avctx->priv_data;

389 390
    if (avctx->width > 65535 || avctx->height > 65535) {
        av_log(avctx, AV_LOG_ERROR, "GIF does not support resolutions above 65535x65535\n");
391
        return AVERROR(EINVAL);
392
    }
393

394 395
    s->transparent_index = -1;

396
    s->lzw = av_mallocz(ff_lzw_encode_state_size);
397 398
    s->buf_size = avctx->width*avctx->height*2 + 1000;
    s->buf = av_malloc(s->buf_size);
399 400
    s->tmpl = av_malloc(avctx->width);
    if (!s->tmpl || !s->buf || !s->lzw)
401
        return AVERROR(ENOMEM);
402 403 404 405

    if (avpriv_set_systematic_pal2(s->palette, avctx->pix_fmt) < 0)
        av_assert0(avctx->pix_fmt == AV_PIX_FMT_PAL8);

406 407 408
    return 0;
}

409 410
static int gif_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
                            const AVFrame *pict, int *got_packet)
411 412
{
    GIFContext *s = avctx->priv_data;
413
    uint8_t *outbuf_ptr, *end;
414
    const uint32_t *palette = NULL;
415 416
    int ret;

417
    if ((ret = ff_alloc_packet2(avctx, pkt, avctx->width*avctx->height*7/5 + AV_INPUT_BUFFER_MIN_SIZE, 0)) < 0)
418 419 420
        return ret;
    outbuf_ptr = pkt->data;
    end        = pkt->data + pkt->size;
421

422
    if (avctx->pix_fmt == AV_PIX_FMT_PAL8) {
423
        palette = (uint32_t*)pict->data[1];
424 425 426 427 428 429 430 431

        if (!s->palette_loaded) {
            memcpy(s->palette, palette, AVPALETTE_SIZE);
            s->transparent_index = get_palette_transparency_index(palette);
            s->palette_loaded = 1;
        } else if (!memcmp(s->palette, palette, AVPALETTE_SIZE)) {
            palette = NULL;
        }
432
    }
433

434 435
    gif_image_write_image(avctx, &outbuf_ptr, end, palette,
                          pict->data[0], pict->linesize[0], pkt);
436
    if (!s->last_frame && !s->image) {
437 438 439 440
        s->last_frame = av_frame_alloc();
        if (!s->last_frame)
            return AVERROR(ENOMEM);
    }
441

442 443 444 445 446 447
    if (!s->image) {
        av_frame_unref(s->last_frame);
        ret = av_frame_ref(s->last_frame, (AVFrame*)pict);
        if (ret < 0)
            return ret;
    }
448 449

    pkt->size   = outbuf_ptr - pkt->data;
450
    if (s->image || !avctx->frame_number)
451
        pkt->flags |= AV_PKT_FLAG_KEY;
452 453 454
    *got_packet = 1;

    return 0;
455 456
}

457 458 459 460 461 462
static int gif_encode_close(AVCodecContext *avctx)
{
    GIFContext *s = avctx->priv_data;

    av_freep(&s->lzw);
    av_freep(&s->buf);
463
    s->buf_size = 0;
464
    av_frame_free(&s->last_frame);
465
    av_freep(&s->tmpl);
466 467 468
    return 0;
}

469 470 471
#define OFFSET(x) offsetof(GIFContext, x)
#define FLAGS AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM
static const AVOption gif_options[] = {
472
    { "gifflags", "set GIF flags", OFFSET(flags), AV_OPT_TYPE_FLAGS, {.i64 = GF_OFFSETTING|GF_TRANSDIFF}, 0, INT_MAX, FLAGS, "flags" },
473
        { "offsetting", "enable picture offsetting", 0, AV_OPT_TYPE_CONST, {.i64=GF_OFFSETTING}, INT_MIN, INT_MAX, FLAGS, "flags" },
474
        { "transdiff", "enable transparency detection between frames", 0, AV_OPT_TYPE_CONST, {.i64=GF_TRANSDIFF}, INT_MIN, INT_MAX, FLAGS, "flags" },
475
    { "gifimage", "enable encoding only images per frame", OFFSET(image), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS },
476 477 478 479 480 481 482 483 484 485
    { NULL }
};

static const AVClass gif_class = {
    .class_name = "GIF encoder",
    .item_name  = av_default_item_name,
    .option     = gif_options,
    .version    = LIBAVUTIL_VERSION_INT,
};

486
AVCodec ff_gif_encoder = {
487
    .name           = "gif",
488
    .long_name      = NULL_IF_CONFIG_SMALL("GIF (Graphics Interchange Format)"),
489
    .type           = AVMEDIA_TYPE_VIDEO,
490
    .id             = AV_CODEC_ID_GIF,
491 492
    .priv_data_size = sizeof(GIFContext),
    .init           = gif_encode_init,
493
    .encode2        = gif_encode_frame,
494
    .close          = gif_encode_close,
495 496 497
    .pix_fmts       = (const enum AVPixelFormat[]){
        AV_PIX_FMT_RGB8, AV_PIX_FMT_BGR8, AV_PIX_FMT_RGB4_BYTE, AV_PIX_FMT_BGR4_BYTE,
        AV_PIX_FMT_GRAY8, AV_PIX_FMT_PAL8, AV_PIX_FMT_NONE
498
    },
499
    .priv_class     = &gif_class,
500
};