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