libavcodec/flacenc.c

   1 /**
   2  * FLAC audio encoder
   3  * Copyright (c) 2006  Justin Ruggles <jruggle@earthlink.net>
   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 "avcodec.h"
  23 #include "bitstream.h"
  24 #include "crc.h"
  25 #include "dsputil.h"
  26 #include "golomb.h"
  27 #include "lls.h"
  28
  29 #define FLAC_MAX_CH  8
  30 #define FLAC_MIN_BLOCKSIZE  16
  31 #define FLAC_MAX_BLOCKSIZE  65535
  32
  33 #define FLAC_SUBFRAME_CONSTANT  0
  34 #define FLAC_SUBFRAME_VERBATIM  1
  35 #define FLAC_SUBFRAME_FIXED     8
  36 #define FLAC_SUBFRAME_LPC      32
  37
  38 #define FLAC_CHMODE_NOT_STEREO      0
  39 #define FLAC_CHMODE_LEFT_RIGHT      1
  40 #define FLAC_CHMODE_LEFT_SIDE       8
  41 #define FLAC_CHMODE_RIGHT_SIDE      9
  42 #define FLAC_CHMODE_MID_SIDE       10
  43
  44 #define ORDER_METHOD_EST     0
  45 #define ORDER_METHOD_2LEVEL  1
  46 #define ORDER_METHOD_4LEVEL  2
  47 #define ORDER_METHOD_8LEVEL  3
  48 #define ORDER_METHOD_SEARCH  4
  49 #define ORDER_METHOD_LOG     5
  50
  51 #define FLAC_STREAMINFO_SIZE  34
  52
  53 #define MIN_LPC_ORDER       1
  54 #define MAX_LPC_ORDER      32
  55 #define MAX_FIXED_ORDER     4
  56 #define MAX_PARTITION_ORDER 8
  57 #define MAX_PARTITIONS     (1 << MAX_PARTITION_ORDER)
  58 #define MAX_LPC_PRECISION  15
  59 #define MAX_LPC_SHIFT      15
  60 #define MAX_RICE_PARAM     14
  61
  62 typedef struct CompressionOptions {
  63     int compression_level;
  64     int block_time_ms;
  65     int use_lpc;
  66     int lpc_coeff_precision;
  67     int min_prediction_order;
  68     int max_prediction_order;
  69     int prediction_order_method;
  70     int min_partition_order;
  71     int max_partition_order;
  72 } CompressionOptions;
  73
  74 typedef struct RiceContext {
  75     int porder;
  76     int params[MAX_PARTITIONS];
  77 } RiceContext;
  78
  79 typedef struct FlacSubframe {
  80     int type;
  81     int type_code;
  82     int obits;
  83     int order;
  84     int32_t coefs[MAX_LPC_ORDER];
  85     int shift;
  86     RiceContext rc;
  87     int32_t samples[FLAC_MAX_BLOCKSIZE];
  88     int32_t residual[FLAC_MAX_BLOCKSIZE+1];
  89 } FlacSubframe;
  90
  91 typedef struct FlacFrame {
  92     FlacSubframe subframes[FLAC_MAX_CH];
  93     int blocksize;
  94     int bs_code[2];
  95     uint8_t crc8;
  96     int ch_mode;
  97 } FlacFrame;
  98
  99 typedef struct FlacEncodeContext {
 100     PutBitContext pb;
 101     int channels;
 102     int ch_code;
 103     int samplerate;
 104     int sr_code[2];
 105     int max_framesize;
 106     uint32_t frame_count;
 107     FlacFrame frame;
 108     CompressionOptions options;
 109     AVCodecContext *avctx;
 110     DSPContext dsp;
 111 } FlacEncodeContext;
 112
 113 static const int flac_samplerates[16] = {
 114     0, 0, 0, 0,
 115     8000, 16000, 22050, 24000, 32000, 44100, 48000, 96000,
 116     0, 0, 0, 0
 117 };
 118
 119 static const int flac_blocksizes[16] = {
 120     0,
 121     192,
 122     576, 1152, 2304, 4608,
 123     0, 0,
 124     256, 512, 1024, 2048, 4096, 8192, 16384, 32768
 125 };
 126
 127 /**
 128  * Writes streaminfo metadata block to byte array
 129  */
 130 static void write_streaminfo(FlacEncodeContext *s, uint8_t *header)
 131 {
 132     PutBitContext pb;
 133
 134     memset(header, 0, FLAC_STREAMINFO_SIZE);
 135     init_put_bits(&pb, header, FLAC_STREAMINFO_SIZE);
 136
 137     /* streaminfo metadata block */
 138     put_bits(&pb, 16, s->avctx->frame_size);
 139     put_bits(&pb, 16, s->avctx->frame_size);
 140     put_bits(&pb, 24, 0);
 141     put_bits(&pb, 24, s->max_framesize);
 142     put_bits(&pb, 20, s->samplerate);
 143     put_bits(&pb, 3, s->channels-1);
 144     put_bits(&pb, 5, 15);       /* bits per sample - 1 */
 145     flush_put_bits(&pb);
 146     /* total samples = 0 */
 147     /* MD5 signature = 0 */
 148 }
 149
 150 /**
 151  * Sets blocksize based on samplerate
 152  * Chooses the closest predefined blocksize >= BLOCK_TIME_MS milliseconds
 153  */
 154 static int select_blocksize(int samplerate, int block_time_ms)
 155 {
 156     int i;
 157     int target;
 158     int blocksize;
 159
 160     assert(samplerate > 0);
 161     blocksize = flac_blocksizes[1];
 162     target = (samplerate * block_time_ms) / 1000;
 163     for(i=0; i<16; i++) {
 164         if(target >= flac_blocksizes[i] && flac_blocksizes[i] > blocksize) {
 165             blocksize = flac_blocksizes[i];
 166         }
 167     }
 168     return blocksize;
 169 }
 170
 171 static av_cold int flac_encode_init(AVCodecContext *avctx)
 172 {
 173     int freq = avctx->sample_rate;
 174     int channels = avctx->channels;
 175     FlacEncodeContext *s = avctx->priv_data;
 176     int i, level;
 177     uint8_t *streaminfo;
 178
 179     s->avctx = avctx;
 180
 181     dsputil_init(&s->dsp, avctx);
 182
 183     if(avctx->sample_fmt != SAMPLE_FMT_S16) {
 184         return -1;
 185     }
 186
 187     if(channels < 1 || channels > FLAC_MAX_CH) {
 188         return -1;
 189     }
 190     s->channels = channels;
 191     s->ch_code = s->channels-1;
 192
 193     /* find samplerate in table */
 194     if(freq < 1)
 195         return -1;
 196     for(i=4; i<12; i++) {
 197         if(freq == flac_samplerates[i]) {
 198             s->samplerate = flac_samplerates[i];
 199             s->sr_code[0] = i;
 200             s->sr_code[1] = 0;
 201             break;
 202         }
 203     }
 204     /* if not in table, samplerate is non-standard */
 205     if(i == 12) {
 206         if(freq % 1000 == 0 && freq < 255000) {
 207             s->sr_code[0] = 12;
 208             s->sr_code[1] = freq / 1000;
 209         } else if(freq % 10 == 0 && freq < 655350) {
 210             s->sr_code[0] = 14;
 211             s->sr_code[1] = freq / 10;
 212         } else if(freq < 65535) {
 213             s->sr_code[0] = 13;
 214             s->sr_code[1] = freq;
 215         } else {
 216             return -1;
 217         }
 218         s->samplerate = freq;
 219     }
 220
 221     /* set compression option defaults based on avctx->compression_level */
 222     if(avctx->compression_level < 0) {
 223         s->options.compression_level = 5;
 224     } else {
 225         s->options.compression_level = avctx->compression_level;
 226     }
 227     av_log(avctx, AV_LOG_DEBUG, " compression: %d\n", s->options.compression_level);
 228
 229     level= s->options.compression_level;
 230     if(level > 12) {
 231         av_log(avctx, AV_LOG_ERROR, "invalid compression level: %d\n",
 232                s->options.compression_level);
 233         return -1;
 234     }
 235
 236     s->options.block_time_ms       = ((int[]){ 27, 27, 27,105,105,105,105,105,105,105,105,105,105})[level];
 237     s->options.use_lpc             = ((int[]){  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1})[level];
 238     s->options.min_prediction_order= ((int[]){  2,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1})[level];
 239     s->options.max_prediction_order= ((int[]){  3,  4,  4,  6,  8,  8,  8,  8, 12, 12, 12, 32, 32})[level];
 240     s->options.prediction_order_method = ((int[]){ ORDER_METHOD_EST,    ORDER_METHOD_EST,    ORDER_METHOD_EST,
 241                                                    ORDER_METHOD_EST,    ORDER_METHOD_EST,    ORDER_METHOD_EST,
 242                                                    ORDER_METHOD_4LEVEL, ORDER_METHOD_LOG,    ORDER_METHOD_4LEVEL,
 243                                                    ORDER_METHOD_LOG,    ORDER_METHOD_SEARCH, ORDER_METHOD_LOG,
 244                                                    ORDER_METHOD_SEARCH})[level];
 245     s->options.min_partition_order = ((int[]){  2,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0})[level];
 246     s->options.max_partition_order = ((int[]){  2,  2,  3,  3,  3,  8,  8,  8,  8,  8,  8,  8,  8})[level];
 247
 248     /* set compression option overrides from AVCodecContext */
 249     if(avctx->use_lpc >= 0) {
 250         s->options.use_lpc = av_clip(avctx->use_lpc, 0, 11);
 251     }
 252     if(s->options.use_lpc == 1)
 253         av_log(avctx, AV_LOG_DEBUG, " use lpc: Levinson-Durbin recursion with Welch window\n");
 254     else if(s->options.use_lpc > 1)
 255         av_log(avctx, AV_LOG_DEBUG, " use lpc: Cholesky factorization\n");
 256
 257     if(avctx->min_prediction_order >= 0) {
 258         if(s->options.use_lpc) {
 259             if(avctx->min_prediction_order < MIN_LPC_ORDER ||
 260                     avctx->min_prediction_order > MAX_LPC_ORDER) {
 261                 av_log(avctx, AV_LOG_ERROR, "invalid min prediction order: %d\n",
 262                        avctx->min_prediction_order);
 263                 return -1;
 264             }
 265         } else {
 266             if(avctx->min_prediction_order > MAX_FIXED_ORDER) {
 267                 av_log(avctx, AV_LOG_ERROR, "invalid min prediction order: %d\n",
 268                        avctx->min_prediction_order);
 269                 return -1;
 270             }
 271         }
 272         s->options.min_prediction_order = avctx->min_prediction_order;
 273     }
 274     if(avctx->max_prediction_order >= 0) {
 275         if(s->options.use_lpc) {
 276             if(avctx->max_prediction_order < MIN_LPC_ORDER ||
 277                     avctx->max_prediction_order > MAX_LPC_ORDER) {
 278                 av_log(avctx, AV_LOG_ERROR, "invalid max prediction order: %d\n",
 279                        avctx->max_prediction_order);
 280                 return -1;
 281             }
 282         } else {
 283             if(avctx->max_prediction_order > MAX_FIXED_ORDER) {
 284                 av_log(avctx, AV_LOG_ERROR, "invalid max prediction order: %d\n",
 285                        avctx->max_prediction_order);
 286                 return -1;
 287             }
 288         }
 289         s->options.max_prediction_order = avctx->max_prediction_order;
 290     }
 291     if(s->options.max_prediction_order < s->options.min_prediction_order) {
 292         av_log(avctx, AV_LOG_ERROR, "invalid prediction orders: min=%d max=%d\n",
 293                s->options.min_prediction_order, s->options.max_prediction_order);
 294         return -1;
 295     }
 296     av_log(avctx, AV_LOG_DEBUG, " prediction order: %d, %d\n",
 297            s->options.min_prediction_order, s->options.max_prediction_order);
 298
 299     if(avctx->prediction_order_method >= 0) {
 300         if(avctx->prediction_order_method > ORDER_METHOD_LOG) {
 301             av_log(avctx, AV_LOG_ERROR, "invalid prediction order method: %d\n",
 302                    avctx->prediction_order_method);
 303             return -1;
 304         }
 305         s->options.prediction_order_method = avctx->prediction_order_method;
 306     }
 307     switch(s->options.prediction_order_method) {
 308         case ORDER_METHOD_EST:    av_log(avctx, AV_LOG_DEBUG, " order method: %s\n",
 309                                          "estimate"); break;
 310         case ORDER_METHOD_2LEVEL: av_log(avctx, AV_LOG_DEBUG, " order method: %s\n",
 311                                          "2-level"); break;
 312         case ORDER_METHOD_4LEVEL: av_log(avctx, AV_LOG_DEBUG, " order method: %s\n",
 313                                          "4-level"); break;
 314         case ORDER_METHOD_8LEVEL: av_log(avctx, AV_LOG_DEBUG, " order method: %s\n",
 315                                          "8-level"); break;
 316         case ORDER_METHOD_SEARCH: av_log(avctx, AV_LOG_DEBUG, " order method: %s\n",
 317                                          "full search"); break;
 318         case ORDER_METHOD_LOG:    av_log(avctx, AV_LOG_DEBUG, " order method: %s\n",
 319                                          "log search"); break;
 320     }
 321
 322     if(avctx->min_partition_order >= 0) {
 323         if(avctx->min_partition_order > MAX_PARTITION_ORDER) {
 324             av_log(avctx, AV_LOG_ERROR, "invalid min partition order: %d\n",
 325                    avctx->min_partition_order);
 326             return -1;
 327         }
 328         s->options.min_partition_order = avctx->min_partition_order;
 329     }
 330     if(avctx->max_partition_order >= 0) {
 331         if(avctx->max_partition_order > MAX_PARTITION_ORDER) {
 332             av_log(avctx, AV_LOG_ERROR, "invalid max partition order: %d\n",
 333                    avctx->max_partition_order);
 334             return -1;
 335         }
 336         s->options.max_partition_order = avctx->max_partition_order;
 337     }
 338     if(s->options.max_partition_order < s->options.min_partition_order) {
 339         av_log(avctx, AV_LOG_ERROR, "invalid partition orders: min=%d max=%d\n",
 340                s->options.min_partition_order, s->options.max_partition_order);
 341         return -1;
 342     }
 343     av_log(avctx, AV_LOG_DEBUG, " partition order: %d, %d\n",
 344            s->options.min_partition_order, s->options.max_partition_order);
 345
 346     if(avctx->frame_size > 0) {
 347         if(avctx->frame_size < FLAC_MIN_BLOCKSIZE ||
 348                 avctx->frame_size > FLAC_MAX_BLOCKSIZE) {
 349             av_log(avctx, AV_LOG_ERROR, "invalid block size: %d\n",
 350                    avctx->frame_size);
 351             return -1;
 352         }
 353     } else {
 354         s->avctx->frame_size = select_blocksize(s->samplerate, s->options.block_time_ms);
 355     }
 356     av_log(avctx, AV_LOG_DEBUG, " block size: %d\n", s->avctx->frame_size);
 357
 358     /* set LPC precision */
 359     if(avctx->lpc_coeff_precision > 0) {
 360         if(avctx->lpc_coeff_precision > MAX_LPC_PRECISION) {
 361             av_log(avctx, AV_LOG_ERROR, "invalid lpc coeff precision: %d\n",
 362                    avctx->lpc_coeff_precision);
 363             return -1;
 364         }
 365         s->options.lpc_coeff_precision = avctx->lpc_coeff_precision;
 366     } else {
 367         /* default LPC precision */
 368         s->options.lpc_coeff_precision = 15;
 369     }
 370     av_log(avctx, AV_LOG_DEBUG, " lpc precision: %d\n",
 371            s->options.lpc_coeff_precision);
 372
 373     /* set maximum encoded frame size in verbatim mode */
 374     if(s->channels == 2) {
 375         s->max_framesize = 14 + ((s->avctx->frame_size * 33 + 7) >> 3);
 376     } else {
 377         s->max_framesize = 14 + (s->avctx->frame_size * s->channels * 2);
 378     }
 379
 380     streaminfo = av_malloc(FLAC_STREAMINFO_SIZE);
 381     write_streaminfo(s, streaminfo);
 382     avctx->extradata = streaminfo;
 383     avctx->extradata_size = FLAC_STREAMINFO_SIZE;
 384
 385     s->frame_count = 0;
 386
 387     avctx->coded_frame = avcodec_alloc_frame();
 388     avctx->coded_frame->key_frame = 1;
 389
 390     return 0;
 391 }
 392
 393 static void init_frame(FlacEncodeContext *s)
 394 {
 395     int i, ch;
 396     FlacFrame *frame;
 397
 398     frame = &s->frame;
 399
 400     for(i=0; i<16; i++) {
 401         if(s->avctx->frame_size == flac_blocksizes[i]) {
 402             frame->blocksize = flac_blocksizes[i];
 403             frame->bs_code[0] = i;
 404             frame->bs_code[1] = 0;
 405             break;
 406         }
 407     }
 408     if(i == 16) {
 409         frame->blocksize = s->avctx->frame_size;
 410         if(frame->blocksize <= 256) {
 411             frame->bs_code[0] = 6;
 412             frame->bs_code[1] = frame->blocksize-1;
 413         } else {
 414             frame->bs_code[0] = 7;
 415             frame->bs_code[1] = frame->blocksize-1;
 416         }
 417     }
 418
 419     for(ch=0; ch<s->channels; ch++) {
 420         frame->subframes[ch].obits = 16;
 421     }
 422 }
 423
 424 /**
 425  * Copy channel-interleaved input samples into separate subframes
 426  */
 427 static void copy_samples(FlacEncodeContext *s, int16_t *samples)
 428 {
 429     int i, j, ch;
 430     FlacFrame *frame;
 431
 432     frame = &s->frame;
 433     for(i=0,j=0; i<frame->blocksize; i++) {
 434         for(ch=0; ch<s->channels; ch++,j++) {
 435             frame->subframes[ch].samples[i] = samples[j];
 436         }
 437     }
 438 }
 439
 440
 441 #define rice_encode_count(sum, n, k) (((n)*((k)+1))+((sum-(n>>1))>>(k)))
 442
 443 /**
 444  * Solve for d/dk(rice_encode_count) = n-((sum-(n>>1))>>(k+1)) = 0
 445  */
 446 static int find_optimal_param(uint32_t sum, int n)
 447 {
 448     int k;
 449     uint32_t sum2;
 450
 451     if(sum <= n>>1)
 452         return 0;
 453     sum2 = sum-(n>>1);
 454     k = av_log2(n<256 ? FASTDIV(sum2,n) : sum2/n);
 455     return FFMIN(k, MAX_RICE_PARAM);
 456 }
 457
 458 static uint32_t calc_optimal_rice_params(RiceContext *rc, int porder,
 459                                          uint32_t *sums, int n, int pred_order)
 460 {
 461     int i;
 462     int k, cnt, part;
 463     uint32_t all_bits;
 464
 465     part = (1 << porder);
 466     all_bits = 4 * part;
 467
 468     cnt = (n >> porder) - pred_order;
 469     for(i=0; i<part; i++) {
 470         k = find_optimal_param(sums[i], cnt);
 471         rc->params[i] = k;
 472         all_bits += rice_encode_count(sums[i], cnt, k);
 473         cnt = n >> porder;
 474     }
 475
 476     rc->porder = porder;
 477
 478     return all_bits;
 479 }
 480
 481 static void calc_sums(int pmin, int pmax, uint32_t *data, int n, int pred_order,
 482                       uint32_t sums[][MAX_PARTITIONS])
 483 {
 484     int i, j;
 485     int parts;
 486     uint32_t *res, *res_end;
 487
 488     /* sums for highest level */
 489     parts = (1 << pmax);
 490     res = &data[pred_order];
 491     res_end = &data[n >> pmax];
 492     for(i=0; i<parts; i++) {
 493         uint32_t sum = 0;
 494         while(res < res_end){
 495             sum += *(res++);
 496         }
 497         sums[pmax][i] = sum;
 498         res_end+= n >> pmax;
 499     }
 500     /* sums for lower levels */
 501     for(i=pmax-1; i>=pmin; i--) {
 502         parts = (1 << i);
 503         for(j=0; j<parts; j++) {
 504             sums[i][j] = sums[i+1][2*j] + sums[i+1][2*j+1];
 505         }
 506     }
 507 }
 508
 509 static uint32_t calc_rice_params(RiceContext *rc, int pmin, int pmax,
 510                                  int32_t *data, int n, int pred_order)
 511 {
 512     int i;
 513     uint32_t bits[MAX_PARTITION_ORDER+1];
 514     int opt_porder;
 515     RiceContext tmp_rc;
 516     uint32_t *udata;
 517     uint32_t sums[MAX_PARTITION_ORDER+1][MAX_PARTITIONS];
 518
 519     assert(pmin >= 0 && pmin <= MAX_PARTITION_ORDER);
 520     assert(pmax >= 0 && pmax <= MAX_PARTITION_ORDER);
 521     assert(pmin <= pmax);
 522
 523     udata = av_malloc(n * sizeof(uint32_t));
 524     for(i=0; i<n; i++) {
 525         udata[i] = (2*data[i]) ^ (data[i]>>31);
 526     }
 527
 528     calc_sums(pmin, pmax, udata, n, pred_order, sums);
 529
 530     opt_porder = pmin;
 531     bits[pmin] = UINT32_MAX;
 532     for(i=pmin; i<=pmax; i++) {
 533         bits[i] = calc_optimal_rice_params(&tmp_rc, i, sums[i], n, pred_order);
 534         if(bits[i] <= bits[opt_porder]) {
 535             opt_porder = i;
 536             *rc= tmp_rc;
 537         }
 538     }
 539
 540     av_freep(&udata);
 541     return bits[opt_porder];
 542 }
 543
 544 static int get_max_p_order(int max_porder, int n, int order)
 545 {
 546     int porder = FFMIN(max_porder, av_log2(n^(n-1)));
 547     if(order > 0)
 548         porder = FFMIN(porder, av_log2(n/order));
 549     return porder;
 550 }
 551
 552 static uint32_t calc_rice_params_fixed(RiceContext *rc, int pmin, int pmax,
 553                                        int32_t *data, int n, int pred_order,
 554                                        int bps)
 555 {
 556     uint32_t bits;
 557     pmin = get_max_p_order(pmin, n, pred_order);
 558     pmax = get_max_p_order(pmax, n, pred_order);
 559     bits = pred_order*bps + 6;
 560     bits += calc_rice_params(rc, pmin, pmax, data, n, pred_order);
 561     return bits;
 562 }
 563
 564 static uint32_t calc_rice_params_lpc(RiceContext *rc, int pmin, int pmax,
 565                                      int32_t *data, int n, int pred_order,
 566                                      int bps, int precision)
 567 {
 568     uint32_t bits;
 569     pmin = get_max_p_order(pmin, n, pred_order);
 570     pmax = get_max_p_order(pmax, n, pred_order);
 571     bits = pred_order*bps + 4 + 5 + pred_order*precision + 6;
 572     bits += calc_rice_params(rc, pmin, pmax, data, n, pred_order);
 573     return bits;
 574 }
 575
 576 /**
 577  * Apply Welch window function to audio block
 578  */
 579 static void apply_welch_window(const int32_t *data, int len, double *w_data)
 580 {
 581     int i, n2;
 582     double w;
 583     double c;
 584
 585     assert(!(len&1)); //the optimization in r11881 does not support odd len
 586                       //if someone wants odd len extend the change in r11881
 587
 588     n2 = (len >> 1);
 589     c = 2.0 / (len - 1.0);
 590
 591     w_data+=n2;
 592       data+=n2;
 593     for(i=0; i<n2; i++) {
 594         w = c - n2 + i;
 595         w = 1.0 - (w * w);
 596         w_data[-i-1] = data[-i-1] * w;
 597         w_data[+i  ] = data[+i  ] * w;
 598     }
 599 }
 600
 601 /**
 602  * Calculates autocorrelation data from audio samples
 603  * A Welch window function is applied before calculation.
 604  */
 605 void ff_flac_compute_autocorr(const int32_t *data, int len, int lag,
 606                               double *autoc)
 607 {
 608     int i, j;
 609     double tmp[len + lag + 1];
 610     double *data1= tmp + lag;
 611
 612     apply_welch_window(data, len, data1);
 613
 614     for(j=0; j<lag; j++)
 615         data1[j-lag]= 0.0;
 616     data1[len] = 0.0;
 617
 618     for(j=0; j<lag; j+=2){
 619         double sum0 = 1.0, sum1 = 1.0;
 620         for(i=0; i<len; i++){
 621             sum0 += data1[i] * data1[i-j];
 622             sum1 += data1[i] * data1[i-j-1];
 623         }
 624         autoc[j  ] = sum0;
 625         autoc[j+1] = sum1;
 626     }
 627
 628     if(j==lag){
 629         double sum = 1.0;
 630         for(i=0; i<len; i+=2){
 631             sum += data1[i  ] * data1[i-j  ]
 632                  + data1[i+1] * data1[i-j+1];
 633         }
 634         autoc[j] = sum;
 635     }
 636 }
 637
 638 /**
 639  * Levinson-Durbin recursion.
 640  * Produces LPC coefficients from autocorrelation data.
 641  */
 642 static void compute_lpc_coefs(const double *autoc, int max_order,
 643                               double lpc[][MAX_LPC_ORDER], double *ref)
 644 {
 645    int i, j, i2;
 646    double r, err, tmp;
 647    double lpc_tmp[MAX_LPC_ORDER];
 648
 649    for(i=0; i<max_order; i++) lpc_tmp[i] = 0;
 650    err = autoc[0];
 651
 652    for(i=0; i<max_order; i++) {
 653       r = -autoc[i+1];
 654       for(j=0; j<i; j++) {
 655           r -= lpc_tmp[j] * autoc[i-j];
 656       }
 657       r /= err;
 658       ref[i] = fabs(r);
 659
 660       err *= 1.0 - (r * r);
 661
 662       i2 = (i >> 1);
 663       lpc_tmp[i] = r;
 664       for(j=0; j<i2; j++) {
 665          tmp = lpc_tmp[j];
 666          lpc_tmp[j] += r * lpc_tmp[i-1-j];
 667          lpc_tmp[i-1-j] += r * tmp;
 668       }
 669       if(i & 1) {
 670           lpc_tmp[j] += lpc_tmp[j] * r;
 671       }
 672
 673       for(j=0; j<=i; j++) {
 674           lpc[i][j] = -lpc_tmp[j];
 675       }
 676    }
 677 }
 678
 679 /**
 680  * Quantize LPC coefficients
 681  */
 682 static void quantize_lpc_coefs(double *lpc_in, int order, int precision,
 683                                int32_t *lpc_out, int *shift)
 684 {
 685     int i;
 686     double cmax, error;
 687     int32_t qmax;
 688     int sh;
 689
 690     /* define maximum levels */
 691     qmax = (1 << (precision - 1)) - 1;
 692
 693     /* find maximum coefficient value */
 694     cmax = 0.0;
 695     for(i=0; i<order; i++) {
 696         cmax= FFMAX(cmax, fabs(lpc_in[i]));
 697     }
 698
 699     /* if maximum value quantizes to zero, return all zeros */
 700     if(cmax * (1 << MAX_LPC_SHIFT) < 1.0) {
 701         *shift = 0;
 702         memset(lpc_out, 0, sizeof(int32_t) * order);
 703         return;
 704     }
 705
 706     /* calculate level shift which scales max coeff to available bits */
 707     sh = MAX_LPC_SHIFT;
 708     while((cmax * (1 << sh) > qmax) && (sh > 0)) {
 709         sh--;
 710     }
 711
 712     /* since negative shift values are unsupported in decoder, scale down
 713        coefficients instead */
 714     if(sh == 0 && cmax > qmax) {
 715         double scale = ((double)qmax) / cmax;
 716         for(i=0; i<order; i++) {
 717             lpc_in[i] *= scale;
 718         }
 719     }
 720
 721     /* output quantized coefficients and level shift */
 722     error=0;
 723     for(i=0; i<order; i++) {
 724         error += lpc_in[i] * (1 << sh);
 725         lpc_out[i] = av_clip(lrintf(error), -qmax, qmax);
 726         error -= lpc_out[i];
 727     }
 728     *shift = sh;
 729 }
 730
 731 static int estimate_best_order(double *ref, int max_order)
 732 {
 733     int i, est;
 734
 735     est = 1;
 736     for(i=max_order-1; i>=0; i--) {
 737         if(ref[i] > 0.10) {
 738             est = i+1;
 739             break;
 740         }
 741     }
 742     return est;
 743 }
 744
 745 /**
 746  * Calculate LPC coefficients for multiple orders
 747  */
 748 static int lpc_calc_coefs(FlacEncodeContext *s,
 749                           const int32_t *samples, int blocksize, int max_order,
 750                           int precision, int32_t coefs[][MAX_LPC_ORDER],
 751                           int *shift, int use_lpc, int omethod)
 752 {
 753     double autoc[MAX_LPC_ORDER+1];
 754     double ref[MAX_LPC_ORDER];
 755     double lpc[MAX_LPC_ORDER][MAX_LPC_ORDER];
 756     int i, j, pass;
 757     int opt_order;
 758
 759     assert(max_order >= MIN_LPC_ORDER && max_order <= MAX_LPC_ORDER);
 760
 761     if(use_lpc == 1){
 762         s->dsp.flac_compute_autocorr(samples, blocksize, max_order, autoc);
 763
 764         compute_lpc_coefs(autoc, max_order, lpc, ref);
 765     }else{
 766         LLSModel m[2];
 767         double var[MAX_LPC_ORDER+1], weight;
 768
 769         for(pass=0; pass<use_lpc-1; pass++){
 770             av_init_lls(&m[pass&1], max_order);
 771
 772             weight=0;
 773             for(i=max_order; i<blocksize; i++){
 774                 for(j=0; j<=max_order; j++)
 775                     var[j]= samples[i-j];
 776
 777                 if(pass){
 778                     double eval, inv, rinv;
 779                     eval= av_evaluate_lls(&m[(pass-1)&1], var+1, max_order-1);
 780                     eval= (512>>pass) + fabs(eval - var[0]);
 781                     inv = 1/eval;
 782                     rinv = sqrt(inv);
 783                     for(j=0; j<=max_order; j++)
 784                         var[j] *= rinv;
 785                     weight += inv;
 786                 }else
 787                     weight++;
 788
 789                 av_update_lls(&m[pass&1], var, 1.0);
 790             }
 791             av_solve_lls(&m[pass&1], 0.001, 0);
 792         }
 793
 794         for(i=0; i<max_order; i++){
 795             for(j=0; j<max_order; j++)
 796                 lpc[i][j]= m[(pass-1)&1].coeff[i][j];
 797             ref[i]= sqrt(m[(pass-1)&1].variance[i] / weight) * (blocksize - max_order) / 4000;
 798         }
 799         for(i=max_order-1; i>0; i--)
 800             ref[i] = ref[i-1] - ref[i];
 801     }
 802     opt_order = max_order;
 803
 804     if(omethod == ORDER_METHOD_EST) {
 805         opt_order = estimate_best_order(ref, max_order);
 806         i = opt_order-1;
 807         quantize_lpc_coefs(lpc[i], i+1, precision, coefs[i], &shift[i]);
 808     } else {
 809         for(i=0; i<max_order; i++) {
 810             quantize_lpc_coefs(lpc[i], i+1, precision, coefs[i], &shift[i]);
 811         }
 812     }
 813
 814     return opt_order;
 815 }
 816
 817
 818 static void encode_residual_verbatim(int32_t *res, int32_t *smp, int n)
 819 {
 820     assert(n > 0);
 821     memcpy(res, smp, n * sizeof(int32_t));
 822 }
 823
 824 static void encode_residual_fixed(int32_t *res, const int32_t *smp, int n,
 825                                   int order)
 826 {
 827     int i;
 828
 829     for(i=0; i<order; i++) {
 830         res[i] = smp[i];
 831     }
 832
 833     if(order==0){
 834         for(i=order; i<n; i++)
 835             res[i]= smp[i];
 836     }else if(order==1){
 837         for(i=order; i<n; i++)
 838             res[i]= smp[i] - smp[i-1];
 839     }else if(order==2){
 840         int a = smp[order-1] - smp[order-2];
 841         for(i=order; i<n; i+=2) {
 842             int b = smp[i] - smp[i-1];
 843             res[i]= b - a;
 844             a = smp[i+1] - smp[i];
 845             res[i+1]= a - b;
 846         }
 847     }else if(order==3){
 848         int a = smp[order-1] - smp[order-2];
 849         int c = smp[order-1] - 2*smp[order-2] + smp[order-3];
 850         for(i=order; i<n; i+=2) {
 851             int b = smp[i] - smp[i-1];
 852             int d = b - a;
 853             res[i]= d - c;
 854             a = smp[i+1] - smp[i];
 855             c = a - b;
 856             res[i+1]= c - d;
 857         }
 858     }else{
 859         int a = smp[order-1] - smp[order-2];
 860         int c = smp[order-1] - 2*smp[order-2] + smp[order-3];
 861         int e = smp[order-1] - 3*smp[order-2] + 3*smp[order-3] - smp[order-4];
 862         for(i=order; i<n; i+=2) {
 863             int b = smp[i] - smp[i-1];
 864             int d = b - a;
 865             int f = d - c;
 866             res[i]= f - e;
 867             a = smp[i+1] - smp[i];
 868             c = a - b;
 869             e = c - d;
 870             res[i+1]= e - f;
 871         }
 872     }
 873 }
 874
 875 #define LPC1(x) {\
 876     int c = coefs[(x)-1];\
 877     p0 += c*s;\
 878     s = smp[i-(x)+1];\
 879     p1 += c*s;\
 880 }
 881
 882 static av_always_inline void encode_residual_lpc_unrolled(
 883     int32_t *res, const int32_t *smp, int n,
 884     int order, const int32_t *coefs, int shift, int big)
 885 {
 886     int i;
 887     for(i=order; i<n; i+=2) {
 888         int s = smp[i-order];
 889         int p0 = 0, p1 = 0;
 890         if(big) {
 891             switch(order) {
 892                 case 32: LPC1(32)
 893                 case 31: LPC1(31)
 894                 case 30: LPC1(30)
 895                 case 29: LPC1(29)
 896                 case 28: LPC1(28)
 897                 case 27: LPC1(27)
 898                 case 26: LPC1(26)
 899                 case 25: LPC1(25)
 900                 case 24: LPC1(24)
 901                 case 23: LPC1(23)
 902                 case 22: LPC1(22)
 903                 case 21: LPC1(21)
 904                 case 20: LPC1(20)
 905                 case 19: LPC1(19)
 906                 case 18: LPC1(18)
 907                 case 17: LPC1(17)
 908                 case 16: LPC1(16)
 909                 case 15: LPC1(15)
 910                 case 14: LPC1(14)
 911                 case 13: LPC1(13)
 912                 case 12: LPC1(12)
 913                 case 11: LPC1(11)
 914                 case 10: LPC1(10)
 915                 case  9: LPC1( 9)
 916                          LPC1( 8)
 917                          LPC1( 7)
 918                          LPC1( 6)
 919                          LPC1( 5)
 920                          LPC1( 4)
 921                          LPC1( 3)
 922                          LPC1( 2)
 923                          LPC1( 1)
 924             }
 925         } else {
 926             switch(order) {
 927                 case  8: LPC1( 8)
 928                 case  7: LPC1( 7)
 929                 case  6: LPC1( 6)
 930                 case  5: LPC1( 5)
 931                 case  4: LPC1( 4)
 932                 case  3: LPC1( 3)
 933                 case  2: LPC1( 2)
 934                 case  1: LPC1( 1)
 935             }
 936         }
 937         res[i  ] = smp[i  ] - (p0 >> shift);
 938         res[i+1] = smp[i+1] - (p1 >> shift);
 939     }
 940 }
 941
 942 static void encode_residual_lpc(int32_t *res, const int32_t *smp, int n,
 943                                 int order, const int32_t *coefs, int shift)
 944 {
 945     int i;
 946     for(i=0; i<order; i++) {
 947         res[i] = smp[i];
 948     }
 949 #ifdef CONFIG_SMALL
 950     for(i=order; i<n; i+=2) {
 951         int j;
 952         int s = smp[i];
 953         int p0 = 0, p1 = 0;
 954         for(j=0; j<order; j++) {
 955             int c = coefs[j];
 956             p1 += c*s;
 957             s = smp[i-j-1];
 958             p0 += c*s;
 959         }
 960         res[i  ] = smp[i  ] - (p0 >> shift);
 961         res[i+1] = smp[i+1] - (p1 >> shift);
 962     }
 963 #else
 964     switch(order) {
 965         case  1: encode_residual_lpc_unrolled(res, smp, n, 1, coefs, shift, 0); break;
 966         case  2: encode_residual_lpc_unrolled(res, smp, n, 2, coefs, shift, 0); break;
 967         case  3: encode_residual_lpc_unrolled(res, smp, n, 3, coefs, shift, 0); break;
 968         case  4: encode_residual_lpc_unrolled(res, smp, n, 4, coefs, shift, 0); break;
 969         case  5: encode_residual_lpc_unrolled(res, smp, n, 5, coefs, shift, 0); break;
 970         case  6: encode_residual_lpc_unrolled(res, smp, n, 6, coefs, shift, 0); break;
 971         case  7: encode_residual_lpc_unrolled(res, smp, n, 7, coefs, shift, 0); break;
 972         case  8: encode_residual_lpc_unrolled(res, smp, n, 8, coefs, shift, 0); break;
 973         default: encode_residual_lpc_unrolled(res, smp, n, order, coefs, shift, 1); break;
 974     }
 975 #endif
 976 }
 977
 978 static int encode_residual(FlacEncodeContext *ctx, int ch)
 979 {
 980     int i, n;
 981     int min_order, max_order, opt_order, precision, omethod;
 982     int min_porder, max_porder;
 983     FlacFrame *frame;
 984     FlacSubframe *sub;
 985     int32_t coefs[MAX_LPC_ORDER][MAX_LPC_ORDER];
 986     int shift[MAX_LPC_ORDER];
 987     int32_t *res, *smp;
 988
 989     frame = &ctx->frame;
 990     sub = &frame->subframes[ch];
 991     res = sub->residual;
 992     smp = sub->samples;
 993     n = frame->blocksize;
 994
 995     /* CONSTANT */
 996     for(i=1; i<n; i++) {
 997         if(smp[i] != smp[0]) break;
 998     }
 999     if(i == n) {
1000         sub->type = sub->type_code = FLAC_SUBFRAME_CONSTANT;
1001         res[0] = smp[0];
1002         return sub->obits;
1003     }
1004
1005     /* VERBATIM */
1006     if(n < 5) {
1007         sub->type = sub->type_code = FLAC_SUBFRAME_VERBATIM;
1008         encode_residual_verbatim(res, smp, n);
1009         return sub->obits * n;
1010     }
1011
1012     min_order = ctx->options.min_prediction_order;
1013     max_order = ctx->options.max_prediction_order;
1014     min_porder = ctx->options.min_partition_order;
1015     max_porder = ctx->options.max_partition_order;
1016     precision = ctx->options.lpc_coeff_precision;
1017     omethod = ctx->options.prediction_order_method;
1018
1019     /* FIXED */
1020     if(!ctx->options.use_lpc || max_order == 0 || (n <= max_order)) {
1021         uint32_t bits[MAX_FIXED_ORDER+1];
1022         if(max_order > MAX_FIXED_ORDER) max_order = MAX_FIXED_ORDER;
1023         opt_order = 0;
1024         bits[0] = UINT32_MAX;
1025         for(i=min_order; i<=max_order; i++) {
1026             encode_residual_fixed(res, smp, n, i);
1027             bits[i] = calc_rice_params_fixed(&sub->rc, min_porder, max_porder, res,
1028                                              n, i, sub->obits);
1029             if(bits[i] < bits[opt_order]) {
1030                 opt_order = i;
1031             }
1032         }
1033         sub->order = opt_order;
1034         sub->type = FLAC_SUBFRAME_FIXED;
1035         sub->type_code = sub->type | sub->order;
1036         if(sub->order != max_order) {
1037             encode_residual_fixed(res, smp, n, sub->order);
1038             return calc_rice_params_fixed(&sub->rc, min_porder, max_porder, res, n,
1039                                           sub->order, sub->obits);
1040         }
1041         return bits[sub->order];
1042     }
1043
1044     /* LPC */
1045     opt_order = lpc_calc_coefs(ctx, smp, n, max_order, precision, coefs, shift, ctx->options.use_lpc, omethod);
1046
1047     if(omethod == ORDER_METHOD_2LEVEL ||
1048        omethod == ORDER_METHOD_4LEVEL ||
1049        omethod == ORDER_METHOD_8LEVEL) {
1050         int levels = 1 << omethod;
1051         uint32_t bits[levels];
1052         int order;
1053         int opt_index = levels-1;
1054         opt_order = max_order-1;
1055         bits[opt_index] = UINT32_MAX;
1056         for(i=levels-1; i>=0; i--) {
1057             order = min_order + (((max_order-min_order+1) * (i+1)) / levels)-1;
1058             if(order < 0) order = 0;
1059             encode_residual_lpc(res, smp, n, order+1, coefs[order], shift[order]);
1060             bits[i] = calc_rice_params_lpc(&sub->rc, min_porder, max_porder,
1061                                            res, n, order+1, sub->obits, precision);
1062             if(bits[i] < bits[opt_index]) {
1063                 opt_index = i;
1064                 opt_order = order;
1065             }
1066         }
1067         opt_order++;
1068     } else if(omethod == ORDER_METHOD_SEARCH) {
1069         // brute-force optimal order search
1070         uint32_t bits[MAX_LPC_ORDER];
1071         opt_order = 0;
1072         bits[0] = UINT32_MAX;
1073         for(i=min_order-1; i<max_order; i++) {
1074             encode_residual_lpc(res, smp, n, i+1, coefs[i], shift[i]);
1075             bits[i] = calc_rice_params_lpc(&sub->rc, min_porder, max_porder,
1076                                            res, n, i+1, sub->obits, precision);
1077             if(bits[i] < bits[opt_order]) {
1078                 opt_order = i;
1079             }
1080         }
1081         opt_order++;
1082     } else if(omethod == ORDER_METHOD_LOG) {
1083         uint32_t bits[MAX_LPC_ORDER];
1084         int step;
1085
1086         opt_order= min_order - 1 + (max_order-min_order)/3;
1087         memset(bits, -1, sizeof(bits));
1088
1089         for(step=16 ;step; step>>=1){
1090             int last= opt_order;
1091             for(i=last-step; i<=last+step; i+= step){
1092                 if(i<min_order-1 || i>=max_order || bits[i] < UINT32_MAX)
1093                     continue;
1094                 encode_residual_lpc(res, smp, n, i+1, coefs[i], shift[i]);
1095                 bits[i] = calc_rice_params_lpc(&sub->rc, min_porder, max_porder,
1096                                             res, n, i+1, sub->obits, precision);
1097                 if(bits[i] < bits[opt_order])
1098                     opt_order= i;
1099             }
1100         }
1101         opt_order++;
1102     }
1103
1104     sub->order = opt_order;
1105     sub->type = FLAC_SUBFRAME_LPC;
1106     sub->type_code = sub->type | (sub->order-1);
1107     sub->shift = shift[sub->order-1];
1108     for(i=0; i<sub->order; i++) {
1109         sub->coefs[i] = coefs[sub->order-1][i];
1110     }
1111     encode_residual_lpc(res, smp, n, sub->order, sub->coefs, sub->shift);
1112     return calc_rice_params_lpc(&sub->rc, min_porder, max_porder, res, n, sub->order,
1113                                 sub->obits, precision);
1114 }
1115
1116 static int encode_residual_v(FlacEncodeContext *ctx, int ch)
1117 {
1118     int i, n;
1119     FlacFrame *frame;
1120     FlacSubframe *sub;
1121     int32_t *res, *smp;
1122
1123     frame = &ctx->frame;
1124     sub = &frame->subframes[ch];
1125     res = sub->residual;
1126     smp = sub->samples;
1127     n = frame->blocksize;
1128
1129     /* CONSTANT */
1130     for(i=1; i<n; i++) {
1131         if(smp[i] != smp[0]) break;
1132     }
1133     if(i == n) {
1134         sub->type = sub->type_code = FLAC_SUBFRAME_CONSTANT;
1135         res[0] = smp[0];
1136         return sub->obits;
1137     }
1138
1139     /* VERBATIM */
1140     sub->type = sub->type_code = FLAC_SUBFRAME_VERBATIM;
1141     encode_residual_verbatim(res, smp, n);
1142     return sub->obits * n;
1143 }
1144
1145 static int estimate_stereo_mode(int32_t *left_ch, int32_t *right_ch, int n)
1146 {
1147     int i, best;
1148     int32_t lt, rt;
1149     uint64_t sum[4];
1150     uint64_t score[4];
1151     int k;
1152
1153     /* calculate sum of 2nd order residual for each channel */
1154     sum[0] = sum[1] = sum[2] = sum[3] = 0;
1155     for(i=2; i<n; i++) {
1156         lt = left_ch[i] - 2*left_ch[i-1] + left_ch[i-2];
1157         rt = right_ch[i] - 2*right_ch[i-1] + right_ch[i-2];
1158         sum[2] += FFABS((lt + rt) >> 1);
1159         sum[3] += FFABS(lt - rt);
1160         sum[0] += FFABS(lt);
1161         sum[1] += FFABS(rt);
1162     }
1163     /* estimate bit counts */
1164     for(i=0; i<4; i++) {
1165         k = find_optimal_param(2*sum[i], n);
1166         sum[i] = rice_encode_count(2*sum[i], n, k);
1167     }
1168
1169     /* calculate score for each mode */
1170     score[0] = sum[0] + sum[1];
1171     score[1] = sum[0] + sum[3];
1172     score[2] = sum[1] + sum[3];
1173     score[3] = sum[2] + sum[3];
1174
1175     /* return mode with lowest score */
1176     best = 0;
1177     for(i=1; i<4; i++) {
1178         if(score[i] < score[best]) {
1179             best = i;
1180         }
1181     }
1182     if(best == 0) {
1183         return FLAC_CHMODE_LEFT_RIGHT;
1184     } else if(best == 1) {
1185         return FLAC_CHMODE_LEFT_SIDE;
1186     } else if(best == 2) {
1187         return FLAC_CHMODE_RIGHT_SIDE;
1188     } else {
1189         return FLAC_CHMODE_MID_SIDE;
1190     }
1191 }
1192
1193 /**
1194  * Perform stereo channel decorrelation
1195  */
1196 static void channel_decorrelation(FlacEncodeContext *ctx)
1197 {
1198     FlacFrame *frame;
1199     int32_t *left, *right;
1200     int i, n;
1201
1202     frame = &ctx->frame;
1203     n = frame->blocksize;
1204     left  = frame->subframes[0].samples;
1205     right = frame->subframes[1].samples;
1206
1207     if(ctx->channels != 2) {
1208         frame->ch_mode = FLAC_CHMODE_NOT_STEREO;
1209         return;
1210     }
1211
1212     frame->ch_mode = estimate_stereo_mode(left, right, n);
1213
1214     /* perform decorrelation and adjust bits-per-sample */
1215     if(frame->ch_mode == FLAC_CHMODE_LEFT_RIGHT) {
1216         return;
1217     }
1218     if(frame->ch_mode == FLAC_CHMODE_MID_SIDE) {
1219         int32_t tmp;
1220         for(i=0; i<n; i++) {
1221             tmp = left[i];
1222             left[i] = (tmp + right[i]) >> 1;
1223             right[i] = tmp - right[i];
1224         }
1225         frame->subframes[1].obits++;
1226     } else if(frame->ch_mode == FLAC_CHMODE_LEFT_SIDE) {
1227         for(i=0; i<n; i++) {
1228             right[i] = left[i] - right[i];
1229         }
1230         frame->subframes[1].obits++;
1231     } else {
1232         for(i=0; i<n; i++) {
1233             left[i] -= right[i];
1234         }
1235         frame->subframes[0].obits++;
1236     }
1237 }
1238
1239 static void put_sbits(PutBitContext *pb, int bits, int32_t val)
1240 {
1241     assert(bits >= 0 && bits <= 31);
1242
1243     put_bits(pb, bits, val & ((1<<bits)-1));
1244 }
1245
1246 static void write_utf8(PutBitContext *pb, uint32_t val)
1247 {
1248     uint8_t tmp;
1249     PUT_UTF8(val, tmp, put_bits(pb, 8, tmp);)
1250 }
1251
1252 static void output_frame_header(FlacEncodeContext *s)
1253 {
1254     FlacFrame *frame;
1255     int crc;
1256
1257     frame = &s->frame;
1258
1259     put_bits(&s->pb, 16, 0xFFF8);
1260     put_bits(&s->pb, 4, frame->bs_code[0]);
1261     put_bits(&s->pb, 4, s->sr_code[0]);
1262     if(frame->ch_mode == FLAC_CHMODE_NOT_STEREO) {
1263         put_bits(&s->pb, 4, s->ch_code);
1264     } else {
1265         put_bits(&s->pb, 4, frame->ch_mode);
1266     }
1267     put_bits(&s->pb, 3, 4); /* bits-per-sample code */
1268     put_bits(&s->pb, 1, 0);
1269     write_utf8(&s->pb, s->frame_count);
1270     if(frame->bs_code[0] == 6) {
1271         put_bits(&s->pb, 8, frame->bs_code[1]);
1272     } else if(frame->bs_code[0] == 7) {
1273         put_bits(&s->pb, 16, frame->bs_code[1]);
1274     }
1275     if(s->sr_code[0] == 12) {
1276         put_bits(&s->pb, 8, s->sr_code[1]);
1277     } else if(s->sr_code[0] > 12) {
1278         put_bits(&s->pb, 16, s->sr_code[1]);
1279     }
1280     flush_put_bits(&s->pb);
1281     crc = av_crc(av_crc_get_table(AV_CRC_8_ATM), 0,
1282                  s->pb.buf, put_bits_count(&s->pb)>>3);
1283     put_bits(&s->pb, 8, crc);
1284 }
1285
1286 static void output_subframe_constant(FlacEncodeContext *s, int ch)
1287 {
1288     FlacSubframe *sub;
1289     int32_t res;
1290
1291     sub = &s->frame.subframes[ch];
1292     res = sub->residual[0];
1293     put_sbits(&s->pb, sub->obits, res);
1294 }
1295
1296 static void output_subframe_verbatim(FlacEncodeContext *s, int ch)
1297 {
1298     int i;
1299     FlacFrame *frame;
1300     FlacSubframe *sub;
1301     int32_t res;
1302
1303     frame = &s->frame;
1304     sub = &frame->subframes[ch];
1305
1306     for(i=0; i<frame->blocksize; i++) {
1307         res = sub->residual[i];
1308         put_sbits(&s->pb, sub->obits, res);
1309     }
1310 }
1311
1312 static void output_residual(FlacEncodeContext *ctx, int ch)
1313 {
1314     int i, j, p, n, parts;
1315     int k, porder, psize, res_cnt;
1316     FlacFrame *frame;
1317     FlacSubframe *sub;
1318     int32_t *res;
1319
1320     frame = &ctx->frame;
1321     sub = &frame->subframes[ch];
1322     res = sub->residual;
1323     n = frame->blocksize;
1324
1325     /* rice-encoded block */
1326     put_bits(&ctx->pb, 2, 0);
1327
1328     /* partition order */
1329     porder = sub->rc.porder;
1330     psize = n >> porder;
1331     parts = (1 << porder);
1332     put_bits(&ctx->pb, 4, porder);
1333     res_cnt = psize - sub->order;
1334
1335     /* residual */
1336     j = sub->order;
1337     for(p=0; p<parts; p++) {
1338         k = sub->rc.params[p];
1339         put_bits(&ctx->pb, 4, k);
1340         if(p == 1) res_cnt = psize;
1341         for(i=0; i<res_cnt && j<n; i++, j++) {
1342             set_sr_golomb_flac(&ctx->pb, res[j], k, INT32_MAX, 0);
1343         }
1344     }
1345 }
1346
1347 static void output_subframe_fixed(FlacEncodeContext *ctx, int ch)
1348 {
1349     int i;
1350     FlacFrame *frame;
1351     FlacSubframe *sub;
1352
1353     frame = &ctx->frame;
1354     sub = &frame->subframes[ch];
1355
1356     /* warm-up samples */
1357     for(i=0; i<sub->order; i++) {
1358         put_sbits(&ctx->pb, sub->obits, sub->residual[i]);
1359     }
1360
1361     /* residual */
1362     output_residual(ctx, ch);
1363 }
1364
1365 static void output_subframe_lpc(FlacEncodeContext *ctx, int ch)
1366 {
1367     int i, cbits;
1368     FlacFrame *frame;
1369     FlacSubframe *sub;
1370
1371     frame = &ctx->frame;
1372     sub = &frame->subframes[ch];
1373
1374     /* warm-up samples */
1375     for(i=0; i<sub->order; i++) {
1376         put_sbits(&ctx->pb, sub->obits, sub->residual[i]);
1377     }
1378
1379     /* LPC coefficients */
1380     cbits = ctx->options.lpc_coeff_precision;
1381     put_bits(&ctx->pb, 4, cbits-1);
1382     put_sbits(&ctx->pb, 5, sub->shift);
1383     for(i=0; i<sub->order; i++) {
1384         put_sbits(&ctx->pb, cbits, sub->coefs[i]);
1385     }
1386
1387     /* residual */
1388     output_residual(ctx, ch);
1389 }
1390
1391 static void output_subframes(FlacEncodeContext *s)
1392 {
1393     FlacFrame *frame;
1394     FlacSubframe *sub;
1395     int ch;
1396
1397     frame = &s->frame;
1398
1399     for(ch=0; ch<s->channels; ch++) {
1400         sub = &frame->subframes[ch];
1401
1402         /* subframe header */
1403         put_bits(&s->pb, 1, 0);
1404         put_bits(&s->pb, 6, sub->type_code);
1405         put_bits(&s->pb, 1, 0); /* no wasted bits */
1406
1407         /* subframe */
1408         if(sub->type == FLAC_SUBFRAME_CONSTANT) {
1409             output_subframe_constant(s, ch);
1410         } else if(sub->type == FLAC_SUBFRAME_VERBATIM) {
1411             output_subframe_verbatim(s, ch);
1412         } else if(sub->type == FLAC_SUBFRAME_FIXED) {
1413             output_subframe_fixed(s, ch);
1414         } else if(sub->type == FLAC_SUBFRAME_LPC) {
1415             output_subframe_lpc(s, ch);
1416         }
1417     }
1418 }
1419
1420 static void output_frame_footer(FlacEncodeContext *s)
1421 {
1422     int crc;
1423     flush_put_bits(&s->pb);
1424     crc = bswap_16(av_crc(av_crc_get_table(AV_CRC_16_ANSI), 0,
1425                           s->pb.buf, put_bits_count(&s->pb)>>3));
1426     put_bits(&s->pb, 16, crc);
1427     flush_put_bits(&s->pb);
1428 }
1429
1430 static int flac_encode_frame(AVCodecContext *avctx, uint8_t *frame,
1431                              int buf_size, void *data)
1432 {
1433     int ch;
1434     FlacEncodeContext *s;
1435     int16_t *samples = data;
1436     int out_bytes;
1437
1438     s = avctx->priv_data;
1439
1440     init_frame(s);
1441
1442     copy_samples(s, samples);
1443
1444     channel_decorrelation(s);
1445
1446     for(ch=0; ch<s->channels; ch++) {
1447         encode_residual(s, ch);
1448     }
1449     init_put_bits(&s->pb, frame, buf_size);
1450     output_frame_header(s);
1451     output_subframes(s);
1452     output_frame_footer(s);
1453     out_bytes = put_bits_count(&s->pb) >> 3;
1454
1455     if(out_bytes > s->max_framesize || out_bytes >= buf_size) {
1456         /* frame too large. use verbatim mode */
1457         for(ch=0; ch<s->channels; ch++) {
1458             encode_residual_v(s, ch);
1459         }
1460         init_put_bits(&s->pb, frame, buf_size);
1461         output_frame_header(s);
1462         output_subframes(s);
1463         output_frame_footer(s);
1464         out_bytes = put_bits_count(&s->pb) >> 3;
1465
1466         if(out_bytes > s->max_framesize || out_bytes >= buf_size) {
1467             /* still too large. must be an error. */
1468             av_log(avctx, AV_LOG_ERROR, "error encoding frame\n");
1469             return -1;
1470         }
1471     }
1472
1473     s->frame_count++;
1474     return out_bytes;
1475 }
1476
1477 static av_cold int flac_encode_close(AVCodecContext *avctx)
1478 {
1479     av_freep(&avctx->extradata);
1480     avctx->extradata_size = 0;
1481     av_freep(&avctx->coded_frame);
1482     return 0;
1483 }
1484
1485 AVCodec flac_encoder = {
1486     "flac",
1487     CODEC_TYPE_AUDIO,
1488     CODEC_ID_FLAC,
1489     sizeof(FlacEncodeContext),
1490     flac_encode_init,
1491     flac_encode_frame,
1492     flac_encode_close,
1493     NULL,
1494     .capabilities = CODEC_CAP_SMALL_LAST_FRAME,
1495     .long_name = "FLAC (Free Lossless Audio Codec)",
1496 };