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