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

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