d1206dba1b40befde425b4a86d901d8d6a8507cc
[flac.git] / src / libFLAC / encoder.c
1 /* libFLAC - Free Lossless Audio Coder library
2  * Copyright (C) 2000,2001  Josh Coalson
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA  02111-1307, USA.
18  */
19
20 #include <assert.h>
21 #include <stdio.h>
22 #include <stdlib.h> /* for malloc() */
23 #include <string.h> /* for memcpy() */
24 #include "FLAC/encoder.h"
25 #include "private/bitbuffer.h"
26 #include "private/encoder_framing.h"
27 #include "private/fixed.h"
28 #include "private/lpc.h"
29 #include "private/md5.h"
30
31 #ifdef min
32 #undef min
33 #endif
34 #define min(x,y) ((x)<(y)?(x):(y))
35
36 #ifdef max
37 #undef max
38 #endif
39 #define max(x,y) ((x)>(y)?(x):(y))
40
41 typedef struct FLAC__EncoderPrivate {
42         unsigned input_capacity;                    /* current size (in samples) of the signal and residual buffers */
43         int32 *integer_signal[FLAC__MAX_CHANNELS];  /* the integer version of the input signal */
44         int32 *integer_signal_mid_side[2];          /* the integer version of the mid-side input signal (stereo only) */
45         real *real_signal[FLAC__MAX_CHANNELS];      /* the floating-point version of the input signal */
46         real *real_signal_mid_side[2];              /* the floating-point version of the mid-side input signal (stereo only) */
47         int32 *residual[2];                         /* where the candidate and best subframe residual signals will be stored */
48         uint32 *abs_residual;                       /* workspace where the abs(candidate residual) is stored */
49         unsigned best_residual;                     /* index into the above */
50         FLAC__BitBuffer frame;                      /* the current frame being worked on */
51         FLAC__BitBuffer frame_mid_side;             /* special parallel workspace for the mid-side coded version of the current frame */
52         FLAC__BitBuffer frame_left_side;            /* special parallel workspace for the left-side coded version of the current frame */
53         FLAC__BitBuffer frame_right_side;           /* special parallel workspace for the right-side coded version of the current frame */
54         FLAC__Subframe best_subframe, candidate_subframe;
55         bool current_frame_can_do_mid_side;         /* encoder sets this false when any given sample of a frame's side channel exceeds 16 bits */
56         FLAC__StreamMetaData metadata;
57         unsigned current_sample_number;
58         unsigned current_frame_number;
59         struct MD5Context md5context;
60         FLAC__EncoderWriteStatus (*write_callback)(const FLAC__Encoder *encoder, const byte buffer[], unsigned bytes, unsigned samples, unsigned current_frame, void *client_data);
61         void (*metadata_callback)(const FLAC__Encoder *encoder, const FLAC__StreamMetaData *metadata, void *client_data);
62         void *client_data;
63 } FLAC__EncoderPrivate;
64
65 static bool encoder_resize_buffers_(FLAC__Encoder *encoder, unsigned new_size);
66 static bool encoder_process_frame_(FLAC__Encoder *encoder, bool is_last_frame);
67 static bool encoder_process_subframes_(FLAC__Encoder *encoder, bool is_last_frame, bool verbatim_only, const FLAC__FrameHeader *frame_header, unsigned channels, const int32 *integer_signal[], const real *real_signal[], FLAC__BitBuffer *bitbuffer);
68 static unsigned encoder_evaluate_constant_subframe_(const int32 signal, unsigned bits_per_sample, FLAC__Subframe *subframe);
69 static unsigned encoder_evaluate_fixed_subframe_(const int32 signal[], int32 residual[], uint32 abs_residual[], unsigned blocksize, unsigned bits_per_sample, unsigned order, unsigned rice_parameter, unsigned max_partition_order, FLAC__Subframe *subframe);
70 static unsigned encoder_evaluate_lpc_subframe_(const int32 signal[], int32 residual[], uint32 abs_residual[], const real lp_coeff[], unsigned blocksize, unsigned bits_per_sample, unsigned order, unsigned qlp_coeff_precision, unsigned rice_parameter, unsigned max_partition_order, FLAC__Subframe *subframe);
71 static unsigned encoder_evaluate_verbatim_subframe_(unsigned blocksize, unsigned bits_per_sample, FLAC__Subframe *subframe);
72 static unsigned encoder_find_best_partition_order_(const int32 residual[], uint32 abs_residual[], unsigned residual_samples, unsigned predictor_order, unsigned rice_parameter, unsigned max_partition_order, unsigned *best_partition_order, unsigned best_parameters[]);
73 static void encoder_promote_candidate_subframe_(FLAC__Encoder *encoder);
74 static bool encoder_set_partitioned_rice_(const uint32 abs_residual[], const unsigned residual_samples, const unsigned predictor_order, const unsigned rice_parameter, const unsigned partition_order, unsigned parameters[], unsigned *bits);
75
76 const char *FLAC__EncoderWriteStatusString[] = {
77         "FLAC__ENCODER_WRITE_OK",
78         "FLAC__ENCODER_WRITE_FATAL_ERROR"
79 };
80
81 const char *FLAC__EncoderStateString[] = {
82         "FLAC__ENCODER_OK",
83         "FLAC__ENCODER_UNINITIALIZED",
84         "FLAC__ENCODER_INVALID_NUMBER_OF_CHANNELS",
85         "FLAC__ENCODER_INVALID_BITS_PER_SAMPLE",
86         "FLAC__ENCODER_INVALID_SAMPLE_RATE",
87         "FLAC__ENCODER_INVALID_BLOCK_SIZE",
88         "FLAC__ENCODER_INVALID_QLP_COEFF_PRECISION",
89         "FLAC__ENCODER_MID_SIDE_CHANNELS_MISMATCH",
90         "FLAC__ENCODER_MID_SIDE_SAMPLE_SIZE_MISMATCH",
91         "FLAC__ENCODER_ILLEGAL_MID_SIDE_FORCE",
92         "FLAC__ENCODER_BLOCK_SIZE_TOO_SMALL_FOR_LPC_ORDER",
93         "FLAC__ENCODER_NOT_STREAMABLE",
94         "FLAC__ENCODER_FRAMING_ERROR",
95         "FLAC__ENCODER_FATAL_ERROR_WHILE_ENCODING",
96         "FLAC__ENCODER_FATAL_ERROR_WHILE_WRITING",
97         "FLAC__ENCODER_MEMORY_ALLOCATION_ERROR"
98 };
99
100
101 bool encoder_resize_buffers_(FLAC__Encoder *encoder, unsigned new_size)
102 {
103         bool ok;
104         unsigned i;
105         int32 *previous_is, *current_is;
106         real *previous_rs, *current_rs;
107         int32 *residual;
108         uint32 *abs_residual;
109
110         assert(new_size > 0);
111         assert(encoder->state == FLAC__ENCODER_OK);
112         assert(encoder->guts->current_sample_number == 0);
113
114         /* To avoid excessive malloc'ing, we only grow the buffer; no shrinking. */
115         if(new_size <= encoder->guts->input_capacity)
116                 return true;
117
118         ok = 1;
119         if(ok) {
120                 for(i = 0; ok && i < encoder->channels; i++) {
121                         /* integer version of the signal */
122                         previous_is = encoder->guts->integer_signal[i];
123                         current_is = (int32*)malloc(sizeof(int32) * new_size);
124                         if(0 == current_is) {
125                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
126                                 ok = 0;
127                         }
128                         else {
129                                 encoder->guts->integer_signal[i] = current_is;
130                                 if(previous_is != 0)
131                                         free(previous_is);
132                         }
133                         /* real version of the signal */
134                         previous_rs = encoder->guts->real_signal[i];
135                         current_rs = (real*)malloc(sizeof(real) * new_size);
136                         if(0 == current_rs) {
137                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
138                                 ok = 0;
139                         }
140                         else {
141                                 encoder->guts->real_signal[i] = current_rs;
142                                 if(previous_rs != 0)
143                                         free(previous_rs);
144                         }
145                 }
146         }
147         if(ok) {
148                 for(i = 0; ok && i < 2; i++) {
149                         /* integer version of the signal */
150                         previous_is = encoder->guts->integer_signal_mid_side[i];
151                         current_is = (int32*)malloc(sizeof(int32) * new_size);
152                         if(0 == current_is) {
153                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
154                                 ok = 0;
155                         }
156                         else {
157                                 encoder->guts->integer_signal_mid_side[i] = current_is;
158                                 if(previous_is != 0)
159                                         free(previous_is);
160                         }
161                         /* real version of the signal */
162                         previous_rs = encoder->guts->real_signal_mid_side[i];
163                         current_rs = (real*)malloc(sizeof(real) * new_size);
164                         if(0 == current_rs) {
165                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
166                                 ok = 0;
167                         }
168                         else {
169                                 encoder->guts->real_signal_mid_side[i] = current_rs;
170                                 if(previous_rs != 0)
171                                         free(previous_rs);
172                         }
173                 }
174         }
175         if(ok) {
176                 for(i = 0; i < 2; i++) {
177                         residual = (int32*)malloc(sizeof(int32) * new_size);
178                         if(0 == residual) {
179                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
180                                 ok = 0;
181                         }
182                         else {
183                                 if(encoder->guts->residual[i] != 0)
184                                         free(encoder->guts->residual[i]);
185                                 encoder->guts->residual[i] = residual;
186                         }
187                 }
188                 abs_residual = (uint32*)malloc(sizeof(uint32) * new_size);
189                 if(0 == residual) {
190                         encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
191                         ok = 0;
192                 }
193                 else {
194                         if(encoder->guts->abs_residual != 0)
195                                 free(encoder->guts->abs_residual);
196                         encoder->guts->abs_residual = abs_residual;
197                 }
198         }
199         if(ok)
200                 encoder->guts->input_capacity = new_size;
201
202         return ok;
203 }
204
205 FLAC__Encoder *FLAC__encoder_get_new_instance()
206 {
207         FLAC__Encoder *encoder = (FLAC__Encoder*)malloc(sizeof(FLAC__Encoder));
208         if(encoder != 0) {
209                 encoder->state = FLAC__ENCODER_UNINITIALIZED;
210                 encoder->guts = 0;
211         }
212         return encoder;
213 }
214
215 void FLAC__encoder_free_instance(FLAC__Encoder *encoder)
216 {
217         assert(encoder != 0);
218         free(encoder);
219 }
220
221 FLAC__EncoderState FLAC__encoder_init(FLAC__Encoder *encoder, FLAC__EncoderWriteStatus (*write_callback)(const FLAC__Encoder *encoder, const byte buffer[], unsigned bytes, unsigned samples, unsigned current_frame, void *client_data), void (*metadata_callback)(const FLAC__Encoder *encoder, const FLAC__StreamMetaData *metadata, void *client_data), void *client_data)
222 {
223         unsigned i;
224
225         assert(sizeof(int) >= 4); /* we want to die right away if this is not true */
226         assert(encoder != 0);
227         assert(write_callback != 0);
228         assert(metadata_callback != 0);
229         assert(encoder->state == FLAC__ENCODER_UNINITIALIZED);
230         assert(encoder->guts == 0);
231
232         encoder->state = FLAC__ENCODER_OK;
233
234         if(encoder->channels == 0 || encoder->channels > FLAC__MAX_CHANNELS)
235                 return encoder->state = FLAC__ENCODER_INVALID_NUMBER_OF_CHANNELS;
236
237         if(encoder->do_mid_side_stereo && encoder->channels != 2)
238                 return encoder->state = FLAC__ENCODER_MID_SIDE_CHANNELS_MISMATCH;
239
240         if(encoder->do_mid_side_stereo && encoder->bits_per_sample > 16)
241                 return encoder->state = FLAC__ENCODER_MID_SIDE_SAMPLE_SIZE_MISMATCH;
242
243         if(encoder->force_mid_side_stereo && !encoder->do_mid_side_stereo)
244                 return encoder->state = FLAC__ENCODER_ILLEGAL_MID_SIDE_FORCE;
245
246         if(encoder->bits_per_sample == 0 || encoder->bits_per_sample > FLAC__MAX_BITS_PER_SAMPLE)
247                 return encoder->state = FLAC__ENCODER_INVALID_BITS_PER_SAMPLE;
248
249         if(encoder->sample_rate == 0 || encoder->sample_rate > FLAC__MAX_SAMPLE_RATE)
250                 return encoder->state = FLAC__ENCODER_INVALID_SAMPLE_RATE;
251
252         if(encoder->blocksize < FLAC__MIN_BLOCK_SIZE || encoder->blocksize > FLAC__MAX_BLOCK_SIZE)
253                 return encoder->state = FLAC__ENCODER_INVALID_BLOCK_SIZE;
254
255         if(encoder->blocksize < encoder->max_lpc_order)
256                 return encoder->state = FLAC__ENCODER_BLOCK_SIZE_TOO_SMALL_FOR_LPC_ORDER;
257
258         if(encoder->qlp_coeff_precision == 0) {
259                 if(encoder->bits_per_sample < 16) {
260                         /* @@@ need some data about how to set this here w.r.t. blocksize and sample rate */
261                         /* @@@ until then we'll make a guess */
262                         encoder->qlp_coeff_precision = max(5, 2 + encoder->bits_per_sample / 2);
263                 }
264                 else if(encoder->bits_per_sample == 16) {
265                         if(encoder->blocksize <= 192)
266                                 encoder->qlp_coeff_precision = 7;
267                         else if(encoder->blocksize <= 384)
268                                 encoder->qlp_coeff_precision = 8;
269                         else if(encoder->blocksize <= 576)
270                                 encoder->qlp_coeff_precision = 9;
271                         else if(encoder->blocksize <= 1152)
272                                 encoder->qlp_coeff_precision = 10;
273                         else if(encoder->blocksize <= 2304)
274                                 encoder->qlp_coeff_precision = 11;
275                         else if(encoder->blocksize <= 4608)
276                                 encoder->qlp_coeff_precision = 12;
277                         else
278                                 encoder->qlp_coeff_precision = 13;
279                 }
280                 else {
281                         encoder->qlp_coeff_precision = min(13, 8*sizeof(int32) - encoder->bits_per_sample - 1);
282                 }
283         }
284         else if(encoder->qlp_coeff_precision < FLAC__MIN_QLP_COEFF_PRECISION || encoder->qlp_coeff_precision + encoder->bits_per_sample >= 8*sizeof(uint32))
285                 return encoder->state = FLAC__ENCODER_INVALID_QLP_COEFF_PRECISION;
286
287         if(encoder->streamable_subset) {
288                 if(encoder->bits_per_sample != 8 && encoder->bits_per_sample != 12 && encoder->bits_per_sample != 16 && encoder->bits_per_sample != 20 && encoder->bits_per_sample != 24)
289                         return encoder->state = FLAC__ENCODER_NOT_STREAMABLE;
290                 if(encoder->sample_rate > 655350)
291                         return encoder->state = FLAC__ENCODER_NOT_STREAMABLE;
292         }
293
294         if(encoder->rice_optimization_level >= (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_ORDER_LEN))
295                 encoder->rice_optimization_level = (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_ORDER_LEN) - 1;
296
297         encoder->guts = (FLAC__EncoderPrivate*)malloc(sizeof(FLAC__EncoderPrivate));
298         if(encoder->guts == 0)
299                 return encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
300
301         encoder->guts->input_capacity = 0;
302         for(i = 0; i < encoder->channels; i++) {
303                 encoder->guts->integer_signal[i] = 0;
304                 encoder->guts->real_signal[i] = 0;
305         }
306         for(i = 0; i < 2; i++) {
307                 encoder->guts->integer_signal_mid_side[i] = 0;
308                 encoder->guts->real_signal_mid_side[i] = 0;
309         }
310         encoder->guts->residual[0] = 0;
311         encoder->guts->residual[1] = 0;
312         encoder->guts->abs_residual = 0;
313         encoder->guts->best_residual = 0;
314         encoder->guts->current_frame_can_do_mid_side = true;
315         encoder->guts->current_sample_number = 0;
316         encoder->guts->current_frame_number = 0;
317
318         if(!encoder_resize_buffers_(encoder, encoder->blocksize)) {
319                 /* the above function sets the state for us in case of an error */
320                 return encoder->state;
321         }
322         FLAC__bitbuffer_init(&encoder->guts->frame);
323         encoder->guts->write_callback = write_callback;
324         encoder->guts->metadata_callback = metadata_callback;
325         encoder->guts->client_data = client_data;
326
327         /*
328          * write the stream header
329          */
330         if(!FLAC__bitbuffer_clear(&encoder->guts->frame))
331                 return encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
332
333         if(!FLAC__bitbuffer_write_raw_uint32(&encoder->guts->frame, FLAC__STREAM_SYNC, FLAC__STREAM_SYNC_LEN))
334                 return encoder->state = FLAC__ENCODER_FRAMING_ERROR;
335
336         encoder->guts->metadata.type = FLAC__METADATA_TYPE_ENCODING;
337         encoder->guts->metadata.is_last = true;
338         encoder->guts->metadata.length = FLAC__STREAM_METADATA_ENCODING_LENGTH;
339         encoder->guts->metadata.data.encoding.min_blocksize = encoder->blocksize; /* this encoder uses the same blocksize for the whole stream */
340         encoder->guts->metadata.data.encoding.max_blocksize = encoder->blocksize;
341         encoder->guts->metadata.data.encoding.min_framesize = 0; /* we don't know this yet; have to fill it in later */
342         encoder->guts->metadata.data.encoding.max_framesize = 0; /* we don't know this yet; have to fill it in later */
343         encoder->guts->metadata.data.encoding.sample_rate = encoder->sample_rate;
344         encoder->guts->metadata.data.encoding.channels = encoder->channels;
345         encoder->guts->metadata.data.encoding.bits_per_sample = encoder->bits_per_sample;
346         encoder->guts->metadata.data.encoding.total_samples = encoder->total_samples_estimate; /* we will replace this later with the real total */
347         memset(encoder->guts->metadata.data.encoding.md5sum, 0, 16); /* we don't know this yet; have to fill it in later */
348         MD5Init(&encoder->guts->md5context);
349         if(!FLAC__add_metadata_block(&encoder->guts->metadata, &encoder->guts->frame))
350                 return encoder->state = FLAC__ENCODER_FRAMING_ERROR;
351
352         assert(encoder->guts->frame.bits == 0); /* assert that we're byte-aligned before writing */
353         assert(encoder->guts->frame.total_consumed_bits == 0); /* assert that no reading of the buffer was done */
354         if(encoder->guts->write_callback(encoder, encoder->guts->frame.buffer, encoder->guts->frame.bytes, 0, encoder->guts->current_frame_number, encoder->guts->client_data) != FLAC__ENCODER_WRITE_OK)
355                 return encoder->state = FLAC__ENCODER_FATAL_ERROR_WHILE_WRITING;
356
357         /* now that the metadata block is written, we can init this to an absurdly-high value... */
358         encoder->guts->metadata.data.encoding.min_framesize = (1u << FLAC__STREAM_METADATA_ENCODING_MIN_FRAME_SIZE_LEN) - 1;
359         /* ... and clear this to 0 */
360         encoder->guts->metadata.data.encoding.total_samples = 0;
361
362         return encoder->state;
363 }
364
365 void FLAC__encoder_finish(FLAC__Encoder *encoder)
366 {
367         unsigned i;
368
369         assert(encoder != 0);
370         if(encoder->state == FLAC__ENCODER_UNINITIALIZED)
371                 return;
372         if(encoder->guts->current_sample_number != 0) {
373                 encoder->blocksize = encoder->guts->current_sample_number;
374                 encoder_process_frame_(encoder, true); /* true => is last frame */
375         }
376         MD5Final(encoder->guts->metadata.data.encoding.md5sum, &encoder->guts->md5context);
377         encoder->guts->metadata_callback(encoder, &encoder->guts->metadata, encoder->guts->client_data);
378         if(encoder->guts != 0) {
379                 for(i = 0; i < encoder->channels; i++) {
380                         if(encoder->guts->integer_signal[i] != 0) {
381                                 free(encoder->guts->integer_signal[i]);
382                                 encoder->guts->integer_signal[i] = 0;
383                         }
384                         if(encoder->guts->real_signal[i] != 0) {
385                                 free(encoder->guts->real_signal[i]);
386                                 encoder->guts->real_signal[i] = 0;
387                         }
388                 }
389                 for(i = 0; i < 2; i++) {
390                         if(encoder->guts->integer_signal_mid_side[i] != 0) {
391                                 free(encoder->guts->integer_signal_mid_side[i]);
392                                 encoder->guts->integer_signal_mid_side[i] = 0;
393                         }
394                         if(encoder->guts->real_signal_mid_side[i] != 0) {
395                                 free(encoder->guts->real_signal_mid_side[i]);
396                                 encoder->guts->real_signal_mid_side[i] = 0;
397                         }
398                 }
399                 for(i = 0; i < 2; i++) {
400                         if(encoder->guts->residual[i] != 0) {
401                                 free(encoder->guts->residual[i]);
402                                 encoder->guts->residual[i] = 0;
403                         }
404                 }
405                 if(encoder->guts->abs_residual != 0) {
406                         free(encoder->guts->abs_residual);
407                         encoder->guts->abs_residual = 0;
408                 }
409                 FLAC__bitbuffer_free(&encoder->guts->frame);
410                 free(encoder->guts);
411                 encoder->guts = 0;
412         }
413         encoder->state = FLAC__ENCODER_UNINITIALIZED;
414 }
415
416 bool FLAC__encoder_process(FLAC__Encoder *encoder, const int32 *buf[], unsigned samples)
417 {
418         unsigned i, j, channel;
419         int32 x, mid, side;
420         const bool ms = encoder->do_mid_side_stereo && encoder->channels == 2;
421         const int32 min_side = -((int64)1 << (encoder->bits_per_sample-1));
422         const int32 max_side =  ((int64)1 << (encoder->bits_per_sample-1)) - 1;
423
424         assert(encoder != 0);
425         assert(encoder->state == FLAC__ENCODER_OK);
426
427         j = 0;
428         do {
429                 for(i = encoder->guts->current_sample_number; i < encoder->blocksize && j < samples; i++, j++) {
430                         for(channel = 0; channel < encoder->channels; channel++) {
431                                 x = buf[channel][j];
432                                 encoder->guts->integer_signal[channel][i] = x;
433                                 encoder->guts->real_signal[channel][i] = (real)x;
434                         }
435                         if(ms && encoder->guts->current_frame_can_do_mid_side) {
436                                 side = buf[0][j] - buf[1][j];
437                                 if(side < min_side || side > max_side) {
438                                         encoder->guts->current_frame_can_do_mid_side = false;
439                                 }
440                                 else {
441                                         mid = (buf[0][j] + buf[1][j]) >> 1; /* NOTE: not the same as divide-by-two ! */
442                                         encoder->guts->integer_signal_mid_side[0][i] = mid;
443                                         encoder->guts->integer_signal_mid_side[1][i] = side;
444                                         encoder->guts->real_signal_mid_side[0][i] = (real)mid;
445                                         encoder->guts->real_signal_mid_side[1][i] = (real)side;
446                                 }
447                         }
448                         encoder->guts->current_sample_number++;
449                 }
450                 if(i == encoder->blocksize) {
451                         if(!encoder_process_frame_(encoder, false)) /* false => not last frame */
452                                 return false;
453                 }
454         } while(j < samples);
455
456         return true;
457 }
458
459 /* 'samples' is channel-wide samples, e.g. for 1 second at 44100Hz, 'samples' = 44100 regardless of the number of channels */
460 bool FLAC__encoder_process_interleaved(FLAC__Encoder *encoder, const int32 buf[], unsigned samples)
461 {
462         unsigned i, j, k, channel;
463         int32 x, left = 0, mid, side;
464         const bool ms = encoder->do_mid_side_stereo && encoder->channels == 2;
465         const int32 min_side = -((int64)1 << (encoder->bits_per_sample-1));
466         const int32 max_side =  ((int64)1 << (encoder->bits_per_sample-1)) - 1;
467
468         assert(encoder != 0);
469         assert(encoder->state == FLAC__ENCODER_OK);
470
471         j = k = 0;
472         do {
473                 for(i = encoder->guts->current_sample_number; i < encoder->blocksize && j < samples; i++, j++, k++) {
474                         for(channel = 0; channel < encoder->channels; channel++, k++) {
475                                 x = buf[k];
476                                 encoder->guts->integer_signal[channel][i] = x;
477                                 encoder->guts->real_signal[channel][i] = (real)x;
478                                 if(ms && encoder->guts->current_frame_can_do_mid_side) {
479                                         if(channel == 0) {
480                                                 left = x;
481                                         }
482                                         else {
483                                                 side = left - x;
484                                                 if(side < min_side || side > max_side) {
485                                                         encoder->guts->current_frame_can_do_mid_side = false;
486                                                 }
487                                                 else {
488                                                         mid = (left + x) >> 1; /* NOTE: not the same as divide-by-two ! */
489                                                         encoder->guts->integer_signal_mid_side[0][i] = mid;
490                                                         encoder->guts->integer_signal_mid_side[1][i] = side;
491                                                         encoder->guts->real_signal_mid_side[0][i] = (real)mid;
492                                                         encoder->guts->real_signal_mid_side[1][i] = (real)side;
493                                                 }
494                                         }
495                                 }
496                         }
497                         encoder->guts->current_sample_number++;
498                 }
499                 if(i == encoder->blocksize) {
500                         if(!encoder_process_frame_(encoder, false)) /* false => not last frame */
501                                 return false;
502                 }
503         } while(j < samples);
504
505         return true;
506 }
507
508 bool encoder_process_frame_(FLAC__Encoder *encoder, bool is_last_frame)
509 {
510         FLAC__FrameHeader frame_header;
511         FLAC__BitBuffer *smallest_frame;
512
513         assert(encoder->state == FLAC__ENCODER_OK);
514
515         /*
516          * Accumulate raw signal to the MD5 signature
517          */
518         if(!FLAC__MD5Accumulate(&encoder->guts->md5context, encoder->guts->integer_signal, encoder->channels, encoder->blocksize, (encoder->bits_per_sample+7) / 8)) {
519                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
520                 return false;
521         }
522
523         /*
524          * First do a normal encoding pass
525          */
526         frame_header.blocksize = encoder->blocksize;
527         frame_header.sample_rate = encoder->sample_rate;
528         frame_header.channels = encoder->channels;
529         frame_header.channel_assignment = FLAC__CHANNEL_ASSIGNMENT_INDEPENDENT; /* the default unless the encoder determines otherwise */
530         frame_header.bits_per_sample = encoder->bits_per_sample;
531         frame_header.number.frame_number = encoder->guts->current_frame_number;
532
533         if(!FLAC__bitbuffer_clear(&encoder->guts->frame)) {
534                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
535                 return false;
536         }
537         if(!FLAC__frame_add_header(&frame_header, encoder->streamable_subset, is_last_frame, &encoder->guts->frame)) {
538                 encoder->state = FLAC__ENCODER_FRAMING_ERROR;
539                 return false;
540         }
541
542         if(!encoder_process_subframes_(encoder, is_last_frame, encoder->force_mid_side_stereo, &frame_header, encoder->channels, encoder->guts->integer_signal, encoder->guts->real_signal, &encoder->guts->frame))
543                 return false;
544
545         smallest_frame = &encoder->guts->frame;
546
547         /*
548          * Now try a mid-side version if necessary; otherwise, just use the previous step's frame
549          */
550         if(encoder->do_mid_side_stereo && encoder->guts->current_frame_can_do_mid_side) {
551                 int32 *integer_signal[2];
552                 real *real_signal[2];
553
554                 assert(encoder->channels == 2);
555
556                 /* mid-side */
557                 frame_header.channel_assignment = FLAC__CHANNEL_ASSIGNMENT_MID_SIDE;
558                 if(!FLAC__bitbuffer_clear(&encoder->guts->frame_mid_side)) {
559                         encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
560                         return false;
561                 }
562                 if(!FLAC__frame_add_header(&frame_header, encoder->streamable_subset, is_last_frame, &encoder->guts->frame_mid_side)) {
563                         encoder->state = FLAC__ENCODER_FRAMING_ERROR;
564                         return false;
565                 }
566                 integer_signal[0] = encoder->guts->integer_signal_mid_side[0]; /* mid channel */
567                 integer_signal[1] = encoder->guts->integer_signal_mid_side[1]; /* side channel */
568                 real_signal[0] = encoder->guts->real_signal_mid_side[0]; /* mid channel */
569                 real_signal[1] = encoder->guts->real_signal_mid_side[1]; /* side channel */
570                 if(!encoder_process_subframes_(encoder, is_last_frame, false, &frame_header, encoder->channels, integer_signal, real_signal, &encoder->guts->frame_mid_side))
571                         return false;
572                 if(encoder->guts->frame_mid_side.total_bits < smallest_frame->total_bits)
573                         smallest_frame = &encoder->guts->frame_mid_side;
574
575                 if(!encoder->force_mid_side_stereo) {
576                         /* left-side */
577                         frame_header.channel_assignment = FLAC__CHANNEL_ASSIGNMENT_LEFT_SIDE;
578                         if(!FLAC__bitbuffer_clear(&encoder->guts->frame_left_side)) {
579                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
580                                 return false;
581                         }
582                         if(!FLAC__frame_add_header(&frame_header, encoder->streamable_subset, is_last_frame, &encoder->guts->frame_left_side)) {
583                                 encoder->state = FLAC__ENCODER_FRAMING_ERROR;
584                                 return false;
585                         }
586                         integer_signal[0] = encoder->guts->integer_signal[0]; /* left channel */
587                         integer_signal[1] = encoder->guts->integer_signal_mid_side[1]; /* side channel */
588                         real_signal[0] = encoder->guts->real_signal[0]; /* left channel */
589                         real_signal[1] = encoder->guts->real_signal_mid_side[1]; /* side channel */
590                         if(!encoder_process_subframes_(encoder, is_last_frame, false, &frame_header, encoder->channels, integer_signal, real_signal, &encoder->guts->frame_left_side))
591                                 return false;
592                         if(encoder->guts->frame_left_side.total_bits < smallest_frame->total_bits)
593                                 smallest_frame = &encoder->guts->frame_left_side;
594
595                         /* right-side */
596                         frame_header.channel_assignment = FLAC__CHANNEL_ASSIGNMENT_RIGHT_SIDE;
597                         if(!FLAC__bitbuffer_clear(&encoder->guts->frame_right_side)) {
598                                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
599                                 return false;
600                         }
601                         if(!FLAC__frame_add_header(&frame_header, encoder->streamable_subset, is_last_frame, &encoder->guts->frame_right_side)) {
602                                 encoder->state = FLAC__ENCODER_FRAMING_ERROR;
603                                 return false;
604                         }
605                         integer_signal[0] = encoder->guts->integer_signal_mid_side[1]; /* side channel */
606                         integer_signal[1] = encoder->guts->integer_signal[1]; /* right channel */
607                         real_signal[0] = encoder->guts->real_signal_mid_side[1]; /* side channel */
608                         real_signal[1] = encoder->guts->real_signal[1]; /* right channel */
609                         if(!encoder_process_subframes_(encoder, is_last_frame, false, &frame_header, encoder->channels, integer_signal, real_signal, &encoder->guts->frame_right_side))
610                                 return false;
611                         if(encoder->guts->frame_right_side.total_bits < smallest_frame->total_bits)
612                                 smallest_frame = &encoder->guts->frame_right_side;
613                 }
614         }
615
616         /*
617          * Zero-pad the frame to a byte_boundary
618          */
619         if(!FLAC__bitbuffer_zero_pad_to_byte_boundary(smallest_frame)) {
620                 encoder->state = FLAC__ENCODER_MEMORY_ALLOCATION_ERROR;
621                 return false;
622         }
623
624         /*
625          * Write it
626          */
627         assert(smallest_frame->bits == 0); /* assert that we're byte-aligned before writing */
628         assert(smallest_frame->total_consumed_bits == 0); /* assert that no reading of the buffer was done */
629         if(encoder->guts->write_callback(encoder, smallest_frame->buffer, smallest_frame->bytes, encoder->blocksize, encoder->guts->current_frame_number, encoder->guts->client_data) != FLAC__ENCODER_WRITE_OK) {
630                 encoder->state = FLAC__ENCODER_FATAL_ERROR_WHILE_WRITING;
631                 return false;
632         }
633
634         /*
635          * Get ready for the next frame
636          */
637         encoder->guts->current_frame_can_do_mid_side = true;
638         encoder->guts->current_sample_number = 0;
639         encoder->guts->current_frame_number++;
640         encoder->guts->metadata.data.encoding.total_samples += (uint64)encoder->blocksize;
641         encoder->guts->metadata.data.encoding.min_framesize = min(smallest_frame->bytes, encoder->guts->metadata.data.encoding.min_framesize);
642         encoder->guts->metadata.data.encoding.max_framesize = max(smallest_frame->bytes, encoder->guts->metadata.data.encoding.max_framesize);
643
644         return true;
645 }
646
647 bool encoder_process_subframes_(FLAC__Encoder *encoder, bool is_last_frame, bool verbatim_only, const FLAC__FrameHeader *frame_header, unsigned channels, const int32 *integer_signal[], const real *real_signal[], FLAC__BitBuffer *frame)
648 {
649         real fixed_residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1];
650         real lpc_residual_bits_per_sample;
651         real autoc[FLAC__MAX_LPC_ORDER+1];
652         real lp_coeff[FLAC__MAX_LPC_ORDER][FLAC__MAX_LPC_ORDER];
653         real lpc_error[FLAC__MAX_LPC_ORDER];
654         unsigned channel;
655         unsigned min_lpc_order, max_lpc_order, lpc_order;
656         unsigned min_fixed_order, max_fixed_order, guess_fixed_order, fixed_order;
657         unsigned max_partition_order;
658         unsigned min_qlp_coeff_precision, max_qlp_coeff_precision, qlp_coeff_precision;
659         unsigned rice_parameter;
660         unsigned candidate_bits, best_bits;
661
662         if(is_last_frame) {
663                 max_partition_order = 0;
664         }
665         else {
666                 unsigned limit = 0, b = encoder->blocksize;
667                 while(!(b & 1)) {
668                         limit++;
669                         b >>= 1;
670                 }
671                 max_partition_order = min(encoder->rice_optimization_level, limit);
672         }
673
674         for(channel = 0; channel < channels; channel++) {
675                 /* verbatim subframe is the baseline against which we measure other compressed subframes */
676                 best_bits = encoder_evaluate_verbatim_subframe_(frame_header->blocksize, frame_header->bits_per_sample, &(encoder->guts->best_subframe));
677
678                 if(!verbatim_only && frame_header->blocksize >= FLAC__MAX_FIXED_ORDER) {
679                         /* check for constant subframe */
680                         guess_fixed_order = FLAC__fixed_compute_best_predictor(integer_signal[channel]+FLAC__MAX_FIXED_ORDER, frame_header->blocksize-FLAC__MAX_FIXED_ORDER, fixed_residual_bits_per_sample);
681                         if(fixed_residual_bits_per_sample[1] == 0.0) {
682                                 /* the above means integer_signal[channel]+FLAC__MAX_FIXED_ORDER is constant, now we just have to check the warmup samples */
683                                 unsigned i, signal_is_constant = true;
684                                 for(i = 1; i <= FLAC__MAX_FIXED_ORDER; i++) {
685                                         if(integer_signal[channel][0] != integer_signal[channel][i]) {
686                                                 signal_is_constant = false;
687                                                 break;
688                                         }
689                                 }
690                                 if(signal_is_constant) {
691                                         candidate_bits = encoder_evaluate_constant_subframe_(integer_signal[channel][0], frame_header->bits_per_sample, &(encoder->guts->candidate_subframe));
692                                         if(candidate_bits < best_bits) {
693                                                 encoder_promote_candidate_subframe_(encoder);
694                                                 best_bits = candidate_bits;
695                                         }
696                                 }
697                         }
698                         else {
699                                 /* encode fixed */
700                                 if(encoder->do_exhaustive_model_search) {
701                                         min_fixed_order = 0;
702                                         max_fixed_order = FLAC__MAX_FIXED_ORDER;
703                                 }
704                                 else {
705                                         min_fixed_order = max_fixed_order = guess_fixed_order;
706                                 }
707                                 for(fixed_order = min_fixed_order; fixed_order <= max_fixed_order; fixed_order++) {
708                                         if(fixed_residual_bits_per_sample[fixed_order] >= (real)frame_header->bits_per_sample)
709                                                 continue; /* don't even try */
710                                         /* 0.5 is for rounding, another 1.0 is to account for the signed->unsigned conversion during rice coding */
711                                         rice_parameter = (fixed_residual_bits_per_sample[fixed_order] > 0.0)? (unsigned)(fixed_residual_bits_per_sample[fixed_order]+1.5) : 0;
712                                         if(rice_parameter >= (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN))
713                                                 rice_parameter = (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN) - 1;
714                                         candidate_bits = encoder_evaluate_fixed_subframe_(integer_signal[channel], encoder->guts->residual[!encoder->guts->best_residual], encoder->guts->abs_residual, frame_header->blocksize, frame_header->bits_per_sample, fixed_order, rice_parameter, max_partition_order, &(encoder->guts->candidate_subframe));
715                                         if(candidate_bits < best_bits) {
716                                                 encoder_promote_candidate_subframe_(encoder);
717                                                 best_bits = candidate_bits;
718                                         }
719                                 }
720
721                                 /* encode lpc */
722                                 if(encoder->max_lpc_order > 0) {
723                                         if(encoder->max_lpc_order >= frame_header->blocksize)
724                                                 max_lpc_order = frame_header->blocksize-1;
725                                         else
726                                                 max_lpc_order = encoder->max_lpc_order;
727                                         if(max_lpc_order > 0) {
728                                                 FLAC__lpc_compute_autocorrelation(real_signal[channel], frame_header->blocksize, max_lpc_order+1, autoc);
729                                                 FLAC__lpc_compute_lp_coefficients(autoc, max_lpc_order, lp_coeff, lpc_error);
730                                                 if(encoder->do_exhaustive_model_search) {
731                                                         min_lpc_order = 1;
732                                                 }
733                                                 else {
734                                                         unsigned guess_lpc_order = FLAC__lpc_compute_best_order(lpc_error, max_lpc_order, frame_header->blocksize, frame_header->bits_per_sample);
735                                                         min_lpc_order = max_lpc_order = guess_lpc_order;
736                                                 }
737                                                 if(encoder->do_qlp_coeff_prec_search) {
738                                                         min_qlp_coeff_precision = FLAC__MIN_QLP_COEFF_PRECISION;
739                                                         max_qlp_coeff_precision = 32 - frame_header->bits_per_sample - 1;
740                                                 }
741                                                 else {
742                                                         min_qlp_coeff_precision = max_qlp_coeff_precision = encoder->qlp_coeff_precision;
743                                                 }
744                                                 for(lpc_order = min_lpc_order; lpc_order <= max_lpc_order; lpc_order++) {
745                                                         lpc_residual_bits_per_sample = FLAC__lpc_compute_expected_bits_per_residual_sample(lpc_error[lpc_order-1], frame_header->blocksize);
746                                                         if(lpc_residual_bits_per_sample >= (real)frame_header->bits_per_sample)
747                                                                 continue; /* don't even try */
748                                                         /* 0.5 is for rounding, another 1.0 is to account for the signed->unsigned conversion during rice coding */
749                                                         rice_parameter = (lpc_residual_bits_per_sample > 0.0)? (unsigned)(lpc_residual_bits_per_sample+1.5) : 0;
750                                                         if(rice_parameter >= (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN))
751                                                                 rice_parameter = (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN) - 1;
752                                                         for(qlp_coeff_precision = min_qlp_coeff_precision; qlp_coeff_precision <= max_qlp_coeff_precision; qlp_coeff_precision++) {
753                                                                 candidate_bits = encoder_evaluate_lpc_subframe_(integer_signal[channel], encoder->guts->residual[!encoder->guts->best_residual], encoder->guts->abs_residual, lp_coeff[lpc_order-1], frame_header->blocksize, frame_header->bits_per_sample, lpc_order, qlp_coeff_precision, rice_parameter, max_partition_order, &(encoder->guts->candidate_subframe));
754                                                                 if(candidate_bits > 0) { /* if == 0, there was a problem quantizing the lpcoeffs */
755                                                                         if(candidate_bits < best_bits) {
756                                                                                 encoder_promote_candidate_subframe_(encoder);
757                                                                                 best_bits = candidate_bits;
758                                                                         }
759                                                                 }
760                                                         }
761                                                 }
762                                         }
763                                 }
764                         }
765                 }
766
767                 /* add the best subframe */
768                 switch(encoder->guts->best_subframe.type) {
769                         case FLAC__SUBFRAME_TYPE_CONSTANT:
770                                 if(!FLAC__subframe_add_constant(&(encoder->guts->best_subframe.data.constant), frame_header->bits_per_sample, frame)) {
771                                         encoder->state = FLAC__ENCODER_FATAL_ERROR_WHILE_ENCODING;
772                                         return false;
773                                 }
774                                 break;
775                         case FLAC__SUBFRAME_TYPE_FIXED:
776                                 encoder->guts->best_subframe.data.fixed.residual = encoder->guts->residual[encoder->guts->best_residual];
777                                 if(!FLAC__subframe_add_fixed(&(encoder->guts->best_subframe.data.fixed), frame_header->blocksize - encoder->guts->best_subframe.data.fixed.order, frame_header->bits_per_sample, frame)) {
778                                         encoder->state = FLAC__ENCODER_FATAL_ERROR_WHILE_ENCODING;
779                                         return false;
780                                 }
781                                 break;
782                         case FLAC__SUBFRAME_TYPE_LPC:
783                                 encoder->guts->best_subframe.data.lpc.residual = encoder->guts->residual[encoder->guts->best_residual];
784                                 if(!FLAC__subframe_add_lpc(&(encoder->guts->best_subframe.data.lpc), frame_header->blocksize - encoder->guts->best_subframe.data.lpc.order, frame_header->bits_per_sample, frame)) {
785                                         encoder->state = FLAC__ENCODER_FATAL_ERROR_WHILE_ENCODING;
786                                         return false;
787                                 }
788                                 break;
789                         case FLAC__SUBFRAME_TYPE_VERBATIM:
790                                 encoder->guts->best_subframe.data.verbatim.data = integer_signal[channel];
791                                 if(!FLAC__subframe_add_verbatim(&(encoder->guts->best_subframe.data.verbatim), frame_header->blocksize, frame_header->bits_per_sample, frame)) {
792                                         encoder->state = FLAC__ENCODER_FATAL_ERROR_WHILE_ENCODING;
793                                         return false;
794                                 }
795                                 break;
796                 }
797         }
798
799         return true;
800 }
801
802 unsigned encoder_evaluate_constant_subframe_(const int32 signal, unsigned bits_per_sample, FLAC__Subframe *subframe)
803 {
804         subframe->type = FLAC__SUBFRAME_TYPE_CONSTANT;
805         subframe->data.constant.value = signal;
806
807         return FLAC__SUBFRAME_TYPE_LEN + bits_per_sample;
808 }
809
810 unsigned encoder_evaluate_fixed_subframe_(const int32 signal[], int32 residual[], uint32 abs_residual[], unsigned blocksize, unsigned bits_per_sample, unsigned order, unsigned rice_parameter, unsigned max_partition_order, FLAC__Subframe *subframe)
811 {
812         unsigned i, residual_bits;
813         const unsigned residual_samples = blocksize - order;
814
815         FLAC__fixed_compute_residual(signal+order, residual_samples, order, residual);
816
817         subframe->type = FLAC__SUBFRAME_TYPE_FIXED;
818
819         subframe->data.fixed.entropy_coding_method.type = FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE;
820
821         residual_bits = encoder_find_best_partition_order_(residual, abs_residual, residual_samples, order, rice_parameter, max_partition_order, &subframe->data.fixed.entropy_coding_method.data.partitioned_rice.order, subframe->data.fixed.entropy_coding_method.data.partitioned_rice.parameters);
822
823         subframe->data.fixed.order = order;
824         for(i = 0; i < order; i++)
825                 subframe->data.fixed.warmup[i] = signal[i];
826
827         return FLAC__SUBFRAME_TYPE_LEN + (order * bits_per_sample) + residual_bits;
828 }
829
830 unsigned encoder_evaluate_lpc_subframe_(const int32 signal[], int32 residual[], uint32 abs_residual[], const real lp_coeff[], unsigned blocksize, unsigned bits_per_sample, unsigned order, unsigned qlp_coeff_precision, unsigned rice_parameter, unsigned max_partition_order, FLAC__Subframe *subframe)
831 {
832         int32 qlp_coeff[FLAC__MAX_LPC_ORDER];
833         unsigned i, residual_bits;
834         int quantization, ret;
835         const unsigned residual_samples = blocksize - order;
836
837         ret = FLAC__lpc_quantize_coefficients(lp_coeff, order, qlp_coeff_precision, bits_per_sample, qlp_coeff, &quantization);
838         if(ret != 0)
839                 return 0; /* this is a hack to indicate to the caller that we can't do lp at this order on this subframe */
840
841         FLAC__lpc_compute_residual_from_qlp_coefficients(signal+order, residual_samples, qlp_coeff, order, quantization, residual);
842
843         subframe->type = FLAC__SUBFRAME_TYPE_LPC;
844
845         subframe->data.lpc.entropy_coding_method.type = FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE;
846
847         residual_bits = encoder_find_best_partition_order_(residual, abs_residual, residual_samples, order, rice_parameter, max_partition_order, &subframe->data.lpc.entropy_coding_method.data.partitioned_rice.order, subframe->data.lpc.entropy_coding_method.data.partitioned_rice.parameters);
848
849         subframe->data.lpc.order = order;
850         subframe->data.lpc.qlp_coeff_precision = qlp_coeff_precision;
851         subframe->data.lpc.quantization_level = quantization;
852         memcpy(subframe->data.lpc.qlp_coeff, qlp_coeff, sizeof(int32)*FLAC__MAX_LPC_ORDER);
853         for(i = 0; i < order; i++)
854                 subframe->data.lpc.warmup[i] = signal[i];
855
856         return FLAC__SUBFRAME_TYPE_LEN + FLAC__SUBFRAME_LPC_QLP_COEFF_PRECISION_LEN + FLAC__SUBFRAME_LPC_QLP_SHIFT_LEN + (order * (qlp_coeff_precision + bits_per_sample)) + residual_bits;
857 }
858
859 unsigned encoder_evaluate_verbatim_subframe_(unsigned blocksize, unsigned bits_per_sample, FLAC__Subframe *subframe)
860 {
861         subframe->type = FLAC__SUBFRAME_TYPE_VERBATIM;
862
863         return FLAC__SUBFRAME_TYPE_LEN + (blocksize * bits_per_sample);
864 }
865
866 unsigned encoder_find_best_partition_order_(const int32 residual[], uint32 abs_residual[], unsigned residual_samples, unsigned predictor_order, unsigned rice_parameter, unsigned max_partition_order, unsigned *best_partition_order, unsigned best_parameters[])
867 {
868         unsigned residual_bits, best_residual_bits = 0;
869         unsigned i, partition_order;
870         unsigned best_parameters_index = 0, parameters[2][1 << FLAC__MAX_RICE_PARTITION_ORDER];
871         int32 r;
872
873         /* compute the abs(residual) for use later */
874         for(i = 0; i < residual_samples; i++) {
875                 r = residual[i];
876                 abs_residual[i] = (uint32)(r<0? -r : r);
877         }
878
879         for(partition_order = 0; partition_order <= max_partition_order; partition_order++) {
880                 if(!encoder_set_partitioned_rice_(abs_residual, residual_samples, predictor_order, rice_parameter, partition_order, parameters[!best_parameters_index], &residual_bits)) {
881                         assert(best_residual_bits != 0);
882                         break;
883                 }
884                 if(best_residual_bits == 0 || residual_bits < best_residual_bits) {
885                         best_residual_bits = residual_bits;
886                         *best_partition_order = partition_order;
887                         best_parameters_index = !best_parameters_index;
888                 }
889         }
890         memcpy(best_parameters, parameters[best_parameters_index], sizeof(unsigned)*(1<<(*best_partition_order)));
891
892         return best_residual_bits;
893 }
894
895 void encoder_promote_candidate_subframe_(FLAC__Encoder *encoder)
896 {
897         assert(encoder->state == FLAC__ENCODER_OK);
898         encoder->guts->best_subframe = encoder->guts->candidate_subframe;
899         encoder->guts->best_residual = !encoder->guts->best_residual;
900 }
901
902 #ifdef ESTIMATE_RICE_BITS
903 #undef ESTIMATE_RICE_BITS
904 #endif
905 #define ESTIMATE_RICE_BITS(value, parameter) ((value) >> (parameter))
906
907 bool encoder_set_partitioned_rice_(const uint32 abs_residual[], const unsigned residual_samples, const unsigned predictor_order, const unsigned rice_parameter, const unsigned partition_order, unsigned parameters[], unsigned *bits)
908 {
909         unsigned bits_ = FLAC__ENTROPY_CODING_METHOD_TYPE_LEN + FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_ORDER_LEN;
910
911         if(partition_order == 0) {
912                 unsigned i;
913 #ifdef ESTIMATE_RICE_BITS
914                 const unsigned rice_parameter_estimate = rice_parameter-1;
915                 bits_ += (1+rice_parameter) * residual_samples;
916 #endif
917                 parameters[0] = rice_parameter;
918                 bits_ += FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN;
919                 for(i = 0; i < residual_samples; i++)
920 #ifdef ESTIMATE_RICE_BITS
921                         bits_ += ESTIMATE_RICE_BITS(abs_residual[i], rice_parameter_estimate);
922 #else
923                         bits_ += FLAC__bitbuffer_rice_bits(residual[i], rice_parameter);
924 #endif
925         }
926         else {
927                 unsigned i, j, k = 0, k_last = 0;
928                 unsigned mean, parameter, partition_samples;
929                 const unsigned max_parameter = (1u << FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN) - 1;
930                 for(i = 0; i < (1u<<partition_order); i++) {
931                         partition_samples = (residual_samples+predictor_order) >> partition_order;
932                         if(i == 0) {
933                                 if(partition_samples <= predictor_order)
934                                         return false;
935                                 else
936                                         partition_samples -= predictor_order;
937                         }
938                         mean = partition_samples >> 1;
939                         for(j = 0; j < partition_samples; j++, k++)
940                                 mean += abs_residual[k];
941                         mean /= partition_samples;
942                         /* calc parameter = floor(log2(mean)) + 1 */
943                         parameter = 0;
944                         while(mean) {
945                                 parameter++;
946                                 mean >>= 1;
947                         }
948                         if(parameter > max_parameter)
949                                 parameter = max_parameter;
950                         parameters[i] = parameter;
951                         bits_ += FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE_PARAMETER_LEN;
952 #ifdef ESTIMATE_RICE_BITS
953                         bits_ += (1+parameter) * partition_samples;
954                         --parameter;
955 #endif
956                         for(j = k_last; j < k; j++)
957 #ifdef ESTIMATE_RICE_BITS
958                                 bits_ += ESTIMATE_RICE_BITS(abs_residual[j], parameter);
959 #else
960                                 bits_ += FLAC__bitbuffer_rice_bits(residual[j], parameter);
961 #endif
962                         k_last = k;
963                 }
964         }
965
966         *bits = bits_;
967         return true;
968 }