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