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 4095x4095 !\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);
 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 #define ABSDIFF(a,b) (abs((int)(a)-(int)(b)))
 416
 417     unsigned int t1 = (c1 & 0x000000ff) + ((c1 & 0x0000ff00) >> 8) + ((c1 & 0x00ff0000) >> 16);
 418     unsigned int t2 = (c2 & 0x000000ff) + ((c2 & 0x0000ff00) >> 8) + ((c2 & 0x00ff0000) >> 16);
 419
 420     return ABSDIFF(t1, t2) + ABSDIFF(c1 & 0x000000ff, c2 & 0x000000ff) +
 421         ABSDIFF((c1 & 0x0000ff00) >> 8 , (c2 & 0x0000ff00) >> 8) +
 422         ABSDIFF((c1 & 0x00ff0000) >> 16, (c2 & 0x00ff0000) >> 16);
 423 }
 424
 425 static inline int pixel_color7_fast(Palette * palette, unsigned c15)
 426 {
 427     return palette->index[c15];
 428 }
 429
 430 static int pixel_color7_slow(Palette * palette, unsigned color)
 431 {
 432     int i, min = 0x7fffffff;
 433     int minc = -1;
 434     for (i = 0; i < 128; i++) {
 435         int c1 = palette->colors[i];
 436         int diff = chroma_diff(c1, color);
 437         if (diff < min) {
 438             min = diff;
 439             minc = i;
 440         }
 441     }
 442     return minc;
 443 }
 444
 445 static inline unsigned pixel_bgr(const uint8_t * src)
 446 {
 447     return (src[0]) | (src[1] << 8) | (src[2] << 16);
 448 }
 449
 450 static int write_pixel_15_7(Palette * palette, uint8_t * dest, const uint8_t * src,
 451                             int dist)
 452 {
 453     unsigned c15 = pixel_color15(src);
 454     unsigned color = pixel_bgr(src);
 455     int d15 = chroma_diff(color, color & 0x00f8f8f8);
 456     int c7 = pixel_color7_fast(palette, c15);
 457     int d7 = chroma_diff(color, palette->colors[c7]);
 458     if (dist + d15 >= d7) {
 459         dest[0] = c7;
 460         return 1;
 461     } else {
 462         dest[0] = 0x80 | (c15 >> 8);
 463         dest[1] = c15 & 0xff;
 464         return 2;
 465     }
 466 }
 467
 468 static int update_palette_index(Palette * palette)
 469 {
 470     int r, g, b;
 471     unsigned int bgr, c15, index;
 472     for (r = 4; r < 256; r += 8) {
 473         for (g = 4; g < 256; g += 8) {
 474             for (b = 4; b < 256; b += 8) {
 475                 bgr = b | (g << 8) | (r << 16);
 476                 c15 = (b >> 3) | ((g & 0xf8) << 2) | ((r & 0xf8) << 7);
 477                 index = pixel_color7_slow(palette, bgr);
 478
 479                 palette->index[c15] = index;
 480             }
 481         }
 482     }
 483     return 0;
 484 }
 485
 486 static const unsigned int default_screen_video_v2_palette[128] = {
 487     0x00000000, 0x00333333, 0x00666666, 0x00999999, 0x00CCCCCC, 0x00FFFFFF,
 488     0x00330000, 0x00660000, 0x00990000, 0x00CC0000, 0x00FF0000, 0x00003300,
 489     0x00006600, 0x00009900, 0x0000CC00, 0x0000FF00, 0x00000033, 0x00000066,
 490     0x00000099, 0x000000CC, 0x000000FF, 0x00333300, 0x00666600, 0x00999900,
 491     0x00CCCC00, 0x00FFFF00, 0x00003333, 0x00006666, 0x00009999, 0x0000CCCC,
 492     0x0000FFFF, 0x00330033, 0x00660066, 0x00990099, 0x00CC00CC, 0x00FF00FF,
 493     0x00FFFF33, 0x00FFFF66, 0x00FFFF99, 0x00FFFFCC, 0x00FF33FF, 0x00FF66FF,
 494     0x00FF99FF, 0x00FFCCFF, 0x0033FFFF, 0x0066FFFF, 0x0099FFFF, 0x00CCFFFF,
 495     0x00CCCC33, 0x00CCCC66, 0x00CCCC99, 0x00CCCCFF, 0x00CC33CC, 0x00CC66CC,
 496     0x00CC99CC, 0x00CCFFCC, 0x0033CCCC, 0x0066CCCC, 0x0099CCCC, 0x00FFCCCC,
 497     0x00999933, 0x00999966, 0x009999CC, 0x009999FF, 0x00993399, 0x00996699,
 498     0x0099CC99, 0x0099FF99, 0x00339999, 0x00669999, 0x00CC9999, 0x00FF9999,
 499     0x00666633, 0x00666699, 0x006666CC, 0x006666FF, 0x00663366, 0x00669966,
 500     0x0066CC66, 0x0066FF66, 0x00336666, 0x00996666, 0x00CC6666, 0x00FF6666,
 501     0x00333366, 0x00333399, 0x003333CC, 0x003333FF, 0x00336633, 0x00339933,
 502     0x0033CC33, 0x0033FF33, 0x00663333, 0x00993333, 0x00CC3333, 0x00FF3333,
 503     0x00003366, 0x00336600, 0x00660033, 0x00006633, 0x00330066, 0x00663300,
 504     0x00336699, 0x00669933, 0x00993366, 0x00339966, 0x00663399, 0x00996633,
 505     0x006699CC, 0x0099CC66, 0x00CC6699, 0x0066CC99, 0x009966CC, 0x00CC9966,
 506     0x0099CCFF, 0x00CCFF99, 0x00FF99CC, 0x0099FFCC, 0x00CC99FF, 0x00FFCC99,
 507     0x00111111, 0x00222222, 0x00444444, 0x00555555, 0x00AAAAAA, 0x00BBBBBB,
 508     0x00DDDDDD, 0x00EEEEEE
 509 };
 510
 511 static int generate_default_palette(Palette * palette)
 512 {
 513     memcpy(palette->colors, default_screen_video_v2_palette,
 514            sizeof(default_screen_video_v2_palette));
 515
 516     return update_palette_index(palette);
 517 }
 518
 519 static int generate_optimum_palette(Palette * palette, const uint8_t * image,
 520                                    int width, int height, int stride)
 521 {
 522     //this isn't implemented yet!  Default palette only!
 523     return -1;
 524 }
 525
 526 static inline int encode_15_7_sl(Palette * palette, uint8_t * dest,
 527                                  const uint8_t * src, int width, int dist)
 528 {
 529     int len = 0, x;
 530     for (x = 0; x < width; x++) {
 531         len += write_pixel_15_7(palette, dest + len, src + 3 * x, dist);
 532     }
 533     return len;
 534 }
 535
 536 static int encode_15_7(Palette * palette, Block * b, const uint8_t * src,
 537                        int stride, int dist)
 538 {
 539     int i;
 540     uint8_t *ptr = b->enc;
 541     for (i = 0; i < b->start; i++)
 542         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 543     b->sl_begin = ptr;
 544     for (; i < b->start + b->len; i++)
 545         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 546     b->sl_end = ptr;
 547     for (; i < b->height; i++)
 548         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
 549     b->enc_size = ptr - b->enc;
 550     return b->enc_size;
 551 }
 552
 553 static int encode_block(FlashSV2Context *s, Palette * palette, Block * b,
 554                         Block * prev, const uint8_t * src, int stride, int comp,
 555                         int dist, int keyframe)
 556 {
 557     unsigned buf_size = b->width * b->height * 6;
 558     uint8_t *buf = s->blockbuffer;
 559     int res;
 560
 561     if (b->flags & COLORSPACE_15_7) {
 562         encode_15_7(palette, b, src, stride, dist);
 563     } else {
 564         encode_bgr(b, src, stride);
 565     }
 566
 567     if (b->len > 0) {
 568         b->data_size = buf_size;
 569         res = encode_zlib(b, b->data, &b->data_size, comp);
 570         if (res)
 571             return res;
 572
 573         if (!keyframe) {
 574             res = encode_zlibprime(b, prev, buf, &buf_size, comp);
 575             if (res)
 576                 return res;
 577
 578             if (buf_size < b->data_size) {
 579                 b->data_size = buf_size;
 580                 memcpy(b->data, buf, buf_size);
 581                 b->flags |= ZLIB_PRIME_COMPRESS_PREVIOUS;
 582             }
 583         }
 584     } else {
 585         b->data_size = 0;
 586     }
 587     return 0;
 588 }
 589
 590 static int compare_sl(FlashSV2Context * s, Block * b, const uint8_t * src,
 591                       uint8_t * frame, uint8_t * key, int y, int keyframe)
 592 {
 593     if (memcmp(src, frame, b->width * 3) != 0) {
 594         b->dirty = 1;
 595         memcpy(frame, src, b->width * 3);
 596 #ifndef FLASHSV2_DUMB
 597         s->diff_lines++;
 598 #endif
 599     }
 600     if (memcmp(src, key, b->width * 3) != 0) {
 601         if (b->len == 0)
 602             b->start = y;
 603         b->len = y + 1 - b->start;
 604     }
 605     return 0;
 606 }
 607
 608 static int mark_all_blocks(FlashSV2Context * s, const uint8_t * src, int stride,
 609                            int keyframe)
 610 {
 611     int sl, rsl, col, pos, possl;
 612     Block *b;
 613     for (sl = s->image_height - 1; sl >= 0; sl--) {
 614         for (col = 0; col < s->cols; col++) {
 615             rsl = s->image_height - sl - 1;
 616             b = s->frame_blocks + col + rsl / s->block_height * s->cols;
 617             possl = stride * sl + col * s->block_width * 3;
 618             pos = s->image_width * rsl * 3 + col * s->block_width * 3;
 619             compare_sl(s, b, src + possl, s->current_frame + pos,
 620                        s->key_frame + pos, rsl % s->block_height, keyframe);
 621         }
 622     }
 623 #ifndef FLASHSV2_DUMB
 624     s->tot_lines += s->image_height * s->cols;
 625 #endif
 626     return 0;
 627 }
 628
 629 static int encode_all_blocks(FlashSV2Context * s, int keyframe)
 630 {
 631     int row, col, res;
 632     uint8_t *data;
 633     Block *b, *prev;
 634     for (row = 0; row < s->rows; row++) {
 635         for (col = 0; col < s->cols; col++) {
 636             b = s->frame_blocks + (row * s->cols + col);
 637             prev = s->key_blocks + (row * s->cols + col);
 638             b->flags = s->use15_7 ? COLORSPACE_15_7 : 0;
 639             if (keyframe) {
 640                 b->start = 0;
 641                 b->len = b->height;
 642             } else if (!b->dirty) {
 643                 b->start = 0;
 644                 b->len = 0;
 645                 b->data_size = 0;
 646                 continue;
 647             } else if (b->start != 0 || b->len != b->height) {
 648                 b->flags |= HAS_DIFF_BLOCKS;
 649             }
 650             data = s->current_frame + s->image_width * 3 * s->block_height * row + s->block_width * col * 3;
 651             res = encode_block(s, &s->palette, b, prev, data, s->image_width * 3, s->comp, s->dist, keyframe);
 652 #ifndef FLASHSV2_DUMB
 653             if (b->dirty)
 654                 s->diff_blocks++;
 655             s->comp_size += b->data_size;
 656             s->uncomp_size += b->enc_size;
 657 #endif
 658             if (res)
 659                 return res;
 660         }
 661     }
 662 #ifndef FLASHSV2_DUMB
 663     s->raw_size += s->image_width * s->image_height * 3;
 664     s->tot_blocks += s->rows * s->cols;
 665 #endif
 666     return 0;
 667 }
 668
 669 static int write_all_blocks(FlashSV2Context * s, uint8_t * buf,
 670                             int buf_size)
 671 {
 672     int row, col, buf_pos = 0, len;
 673     Block *b;
 674     for (row = 0; row < s->rows; row++) {
 675         for (col = 0; col < s->cols; col++) {
 676             b = s->frame_blocks + row * s->cols + col;
 677             len = write_block(b, buf + buf_pos, buf_size - buf_pos);
 678             b->start = b->len = b->dirty = 0;
 679             if (len < 0)
 680                 return len;
 681             buf_pos += len;
 682         }
 683     }
 684     return buf_pos;
 685 }
 686
 687 static int write_bitstream(FlashSV2Context * s, const uint8_t * src, int stride,
 688                            uint8_t * buf, int buf_size, int keyframe)
 689 {
 690     int buf_pos, res;
 691
 692     res = mark_all_blocks(s, src, stride, keyframe);
 693     if (res)
 694         return res;
 695     res = encode_all_blocks(s, keyframe);
 696     if (res)
 697         return res;
 698
 699     res = write_header(s, buf, buf_size);
 700     if (res < 0) {
 701         return res;
 702     } else {
 703         buf_pos = res;
 704     }
 705     res = write_all_blocks(s, buf + buf_pos, buf_size - buf_pos);
 706     if (res < 0)
 707         return res;
 708     buf_pos += res;
 709 #ifndef FLASHSV2_DUMB
 710     s->total_bits += ((double) buf_pos) * 8.0;
 711 #endif
 712
 713     return buf_pos;
 714 }
 715
 716 static void recommend_keyframe(FlashSV2Context * s, int *keyframe)
 717 {
 718 #ifndef FLASHSV2_DUMB
 719     double block_ratio, line_ratio, enc_ratio, comp_ratio, data_ratio;
 720     if (s->avctx->gop_size > 0) {
 721         block_ratio = s->diff_blocks / s->tot_blocks;
 722         line_ratio = s->diff_lines / s->tot_lines;
 723         enc_ratio = s->uncomp_size / s->raw_size;
 724         comp_ratio = s->comp_size / s->uncomp_size;
 725         data_ratio = s->comp_size / s->raw_size;
 726
 727         if ((block_ratio >= 0.5 && line_ratio / block_ratio <= 0.5) || line_ratio >= 0.95) {
 728             *keyframe = 1;
 729             return;
 730         }
 731     }
 732 #else
 733     return;
 734 #endif
 735 }
 736
 737 #ifndef FLASHSV2_DUMB
 738 static const double block_size_fraction = 1.0 / 300;
 739 static const double use15_7_threshold = 8192;
 740 static const double color15_7_factor = 100;
 741 #endif
 742 static int optimum_block_width(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 width = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_width;
 747     int pwidth = ((int) width);
 748     return FFCLIP(pwidth & ~15, 256, 16);
 749 #else
 750     return 64;
 751 #endif
 752 }
 753
 754 static int optimum_block_height(FlashSV2Context * s)
 755 {
 756 #ifndef FLASHSV2_DUMB
 757     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
 758     double height = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_height;
 759     int pheight = ((int) height);
 760     return FFCLIP(pheight & ~15, 256, 16);
 761 #else
 762     return 64;
 763 #endif
 764 }
 765
 766 static int optimum_use15_7(FlashSV2Context * s)
 767 {
 768 #ifndef FLASHSV2_DUMB
 769     double ideal = ((double)(s->avctx->bit_rate * s->avctx->time_base.den * s->avctx->ticks_per_frame)) /
 770         ((double) s->avctx->time_base.num) * s->avctx->frame_number;
 771     if (ideal + use15_7_threshold < s->total_bits) {
 772         return 1;
 773     } else {
 774         return 0;
 775     }
 776 #else
 777     return s->avctx->global_quality == 0;
 778 #endif
 779 }
 780
 781 static int optimum_dist(FlashSV2Context * s)
 782 {
 783 #ifndef FLASHSV2_DUMB
 784     double ideal =
 785         s->avctx->bit_rate * s->avctx->time_base.den *
 786         s->avctx->ticks_per_frame;
 787     int dist = pow((s->total_bits / ideal) * color15_7_factor, 3);
 788     av_log(s->avctx, AV_LOG_DEBUG, "dist: %d\n", dist);
 789     return dist;
 790 #else
 791     return 15;
 792 #endif
 793 }
 794
 795
 796 static int reconfigure_at_keyframe(FlashSV2Context * s, const uint8_t * image,
 797                                    int stride)
 798 {
 799     int update_palette = 0;
 800     int res;
 801     int block_width  = optimum_block_width (s);
 802     int block_height = optimum_block_height(s);
 803
 804     s->rows = (s->image_height + block_height - 1) / block_height;
 805     s->cols = (s->image_width  + block_width  - 1) / block_width;
 806
 807     if (block_width != s->block_width || block_height != s->block_height) {
 808         s->block_width  = block_width;
 809         s->block_height = block_height;
 810         if (s->rows * s->cols > s->blocks_size / sizeof(Block)) {
 811             s->frame_blocks = av_realloc_array(s->frame_blocks, s->rows, s->cols * sizeof(Block));
 812             s->key_blocks = av_realloc_array(s->key_blocks, s->cols, s->rows * sizeof(Block));
 813             if (!s->frame_blocks || !s->key_blocks) {
 814                 av_log(s->avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
 815                 return -1;
 816             }
 817             s->blocks_size = s->rows * s->cols * sizeof(Block);
 818         }
 819         init_blocks(s, s->frame_blocks, s->encbuffer, s->databuffer);
 820         init_blocks(s, s->key_blocks, s->keybuffer, 0);
 821
 822         av_fast_malloc(&s->blockbuffer, &s->blockbuffer_size, block_width * block_height * 6);
 823         if (!s->blockbuffer) {
 824             av_log(s->avctx, AV_LOG_ERROR, "Could not allocate block buffer.\n");
 825             return AVERROR(ENOMEM);
 826         }
 827     }
 828
 829     s->use15_7 = optimum_use15_7(s);
 830     if (s->use15_7) {
 831         if ((s->use_custom_palette && s->palette_type != 1) || update_palette) {
 832             res = generate_optimum_palette(&s->palette, image, s->image_width, s->image_height, stride);
 833             if (res)
 834                 return res;
 835             s->palette_type = 1;
 836             av_log(s->avctx, AV_LOG_DEBUG, "Generated optimum palette\n");
 837         } else if (!s->use_custom_palette && s->palette_type != 0) {
 838             res = generate_default_palette(&s->palette);
 839             if (res)
 840                 return res;
 841             s->palette_type = 0;
 842             av_log(s->avctx, AV_LOG_DEBUG, "Generated default palette\n");
 843         }
 844     }
 845
 846
 847     reset_stats(s);
 848
 849     return 0;
 850 }
 851
 852 static int flashsv2_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
 853                                  const AVFrame *p, int *got_packet)
 854 {
 855     FlashSV2Context *const s = avctx->priv_data;
 856     int res;
 857     int keyframe = 0;
 858
 859     if ((res = ff_alloc_packet2(avctx, pkt, s->frame_size + AV_INPUT_BUFFER_MIN_SIZE, 0)) < 0)
 860         return res;
 861
 862     /* First frame needs to be a keyframe */
 863     if (avctx->frame_number == 0)
 864         keyframe = 1;
 865
 866     /* Check the placement of keyframes */
 867     if (avctx->gop_size > 0) {
 868         if (avctx->frame_number >= s->last_key_frame + avctx->gop_size)
 869             keyframe = 1;
 870     }
 871
 872     if (!keyframe
 873         && avctx->frame_number > s->last_key_frame + avctx->keyint_min) {
 874         recommend_keyframe(s, &keyframe);
 875         if (keyframe)
 876             av_log(avctx, AV_LOG_DEBUG, "Recommending key frame at frame %d\n", avctx->frame_number);
 877     }
 878
 879     if (keyframe) {
 880         res = reconfigure_at_keyframe(s, p->data[0], p->linesize[0]);
 881         if (res)
 882             return res;
 883     }
 884
 885     if (s->use15_7)
 886         s->dist = optimum_dist(s);
 887
 888     res = write_bitstream(s, p->data[0], p->linesize[0], pkt->data, pkt->size, keyframe);
 889
 890     if (keyframe) {
 891         new_key_frame(s);
 892         s->last_key_frame = avctx->frame_number;
 893         pkt->flags |= AV_PKT_FLAG_KEY;
 894         av_log(avctx, AV_LOG_DEBUG, "Inserting key frame at frame %d\n", avctx->frame_number);
 895     }
 896
 897     pkt->size = res;
 898     *got_packet = 1;
 899
 900     return 0;
 901 }
 902
 903 static av_cold int flashsv2_encode_end(AVCodecContext * avctx)
 904 {
 905     FlashSV2Context *s = avctx->priv_data;
 906
 907     cleanup(s);
 908
 909     return 0;
 910 }
 911
 912 AVCodec ff_flashsv2_encoder = {
 913     .name           = "flashsv2",
 914     .long_name      = NULL_IF_CONFIG_SMALL("Flash Screen Video Version 2"),
 915     .type           = AVMEDIA_TYPE_VIDEO,
 916     .id             = AV_CODEC_ID_FLASHSV2,
 917     .priv_data_size = sizeof(FlashSV2Context),
 918     .init           = flashsv2_encode_init,
 919     .encode2        = flashsv2_encode_frame,
 920     .close          = flashsv2_encode_end,
 921     .pix_fmts       = (const enum AVPixelFormat[]){ AV_PIX_FMT_BGR24, AV_PIX_FMT_NONE },
 922 };