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