Add Cinepak encoder
[ffmpeg.git] / libavcodec / cinepakenc.c
1 /*
2  * Cinepak encoder (c) 2011 Tomas Härdin
3  * http://titan.codemill.se/~tomhar/cinepakenc.patch
4
5 Permission is hereby granted, free of charge, to any person obtaining a
6 copy of this software and associated documentation files (the "Software"),
7 to deal in the Software without restriction, including without limitation
8 the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 and/or sell copies of the Software, and to permit persons to whom the
10 Software is furnished to do so, subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be included
13 in all copies or substantial portions of the Software.
14
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
19 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
20 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
21 OTHER DEALINGS IN THE SOFTWARE.
22
23  */
24
25 #include "libavutil/common.h"
26 #include "libavutil/intreadwrite.h"
27 #include "avcodec.h"
28 #include "libavutil/lfg.h"
29 #include "elbg.h"
30
31 #define CVID_HEADER_SIZE 10
32 #define STRIP_HEADER_SIZE 12
33 #define CHUNK_HEADER_SIZE 4
34
35 #define MB_SIZE 4           //4x4 MBs
36 #define MB_AREA (MB_SIZE*MB_SIZE)
37
38 #define VECTOR_MAX 6        //six or four entries per vector depending on format
39 #define CODEBOOK_MAX 256
40 #define CODEBOOK_NUM 5      //five potential codebooks (1, 4, 16, 64, 256) for V1 and V4
41
42 #define MAX_STRIPS  1       //Note: having fewer choices regarding the number of strip speeds up encoding (obviously)
43 #define MIN_STRIPS  1       //Note: having more strips speeds up encoding the frame (this is less obvious)
44
45 typedef enum {
46     MODE_V1_ONLY = 0,
47     MODE_V1_V4,
48     MODE_MC,
49
50     MODE_COUNT,
51 } CinepakMode;
52
53 typedef enum {
54     ENC_V1,
55     ENC_V4,
56     ENC_SKIP
57 } mb_encoding;
58
59 typedef struct {
60     int v1_vector;                  //index into v1 codebook
61     int v1_error;                   //error when using V1 encoding
62     int v4_vector[CODEBOOK_NUM][4]; //indices into v4 codebooks
63     int v4_error[CODEBOOK_NUM];     //error when using V4 encodings
64     int skip_error;                 //error when block is skipped (aka copied from last frame)
65     mb_encoding best_encoding;      //last result from calculate_mode_score()
66 } mb_info;
67
68 typedef struct {
69     int v1_codebook[CODEBOOK_MAX*VECTOR_MAX];
70     int *v4_codebook;
71 } strip_info;
72
73 typedef struct {
74     AVCodecContext *avctx;
75     unsigned char *pict_bufs[3], *strip_buf, *frame_buf;
76     AVFrame last_frame;
77     AVFrame best_frame;
78     AVFrame scratch_frame;
79     enum AVPixelFormat pix_fmt;
80     int w, h;
81     int curframe, keyint;
82     AVLFG randctx;
83     uint64_t lambda;
84     int *codebook_input;
85     int *codebook_closest;
86     mb_info *mb;                                //MB RD state
87 #ifdef CINEPAKENC_DEBUG
88     mb_info *best_mb;                           //TODO: remove. only used for printing stats
89 #endif
90     int num_v1_mode, num_v4_mode, num_mc_mode;
91     int num_v1_encs, num_v4_encs, num_skips;
92 } CinepakEncContext;
93
94 static av_cold int cinepak_encode_init(AVCodecContext *avctx)
95 {
96     CinepakEncContext *s = avctx->priv_data;
97     int x, mb_count, strip_buf_size, frame_buf_size;
98
99     if (avctx->width & 3 || avctx->height & 3) {
100         av_log(avctx, AV_LOG_ERROR, "width and height must be multiples of four (got %ix%i)\n",
101                 avctx->width, avctx->height);
102         return AVERROR(EINVAL);
103     }
104
105     if (!(s->codebook_input = av_malloc(sizeof(int) * (avctx->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4) * (avctx->width * avctx->height) >> 2)))
106         return AVERROR(ENOMEM);
107
108     if (!(s->codebook_closest = av_malloc(sizeof(int) * (avctx->width * avctx->height) >> 2)))
109         goto enomem;
110
111     for(x = 0; x < 3; x++)
112         if(!(s->pict_bufs[x] = av_malloc((avctx->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4) * (avctx->width * avctx->height) >> 2)))
113             goto enomem;
114
115     mb_count = avctx->width * avctx->height / MB_AREA;
116
117     //the largest possible chunk is 0x31 with all MBs encoded in V4 mode, which is 34 bits per MB
118     strip_buf_size = STRIP_HEADER_SIZE + 3 * CHUNK_HEADER_SIZE + 2 * VECTOR_MAX * CODEBOOK_MAX + 4 * (mb_count + (mb_count + 15) / 16);
119
120     frame_buf_size = CVID_HEADER_SIZE + MAX_STRIPS * strip_buf_size;
121
122     if (!(s->strip_buf = av_malloc(strip_buf_size)))
123         goto enomem;
124
125     if (!(s->frame_buf = av_malloc(frame_buf_size)))
126         goto enomem;
127
128     if (!(s->mb = av_malloc(mb_count*sizeof(mb_info))))
129         goto enomem;
130
131 #ifdef CINEPAKENC_DEBUG
132     if (!(s->best_mb = av_malloc(mb_count*sizeof(mb_info))))
133         goto enomem;
134 #endif
135
136     av_lfg_init(&s->randctx, 1);
137     s->avctx = avctx;
138     s->w = avctx->width;
139     s->h = avctx->height;
140     s->curframe = 0;
141     s->keyint = avctx->keyint_min;
142     s->pix_fmt = avctx->pix_fmt;
143
144     //set up AVFrames
145     s->last_frame.data[0]        = s->pict_bufs[0];
146     s->last_frame.linesize[0]    = s->w;
147     s->best_frame.data[0]        = s->pict_bufs[1];
148     s->best_frame.linesize[0]    = s->w;
149     s->scratch_frame.data[0]     = s->pict_bufs[2];
150     s->scratch_frame.linesize[0] = s->w;
151
152     if(s->pix_fmt == AV_PIX_FMT_YUV420P) {
153         s->last_frame.data[1]        = s->last_frame.data[0] + s->w * s->h;
154         s->last_frame.data[2]        = s->last_frame.data[1] + ((s->w * s->h) >> 2);
155         s->last_frame.linesize[1]    = s->last_frame.linesize[2] = s->w >> 1;
156
157         s->best_frame.data[1]        = s->best_frame.data[0] + s->w * s->h;
158         s->best_frame.data[2]        = s->best_frame.data[1] + ((s->w * s->h) >> 2);
159         s->best_frame.linesize[1]    = s->best_frame.linesize[2] = s->w >> 1;
160
161         s->scratch_frame.data[1]     = s->scratch_frame.data[0] + s->w * s->h;
162         s->scratch_frame.data[2]     = s->scratch_frame.data[1] + ((s->w * s->h) >> 2);
163         s->scratch_frame.linesize[1] = s->scratch_frame.linesize[2] = s->w >> 1;
164     }
165
166     s->num_v1_mode = s->num_v4_mode = s->num_mc_mode = s->num_v1_encs = s->num_v4_encs = s->num_skips = 0;
167
168     return 0;
169
170 enomem:
171     av_free(s->codebook_input);
172     av_free(s->codebook_closest);
173     av_free(s->strip_buf);
174     av_free(s->frame_buf);
175     av_free(s->mb);
176 #ifdef CINEPAKENC_DEBUG
177     av_free(s->best_mb);
178 #endif
179
180     for(x = 0; x < 3; x++)
181         av_free(s->pict_bufs[x]);
182
183     return AVERROR(ENOMEM);
184 }
185
186 static int64_t calculate_mode_score(CinepakEncContext *s, CinepakMode mode, int h, int v1_size, int v4_size, int v4, strip_info *info)
187 {
188     //score = FF_LAMBDA_SCALE * error + lambda * bits
189     int x;
190     int entry_size = s->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4;
191     int mb_count = s->w * h / MB_AREA;
192     mb_info *mb;
193     int64_t score1, score2, score3;
194     int64_t ret = s->lambda * ((v1_size ? CHUNK_HEADER_SIZE + v1_size * entry_size : 0) +
195                    (v4_size ? CHUNK_HEADER_SIZE + v4_size * entry_size : 0) +
196                    CHUNK_HEADER_SIZE) << 3;
197
198     //av_log(s->avctx, AV_LOG_INFO, "sizes %3i %3i -> %9li score mb_count %i", v1_size, v4_size, ret, mb_count);
199
200     switch(mode) {
201     case MODE_V1_ONLY:
202         //one byte per MB
203         ret += s->lambda * 8 * mb_count;
204
205         for(x = 0; x < mb_count; x++) {
206             mb = &s->mb[x];
207             ret += FF_LAMBDA_SCALE * mb->v1_error;
208             mb->best_encoding = ENC_V1;
209         }
210
211         break;
212     case MODE_V1_V4:
213         //9 or 33 bits per MB
214         for(x = 0; x < mb_count; x++) {
215             mb = &s->mb[x];
216             score1 = s->lambda * 9  + FF_LAMBDA_SCALE * mb->v1_error;
217             score2 = s->lambda * 33 + FF_LAMBDA_SCALE * mb->v4_error[v4];
218
219             if(score1 <= score2) {
220                 ret += score1;
221                 mb->best_encoding = ENC_V1;
222             } else {
223                 ret += score2;
224                 mb->best_encoding = ENC_V4;
225             }
226         }
227
228         break;
229     case MODE_MC:
230         //1, 10 or 34 bits per MB
231         for(x = 0; x < mb_count; x++) {
232             mb = &s->mb[x];
233             score1 = s->lambda * 1  + FF_LAMBDA_SCALE * mb->skip_error;
234             score2 = s->lambda * 10 + FF_LAMBDA_SCALE * mb->v1_error;
235             score3 = s->lambda * 34 + FF_LAMBDA_SCALE * mb->v4_error[v4];
236
237
238             if(score1 <= score2 && score1 <= score3) {
239                 ret += score1;
240                 mb->best_encoding = ENC_SKIP;
241             } else if(score2 <= score1 && score2 <= score3) {
242                 ret += score2;
243                 mb->best_encoding = ENC_V1;
244             } else {
245                 ret += score3;
246                 mb->best_encoding = ENC_V4;
247             }
248         }
249
250         break;
251     }
252
253     return ret;
254 }
255
256 static int write_chunk_header(unsigned char *buf, int chunk_type, int chunk_size)
257 {
258     buf[0] = chunk_type;
259     AV_WB24(&buf[1], chunk_size + CHUNK_HEADER_SIZE);
260     return CHUNK_HEADER_SIZE;
261 }
262
263 static int encode_codebook(CinepakEncContext *s, int *codebook, int size, int chunk_type_yuv, int chunk_type_gray, unsigned char *buf)
264 {
265     int x, y, ret, entry_size = s->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4;
266
267     ret = write_chunk_header(buf, s->pix_fmt == AV_PIX_FMT_YUV420P ? chunk_type_yuv : chunk_type_gray, entry_size * size);
268
269     for(x = 0; x < size; x++)
270         for(y = 0; y < entry_size; y++)
271             buf[ret++] = codebook[y + x*entry_size] ^ (y >= 4 ? 0x80 : 0);
272
273     return ret;
274 }
275
276 //sets out to the sub picture starting at (x,y) in in
277 static void get_sub_picture(CinepakEncContext *s, int x, int y, AVPicture *in, AVPicture *out)
278 {
279     out->data[0] = in->data[0] + x + y * in->linesize[0];
280     out->linesize[0] = in->linesize[0];
281
282     if(s->pix_fmt == AV_PIX_FMT_YUV420P) {
283         out->data[1] = in->data[1] + (x >> 1) + (y >> 1) * in->linesize[1];
284         out->linesize[1] = in->linesize[1];
285
286         out->data[2] = in->data[2] + (x >> 1) + (y >> 1) * in->linesize[2];
287         out->linesize[2] = in->linesize[2];
288     }
289 }
290
291 //decodes the V1 vector in mb into the 4x4 MB pointed to by sub_pict
292 static void decode_v1_vector(CinepakEncContext *s, AVPicture *sub_pict, mb_info *mb, strip_info *info)
293 {
294     int entry_size = s->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4;
295
296     sub_pict->data[0][0] =
297             sub_pict->data[0][1] =
298             sub_pict->data[0][    sub_pict->linesize[0]] =
299             sub_pict->data[0][1+  sub_pict->linesize[0]] = info->v1_codebook[mb->v1_vector*entry_size];
300
301     sub_pict->data[0][2] =
302             sub_pict->data[0][3] =
303             sub_pict->data[0][2+  sub_pict->linesize[0]] =
304             sub_pict->data[0][3+  sub_pict->linesize[0]] = info->v1_codebook[mb->v1_vector*entry_size+1];
305
306     sub_pict->data[0][2*sub_pict->linesize[0]] =
307             sub_pict->data[0][1+2*sub_pict->linesize[0]] =
308             sub_pict->data[0][  3*sub_pict->linesize[0]] =
309             sub_pict->data[0][1+3*sub_pict->linesize[0]] = info->v1_codebook[mb->v1_vector*entry_size+2];
310
311     sub_pict->data[0][2+2*sub_pict->linesize[0]] =
312             sub_pict->data[0][3+2*sub_pict->linesize[0]] =
313             sub_pict->data[0][2+3*sub_pict->linesize[0]] =
314             sub_pict->data[0][3+3*sub_pict->linesize[0]] = info->v1_codebook[mb->v1_vector*entry_size+3];
315
316     if(s->pix_fmt == AV_PIX_FMT_YUV420P) {
317         sub_pict->data[1][0] =
318             sub_pict->data[1][1] =
319             sub_pict->data[1][    sub_pict->linesize[1]] =
320             sub_pict->data[1][1+  sub_pict->linesize[1]] = info->v1_codebook[mb->v1_vector*entry_size+4];
321
322         sub_pict->data[2][0] =
323             sub_pict->data[2][1] =
324             sub_pict->data[2][    sub_pict->linesize[2]] =
325             sub_pict->data[2][1+  sub_pict->linesize[2]] = info->v1_codebook[mb->v1_vector*entry_size+5];
326     }
327 }
328
329 //decodes the V4 vectors in mb into the 4x4 MB pointed to by sub_pict
330 static void decode_v4_vector(CinepakEncContext *s, AVPicture *sub_pict, int *v4_vector, strip_info *info)
331 {
332     int i, x, y, entry_size = s->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4;
333
334     for(i = y = 0; y < 4; y += 2) {
335         for(x = 0; x < 4; x += 2, i++) {
336             sub_pict->data[0][x   +     y*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size];
337             sub_pict->data[0][x+1 +     y*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size+1];
338             sub_pict->data[0][x   + (y+1)*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size+2];
339             sub_pict->data[0][x+1 + (y+1)*sub_pict->linesize[0]] = info->v4_codebook[v4_vector[i]*entry_size+3];
340
341             if(s->pix_fmt == AV_PIX_FMT_YUV420P) {
342                 sub_pict->data[1][(x>>1) + (y>>1)*sub_pict->linesize[1]] = info->v4_codebook[v4_vector[i]*entry_size+4];
343                 sub_pict->data[2][(x>>1) + (y>>1)*sub_pict->linesize[2]] = info->v4_codebook[v4_vector[i]*entry_size+5];
344             }
345         }
346     }
347 }
348
349 static int encode_mode(CinepakEncContext *s, CinepakMode mode, int h, int v1_size, int v4_size, int v4, AVPicture *scratch_pict, strip_info *info, unsigned char *buf)
350 {
351     int x, y, z, flags, bits, temp_size, header_ofs, ret = 0, mb_count = s->w * h / MB_AREA;
352     int needs_extra_bit, should_write_temp;
353     unsigned char temp[64]; //32/2 = 16 V4 blocks at 4 B each -> 64 B
354     mb_info *mb;
355     AVPicture sub_scratch;
356
357     //encode codebooks
358     if(v1_size)
359         ret += encode_codebook(s, info->v1_codebook, v1_size, 0x22, 0x26, buf + ret);
360
361     if(v4_size)
362         ret += encode_codebook(s, info->v4_codebook, v4_size, 0x20, 0x24, buf + ret);
363
364     //update scratch picture
365     for(z = y = 0; y < h; y += MB_SIZE) {
366         for(x = 0; x < s->w; x += MB_SIZE, z++) {
367             mb = &s->mb[z];
368
369             if(mode == MODE_MC && mb->best_encoding == ENC_SKIP)
370                 continue;
371
372             get_sub_picture(s, x, y, scratch_pict, &sub_scratch);
373
374             if(mode == MODE_V1_ONLY || mb->best_encoding == ENC_V1)
375                 decode_v1_vector(s, &sub_scratch, mb, info);
376             else if(mode != MODE_V1_ONLY && mb->best_encoding == ENC_V4)
377                 decode_v4_vector(s, &sub_scratch, mb->v4_vector[v4], info);
378         }
379     }
380
381     switch(mode) {
382     case MODE_V1_ONLY:
383         //av_log(s->avctx, AV_LOG_INFO, "mb_count = %i\n", mb_count);
384         ret += write_chunk_header(buf + ret, 0x32, mb_count);
385
386         for(x = 0; x < mb_count; x++)
387             buf[ret++] = s->mb[x].v1_vector;
388
389         break;
390     case MODE_V1_V4:
391         //remember header position
392         header_ofs = ret;
393         ret += CHUNK_HEADER_SIZE;
394
395         for(x = 0; x < mb_count; x += 32) {
396             flags = 0;
397             for(y = x; y < FFMIN(x+32, mb_count); y++)
398                 if(s->mb[y].best_encoding == ENC_V4)
399                     flags |= 1 << (31 - y + x);
400
401             AV_WB32(&buf[ret], flags);
402             ret += 4;
403
404             for(y = x; y < FFMIN(x+32, mb_count); y++) {
405                 mb = &s->mb[y];
406
407                 if(mb->best_encoding == ENC_V1)
408                     buf[ret++] = mb->v1_vector;
409                 else
410                     for(z = 0; z < 4; z++)
411                         buf[ret++] = mb->v4_vector[v4][z];
412             }
413         }
414
415         write_chunk_header(buf + header_ofs, 0x30, ret - header_ofs - CHUNK_HEADER_SIZE);
416
417         break;
418     case MODE_MC:
419         //remember header position
420         header_ofs = ret;
421         ret += CHUNK_HEADER_SIZE;
422         flags = bits = temp_size = 0;
423
424         for(x = 0; x < mb_count; x++) {
425             mb = &s->mb[x];
426             flags |= (mb->best_encoding != ENC_SKIP) << (31 - bits++);
427             needs_extra_bit = 0;
428             should_write_temp = 0;
429
430             if(mb->best_encoding != ENC_SKIP) {
431                 if(bits < 32)
432                     flags |= (mb->best_encoding == ENC_V4) << (31 - bits++);
433                 else
434                     needs_extra_bit = 1;
435             }
436
437             if(bits == 32) {
438                 AV_WB32(&buf[ret], flags);
439                 ret += 4;
440                 flags = bits = 0;
441
442                 if(mb->best_encoding == ENC_SKIP || needs_extra_bit) {
443                     memcpy(&buf[ret], temp, temp_size);
444                     ret += temp_size;
445                     temp_size = 0;
446                 } else
447                     should_write_temp = 1;
448             }
449
450             if(needs_extra_bit) {
451                 flags = (mb->best_encoding == ENC_V4) << 31;
452                 bits = 1;
453             }
454
455             if(mb->best_encoding == ENC_V1)
456                 temp[temp_size++] = mb->v1_vector;
457             else if(mb->best_encoding == ENC_V4)
458                 for(z = 0; z < 4; z++)
459                     temp[temp_size++] = mb->v4_vector[v4][z];
460
461             if(should_write_temp) {
462                 memcpy(&buf[ret], temp, temp_size);
463                 ret += temp_size;
464                 temp_size = 0;
465             }
466         }
467
468         if(bits > 0) {
469             AV_WB32(&buf[ret], flags);
470             ret += 4;
471             memcpy(&buf[ret], temp, temp_size);
472             ret += temp_size;
473         }
474
475         write_chunk_header(buf + header_ofs, 0x31, ret - header_ofs - CHUNK_HEADER_SIZE);
476
477         break;
478     }
479
480     return ret;
481 }
482
483 //computes distortion of 4x4 MB in b compared to a
484 static int compute_mb_distortion(CinepakEncContext *s, AVPicture *a, AVPicture *b)
485 {
486     int x, y, p, d, ret = 0;
487
488     for(y = 0; y < MB_SIZE; y++) {
489         for(x = 0; x < MB_SIZE; x++) {
490             d = a->data[0][x + y*a->linesize[0]] - b->data[0][x + y*b->linesize[0]];
491             ret += d*d;
492         }
493     }
494
495     if(s->pix_fmt == AV_PIX_FMT_YUV420P) {
496         for(p = 1; p <= 2; p++) {
497             for(y = 0; y < MB_SIZE/2; y++) {
498                 for(x = 0; x < MB_SIZE/2; x++) {
499                     d = a->data[p][x + y*a->linesize[p]] - b->data[p][x + y*b->linesize[p]];
500                     ret += d*d;
501                 }
502             }
503         }
504     }
505
506     return ret;
507 }
508
509 static int quantize(CinepakEncContext *s, int h, AVPicture *pict, int v1mode, int size, int v4, strip_info *info)
510 {
511     int x, y, i, j, k, x2, y2, x3, y3, plane, shift;
512     int entry_size = s->pix_fmt == AV_PIX_FMT_YUV420P ? 6 : 4;
513     int *codebook = v1mode ? info->v1_codebook : info->v4_codebook;
514     int64_t total_error = 0;
515     uint8_t vq_pict_buf[(MB_AREA*3)/2];
516     AVPicture sub_pict, vq_pict;
517
518     for(i = y = 0; y < h; y += MB_SIZE) {
519         for(x = 0; x < s->w; x += MB_SIZE, i += v1mode ? 1 : 4) {
520             int *base = s->codebook_input + i*entry_size;
521
522             if(v1mode) {
523                 //subsample
524                 for(j = y2 = 0; y2 < entry_size; y2 += 2) {
525                     for(x2 = 0; x2 < 4; x2 += 2, j++) {
526                         plane = y2 < 4 ? 0 : 1 + (x2 >> 1);
527                         shift = y2 < 4 ? 0 : 1;
528                         x3 = shift ? 0 : x2;
529                         y3 = shift ? 0 : y2;
530                         base[j] = (pict->data[plane][((x+x3) >> shift) +      ((y+y3) >> shift)      * pict->linesize[plane]] +
531                                    pict->data[plane][((x+x3) >> shift) + 1 +  ((y+y3) >> shift)      * pict->linesize[plane]] +
532                                    pict->data[plane][((x+x3) >> shift) +     (((y+y3) >> shift) + 1) * pict->linesize[plane]] +
533                                    pict->data[plane][((x+x3) >> shift) + 1 + (((y+y3) >> shift) + 1) * pict->linesize[plane]]) >> 2;
534                     }
535                 }
536             } else {
537                 //copy
538                 for(j = y2 = 0; y2 < MB_SIZE; y2 += 2) {
539                     for(x2 = 0; x2 < MB_SIZE; x2 += 2) {
540                         for(k = 0; k < entry_size; k++, j++) {
541                             plane = k >= 4 ? k - 3 : 0;
542
543                             if(k >= 4) {
544                                 x3 = (x+x2) >> 1;
545                                 y3 = (y+y2) >> 1;
546                             } else {
547                                 x3 = x + x2 + (k & 1);
548                                 y3 = y + y2 + (k >> 1);
549                             }
550
551                             base[j] = pict->data[plane][x3 + y3*pict->linesize[plane]];
552                         }
553                     }
554                 }
555             }
556         }
557     }
558
559     ff_init_elbg(s->codebook_input, entry_size, i, codebook, size, 1, s->codebook_closest, &s->randctx);
560     ff_do_elbg(s->codebook_input, entry_size, i, codebook, size, 1, s->codebook_closest, &s->randctx);
561
562     //setup vq_pict, which contains a single MB
563     vq_pict.data[0] = vq_pict_buf;
564     vq_pict.linesize[0] = MB_SIZE;
565     vq_pict.data[1] = &vq_pict_buf[MB_AREA];
566     vq_pict.data[2] = vq_pict.data[1] + (MB_AREA >> 2);
567     vq_pict.linesize[1] = vq_pict.linesize[2] = MB_SIZE >> 1;
568
569     //copy indices
570     for(i = j = y = 0; y < h; y += MB_SIZE) {
571         for(x = 0; x < s->w; x += MB_SIZE, j++, i += v1mode ? 1 : 4) {
572             mb_info *mb = &s->mb[j];
573
574             //point sub_pict to current MB
575             get_sub_picture(s, x, y, pict, &sub_pict);
576
577             if(v1mode) {
578                 mb->v1_vector = s->codebook_closest[i];
579
580                 //fill in vq_pict with V1 data
581                 decode_v1_vector(s, &vq_pict, mb, info);
582
583                 mb->v1_error = compute_mb_distortion(s, &sub_pict, &vq_pict);
584                 total_error += mb->v1_error;
585             } else {
586                 for(k = 0; k < 4; k++)
587                     mb->v4_vector[v4][k] = s->codebook_closest[i+k];
588
589                 //fill in vq_pict with V4 data
590                 decode_v4_vector(s, &vq_pict, mb->v4_vector[v4], info);
591
592                 mb->v4_error[v4] = compute_mb_distortion(s, &sub_pict, &vq_pict);
593                 total_error += mb->v4_error[v4];
594             }
595         }
596     }
597
598     //av_log(s->avctx, AV_LOG_INFO, "mode %i size %i i %i error %li\n", v1mode, size, i, total_error);
599
600     return 0;
601 }
602
603 static void calculate_skip_errors(CinepakEncContext *s, int h, AVPicture *last_pict, AVPicture *pict, strip_info *info)
604 {
605     int x, y, i;
606     AVPicture sub_last, sub_pict;
607
608     for(i = y = 0; y < h; y += MB_SIZE) {
609         for(x = 0; x < s->w; x += MB_SIZE, i++) {
610             get_sub_picture(s, x, y, last_pict, &sub_last);
611             get_sub_picture(s, x, y, pict,      &sub_pict);
612
613             s->mb[i].skip_error = compute_mb_distortion(s, &sub_last, &sub_pict);
614         }
615     }
616 }
617
618 static void write_strip_header(CinepakEncContext *s, int y, int h, int keyframe, unsigned char *buf, int strip_size)
619 {
620     buf[0] = keyframe ? 0x11: 0x10;
621     AV_WB24(&buf[1], strip_size + STRIP_HEADER_SIZE);
622     AV_WB16(&buf[4], y);
623     AV_WB16(&buf[6], 0);
624     AV_WB16(&buf[8], h);
625     AV_WB16(&buf[10], s->w);
626 }
627
628 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)
629 {
630     int64_t score = 0;
631     int best_size = 0, v1_size, v4_size, v4, mb_count = s->w * h / MB_AREA;
632     strip_info info;
633     CinepakMode best_mode;
634     int v4_codebooks[CODEBOOK_NUM][CODEBOOK_MAX*VECTOR_MAX];
635
636     if(!keyframe)
637         calculate_skip_errors(s, h, last_pict, pict, &info);
638
639     //precompute V4 codebooks
640     for(v4_size = 1, v4 = 0; v4_size <= 256; v4_size <<= 2, v4++) {
641         info.v4_codebook = v4_codebooks[v4];
642         quantize(s, h, pict, 0, v4_size, v4, &info);
643     }
644
645     //try all powers of 4 for the size of the codebooks
646     //constraint the v4 codebook to be no bigger than the v1 codebook
647     for(v1_size = 1; v1_size <= 256; v1_size <<= 2) {
648         //compute V1 codebook
649         quantize(s, h, pict, 1, v1_size, -1, &info);
650
651         for(v4_size = 0, v4 = -1; v4_size <= v1_size; v4_size = v4_size ? v4_size << 2 : v1_size >= 4 ? v1_size >> 2 : 1, v4++) {
652             //try all modes
653             for(CinepakMode mode = 0; mode < MODE_COUNT; mode++) {
654                 //don't allow MODE_MC in inter frames
655                 if(keyframe && mode == MODE_MC)
656                     continue;
657
658                 //only allow V1-only mode if v4 codebook is empty
659                 if(!v4_size && mode != MODE_V1_ONLY)
660                     continue;
661
662                 info.v4_codebook = v4 >= 0 ? v4_codebooks[v4] : NULL;
663                 score = calculate_mode_score(s, mode, h, v1_size, v4_size, v4, &info);
664
665                 //av_log(s->avctx, AV_LOG_INFO, "%3i %3i score = %li\n", v1_size, v4_size, score);
666
667                 if(best_size == 0 || score < *best_score) {
668                     *best_score = score;
669                     best_size = encode_mode(s, mode, h, v1_size, v4_size, v4, scratch_pict, &info, s->strip_buf + STRIP_HEADER_SIZE);
670                     best_mode = mode;
671
672                     av_log(s->avctx, AV_LOG_INFO, "mode %i, %3i, %3i: %18li %i B\n", mode, v1_size, v4_size, score, best_size);
673
674 #ifdef CINEPAKENC_DEBUG
675                     //save MB encoding choices
676                     memcpy(s->best_mb, s->mb, mb_count*sizeof(mb_info));
677 #endif
678
679                     //memcpy(strip_temp + STRIP_HEADER_SIZE, strip_temp, best_size);
680                     write_strip_header(s, y, h, keyframe, s->strip_buf, best_size);
681                 }
682             }
683         }
684     }
685
686 #ifdef CINEPAKENC_DEBUG
687     //gather stats. this will only work properly of MAX_STRIPS == 1
688     if(best_mode == MODE_V1_ONLY) {
689         s->num_v1_mode++;
690         s->num_v1_encs += s->w*h/MB_AREA;
691     } else {
692         if(best_mode == MODE_V1_V4)
693             s->num_v4_mode++;
694         else
695             s->num_mc_mode++;
696
697         int x;
698         for(x = 0; x < s->w*h/MB_AREA; x++)
699             if(s->best_mb[x].best_encoding == ENC_V1)
700                 s->num_v1_encs++;
701             else if(s->best_mb[x].best_encoding == ENC_V4)
702                 s->num_v4_encs++;
703             else
704                 s->num_skips++;
705     }
706 #endif
707
708     best_size += STRIP_HEADER_SIZE;
709     memcpy(buf, s->strip_buf, best_size);
710
711
712     return best_size;
713 }
714
715 static int write_cvid_header(CinepakEncContext *s, unsigned char *buf, int num_strips, int data_size)
716 {
717     buf[0] = 0;
718     AV_WB24(&buf[1], data_size + CVID_HEADER_SIZE);
719     AV_WB16(&buf[4], s->w);
720     AV_WB16(&buf[6], s->h);
721     AV_WB16(&buf[8], num_strips);
722
723     return CVID_HEADER_SIZE;
724 }
725
726 static int rd_frame(CinepakEncContext *s, AVFrame *frame, unsigned char *buf, int buf_size)
727 {
728     int num_strips, strip, h, i, y, size, temp_size, best_size;
729     AVPicture last_pict, pict, scratch_pict;
730     int64_t best_score = 0, score, score_temp;
731
732     //TODO: support encoding zero strips (meaning skip the whole frame)
733     for(num_strips = MIN_STRIPS; num_strips <= MAX_STRIPS && num_strips <= s->h / MB_SIZE; num_strips++) {
734         score = 0;
735         size = 0;
736         h = s->h / num_strips;
737         //make h into next multiple of 4
738         h += 4 - (h & 3);
739
740         for(strip = 0; strip < num_strips; strip++) {
741             y = strip*h;
742
743             get_sub_picture(s, 0, y, (AVPicture*)frame,            &pict);
744             get_sub_picture(s, 0, y, (AVPicture*)&s->last_frame,    &last_pict);
745             get_sub_picture(s, 0, y, (AVPicture*)&s->scratch_frame, &scratch_pict);
746
747             if((temp_size = rd_strip(s, y, FFMIN(h, s->h - y), frame->key_frame, &last_pict, &pict, &scratch_pict, s->frame_buf + CVID_HEADER_SIZE, &score_temp)) < 0)
748                 return temp_size;
749
750             score += score_temp;
751             size += temp_size;
752         }
753
754         if(best_score == 0 || score < best_score) {
755             best_score = score;
756             best_size = size + write_cvid_header(s, s->frame_buf, num_strips, size);
757             av_log(s->avctx, AV_LOG_INFO, "best number of strips so far: %2i, %12li, %i B\n", num_strips, score, best_size);
758
759             FFSWAP(AVFrame, s->best_frame, s->scratch_frame);
760         }
761     }
762
763     memcpy(buf, s->frame_buf, best_size);
764
765     return best_size;
766 }
767
768 static int cinepak_encode_frame(AVCodecContext *avctx, unsigned char *buf, int buf_size, void *data)
769 {
770     CinepakEncContext *s = avctx->priv_data;
771     AVFrame *frame = data;
772     int ret;
773
774     s->lambda = frame->quality ? frame->quality - 1 : 2 * FF_LAMBDA_SCALE;
775
776     frame->key_frame = s->curframe == 0;
777     frame->pict_type = frame->key_frame ? AV_PICTURE_TYPE_I : AV_PICTURE_TYPE_P;
778
779     ret = rd_frame(s, frame, buf, buf_size);
780
781     FFSWAP(AVFrame, s->last_frame, s->best_frame);
782
783     if (++s->curframe >= s->keyint)
784         s->curframe = 0;
785
786     return ret;
787 }
788
789 static av_cold int cinepak_encode_end(AVCodecContext *avctx)
790 {
791     CinepakEncContext *s = avctx->priv_data;
792     int x;
793
794     av_free(s->codebook_input);
795     av_free(s->codebook_closest);
796     av_free(s->strip_buf);
797     av_free(s->frame_buf);
798     av_free(s->mb);
799 #ifdef CINEPAKENC_DEBUG
800     av_free(s->best_mb);
801 #endif
802
803     for(x = 0; x < 3; x++)
804         av_free(s->pict_bufs[x]);
805
806     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",
807         s->num_v1_mode, s->num_v4_mode, s->num_mc_mode, s->num_v1_encs, s->num_v4_encs, s->num_skips);
808
809     return 0;
810 }
811
812 AVCodec ff_cinepak_encoder = {
813     .name           = "cinepak",
814     .type           = AVMEDIA_TYPE_VIDEO,
815     .id             = AV_CODEC_ID_CINEPAK,
816     .priv_data_size = sizeof(CinepakEncContext),
817     .init           = cinepak_encode_init,
818     .encode2        = cinepak_encode_frame,
819     .close          = cinepak_encode_end,
820     .pix_fmts       = (const enum AVPixelFormat[]){AV_PIX_FMT_RGB24, AV_PIX_FMT_GRAY8, AV_PIX_FMT_NONE},
821     .long_name      = NULL_IF_CONFIG_SMALL("Cinepak"),
822 };