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