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     AVFrame frame;
  91     uint8_t *encbuffer;
  92     uint8_t *keybuffer;
  93     uint8_t *databuffer;
  94
  95     uint8_t *blockbuffer;
  96     int blockbuffer_size;
  97
  98     Block *frame_blocks;
  99     Block *key_blocks;
 100     int frame_size;
 101     int blocks_size;
 102
 103     int use15_7, dist, comp;
 104
 105     int rows, cols;
 106
 107     int last_key_frame;
 108
 109     int image_width, image_height;
 110     int block_width, block_height;
 111     uint8_t flags;
 112     uint8_t use_custom_palette;
 113     uint8_t palette_type;       ///< 0=>default, 1=>custom - changed when palette regenerated.
 114     Palette palette;
 115 #ifndef FLASHSV2_DUMB
 116     double tot_blocks;          ///< blocks encoded since last keyframe
 117     double diff_blocks;         ///< blocks that were different since last keyframe
 118     double tot_lines;           ///< total scanlines in image since last keyframe
 119     double diff_lines;          ///< scanlines that were different since last keyframe
 120     double raw_size;            ///< size of raw frames since last keyframe
 121     double comp_size;           ///< size of compressed data since last keyframe
 122     double uncomp_size;         ///< size of uncompressed data since last keyframe
 123
 124     double total_bits;          ///< total bits written to stream so far
 125 #endif
 126 } FlashSV2Context;
 127
 128 static av_cold void cleanup(FlashSV2Context * s)
 129 {
 130     av_freep(&s->encbuffer);
 131     av_freep(&s->keybuffer);
 132     av_freep(&s->databuffer);
 133     av_freep(&s->blockbuffer);
 134     av_freep(&s->current_frame);
 135     av_freep(&s->key_frame);
 136
 137     av_freep(&s->frame_blocks);
 138     av_freep(&s->key_blocks);
 139 }
 140
 141 static void init_blocks(FlashSV2Context * s, Block * blocks,
 142                         uint8_t * encbuf, uint8_t * databuf)
 143 {
 144     int row, col;
 145     Block *b;
 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 ? 0 : b->width * b->height * 6;
 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 av_cold int flashsv2_encode_init(AVCodecContext * avctx)
 179 {
 180     FlashSV2Context *s = avctx->priv_data;
 181
 182     s->avctx = avctx;
 183
 184     s->comp = avctx->compression_level;
 185     if (s->comp == -1)
 186         s->comp = 9;
 187     if (s->comp < 0 || s->comp > 9) {
 188         av_log(avctx, AV_LOG_ERROR,
 189                "Compression level should be 0-9, not %d\n", s->comp);
 190         return -1;
 191     }
 192
 193
 194     if ((avctx->width > 4095) || (avctx->height > 4095)) {
 195         av_log(avctx, AV_LOG_ERROR,
 196                "Input dimensions too large, input must be max 4096x4096 !\n");
 197         return -1;
 198     }
 199     if ((avctx->width < 16) || (avctx->height < 16)) {
 200         av_log(avctx, AV_LOG_ERROR,
 201                "Input dimensions too small, input must be at least 16x16 !\n");
 202         return -1;
 203     }
 204
 205     if (av_image_check_size(avctx->width, avctx->height, 0, avctx) < 0)
 206         return -1;
 207
 208
 209     s->last_key_frame = 0;
 210
 211     s->image_width  = avctx->width;
 212     s->image_height = avctx->height;
 213
 214     s->block_width  = (s->image_width /  12) & ~15;
 215     s->block_height = (s->image_height / 12) & ~15;
 216
 217     if(!s->block_width)
 218         s->block_width = 1;
 219     if(!s->block_height)
 220         s->block_height = 1;
 221
 222     s->rows = (s->image_height + s->block_height - 1) / s->block_height;
 223     s->cols = (s->image_width +  s->block_width -  1) / s->block_width;
 224
 225     s->frame_size  = s->image_width * s->image_height * 3;
 226     s->blocks_size = s->rows * s->cols * sizeof(Block);
 227
 228     s->encbuffer     = av_mallocz(s->frame_size);
 229     s->keybuffer     = av_mallocz(s->frame_size);
 230     s->databuffer    = av_mallocz(s->frame_size * 6);
 231     s->current_frame = av_mallocz(s->frame_size);
 232     s->key_frame     = av_mallocz(s->frame_size);
 233     s->frame_blocks  = av_mallocz(s->blocks_size);
 234     s->key_blocks    = av_mallocz(s->blocks_size);
 235
 236     s->blockbuffer      = NULL;
 237     s->blockbuffer_size = 0;
 238
 239     init_blocks(s, s->frame_blocks, s->encbuffer, s->databuffer);
 240     init_blocks(s, s->key_blocks,   s->keybuffer, 0);
 241     reset_stats(s);
 242 #ifndef FLASHSV2_DUMB
 243     s->total_bits = 1;
 244 #endif
 245
 246     s->use_custom_palette =  0;
 247     s->palette_type       = -1;        // so that the palette will be generated in reconfigure_at_keyframe
 248
 249     if (!s->encbuffer || !s->keybuffer || !s->databuffer
 250         || !s->current_frame || !s->key_frame || !s->key_blocks
 251         || !s->frame_blocks) {
 252         av_log(avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
 253         cleanup(s);
 254         return -1;
 255     }
 256
 257     return 0;
 258 }
 259
 260 static int new_key_frame(FlashSV2Context * s)
 261 {
 262     int i;
 263     memcpy(s->key_blocks, s->frame_blocks, s->blocks_size);
 264     memcpy(s->key_frame, s->current_frame, s->frame_size);
 265
 266     for (i = 0; i < s->rows * s->cols; i++) {
 267         s->key_blocks[i].enc += (s->keybuffer - s->encbuffer);
 268         s->key_blocks[i].sl_begin = 0;
 269         s->key_blocks[i].sl_end   = 0;
 270         s->key_blocks[i].data     = 0;
 271     }
 272     memcpy(s->keybuffer, s->encbuffer, s->frame_size);
 273
 274     return 0;
 275 }
 276
 277 static int write_palette(FlashSV2Context * s, uint8_t * buf, int buf_size)
 278 {
 279     //this isn't implemented yet!  Default palette only!
 280     return -1;
 281 }
 282
 283 static int write_header(FlashSV2Context * s, uint8_t * buf, int buf_size)
 284 {
 285     PutBitContext pb;
 286     int buf_pos, len;
 287
 288     if (buf_size < 5)
 289         return -1;
 290
 291     init_put_bits(&pb, buf, buf_size * 8);
 292
 293     put_bits(&pb, 4, (s->block_width  >> 4) - 1);
 294     put_bits(&pb, 12, s->image_width);
 295     put_bits(&pb, 4, (s->block_height >> 4) - 1);
 296     put_bits(&pb, 12, s->image_height);
 297
 298     flush_put_bits(&pb);
 299     buf_pos = 4;
 300
 301     buf[buf_pos++] = s->flags;
 302
 303     if (s->flags & HAS_PALLET_INFO) {
 304         len = write_palette(s, buf + buf_pos, buf_size - buf_pos);
 305         if (len < 0)
 306             return -1;
 307         buf_pos += len;
 308     }
 309
 310     return buf_pos;
 311 }
 312
 313 static int write_block(Block * b, uint8_t * buf, int buf_size)
 314 {
 315     int buf_pos = 0;
 316     unsigned block_size = b->data_size;
 317
 318     if (b->flags & HAS_DIFF_BLOCKS)
 319         block_size += 2;
 320     if (b->flags & ZLIB_PRIME_COMPRESS_CURRENT)
 321         block_size += 2;
 322     if (block_size > 0)
 323         block_size += 1;
 324     if (buf_size < block_size + 2)
 325         return -1;
 326
 327     buf[buf_pos++] = block_size >> 8;
 328     buf[buf_pos++] = block_size;
 329
 330     if (block_size == 0)
 331         return buf_pos;
 332
 333     buf[buf_pos++] = b->flags;
 334
 335     if (b->flags & HAS_DIFF_BLOCKS) {
 336         buf[buf_pos++] = (b->start);
 337         buf[buf_pos++] = (b->len);
 338     }
 339
 340     if (b->flags & ZLIB_PRIME_COMPRESS_CURRENT) {
 341         //This feature of the format is poorly understood, and as of now, unused.
 342         buf[buf_pos++] = (b->col);
 343         buf[buf_pos++] = (b->row);
 344     }
 345
 346     memcpy(buf + buf_pos, b->data, b->data_size);
 347
 348     buf_pos += b->data_size;
 349
 350     return buf_pos;
 351 }
 352
 353 static int encode_zlib(Block * b, uint8_t * buf, unsigned long *buf_size, int comp)
 354 {
 355     int res = compress2(buf, buf_size, b->sl_begin, b->sl_end - b->sl_begin, comp);
 356     return res == Z_OK ? 0 : -1;
 357 }
 358
 359 static int encode_zlibprime(Block * b, Block * prime, uint8_t * buf,
 360                             int *buf_size, int comp)
 361 {
 362     z_stream s;
 363     int res;
 364     s.zalloc = NULL;
 365     s.zfree  = NULL;
 366     s.opaque = NULL;
 367     res = deflateInit(&s, comp);
 368     if (res < 0)
 369         return -1;
 370
 371     s.next_in  = prime->enc;
 372     s.avail_in = prime->enc_size;
 373     while (s.avail_in > 0) {
 374         s.next_out  = buf;
 375         s.avail_out = *buf_size;
 376         res = deflate(&s, Z_SYNC_FLUSH);
 377         if (res < 0)
 378             return -1;
 379     }
 380
 381     s.next_in   = b->sl_begin;
 382     s.avail_in  = b->sl_end - b->sl_begin;
 383     s.next_out  = buf;
 384     s.avail_out = *buf_size;
 385     res = deflate(&s, Z_FINISH);
 386     deflateEnd(&s);
 387     *buf_size -= s.avail_out;
 388     if (res != Z_STREAM_END)
 389         return -1;
 390     return 0;
 391 }
 392
 393 static int encode_bgr(Block * b, const uint8_t * src, int stride)
 394 {
 395     int i;
 396     uint8_t *ptr = b->enc;
 397     for (i = 0; i < b->start; i++)
 398         memcpy(ptr + i * b->width * 3, src + i * stride, b->width * 3);
 399     b->sl_begin = ptr + i * b->width * 3;
 400     for (; i < b->start + b->len; i++)
 401         memcpy(ptr + i * b->width * 3, src + i * stride, b->width * 3);
 402     b->sl_end = ptr + i * b->width * 3;
 403     for (; i < b->height; i++)
 404         memcpy(ptr + i * b->width * 3, src + i * stride, b->width * 3);
 405     b->enc_size = ptr + i * b->width * 3 - b->enc;
 406     return b->enc_size;
 407 }
 408
 409 static inline unsigned pixel_color15(const uint8_t * src)
 410 {
 411     return (src[0] >> 3) | ((src[1] & 0xf8) << 2) | ((src[2] & 0xf8) << 7);
 412 }
 413
 414 static inline unsigned int chroma_diff(unsigned int c1, unsigned int c2)
 415 {
 416     unsigned int t1 = (c1 & 0x000000ff) + ((c1 & 0x0000ff00) >> 8) + ((c1 & 0x00ff0000) >> 16);
 417     unsigned int t2 = (c2 & 0x000000ff) + ((c2 & 0x0000ff00) >> 8) + ((c2 & 0x00ff0000) >> 16);
 418
 419     return abs(t1 - t2) + abs((c1 & 0x000000ff) - (c2 & 0x000000ff)) +
 420         abs(((c1 & 0x0000ff00) >> 8) - ((c2 & 0x0000ff00) >> 8)) +
 421         abs(((c1 & 0x00ff0000) >> 16) - ((c2 & 0x00ff0000) >> 16));
 422 }
 423
 424 static inline int pixel_color7_fast(Palette * palette, unsigned c15)
 425 {
 426     return palette->index[c15];
 427 }
 428
 429 static int pixel_color7_slow(Palette * palette, unsigned color)
 430 {
 431     int i, min = 0x7fffffff;
 432     int minc = -1;
 433     for (i = 0; i < 128; i++) {
 434         int c1 = palette->colors[i];
 435         int diff = chroma_diff(c1, color);
 436         if (diff < min) {
 437             min = diff;
 438             minc = i;
 439         }
 440     }
 441     return minc;
 442 }
 443
 444 static inline unsigned pixel_bgr(const uint8_t * src)
 445 {
 446     return (src[0]) | (src[1] << 8) | (src[2] << 16);
 447 }
 448
 449 static int write_pixel_15_7(Palette * palette, uint8_t * dest, const uint8_t * src,
 450                             int dist)
 451 {
 452     unsigned c15 = pixel_color15(src);
 453     unsigned color = pixel_bgr(src);
 454     int d15 = chroma_diff(color, color & 0x00f8f8f8);
 455     int c7 = pixel_color7_fast(palette, c15);
 456     int d7 = chroma_diff(color, palette->colors[c7]);
 457     if (dist + d15 >= d7) {
 458         dest[0] = c7;
 459         return 1;
 460     } else {
 461         dest[0] = 0x80 | (c15 >> 8);
 462         dest[1] = c15 & 0xff;
 463         return 2;
 464     }
 465 }
 466
 467 static int update_palette_index(Palette * palette)
 468 {
 469     int r, g, b;
 470     unsigned int bgr, c15, index;
 471     for (r = 4; r < 256; r += 8) {
 472         for (g = 4; g < 256; g += 8) {
 473             for (b = 4; b < 256; b += 8) {
 474                 bgr = b | (g << 8) | (r << 16);
 475                 c15 = (b >> 3) | ((g & 0xf8) << 2) | ((r & 0xf8) << 7);
 476                 index = pixel_color7_slow(palette, bgr);
 477
 478                 palette->index[c15] = index;
 479             }
 480         }
 481     }
 482     return 0;
 483 }
 484
 485 static const unsigned int default_screen_video_v2_palette[128] = {
 486     0x00000000, 0x00333333, 0x00666666, 0x00999999, 0x00CCCCCC, 0x00FFFFFF,
 487     0x00330000, 0x00660000, 0x00990000, 0x00CC0000, 0x00FF0000, 0x00003300,
 488     0x00006600, 0x00009900, 0x0000CC00, 0x0000FF00, 0x00000033, 0x00000066,
 489     0x00000099, 0x000000CC, 0x000000FF, 0x00333300, 0x00666600, 0x00999900,
 490     0x00CCCC00, 0x00FFFF00, 0x00003333, 0x00006666, 0x00009999, 0x0000CCCC,
 491     0x0000FFFF, 0x00330033, 0x00660066, 0x00990099, 0x00CC00CC, 0x00FF00FF,
 492     0x00FFFF33, 0x00FFFF66, 0x00FFFF99, 0x00FFFFCC, 0x00FF33FF, 0x00FF66FF,
 493     0x00FF99FF, 0x00FFCCFF, 0x0033FFFF, 0x0066FFFF, 0x0099FFFF, 0x00CCFFFF,
 494     0x00CCCC33, 0x00CCCC66, 0x00CCCC99, 0x00CCCCFF, 0x00CC33CC, 0x00CC66CC,
 495     0x00CC99CC, 0x00CCFFCC, 0x0033CCCC, 0x0066CCCC, 0x0099CCCC, 0x00FFCCCC,
 496     0x00999933, 0x00999966, 0x009999CC, 0x009999FF, 0x00993399, 0x00996699,
 497     0x0099CC99, 0x0099FF99, 0x00339999, 0x00669999, 0x00CC9999, 0x00FF9999,
 498     0x00666633, 0x00666699, 0x006666CC, 0x006666FF, 0x00663366, 0x00669966,
 499     0x0066CC66, 0x0066FF66, 0x00336666, 0x00996666, 0x00CC6666, 0x00FF6666,
 500     0x00333366, 0x00333399, 0x003333CC, 0x003333FF, 0x00336633, 0x00339933,
 501     0x0033CC33, 0x0033FF33, 0x00663333, 0x00993333, 0x00CC3333, 0x00FF3333,
 502     0x00003366, 0x00336600, 0x00660033, 0x00006633, 0x00330066, 0x00663300,
 503     0x00336699, 0x00669933, 0x00993366, 0x00339966, 0x00663399, 0x00996633,
 504     0x006699CC, 0x0099CC66, 0x00CC6699, 0x0066CC99, 0x009966CC, 0x00CC9966,
 505     0x0099CCFF, 0x00CCFF99, 0x00FF99CC, 0x0099FFCC, 0x00CC99FF, 0x00FFCC99,
 506     0x00111111, 0x00222222, 0x00444444, 0x00555555, 0x00AAAAAA, 0x00BBBBBB,
 507     0x00DDDDDD, 0x00EEEEEE
 508 };
 509
 510 static int generate_default_palette(Palette * palette)
 511 {
 512     memcpy(palette->colors, default_screen_video_v2_palette,
 513            sizeof(default_screen_video_v2_palette));
 514
 515     return update_palette_index(palette);
 516 }
 517
 518 static int generate_optimum_palette(Palette * palette, const uint8_t * image,
 519                                    int width, int height, int stride)
 520 {
 521     //this isn't implemented yet!  Default palette only!
 522     return -1;
 523 }
 524
 525 static inline int encode_15_7_sl(Palette * palette, uint8_t * dest,
 526                                  const uint8_t * src, int width, int dist)
 527 {
 528     int len = 0, x;
 529     for (x = 0; x < width; x++) {
 530         len += write_pixel_15_7(palette, dest + len, src + 3 * x, dist);
 531     }
 532     return len;
 533 }
 534
 535 static int encode_15_7(Palette * palette, Block * b, const uint8_t * src,
 536                        int stride, int dist)
 537 {
 538     int i;
 539     uint8_t *ptr = b->enc;
 540     for (i = 0; i < b->start; i++)
 541         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 542     b->sl_begin = ptr;
 543     for (; i < b->start + b->len; i++)
 544         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 545     b->sl_end = ptr;
 546     for (; i < b->height; i++)
 547         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 548     b->enc_size = ptr - b->enc;
 549     return b->enc_size;
 550 }
 551
 552 static int encode_block(FlashSV2Context *s, Palette * palette, Block * b,
 553                         Block * prev, const uint8_t * src, int stride, int comp,
 554                         int dist, int keyframe)
 555 {
 556     unsigned buf_size = b->width * b->height * 6;
 557     uint8_t *buf = s->blockbuffer;
 558     int res;
 559
 560     if (b->flags & COLORSPACE_15_7) {
 561         encode_15_7(palette, b, src, stride, dist);
 562     } else {
 563         encode_bgr(b, src, stride);
 564     }
 565
 566     if (b->len > 0) {
 567         b->data_size = buf_size;
 568         res = encode_zlib(b, b->data, &b->data_size, comp);
 569         if (res)
 570             return res;
 571
 572         if (!keyframe) {
 573             res = encode_zlibprime(b, prev, buf, &buf_size, comp);
 574             if (res)
 575                 return res;
 576
 577             if (buf_size < b->data_size) {
 578                 b->data_size = buf_size;
 579                 memcpy(b->data, buf, buf_size);
 580                 b->flags |= ZLIB_PRIME_COMPRESS_PREVIOUS;
 581             }
 582         }
 583     } else {
 584         b->data_size = 0;
 585     }
 586     return 0;
 587 }
 588
 589 static int compare_sl(FlashSV2Context * s, Block * b, const uint8_t * src,
 590                       uint8_t * frame, uint8_t * key, int y, int keyframe)
 591 {
 592     if (memcmp(src, frame, b->width * 3) != 0) {
 593         b->dirty = 1;
 594         memcpy(frame, src, b->width * 3);
 595 #ifndef FLASHSV2_DUMB
 596         s->diff_lines++;
 597 #endif
 598     }
 599     if (memcmp(src, key, b->width * 3) != 0) {
 600         if (b->len == 0)
 601             b->start = y;
 602         b->len = y + 1 - b->start;
 603     }
 604     return 0;
 605 }
 606
 607 static int mark_all_blocks(FlashSV2Context * s, const uint8_t * src, int stride,
 608                            int keyframe)
 609 {
 610     int sl, rsl, col, pos, possl;
 611     Block *b;
 612     for (sl = s->image_height - 1; sl >= 0; sl--) {
 613         for (col = 0; col < s->cols; col++) {
 614             rsl = s->image_height - sl - 1;
 615             b = s->frame_blocks + col + rsl / s->block_height * s->cols;
 616             possl = stride * sl + col * s->block_width * 3;
 617             pos = s->image_width * rsl * 3 + col * s->block_width * 3;
 618             compare_sl(s, b, src + possl, s->current_frame + pos,
 619                        s->key_frame + pos, rsl % s->block_height, keyframe);
 620         }
 621     }
 622 #ifndef FLASHSV2_DUMB
 623     s->tot_lines += s->image_height * s->cols;
 624 #endif
 625     return 0;
 626 }
 627
 628 static int encode_all_blocks(FlashSV2Context * s, int keyframe)
 629 {
 630     int row, col, res;
 631     uint8_t *data;
 632     Block *b, *prev;
 633     for (row = 0; row < s->rows; row++) {
 634         for (col = 0; col < s->cols; col++) {
 635             b = s->frame_blocks + (row * s->cols + col);
 636             prev = s->key_blocks + (row * s->cols + col);
 637             b->flags = s->use15_7 ? COLORSPACE_15_7 : 0;
 638             if (keyframe) {
 639                 b->start = 0;
 640                 b->len = b->height;
 641             } else if (!b->dirty) {
 642                 b->start = 0;
 643                 b->len = 0;
 644                 b->data_size = 0;
 645                 continue;
 646             } else if (b->start != 0 || b->len != b->height) {
 647                 b->flags |= HAS_DIFF_BLOCKS;
 648             }
 649             data = s->current_frame + s->image_width * 3 * s->block_height * row + s->block_width * col * 3;
 650             res = encode_block(s, &s->palette, b, prev, data, s->image_width * 3, s->comp, s->dist, keyframe);
 651 #ifndef FLASHSV2_DUMB
 652             if (b->dirty)
 653                 s->diff_blocks++;
 654             s->comp_size += b->data_size;
 655             s->uncomp_size += b->enc_size;
 656 #endif
 657             if (res)
 658                 return res;
 659         }
 660     }
 661 #ifndef FLASHSV2_DUMB
 662     s->raw_size += s->image_width * s->image_height * 3;
 663     s->tot_blocks += s->rows * s->cols;
 664 #endif
 665     return 0;
 666 }
 667
 668 static int write_all_blocks(FlashSV2Context * s, uint8_t * buf,
 669                             int buf_size)
 670 {
 671     int row, col, buf_pos = 0, len;
 672     Block *b;
 673     for (row = 0; row < s->rows; row++) {
 674         for (col = 0; col < s->cols; col++) {
 675             b = s->frame_blocks + row * s->cols + col;
 676             len = write_block(b, buf + buf_pos, buf_size - buf_pos);
 677             b->start = b->len = b->dirty = 0;
 678             if (len < 0)
 679                 return len;
 680             buf_pos += len;
 681         }
 682     }
 683     return buf_pos;
 684 }
 685
 686 static int write_bitstream(FlashSV2Context * s, const uint8_t * src, int stride,
 687                            uint8_t * buf, int buf_size, int keyframe)
 688 {
 689     int buf_pos, res;
 690
 691     res = mark_all_blocks(s, src, stride, keyframe);
 692     if (res)
 693         return res;
 694     res = encode_all_blocks(s, keyframe);
 695     if (res)
 696         return res;
 697
 698     res = write_header(s, buf, buf_size);
 699     if (res < 0) {
 700         return res;
 701     } else {
 702         buf_pos = res;
 703     }
 704     res = write_all_blocks(s, buf + buf_pos, buf_size - buf_pos);
 705     if (res < 0)
 706         return res;
 707     buf_pos += res;
 708 #ifndef FLASHSV2_DUMB
 709     s->total_bits += ((double) buf_pos) * 8.0;
 710 #endif
 711
 712     return buf_pos;
 713 }
 714
 715 static void recommend_keyframe(FlashSV2Context * s, int *keyframe)
 716 {
 717 #ifndef FLASHSV2_DUMB
 718     double block_ratio, line_ratio, enc_ratio, comp_ratio, data_ratio;
 719     if (s->avctx->gop_size > 0) {
 720         block_ratio = s->diff_blocks / s->tot_blocks;
 721         line_ratio = s->diff_lines / s->tot_lines;
 722         enc_ratio = s->uncomp_size / s->raw_size;
 723         comp_ratio = s->comp_size / s->uncomp_size;
 724         data_ratio = s->comp_size / s->raw_size;
 725
 726         if ((block_ratio >= 0.5 && line_ratio / block_ratio <= 0.5) || line_ratio >= 0.95) {
 727             *keyframe = 1;
 728             return;
 729         }
 730     }
 731 #else
 732     return;
 733 #endif
 734 }
 735
 736 static const double block_size_fraction = 1.0 / 300;
 737 static int optimum_block_width(FlashSV2Context * s)
 738 {
 739 #ifndef FLASHSV2_DUMB
 740     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
 741     double width = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_width;
 742     int pwidth = ((int) width);
 743     return FFCLIP(pwidth & ~15, 256, 16);
 744 #else
 745     return 64;
 746 #endif
 747 }
 748
 749 static int optimum_block_height(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 height = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_height;
 754     int pheight = ((int) height);
 755     return FFCLIP(pheight & ~15, 256, 16);
 756 #else
 757     return 64;
 758 #endif
 759 }
 760
 761 static const double use15_7_threshold = 8192;
 762
 763 static int optimum_use15_7(FlashSV2Context * s)
 764 {
 765 #ifndef FLASHSV2_DUMB
 766     double ideal = ((double)(s->avctx->bit_rate * s->avctx->time_base.den * s->avctx->ticks_per_frame)) /
 767         ((double) s->avctx->time_base.num) * s->avctx->frame_number;
 768     if (ideal + use15_7_threshold < s->total_bits) {
 769         return 1;
 770     } else {
 771         return 0;
 772     }
 773 #else
 774     return s->avctx->global_quality == 0;
 775 #endif
 776 }
 777
 778 static const double color15_7_factor = 100;
 779
 780 static int optimum_dist(FlashSV2Context * s)
 781 {
 782 #ifndef FLASHSV2_DUMB
 783     double ideal =
 784         s->avctx->bit_rate * s->avctx->time_base.den *
 785         s->avctx->ticks_per_frame;
 786     int dist = pow((s->total_bits / ideal) * color15_7_factor, 3);
 787     av_log(s->avctx, AV_LOG_DEBUG, "dist: %d\n", dist);
 788     return dist;
 789 #else
 790     return 15;
 791 #endif
 792 }
 793
 794
 795 static int reconfigure_at_keyframe(FlashSV2Context * s, const uint8_t * image,
 796                                    int stride)
 797 {
 798     int update_palette = 0;
 799     int res;
 800     int block_width  = optimum_block_width (s);
 801     int block_height = optimum_block_height(s);
 802
 803     s->rows = (s->image_height + block_height - 1) / block_height;
 804     s->cols = (s->image_width  + block_width  - 1) / block_width;
 805
 806     if (block_width != s->block_width || block_height != s->block_height) {
 807         s->block_width  = block_width;
 808         s->block_height = block_height;
 809         if (s->rows * s->cols > s->blocks_size / sizeof(Block)) {
 810             s->frame_blocks = av_realloc(s->frame_blocks, s->rows * s->cols * sizeof(Block));
 811             s->key_blocks = av_realloc(s->key_blocks, s->cols * s->rows * sizeof(Block));
 812             if (!s->frame_blocks || !s->key_blocks) {
 813                 av_log(s->avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
 814                 return -1;
 815             }
 816             s->blocks_size = s->rows * s->cols * sizeof(Block);
 817         }
 818         init_blocks(s, s->frame_blocks, s->encbuffer, s->databuffer);
 819         init_blocks(s, s->key_blocks, s->keybuffer, 0);
 820
 821         av_fast_malloc(&s->blockbuffer, &s->blockbuffer_size, block_width * block_height * 6);
 822         if (!s->blockbuffer) {
 823             av_log(s->avctx, AV_LOG_ERROR, "Could not allocate block buffer.\n");
 824             return AVERROR(ENOMEM);
 825         }
 826     }
 827
 828     s->use15_7 = optimum_use15_7(s);
 829     if (s->use15_7) {
 830         if ((s->use_custom_palette && s->palette_type != 1) || update_palette) {
 831             res = generate_optimum_palette(&s->palette, image, s->image_width, s->image_height, stride);
 832             if (res)
 833                 return res;
 834             s->palette_type = 1;
 835             av_log(s->avctx, AV_LOG_DEBUG, "Generated optimum palette\n");
 836         } else if (!s->use_custom_palette && s->palette_type != 0) {
 837             res = generate_default_palette(&s->palette);
 838             if (res)
 839                 return res;
 840             s->palette_type = 0;
 841             av_log(s->avctx, AV_LOG_DEBUG, "Generated default palette\n");
 842         }
 843     }
 844
 845
 846     reset_stats(s);
 847
 848     return 0;
 849 }
 850
 851 static int flashsv2_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
 852                                  const AVFrame *pict, int *got_packet)
 853 {
 854     FlashSV2Context *const s = avctx->priv_data;
 855     AVFrame *const p = &s->frame;
 856     int res;
 857     int keyframe = 0;
 858
 859     *p = *pict;
 860
 861     if ((res = ff_alloc_packet2(avctx, pkt, s->frame_size + FF_MIN_BUFFER_SIZE)) < 0)
 862         return res;
 863
 864     /* First frame needs to be a keyframe */
 865     if (avctx->frame_number == 0)
 866         keyframe = 1;
 867
 868     /* Check the placement of keyframes */
 869     if (avctx->gop_size > 0) {
 870         if (avctx->frame_number >= s->last_key_frame + avctx->gop_size)
 871             keyframe = 1;
 872     }
 873
 874     if (!keyframe
 875         && avctx->frame_number > s->last_key_frame + avctx->keyint_min) {
 876         recommend_keyframe(s, &keyframe);
 877         if (keyframe)
 878             av_log(avctx, AV_LOG_DEBUG, "Recommending key frame at frame %d\n", avctx->frame_number);
 879     }
 880
 881     if (keyframe) {
 882         res = reconfigure_at_keyframe(s, p->data[0], p->linesize[0]);
 883         if (res)
 884             return res;
 885     }
 886
 887     if (s->use15_7)
 888         s->dist = optimum_dist(s);
 889
 890     res = write_bitstream(s, p->data[0], p->linesize[0], pkt->data, pkt->size, keyframe);
 891
 892     if (keyframe) {
 893         new_key_frame(s);
 894         p->pict_type = AV_PICTURE_TYPE_I;
 895         p->key_frame = 1;
 896         s->last_key_frame = avctx->frame_number;
 897         pkt->flags |= AV_PKT_FLAG_KEY;
 898         av_log(avctx, AV_LOG_DEBUG, "Inserting key frame at frame %d\n", avctx->frame_number);
 899     } else {
 900         p->pict_type = AV_PICTURE_TYPE_P;
 901         p->key_frame = 0;
 902     }
 903
 904     avctx->coded_frame = p;
 905
 906     pkt->size = res;
 907     *got_packet = 1;
 908
 909     return 0;
 910 }
 911
 912 static av_cold int flashsv2_encode_end(AVCodecContext * avctx)
 913 {
 914     FlashSV2Context *s = avctx->priv_data;
 915
 916     cleanup(s);
 917
 918     return 0;
 919 }
 920
 921 AVCodec ff_flashsv2_encoder = {
 922     .name           = "flashsv2",
 923     .type           = AVMEDIA_TYPE_VIDEO,
 924     .id             = AV_CODEC_ID_FLASHSV2,
 925     .priv_data_size = sizeof(FlashSV2Context),
 926     .init           = flashsv2_encode_init,
 927     .encode2        = flashsv2_encode_frame,
 928     .close          = flashsv2_encode_end,
 929     .pix_fmts       = (const enum AVPixelFormat[]){ AV_PIX_FMT_BGR24, AV_PIX_FMT_NONE },
 930     .long_name      = NULL_IF_CONFIG_SMALL("Flash Screen Video Version 2"),
 931 };