9725f2920602d648a522213861190ac28bc4ae9c
[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             if (keyframe) {
638                 b->start = 0;
639                 b->len = b->height;
640                 b->flags = s->use15_7 ? COLORSPACE_15_7 : 0;
641             } else if (!b->dirty) {
642                 b->start = 0;
643                 b->len = 0;
644                 b->data_size = 0;
645                 b->flags = s->use15_7 ? COLORSPACE_15_7 : 0;
646                 continue;
647             } else {
648                 b->flags = s->use15_7 ? COLORSPACE_15_7 | HAS_DIFF_BLOCKS : HAS_DIFF_BLOCKS;
649             }
650             data = s->current_frame + s->image_width * 3 * s->block_height * row + s->block_width * col * 3;
651             res = encode_block(s, &s->palette, b, prev, data, s->image_width * 3, s->comp, s->dist, keyframe);
652 #ifndef FLASHSV2_DUMB
653             if (b->dirty)
654                 s->diff_blocks++;
655             s->comp_size += b->data_size;
656             s->uncomp_size += b->enc_size;
657 #endif
658             if (res)
659                 return res;
660         }
661     }
662 #ifndef FLASHSV2_DUMB
663     s->raw_size += s->image_width * s->image_height * 3;
664     s->tot_blocks += s->rows * s->cols;
665 #endif
666     return 0;
667 }
668
669 static int write_all_blocks(FlashSV2Context * s, uint8_t * buf,
670                             int buf_size)
671 {
672     int row, col, buf_pos = 0, len;
673     Block *b;
674     for (row = 0; row < s->rows; row++) {
675         for (col = 0; col < s->cols; col++) {
676             b = s->frame_blocks + row * s->cols + col;
677             len = write_block(b, buf + buf_pos, buf_size - buf_pos);
678             b->start = b->len = b->dirty = 0;
679             if (len < 0)
680                 return len;
681             buf_pos += len;
682         }
683     }
684     return buf_pos;
685 }
686
687 static int write_bitstream(FlashSV2Context * s, const uint8_t * src, int stride,
688                            uint8_t * buf, int buf_size, int keyframe)
689 {
690     int buf_pos, res;
691
692     res = mark_all_blocks(s, src, stride, keyframe);
693     if (res)
694         return res;
695     res = encode_all_blocks(s, keyframe);
696     if (res)
697         return res;
698
699     res = write_header(s, buf, buf_size);
700     if (res < 0) {
701         return res;
702     } else {
703         buf_pos = res;
704     }
705     res = write_all_blocks(s, buf + buf_pos, buf_size - buf_pos);
706     if (res < 0)
707         return res;
708     buf_pos += res;
709 #ifndef FLASHSV2_DUMB
710     s->total_bits += ((double) buf_pos) * 8.0;
711 #endif
712
713     return buf_pos;
714 }
715
716 static void recommend_keyframe(FlashSV2Context * s, int *keyframe)
717 {
718 #ifndef FLASHSV2_DUMB
719     double block_ratio, line_ratio, enc_ratio, comp_ratio, data_ratio;
720     if (s->avctx->gop_size > 0) {
721         block_ratio = s->diff_blocks / s->tot_blocks;
722         line_ratio = s->diff_lines / s->tot_lines;
723         enc_ratio = s->uncomp_size / s->raw_size;
724         comp_ratio = s->comp_size / s->uncomp_size;
725         data_ratio = s->comp_size / s->raw_size;
726
727         if ((block_ratio >= 0.5 && line_ratio / block_ratio <= 0.5) || line_ratio >= 0.95) {
728             *keyframe = 1;
729             return;
730         }
731     }
732 #else
733     return;
734 #endif
735 }
736
737 static const double block_size_fraction = 1.0 / 300;
738 static int optimum_block_width(FlashSV2Context * s)
739 {
740 #ifndef FLASHSV2_DUMB
741     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
742     double width = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_width;
743     int pwidth = ((int) width);
744     return FFCLIP(pwidth & ~15, 256, 16);
745 #else
746     return 64;
747 #endif
748 }
749
750 static int optimum_block_height(FlashSV2Context * s)
751 {
752 #ifndef FLASHSV2_DUMB
753     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
754     double height = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_height;
755     int pheight = ((int) height);
756     return FFCLIP(pheight & ~15, 256, 16);
757 #else
758     return 64;
759 #endif
760 }
761
762 static const double use15_7_threshold = 8192;
763
764 static int optimum_use15_7(FlashSV2Context * s)
765 {
766 #ifndef FLASHSV2_DUMB
767     double ideal = ((double)(s->avctx->bit_rate * s->avctx->time_base.den * s->avctx->ticks_per_frame)) /
768         ((double) s->avctx->time_base.num) * s->avctx->frame_number;
769     if (ideal + use15_7_threshold < s->total_bits) {
770         return 1;
771     } else {
772         return 0;
773     }
774 #else
775     return s->avctx->global_quality == 0;
776 #endif
777 }
778
779 static const double color15_7_factor = 100;
780
781 static int optimum_dist(FlashSV2Context * s)
782 {
783 #ifndef FLASHSV2_DUMB
784     double ideal =
785         s->avctx->bit_rate * s->avctx->time_base.den *
786         s->avctx->ticks_per_frame;
787     int dist = pow((s->total_bits / ideal) * color15_7_factor, 3);
788     av_log(s->avctx, AV_LOG_DEBUG, "dist: %d\n", dist);
789     return dist;
790 #else
791     return 15;
792 #endif
793 }
794
795
796 static int reconfigure_at_keyframe(FlashSV2Context * s, const uint8_t * image,
797                                    int stride)
798 {
799     int update_palette = 0;
800     int res;
801     int block_width  = optimum_block_width (s);
802     int block_height = optimum_block_height(s);
803
804     s->rows = (s->image_height + block_height - 1) / block_height;
805     s->cols = (s->image_width  + block_width  - 1) / block_width;
806
807     if (block_width != s->block_width || block_height != s->block_height) {
808         s->block_width  = block_width;
809         s->block_height = block_height;
810         if (s->rows * s->cols > s->blocks_size / sizeof(Block)) {
811             s->frame_blocks = av_realloc(s->frame_blocks, s->rows * s->cols * sizeof(Block));
812             s->key_blocks = av_realloc(s->key_blocks, s->cols * s->rows * sizeof(Block));
813             if (!s->frame_blocks || !s->key_blocks) {
814                 av_log(s->avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
815                 return -1;
816             }
817             s->blocks_size = s->rows * s->cols * sizeof(Block);
818         }
819         init_blocks(s, s->frame_blocks, s->encbuffer, s->databuffer);
820         init_blocks(s, s->key_blocks, s->keybuffer, 0);
821
822         av_fast_malloc(&s->blockbuffer, &s->blockbuffer_size, block_width * block_height * 6);
823         if (!s->blockbuffer) {
824             av_log(s->avctx, AV_LOG_ERROR, "Could not allocate block buffer.\n");
825             return AVERROR(ENOMEM);
826         }
827     }
828
829     s->use15_7 = optimum_use15_7(s);
830     if (s->use15_7) {
831         if ((s->use_custom_palette && s->palette_type != 1) || update_palette) {
832             res = generate_optimum_palette(&s->palette, image, s->image_width, s->image_height, stride);
833             if (res)
834                 return res;
835             s->palette_type = 1;
836             av_log(s->avctx, AV_LOG_DEBUG, "Generated optimum palette\n");
837         } else if (!s->use_custom_palette && s->palette_type != 0) {
838             res = generate_default_palette(&s->palette);
839             if (res)
840                 return res;
841             s->palette_type = 0;
842             av_log(s->avctx, AV_LOG_DEBUG, "Generated default palette\n");
843         }
844     }
845
846
847     reset_stats(s);
848
849     return 0;
850 }
851
852 static int flashsv2_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
853                                  const AVFrame *pict, int *got_packet)
854 {
855     FlashSV2Context *const s = avctx->priv_data;
856     AVFrame *const p = &s->frame;
857     int res;
858     int keyframe = 0;
859
860     *p = *pict;
861
862     if ((res = ff_alloc_packet2(avctx, pkt, s->frame_size + FF_MIN_BUFFER_SIZE)) < 0)
863         return res;
864
865     /* First frame needs to be a keyframe */
866     if (avctx->frame_number == 0)
867         keyframe = 1;
868
869     /* Check the placement of keyframes */
870     if (avctx->gop_size > 0) {
871         if (avctx->frame_number >= s->last_key_frame + avctx->gop_size)
872             keyframe = 1;
873     }
874
875     if (!keyframe
876         && avctx->frame_number > s->last_key_frame + avctx->keyint_min) {
877         recommend_keyframe(s, &keyframe);
878         if (keyframe)
879             av_log(avctx, AV_LOG_DEBUG, "Recommending key frame at frame %d\n", avctx->frame_number);
880     }
881
882     if (keyframe) {
883         res = reconfigure_at_keyframe(s, p->data[0], p->linesize[0]);
884         if (res)
885             return res;
886     }
887
888     if (s->use15_7)
889         s->dist = optimum_dist(s);
890
891     res = write_bitstream(s, p->data[0], p->linesize[0], pkt->data, pkt->size, keyframe);
892
893     if (keyframe) {
894         new_key_frame(s);
895         p->pict_type = AV_PICTURE_TYPE_I;
896         p->key_frame = 1;
897         s->last_key_frame = avctx->frame_number;
898         pkt->flags |= AV_PKT_FLAG_KEY;
899         av_log(avctx, AV_LOG_DEBUG, "Inserting key frame at frame %d\n", avctx->frame_number);
900     } else {
901         p->pict_type = AV_PICTURE_TYPE_P;
902         p->key_frame = 0;
903     }
904
905     avctx->coded_frame = p;
906
907     pkt->size = res;
908     *got_packet = 1;
909
910     return 0;
911 }
912
913 static av_cold int flashsv2_encode_end(AVCodecContext * avctx)
914 {
915     FlashSV2Context *s = avctx->priv_data;
916
917     cleanup(s);
918
919     return 0;
920 }
921
922 AVCodec ff_flashsv2_encoder = {
923     .name           = "flashsv2",
924     .type           = AVMEDIA_TYPE_VIDEO,
925     .id             = AV_CODEC_ID_FLASHSV2,
926     .priv_data_size = sizeof(FlashSV2Context),
927     .init           = flashsv2_encode_init,
928     .encode2        = flashsv2_encode_frame,
929     .close          = flashsv2_encode_end,
930     .pix_fmts       = (const enum PixelFormat[]){ PIX_FMT_BGR24, PIX_FMT_NONE },
931     .long_name      = NULL_IF_CONFIG_SMALL("Flash Screen Video Version 2"),
932 };