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