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