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