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