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