git.sesse.net Git - ffmpeg/blob - libavcodec/flacenc.c

   1 /*
   2  * FLAC audio encoder
   3  * Copyright (c) 2006  Justin Ruggles <justin.ruggles@gmail.com>
   4  *
   5  * This file is part of FFmpeg.
   6  *
   7  * FFmpeg is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * FFmpeg is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with FFmpeg; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #include "libavutil/avassert.h"
  23 #include "libavutil/crc.h"
  24 #include "libavutil/intmath.h"
  25 #include "libavutil/md5.h"
  26 #include "libavutil/opt.h"
  27
  28 #include "avcodec.h"
  29 #include "bswapdsp.h"
  30 #include "put_bits.h"
  31 #include "golomb.h"
  32 #include "internal.h"
  33 #include "lpc.h"
  34 #include "flac.h"
  35 #include "flacdata.h"
  36 #include "flacdsp.h"
  37
  38 #define FLAC_SUBFRAME_CONSTANT  0
  39 #define FLAC_SUBFRAME_VERBATIM  1
  40 #define FLAC_SUBFRAME_FIXED     8
  41 #define FLAC_SUBFRAME_LPC      32
  42
  43 #define MAX_FIXED_ORDER     4
  44 #define MAX_PARTITION_ORDER 8
  45 #define MAX_PARTITIONS     (1 << MAX_PARTITION_ORDER)
  46 #define MAX_LPC_PRECISION  15
  47 #define MIN_LPC_SHIFT       0
  48 #define MAX_LPC_SHIFT      15
  49
  50 enum CodingMode {
  51     CODING_MODE_RICE  = 4,
  52     CODING_MODE_RICE2 = 5,
  53 };
  54
  55 typedef struct CompressionOptions {
  56     int compression_level;
  57     int block_time_ms;
  58     enum FFLPCType lpc_type;
  59     int lpc_passes;
  60     int lpc_coeff_precision;
  61     int min_prediction_order;
  62     int max_prediction_order;
  63     int prediction_order_method;
  64     int min_partition_order;
  65     int max_partition_order;
  66     int ch_mode;
  67     int exact_rice_parameters;
  68     int multi_dim_quant;
  69 } CompressionOptions;
  70
  71 typedef struct RiceContext {
  72     enum CodingMode coding_mode;
  73     int porder;
  74     int params[MAX_PARTITIONS];
  75 } RiceContext;
  76
  77 typedef struct FlacSubframe {
  78     int type;
  79     int type_code;
  80     int obits;
  81     int wasted;
  82     int order;
  83     int32_t coefs[MAX_LPC_ORDER];
  84     int shift;
  85
  86     RiceContext rc;
  87     uint32_t rc_udata[FLAC_MAX_BLOCKSIZE];
  88     uint64_t rc_sums[32][MAX_PARTITIONS];
  89
  90     int32_t samples[FLAC_MAX_BLOCKSIZE];
  91     int32_t residual[FLAC_MAX_BLOCKSIZE+11];
  92 } FlacSubframe;
  93
  94 typedef struct FlacFrame {
  95     FlacSubframe subframes[FLAC_MAX_CHANNELS];
  96     int blocksize;
  97     int bs_code[2];
  98     uint8_t crc8;
  99     int ch_mode;
 100     int verbatim_only;
 101 } FlacFrame;
 102
 103 typedef struct FlacEncodeContext {
 104     AVClass *class;
 105     PutBitContext pb;
 106     int channels;
 107     int samplerate;
 108     int sr_code[2];
 109     int bps_code;
 110     int max_blocksize;
 111     int min_framesize;
 112     int max_framesize;
 113     int max_encoded_framesize;
 114     uint32_t frame_count;
 115     uint64_t sample_count;
 116     uint8_t md5sum[16];
 117     FlacFrame frame;
 118     CompressionOptions options;
 119     AVCodecContext *avctx;
 120     LPCContext lpc_ctx;
 121     struct AVMD5 *md5ctx;
 122     uint8_t *md5_buffer;
 123     unsigned int md5_buffer_size;
 124     BswapDSPContext bdsp;
 125     FLACDSPContext flac_dsp;
 126
 127     int flushed;
 128     int64_t next_pts;
 129 } FlacEncodeContext;
 130
 131
 132 /**
 133  * Write streaminfo metadata block to byte array.
 134  */
 135 static void write_streaminfo(FlacEncodeContext *s, uint8_t *header)
 136 {
 137     PutBitContext pb;
 138
 139     memset(header, 0, FLAC_STREAMINFO_SIZE);
 140     init_put_bits(&pb, header, FLAC_STREAMINFO_SIZE);
 141
 142     /* streaminfo metadata block */
 143     put_bits(&pb, 16, s->max_blocksize);
 144     put_bits(&pb, 16, s->max_blocksize);
 145     put_bits(&pb, 24, s->min_framesize);
 146     put_bits(&pb, 24, s->max_framesize);
 147     put_bits(&pb, 20, s->samplerate);
 148     put_bits(&pb, 3, s->channels-1);
 149     put_bits(&pb,  5, s->avctx->bits_per_raw_sample - 1);
 150     /* write 36-bit sample count in 2 put_bits() calls */
 151     put_bits(&pb, 24, (s->sample_count & 0xFFFFFF000LL) >> 12);
 152     put_bits(&pb, 12,  s->sample_count & 0x000000FFFLL);
 153     flush_put_bits(&pb);
 154     memcpy(&header[18], s->md5sum, 16);
 155 }
 156
 157
 158 /**
 159  * Set blocksize based on samplerate.
 160  * Choose the closest predefined blocksize >= BLOCK_TIME_MS milliseconds.
 161  */
 162 static int select_blocksize(int samplerate, int block_time_ms)
 163 {
 164     int i;
 165     int target;
 166     int blocksize;
 167
 168     av_assert0(samplerate > 0);
 169     blocksize = ff_flac_blocksize_table[1];
 170     target    = (samplerate * block_time_ms) / 1000;
 171     for (i = 0; i < 16; i++) {
 172         if (target >= ff_flac_blocksize_table[i] &&
 173             ff_flac_blocksize_table[i] > blocksize) {
 174             blocksize = ff_flac_blocksize_table[i];
 175         }
 176     }
 177     return blocksize;
 178 }
 179
 180
 181 static av_cold void dprint_compression_options(FlacEncodeContext *s)
 182 {
 183     AVCodecContext     *avctx = s->avctx;
 184     CompressionOptions *opt   = &s->options;
 185
 186     av_log(avctx, AV_LOG_DEBUG, " compression: %d\n", opt->compression_level);
 187
 188     switch (opt->lpc_type) {
 189     case FF_LPC_TYPE_NONE:
 190         av_log(avctx, AV_LOG_DEBUG, " lpc type: None\n");
 191         break;
 192     case FF_LPC_TYPE_FIXED:
 193         av_log(avctx, AV_LOG_DEBUG, " lpc type: Fixed pre-defined coefficients\n");
 194         break;
 195     case FF_LPC_TYPE_LEVINSON:
 196         av_log(avctx, AV_LOG_DEBUG, " lpc type: Levinson-Durbin recursion with Welch window\n");
 197         break;
 198     case FF_LPC_TYPE_CHOLESKY:
 199         av_log(avctx, AV_LOG_DEBUG, " lpc type: Cholesky factorization, %d pass%s\n",
 200                opt->lpc_passes, opt->lpc_passes == 1 ? "" : "es");
 201         break;
 202     }
 203
 204     av_log(avctx, AV_LOG_DEBUG, " prediction order: %d, %d\n",
 205            opt->min_prediction_order, opt->max_prediction_order);
 206
 207     switch (opt->prediction_order_method) {
 208     case ORDER_METHOD_EST:
 209         av_log(avctx, AV_LOG_DEBUG, " order method: %s\n", "estimate");
 210         break;
 211     case ORDER_METHOD_2LEVEL:
 212         av_log(avctx, AV_LOG_DEBUG, " order method: %s\n", "2-level");
 213         break;
 214     case ORDER_METHOD_4LEVEL:
 215         av_log(avctx, AV_LOG_DEBUG, " order method: %s\n", "4-level");
 216         break;
 217     case ORDER_METHOD_8LEVEL:
 218         av_log(avctx, AV_LOG_DEBUG, " order method: %s\n", "8-level");
 219         break;
 220     case ORDER_METHOD_SEARCH:
 221         av_log(avctx, AV_LOG_DEBUG, " order method: %s\n", "full search");
 222         break;
 223     case ORDER_METHOD_LOG:
 224         av_log(avctx, AV_LOG_DEBUG, " order method: %s\n", "log search");
 225         break;
 226     }
 227
 228
 229     av_log(avctx, AV_LOG_DEBUG, " partition order: %d, %d\n",
 230            opt->min_partition_order, opt->max_partition_order);
 231
 232     av_log(avctx, AV_LOG_DEBUG, " block size: %d\n", avctx->frame_size);
 233
 234     av_log(avctx, AV_LOG_DEBUG, " lpc precision: %d\n",
 235            opt->lpc_coeff_precision);
 236 }
 237
 238
 239 static av_cold int flac_encode_init(AVCodecContext *avctx)
 240 {
 241     int freq = avctx->sample_rate;
 242     int channels = avctx->channels;
 243     FlacEncodeContext *s = avctx->priv_data;
 244     int i, level, ret;
 245     uint8_t *streaminfo;
 246
 247     s->avctx = avctx;
 248
 249     switch (avctx->sample_fmt) {
 250     case AV_SAMPLE_FMT_S16:
 251         avctx->bits_per_raw_sample = 16;
 252         s->bps_code                = 4;
 253         break;
 254     case AV_SAMPLE_FMT_S32:
 255         if (avctx->bits_per_raw_sample != 24)
 256             av_log(avctx, AV_LOG_WARNING, "encoding as 24 bits-per-sample\n");
 257         avctx->bits_per_raw_sample = 24;
 258         s->bps_code                = 6;
 259         break;
 260     }
 261
 262     if (channels < 1 || channels > FLAC_MAX_CHANNELS) {
 263         av_log(avctx, AV_LOG_ERROR, "%d channels not supported (max %d)\n",
 264                channels, FLAC_MAX_CHANNELS);
 265         return AVERROR(EINVAL);
 266     }
 267     s->channels = channels;
 268
 269     /* find samplerate in table */
 270     if (freq < 1)
 271         return AVERROR(EINVAL);
 272     for (i = 4; i < 12; i++) {
 273         if (freq == ff_flac_sample_rate_table[i]) {
 274             s->samplerate = ff_flac_sample_rate_table[i];
 275             s->sr_code[0] = i;
 276             s->sr_code[1] = 0;
 277             break;
 278         }
 279     }
 280     /* if not in table, samplerate is non-standard */
 281     if (i == 12) {
 282         if (freq % 1000 == 0 && freq < 255000) {
 283             s->sr_code[0] = 12;
 284             s->sr_code[1] = freq / 1000;
 285         } else if (freq % 10 == 0 && freq < 655350) {
 286             s->sr_code[0] = 14;
 287             s->sr_code[1] = freq / 10;
 288         } else if (freq < 65535) {
 289             s->sr_code[0] = 13;
 290             s->sr_code[1] = freq;
 291         } else {
 292             av_log(avctx, AV_LOG_ERROR, "%d Hz not supported\n", freq);
 293             return AVERROR(EINVAL);
 294         }
 295         s->samplerate = freq;
 296     }
 297
 298     /* set compression option defaults based on avctx->compression_level */
 299     if (avctx->compression_level < 0)
 300         s->options.compression_level = 5;
 301     else
 302         s->options.compression_level = avctx->compression_level;
 303
 304     level = s->options.compression_level;
 305     if (level > 12) {
 306         av_log(avctx, AV_LOG_ERROR, "invalid compression level: %d\n",
 307                s->options.compression_level);
 308         return AVERROR(EINVAL);
 309     }
 310
 311     s->options.block_time_ms = ((int[]){ 27, 27, 27,105,105,105,105,105,105,105,105,105,105})[level];
 312
 313     if (s->options.lpc_type == FF_LPC_TYPE_DEFAULT)
 314         s->options.lpc_type  = ((int[]){ FF_LPC_TYPE_FIXED,    FF_LPC_TYPE_FIXED,    FF_LPC_TYPE_FIXED,
 315                                          FF_LPC_TYPE_LEVINSON, FF_LPC_TYPE_LEVINSON, FF_LPC_TYPE_LEVINSON,
 316                                          FF_LPC_TYPE_LEVINSON, FF_LPC_TYPE_LEVINSON, FF_LPC_TYPE_LEVINSON,
 317                                          FF_LPC_TYPE_LEVINSON, FF_LPC_TYPE_LEVINSON, FF_LPC_TYPE_LEVINSON,
 318                                          FF_LPC_TYPE_LEVINSON})[level];
 319
 320     if (s->options.min_prediction_order < 0)
 321         s->options.min_prediction_order = ((int[]){  2,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1})[level];
 322     if (s->options.max_prediction_order < 0)
 323         s->options.max_prediction_order = ((int[]){  3,  4,  4,  6,  8,  8,  8,  8, 12, 12, 12, 32, 32})[level];
 324
 325     if (s->options.prediction_order_method < 0)
 326         s->options.prediction_order_method = ((int[]){ ORDER_METHOD_EST,    ORDER_METHOD_EST,    ORDER_METHOD_EST,
 327                                                        ORDER_METHOD_EST,    ORDER_METHOD_EST,    ORDER_METHOD_EST,
 328                                                        ORDER_METHOD_4LEVEL, ORDER_METHOD_LOG,    ORDER_METHOD_4LEVEL,
 329                                                        ORDER_METHOD_LOG,    ORDER_METHOD_SEARCH, ORDER_METHOD_LOG,
 330                                                        ORDER_METHOD_SEARCH})[level];
 331
 332     if (s->options.min_partition_order > s->options.max_partition_order) {
 333         av_log(avctx, AV_LOG_ERROR, "invalid partition orders: min=%d max=%d\n",
 334                s->options.min_partition_order, s->options.max_partition_order);
 335         return AVERROR(EINVAL);
 336     }
 337     if (s->options.min_partition_order < 0)
 338         s->options.min_partition_order = ((int[]){  2,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0})[level];
 339     if (s->options.max_partition_order < 0)
 340         s->options.max_partition_order = ((int[]){  2,  2,  3,  3,  3,  8,  8,  8,  8,  8,  8,  8,  8})[level];
 341
 342     if (s->options.lpc_type == FF_LPC_TYPE_NONE) {
 343         s->options.min_prediction_order = 0;
 344         s->options.max_prediction_order = 0;
 345     } else if (s->options.lpc_type == FF_LPC_TYPE_FIXED) {
 346         if (s->options.min_prediction_order > MAX_FIXED_ORDER) {
 347             av_log(avctx, AV_LOG_WARNING,
 348                    "invalid min prediction order %d, clamped to %d\n",
 349                    s->options.min_prediction_order, MAX_FIXED_ORDER);
 350             s->options.min_prediction_order = MAX_FIXED_ORDER;
 351         }
 352         if (s->options.max_prediction_order > MAX_FIXED_ORDER) {
 353             av_log(avctx, AV_LOG_WARNING,
 354                    "invalid max prediction order %d, clamped to %d\n",
 355                    s->options.max_prediction_order, MAX_FIXED_ORDER);
 356             s->options.max_prediction_order = MAX_FIXED_ORDER;
 357         }
 358     }
 359
 360     if (s->options.max_prediction_order < s->options.min_prediction_order) {
 361         av_log(avctx, AV_LOG_ERROR, "invalid prediction orders: min=%d max=%d\n",
 362                s->options.min_prediction_order, s->options.max_prediction_order);
 363         return AVERROR(EINVAL);
 364     }
 365
 366     if (avctx->frame_size > 0) {
 367         if (avctx->frame_size < FLAC_MIN_BLOCKSIZE ||
 368                 avctx->frame_size > FLAC_MAX_BLOCKSIZE) {
 369             av_log(avctx, AV_LOG_ERROR, "invalid block size: %d\n",
 370                    avctx->frame_size);
 371             return AVERROR(EINVAL);
 372         }
 373     } else {
 374         s->avctx->frame_size = select_blocksize(s->samplerate, s->options.block_time_ms);
 375     }
 376     s->max_blocksize = s->avctx->frame_size;
 377
 378     /* set maximum encoded frame size in verbatim mode */
 379     s->max_framesize = ff_flac_get_max_frame_size(s->avctx->frame_size,
 380                                                   s->channels,
 381                                                   s->avctx->bits_per_raw_sample);
 382
 383     /* initialize MD5 context */
 384     s->md5ctx = av_md5_alloc();
 385     if (!s->md5ctx)
 386         return AVERROR(ENOMEM);
 387     av_md5_init(s->md5ctx);
 388
 389     streaminfo = av_malloc(FLAC_STREAMINFO_SIZE);
 390     if (!streaminfo)
 391         return AVERROR(ENOMEM);
 392     write_streaminfo(s, streaminfo);
 393     avctx->extradata = streaminfo;
 394     avctx->extradata_size = FLAC_STREAMINFO_SIZE;
 395
 396     s->frame_count   = 0;
 397     s->min_framesize = s->max_framesize;
 398
 399     if (channels == 3 &&
 400             avctx->channel_layout != (AV_CH_LAYOUT_STEREO|AV_CH_FRONT_CENTER) ||
 401         channels == 4 &&
 402             avctx->channel_layout != AV_CH_LAYOUT_2_2 &&
 403             avctx->channel_layout != AV_CH_LAYOUT_QUAD ||
 404         channels == 5 &&
 405             avctx->channel_layout != AV_CH_LAYOUT_5POINT0 &&
 406             avctx->channel_layout != AV_CH_LAYOUT_5POINT0_BACK ||
 407         channels == 6 &&
 408             avctx->channel_layout != AV_CH_LAYOUT_5POINT1 &&
 409             avctx->channel_layout != AV_CH_LAYOUT_5POINT1_BACK) {
 410         if (avctx->channel_layout) {
 411             av_log(avctx, AV_LOG_ERROR, "Channel layout not supported by Flac, "
 412                                              "output stream will have incorrect "
 413                                              "channel layout.\n");
 414         } else {
 415             av_log(avctx, AV_LOG_WARNING, "No channel layout specified. The encoder "
 416                                                "will use Flac channel layout for "
 417                                                "%d channels.\n", channels);
 418         }
 419     }
 420
 421     ret = ff_lpc_init(&s->lpc_ctx, avctx->frame_size,
 422                       s->options.max_prediction_order, FF_LPC_TYPE_LEVINSON);
 423
 424     ff_bswapdsp_init(&s->bdsp);
 425     ff_flacdsp_init(&s->flac_dsp, avctx->sample_fmt, channels,
 426                     avctx->bits_per_raw_sample);
 427
 428     dprint_compression_options(s);
 429
 430     return ret;
 431 }
 432
 433
 434 static void init_frame(FlacEncodeContext *s, int nb_samples)
 435 {
 436     int i, ch;
 437     FlacFrame *frame;
 438
 439     frame = &s->frame;
 440
 441     for (i = 0; i < 16; i++) {
 442         if (nb_samples == ff_flac_blocksize_table[i]) {
 443             frame->blocksize  = ff_flac_blocksize_table[i];
 444             frame->bs_code[0] = i;
 445             frame->bs_code[1] = 0;
 446             break;
 447         }
 448     }
 449     if (i == 16) {
 450         frame->blocksize = nb_samples;
 451         if (frame->blocksize <= 256) {
 452             frame->bs_code[0] = 6;
 453             frame->bs_code[1] = frame->blocksize-1;
 454         } else {
 455             frame->bs_code[0] = 7;
 456             frame->bs_code[1] = frame->blocksize-1;
 457         }
 458     }
 459
 460     for (ch = 0; ch < s->channels; ch++) {
 461         FlacSubframe *sub = &frame->subframes[ch];
 462
 463         sub->wasted = 0;
 464         sub->obits  = s->avctx->bits_per_raw_sample;
 465
 466         if (sub->obits > 16)
 467             sub->rc.coding_mode = CODING_MODE_RICE2;
 468         else
 469             sub->rc.coding_mode = CODING_MODE_RICE;
 470     }
 471
 472     frame->verbatim_only = 0;
 473 }
 474
 475
 476 /**
 477  * Copy channel-interleaved input samples into separate subframes.
 478  */
 479 static void copy_samples(FlacEncodeContext *s, const void *samples)
 480 {
 481     int i, j, ch;
 482     FlacFrame *frame;
 483     int shift = av_get_bytes_per_sample(s->avctx->sample_fmt) * 8 -
 484                 s->avctx->bits_per_raw_sample;
 485
 486 #define COPY_SAMPLES(bits) do {                                     \
 487     const int ## bits ## _t *samples0 = samples;                    \
 488     frame = &s->frame;                                              \
 489     for (i = 0, j = 0; i < frame->blocksize; i++)                   \
 490         for (ch = 0; ch < s->channels; ch++, j++)                   \
 491             frame->subframes[ch].samples[i] = samples0[j] >> shift; \
 492 } while (0)
 493
 494     if (s->avctx->sample_fmt == AV_SAMPLE_FMT_S16)
 495         COPY_SAMPLES(16);
 496     else
 497         COPY_SAMPLES(32);
 498 }
 499
 500
 501 static uint64_t rice_count_exact(const int32_t *res, int n, int k)
 502 {
 503     int i;
 504     uint64_t count = 0;
 505
 506     for (i = 0; i < n; i++) {
 507         int32_t v = -2 * res[i] - 1;
 508         v ^= v >> 31;
 509         count += (v >> k) + 1 + k;
 510     }
 511     return count;
 512 }
 513
 514
 515 static uint64_t subframe_count_exact(FlacEncodeContext *s, FlacSubframe *sub,
 516                                      int pred_order)
 517 {
 518     int p, porder, psize;
 519     int i, part_end;
 520     uint64_t count = 0;
 521
 522     /* subframe header */
 523     count += 8;
 524
 525     if (sub->wasted)
 526         count += sub->wasted;
 527
 528     /* subframe */
 529     if (sub->type == FLAC_SUBFRAME_CONSTANT) {
 530         count += sub->obits;
 531     } else if (sub->type == FLAC_SUBFRAME_VERBATIM) {
 532         count += s->frame.blocksize * sub->obits;
 533     } else {
 534         /* warm-up samples */
 535         count += pred_order * sub->obits;
 536
 537         /* LPC coefficients */
 538         if (sub->type == FLAC_SUBFRAME_LPC)
 539             count += 4 + 5 + pred_order * s->options.lpc_coeff_precision;
 540
 541         /* rice-encoded block */
 542         count += 2;
 543
 544         /* partition order */
 545         porder = sub->rc.porder;
 546         psize  = s->frame.blocksize >> porder;
 547         count += 4;
 548
 549         /* residual */
 550         i        = pred_order;
 551         part_end = psize;
 552         for (p = 0; p < 1 << porder; p++) {
 553             int k = sub->rc.params[p];
 554             count += sub->rc.coding_mode;
 555             count += rice_count_exact(&sub->residual[i], part_end - i, k);
 556             i = part_end;
 557             part_end = FFMIN(s->frame.blocksize, part_end + psize);
 558         }
 559     }
 560
 561     return count;
 562 }
 563
 564
 565 #define rice_encode_count(sum, n, k) (((n)*((k)+1))+((sum-(n>>1))>>(k)))
 566
 567 /**
 568  * Solve for d/dk(rice_encode_count) = n-((sum-(n>>1))>>(k+1)) = 0.
 569  */
 570 static int find_optimal_param(uint64_t sum, int n, int max_param)
 571 {
 572     int k;
 573     uint64_t sum2;
 574
 575     if (sum <= n >> 1)
 576         return 0;
 577     sum2 = sum - (n >> 1);
 578     k    = av_log2(av_clipl_int32(sum2 / n));
 579     return FFMIN(k, max_param);
 580 }
 581
 582 static int find_optimal_param_exact(uint64_t sums[32][MAX_PARTITIONS], int i, int max_param)
 583 {
 584     int bestk = 0;
 585     int64_t bestbits = INT64_MAX;
 586     int k;
 587
 588     for (k = 0; k <= max_param; k++) {
 589         int64_t bits = sums[k][i];
 590         if (bits < bestbits) {
 591             bestbits = bits;
 592             bestk = k;
 593         }
 594     }
 595
 596     return bestk;
 597 }
 598
 599 static uint64_t calc_optimal_rice_params(RiceContext *rc, int porder,
 600                                          uint64_t sums[32][MAX_PARTITIONS],
 601                                          int n, int pred_order, int max_param, int exact)
 602 {
 603     int i;
 604     int k, cnt, part;
 605     uint64_t all_bits;
 606
 607     part     = (1 << porder);
 608     all_bits = 4 * part;
 609
 610     cnt = (n >> porder) - pred_order;
 611     for (i = 0; i < part; i++) {
 612         if (exact) {
 613             k = find_optimal_param_exact(sums, i, max_param);
 614             all_bits += sums[k][i];
 615         } else {
 616             k = find_optimal_param(sums[0][i], cnt, max_param);
 617             all_bits += rice_encode_count(sums[0][i], cnt, k);
 618         }
 619         rc->params[i] = k;
 620         cnt = n >> porder;
 621     }
 622
 623     rc->porder = porder;
 624
 625     return all_bits;
 626 }
 627
 628
 629 static void calc_sum_top(int pmax, int kmax, const uint32_t *data, int n, int pred_order,
 630                          uint64_t sums[32][MAX_PARTITIONS])
 631 {
 632     int i, k;
 633     int parts;
 634     const uint32_t *res, *res_end;
 635
 636     /* sums for highest level */
 637     parts   = (1 << pmax);
 638
 639     for (k = 0; k <= kmax; k++) {
 640         res     = &data[pred_order];
 641         res_end = &data[n >> pmax];
 642         for (i = 0; i < parts; i++) {
 643             if (kmax) {
 644                 uint64_t sum = (1LL + k) * (res_end - res);
 645                 while (res < res_end)
 646                     sum += *(res++) >> k;
 647                 sums[k][i] = sum;
 648             } else {
 649                 uint64_t sum = 0;
 650                 while (res < res_end)
 651                     sum += *(res++);
 652                 sums[k][i] = sum;
 653             }
 654             res_end += n >> pmax;
 655         }
 656     }
 657 }
 658
 659 static void calc_sum_next(int level, uint64_t sums[32][MAX_PARTITIONS], int kmax)
 660 {
 661     int i, k;
 662     int parts = (1 << level);
 663     for (i = 0; i < parts; i++) {
 664         for (k=0; k<=kmax; k++)
 665             sums[k][i] = sums[k][2*i] + sums[k][2*i+1];
 666     }
 667 }
 668
 669 static uint64_t calc_rice_params(RiceContext *rc,
 670                                  uint32_t udata[FLAC_MAX_BLOCKSIZE],
 671                                  uint64_t sums[32][MAX_PARTITIONS],
 672                                  int pmin, int pmax,
 673                                  const int32_t *data, int n, int pred_order, int exact)
 674 {
 675     int i;
 676     uint64_t bits[MAX_PARTITION_ORDER+1];
 677     int opt_porder;
 678     RiceContext tmp_rc;
 679     int kmax = (1 << rc->coding_mode) - 2;
 680
 681     av_assert1(pmin >= 0 && pmin <= MAX_PARTITION_ORDER);
 682     av_assert1(pmax >= 0 && pmax <= MAX_PARTITION_ORDER);
 683     av_assert1(pmin <= pmax);
 684
 685     tmp_rc.coding_mode = rc->coding_mode;
 686
 687     for (i = 0; i < n; i++)
 688         udata[i] = (2 * data[i]) ^ (data[i] >> 31);
 689
 690     calc_sum_top(pmax, exact ? kmax : 0, udata, n, pred_order, sums);
 691
 692     opt_porder = pmin;
 693     bits[pmin] = UINT32_MAX;
 694     for (i = pmax; ; ) {
 695         bits[i] = calc_optimal_rice_params(&tmp_rc, i, sums, n, pred_order, kmax, exact);
 696         if (bits[i] < bits[opt_porder] || pmax == pmin) {
 697             opt_porder = i;
 698             *rc = tmp_rc;
 699         }
 700         if (i == pmin)
 701             break;
 702         calc_sum_next(--i, sums, exact ? kmax : 0);
 703     }
 704
 705     return bits[opt_porder];
 706 }
 707
 708
 709 static int get_max_p_order(int max_porder, int n, int order)
 710 {
 711     int porder = FFMIN(max_porder, av_log2(n^(n-1)));
 712     if (order > 0)
 713         porder = FFMIN(porder, av_log2(n/order));
 714     return porder;
 715 }
 716
 717
 718 static uint64_t find_subframe_rice_params(FlacEncodeContext *s,
 719                                           FlacSubframe *sub, int pred_order)
 720 {
 721     int pmin = get_max_p_order(s->options.min_partition_order,
 722                                s->frame.blocksize, pred_order);
 723     int pmax = get_max_p_order(s->options.max_partition_order,
 724                                s->frame.blocksize, pred_order);
 725
 726     uint64_t bits = 8 + pred_order * sub->obits + 2 + sub->rc.coding_mode;
 727     if (sub->type == FLAC_SUBFRAME_LPC)
 728         bits += 4 + 5 + pred_order * s->options.lpc_coeff_precision;
 729     bits += calc_rice_params(&sub->rc, sub->rc_udata, sub->rc_sums, pmin, pmax, sub->residual,
 730                              s->frame.blocksize, pred_order, s->options.exact_rice_parameters);
 731     return bits;
 732 }
 733
 734
 735 static void encode_residual_fixed(int32_t *res, const int32_t *smp, int n,
 736                                   int order)
 737 {
 738     int i;
 739
 740     for (i = 0; i < order; i++)
 741         res[i] = smp[i];
 742
 743     if (order == 0) {
 744         for (i = order; i < n; i++)
 745             res[i] = smp[i];
 746     } else if (order == 1) {
 747         for (i = order; i < n; i++)
 748             res[i] = smp[i] - smp[i-1];
 749     } else if (order == 2) {
 750         int a = smp[order-1] - smp[order-2];
 751         for (i = order; i < n; i += 2) {
 752             int b    = smp[i  ] - smp[i-1];
 753             res[i]   = b - a;
 754             a        = smp[i+1] - smp[i  ];
 755             res[i+1] = a - b;
 756         }
 757     } else if (order == 3) {
 758         int a = smp[order-1] -   smp[order-2];
 759         int c = smp[order-1] - 2*smp[order-2] + smp[order-3];
 760         for (i = order; i < n; i += 2) {
 761             int b    = smp[i  ] - smp[i-1];
 762             int d    = b - a;
 763             res[i]   = d - c;
 764             a        = smp[i+1] - smp[i  ];
 765             c        = a - b;
 766             res[i+1] = c - d;
 767         }
 768     } else {
 769         int a = smp[order-1] -   smp[order-2];
 770         int c = smp[order-1] - 2*smp[order-2] +   smp[order-3];
 771         int e = smp[order-1] - 3*smp[order-2] + 3*smp[order-3] - smp[order-4];
 772         for (i = order; i < n; i += 2) {
 773             int b    = smp[i  ] - smp[i-1];
 774             int d    = b - a;
 775             int f    = d - c;
 776             res[i  ] = f - e;
 777             a        = smp[i+1] - smp[i  ];
 778             c        = a - b;
 779             e        = c - d;
 780             res[i+1] = e - f;
 781         }
 782     }
 783 }
 784
 785
 786 static int encode_residual_ch(FlacEncodeContext *s, int ch)
 787 {
 788     int i, n;
 789     int min_order, max_order, opt_order, omethod;
 790     FlacFrame *frame;
 791     FlacSubframe *sub;
 792     int32_t coefs[MAX_LPC_ORDER][MAX_LPC_ORDER];
 793     int shift[MAX_LPC_ORDER];
 794     int32_t *res, *smp;
 795
 796     frame = &s->frame;
 797     sub   = &frame->subframes[ch];
 798     res   = sub->residual;
 799     smp   = sub->samples;
 800     n     = frame->blocksize;
 801
 802     /* CONSTANT */
 803     for (i = 1; i < n; i++)
 804         if(smp[i] != smp[0])
 805             break;
 806     if (i == n) {
 807         sub->type = sub->type_code = FLAC_SUBFRAME_CONSTANT;
 808         res[0] = smp[0];
 809         return subframe_count_exact(s, sub, 0);
 810     }
 811
 812     /* VERBATIM */
 813     if (frame->verbatim_only || n < 5) {
 814         sub->type = sub->type_code = FLAC_SUBFRAME_VERBATIM;
 815         memcpy(res, smp, n * sizeof(int32_t));
 816         return subframe_count_exact(s, sub, 0);
 817     }
 818
 819     min_order  = s->options.min_prediction_order;
 820     max_order  = s->options.max_prediction_order;
 821     omethod    = s->options.prediction_order_method;
 822
 823     /* FIXED */
 824     sub->type = FLAC_SUBFRAME_FIXED;
 825     if (s->options.lpc_type == FF_LPC_TYPE_NONE  ||
 826         s->options.lpc_type == FF_LPC_TYPE_FIXED || n <= max_order) {
 827         uint64_t bits[MAX_FIXED_ORDER+1];
 828         if (max_order > MAX_FIXED_ORDER)
 829             max_order = MAX_FIXED_ORDER;
 830         opt_order = 0;
 831         bits[0]   = UINT32_MAX;
 832         for (i = min_order; i <= max_order; i++) {
 833             encode_residual_fixed(res, smp, n, i);
 834             bits[i] = find_subframe_rice_params(s, sub, i);
 835             if (bits[i] < bits[opt_order])
 836                 opt_order = i;
 837         }
 838         sub->order     = opt_order;
 839         sub->type_code = sub->type | sub->order;
 840         if (sub->order != max_order) {
 841             encode_residual_fixed(res, smp, n, sub->order);
 842             find_subframe_rice_params(s, sub, sub->order);
 843         }
 844         return subframe_count_exact(s, sub, sub->order);
 845     }
 846
 847     /* LPC */
 848     sub->type = FLAC_SUBFRAME_LPC;
 849     opt_order = ff_lpc_calc_coefs(&s->lpc_ctx, smp, n, min_order, max_order,
 850                                   s->options.lpc_coeff_precision, coefs, shift, s->options.lpc_type,
 851                                   s->options.lpc_passes, omethod,
 852                                   MIN_LPC_SHIFT, MAX_LPC_SHIFT, 0);
 853
 854     if (omethod == ORDER_METHOD_2LEVEL ||
 855         omethod == ORDER_METHOD_4LEVEL ||
 856         omethod == ORDER_METHOD_8LEVEL) {
 857         int levels = 1 << omethod;
 858         uint64_t bits[1 << ORDER_METHOD_8LEVEL];
 859         int order       = -1;
 860         int opt_index   = levels-1;
 861         opt_order       = max_order-1;
 862         bits[opt_index] = UINT32_MAX;
 863         for (i = levels-1; i >= 0; i--) {
 864             int last_order = order;
 865             order = min_order + (((max_order-min_order+1) * (i+1)) / levels)-1;
 866             order = av_clip(order, min_order - 1, max_order - 1);
 867             if (order == last_order)
 868                 continue;
 869             if (s->bps_code * 4 + s->options.lpc_coeff_precision + av_log2(order) <= 32) {
 870                 s->flac_dsp.lpc16_encode(res, smp, n, order+1, coefs[order],
 871                                          shift[order]);
 872             } else {
 873                 s->flac_dsp.lpc32_encode(res, smp, n, order+1, coefs[order],
 874                                          shift[order]);
 875             }
 876             bits[i] = find_subframe_rice_params(s, sub, order+1);
 877             if (bits[i] < bits[opt_index]) {
 878                 opt_index = i;
 879                 opt_order = order;
 880             }
 881         }
 882         opt_order++;
 883     } else if (omethod == ORDER_METHOD_SEARCH) {
 884         // brute-force optimal order search
 885         uint64_t bits[MAX_LPC_ORDER];
 886         opt_order = 0;
 887         bits[0]   = UINT32_MAX;
 888         for (i = min_order-1; i < max_order; i++) {
 889             if (s->bps_code * 4 + s->options.lpc_coeff_precision + av_log2(i) <= 32) {
 890                 s->flac_dsp.lpc16_encode(res, smp, n, i+1, coefs[i], shift[i]);
 891             } else {
 892                 s->flac_dsp.lpc32_encode(res, smp, n, i+1, coefs[i], shift[i]);
 893             }
 894             bits[i] = find_subframe_rice_params(s, sub, i+1);
 895             if (bits[i] < bits[opt_order])
 896                 opt_order = i;
 897         }
 898         opt_order++;
 899     } else if (omethod == ORDER_METHOD_LOG) {
 900         uint64_t bits[MAX_LPC_ORDER];
 901         int step;
 902
 903         opt_order = min_order - 1 + (max_order-min_order)/3;
 904         memset(bits, -1, sizeof(bits));
 905
 906         for (step = 16; step; step >>= 1) {
 907             int last = opt_order;
 908             for (i = last-step; i <= last+step; i += step) {
 909                 if (i < min_order-1 || i >= max_order || bits[i] < UINT32_MAX)
 910                     continue;
 911                 if (s->bps_code * 4 + s->options.lpc_coeff_precision + av_log2(i) <= 32) {
 912                     s->flac_dsp.lpc32_encode(res, smp, n, i+1, coefs[i], shift[i]);
 913                 } else {
 914                     s->flac_dsp.lpc16_encode(res, smp, n, i+1, coefs[i], shift[i]);
 915                 }
 916                 bits[i] = find_subframe_rice_params(s, sub, i+1);
 917                 if (bits[i] < bits[opt_order])
 918                     opt_order = i;
 919             }
 920         }
 921         opt_order++;
 922     }
 923
 924     if (s->options.multi_dim_quant) {
 925         int allsteps = 1;
 926         int i, step, improved;
 927         int64_t best_score = INT64_MAX;
 928         int32_t qmax;
 929
 930         qmax = (1 << (s->options.lpc_coeff_precision - 1)) - 1;
 931
 932         for (i=0; i<opt_order; i++)
 933             allsteps *= 3;
 934
 935         do {
 936             improved = 0;
 937             for (step = 0; step < allsteps; step++) {
 938                 int tmp = step;
 939                 int32_t lpc_try[MAX_LPC_ORDER];
 940                 int64_t score = 0;
 941                 int diffsum = 0;
 942
 943                 for (i=0; i<opt_order; i++) {
 944                     int diff = ((tmp + 1) % 3) - 1;
 945                     lpc_try[i] = av_clip(coefs[opt_order - 1][i] + diff, -qmax, qmax);
 946                     tmp /= 3;
 947                     diffsum += !!diff;
 948                 }
 949                 if (diffsum >8)
 950                     continue;
 951
 952                 if (s->bps_code * 4 + s->options.lpc_coeff_precision + av_log2(opt_order - 1) <= 32) {
 953                     s->flac_dsp.lpc16_encode(res, smp, n, opt_order, lpc_try, shift[opt_order-1]);
 954                 } else {
 955                     s->flac_dsp.lpc32_encode(res, smp, n, opt_order, lpc_try, shift[opt_order-1]);
 956                 }
 957                 score = find_subframe_rice_params(s, sub, opt_order);
 958                 if (score < best_score) {
 959                     best_score = score;
 960                     memcpy(coefs[opt_order-1], lpc_try, sizeof(*coefs));
 961                     improved=1;
 962                 }
 963             }
 964         } while(improved);
 965     }
 966
 967     sub->order     = opt_order;
 968     sub->type_code = sub->type | (sub->order-1);
 969     sub->shift     = shift[sub->order-1];
 970     for (i = 0; i < sub->order; i++)
 971         sub->coefs[i] = coefs[sub->order-1][i];
 972
 973     if (s->bps_code * 4 + s->options.lpc_coeff_precision + av_log2(opt_order) <= 32) {
 974         s->flac_dsp.lpc16_encode(res, smp, n, sub->order, sub->coefs, sub->shift);
 975     } else {
 976         s->flac_dsp.lpc32_encode(res, smp, n, sub->order, sub->coefs, sub->shift);
 977     }
 978
 979     find_subframe_rice_params(s, sub, sub->order);
 980
 981     return subframe_count_exact(s, sub, sub->order);
 982 }
 983
 984
 985 static int count_frame_header(FlacEncodeContext *s)
 986 {
 987     uint8_t av_unused tmp;
 988     int count;
 989
 990     /*
 991     <14> Sync code
 992     <1>  Reserved
 993     <1>  Blocking strategy
 994     <4>  Block size in inter-channel samples
 995     <4>  Sample rate
 996     <4>  Channel assignment
 997     <3>  Sample size in bits
 998     <1>  Reserved
 999     */
1000     count = 32;
1001
1002     /* coded frame number */
1003     PUT_UTF8(s->frame_count, tmp, count += 8;)
1004
1005     /* explicit block size */
1006     if (s->frame.bs_code[0] == 6)
1007         count += 8;
1008     else if (s->frame.bs_code[0] == 7)
1009         count += 16;
1010
1011     /* explicit sample rate */
1012     count += ((s->sr_code[0] == 12) + (s->sr_code[0] > 12) * 2) * 8;
1013
1014     /* frame header CRC-8 */
1015     count += 8;
1016
1017     return count;
1018 }
1019
1020
1021 static int encode_frame(FlacEncodeContext *s)
1022 {
1023     int ch;
1024     uint64_t count;
1025
1026     count = count_frame_header(s);
1027
1028     for (ch = 0; ch < s->channels; ch++)
1029         count += encode_residual_ch(s, ch);
1030
1031     count += (8 - (count & 7)) & 7; // byte alignment
1032     count += 16;                    // CRC-16
1033
1034     count >>= 3;
1035     if (count > INT_MAX)
1036         return AVERROR_BUG;
1037     return count;
1038 }
1039
1040
1041 static void remove_wasted_bits(FlacEncodeContext *s)
1042 {
1043     int ch, i;
1044
1045     for (ch = 0; ch < s->channels; ch++) {
1046         FlacSubframe *sub = &s->frame.subframes[ch];
1047         int32_t v         = 0;
1048
1049         for (i = 0; i < s->frame.blocksize; i++) {
1050             v |= sub->samples[i];
1051             if (v & 1)
1052                 break;
1053         }
1054
1055         if (v && !(v & 1)) {
1056             v = ff_ctz(v);
1057
1058             for (i = 0; i < s->frame.blocksize; i++)
1059                 sub->samples[i] >>= v;
1060
1061             sub->wasted = v;
1062             sub->obits -= v;
1063
1064             /* for 24-bit, check if removing wasted bits makes the range better
1065                suited for using RICE instead of RICE2 for entropy coding */
1066             if (sub->obits <= 17)
1067                 sub->rc.coding_mode = CODING_MODE_RICE;
1068         }
1069     }
1070 }
1071
1072
1073 static int estimate_stereo_mode(const int32_t *left_ch, const int32_t *right_ch, int n,
1074                                 int max_rice_param)
1075 {
1076     int i, best;
1077     int32_t lt, rt;
1078     uint64_t sum[4];
1079     uint64_t score[4];
1080     int k;
1081
1082     /* calculate sum of 2nd order residual for each channel */
1083     sum[0] = sum[1] = sum[2] = sum[3] = 0;
1084     for (i = 2; i < n; i++) {
1085         lt = left_ch[i]  - 2*left_ch[i-1]  + left_ch[i-2];
1086         rt = right_ch[i] - 2*right_ch[i-1] + right_ch[i-2];
1087         sum[2] += FFABS((lt + rt) >> 1);
1088         sum[3] += FFABS(lt - rt);
1089         sum[0] += FFABS(lt);
1090         sum[1] += FFABS(rt);
1091     }
1092     /* estimate bit counts */
1093     for (i = 0; i < 4; i++) {
1094         k      = find_optimal_param(2 * sum[i], n, max_rice_param);
1095         sum[i] = rice_encode_count( 2 * sum[i], n, k);
1096     }
1097
1098     /* calculate score for each mode */
1099     score[0] = sum[0] + sum[1];
1100     score[1] = sum[0] + sum[3];
1101     score[2] = sum[1] + sum[3];
1102     score[3] = sum[2] + sum[3];
1103
1104     /* return mode with lowest score */
1105     best = 0;
1106     for (i = 1; i < 4; i++)
1107         if (score[i] < score[best])
1108             best = i;
1109
1110     return best;
1111 }
1112
1113
1114 /**
1115  * Perform stereo channel decorrelation.
1116  */
1117 static void channel_decorrelation(FlacEncodeContext *s)
1118 {
1119     FlacFrame *frame;
1120     int32_t *left, *right;
1121     int i, n;
1122
1123     frame = &s->frame;
1124     n     = frame->blocksize;
1125     left  = frame->subframes[0].samples;
1126     right = frame->subframes[1].samples;
1127
1128     if (s->channels != 2) {
1129         frame->ch_mode = FLAC_CHMODE_INDEPENDENT;
1130         return;
1131     }
1132
1133     if (s->options.ch_mode < 0) {
1134         int max_rice_param = (1 << frame->subframes[0].rc.coding_mode) - 2;
1135         frame->ch_mode = estimate_stereo_mode(left, right, n, max_rice_param);
1136     } else
1137         frame->ch_mode = s->options.ch_mode;
1138
1139     /* perform decorrelation and adjust bits-per-sample */
1140     if (frame->ch_mode == FLAC_CHMODE_INDEPENDENT)
1141         return;
1142     if (frame->ch_mode == FLAC_CHMODE_MID_SIDE) {
1143         int32_t tmp;
1144         for (i = 0; i < n; i++) {
1145             tmp      = left[i];
1146             left[i]  = (tmp + right[i]) >> 1;
1147             right[i] =  tmp - right[i];
1148         }
1149         frame->subframes[1].obits++;
1150     } else if (frame->ch_mode == FLAC_CHMODE_LEFT_SIDE) {
1151         for (i = 0; i < n; i++)
1152             right[i] = left[i] - right[i];
1153         frame->subframes[1].obits++;
1154     } else {
1155         for (i = 0; i < n; i++)
1156             left[i] -= right[i];
1157         frame->subframes[0].obits++;
1158     }
1159 }
1160
1161
1162 static void write_utf8(PutBitContext *pb, uint32_t val)
1163 {
1164     uint8_t tmp;
1165     PUT_UTF8(val, tmp, put_bits(pb, 8, tmp);)
1166 }
1167
1168
1169 static void write_frame_header(FlacEncodeContext *s)
1170 {
1171     FlacFrame *frame;
1172     int crc;
1173
1174     frame = &s->frame;
1175
1176     put_bits(&s->pb, 16, 0xFFF8);
1177     put_bits(&s->pb, 4, frame->bs_code[0]);
1178     put_bits(&s->pb, 4, s->sr_code[0]);
1179
1180     if (frame->ch_mode == FLAC_CHMODE_INDEPENDENT)
1181         put_bits(&s->pb, 4, s->channels-1);
1182     else
1183         put_bits(&s->pb, 4, frame->ch_mode + FLAC_MAX_CHANNELS - 1);
1184
1185     put_bits(&s->pb, 3, s->bps_code);
1186     put_bits(&s->pb, 1, 0);
1187     write_utf8(&s->pb, s->frame_count);
1188
1189     if (frame->bs_code[0] == 6)
1190         put_bits(&s->pb, 8, frame->bs_code[1]);
1191     else if (frame->bs_code[0] == 7)
1192         put_bits(&s->pb, 16, frame->bs_code[1]);
1193
1194     if (s->sr_code[0] == 12)
1195         put_bits(&s->pb, 8, s->sr_code[1]);
1196     else if (s->sr_code[0] > 12)
1197         put_bits(&s->pb, 16, s->sr_code[1]);
1198
1199     flush_put_bits(&s->pb);
1200     crc = av_crc(av_crc_get_table(AV_CRC_8_ATM), 0, s->pb.buf,
1201                  put_bytes_output(&s->pb));
1202     put_bits(&s->pb, 8, crc);
1203 }
1204
1205
1206 static void write_subframes(FlacEncodeContext *s)
1207 {
1208     int ch;
1209
1210     for (ch = 0; ch < s->channels; ch++) {
1211         FlacSubframe *sub = &s->frame.subframes[ch];
1212         int i, p, porder, psize;
1213         int32_t *part_end;
1214         int32_t *res       =  sub->residual;
1215         int32_t *frame_end = &sub->residual[s->frame.blocksize];
1216
1217         /* subframe header */
1218         put_bits(&s->pb, 1, 0);
1219         put_bits(&s->pb, 6, sub->type_code);
1220         put_bits(&s->pb, 1, !!sub->wasted);
1221         if (sub->wasted)
1222             put_bits(&s->pb, sub->wasted, 1);
1223
1224         /* subframe */
1225         if (sub->type == FLAC_SUBFRAME_CONSTANT) {
1226             put_sbits(&s->pb, sub->obits, res[0]);
1227         } else if (sub->type == FLAC_SUBFRAME_VERBATIM) {
1228             while (res < frame_end)
1229                 put_sbits(&s->pb, sub->obits, *res++);
1230         } else {
1231             /* warm-up samples */
1232             for (i = 0; i < sub->order; i++)
1233                 put_sbits(&s->pb, sub->obits, *res++);
1234
1235             /* LPC coefficients */
1236             if (sub->type == FLAC_SUBFRAME_LPC) {
1237                 int cbits = s->options.lpc_coeff_precision;
1238                 put_bits( &s->pb, 4, cbits-1);
1239                 put_sbits(&s->pb, 5, sub->shift);
1240                 for (i = 0; i < sub->order; i++)
1241                     put_sbits(&s->pb, cbits, sub->coefs[i]);
1242             }
1243
1244             /* rice-encoded block */
1245             put_bits(&s->pb, 2, sub->rc.coding_mode - 4);
1246
1247             /* partition order */
1248             porder  = sub->rc.porder;
1249             psize   = s->frame.blocksize >> porder;
1250             put_bits(&s->pb, 4, porder);
1251
1252             /* residual */
1253             part_end  = &sub->residual[psize];
1254             for (p = 0; p < 1 << porder; p++) {
1255                 int k = sub->rc.params[p];
1256                 put_bits(&s->pb, sub->rc.coding_mode, k);
1257                 while (res < part_end)
1258                     set_sr_golomb_flac(&s->pb, *res++, k, INT32_MAX, 0);
1259                 part_end = FFMIN(frame_end, part_end + psize);
1260             }
1261         }
1262     }
1263 }
1264
1265
1266 static void write_frame_footer(FlacEncodeContext *s)
1267 {
1268     int crc;
1269     flush_put_bits(&s->pb);
1270     crc = av_bswap16(av_crc(av_crc_get_table(AV_CRC_16_ANSI), 0, s->pb.buf,
1271                             put_bytes_output(&s->pb)));
1272     put_bits(&s->pb, 16, crc);
1273     flush_put_bits(&s->pb);
1274 }
1275
1276
1277 static int write_frame(FlacEncodeContext *s, AVPacket *avpkt)
1278 {
1279     init_put_bits(&s->pb, avpkt->data, avpkt->size);
1280     write_frame_header(s);
1281     write_subframes(s);
1282     write_frame_footer(s);
1283     return put_bytes_output(&s->pb);
1284 }
1285
1286
1287 static int update_md5_sum(FlacEncodeContext *s, const void *samples)
1288 {
1289     const uint8_t *buf;
1290     int buf_size = s->frame.blocksize * s->channels *
1291                    ((s->avctx->bits_per_raw_sample + 7) / 8);
1292
1293     if (s->avctx->bits_per_raw_sample > 16 || HAVE_BIGENDIAN) {
1294         av_fast_malloc(&s->md5_buffer, &s->md5_buffer_size, buf_size);
1295         if (!s->md5_buffer)
1296             return AVERROR(ENOMEM);
1297     }
1298
1299     if (s->avctx->bits_per_raw_sample <= 16) {
1300         buf = (const uint8_t *)samples;
1301 #if HAVE_BIGENDIAN
1302         s->bdsp.bswap16_buf((uint16_t *) s->md5_buffer,
1303                             (const uint16_t *) samples, buf_size / 2);
1304         buf = s->md5_buffer;
1305 #endif
1306     } else {
1307         int i;
1308         const int32_t *samples0 = samples;
1309         uint8_t *tmp            = s->md5_buffer;
1310
1311         for (i = 0; i < s->frame.blocksize * s->channels; i++) {
1312             int32_t v = samples0[i] >> 8;
1313             AV_WL24(tmp + 3*i, v);
1314         }
1315         buf = s->md5_buffer;
1316     }
1317     av_md5_update(s->md5ctx, buf, buf_size);
1318
1319     return 0;
1320 }
1321
1322
1323 static int flac_encode_frame(AVCodecContext *avctx, AVPacket *avpkt,
1324                              const AVFrame *frame, int *got_packet_ptr)
1325 {
1326     FlacEncodeContext *s;
1327     int frame_bytes, out_bytes, ret;
1328
1329     s = avctx->priv_data;
1330
1331     /* when the last block is reached, update the header in extradata */
1332     if (!frame) {
1333         s->max_framesize = s->max_encoded_framesize;
1334         av_md5_final(s->md5ctx, s->md5sum);
1335         write_streaminfo(s, avctx->extradata);
1336
1337         if (!s->flushed) {
1338             uint8_t *side_data = av_packet_new_side_data(avpkt, AV_PKT_DATA_NEW_EXTRADATA,
1339                                                          avctx->extradata_size);
1340             if (!side_data)
1341                 return AVERROR(ENOMEM);
1342             memcpy(side_data, avctx->extradata, avctx->extradata_size);
1343
1344             avpkt->pts = s->next_pts;
1345
1346             *got_packet_ptr = 1;
1347             s->flushed = 1;
1348         }
1349
1350         return 0;
1351     }
1352
1353     /* change max_framesize for small final frame */
1354     if (frame->nb_samples < s->frame.blocksize) {
1355         s->max_framesize = ff_flac_get_max_frame_size(frame->nb_samples,
1356                                                       s->channels,
1357                                                       avctx->bits_per_raw_sample);
1358     }
1359
1360     init_frame(s, frame->nb_samples);
1361
1362     copy_samples(s, frame->data[0]);
1363
1364     channel_decorrelation(s);
1365
1366     remove_wasted_bits(s);
1367
1368     frame_bytes = encode_frame(s);
1369
1370     /* Fall back on verbatim mode if the compressed frame is larger than it
1371        would be if encoded uncompressed. */
1372     if (frame_bytes < 0 || frame_bytes > s->max_framesize) {
1373         s->frame.verbatim_only = 1;
1374         frame_bytes = encode_frame(s);
1375         if (frame_bytes < 0) {
1376             av_log(avctx, AV_LOG_ERROR, "Bad frame count\n");
1377             return frame_bytes;
1378         }
1379     }
1380
1381     if ((ret = ff_alloc_packet2(avctx, avpkt, frame_bytes, 0)) < 0)
1382         return ret;
1383
1384     out_bytes = write_frame(s, avpkt);
1385
1386     s->frame_count++;
1387     s->sample_count += frame->nb_samples;
1388     if ((ret = update_md5_sum(s, frame->data[0])) < 0) {
1389         av_log(avctx, AV_LOG_ERROR, "Error updating MD5 checksum\n");
1390         return ret;
1391     }
1392     if (out_bytes > s->max_encoded_framesize)
1393         s->max_encoded_framesize = out_bytes;
1394     if (out_bytes < s->min_framesize)
1395         s->min_framesize = out_bytes;
1396
1397     avpkt->pts      = frame->pts;
1398     avpkt->duration = ff_samples_to_time_base(avctx, frame->nb_samples);
1399     avpkt->size     = out_bytes;
1400
1401     s->next_pts = avpkt->pts + avpkt->duration;
1402
1403     *got_packet_ptr = 1;
1404     return 0;
1405 }
1406
1407
1408 static av_cold int flac_encode_close(AVCodecContext *avctx)
1409 {
1410     if (avctx->priv_data) {
1411         FlacEncodeContext *s = avctx->priv_data;
1412         av_freep(&s->md5ctx);
1413         av_freep(&s->md5_buffer);
1414         ff_lpc_end(&s->lpc_ctx);
1415     }
1416     av_freep(&avctx->extradata);
1417     avctx->extradata_size = 0;
1418     return 0;
1419 }
1420
1421 #define FLAGS AV_OPT_FLAG_ENCODING_PARAM | AV_OPT_FLAG_AUDIO_PARAM
1422 static const AVOption options[] = {
1423 { "lpc_coeff_precision", "LPC coefficient precision", offsetof(FlacEncodeContext, options.lpc_coeff_precision), AV_OPT_TYPE_INT, {.i64 = 15 }, 0, MAX_LPC_PRECISION, FLAGS },
1424 { "lpc_type", "LPC algorithm", offsetof(FlacEncodeContext, options.lpc_type), AV_OPT_TYPE_INT, {.i64 = FF_LPC_TYPE_DEFAULT }, FF_LPC_TYPE_DEFAULT, FF_LPC_TYPE_NB-1, FLAGS, "lpc_type" },
1425 { "none",     NULL, 0, AV_OPT_TYPE_CONST, {.i64 = FF_LPC_TYPE_NONE },     INT_MIN, INT_MAX, FLAGS, "lpc_type" },
1426 { "fixed",    NULL, 0, AV_OPT_TYPE_CONST, {.i64 = FF_LPC_TYPE_FIXED },    INT_MIN, INT_MAX, FLAGS, "lpc_type" },
1427 { "levinson", NULL, 0, AV_OPT_TYPE_CONST, {.i64 = FF_LPC_TYPE_LEVINSON }, INT_MIN, INT_MAX, FLAGS, "lpc_type" },
1428 { "cholesky", NULL, 0, AV_OPT_TYPE_CONST, {.i64 = FF_LPC_TYPE_CHOLESKY }, INT_MIN, INT_MAX, FLAGS, "lpc_type" },
1429 { "lpc_passes", "Number of passes to use for Cholesky factorization during LPC analysis", offsetof(FlacEncodeContext, options.lpc_passes),  AV_OPT_TYPE_INT, {.i64 = 2 }, 1, INT_MAX, FLAGS },
1430 { "min_partition_order",  NULL, offsetof(FlacEncodeContext, options.min_partition_order),  AV_OPT_TYPE_INT, {.i64 = -1 },      -1, MAX_PARTITION_ORDER, FLAGS },
1431 { "max_partition_order",  NULL, offsetof(FlacEncodeContext, options.max_partition_order),  AV_OPT_TYPE_INT, {.i64 = -1 },      -1, MAX_PARTITION_ORDER, FLAGS },
1432 { "prediction_order_method", "Search method for selecting prediction order", offsetof(FlacEncodeContext, options.prediction_order_method), AV_OPT_TYPE_INT, {.i64 = -1 }, -1, ORDER_METHOD_LOG, FLAGS, "predm" },
1433 { "estimation", NULL, 0, AV_OPT_TYPE_CONST, {.i64 = ORDER_METHOD_EST },    INT_MIN, INT_MAX, FLAGS, "predm" },
1434 { "2level",     NULL, 0, AV_OPT_TYPE_CONST, {.i64 = ORDER_METHOD_2LEVEL }, INT_MIN, INT_MAX, FLAGS, "predm" },
1435 { "4level",     NULL, 0, AV_OPT_TYPE_CONST, {.i64 = ORDER_METHOD_4LEVEL }, INT_MIN, INT_MAX, FLAGS, "predm" },
1436 { "8level",     NULL, 0, AV_OPT_TYPE_CONST, {.i64 = ORDER_METHOD_8LEVEL }, INT_MIN, INT_MAX, FLAGS, "predm" },
1437 { "search",     NULL, 0, AV_OPT_TYPE_CONST, {.i64 = ORDER_METHOD_SEARCH }, INT_MIN, INT_MAX, FLAGS, "predm" },
1438 { "log",        NULL, 0, AV_OPT_TYPE_CONST, {.i64 = ORDER_METHOD_LOG },    INT_MIN, INT_MAX, FLAGS, "predm" },
1439 { "ch_mode", "Stereo decorrelation mode", offsetof(FlacEncodeContext, options.ch_mode), AV_OPT_TYPE_INT, { .i64 = -1 }, -1, FLAC_CHMODE_MID_SIDE, FLAGS, "ch_mode" },
1440 { "auto",       NULL, 0, AV_OPT_TYPE_CONST, { .i64 = -1                      }, INT_MIN, INT_MAX, FLAGS, "ch_mode" },
1441 { "indep",      NULL, 0, AV_OPT_TYPE_CONST, { .i64 = FLAC_CHMODE_INDEPENDENT }, INT_MIN, INT_MAX, FLAGS, "ch_mode" },
1442 { "left_side",  NULL, 0, AV_OPT_TYPE_CONST, { .i64 = FLAC_CHMODE_LEFT_SIDE   }, INT_MIN, INT_MAX, FLAGS, "ch_mode" },
1443 { "right_side", NULL, 0, AV_OPT_TYPE_CONST, { .i64 = FLAC_CHMODE_RIGHT_SIDE  }, INT_MIN, INT_MAX, FLAGS, "ch_mode" },
1444 { "mid_side",   NULL, 0, AV_OPT_TYPE_CONST, { .i64 = FLAC_CHMODE_MID_SIDE    }, INT_MIN, INT_MAX, FLAGS, "ch_mode" },
1445 { "exact_rice_parameters", "Calculate rice parameters exactly", offsetof(FlacEncodeContext, options.exact_rice_parameters), AV_OPT_TYPE_BOOL, { .i64 = 0 }, 0, 1, FLAGS },
1446 { "multi_dim_quant",       "Multi-dimensional quantization",    offsetof(FlacEncodeContext, options.multi_dim_quant),       AV_OPT_TYPE_BOOL, { .i64 = 0 }, 0, 1, FLAGS },
1447 { "min_prediction_order", NULL, offsetof(FlacEncodeContext, options.min_prediction_order), AV_OPT_TYPE_INT, { .i64 = -1 }, -1, MAX_LPC_ORDER, FLAGS },
1448 { "max_prediction_order", NULL, offsetof(FlacEncodeContext, options.max_prediction_order), AV_OPT_TYPE_INT, { .i64 = -1 }, -1, MAX_LPC_ORDER, FLAGS },
1449
1450 { NULL },
1451 };
1452
1453 static const AVClass flac_encoder_class = {
1454     .class_name = "FLAC encoder",
1455     .item_name  = av_default_item_name,
1456     .option     = options,
1457     .version    = LIBAVUTIL_VERSION_INT,
1458 };
1459
1460 AVCodec ff_flac_encoder = {
1461     .name           = "flac",
1462     .long_name      = NULL_IF_CONFIG_SMALL("FLAC (Free Lossless Audio Codec)"),
1463     .type           = AVMEDIA_TYPE_AUDIO,
1464     .id             = AV_CODEC_ID_FLAC,
1465     .priv_data_size = sizeof(FlacEncodeContext),
1466     .init           = flac_encode_init,
1467     .encode2        = flac_encode_frame,
1468     .close          = flac_encode_close,
1469     .capabilities   = AV_CODEC_CAP_SMALL_LAST_FRAME | AV_CODEC_CAP_DELAY,
1470     .sample_fmts    = (const enum AVSampleFormat[]){ AV_SAMPLE_FMT_S16,
1471                                                      AV_SAMPLE_FMT_S32,
1472                                                      AV_SAMPLE_FMT_NONE },
1473     .priv_class     = &flac_encoder_class,
1474     .caps_internal  = FF_CODEC_CAP_INIT_CLEANUP,
1475 };