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