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