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