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