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