avcodec/cinepakenc: use av_malloc_array()
[ffmpeg.git] / libavcodec / cinepakenc.c
1 /*
2  * Cinepak encoder (c) 2011 Tomas Härdin
3  * http://titan.codemill.se/~tomhar/cinepakenc.patch
4  *
5  * Fixes and improvements, vintage decoders compatibility
6  *  (c) 2013, 2014 Rl, Aetey Global Technologies AB
7
8 Permission is hereby granted, free of charge, to any person obtaining a
9 copy of this software and associated documentation files (the "Software"),
10 to deal in the Software without restriction, including without limitation
11 the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 and/or sell copies of the Software, and to permit persons to whom the
13 Software is furnished to do so, subject to the following conditions:
14
15 The above copyright notice and this permission notice shall be included
16 in all copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 OTHER DEALINGS IN THE SOFTWARE.
25
26  * TODO:
27  * - optimize: color space conversion, ...
28  * - implement options to set the min/max number of strips?
29  * MAYBE:
30  * - "optimally" split the frame into several non-regular areas
31  *   using a separate codebook pair for each area and approximating
32  *   the area by several rectangular strips (generally not full width ones)
33  *   (use quadtree splitting? a simple fixed-granularity grid?)
34  *
35  *
36  * version 2014-01-23 Rl
37  * - added option handling for flexibility
38  *
39  * version 2014-01-21 Rl
40  * - believe it or not, now we get even smaller files, with better quality
41  *   (which means I missed an optimization earlier :)
42  *
43  * version 2014-01-20 Rl
44  * - made the encoder compatible with vintage decoders
45  *   and added some yet unused code for possible future
46  *   incremental codebook updates
47  * - fixed a small memory leak
48  *
49  * version 2013-04-28 Rl
50  * - bugfixed codebook optimization logic
51  *
52  * version 2013-02-14 Rl
53  * "Valentine's Day" version:
54  * - made strip division more robust
55  * - minimized bruteforcing the number of strips,
56  *   (costs some R/D but speeds up compession a lot), the heuristic
57  *   assumption is that score as a function of the number of strips has
58  *   one wide minimum which moves slowly, of course not fully true
59  * - simplified codebook generation,
60  *   the old code was meant for other optimizations than we actually do
61  * - optimized the codebook generation / error estimation for MODE_MC
62  *
63  * version 2013-02-12 Rl
64  * - separated codebook training sets, avoided the transfer of wasted bytes,
65  *   which yields both better quality and smaller files
66  * - now using the correct colorspace (TODO: move conversion to libswscale)
67  *
68  * version 2013-02-08 Rl
69  * - fixes/optimization in multistrip encoding and codebook size choice,
70  *   quality/bitrate is now better than that of the binary proprietary encoder
71  */
72
73 #include "libavutil/intreadwrite.h"
74 #include "avcodec.h"
75 #include "libavutil/lfg.h"
76 #include "elbg.h"
77 #include "internal.h"
78
79 #include "libavutil/avassert.h"
80 #include "libavutil/opt.h"
81
82 #define CVID_HEADER_SIZE 10
83 #define STRIP_HEADER_SIZE 12
84 #define CHUNK_HEADER_SIZE 4
85
86 #define MB_SIZE 4           //4x4 MBs
87 #define MB_AREA (MB_SIZE*MB_SIZE)
88
89 #define VECTOR_MAX 6        //six or four entries per vector depending on format
90 #define CODEBOOK_MAX 256    //size of a codebook
91
92 #define MAX_STRIPS  32      //Note: having fewer choices regarding the number of strips speeds up encoding (obviously)
93 #define MIN_STRIPS  1       //Note: having more strips speeds up encoding the frame (this is less obvious)
94 // MAX_STRIPS limits the maximum quality you can reach
95 //            when you want hight quality on high resolutions,
96 // MIN_STRIPS limits the minimum efficiently encodable bit rate
97 //            on low resolutions
98 // the numbers are only used for brute force optimization for the first frame,
99 // for the following frames they are adaptively readjusted
100 // NOTE the decoder in ffmpeg has its own arbitrary limitation on the number
101 // of strips, currently 32
102
103 typedef enum {
104     MODE_V1_ONLY = 0,
105     MODE_V1_V4,
106     MODE_MC,
107
108     MODE_COUNT,
109 } CinepakMode;
110
111 typedef enum {
112     ENC_V1,
113     ENC_V4,
114     ENC_SKIP,
115
116     ENC_UNCERTAIN
117 } mb_encoding;
118
119 typedef struct {
120     int v1_vector;                  //index into v1 codebook
121     int v1_error;                   //error when using V1 encoding
122     int v4_vector[4];               //indices into v4 codebooks
123     int v4_error;                   //error when using V4 encoding
124     int skip_error;                 //error when block is skipped (aka copied from last frame)
125     mb_encoding best_encoding;      //last result from calculate_mode_score()
126 } mb_info;
127
128 typedef struct {
129     int v1_codebook[CODEBOOK_MAX*VECTOR_MAX];
130     int v4_codebook[CODEBOOK_MAX*VECTOR_MAX];
131     int v1_size;
132     int v4_size;
133     CinepakMode mode;
134 } strip_info;
135
136 typedef struct {
137     const AVClass *class;
138     AVCodecContext *avctx;
139     unsigned char *pict_bufs[4], *strip_buf, *frame_buf;
140     AVFrame *last_frame;
141     AVFrame *best_frame;
142     AVFrame *scratch_frame;
143     AVFrame *input_frame;
144     enum AVPixelFormat pix_fmt;
145     int w, h;
146     int frame_buf_size;
147     int curframe, keyint;
148     AVLFG randctx;
149     uint64_t lambda;
150     int *codebook_input;
151     int *codebook_closest;
152     mb_info *mb;                                //MB RD state
153     int min_strips;          //the current limit
154     int max_strips;          //the current limit
155 #ifdef CINEPAKENC_DEBUG
156     mb_info *best_mb;                           //TODO: remove. only used for printing stats
157     int num_v1_mode, num_v4_mode, num_mc_mode;
158     int num_v1_encs, num_v4_encs, num_skips;
159 #endif
160 // options
161     int max_extra_cb_iterations;
162     int skip_empty_cb;
163     int min_min_strips;
164     int max_max_strips;
165     int strip_number_delta_range;
166 } CinepakEncContext;
167
168 #define OFFSET(x) offsetof(CinepakEncContext, x)
169 #define VE AV_OPT_FLAG_VIDEO_PARAM | AV_OPT_FLAG_ENCODING_PARAM
170 static const AVOption options[] = {
171     { "max_extra_cb_iterations", "Max extra codebook recalculation passes, more is better and slower", OFFSET(max_extra_cb_iterations), AV_OPT_TYPE_INT, { .i64 = 2 }, 0, INT_MAX, VE },
172     { "skip_empty_cb", "Avoid wasting bytes, ignore vintage MacOS decoder", OFFSET(skip_empty_cb), AV_OPT_TYPE_INT, { .i64 = 0 }, 0, 1, VE },
173     { "max_strips", "Limit strips/frame, vintage compatible is 1..3, otherwise the more the better", OFFSET(max_max_strips), AV_OPT_TYPE_INT, { .i64 = 3 }, MIN_STRIPS, MAX_STRIPS, VE },
174     { "min_strips", "Enforce min strips/frame, more is worse and faster, must be <= max_strips", OFFSET(min_min_strips), AV_OPT_TYPE_INT, { .i64 = MIN_STRIPS }, MIN_STRIPS, MAX_STRIPS, VE },
175     { "strip_number_adaptivity", "How fast the strip number adapts, more is slightly better, much slower", OFFSET(strip_number_delta_range), AV_OPT_TYPE_INT, { .i64 = 0 }, 0, MAX_STRIPS-MIN_STRIPS, VE },
176     { NULL },
177 };
178
179 static const AVClass cinepak_class = {
180     .class_name = "cinepak",
181     .item_name  = av_default_item_name,
182     .option     = options,
183     .version    = LIBAVUTIL_VERSION_INT,
184 };
185
186 static av_cold int cinepak_encode_init(AVCodecContext *avctx)
187 {
188     CinepakEncContext *s = avctx->priv_data;
189     int x, mb_count, strip_buf_size, frame_buf_size;
190
191     if (avctx->width & 3 || avctx->height & 3) {
192         av_log(avctx, AV_LOG_ERROR, "width and height must be multiples of four (got %ix%i)\n",
193                 avctx->width, avctx->height);
194         return AVERROR(EINVAL);
195     }
196
197     if (s->min_min_strips > s->max_max_strips) {
198         av_log(avctx, AV_LOG_ERROR, "minimal number of strips can not exceed maximal (got %i and %i)\n",
199                 s->min_min_strips, s->max_max_strips);
200         return AVERROR(EINVAL);
201     }
202
203     if (!(s->last_frame = av_frame_alloc()))
204         return AVERROR(ENOMEM);
205     if (!(s->best_frame = av_frame_alloc()))
206         goto enomem;
207     if (!(s->scratch_frame = av_frame_alloc()))
208         goto enomem;
209     if (avctx->pix_fmt == AV_PIX_FMT_RGB24)
210         if (!(s->input_frame = av_frame_alloc()))
211             goto enomem;
212
213     if (!(s->codebook_input = av_malloc(sizeof(int) * (avctx->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4) * (avctx->width * avctx->height) >> 2)))
214         goto enomem;
215
216     if (!(s->codebook_closest = av_malloc(sizeof(int) * (avctx->width * avctx->height) >> 2)))
217         goto enomem;
218
219     for(x = 0; x < (avctx->pix_fmt == AV_PIX_FMT_RGB24 ? 4 : 3); x++)
220         if(!(s->pict_bufs[x] = av_malloc((avctx->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4) * (avctx->width * avctx->height) >> 2)))
221             goto enomem;
222
223     mb_count = avctx->width * avctx->height / MB_AREA;
224
225     //the largest possible chunk is 0x31 with all MBs encoded in V4 mode
226     //and full codebooks being replaced in INTER mode,
227     // which is 34 bits per MB
228     //and 2*256 extra flag bits per strip
229     strip_buf_size = STRIP_HEADER_SIZE + 3 * CHUNK_HEADER_SIZE + 2 * VECTOR_MAX * CODEBOOK_MAX + 4 * (mb_count + (mb_count + 15) / 16) + (2 * CODEBOOK_MAX)/8;
230
231     frame_buf_size = CVID_HEADER_SIZE + s->max_max_strips * strip_buf_size;
232
233     if (!(s->strip_buf = av_malloc(strip_buf_size)))
234         goto enomem;
235
236     if (!(s->frame_buf = av_malloc(frame_buf_size)))
237         goto enomem;
238
239     if (!(s->mb = av_malloc_array(mb_count, sizeof(mb_info))))
240         goto enomem;
241
242 #ifdef CINEPAKENC_DEBUG
243     if (!(s->best_mb = av_malloc_array(mb_count, sizeof(mb_info))))
244         goto enomem;
245 #endif
246
247     av_lfg_init(&s->randctx, 1);
248     s->avctx = avctx;
249     s->w = avctx->width;
250     s->h = avctx->height;
251     s->frame_buf_size = frame_buf_size;
252     s->curframe = 0;
253     s->keyint = avctx->keyint_min;
254     s->pix_fmt = avctx->pix_fmt;
255
256     //set up AVFrames
257     s->last_frame->data[0]        = s->pict_bufs[0];
258     s->last_frame->linesize[0]    = s->w;
259     s->best_frame->data[0]        = s->pict_bufs[1];
260     s->best_frame->linesize[0]    = s->w;
261     s->scratch_frame->data[0]     = s->pict_bufs[2];
262     s->scratch_frame->linesize[0] = s->w;
263
264     if (s->pix_fmt == AV_PIX_FMT_RGB24) {
265         s->last_frame->data[1]        = s->last_frame->data[0] + s->w * s->h;
266         s->last_frame->data[2]        = s->last_frame->data[1] + ((s->w * s->h) >> 2);
267         s->last_frame->linesize[1]    = s->last_frame->linesize[2] = s->w >> 1;
268
269         s->best_frame->data[1]        = s->best_frame->data[0] + s->w * s->h;
270         s->best_frame->data[2]        = s->best_frame->data[1] + ((s->w * s->h) >> 2);
271         s->best_frame->linesize[1]    = s->best_frame->linesize[2] = s->w >> 1;
272
273         s->scratch_frame->data[1]     = s->scratch_frame->data[0] + s->w * s->h;
274         s->scratch_frame->data[2]     = s->scratch_frame->data[1] + ((s->w * s->h) >> 2);
275         s->scratch_frame->linesize[1] = s->scratch_frame->linesize[2] = s->w >> 1;
276
277         s->input_frame->data[0]       = s->pict_bufs[3];
278         s->input_frame->linesize[0]   = s->w;
279         s->input_frame->data[1]       = s->input_frame->data[0] + s->w * s->h;
280         s->input_frame->data[2]       = s->input_frame->data[1] + ((s->w * s->h) >> 2);
281         s->input_frame->linesize[1]   = s->input_frame->linesize[2] = s->w >> 1;
282     }
283
284     s->min_strips = s->min_min_strips;
285     s->max_strips = s->max_max_strips;
286
287 #ifdef CINEPAKENC_DEBUG
288     s->num_v1_mode = s->num_v4_mode = s->num_mc_mode = s->num_v1_encs = s->num_v4_encs = s->num_skips = 0;
289 #endif
290
291     return 0;
292
293 enomem:
294     av_frame_free(&s->last_frame);
295     av_frame_free(&s->best_frame);
296     av_frame_free(&s->scratch_frame);
297     if (avctx->pix_fmt == AV_PIX_FMT_RGB24)
298         av_frame_free(&s->input_frame);
299     av_freep(&s->codebook_input);
300     av_freep(&s->codebook_closest);
301     av_freep(&s->strip_buf);
302     av_freep(&s->frame_buf);
303     av_freep(&s->mb);
304 #ifdef CINEPAKENC_DEBUG
305     av_freep(&s->best_mb);
306 #endif
307
308     for(x = 0; x < (avctx->pix_fmt == AV_PIX_FMT_RGB24 ? 4 : 3); x++)
309         av_freep(&s->pict_bufs[x]);
310
311     return AVERROR(ENOMEM);
312 }
313
314 static int64_t calculate_mode_score(CinepakEncContext *s, int h, strip_info *info, int report, int *training_set_v1_shrunk, int *training_set_v4_shrunk
315 #ifdef CINEPAK_REPORT_SERR
316 , int64_t *serr
317 #endif
318 )
319 {
320     //score = FF_LAMBDA_SCALE * error + lambda * bits
321     int x;
322     int entry_size = s->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4;
323     int mb_count = s->w * h / MB_AREA;
324     mb_info *mb;
325     int64_t score1, score2, score3;
326     int64_t ret = s->lambda * ((info->v1_size ? CHUNK_HEADER_SIZE + info->v1_size * entry_size : 0) +
327                    (info->v4_size ? CHUNK_HEADER_SIZE + info->v4_size * entry_size : 0) +
328                    CHUNK_HEADER_SIZE) << 3;
329
330     //av_log(s->avctx, AV_LOG_INFO, "sizes %3i %3i -> %9lli score mb_count %i", info->v1_size, info->v4_size, (long long int)ret, mb_count);
331
332 #ifdef CINEPAK_REPORT_SERR
333     *serr = 0;
334 #endif
335
336     switch(info->mode) {
337     case MODE_V1_ONLY:
338         //one byte per MB
339         ret += s->lambda * 8 * mb_count;
340
341 // while calculating we assume all blocks are ENC_V1
342         for(x = 0; x < mb_count; x++) {
343             mb = &s->mb[x];
344             ret += FF_LAMBDA_SCALE * mb->v1_error;
345 #ifdef CINEPAK_REPORT_SERR
346             *serr += mb->v1_error;
347 #endif
348 // this function is never called for report in MODE_V1_ONLY
349 //            if(!report)
350             mb->best_encoding = ENC_V1;
351         }
352
353         break;
354     case MODE_V1_V4:
355         //9 or 33 bits per MB
356         if(report) {
357 // no moves between the corresponding training sets are allowed
358             *training_set_v1_shrunk = *training_set_v4_shrunk = 0;
359             for(x = 0; x < mb_count; x++) {
360                 int mberr;
361                 mb = &s->mb[x];
362                 if(mb->best_encoding == ENC_V1)
363                     score1 = s->lambda * 9  + FF_LAMBDA_SCALE * (mberr=mb->v1_error);
364                 else
365                     score1 = s->lambda * 33 + FF_LAMBDA_SCALE * (mberr=mb->v4_error);
366                 ret += score1;
367 #ifdef CINEPAK_REPORT_SERR
368                 *serr += mberr;
369 #endif
370             }
371         } else { // find best mode per block
372             for(x = 0; x < mb_count; x++) {
373                 mb = &s->mb[x];
374                 score1 = s->lambda * 9  + FF_LAMBDA_SCALE * mb->v1_error;
375                 score2 = s->lambda * 33 + FF_LAMBDA_SCALE * mb->v4_error;
376
377                 if(score1 <= score2) {
378                     ret += score1;
379 #ifdef CINEPAK_REPORT_SERR
380                     *serr += mb->v1_error;
381 #endif
382                     mb->best_encoding = ENC_V1;
383                 } else {
384                     ret += score2;
385 #ifdef CINEPAK_REPORT_SERR
386                     *serr += mb->v4_error;
387 #endif
388                     mb->best_encoding = ENC_V4;
389                 }
390             }
391         }
392
393         break;
394     case MODE_MC:
395         //1, 10 or 34 bits per MB
396         if(report) {
397             int v1_shrunk = 0, v4_shrunk = 0;
398             for(x = 0; x < mb_count; x++) {
399                 mb = &s->mb[x];
400 // it is OK to move blocks to ENC_SKIP here
401 // but not to any codebook encoding!
402                 score1 = s->lambda * 1  + FF_LAMBDA_SCALE * mb->skip_error;
403                 if(mb->best_encoding == ENC_SKIP) {
404                     ret += score1;
405 #ifdef CINEPAK_REPORT_SERR
406                     *serr += mb->skip_error;
407 #endif
408                 } else if(mb->best_encoding == ENC_V1) {
409                     if((score2=s->lambda * 10 + FF_LAMBDA_SCALE * mb->v1_error) >= score1) {
410                         mb->best_encoding = ENC_SKIP;
411                         ++v1_shrunk;
412                         ret += score1;
413 #ifdef CINEPAK_REPORT_SERR
414                         *serr += mb->skip_error;
415 #endif
416                     } else {
417                         ret += score2;
418 #ifdef CINEPAK_REPORT_SERR
419                         *serr += mb->v1_error;
420 #endif
421                     }
422                 } else {
423                     if((score3=s->lambda * 34 + FF_LAMBDA_SCALE * mb->v4_error) >= score1) {
424                         mb->best_encoding = ENC_SKIP;
425                         ++v4_shrunk;
426                         ret += score1;
427 #ifdef CINEPAK_REPORT_SERR
428                         *serr += mb->skip_error;
429 #endif
430                     } else {
431                         ret += score3;
432 #ifdef CINEPAK_REPORT_SERR
433                         *serr += mb->v4_error;
434 #endif
435                     }
436                 }
437             }
438             *training_set_v1_shrunk = v1_shrunk;
439             *training_set_v4_shrunk = v4_shrunk;
440         } else { // find best mode per block
441             for(x = 0; x < mb_count; x++) {
442                 mb = &s->mb[x];
443                 score1 = s->lambda * 1  + FF_LAMBDA_SCALE * mb->skip_error;
444                 score2 = s->lambda * 10 + FF_LAMBDA_SCALE * mb->v1_error;
445                 score3 = s->lambda * 34 + FF_LAMBDA_SCALE * mb->v4_error;
446
447                 if(score1 <= score2 && score1 <= score3) {
448                     ret += score1;
449 #ifdef CINEPAK_REPORT_SERR
450                     *serr += mb->skip_error;
451 #endif
452                     mb->best_encoding = ENC_SKIP;
453                 } else if(score2 <= score3) {
454                     ret += score2;
455 #ifdef CINEPAK_REPORT_SERR
456                     *serr += mb->v1_error;
457 #endif
458                     mb->best_encoding = ENC_V1;
459                 } else {
460                     ret += score3;
461 #ifdef CINEPAK_REPORT_SERR
462                     *serr += mb->v4_error;
463 #endif
464                     mb->best_encoding = ENC_V4;
465                 }
466             }
467         }
468
469         break;
470     }
471
472     return ret;
473 }
474
475 static int write_chunk_header(unsigned char *buf, int chunk_type, int chunk_size)
476 {
477     buf[0] = chunk_type;
478     AV_WB24(&buf[1], chunk_size + CHUNK_HEADER_SIZE);
479     return CHUNK_HEADER_SIZE;
480 }
481
482 static int encode_codebook(CinepakEncContext *s, int *codebook, int size, int chunk_type_yuv, int chunk_type_gray, unsigned char *buf)
483 {
484     int x, y, ret, entry_size = s->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4;
485     int incremental_codebook_replacement_mode = 0; // hardcoded here,
486                 // the compiler should notice that this is a constant -- rl
487
488     ret = write_chunk_header(buf,
489           s->pix_fmt == AV_PIX_FMT_RGB24 ?
490            chunk_type_yuv+(incremental_codebook_replacement_mode?1:0) :
491            chunk_type_gray+(incremental_codebook_replacement_mode?1:0),
492           entry_size * size
493            + (incremental_codebook_replacement_mode?(size+31)/32*4:0) );
494
495 // we do codebook encoding according to the "intra" mode
496 // but we keep the "dead" code for reference in case we will want
497 // to use incremental codebook updates (which actually would give us
498 // "kind of" motion compensation, especially in 1 strip/frame case) -- rl
499 // (of course, the code will be not useful as-is)
500     if(incremental_codebook_replacement_mode) {
501         int flags = 0;
502         int flagsind;
503         for(x = 0; x < size; x++) {
504             if(flags == 0) {
505                 flagsind = ret;
506                 ret += 4;
507                 flags = 0x80000000;
508             } else
509                 flags = ((flags>>1) | 0x80000000);
510             for(y = 0; y < entry_size; y++)
511                 buf[ret++] = codebook[y + x*entry_size] ^ (y >= 4 ? 0x80 : 0);
512             if((flags&0xffffffff) == 0xffffffff) {
513                 AV_WB32(&buf[flagsind], flags);
514                 flags = 0;
515             }
516         }
517         if(flags)
518             AV_WB32(&buf[flagsind], flags);
519     } else
520         for(x = 0; x < size; x++)
521             for(y = 0; y < entry_size; y++)
522                 buf[ret++] = codebook[y + x*entry_size] ^ (y >= 4 ? 0x80 : 0);
523
524     return ret;
525 }
526
527 //sets out to the sub picture starting at (x,y) in in
528 static void get_sub_picture(CinepakEncContext *s, int x, int y, AVPicture *in, AVPicture *out)
529 {
530     out->data[0] = in->data[0] + x + y * in->linesize[0];
531     out->linesize[0] = in->linesize[0];
532
533     if(s->pix_fmt == AV_PIX_FMT_RGB24) {
534         out->data[1] = in->data[1] + (x >> 1) + (y >> 1) * in->linesize[1];
535         out->linesize[1] = in->linesize[1];
536
537         out->data[2] = in->data[2] + (x >> 1) + (y >> 1) * in->linesize[2];
538         out->linesize[2] = in->linesize[2];
539     }
540 }
541
542 //decodes the V1 vector in mb into the 4x4 MB pointed to by sub_pict
543 static void decode_v1_vector(CinepakEncContext *s, AVPicture *sub_pict, int v1_vector, strip_info *info)
544 {
545     int entry_size = s->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4;
546
547     sub_pict->data[0][0] =
548             sub_pict->data[0][1] =
549             sub_pict->data[0][    sub_pict->linesize[0]] =
550             sub_pict->data[0][1+  sub_pict->linesize[0]] = info->v1_codebook[v1_vector*entry_size];
551
552     sub_pict->data[0][2] =
553             sub_pict->data[0][3] =
554             sub_pict->data[0][2+  sub_pict->linesize[0]] =
555             sub_pict->data[0][3+  sub_pict->linesize[0]] = info->v1_codebook[v1_vector*entry_size+1];
556
557     sub_pict->data[0][2*sub_pict->linesize[0]] =
558             sub_pict->data[0][1+2*sub_pict->linesize[0]] =
559             sub_pict->data[0][  3*sub_pict->linesize[0]] =
560             sub_pict->data[0][1+3*sub_pict->linesize[0]] = info->v1_codebook[v1_vector*entry_size+2];
561
562     sub_pict->data[0][2+2*sub_pict->linesize[0]] =
563             sub_pict->data[0][3+2*sub_pict->linesize[0]] =
564             sub_pict->data[0][2+3*sub_pict->linesize[0]] =
565             sub_pict->data[0][3+3*sub_pict->linesize[0]] = info->v1_codebook[v1_vector*entry_size+3];
566
567     if(s->pix_fmt == AV_PIX_FMT_RGB24) {
568         sub_pict->data[1][0] =
569             sub_pict->data[1][1] =
570             sub_pict->data[1][    sub_pict->linesize[1]] =
571             sub_pict->data[1][1+  sub_pict->linesize[1]] = info->v1_codebook[v1_vector*entry_size+4];
572
573         sub_pict->data[2][0] =
574             sub_pict->data[2][1] =
575             sub_pict->data[2][    sub_pict->linesize[2]] =
576             sub_pict->data[2][1+  sub_pict->linesize[2]] = info->v1_codebook[v1_vector*entry_size+5];
577     }
578 }
579
580 //decodes the V4 vectors in mb into the 4x4 MB pointed to by sub_pict
581 static void decode_v4_vector(CinepakEncContext *s, AVPicture *sub_pict, int *v4_vector, strip_info *info)
582 {
583     int i, x, y, entry_size = s->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4;
584
585     for(i = y = 0; y < 4; y += 2) {
586         for(x = 0; x < 4; x += 2, i++) {
587             sub_pict->data[0][x   +     y*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size];
588             sub_pict->data[0][x+1 +     y*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size+1];
589             sub_pict->data[0][x   + (y+1)*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size+2];
590             sub_pict->data[0][x+1 + (y+1)*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size+3];
591
592             if(s->pix_fmt == AV_PIX_FMT_RGB24) {
593                 sub_pict->data[1][(x>>1) + (y>>1)*sub_pict->linesize[1]] = info->v4_codebook[v4_vector[i]*entry_size+4];
594                 sub_pict->data[2][(x>>1) + (y>>1)*sub_pict->linesize[2]] = info->v4_codebook[v4_vector[i]*entry_size+5];
595             }
596         }
597     }
598 }
599
600 static void copy_mb(CinepakEncContext *s, AVPicture *a, AVPicture *b)
601 {
602     int y, p;
603
604     for(y = 0; y < MB_SIZE; y++) {
605         memcpy(a->data[0]+y*a->linesize[0], b->data[0]+y*b->linesize[0],
606                MB_SIZE);
607     }
608
609     if(s->pix_fmt == AV_PIX_FMT_RGB24) {
610         for(p = 1; p <= 2; p++) {
611             for(y = 0; y < MB_SIZE/2; y++) {
612                 memcpy(a->data[p] + y*a->linesize[p],
613                        b->data[p] + y*b->linesize[p],
614                        MB_SIZE/2);
615             }
616         }
617     }
618 }
619
620 static int encode_mode(CinepakEncContext *s, int h, AVPicture *scratch_pict, AVPicture *last_pict, strip_info *info, unsigned char *buf)
621 {
622     int x, y, z, flags, bits, temp_size, header_ofs, ret = 0, mb_count = s->w * h / MB_AREA;
623     int needs_extra_bit, should_write_temp;
624     unsigned char temp[64]; //32/2 = 16 V4 blocks at 4 B each -> 64 B
625     mb_info *mb;
626     AVPicture sub_scratch = {{0}}, sub_last = {{0}};
627
628     //encode codebooks
629 ////// MacOS vintage decoder compatibility dictates the presence of
630 ////// the codebook chunk even when the codebook is empty - pretty dumb...
631 ////// and also the certain order of the codebook chunks -- rl
632     if(info->v4_size || !s->skip_empty_cb)
633         ret += encode_codebook(s, info->v4_codebook, info->v4_size, 0x20, 0x24, buf + ret);
634
635     if(info->v1_size || !s->skip_empty_cb)
636         ret += encode_codebook(s, info->v1_codebook, info->v1_size, 0x22, 0x26, buf + ret);
637
638     //update scratch picture
639     for(z = y = 0; y < h; y += MB_SIZE) {
640         for(x = 0; x < s->w; x += MB_SIZE, z++) {
641             mb = &s->mb[z];
642
643             get_sub_picture(s, x, y, scratch_pict, &sub_scratch);
644
645             if(info->mode == MODE_MC && mb->best_encoding == ENC_SKIP) {
646                 get_sub_picture(s, x, y, last_pict, &sub_last);
647                 copy_mb(s, &sub_scratch, &sub_last);
648             } else if(info->mode == MODE_V1_ONLY || mb->best_encoding == ENC_V1)
649                 decode_v1_vector(s, &sub_scratch, mb->v1_vector, info);
650             else
651                 decode_v4_vector(s, &sub_scratch, mb->v4_vector, info);
652         }
653     }
654
655     switch(info->mode) {
656     case MODE_V1_ONLY:
657         //av_log(s->avctx, AV_LOG_INFO, "mb_count = %i\n", mb_count);
658         ret += write_chunk_header(buf + ret, 0x32, mb_count);
659
660         for(x = 0; x < mb_count; x++)
661             buf[ret++] = s->mb[x].v1_vector;
662
663         break;
664     case MODE_V1_V4:
665         //remember header position
666         header_ofs = ret;
667         ret += CHUNK_HEADER_SIZE;
668
669         for(x = 0; x < mb_count; x += 32) {
670             flags = 0;
671             for(y = x; y < FFMIN(x+32, mb_count); y++)
672                 if(s->mb[y].best_encoding == ENC_V4)
673                     flags |= 1 << (31 - y + x);
674
675             AV_WB32(&buf[ret], flags);
676             ret += 4;
677
678             for(y = x; y < FFMIN(x+32, mb_count); y++) {
679                 mb = &s->mb[y];
680
681                 if(mb->best_encoding == ENC_V1)
682                     buf[ret++] = mb->v1_vector;
683                 else
684                     for(z = 0; z < 4; z++)
685                         buf[ret++] = mb->v4_vector[z];
686             }
687         }
688
689         write_chunk_header(buf + header_ofs, 0x30, ret - header_ofs - CHUNK_HEADER_SIZE);
690
691         break;
692     case MODE_MC:
693         //remember header position
694         header_ofs = ret;
695         ret += CHUNK_HEADER_SIZE;
696         flags = bits = temp_size = 0;
697
698         for(x = 0; x < mb_count; x++) {
699             mb = &s->mb[x];
700             flags |= (mb->best_encoding != ENC_SKIP) << (31 - bits++);
701             needs_extra_bit = 0;
702             should_write_temp = 0;
703
704             if(mb->best_encoding != ENC_SKIP) {
705                 if(bits < 32)
706                     flags |= (mb->best_encoding == ENC_V4) << (31 - bits++);
707                 else
708                     needs_extra_bit = 1;
709             }
710
711             if(bits == 32) {
712                 AV_WB32(&buf[ret], flags);
713                 ret += 4;
714                 flags = bits = 0;
715
716                 if(mb->best_encoding == ENC_SKIP || needs_extra_bit) {
717                     memcpy(&buf[ret], temp, temp_size);
718                     ret += temp_size;
719                     temp_size = 0;
720                 } else
721                     should_write_temp = 1;
722             }
723
724             if(needs_extra_bit) {
725                 flags = (mb->best_encoding == ENC_V4) << 31;
726                 bits = 1;
727             }
728
729             if(mb->best_encoding == ENC_V1)
730                 temp[temp_size++] = mb->v1_vector;
731             else if(mb->best_encoding == ENC_V4)
732                 for(z = 0; z < 4; z++)
733                     temp[temp_size++] = mb->v4_vector[z];
734
735             if(should_write_temp) {
736                 memcpy(&buf[ret], temp, temp_size);
737                 ret += temp_size;
738                 temp_size = 0;
739             }
740         }
741
742         if(bits > 0) {
743             AV_WB32(&buf[ret], flags);
744             ret += 4;
745             memcpy(&buf[ret], temp, temp_size);
746             ret += temp_size;
747         }
748
749         write_chunk_header(buf + header_ofs, 0x31, ret - header_ofs - CHUNK_HEADER_SIZE);
750
751         break;
752     }
753
754     return ret;
755 }
756
757 //computes distortion of 4x4 MB in b compared to a
758 static int compute_mb_distortion(CinepakEncContext *s, AVPicture *a, AVPicture *b)
759 {
760     int x, y, p, d, ret = 0;
761
762     for(y = 0; y < MB_SIZE; y++) {
763         for(x = 0; x < MB_SIZE; x++) {
764             d = a->data[0][x + y*a->linesize[0]] - b->data[0][x + y*b->linesize[0]];
765             ret += d*d;
766         }
767     }
768
769     if(s->pix_fmt == AV_PIX_FMT_RGB24) {
770         for(p = 1; p <= 2; p++) {
771             for(y = 0; y < MB_SIZE/2; y++) {
772                 for(x = 0; x < MB_SIZE/2; x++) {
773                     d = a->data[p][x + y*a->linesize[p]] - b->data[p][x + y*b->linesize[p]];
774                     ret += d*d;
775                 }
776             }
777         }
778     }
779
780     return ret;
781 }
782
783 // return the possibly adjusted size of the codebook
784 #define CERTAIN(x) ((x)!=ENC_UNCERTAIN)
785 static int quantize(CinepakEncContext *s, int h, AVPicture *pict,
786                     int v1mode, strip_info *info,
787                     mb_encoding encoding)
788 {
789     int x, y, i, j, k, x2, y2, x3, y3, plane, shift, mbn;
790     int entry_size = s->pix_fmt == AV_PIX_FMT_RGB24 ? 6 : 4;
791     int *codebook = v1mode ? info->v1_codebook : info->v4_codebook;
792     int size = v1mode ? info->v1_size : info->v4_size;
793     int64_t total_error = 0;
794     uint8_t vq_pict_buf[(MB_AREA*3)/2];
795     AVPicture sub_pict, vq_pict;
796
797     for(mbn = i = y = 0; y < h; y += MB_SIZE) {
798         for(x = 0; x < s->w; x += MB_SIZE, ++mbn) {
799             int *base;
800
801             if(CERTAIN(encoding)) {
802 // use for the training only the blocks known to be to be encoded [sic:-]
803                if(s->mb[mbn].best_encoding != encoding) continue;
804             }
805
806             base = s->codebook_input + i*entry_size;
807             if(v1mode) {
808                 //subsample
809                 for(j = y2 = 0; y2 < entry_size; y2 += 2) {
810                     for(x2 = 0; x2 < 4; x2 += 2, j++) {
811                         plane = y2 < 4 ? 0 : 1 + (x2 >> 1);
812                         shift = y2 < 4 ? 0 : 1;
813                         x3 = shift ? 0 : x2;
814                         y3 = shift ? 0 : y2;
815                         base[j] = (pict->data[plane][((x+x3) >> shift) +      ((y+y3) >> shift)      * pict->linesize[plane]] +
816                                    pict->data[plane][((x+x3) >> shift) + 1 +  ((y+y3) >> shift)      * pict->linesize[plane]] +
817                                    pict->data[plane][((x+x3) >> shift) +     (((y+y3) >> shift) + 1) * pict->linesize[plane]] +
818                                    pict->data[plane][((x+x3) >> shift) + 1 + (((y+y3) >> shift) + 1) * pict->linesize[plane]]) >> 2;
819                     }
820                 }
821             } else {
822                 //copy
823                 for(j = y2 = 0; y2 < MB_SIZE; y2 += 2) {
824                     for(x2 = 0; x2 < MB_SIZE; x2 += 2) {
825                         for(k = 0; k < entry_size; k++, j++) {
826                             plane = k >= 4 ? k - 3 : 0;
827
828                             if(k >= 4) {
829                                 x3 = (x+x2) >> 1;
830                                 y3 = (y+y2) >> 1;
831                             } else {
832                                 x3 = x + x2 + (k & 1);
833                                 y3 = y + y2 + (k >> 1);
834                             }
835
836                             base[j] = pict->data[plane][x3 + y3*pict->linesize[plane]];
837                         }
838                     }
839                 }
840             }
841             i += v1mode ? 1 : 4;
842         }
843     }
844 //    if(i < mbn*(v1mode ? 1 : 4)) {
845 //        av_log(s->avctx, AV_LOG_INFO, "reducing training set for %s from %i to %i (encoding %i)\n", v1mode?"v1":"v4", mbn*(v1mode ? 1 : 4), i, encoding);
846 //    }
847
848     if(i == 0) // empty training set, nothing to do
849         return 0;
850     if(i < size) {
851         //av_log(s->avctx, (CERTAIN(encoding) ? AV_LOG_ERROR : AV_LOG_INFO), "WOULD WASTE: %s cbsize %i bigger than training set size %i (encoding %i)\n", v1mode?"v1":"v4", size, i, encoding);
852         size = i;
853     }
854
855     avpriv_init_elbg(s->codebook_input, entry_size, i, codebook, size, 1, s->codebook_closest, &s->randctx);
856     avpriv_do_elbg(s->codebook_input, entry_size, i, codebook, size, 1, s->codebook_closest, &s->randctx);
857
858     //setup vq_pict, which contains a single MB
859     vq_pict.data[0] = vq_pict_buf;
860     vq_pict.linesize[0] = MB_SIZE;
861     vq_pict.data[1] = &vq_pict_buf[MB_AREA];
862     vq_pict.data[2] = vq_pict.data[1] + (MB_AREA >> 2);
863     vq_pict.linesize[1] = vq_pict.linesize[2] = MB_SIZE >> 1;
864
865     //copy indices
866     for(i = j = y = 0; y < h; y += MB_SIZE) {
867         for(x = 0; x < s->w; x += MB_SIZE, j++) {
868             mb_info *mb = &s->mb[j];
869 // skip uninteresting blocks if we know their preferred encoding
870             if(CERTAIN(encoding) && mb->best_encoding != encoding)
871                 continue;
872
873             //point sub_pict to current MB
874             get_sub_picture(s, x, y, pict, &sub_pict);
875
876             if(v1mode) {
877                 mb->v1_vector = s->codebook_closest[i];
878
879                 //fill in vq_pict with V1 data
880                 decode_v1_vector(s, &vq_pict, mb->v1_vector, info);
881
882                 mb->v1_error = compute_mb_distortion(s, &sub_pict, &vq_pict);
883                 total_error += mb->v1_error;
884             } else {
885                 for(k = 0; k < 4; k++)
886                     mb->v4_vector[k] = s->codebook_closest[i+k];
887
888                 //fill in vq_pict with V4 data
889                 decode_v4_vector(s, &vq_pict, mb->v4_vector, info);
890
891                 mb->v4_error = compute_mb_distortion(s, &sub_pict, &vq_pict);
892                 total_error += mb->v4_error;
893             }
894             i += v1mode ? 1 : 4;
895         }
896     }
897 // check that we did it right in the beginning of the function
898     av_assert0(i >= size); // training set is no smaller than the codebook
899
900     //av_log(s->avctx, AV_LOG_INFO, "isv1 %i size= %i i= %i error %lli\n", v1mode, size, i, (long long int)total_error);
901
902     return size;
903 }
904
905 static void calculate_skip_errors(CinepakEncContext *s, int h, AVPicture *last_pict, AVPicture *pict, strip_info *info)
906 {
907     int x, y, i;
908     AVPicture sub_last, sub_pict;
909
910     for(i = y = 0; y < h; y += MB_SIZE) {
911         for(x = 0; x < s->w; x += MB_SIZE, i++) {
912             get_sub_picture(s, x, y, last_pict, &sub_last);
913             get_sub_picture(s, x, y, pict,      &sub_pict);
914
915             s->mb[i].skip_error = compute_mb_distortion(s, &sub_last, &sub_pict);
916         }
917     }
918 }
919
920 static void write_strip_header(CinepakEncContext *s, int y, int h, int keyframe, unsigned char *buf, int strip_size)
921 {
922 // actually we are exclusively using intra strip coding (how much can we win
923 // otherwise? how to choose which part of a codebook to update?),
924 // keyframes are different only because we disallow ENC_SKIP on them -- rl
925 // (besides, the logic here used to be inverted: )
926 //    buf[0] = keyframe ? 0x11: 0x10;
927     buf[0] = keyframe ? 0x10: 0x11;
928     AV_WB24(&buf[1], strip_size + STRIP_HEADER_SIZE);
929 //    AV_WB16(&buf[4], y); /* using absolute y values works -- rl */
930     AV_WB16(&buf[4], 0); /* using relative values works as well -- rl */
931     AV_WB16(&buf[6], 0);
932 //    AV_WB16(&buf[8], y+h); /* using absolute y values works -- rl */
933     AV_WB16(&buf[8], h); /* using relative values works as well -- rl */
934     AV_WB16(&buf[10], s->w);
935     //av_log(s->avctx, AV_LOG_INFO, "write_strip_header() %x keyframe=%d\n", buf[0], keyframe);
936 }
937
938 static int rd_strip(CinepakEncContext *s, int y, int h, int keyframe, AVPicture *last_pict, AVPicture *pict, AVPicture *scratch_pict, unsigned char *buf, int64_t *best_score
939 #ifdef CINEPAK_REPORT_SERR
940 , int64_t *best_serr
941 #endif
942 )
943 {
944     int64_t score = 0;
945 #ifdef CINEPAK_REPORT_SERR
946     int64_t serr;
947 #endif
948     int best_size = 0;
949     strip_info info;
950 // for codebook optimization:
951     int v1enough, v1_size, v4enough, v4_size;
952     int new_v1_size, new_v4_size;
953     int v1shrunk, v4shrunk;
954
955     if(!keyframe)
956         calculate_skip_errors(s, h, last_pict, pict, &info);
957
958     //try some powers of 4 for the size of the codebooks
959     //constraint the v4 codebook to be no bigger than v1 one,
960     //(and no less than v1_size/4)
961     //thus making v1 preferable and possibly losing small details? should be ok
962 #define SMALLEST_CODEBOOK 1
963     for(v1enough = 0, v1_size = SMALLEST_CODEBOOK; v1_size <= CODEBOOK_MAX && !v1enough; v1_size <<= 2) {
964         for(v4enough = 0, v4_size = 0; v4_size <= v1_size && !v4enough; v4_size = v4_size ? v4_size << 2 : v1_size >= SMALLEST_CODEBOOK << 2 ? v1_size >> 2 : SMALLEST_CODEBOOK) {
965             //try all modes
966             for(CinepakMode mode = 0; mode < MODE_COUNT; mode++) {
967                 //don't allow MODE_MC in intra frames
968                 if(keyframe && mode == MODE_MC)
969                     continue;
970
971                 if(mode == MODE_V1_ONLY) {
972                     info.v1_size = v1_size;
973 // the size may shrink even before optimizations if the input is short:
974                     info.v1_size = quantize(s, h, pict, 1, &info, ENC_UNCERTAIN);
975                     if(info.v1_size < v1_size)
976 // too few eligible blocks, no sense in trying bigger sizes
977                         v1enough = 1;
978
979                     info.v4_size = 0;
980                 } else { // mode != MODE_V1_ONLY
981                     // if v4 codebook is empty then only allow V1-only mode
982                     if(!v4_size)
983                         continue;
984
985                     if(mode == MODE_V1_V4) {
986                         info.v4_size = v4_size;
987                         info.v4_size = quantize(s, h, pict, 0, &info, ENC_UNCERTAIN);
988                         if(info.v4_size < v4_size)
989 // too few eligible blocks, no sense in trying bigger sizes
990                             v4enough = 1;
991                     }
992                 }
993
994                 info.mode = mode;
995 // choose the best encoding per block, based on current experience
996                 score = calculate_mode_score(s, h, &info, 0,
997                                              &v1shrunk, &v4shrunk
998 #ifdef CINEPAK_REPORT_SERR
999 , &serr
1000 #endif
1001 );
1002
1003                 if(mode != MODE_V1_ONLY){
1004                     int extra_iterations_limit = s->max_extra_cb_iterations;
1005 // recompute the codebooks, omitting the extra blocks
1006 // we assume we _may_ come here with more blocks to encode than before
1007                     info.v1_size = v1_size;
1008                     new_v1_size = quantize(s, h, pict, 1, &info, ENC_V1);
1009                     if(new_v1_size < info.v1_size){
1010                         //av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: cut v1 codebook to %i entries\n", mode, v1_size, v4_size, new_v1_size);
1011                         info.v1_size = new_v1_size;
1012                     }
1013 // we assume we _may_ come here with more blocks to encode than before
1014                     info.v4_size = v4_size;
1015                     new_v4_size = quantize(s, h, pict, 0, &info, ENC_V4);
1016                     if(new_v4_size < info.v4_size) {
1017                         //av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: cut v4 codebook to %i entries at first iteration\n", mode, v1_size, v4_size, new_v4_size);
1018                         info.v4_size = new_v4_size;
1019                     }
1020 // calculate the resulting score
1021 // (do not move blocks to codebook encodings now, as some blocks may have
1022 // got bigger errors despite a smaller training set - but we do not
1023 // ever grow the training sets back)
1024                     for(;;) {
1025                         score = calculate_mode_score(s, h, &info, 1,
1026                                                      &v1shrunk, &v4shrunk
1027 #ifdef CINEPAK_REPORT_SERR
1028 , &serr
1029 #endif
1030 );
1031 // do we have a reason to reiterate? if so, have we reached the limit?
1032                         if((!v1shrunk && !v4shrunk) || !extra_iterations_limit--) break;
1033 // recompute the codebooks, omitting the extra blocks
1034                         if(v1shrunk) {
1035                             info.v1_size = v1_size;
1036                             new_v1_size = quantize(s, h, pict, 1, &info, ENC_V1);
1037                             if(new_v1_size < info.v1_size){
1038                                 //av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: cut v1 codebook to %i entries\n", mode, v1_size, v4_size, new_v1_size);
1039                                 info.v1_size = new_v1_size;
1040                             }
1041                         }
1042                         if(v4shrunk) {
1043                             info.v4_size = v4_size;
1044                             new_v4_size = quantize(s, h, pict, 0, &info, ENC_V4);
1045                             if(new_v4_size < info.v4_size) {
1046                                 //av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: cut v4 codebook to %i entries\n", mode, v1_size, v4_size, new_v4_size);
1047                                 info.v4_size = new_v4_size;
1048                             }
1049                         }
1050                     }
1051                 }
1052
1053                 //av_log(s->avctx, AV_LOG_INFO, "%3i %3i score = %lli\n", v1_size, v4_size, (long long int)score);
1054
1055                 if(best_size == 0 || score < *best_score) {
1056
1057                     *best_score = score;
1058 #ifdef CINEPAK_REPORT_SERR
1059                     *best_serr = serr;
1060 #endif
1061                     best_size = encode_mode(s, h, scratch_pict, last_pict, &info, s->strip_buf + STRIP_HEADER_SIZE);
1062
1063                     //av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: %18lli %i B", mode, info.v1_size, info.v4_size, (long long int)score, best_size);
1064                     //av_log(s->avctx, AV_LOG_INFO, "\n");
1065 #ifdef CINEPAK_REPORT_SERR
1066                     av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: %18lli %i B\n", mode, v1_size, v4_size, (long long int)serr, best_size);
1067 #endif
1068
1069 #ifdef CINEPAKENC_DEBUG
1070                     //save MB encoding choices
1071                     memcpy(s->best_mb, s->mb, mb_count*sizeof(mb_info));
1072 #endif
1073
1074                     //memcpy(strip_temp + STRIP_HEADER_SIZE, strip_temp, best_size);
1075                     write_strip_header(s, y, h, keyframe, s->strip_buf, best_size);
1076
1077                 }
1078             }
1079         }
1080     }
1081
1082 #ifdef CINEPAKENC_DEBUG
1083     //gather stats. this will only work properly of MAX_STRIPS == 1
1084     if(best_info.mode == MODE_V1_ONLY) {
1085         s->num_v1_mode++;
1086         s->num_v1_encs += s->w*h/MB_AREA;
1087     } else {
1088         if(best_info.mode == MODE_V1_V4)
1089             s->num_v4_mode++;
1090         else
1091             s->num_mc_mode++;
1092
1093         int x;
1094         for(x = 0; x < s->w*h/MB_AREA; x++)
1095             if(s->best_mb[x].best_encoding == ENC_V1)
1096                 s->num_v1_encs++;
1097             else if(s->best_mb[x].best_encoding == ENC_V4)
1098                 s->num_v4_encs++;
1099             else
1100                 s->num_skips++;
1101     }
1102 #endif
1103
1104     best_size += STRIP_HEADER_SIZE;
1105     memcpy(buf, s->strip_buf, best_size);
1106
1107     return best_size;
1108 }
1109
1110 static int write_cvid_header(CinepakEncContext *s, unsigned char *buf, int num_strips, int data_size, int isakeyframe)
1111 {
1112     buf[0] = isakeyframe ? 0 : 1;
1113     AV_WB24(&buf[1], data_size + CVID_HEADER_SIZE);
1114     AV_WB16(&buf[4], s->w);
1115     AV_WB16(&buf[6], s->h);
1116     AV_WB16(&buf[8], num_strips);
1117
1118     return CVID_HEADER_SIZE;
1119 }
1120
1121 static int rd_frame(CinepakEncContext *s, const AVFrame *frame, int isakeyframe, unsigned char *buf, int buf_size)
1122 {
1123     int num_strips, strip, i, y, nexty, size, temp_size;
1124     AVPicture last_pict, pict, scratch_pict;
1125     int64_t best_score = 0, score, score_temp;
1126 #ifdef CINEPAK_REPORT_SERR
1127     int64_t best_serr = 0, serr, serr_temp;
1128 #endif
1129
1130     int best_nstrips = -1, best_size = -1; // mark as uninitialzed
1131
1132     if(s->pix_fmt == AV_PIX_FMT_RGB24) {
1133         int x;
1134 // build a copy of the given frame in the correct colorspace
1135         for(y = 0; y < s->h; y += 2) {
1136             for(x = 0; x < s->w; x += 2) {
1137                 uint8_t *ir[2]; int32_t r, g, b, rr, gg, bb;
1138                 ir[0] = ((AVPicture*)frame)->data[0] + x*3 + y*((AVPicture*)frame)->linesize[0];
1139                 ir[1] = ir[0] + ((AVPicture*)frame)->linesize[0];
1140                 get_sub_picture(s, x, y, (AVPicture*)s->input_frame, &scratch_pict);
1141                 r = g = b = 0;
1142                 for(i=0; i<4; ++i) {
1143                     int i1, i2;
1144                     i1 = (i&1); i2 = (i>=2);
1145                     rr = ir[i2][i1*3+0];
1146                     gg = ir[i2][i1*3+1];
1147                     bb = ir[i2][i1*3+2];
1148                     r += rr; g += gg; b += bb;
1149 // using fixed point arithmetic for portable repeatability, scaling by 2^23
1150 // "Y"
1151 //                    rr = 0.2857*rr + 0.5714*gg + 0.1429*bb;
1152                     rr = (2396625*rr + 4793251*gg + 1198732*bb) >> 23;
1153                     if(      rr <   0) rr =   0;
1154                     else if (rr > 255) rr = 255;
1155                     scratch_pict.data[0][i1 + i2*scratch_pict.linesize[0]] = rr;
1156                 }
1157 // let us scale down as late as possible
1158 //                r /= 4; g /= 4; b /= 4;
1159 // "U"
1160 //                rr = -0.1429*r - 0.2857*g + 0.4286*b;
1161                 rr = (-299683*r - 599156*g + 898839*b) >> 23;
1162                 if(      rr < -128) rr = -128;
1163                 else if (rr >  127) rr =  127;
1164                 scratch_pict.data[1][0] = rr + 128; // quantize needs unsigned
1165 // "V"
1166 //                rr = 0.3571*r - 0.2857*g - 0.0714*b;
1167                 rr = (748893*r - 599156*g - 149737*b) >> 23;
1168                 if(      rr < -128) rr = -128;
1169                 else if (rr >  127) rr =  127;
1170                 scratch_pict.data[2][0] = rr + 128; // quantize needs unsigned
1171             }
1172         }
1173     }
1174
1175     //would be nice but quite certainly incompatible with vintage players:
1176     // support encoding zero strips (meaning skip the whole frame)
1177     for(num_strips = s->min_strips; num_strips <= s->max_strips && num_strips <= s->h / MB_SIZE; num_strips++) {
1178         score = 0;
1179         size = 0;
1180 #ifdef CINEPAK_REPORT_SERR
1181         serr = 0;
1182 #endif
1183
1184         for(y = 0, strip = 1; y < s->h; strip++, y = nexty) {
1185             int strip_height;
1186
1187             nexty = strip * s->h / num_strips; // <= s->h
1188             //make nexty the next multiple of 4 if not already there
1189             if(nexty & 3)
1190                 nexty += 4 - (nexty & 3);
1191
1192             strip_height = nexty - y;
1193             if(strip_height <= 0) { // can this ever happen?
1194                 av_log(s->avctx, AV_LOG_INFO, "skipping zero height strip %i of %i\n", strip, num_strips);
1195                 continue;
1196             }
1197
1198             if(s->pix_fmt == AV_PIX_FMT_RGB24)
1199                 get_sub_picture(s, 0, y, (AVPicture*)s->input_frame,    &pict);
1200             else
1201                 get_sub_picture(s, 0, y, (AVPicture*)frame,              &pict);
1202             get_sub_picture(s, 0, y, (AVPicture*)s->last_frame,    &last_pict);
1203             get_sub_picture(s, 0, y, (AVPicture*)s->scratch_frame, &scratch_pict);
1204
1205             if((temp_size = rd_strip(s, y, strip_height, isakeyframe, &last_pict, &pict, &scratch_pict, s->frame_buf + size + CVID_HEADER_SIZE, &score_temp
1206 #ifdef CINEPAK_REPORT_SERR
1207 , &serr_temp
1208 #endif
1209 )) < 0)
1210                 return temp_size;
1211
1212             score += score_temp;
1213 #ifdef CINEPAK_REPORT_SERR
1214             serr += serr_temp;
1215 #endif
1216             size += temp_size;
1217             //av_log(s->avctx, AV_LOG_INFO, "strip %d, isakeyframe=%d", strip, isakeyframe);
1218             //av_log(s->avctx, AV_LOG_INFO, "\n");
1219         }
1220
1221         if(best_score == 0 || score < best_score) {
1222             best_score = score;
1223 #ifdef CINEPAK_REPORT_SERR
1224             best_serr = serr;
1225 #endif
1226             best_size = size + write_cvid_header(s, s->frame_buf, num_strips, size, isakeyframe);
1227             //av_log(s->avctx, AV_LOG_INFO, "best number of strips so far: %2i, %12lli, %i B\n", num_strips, (long long int)score, best_size);
1228 #ifdef CINEPAK_REPORT_SERR
1229             av_log(s->avctx, AV_LOG_INFO, "best number of strips so far: %2i, %12lli, %i B\n", num_strips, (long long int)serr, best_size);
1230 #endif
1231
1232             FFSWAP(AVFrame *, s->best_frame, s->scratch_frame);
1233             memcpy(buf, s->frame_buf, best_size);
1234             best_nstrips = num_strips;
1235         }
1236 // avoid trying too many strip numbers without a real reason
1237 // (this makes the processing of the very first frame faster)
1238         if(num_strips - best_nstrips > 4)
1239             break;
1240     }
1241
1242     av_assert0(best_nstrips >= 0 && best_size >= 0);
1243
1244 // let the number of strips slowly adapt to the changes in the contents,
1245 // compared to full bruteforcing every time this will occasionally lead
1246 // to some r/d performance loss but makes encoding up to several times faster
1247     if(!s->strip_number_delta_range) {
1248         if(best_nstrips == s->max_strips) { // let us try to step up
1249             s->max_strips = best_nstrips + 1;
1250             if(s->max_strips >= s->max_max_strips)
1251                 s->max_strips = s->max_max_strips;
1252         } else { // try to step down
1253             s->max_strips = best_nstrips;
1254         }
1255         s->min_strips = s->max_strips - 1;
1256         if(s->min_strips < s->min_min_strips)
1257             s->min_strips = s->min_min_strips;
1258     } else {
1259         s->max_strips = best_nstrips + s->strip_number_delta_range;
1260         if(s->max_strips >= s->max_max_strips)
1261             s->max_strips = s->max_max_strips;
1262         s->min_strips = best_nstrips - s->strip_number_delta_range;
1263         if(s->min_strips < s->min_min_strips)
1264             s->min_strips = s->min_min_strips;
1265     }
1266
1267     return best_size;
1268 }
1269
1270 static int cinepak_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
1271                                 const AVFrame *frame, int *got_packet)
1272 {
1273     CinepakEncContext *s = avctx->priv_data;
1274     int ret;
1275
1276     s->lambda = frame->quality ? frame->quality - 1 : 2 * FF_LAMBDA_SCALE;
1277
1278     if ((ret = ff_alloc_packet2(avctx, pkt, s->frame_buf_size)) < 0)
1279         return ret;
1280     ret = rd_frame(s, frame, (s->curframe == 0), pkt->data, s->frame_buf_size);
1281     pkt->size = ret;
1282     if (s->curframe == 0)
1283         pkt->flags |= AV_PKT_FLAG_KEY;
1284     *got_packet = 1;
1285
1286     FFSWAP(AVFrame *, s->last_frame, s->best_frame);
1287
1288     if (++s->curframe >= s->keyint)
1289         s->curframe = 0;
1290
1291     return 0;
1292 }
1293
1294 static av_cold int cinepak_encode_end(AVCodecContext *avctx)
1295 {
1296     CinepakEncContext *s = avctx->priv_data;
1297     int x;
1298
1299     av_frame_free(&s->last_frame);
1300     av_frame_free(&s->best_frame);
1301     av_frame_free(&s->scratch_frame);
1302     if (avctx->pix_fmt == AV_PIX_FMT_RGB24)
1303         av_frame_free(&s->input_frame);
1304     av_freep(&s->codebook_input);
1305     av_freep(&s->codebook_closest);
1306     av_freep(&s->strip_buf);
1307     av_freep(&s->frame_buf);
1308     av_freep(&s->mb);
1309 #ifdef CINEPAKENC_DEBUG
1310     av_freep(&s->best_mb);
1311 #endif
1312
1313     for(x = 0; x < (avctx->pix_fmt == AV_PIX_FMT_RGB24 ? 4 : 3); x++)
1314         av_freep(&s->pict_bufs[x]);
1315
1316 #ifdef CINEPAKENC_DEBUG
1317     av_log(avctx, AV_LOG_INFO, "strip coding stats: %i V1 mode, %i V4 mode, %i MC mode (%i V1 encs, %i V4 encs, %i skips)\n",
1318         s->num_v1_mode, s->num_v4_mode, s->num_mc_mode, s->num_v1_encs, s->num_v4_encs, s->num_skips);
1319 #endif
1320
1321     return 0;
1322 }
1323
1324 AVCodec ff_cinepak_encoder = {
1325     .name           = "cinepak",
1326     .type           = AVMEDIA_TYPE_VIDEO,
1327     .id             = AV_CODEC_ID_CINEPAK,
1328     .priv_data_size = sizeof(CinepakEncContext),
1329     .init           = cinepak_encode_init,
1330     .encode2        = cinepak_encode_frame,
1331     .close          = cinepak_encode_end,
1332     .pix_fmts       = (const enum AVPixelFormat[]){AV_PIX_FMT_RGB24, AV_PIX_FMT_GRAY8, AV_PIX_FMT_NONE},
1333     .long_name      = NULL_IF_CONFIG_SMALL("Cinepak / CVID"),
1334     .priv_class     = &cinepak_class,
1335 };