git.sesse.net Git - ffmpeg/blob - libavcodec/flashsv2enc.c

   1 /*
   2  * Flash Screen Video Version 2 encoder
   3  * Copyright (C) 2009 Joshua Warner
   4  *
   5  * This file is part of FFmpeg.
   6  *
   7  * FFmpeg is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * FFmpeg is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with FFmpeg; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 /**
  23  * @file
  24  * Flash Screen Video Version 2 encoder
  25  * @author Joshua Warner
  26  */
  27
  28 /* Differences from version 1 stream:
  29  * NOTE: Currently, the only player that supports version 2 streams is Adobe Flash Player itself.
  30  * * Supports sending only a range of scanlines in a block,
  31  *   indicating a difference from the corresponding block in the last keyframe.
  32  * * Supports initializing the zlib dictionary with data from the corresponding
  33  *   block in the last keyframe, to improve compression.
  34  * * Supports a hybrid 15-bit rgb / 7-bit palette color space.
  35  */
  36
  37 /* TODO:
  38  * Don't keep Block structures for both current frame and keyframe.
  39  * Make better heuristics for deciding stream parameters (optimum_* functions).  Currently these return constants.
  40  * Figure out how to encode palette information in the stream, choose an optimum palette at each keyframe.
  41  * Figure out how the zlibPrimeCompressCurrent flag works, implement support.
  42  * Find other sample files (that weren't generated here), develop a decoder.
  43  */
  44
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #include <zlib.h>
  48
  49 #include "libavutil/imgutils.h"
  50 #include "avcodec.h"
  51 #include "internal.h"
  52 #include "put_bits.h"
  53 #include "bytestream.h"
  54
  55 #define HAS_IFRAME_IMAGE 0x02
  56 #define HAS_PALLET_INFO 0x01
  57
  58 #define COLORSPACE_BGR 0x00
  59 #define COLORSPACE_15_7 0x10
  60 #define HAS_DIFF_BLOCKS 0x04
  61 #define ZLIB_PRIME_COMPRESS_CURRENT 0x02
  62 #define ZLIB_PRIME_COMPRESS_PREVIOUS 0x01
  63
  64 // Disables experimental "smart" parameter-choosing code, as well as the statistics that it depends on.
  65 // At the moment, the "smart" code is a great example of how the parameters *shouldn't* be chosen.
  66 #define FLASHSV2_DUMB
  67
  68 typedef struct Block {
  69     uint8_t *enc;
  70     uint8_t *sl_begin, *sl_end;
  71     int enc_size;
  72     uint8_t *data;
  73     unsigned long data_size;
  74
  75     uint8_t start, len;
  76     uint8_t dirty;
  77     uint8_t col, row, width, height;
  78     uint8_t flags;
  79 } Block;
  80
  81 typedef struct Palette {
  82     unsigned colors[128];
  83     uint8_t index[1 << 15];
  84 } Palette;
  85
  86 typedef struct FlashSV2Context {
  87     AVCodecContext *avctx;
  88     uint8_t *current_frame;
  89     uint8_t *key_frame;
  90     uint8_t *encbuffer;
  91     uint8_t *keybuffer;
  92     uint8_t *databuffer;
  93
  94     uint8_t *blockbuffer;
  95     int blockbuffer_size;
  96
  97     Block *frame_blocks;
  98     Block *key_blocks;
  99     int frame_size;
 100     int blocks_size;
 101
 102     int use15_7, dist, comp;
 103
 104     int rows, cols;
 105
 106     int last_key_frame;
 107
 108     int image_width, image_height;
 109     int block_width, block_height;
 110     uint8_t flags;
 111     uint8_t use_custom_palette;
 112     uint8_t palette_type;       ///< 0=>default, 1=>custom - changed when palette regenerated.
 113     Palette palette;
 114 #ifndef FLASHSV2_DUMB
 115     double tot_blocks;          ///< blocks encoded since last keyframe
 116     double diff_blocks;         ///< blocks that were different since last keyframe
 117     double tot_lines;           ///< total scanlines in image since last keyframe
 118     double diff_lines;          ///< scanlines that were different since last keyframe
 119     double raw_size;            ///< size of raw frames since last keyframe
 120     double comp_size;           ///< size of compressed data since last keyframe
 121     double uncomp_size;         ///< size of uncompressed data since last keyframe
 122
 123     double total_bits;          ///< total bits written to stream so far
 124 #endif
 125 } FlashSV2Context;
 126
 127 static av_cold void cleanup(FlashSV2Context * s)
 128 {
 129     av_freep(&s->encbuffer);
 130     av_freep(&s->keybuffer);
 131     av_freep(&s->databuffer);
 132     av_freep(&s->blockbuffer);
 133     av_freep(&s->current_frame);
 134     av_freep(&s->key_frame);
 135
 136     av_freep(&s->frame_blocks);
 137     av_freep(&s->key_blocks);
 138 }
 139
 140 static void init_blocks(FlashSV2Context * s, Block * blocks,
 141                         uint8_t * encbuf, uint8_t * databuf)
 142 {
 143     int row, col;
 144     Block *b;
 145     memset(blocks, 0, s->cols * s->rows * sizeof(*blocks));
 146     for (col = 0; col < s->cols; col++) {
 147         for (row = 0; row < s->rows; row++) {
 148             b = blocks + (col + row * s->cols);
 149             b->width = (col < s->cols - 1) ?
 150                 s->block_width :
 151                 s->image_width - col * s->block_width;
 152
 153             b->height = (row < s->rows - 1) ?
 154                 s->block_height :
 155                 s->image_height - row * s->block_height;
 156
 157             b->row   = row;
 158             b->col   = col;
 159             b->enc   = encbuf;
 160             b->data  = databuf;
 161             encbuf  += b->width * b->height * 3;
 162             databuf  = databuf ? databuf + b->width * b->height * 6 : NULL;
 163         }
 164     }
 165 }
 166
 167 static void reset_stats(FlashSV2Context * s)
 168 {
 169 #ifndef FLASHSV2_DUMB
 170     s->diff_blocks = 0.1;
 171     s->tot_blocks = 1;
 172     s->diff_lines = 0.1;
 173     s->tot_lines = 1;
 174     s->raw_size = s->comp_size = s->uncomp_size = 10;
 175 #endif
 176 }
 177
 178 static int update_block_dimensions(FlashSV2Context *s, int block_width, int block_height)
 179 {
 180     s->block_width  = block_width;
 181     s->block_height = block_height;
 182     s->rows = (s->image_height + s->block_height - 1) / s->block_height;
 183     s->cols = (s->image_width  + s->block_width  - 1) / s->block_width;
 184     if (s->rows * s->cols > s->blocks_size / sizeof(Block)) {
 185         s->frame_blocks = av_realloc_array(s->frame_blocks, s->rows, s->cols * sizeof(Block));
 186         s->key_blocks = av_realloc_array(s->key_blocks, s->cols, s->rows * sizeof(Block));
 187         if (!s->frame_blocks || !s->key_blocks) {
 188             av_log(s->avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
 189             return AVERROR(ENOMEM);
 190         }
 191         s->blocks_size = s->rows * s->cols * sizeof(Block);
 192     }
 193     init_blocks(s, s->frame_blocks, s->encbuffer, s->databuffer);
 194     init_blocks(s, s->key_blocks, s->keybuffer, 0);
 195
 196     av_fast_malloc(&s->blockbuffer, &s->blockbuffer_size, block_width * block_height * 6);
 197     if (!s->blockbuffer) {
 198         av_log(s->avctx, AV_LOG_ERROR, "Could not allocate block buffer.\n");
 199         return AVERROR(ENOMEM);
 200     }
 201     return 0;
 202 }
 203
 204
 205 static av_cold int flashsv2_encode_init(AVCodecContext * avctx)
 206 {
 207     FlashSV2Context *s = avctx->priv_data;
 208     int ret;
 209
 210     s->avctx = avctx;
 211
 212     s->comp = avctx->compression_level;
 213     if (s->comp == -1)
 214         s->comp = 9;
 215     if (s->comp < 0 || s->comp > 9) {
 216         av_log(avctx, AV_LOG_ERROR,
 217                "Compression level should be 0-9, not %d\n", s->comp);
 218         return AVERROR(EINVAL);
 219     }
 220
 221
 222     if ((avctx->width > 4095) || (avctx->height > 4095)) {
 223         av_log(avctx, AV_LOG_ERROR,
 224                "Input dimensions too large, input must be max 4095x4095 !\n");
 225         return AVERROR(EINVAL);
 226     }
 227     if ((avctx->width < 16) || (avctx->height < 16)) {
 228         av_log(avctx, AV_LOG_ERROR,
 229                "Input dimensions too small, input must be at least 16x16 !\n");
 230         return AVERROR(EINVAL);
 231     }
 232
 233     if ((ret = av_image_check_size(avctx->width, avctx->height, 0, avctx)) < 0)
 234         return ret;
 235
 236
 237     s->last_key_frame = 0;
 238
 239     s->image_width  = avctx->width;
 240     s->image_height = avctx->height;
 241
 242     s->frame_size  = s->image_width * s->image_height * 3;
 243
 244     s->encbuffer     = av_mallocz(s->frame_size);
 245     s->keybuffer     = av_mallocz(s->frame_size);
 246     s->databuffer    = av_mallocz(s->frame_size * 6);
 247     s->current_frame = av_mallocz(s->frame_size);
 248     s->key_frame     = av_mallocz(s->frame_size);
 249     if (!s->encbuffer || !s->keybuffer || !s->databuffer
 250         || !s->current_frame || !s->key_frame) {
 251         av_log(avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
 252         return AVERROR(ENOMEM);
 253     }
 254
 255     reset_stats(s);
 256 #ifndef FLASHSV2_DUMB
 257     s->total_bits = 1;
 258 #endif
 259
 260     s->use_custom_palette =  0;
 261     s->palette_type       = -1;        // so that the palette will be generated in reconfigure_at_keyframe
 262
 263     return update_block_dimensions(s, 64, 64);
 264 }
 265
 266 static int new_key_frame(FlashSV2Context * s)
 267 {
 268     int i;
 269     memcpy(s->key_blocks, s->frame_blocks, s->blocks_size);
 270     memcpy(s->key_frame, s->current_frame, s->frame_size);
 271
 272     for (i = 0; i < s->rows * s->cols; i++) {
 273         s->key_blocks[i].enc += (s->keybuffer - s->encbuffer);
 274         s->key_blocks[i].sl_begin = 0;
 275         s->key_blocks[i].sl_end   = 0;
 276         s->key_blocks[i].data     = 0;
 277     }
 278     memcpy(s->keybuffer, s->encbuffer, s->frame_size);
 279
 280     return 0;
 281 }
 282
 283 static int write_palette(FlashSV2Context * s, uint8_t * buf, int buf_size)
 284 {
 285     //this isn't implemented yet!  Default palette only!
 286     return -1;
 287 }
 288
 289 static int write_header(FlashSV2Context * s, uint8_t * buf, int buf_size)
 290 {
 291     PutBitContext pb;
 292     int buf_pos, len;
 293
 294     if (buf_size < 5)
 295         return -1;
 296
 297     init_put_bits(&pb, buf, buf_size);
 298
 299     put_bits(&pb, 4, (s->block_width  >> 4) - 1);
 300     put_bits(&pb, 12, s->image_width);
 301     put_bits(&pb, 4, (s->block_height >> 4) - 1);
 302     put_bits(&pb, 12, s->image_height);
 303
 304     flush_put_bits(&pb);
 305     buf_pos = 4;
 306
 307     buf[buf_pos++] = s->flags;
 308
 309     if (s->flags & HAS_PALLET_INFO) {
 310         len = write_palette(s, buf + buf_pos, buf_size - buf_pos);
 311         if (len < 0)
 312             return -1;
 313         buf_pos += len;
 314     }
 315
 316     return buf_pos;
 317 }
 318
 319 static int write_block(Block * b, uint8_t * buf, int buf_size)
 320 {
 321     int buf_pos = 0;
 322     unsigned block_size = b->data_size;
 323
 324     if (b->flags & HAS_DIFF_BLOCKS)
 325         block_size += 2;
 326     if (b->flags & ZLIB_PRIME_COMPRESS_CURRENT)
 327         block_size += 2;
 328     if (block_size > 0)
 329         block_size += 1;
 330     if (buf_size < block_size + 2)
 331         return -1;
 332
 333     buf[buf_pos++] = block_size >> 8;
 334     buf[buf_pos++] = block_size;
 335
 336     if (block_size == 0)
 337         return buf_pos;
 338
 339     buf[buf_pos++] = b->flags;
 340
 341     if (b->flags & HAS_DIFF_BLOCKS) {
 342         buf[buf_pos++] = (b->start);
 343         buf[buf_pos++] = (b->len);
 344     }
 345
 346     if (b->flags & ZLIB_PRIME_COMPRESS_CURRENT) {
 347         //This feature of the format is poorly understood, and as of now, unused.
 348         buf[buf_pos++] = (b->col);
 349         buf[buf_pos++] = (b->row);
 350     }
 351
 352     memcpy(buf + buf_pos, b->data, b->data_size);
 353
 354     buf_pos += b->data_size;
 355
 356     return buf_pos;
 357 }
 358
 359 static int encode_zlib(Block * b, uint8_t * buf, unsigned long *buf_size, int comp)
 360 {
 361     int res = compress2(buf, buf_size, b->sl_begin, b->sl_end - b->sl_begin, comp);
 362     return res == Z_OK ? 0 : -1;
 363 }
 364
 365 static int encode_zlibprime(Block * b, Block * prime, uint8_t * buf,
 366                             int *buf_size, int comp)
 367 {
 368     z_stream s;
 369     int res;
 370     s.zalloc = NULL;
 371     s.zfree  = NULL;
 372     s.opaque = NULL;
 373     res = deflateInit(&s, comp);
 374     if (res < 0)
 375         return -1;
 376
 377     s.next_in  = prime->enc;
 378     s.avail_in = prime->enc_size;
 379     while (s.avail_in > 0) {
 380         s.next_out  = buf;
 381         s.avail_out = *buf_size;
 382         res = deflate(&s, Z_SYNC_FLUSH);
 383         if (res < 0)
 384             return -1;
 385     }
 386
 387     s.next_in   = b->sl_begin;
 388     s.avail_in  = b->sl_end - b->sl_begin;
 389     s.next_out  = buf;
 390     s.avail_out = *buf_size;
 391     res = deflate(&s, Z_FINISH);
 392     deflateEnd(&s);
 393     *buf_size -= s.avail_out;
 394     if (res != Z_STREAM_END)
 395         return -1;
 396     return 0;
 397 }
 398
 399 static int encode_bgr(Block * b, const uint8_t * src, int stride)
 400 {
 401     int i;
 402     uint8_t *ptr = b->enc;
 403     for (i = 0; i < b->start; i++)
 404         memcpy(ptr + i * b->width * 3, src + i * stride, b->width * 3);
 405     b->sl_begin = ptr + i * b->width * 3;
 406     for (; i < b->start + b->len; i++)
 407         memcpy(ptr + i * b->width * 3, src + i * stride, b->width * 3);
 408     b->sl_end = ptr + i * b->width * 3;
 409     for (; i < b->height; i++)
 410         memcpy(ptr + i * b->width * 3, src + i * stride, b->width * 3);
 411     b->enc_size = ptr + i * b->width * 3 - b->enc;
 412     return b->enc_size;
 413 }
 414
 415 static inline unsigned pixel_color15(const uint8_t * src)
 416 {
 417     return (src[0] >> 3) | ((src[1] & 0xf8) << 2) | ((src[2] & 0xf8) << 7);
 418 }
 419
 420 static inline unsigned int chroma_diff(unsigned int c1, unsigned int c2)
 421 {
 422 #define ABSDIFF(a,b) (abs((int)(a)-(int)(b)))
 423
 424     unsigned int t1 = (c1 & 0x000000ff) + ((c1 & 0x0000ff00) >> 8) + ((c1 & 0x00ff0000) >> 16);
 425     unsigned int t2 = (c2 & 0x000000ff) + ((c2 & 0x0000ff00) >> 8) + ((c2 & 0x00ff0000) >> 16);
 426
 427     return ABSDIFF(t1, t2) + ABSDIFF(c1 & 0x000000ff, c2 & 0x000000ff) +
 428         ABSDIFF((c1 & 0x0000ff00) >> 8 , (c2 & 0x0000ff00) >> 8) +
 429         ABSDIFF((c1 & 0x00ff0000) >> 16, (c2 & 0x00ff0000) >> 16);
 430 }
 431
 432 static inline int pixel_color7_fast(Palette * palette, unsigned c15)
 433 {
 434     return palette->index[c15];
 435 }
 436
 437 static int pixel_color7_slow(Palette * palette, unsigned color)
 438 {
 439     int i, min = 0x7fffffff;
 440     int minc = -1;
 441     for (i = 0; i < 128; i++) {
 442         int c1 = palette->colors[i];
 443         int diff = chroma_diff(c1, color);
 444         if (diff < min) {
 445             min = diff;
 446             minc = i;
 447         }
 448     }
 449     return minc;
 450 }
 451
 452 static inline unsigned pixel_bgr(const uint8_t * src)
 453 {
 454     return (src[0]) | (src[1] << 8) | (src[2] << 16);
 455 }
 456
 457 static int write_pixel_15_7(Palette * palette, uint8_t * dest, const uint8_t * src,
 458                             int dist)
 459 {
 460     unsigned c15 = pixel_color15(src);
 461     unsigned color = pixel_bgr(src);
 462     int d15 = chroma_diff(color, color & 0x00f8f8f8);
 463     int c7 = pixel_color7_fast(palette, c15);
 464     int d7 = chroma_diff(color, palette->colors[c7]);
 465     if (dist + d15 >= d7) {
 466         dest[0] = c7;
 467         return 1;
 468     } else {
 469         dest[0] = 0x80 | (c15 >> 8);
 470         dest[1] = c15 & 0xff;
 471         return 2;
 472     }
 473 }
 474
 475 static int update_palette_index(Palette * palette)
 476 {
 477     int r, g, b;
 478     unsigned int bgr, c15, index;
 479     for (r = 4; r < 256; r += 8) {
 480         for (g = 4; g < 256; g += 8) {
 481             for (b = 4; b < 256; b += 8) {
 482                 bgr = b | (g << 8) | (r << 16);
 483                 c15 = (b >> 3) | ((g & 0xf8) << 2) | ((r & 0xf8) << 7);
 484                 index = pixel_color7_slow(palette, bgr);
 485
 486                 palette->index[c15] = index;
 487             }
 488         }
 489     }
 490     return 0;
 491 }
 492
 493 static const unsigned int default_screen_video_v2_palette[128] = {
 494     0x00000000, 0x00333333, 0x00666666, 0x00999999, 0x00CCCCCC, 0x00FFFFFF,
 495     0x00330000, 0x00660000, 0x00990000, 0x00CC0000, 0x00FF0000, 0x00003300,
 496     0x00006600, 0x00009900, 0x0000CC00, 0x0000FF00, 0x00000033, 0x00000066,
 497     0x00000099, 0x000000CC, 0x000000FF, 0x00333300, 0x00666600, 0x00999900,
 498     0x00CCCC00, 0x00FFFF00, 0x00003333, 0x00006666, 0x00009999, 0x0000CCCC,
 499     0x0000FFFF, 0x00330033, 0x00660066, 0x00990099, 0x00CC00CC, 0x00FF00FF,
 500     0x00FFFF33, 0x00FFFF66, 0x00FFFF99, 0x00FFFFCC, 0x00FF33FF, 0x00FF66FF,
 501     0x00FF99FF, 0x00FFCCFF, 0x0033FFFF, 0x0066FFFF, 0x0099FFFF, 0x00CCFFFF,
 502     0x00CCCC33, 0x00CCCC66, 0x00CCCC99, 0x00CCCCFF, 0x00CC33CC, 0x00CC66CC,
 503     0x00CC99CC, 0x00CCFFCC, 0x0033CCCC, 0x0066CCCC, 0x0099CCCC, 0x00FFCCCC,
 504     0x00999933, 0x00999966, 0x009999CC, 0x009999FF, 0x00993399, 0x00996699,
 505     0x0099CC99, 0x0099FF99, 0x00339999, 0x00669999, 0x00CC9999, 0x00FF9999,
 506     0x00666633, 0x00666699, 0x006666CC, 0x006666FF, 0x00663366, 0x00669966,
 507     0x0066CC66, 0x0066FF66, 0x00336666, 0x00996666, 0x00CC6666, 0x00FF6666,
 508     0x00333366, 0x00333399, 0x003333CC, 0x003333FF, 0x00336633, 0x00339933,
 509     0x0033CC33, 0x0033FF33, 0x00663333, 0x00993333, 0x00CC3333, 0x00FF3333,
 510     0x00003366, 0x00336600, 0x00660033, 0x00006633, 0x00330066, 0x00663300,
 511     0x00336699, 0x00669933, 0x00993366, 0x00339966, 0x00663399, 0x00996633,
 512     0x006699CC, 0x0099CC66, 0x00CC6699, 0x0066CC99, 0x009966CC, 0x00CC9966,
 513     0x0099CCFF, 0x00CCFF99, 0x00FF99CC, 0x0099FFCC, 0x00CC99FF, 0x00FFCC99,
 514     0x00111111, 0x00222222, 0x00444444, 0x00555555, 0x00AAAAAA, 0x00BBBBBB,
 515     0x00DDDDDD, 0x00EEEEEE
 516 };
 517
 518 static int generate_default_palette(Palette * palette)
 519 {
 520     memcpy(palette->colors, default_screen_video_v2_palette,
 521            sizeof(default_screen_video_v2_palette));
 522
 523     return update_palette_index(palette);
 524 }
 525
 526 static int generate_optimum_palette(Palette * palette, const uint8_t * image,
 527                                    int width, int height, int stride)
 528 {
 529     //this isn't implemented yet!  Default palette only!
 530     return -1;
 531 }
 532
 533 static inline int encode_15_7_sl(Palette * palette, uint8_t * dest,
 534                                  const uint8_t * src, int width, int dist)
 535 {
 536     int len = 0, x;
 537     for (x = 0; x < width; x++) {
 538         len += write_pixel_15_7(palette, dest + len, src + 3 * x, dist);
 539     }
 540     return len;
 541 }
 542
 543 static int encode_15_7(Palette * palette, Block * b, const uint8_t * src,
 544                        int stride, int dist)
 545 {
 546     int i;
 547     uint8_t *ptr = b->enc;
 548     for (i = 0; i < b->start; i++)
 549         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 550     b->sl_begin = ptr;
 551     for (; i < b->start + b->len; i++)
 552         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 553     b->sl_end = ptr;
 554     for (; i < b->height; i++)
 555         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 556     b->enc_size = ptr - b->enc;
 557     return b->enc_size;
 558 }
 559
 560 static int encode_block(FlashSV2Context *s, Palette * palette, Block * b,
 561                         Block * prev, const uint8_t * src, int stride, int comp,
 562                         int dist, int keyframe)
 563 {
 564     unsigned buf_size = b->width * b->height * 6;
 565     uint8_t *buf = s->blockbuffer;
 566     int res;
 567
 568     if (b->flags & COLORSPACE_15_7) {
 569         encode_15_7(palette, b, src, stride, dist);
 570     } else {
 571         encode_bgr(b, src, stride);
 572     }
 573
 574     if (b->len > 0) {
 575         b->data_size = buf_size;
 576         res = encode_zlib(b, b->data, &b->data_size, comp);
 577         if (res)
 578             return res;
 579
 580         if (!keyframe) {
 581             res = encode_zlibprime(b, prev, buf, &buf_size, comp);
 582             if (res)
 583                 return res;
 584
 585             if (buf_size < b->data_size) {
 586                 b->data_size = buf_size;
 587                 memcpy(b->data, buf, buf_size);
 588                 b->flags |= ZLIB_PRIME_COMPRESS_PREVIOUS;
 589             }
 590         }
 591     } else {
 592         b->data_size = 0;
 593     }
 594     return 0;
 595 }
 596
 597 static int compare_sl(FlashSV2Context * s, Block * b, const uint8_t * src,
 598                       uint8_t * frame, uint8_t * key, int y, int keyframe)
 599 {
 600     if (memcmp(src, frame, b->width * 3) != 0) {
 601         b->dirty = 1;
 602         memcpy(frame, src, b->width * 3);
 603 #ifndef FLASHSV2_DUMB
 604         s->diff_lines++;
 605 #endif
 606     }
 607     if (memcmp(src, key, b->width * 3) != 0) {
 608         if (b->len == 0)
 609             b->start = y;
 610         b->len = y + 1 - b->start;
 611     }
 612     return 0;
 613 }
 614
 615 static int mark_all_blocks(FlashSV2Context * s, const uint8_t * src, int stride,
 616                            int keyframe)
 617 {
 618     int sl, rsl, col, pos, possl;
 619     Block *b;
 620     for (sl = s->image_height - 1; sl >= 0; sl--) {
 621         for (col = 0; col < s->cols; col++) {
 622             rsl = s->image_height - sl - 1;
 623             b = s->frame_blocks + col + rsl / s->block_height * s->cols;
 624             possl = stride * sl + col * s->block_width * 3;
 625             pos = s->image_width * rsl * 3 + col * s->block_width * 3;
 626             compare_sl(s, b, src + possl, s->current_frame + pos,
 627                        s->key_frame + pos, rsl % s->block_height, keyframe);
 628         }
 629     }
 630 #ifndef FLASHSV2_DUMB
 631     s->tot_lines += s->image_height * s->cols;
 632 #endif
 633     return 0;
 634 }
 635
 636 static int encode_all_blocks(FlashSV2Context * s, int keyframe)
 637 {
 638     int row, col, res;
 639     uint8_t *data;
 640     Block *b, *prev;
 641     for (row = 0; row < s->rows; row++) {
 642         for (col = 0; col < s->cols; col++) {
 643             b = s->frame_blocks + (row * s->cols + col);
 644             prev = s->key_blocks + (row * s->cols + col);
 645             b->flags = s->use15_7 ? COLORSPACE_15_7 : 0;
 646             if (keyframe) {
 647                 b->start = 0;
 648                 b->len = b->height;
 649             } else if (!b->dirty) {
 650                 b->start = 0;
 651                 b->len = 0;
 652                 b->data_size = 0;
 653                 continue;
 654             } else if (b->start != 0 || b->len != b->height) {
 655                 b->flags |= HAS_DIFF_BLOCKS;
 656             }
 657             data = s->current_frame + s->image_width * 3 * s->block_height * row + s->block_width * col * 3;
 658             res = encode_block(s, &s->palette, b, prev, data, s->image_width * 3, s->comp, s->dist, keyframe);
 659 #ifndef FLASHSV2_DUMB
 660             if (b->dirty)
 661                 s->diff_blocks++;
 662             s->comp_size += b->data_size;
 663             s->uncomp_size += b->enc_size;
 664 #endif
 665             if (res)
 666                 return res;
 667         }
 668     }
 669 #ifndef FLASHSV2_DUMB
 670     s->raw_size += s->image_width * s->image_height * 3;
 671     s->tot_blocks += s->rows * s->cols;
 672 #endif
 673     return 0;
 674 }
 675
 676 static int write_all_blocks(FlashSV2Context * s, uint8_t * buf,
 677                             int buf_size)
 678 {
 679     int row, col, buf_pos = 0, len;
 680     Block *b;
 681     for (row = 0; row < s->rows; row++) {
 682         for (col = 0; col < s->cols; col++) {
 683             b = s->frame_blocks + row * s->cols + col;
 684             len = write_block(b, buf + buf_pos, buf_size - buf_pos);
 685             b->start = b->len = b->dirty = 0;
 686             if (len < 0)
 687                 return len;
 688             buf_pos += len;
 689         }
 690     }
 691     return buf_pos;
 692 }
 693
 694 static int write_bitstream(FlashSV2Context * s, const uint8_t * src, int stride,
 695                            uint8_t * buf, int buf_size, int keyframe)
 696 {
 697     int buf_pos, res;
 698
 699     res = mark_all_blocks(s, src, stride, keyframe);
 700     if (res)
 701         return res;
 702     res = encode_all_blocks(s, keyframe);
 703     if (res)
 704         return res;
 705
 706     res = write_header(s, buf, buf_size);
 707     if (res < 0) {
 708         return res;
 709     } else {
 710         buf_pos = res;
 711     }
 712     res = write_all_blocks(s, buf + buf_pos, buf_size - buf_pos);
 713     if (res < 0)
 714         return res;
 715     buf_pos += res;
 716 #ifndef FLASHSV2_DUMB
 717     s->total_bits += ((double) buf_pos) * 8.0;
 718 #endif
 719
 720     return buf_pos;
 721 }
 722
 723 static void recommend_keyframe(FlashSV2Context * s, int *keyframe)
 724 {
 725 #ifndef FLASHSV2_DUMB
 726     double block_ratio, line_ratio, enc_ratio, comp_ratio, data_ratio;
 727     if (s->avctx->gop_size > 0) {
 728         block_ratio = s->diff_blocks / s->tot_blocks;
 729         line_ratio = s->diff_lines / s->tot_lines;
 730         enc_ratio = s->uncomp_size / s->raw_size;
 731         comp_ratio = s->comp_size / s->uncomp_size;
 732         data_ratio = s->comp_size / s->raw_size;
 733
 734         if ((block_ratio >= 0.5 && line_ratio / block_ratio <= 0.5) || line_ratio >= 0.95) {
 735             *keyframe = 1;
 736             return;
 737         }
 738     }
 739 #else
 740     return;
 741 #endif
 742 }
 743
 744 #ifndef FLASHSV2_DUMB
 745 static const double block_size_fraction = 1.0 / 300;
 746 static const double use15_7_threshold = 8192;
 747 static const double color15_7_factor = 100;
 748 #endif
 749 static int optimum_block_width(FlashSV2Context * s)
 750 {
 751 #ifndef FLASHSV2_DUMB
 752     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
 753     double width = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_width;
 754     int pwidth = ((int) width);
 755     return FFCLIP(pwidth & ~15, 256, 16);
 756 #else
 757     return 64;
 758 #endif
 759 }
 760
 761 static int optimum_block_height(FlashSV2Context * s)
 762 {
 763 #ifndef FLASHSV2_DUMB
 764     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
 765     double height = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_height;
 766     int pheight = ((int) height);
 767     return FFCLIP(pheight & ~15, 256, 16);
 768 #else
 769     return 64;
 770 #endif
 771 }
 772
 773 static int optimum_use15_7(FlashSV2Context * s)
 774 {
 775 #ifndef FLASHSV2_DUMB
 776     double ideal = ((double)(s->avctx->bit_rate * s->avctx->time_base.den * s->avctx->ticks_per_frame)) /
 777         ((double) s->avctx->time_base.num) * s->avctx->frame_number;
 778     if (ideal + use15_7_threshold < s->total_bits) {
 779         return 1;
 780     } else {
 781         return 0;
 782     }
 783 #else
 784     return s->avctx->global_quality == 0;
 785 #endif
 786 }
 787
 788 static int optimum_dist(FlashSV2Context * s)
 789 {
 790 #ifndef FLASHSV2_DUMB
 791     double ideal =
 792         s->avctx->bit_rate * s->avctx->time_base.den *
 793         s->avctx->ticks_per_frame;
 794     int dist = pow((s->total_bits / ideal) * color15_7_factor, 3);
 795     av_log(s->avctx, AV_LOG_DEBUG, "dist: %d\n", dist);
 796     return dist;
 797 #else
 798     return 15;
 799 #endif
 800 }
 801
 802
 803 static int reconfigure_at_keyframe(FlashSV2Context * s, const uint8_t * image,
 804                                    int stride)
 805 {
 806     int update_palette = 0;
 807     int res;
 808     int block_width  = optimum_block_width (s);
 809     int block_height = optimum_block_height(s);
 810
 811     if (block_width != s->block_width || block_height != s->block_height) {
 812         res = update_block_dimensions(s, block_width, block_height);
 813         if (res < 0)
 814             return res;
 815     }
 816
 817     s->use15_7 = optimum_use15_7(s);
 818     if (s->use15_7) {
 819         if ((s->use_custom_palette && s->palette_type != 1) || update_palette) {
 820             res = generate_optimum_palette(&s->palette, image, s->image_width, s->image_height, stride);
 821             if (res)
 822                 return res;
 823             s->palette_type = 1;
 824             av_log(s->avctx, AV_LOG_DEBUG, "Generated optimum palette\n");
 825         } else if (!s->use_custom_palette && s->palette_type != 0) {
 826             res = generate_default_palette(&s->palette);
 827             if (res)
 828                 return res;
 829             s->palette_type = 0;
 830             av_log(s->avctx, AV_LOG_DEBUG, "Generated default palette\n");
 831         }
 832     }
 833
 834
 835     reset_stats(s);
 836
 837     return 0;
 838 }
 839
 840 static int flashsv2_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
 841                                  const AVFrame *p, int *got_packet)
 842 {
 843     FlashSV2Context *const s = avctx->priv_data;
 844     int res;
 845     int keyframe = 0;
 846
 847     if ((res = ff_alloc_packet2(avctx, pkt, s->frame_size + AV_INPUT_BUFFER_MIN_SIZE, 0)) < 0)
 848         return res;
 849
 850     /* First frame needs to be a keyframe */
 851     if (avctx->frame_number == 0)
 852         keyframe = 1;
 853
 854     /* Check the placement of keyframes */
 855     if (avctx->gop_size > 0) {
 856         if (avctx->frame_number >= s->last_key_frame + avctx->gop_size)
 857             keyframe = 1;
 858     }
 859
 860     if (!keyframe
 861         && avctx->frame_number > s->last_key_frame + avctx->keyint_min) {
 862         recommend_keyframe(s, &keyframe);
 863         if (keyframe)
 864             av_log(avctx, AV_LOG_DEBUG, "Recommending key frame at frame %d\n", avctx->frame_number);
 865     }
 866
 867     if (keyframe) {
 868         res = reconfigure_at_keyframe(s, p->data[0], p->linesize[0]);
 869         if (res)
 870             return res;
 871     }
 872
 873     if (s->use15_7)
 874         s->dist = optimum_dist(s);
 875
 876     res = write_bitstream(s, p->data[0], p->linesize[0], pkt->data, pkt->size, keyframe);
 877
 878     if (keyframe) {
 879         new_key_frame(s);
 880         s->last_key_frame = avctx->frame_number;
 881         pkt->flags |= AV_PKT_FLAG_KEY;
 882         av_log(avctx, AV_LOG_DEBUG, "Inserting key frame at frame %d\n", avctx->frame_number);
 883     }
 884
 885     pkt->size = res;
 886     *got_packet = 1;
 887
 888     return 0;
 889 }
 890
 891 static av_cold int flashsv2_encode_end(AVCodecContext * avctx)
 892 {
 893     FlashSV2Context *s = avctx->priv_data;
 894
 895     cleanup(s);
 896
 897     return 0;
 898 }
 899
 900 AVCodec ff_flashsv2_encoder = {
 901     .name           = "flashsv2",
 902     .long_name      = NULL_IF_CONFIG_SMALL("Flash Screen Video Version 2"),
 903     .type           = AVMEDIA_TYPE_VIDEO,
 904     .id             = AV_CODEC_ID_FLASHSV2,
 905     .priv_data_size = sizeof(FlashSV2Context),
 906     .init           = flashsv2_encode_init,
 907     .encode2        = flashsv2_encode_frame,
 908     .close          = flashsv2_encode_end,
 909     .pix_fmts       = (const enum AVPixelFormat[]){ AV_PIX_FMT_BGR24, AV_PIX_FMT_NONE },
 910     .caps_internal  = FF_CODEC_CAP_INIT_CLEANUP,
 911 };