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 "codec_internal.h" 39#include "encode.h" 40#include "lzw.h" 41#include "gif.h" 42 43#include "put_bits.h" 44 45#define DEFAULT_TRANSPARENCY_INDEX 0x1f 46 47typedef struct GIFContext { 48 const AVClass *class; 49 LZWState *lzw; 50 uint8_t *buf; 51 uint8_t *shrunk_buf; 52 int buf_size; 53 AVFrame *last_frame; 54 int flags; 55 int image; 56 int use_global_palette; 57 uint32_t palette[AVPALETTE_COUNT]; ///< local reference palette for !pal8 58 int palette_loaded; 59 int transparent_index; 60 uint8_t *tmpl; ///< temporary line buffer 61} GIFContext; 62 63enum { 64 GF_OFFSETTING = 1<<0, 65 GF_TRANSDIFF = 1<<1, 66}; 67 68static void shrink_palette(const uint32_t *src, uint8_t *map, 69 uint32_t *dst, size_t *palette_count) 70{ 71 size_t colors_seen = 0; 72 73 for (size_t i = 0; i < AVPALETTE_COUNT; i++) { 74 int seen = 0; 75 for (size_t c = 0; c < colors_seen; c++) { 76 if (src[i] == dst[c]) { 77 seen = 1; 78 break; 79 } 80 } 81 if (!seen) { 82 dst[colors_seen] = src[i]; 83 map[i] = colors_seen; 84 colors_seen++; 85 } 86 } 87 88 *palette_count = colors_seen; 89} 90 91static void remap_frame_to_palette(const uint8_t *src, int src_linesize, 92 uint8_t *dst, int dst_linesize, 93 int w, int h, uint8_t *map) 94{ 95 for (int i = 0; i < h; i++) 96 for (int j = 0; j < w; j++) 97 dst[i * dst_linesize + j] = map[src[i * src_linesize + j]]; 98} 99 100static int is_image_translucent(AVCodecContext *avctx, 101 const uint8_t *buf, const int linesize) 102{ 103 GIFContext *s = avctx->priv_data; 104 int trans = s->transparent_index; 105 106 if (trans < 0) 107 return 0; 108 109 for (int y = 0; y < avctx->height; y++) { 110 for (int x = 0; x < avctx->width; x++) { 111 if (buf[x] == trans) { 112 return 1; 113 } 114 } 115 buf += linesize; 116 } 117 118 return 0; 119} 120 121static int get_palette_transparency_index(const uint32_t *palette) 122{ 123 int transparent_color_index = -1; 124 unsigned i, smallest_alpha = 0xff; 125 126 if (!palette) 127 return -1; 128 129 for (i = 0; i < AVPALETTE_COUNT; i++) { 130 const uint32_t v = palette[i]; 131 if (v >> 24 < smallest_alpha) { 132 smallest_alpha = v >> 24; 133 transparent_color_index = i; 134 } 135 } 136 return smallest_alpha < 128 ? transparent_color_index : -1; 137} 138 139static int pick_palette_entry(const uint8_t *buf, int linesize, int w, int h) 140{ 141 int histogram[AVPALETTE_COUNT] = {0}; 142 int x, y, i; 143 144 for (y = 0; y < h; y++) { 145 for (x = 0; x < w; x++) 146 histogram[buf[x]]++; 147 buf += linesize; 148 } 149 for (i = 0; i < FF_ARRAY_ELEMS(histogram); i++) 150 if (!histogram[i]) 151 return i; 152 return -1; 153} 154 155static void gif_crop_translucent(AVCodecContext *avctx, 156 const uint8_t *buf, const int linesize, 157 int *width, int *height, 158 int *x_start, int *y_start) 159{ 160 GIFContext *s = avctx->priv_data; 161 int trans = s->transparent_index; 162 163 /* Crop image */ 164 if ((s->flags & GF_OFFSETTING) && trans >= 0) { 165 const int w = avctx->width; 166 const int h = avctx->height; 167 int x_end = w - 1, 168 y_end = h - 1; 169 170 // crop top 171 while (*y_start < y_end) { 172 int is_trans = 1; 173 for (int i = 0; i < w; i++) { 174 if (buf[linesize * *y_start + i] != trans) { 175 is_trans = 0; 176 break; 177 } 178 } 179 180 if (!is_trans) 181 break; 182 (*y_start)++; 183 } 184 185 // crop bottom 186 while (y_end > *y_start) { 187 int is_trans = 1; 188 for (int i = 0; i < w; i++) { 189 if (buf[linesize * y_end + i] != trans) { 190 is_trans = 0; 191 break; 192 } 193 } 194 if (!is_trans) 195 break; 196 y_end--; 197 } 198 199 // crop left 200 while (*x_start < x_end) { 201 int is_trans = 1; 202 for (int i = *y_start; i < y_end; i++) { 203 if (buf[linesize * i + *x_start] != trans) { 204 is_trans = 0; 205 break; 206 } 207 } 208 if (!is_trans) 209 break; 210 (*x_start)++; 211 } 212 213 // crop right 214 while (x_end > *x_start) { 215 int is_trans = 1; 216 for (int i = *y_start; i < y_end; i++) { 217 if (buf[linesize * i + x_end] != trans) { 218 is_trans = 0; 219 break; 220 } 221 } 222 if (!is_trans) 223 break; 224 x_end--; 225 } 226 227 *height = y_end + 1 - *y_start; 228 *width = x_end + 1 - *x_start; 229 av_log(avctx, AV_LOG_DEBUG,"%dx%d image at pos (%d;%d) [area:%dx%d]\n", 230 *width, *height, *x_start, *y_start, avctx->width, avctx->height); 231 } 232} 233 234static void gif_crop_opaque(AVCodecContext *avctx, 235 const uint32_t *palette, 236 const uint8_t *buf, const int linesize, 237 int *width, int *height, int *x_start, int *y_start) 238{ 239 GIFContext *s = avctx->priv_data; 240 241 /* Crop image */ 242 if ((s->flags & GF_OFFSETTING) && s->last_frame && !palette) { 243 const uint8_t *ref = s->last_frame->data[0]; 244 const int ref_linesize = s->last_frame->linesize[0]; 245 int x_end = avctx->width - 1, 246 y_end = avctx->height - 1; 247 248 /* skip common lines */ 249 while (*y_start < y_end) { 250 if (memcmp(ref + *y_start*ref_linesize, buf + *y_start*linesize, *width)) 251 break; 252 (*y_start)++; 253 } 254 while (y_end > *y_start) { 255 if (memcmp(ref + y_end*ref_linesize, buf + y_end*linesize, *width)) 256 break; 257 y_end--; 258 } 259 *height = y_end + 1 - *y_start; 260 261 /* skip common columns */ 262 while (*x_start < x_end) { 263 int same_column = 1; 264 for (int y = *y_start; y <= y_end; y++) { 265 if (ref[y*ref_linesize + *x_start] != buf[y*linesize + *x_start]) { 266 same_column = 0; 267 break; 268 } 269 } 270 if (!same_column) 271 break; 272 (*x_start)++; 273 } 274 while (x_end > *x_start) { 275 int same_column = 1; 276 for (int y = *y_start; y <= y_end; y++) { 277 if (ref[y*ref_linesize + x_end] != buf[y*linesize + x_end]) { 278 same_column = 0; 279 break; 280 } 281 } 282 if (!same_column) 283 break; 284 x_end--; 285 } 286 *width = x_end + 1 - *x_start; 287 288 av_log(avctx, AV_LOG_DEBUG,"%dx%d image at pos (%d;%d) [area:%dx%d]\n", 289 *width, *height, *x_start, *y_start, avctx->width, avctx->height); 290 } 291} 292 293static int gif_image_write_image(AVCodecContext *avctx, 294 uint8_t **bytestream, uint8_t *end, 295 const uint32_t *palette, 296 const uint8_t *buf, const int linesize, 297 AVPacket *pkt) 298{ 299 GIFContext *s = avctx->priv_data; 300 int disposal, len = 0, height = avctx->height, width = avctx->width, x, y; 301 int x_start = 0, y_start = 0, trans = s->transparent_index; 302 int bcid = -1, honor_transparency = (s->flags & GF_TRANSDIFF) && s->last_frame && !palette; 303 const uint8_t *ptr; 304 uint32_t shrunk_palette[AVPALETTE_COUNT]; 305 uint8_t map[AVPALETTE_COUNT] = { 0 }; 306 size_t shrunk_palette_count = 0; 307 308 /* 309 * We memset to 0xff instead of 0x00 so that the transparency detection 310 * doesn't pick anything after the palette entries as the transparency 311 * index, and because GIF89a requires us to always write a power-of-2 312 * number of palette entries. 313 */ 314 memset(shrunk_palette, 0xff, AVPALETTE_SIZE); 315 316 if (!s->image && is_image_translucent(avctx, buf, linesize)) { 317 gif_crop_translucent(avctx, buf, linesize, &width, &height, &x_start, &y_start); 318 honor_transparency = 0; 319 disposal = GCE_DISPOSAL_BACKGROUND; 320 } else { 321 gif_crop_opaque(avctx, palette, buf, linesize, &width, &height, &x_start, &y_start); 322 disposal = GCE_DISPOSAL_INPLACE; 323 } 324 325 if (s->image || !avctx->frame_number) { /* GIF header */ 326 const uint32_t *global_palette = palette ? palette : s->palette; 327 const AVRational sar = avctx->sample_aspect_ratio; 328 int64_t aspect = 0; 329 330 if (sar.num > 0 && sar.den > 0) { 331 aspect = sar.num * 64LL / sar.den - 15; 332 if (aspect < 0 || aspect > 255) 333 aspect = 0; 334 } 335 336 bytestream_put_buffer(bytestream, gif89a_sig, sizeof(gif89a_sig)); 337 bytestream_put_le16(bytestream, avctx->width); 338 bytestream_put_le16(bytestream, avctx->height); 339 340 bcid = get_palette_transparency_index(global_palette); 341 342 bytestream_put_byte(bytestream, ((uint8_t) s->use_global_palette << 7) | 0x70 | (s->use_global_palette ? 7 : 0)); /* flags: global clut, 256 entries */ 343 bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : bcid); /* background color index */ 344 bytestream_put_byte(bytestream, aspect); 345 if (s->use_global_palette) { 346 for (int i = 0; i < 256; i++) { 347 const uint32_t v = global_palette[i] & 0xffffff; 348 bytestream_put_be24(bytestream, v); 349 } 350 } 351 } 352 353 if (honor_transparency && trans < 0) { 354 trans = pick_palette_entry(buf + y_start*linesize + x_start, 355 linesize, width, height); 356 if (trans < 0) // TODO, patch welcome 357 av_log(avctx, AV_LOG_DEBUG, "No available color, can not use transparency\n"); 358 } 359 360 if (trans < 0) 361 honor_transparency = 0; 362 363 if (palette || !s->use_global_palette) { 364 const uint32_t *pal = palette ? palette : s->palette; 365 shrink_palette(pal, map, shrunk_palette, &shrunk_palette_count); 366 } 367 368 bcid = honor_transparency || disposal == GCE_DISPOSAL_BACKGROUND ? trans : get_palette_transparency_index(palette); 369 370 /* graphic control extension */ 371 bytestream_put_byte(bytestream, GIF_EXTENSION_INTRODUCER); 372 bytestream_put_byte(bytestream, GIF_GCE_EXT_LABEL); 373 bytestream_put_byte(bytestream, 0x04); /* block size */ 374 bytestream_put_byte(bytestream, disposal<<2 | (bcid >= 0)); 375 bytestream_put_le16(bytestream, 5); // default delay 376 bytestream_put_byte(bytestream, bcid < 0 ? DEFAULT_TRANSPARENCY_INDEX : (shrunk_palette_count ? map[bcid] : bcid)); 377 bytestream_put_byte(bytestream, 0x00); 378 379 /* image block */ 380 bytestream_put_byte(bytestream, GIF_IMAGE_SEPARATOR); 381 bytestream_put_le16(bytestream, x_start); 382 bytestream_put_le16(bytestream, y_start); 383 bytestream_put_le16(bytestream, width); 384 bytestream_put_le16(bytestream, height); 385 386 if (palette || !s->use_global_palette) { 387 unsigned pow2_count = av_log2(shrunk_palette_count - 1); 388 unsigned i; 389 390 bytestream_put_byte(bytestream, 1<<7 | pow2_count); /* flags */ 391 for (i = 0; i < 1 << (pow2_count + 1); i++) { 392 const uint32_t v = shrunk_palette[i]; 393 bytestream_put_be24(bytestream, v); 394 } 395 } else { 396 bytestream_put_byte(bytestream, 0x00); /* flags */ 397 } 398 399 bytestream_put_byte(bytestream, 0x08); 400 401 ff_lzw_encode_init(s->lzw, s->buf, s->buf_size, 402 12, FF_LZW_GIF, 1); 403 404 if (shrunk_palette_count) { 405 if (!s->shrunk_buf) { 406 s->shrunk_buf = av_malloc(avctx->height * linesize); 407 if (!s->shrunk_buf) { 408 av_log(avctx, AV_LOG_ERROR, "Could not allocated remapped frame buffer.\n"); 409 return AVERROR(ENOMEM); 410 } 411 } 412 remap_frame_to_palette(buf, linesize, s->shrunk_buf, linesize, avctx->width, avctx->height, map); 413 ptr = s->shrunk_buf + y_start*linesize + x_start; 414 } else { 415 ptr = buf + y_start*linesize + x_start; 416 } 417 if (honor_transparency) { 418 const int ref_linesize = s->last_frame->linesize[0]; 419 const uint8_t *ref = s->last_frame->data[0] + y_start*ref_linesize + x_start; 420 421 for (y = 0; y < height; y++) { 422 memcpy(s->tmpl, ptr, width); 423 for (x = 0; x < width; x++) 424 if (ref[x] == ptr[x]) 425 s->tmpl[x] = trans; 426 len += ff_lzw_encode(s->lzw, s->tmpl, width); 427 ptr += linesize; 428 ref += ref_linesize; 429 } 430 } else { 431 for (y = 0; y < height; y++) { 432 len += ff_lzw_encode(s->lzw, ptr, width); 433 ptr += linesize; 434 } 435 } 436 len += ff_lzw_encode_flush(s->lzw); 437 438 ptr = s->buf; 439 while (len > 0) { 440 int size = FFMIN(255, len); 441 bytestream_put_byte(bytestream, size); 442 if (end - *bytestream < size) 443 return -1; 444 bytestream_put_buffer(bytestream, ptr, size); 445 ptr += size; 446 len -= size; 447 } 448 bytestream_put_byte(bytestream, 0x00); /* end of image block */ 449 return 0; 450} 451 452static av_cold int gif_encode_init(AVCodecContext *avctx) 453{ 454 GIFContext *s = avctx->priv_data; 455 456 if (avctx->width > 65535 || avctx->height > 65535) { 457 av_log(avctx, AV_LOG_ERROR, "GIF does not support resolutions above 65535x65535\n"); 458 return AVERROR(EINVAL); 459 } 460 461 s->transparent_index = -1; 462 463 s->lzw = av_mallocz(ff_lzw_encode_state_size); 464 s->buf_size = avctx->width*avctx->height*2 + 1000; 465 s->buf = av_malloc(s->buf_size); 466 s->tmpl = av_malloc(avctx->width); 467 if (!s->tmpl || !s->buf || !s->lzw) 468 return AVERROR(ENOMEM); 469 470 if (avpriv_set_systematic_pal2(s->palette, avctx->pix_fmt) < 0) 471 av_assert0(avctx->pix_fmt == AV_PIX_FMT_PAL8); 472 473 return 0; 474} 475 476static int gif_encode_frame(AVCodecContext *avctx, AVPacket *pkt, 477 const AVFrame *pict, int *got_packet) 478{ 479 GIFContext *s = avctx->priv_data; 480 uint8_t *outbuf_ptr, *end; 481 const uint32_t *palette = NULL; 482 int ret; 483 484 if ((ret = ff_alloc_packet(avctx, pkt, avctx->width*avctx->height*7/5 + AV_INPUT_BUFFER_MIN_SIZE)) < 0) 485 return ret; 486 outbuf_ptr = pkt->data; 487 end = pkt->data + pkt->size; 488 489 if (avctx->pix_fmt == AV_PIX_FMT_PAL8) { 490 palette = (uint32_t*)pict->data[1]; 491 492 if (!s->palette_loaded) { 493 memcpy(s->palette, palette, AVPALETTE_SIZE); 494 s->transparent_index = get_palette_transparency_index(palette); 495 s->palette_loaded = 1; 496 } else if (!memcmp(s->palette, palette, AVPALETTE_SIZE)) { 497 palette = NULL; 498 } 499 } 500 501 gif_image_write_image(avctx, &outbuf_ptr, end, palette, 502 pict->data[0], pict->linesize[0], pkt); 503 if (!s->last_frame && !s->image) { 504 s->last_frame = av_frame_alloc(); 505 if (!s->last_frame) 506 return AVERROR(ENOMEM); 507 } 508 509 if (!s->image) { 510 av_frame_unref(s->last_frame); 511 ret = av_frame_ref(s->last_frame, (AVFrame*)pict); 512 if (ret < 0) 513 return ret; 514 } 515 516 pkt->size = outbuf_ptr - pkt->data; 517 if (s->image || !avctx->frame_number) 518 pkt->flags |= AV_PKT_FLAG_KEY; 519 *got_packet = 1; 520 521 return 0; 522} 523 524static int gif_encode_close(AVCodecContext *avctx) 525{ 526 GIFContext *s = avctx->priv_data; 527 528 av_freep(&s->lzw); 529 av_freep(&s->buf); 530 av_freep(&s->shrunk_buf); 531 s->buf_size = 0; 532 av_frame_free(&s->last_frame); 533 av_freep(&s->tmpl); 534 return 0; 535} 536 537#define OFFSET(x) offsetof(GIFContext, x) 538#define FLAGS AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM 539static const AVOption gif_options[] = { 540 { "gifflags", "set GIF flags", OFFSET(flags), AV_OPT_TYPE_FLAGS, {.i64 = GF_OFFSETTING|GF_TRANSDIFF}, 0, INT_MAX, FLAGS, "flags" }, 541 { "offsetting", "enable picture offsetting", 0, AV_OPT_TYPE_CONST, {.i64=GF_OFFSETTING}, INT_MIN, INT_MAX, FLAGS, "flags" }, 542 { "transdiff", "enable transparency detection between frames", 0, AV_OPT_TYPE_CONST, {.i64=GF_TRANSDIFF}, INT_MIN, INT_MAX, FLAGS, "flags" }, 543 { "gifimage", "enable encoding only images per frame", OFFSET(image), AV_OPT_TYPE_BOOL, {.i64=0}, 0, 1, FLAGS }, 544 { "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 }, 545 { NULL } 546}; 547 548static const AVClass gif_class = { 549 .class_name = "GIF encoder", 550 .item_name = av_default_item_name, 551 .option = gif_options, 552 .version = LIBAVUTIL_VERSION_INT, 553}; 554 555const FFCodec ff_gif_encoder = { 556 .p.name = "gif", 557 .p.long_name = NULL_IF_CONFIG_SMALL("GIF (Graphics Interchange Format)"), 558 .p.type = AVMEDIA_TYPE_VIDEO, 559 .p.id = AV_CODEC_ID_GIF, 560 .priv_data_size = sizeof(GIFContext), 561 .init = gif_encode_init, 562 FF_CODEC_ENCODE_CB(gif_encode_frame), 563 .close = gif_encode_close, 564 .p.pix_fmts = (const enum AVPixelFormat[]){ 565 AV_PIX_FMT_RGB8, AV_PIX_FMT_BGR8, AV_PIX_FMT_RGB4_BYTE, AV_PIX_FMT_BGR4_BYTE, 566 AV_PIX_FMT_GRAY8, AV_PIX_FMT_PAL8, AV_PIX_FMT_NONE 567 }, 568 .p.priv_class = &gif_class, 569 .caps_internal = FF_CODEC_CAP_INIT_THREADSAFE | FF_CODEC_CAP_INIT_CLEANUP, 570}; 571