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