avcodec/gsmdec_template: Fix runtime error: signed integer overflow: -22527 * 99113...
[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 4095x4095 !\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);
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 #define ABSDIFF(a,b) (abs((int)(a)-(int)(b)))
416
417     unsigned int t1 = (c1 & 0x000000ff) + ((c1 & 0x0000ff00) >> 8) + ((c1 & 0x00ff0000) >> 16);
418     unsigned int t2 = (c2 & 0x000000ff) + ((c2 & 0x0000ff00) >> 8) + ((c2 & 0x00ff0000) >> 16);
419
420     return ABSDIFF(t1, t2) + ABSDIFF(c1 & 0x000000ff, c2 & 0x000000ff) +
421         ABSDIFF((c1 & 0x0000ff00) >> 8 , (c2 & 0x0000ff00) >> 8) +
422         ABSDIFF((c1 & 0x00ff0000) >> 16, (c2 & 0x00ff0000) >> 16);
423 }
424
425 static inline int pixel_color7_fast(Palette * palette, unsigned c15)
426 {
427     return palette->index[c15];
428 }
429
430 static int pixel_color7_slow(Palette * palette, unsigned color)
431 {
432     int i, min = 0x7fffffff;
433     int minc = -1;
434     for (i = 0; i < 128; i++) {
435         int c1 = palette->colors[i];
436         int diff = chroma_diff(c1, color);
437         if (diff < min) {
438             min = diff;
439             minc = i;
440         }
441     }
442     return minc;
443 }
444
445 static inline unsigned pixel_bgr(const uint8_t * src)
446 {
447     return (src[0]) | (src[1] << 8) | (src[2] << 16);
448 }
449
450 static int write_pixel_15_7(Palette * palette, uint8_t * dest, const uint8_t * src,
451                             int dist)
452 {
453     unsigned c15 = pixel_color15(src);
454     unsigned color = pixel_bgr(src);
455     int d15 = chroma_diff(color, color & 0x00f8f8f8);
456     int c7 = pixel_color7_fast(palette, c15);
457     int d7 = chroma_diff(color, palette->colors[c7]);
458     if (dist + d15 >= d7) {
459         dest[0] = c7;
460         return 1;
461     } else {
462         dest[0] = 0x80 | (c15 >> 8);
463         dest[1] = c15 & 0xff;
464         return 2;
465     }
466 }
467
468 static int update_palette_index(Palette * palette)
469 {
470     int r, g, b;
471     unsigned int bgr, c15, index;
472     for (r = 4; r < 256; r += 8) {
473         for (g = 4; g < 256; g += 8) {
474             for (b = 4; b < 256; b += 8) {
475                 bgr = b | (g << 8) | (r << 16);
476                 c15 = (b >> 3) | ((g & 0xf8) << 2) | ((r & 0xf8) << 7);
477                 index = pixel_color7_slow(palette, bgr);
478
479                 palette->index[c15] = index;
480             }
481         }
482     }
483     return 0;
484 }
485
486 static const unsigned int default_screen_video_v2_palette[128] = {
487     0x00000000, 0x00333333, 0x00666666, 0x00999999, 0x00CCCCCC, 0x00FFFFFF,
488     0x00330000, 0x00660000, 0x00990000, 0x00CC0000, 0x00FF0000, 0x00003300,
489     0x00006600, 0x00009900, 0x0000CC00, 0x0000FF00, 0x00000033, 0x00000066,
490     0x00000099, 0x000000CC, 0x000000FF, 0x00333300, 0x00666600, 0x00999900,
491     0x00CCCC00, 0x00FFFF00, 0x00003333, 0x00006666, 0x00009999, 0x0000CCCC,
492     0x0000FFFF, 0x00330033, 0x00660066, 0x00990099, 0x00CC00CC, 0x00FF00FF,
493     0x00FFFF33, 0x00FFFF66, 0x00FFFF99, 0x00FFFFCC, 0x00FF33FF, 0x00FF66FF,
494     0x00FF99FF, 0x00FFCCFF, 0x0033FFFF, 0x0066FFFF, 0x0099FFFF, 0x00CCFFFF,
495     0x00CCCC33, 0x00CCCC66, 0x00CCCC99, 0x00CCCCFF, 0x00CC33CC, 0x00CC66CC,
496     0x00CC99CC, 0x00CCFFCC, 0x0033CCCC, 0x0066CCCC, 0x0099CCCC, 0x00FFCCCC,
497     0x00999933, 0x00999966, 0x009999CC, 0x009999FF, 0x00993399, 0x00996699,
498     0x0099CC99, 0x0099FF99, 0x00339999, 0x00669999, 0x00CC9999, 0x00FF9999,
499     0x00666633, 0x00666699, 0x006666CC, 0x006666FF, 0x00663366, 0x00669966,
500     0x0066CC66, 0x0066FF66, 0x00336666, 0x00996666, 0x00CC6666, 0x00FF6666,
501     0x00333366, 0x00333399, 0x003333CC, 0x003333FF, 0x00336633, 0x00339933,
502     0x0033CC33, 0x0033FF33, 0x00663333, 0x00993333, 0x00CC3333, 0x00FF3333,
503     0x00003366, 0x00336600, 0x00660033, 0x00006633, 0x00330066, 0x00663300,
504     0x00336699, 0x00669933, 0x00993366, 0x00339966, 0x00663399, 0x00996633,
505     0x006699CC, 0x0099CC66, 0x00CC6699, 0x0066CC99, 0x009966CC, 0x00CC9966,
506     0x0099CCFF, 0x00CCFF99, 0x00FF99CC, 0x0099FFCC, 0x00CC99FF, 0x00FFCC99,
507     0x00111111, 0x00222222, 0x00444444, 0x00555555, 0x00AAAAAA, 0x00BBBBBB,
508     0x00DDDDDD, 0x00EEEEEE
509 };
510
511 static int generate_default_palette(Palette * palette)
512 {
513     memcpy(palette->colors, default_screen_video_v2_palette,
514            sizeof(default_screen_video_v2_palette));
515
516     return update_palette_index(palette);
517 }
518
519 static int generate_optimum_palette(Palette * palette, const uint8_t * image,
520                                    int width, int height, int stride)
521 {
522     //this isn't implemented yet!  Default palette only!
523     return -1;
524 }
525
526 static inline int encode_15_7_sl(Palette * palette, uint8_t * dest,
527                                  const uint8_t * src, int width, int dist)
528 {
529     int len = 0, x;
530     for (x = 0; x < width; x++) {
531         len += write_pixel_15_7(palette, dest + len, src + 3 * x, dist);
532     }
533     return len;
534 }
535
536 static int encode_15_7(Palette * palette, Block * b, const uint8_t * src,
537                        int stride, int dist)
538 {
539     int i;
540     uint8_t *ptr = b->enc;
541     for (i = 0; i < b->start; i++)
542         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
543     b->sl_begin = ptr;
544     for (; i < b->start + b->len; i++)
545         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
546     b->sl_end = ptr;
547     for (; i < b->height; i++)
548         ptr += encode_15_7_sl(palette, ptr, src + i * stride, b->width, dist);
549     b->enc_size = ptr - b->enc;
550     return b->enc_size;
551 }
552
553 static int encode_block(FlashSV2Context *s, Palette * palette, Block * b,
554                         Block * prev, const uint8_t * src, int stride, int comp,
555                         int dist, int keyframe)
556 {
557     unsigned buf_size = b->width * b->height * 6;
558     uint8_t *buf = s->blockbuffer;
559     int res;
560
561     if (b->flags & COLORSPACE_15_7) {
562         encode_15_7(palette, b, src, stride, dist);
563     } else {
564         encode_bgr(b, src, stride);
565     }
566
567     if (b->len > 0) {
568         b->data_size = buf_size;
569         res = encode_zlib(b, b->data, &b->data_size, comp);
570         if (res)
571             return res;
572
573         if (!keyframe) {
574             res = encode_zlibprime(b, prev, buf, &buf_size, comp);
575             if (res)
576                 return res;
577
578             if (buf_size < b->data_size) {
579                 b->data_size = buf_size;
580                 memcpy(b->data, buf, buf_size);
581                 b->flags |= ZLIB_PRIME_COMPRESS_PREVIOUS;
582             }
583         }
584     } else {
585         b->data_size = 0;
586     }
587     return 0;
588 }
589
590 static int compare_sl(FlashSV2Context * s, Block * b, const uint8_t * src,
591                       uint8_t * frame, uint8_t * key, int y, int keyframe)
592 {
593     if (memcmp(src, frame, b->width * 3) != 0) {
594         b->dirty = 1;
595         memcpy(frame, src, b->width * 3);
596 #ifndef FLASHSV2_DUMB
597         s->diff_lines++;
598 #endif
599     }
600     if (memcmp(src, key, b->width * 3) != 0) {
601         if (b->len == 0)
602             b->start = y;
603         b->len = y + 1 - b->start;
604     }
605     return 0;
606 }
607
608 static int mark_all_blocks(FlashSV2Context * s, const uint8_t * src, int stride,
609                            int keyframe)
610 {
611     int sl, rsl, col, pos, possl;
612     Block *b;
613     for (sl = s->image_height - 1; sl >= 0; sl--) {
614         for (col = 0; col < s->cols; col++) {
615             rsl = s->image_height - sl - 1;
616             b = s->frame_blocks + col + rsl / s->block_height * s->cols;
617             possl = stride * sl + col * s->block_width * 3;
618             pos = s->image_width * rsl * 3 + col * s->block_width * 3;
619             compare_sl(s, b, src + possl, s->current_frame + pos,
620                        s->key_frame + pos, rsl % s->block_height, keyframe);
621         }
622     }
623 #ifndef FLASHSV2_DUMB
624     s->tot_lines += s->image_height * s->cols;
625 #endif
626     return 0;
627 }
628
629 static int encode_all_blocks(FlashSV2Context * s, int keyframe)
630 {
631     int row, col, res;
632     uint8_t *data;
633     Block *b, *prev;
634     for (row = 0; row < s->rows; row++) {
635         for (col = 0; col < s->cols; col++) {
636             b = s->frame_blocks + (row * s->cols + col);
637             prev = s->key_blocks + (row * s->cols + col);
638             b->flags = s->use15_7 ? COLORSPACE_15_7 : 0;
639             if (keyframe) {
640                 b->start = 0;
641                 b->len = b->height;
642             } else if (!b->dirty) {
643                 b->start = 0;
644                 b->len = 0;
645                 b->data_size = 0;
646                 continue;
647             } else if (b->start != 0 || b->len != b->height) {
648                 b->flags |= HAS_DIFF_BLOCKS;
649             }
650             data = s->current_frame + s->image_width * 3 * s->block_height * row + s->block_width * col * 3;
651             res = encode_block(s, &s->palette, b, prev, data, s->image_width * 3, s->comp, s->dist, keyframe);
652 #ifndef FLASHSV2_DUMB
653             if (b->dirty)
654                 s->diff_blocks++;
655             s->comp_size += b->data_size;
656             s->uncomp_size += b->enc_size;
657 #endif
658             if (res)
659                 return res;
660         }
661     }
662 #ifndef FLASHSV2_DUMB
663     s->raw_size += s->image_width * s->image_height * 3;
664     s->tot_blocks += s->rows * s->cols;
665 #endif
666     return 0;
667 }
668
669 static int write_all_blocks(FlashSV2Context * s, uint8_t * buf,
670                             int buf_size)
671 {
672     int row, col, buf_pos = 0, len;
673     Block *b;
674     for (row = 0; row < s->rows; row++) {
675         for (col = 0; col < s->cols; col++) {
676             b = s->frame_blocks + row * s->cols + col;
677             len = write_block(b, buf + buf_pos, buf_size - buf_pos);
678             b->start = b->len = b->dirty = 0;
679             if (len < 0)
680                 return len;
681             buf_pos += len;
682         }
683     }
684     return buf_pos;
685 }
686
687 static int write_bitstream(FlashSV2Context * s, const uint8_t * src, int stride,
688                            uint8_t * buf, int buf_size, int keyframe)
689 {
690     int buf_pos, res;
691
692     res = mark_all_blocks(s, src, stride, keyframe);
693     if (res)
694         return res;
695     res = encode_all_blocks(s, keyframe);
696     if (res)
697         return res;
698
699     res = write_header(s, buf, buf_size);
700     if (res < 0) {
701         return res;
702     } else {
703         buf_pos = res;
704     }
705     res = write_all_blocks(s, buf + buf_pos, buf_size - buf_pos);
706     if (res < 0)
707         return res;
708     buf_pos += res;
709 #ifndef FLASHSV2_DUMB
710     s->total_bits += ((double) buf_pos) * 8.0;
711 #endif
712
713     return buf_pos;
714 }
715
716 static void recommend_keyframe(FlashSV2Context * s, int *keyframe)
717 {
718 #ifndef FLASHSV2_DUMB
719     double block_ratio, line_ratio, enc_ratio, comp_ratio, data_ratio;
720     if (s->avctx->gop_size > 0) {
721         block_ratio = s->diff_blocks / s->tot_blocks;
722         line_ratio = s->diff_lines / s->tot_lines;
723         enc_ratio = s->uncomp_size / s->raw_size;
724         comp_ratio = s->comp_size / s->uncomp_size;
725         data_ratio = s->comp_size / s->raw_size;
726
727         if ((block_ratio >= 0.5 && line_ratio / block_ratio <= 0.5) || line_ratio >= 0.95) {
728             *keyframe = 1;
729             return;
730         }
731     }
732 #else
733     return;
734 #endif
735 }
736
737 #ifndef FLASHSV2_DUMB
738 static const double block_size_fraction = 1.0 / 300;
739 static const double use15_7_threshold = 8192;
740 static const double color15_7_factor = 100;
741 #endif
742 static int optimum_block_width(FlashSV2Context * s)
743 {
744 #ifndef FLASHSV2_DUMB
745     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
746     double width = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_width;
747     int pwidth = ((int) width);
748     return FFCLIP(pwidth & ~15, 256, 16);
749 #else
750     return 64;
751 #endif
752 }
753
754 static int optimum_block_height(FlashSV2Context * s)
755 {
756 #ifndef FLASHSV2_DUMB
757     double save = (1-pow(s->diff_lines/s->diff_blocks/s->block_height, 0.5)) * s->comp_size/s->tot_blocks;
758     double height = block_size_fraction * sqrt(0.5 * save * s->rows * s->cols) * s->image_height;
759     int pheight = ((int) height);
760     return FFCLIP(pheight & ~15, 256, 16);
761 #else
762     return 64;
763 #endif
764 }
765
766 static int optimum_use15_7(FlashSV2Context * s)
767 {
768 #ifndef FLASHSV2_DUMB
769     double ideal = ((double)(s->avctx->bit_rate * s->avctx->time_base.den * s->avctx->ticks_per_frame)) /
770         ((double) s->avctx->time_base.num) * s->avctx->frame_number;
771     if (ideal + use15_7_threshold < s->total_bits) {
772         return 1;
773     } else {
774         return 0;
775     }
776 #else
777     return s->avctx->global_quality == 0;
778 #endif
779 }
780
781 static int optimum_dist(FlashSV2Context * s)
782 {
783 #ifndef FLASHSV2_DUMB
784     double ideal =
785         s->avctx->bit_rate * s->avctx->time_base.den *
786         s->avctx->ticks_per_frame;
787     int dist = pow((s->total_bits / ideal) * color15_7_factor, 3);
788     av_log(s->avctx, AV_LOG_DEBUG, "dist: %d\n", dist);
789     return dist;
790 #else
791     return 15;
792 #endif
793 }
794
795
796 static int reconfigure_at_keyframe(FlashSV2Context * s, const uint8_t * image,
797                                    int stride)
798 {
799     int update_palette = 0;
800     int res;
801     int block_width  = optimum_block_width (s);
802     int block_height = optimum_block_height(s);
803
804     s->rows = (s->image_height + block_height - 1) / block_height;
805     s->cols = (s->image_width  + block_width  - 1) / block_width;
806
807     if (block_width != s->block_width || block_height != s->block_height) {
808         s->block_width  = block_width;
809         s->block_height = block_height;
810         if (s->rows * s->cols > s->blocks_size / sizeof(Block)) {
811             s->frame_blocks = av_realloc_array(s->frame_blocks, s->rows, s->cols * sizeof(Block));
812             s->key_blocks = av_realloc_array(s->key_blocks, s->cols, s->rows * sizeof(Block));
813             if (!s->frame_blocks || !s->key_blocks) {
814                 av_log(s->avctx, AV_LOG_ERROR, "Memory allocation failed.\n");
815                 return -1;
816             }
817             s->blocks_size = s->rows * s->cols * sizeof(Block);
818         }
819         init_blocks(s, s->frame_blocks, s->encbuffer, s->databuffer);
820         init_blocks(s, s->key_blocks, s->keybuffer, 0);
821
822         av_fast_malloc(&s->blockbuffer, &s->blockbuffer_size, block_width * block_height * 6);
823         if (!s->blockbuffer) {
824             av_log(s->avctx, AV_LOG_ERROR, "Could not allocate block buffer.\n");
825             return AVERROR(ENOMEM);
826         }
827     }
828
829     s->use15_7 = optimum_use15_7(s);
830     if (s->use15_7) {
831         if ((s->use_custom_palette && s->palette_type != 1) || update_palette) {
832             res = generate_optimum_palette(&s->palette, image, s->image_width, s->image_height, stride);
833             if (res)
834                 return res;
835             s->palette_type = 1;
836             av_log(s->avctx, AV_LOG_DEBUG, "Generated optimum palette\n");
837         } else if (!s->use_custom_palette && s->palette_type != 0) {
838             res = generate_default_palette(&s->palette);
839             if (res)
840                 return res;
841             s->palette_type = 0;
842             av_log(s->avctx, AV_LOG_DEBUG, "Generated default palette\n");
843         }
844     }
845
846
847     reset_stats(s);
848
849     return 0;
850 }
851
852 static int flashsv2_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
853                                  const AVFrame *p, int *got_packet)
854 {
855     FlashSV2Context *const s = avctx->priv_data;
856     int res;
857     int keyframe = 0;
858
859     if ((res = ff_alloc_packet2(avctx, pkt, s->frame_size + AV_INPUT_BUFFER_MIN_SIZE, 0)) < 0)
860         return res;
861
862     /* First frame needs to be a keyframe */
863     if (avctx->frame_number == 0)
864         keyframe = 1;
865
866     /* Check the placement of keyframes */
867     if (avctx->gop_size > 0) {
868         if (avctx->frame_number >= s->last_key_frame + avctx->gop_size)
869             keyframe = 1;
870     }
871
872     if (!keyframe
873         && avctx->frame_number > s->last_key_frame + avctx->keyint_min) {
874         recommend_keyframe(s, &keyframe);
875         if (keyframe)
876             av_log(avctx, AV_LOG_DEBUG, "Recommending key frame at frame %d\n", avctx->frame_number);
877     }
878
879     if (keyframe) {
880         res = reconfigure_at_keyframe(s, p->data[0], p->linesize[0]);
881         if (res)
882             return res;
883     }
884
885     if (s->use15_7)
886         s->dist = optimum_dist(s);
887
888     res = write_bitstream(s, p->data[0], p->linesize[0], pkt->data, pkt->size, keyframe);
889
890     if (keyframe) {
891         new_key_frame(s);
892         s->last_key_frame = avctx->frame_number;
893         pkt->flags |= AV_PKT_FLAG_KEY;
894         av_log(avctx, AV_LOG_DEBUG, "Inserting key frame at frame %d\n", avctx->frame_number);
895     }
896
897     pkt->size = res;
898     *got_packet = 1;
899
900     return 0;
901 }
902
903 static av_cold int flashsv2_encode_end(AVCodecContext * avctx)
904 {
905     FlashSV2Context *s = avctx->priv_data;
906
907     cleanup(s);
908
909     return 0;
910 }
911
912 AVCodec ff_flashsv2_encoder = {
913     .name           = "flashsv2",
914     .long_name      = NULL_IF_CONFIG_SMALL("Flash Screen Video Version 2"),
915     .type           = AVMEDIA_TYPE_VIDEO,
916     .id             = AV_CODEC_ID_FLASHSV2,
917     .priv_data_size = sizeof(FlashSV2Context),
918     .init           = flashsv2_encode_init,
919     .encode2        = flashsv2_encode_frame,
920     .close          = flashsv2_encode_end,
921     .pix_fmts       = (const enum AVPixelFormat[]){ AV_PIX_FMT_BGR24, AV_PIX_FMT_NONE },
922 };