Josh Coalson | 26560dd | 2001-02-08 00:38:41 +0000 | [diff] [blame] | 1 | /* libFLAC - Free Lossless Audio Codec library |
Josh Coalson | 0395dac | 2006-04-25 06:59:33 +0000 | [diff] [blame] | 2 | * Copyright (C) 2000,2001,2002,2003,2004,2005,2006 Josh Coalson |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 3 | * |
Josh Coalson | afd8107 | 2003-01-31 23:34:56 +0000 | [diff] [blame] | 4 | * Redistribution and use in source and binary forms, with or without |
| 5 | * modification, are permitted provided that the following conditions |
| 6 | * are met: |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 7 | * |
Josh Coalson | afd8107 | 2003-01-31 23:34:56 +0000 | [diff] [blame] | 8 | * - Redistributions of source code must retain the above copyright |
| 9 | * notice, this list of conditions and the following disclaimer. |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 10 | * |
Josh Coalson | afd8107 | 2003-01-31 23:34:56 +0000 | [diff] [blame] | 11 | * - Redistributions in binary form must reproduce the above copyright |
| 12 | * notice, this list of conditions and the following disclaimer in the |
| 13 | * documentation and/or other materials provided with the distribution. |
| 14 | * |
| 15 | * - Neither the name of the Xiph.org Foundation nor the names of its |
| 16 | * contributors may be used to endorse or promote products derived from |
| 17 | * this software without specific prior written permission. |
| 18 | * |
| 19 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 20 | * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 21 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 22 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR |
| 23 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| 24 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| 25 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 26 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 27 | * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 28 | * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 29 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 30 | */ |
| 31 | |
Josh Coalson | b1ec796 | 2006-05-24 04:41:36 +0000 | [diff] [blame^] | 32 | #if HAVE_CONFIG_H |
| 33 | # include <config.h> |
| 34 | #endif |
| 35 | |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 36 | #include <math.h> |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 37 | #include "FLAC/assert.h" |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 38 | #include "FLAC/format.h" |
Josh Coalson | eac1024 | 2002-10-04 05:25:54 +0000 | [diff] [blame] | 39 | #include "private/bitmath.h" |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 40 | #include "private/lpc.h" |
Josh Coalson | 03ed88b | 2002-05-17 06:19:28 +0000 | [diff] [blame] | 41 | #if defined DEBUG || defined FLAC__OVERFLOW_DETECT || defined FLAC__OVERFLOW_DETECT_VERBOSE |
| 42 | #include <stdio.h> |
| 43 | #endif |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 44 | |
Josh Coalson | 5f2b46d | 2004-11-09 01:34:01 +0000 | [diff] [blame] | 45 | #ifndef FLAC__INTEGER_ONLY_LIBRARY |
| 46 | |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 47 | #ifndef M_LN2 |
| 48 | /* math.h in VC++ doesn't seem to have this (how Microsoft is that?) */ |
| 49 | #define M_LN2 0.69314718055994530942 |
| 50 | #endif |
| 51 | |
Josh Coalson | bf0f52c | 2006-04-25 06:38:43 +0000 | [diff] [blame] | 52 | void FLAC__lpc_window_data(const FLAC__real in[], const FLAC__real window[], FLAC__real out[], unsigned data_len) |
| 53 | { |
| 54 | unsigned i; |
| 55 | for(i = 0; i < data_len; i++) |
| 56 | out[i] = in[i] * window[i]; |
| 57 | } |
| 58 | |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 59 | void FLAC__lpc_compute_autocorrelation(const FLAC__real data[], unsigned data_len, unsigned lag, FLAC__real autoc[]) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 60 | { |
Josh Coalson | c0785cd | 2001-05-10 19:29:41 +0000 | [diff] [blame] | 61 | /* a readable, but slower, version */ |
| 62 | #if 0 |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 63 | FLAC__real d; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 64 | unsigned i; |
| 65 | |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 66 | FLAC__ASSERT(lag > 0); |
| 67 | FLAC__ASSERT(lag <= data_len); |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 68 | |
Josh Coalson | 6e2b565 | 2006-04-28 00:11:31 +0000 | [diff] [blame] | 69 | /* |
| 70 | * Technically we should subtract the mean first like so: |
| 71 | * for(i = 0; i < data_len; i++) |
| 72 | * data[i] -= mean; |
| 73 | * but it appears not to make enough of a difference to matter, and |
| 74 | * most signals are already closely centered around zero |
| 75 | */ |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 76 | while(lag--) { |
| 77 | for(i = lag, d = 0.0; i < data_len; i++) |
| 78 | d += data[i] * data[i - lag]; |
| 79 | autoc[lag] = d; |
| 80 | } |
Josh Coalson | c0785cd | 2001-05-10 19:29:41 +0000 | [diff] [blame] | 81 | #endif |
| 82 | |
| 83 | /* |
| 84 | * this version tends to run faster because of better data locality |
| 85 | * ('data_len' is usually much larger than 'lag') |
| 86 | */ |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 87 | FLAC__real d; |
Josh Coalson | c0785cd | 2001-05-10 19:29:41 +0000 | [diff] [blame] | 88 | unsigned sample, coeff; |
| 89 | const unsigned limit = data_len - lag; |
| 90 | |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 91 | FLAC__ASSERT(lag > 0); |
| 92 | FLAC__ASSERT(lag <= data_len); |
Josh Coalson | c0785cd | 2001-05-10 19:29:41 +0000 | [diff] [blame] | 93 | |
| 94 | for(coeff = 0; coeff < lag; coeff++) |
| 95 | autoc[coeff] = 0.0; |
Josh Coalson | 376807d | 2001-05-16 19:23:35 +0000 | [diff] [blame] | 96 | for(sample = 0; sample <= limit; sample++) { |
Josh Coalson | c0785cd | 2001-05-10 19:29:41 +0000 | [diff] [blame] | 97 | d = data[sample]; |
| 98 | for(coeff = 0; coeff < lag; coeff++) |
| 99 | autoc[coeff] += d * data[sample+coeff]; |
| 100 | } |
Josh Coalson | 376807d | 2001-05-16 19:23:35 +0000 | [diff] [blame] | 101 | for(; sample < data_len; sample++) { |
Josh Coalson | c0785cd | 2001-05-10 19:29:41 +0000 | [diff] [blame] | 102 | d = data[sample]; |
| 103 | for(coeff = 0; coeff < data_len - sample; coeff++) |
| 104 | autoc[coeff] += d * data[sample+coeff]; |
| 105 | } |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 106 | } |
| 107 | |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 108 | void FLAC__lpc_compute_lp_coefficients(const FLAC__real autoc[], unsigned max_order, FLAC__real lp_coeff[][FLAC__MAX_LPC_ORDER], FLAC__double error[]) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 109 | { |
| 110 | unsigned i, j; |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 111 | FLAC__double r, err, ref[FLAC__MAX_LPC_ORDER], lpc[FLAC__MAX_LPC_ORDER]; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 112 | |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 113 | FLAC__ASSERT(0 < max_order); |
| 114 | FLAC__ASSERT(max_order <= FLAC__MAX_LPC_ORDER); |
| 115 | FLAC__ASSERT(autoc[0] != 0.0); |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 116 | |
| 117 | err = autoc[0]; |
| 118 | |
| 119 | for(i = 0; i < max_order; i++) { |
| 120 | /* Sum up this iteration's reflection coefficient. */ |
Josh Coalson | a1b53c4 | 2001-05-24 19:27:08 +0000 | [diff] [blame] | 121 | r = -autoc[i+1]; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 122 | for(j = 0; j < i; j++) |
| 123 | r -= lpc[j] * autoc[i-j]; |
| 124 | ref[i] = (r/=err); |
| 125 | |
| 126 | /* Update LPC coefficients and total error. */ |
| 127 | lpc[i]=r; |
| 128 | for(j = 0; j < (i>>1); j++) { |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 129 | FLAC__double tmp = lpc[j]; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 130 | lpc[j] += r * lpc[i-1-j]; |
| 131 | lpc[i-1-j] += r * tmp; |
| 132 | } |
| 133 | if(i & 1) |
| 134 | lpc[j] += lpc[j] * r; |
| 135 | |
| 136 | err *= (1.0 - r * r); |
| 137 | |
| 138 | /* save this order */ |
| 139 | for(j = 0; j <= i; j++) |
Josh Coalson | b35bebd | 2001-07-03 04:37:18 +0000 | [diff] [blame] | 140 | lp_coeff[i][j] = (FLAC__real)(-lpc[j]); /* negate FIR filter coeff to get predictor coeff */ |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 141 | error[i] = err; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 142 | } |
| 143 | } |
| 144 | |
Josh Coalson | eac1024 | 2002-10-04 05:25:54 +0000 | [diff] [blame] | 145 | int FLAC__lpc_quantize_coefficients(const FLAC__real lp_coeff[], unsigned order, unsigned precision, FLAC__int32 qlp_coeff[], int *shift) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 146 | { |
| 147 | unsigned i; |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 148 | FLAC__double d, cmax = -1e32; |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 149 | FLAC__int32 qmax, qmin; |
| 150 | const int max_shiftlimit = (1 << (FLAC__SUBFRAME_LPC_QLP_SHIFT_LEN-1)) - 1; |
| 151 | const int min_shiftlimit = -max_shiftlimit - 1; |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 152 | |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 153 | FLAC__ASSERT(precision > 0); |
| 154 | FLAC__ASSERT(precision >= FLAC__MIN_QLP_COEFF_PRECISION); |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 155 | |
| 156 | /* drop one bit for the sign; from here on out we consider only |lp_coeff[i]| */ |
| 157 | precision--; |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 158 | qmax = 1 << precision; |
| 159 | qmin = -qmax; |
| 160 | qmax--; |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 161 | |
| 162 | for(i = 0; i < order; i++) { |
| 163 | if(lp_coeff[i] == 0.0) |
| 164 | continue; |
Josh Coalson | f52360a | 2001-08-13 23:10:06 +0000 | [diff] [blame] | 165 | d = fabs(lp_coeff[i]); |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 166 | if(d > cmax) |
| 167 | cmax = d; |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 168 | } |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 169 | redo_it: |
Josh Coalson | d3ed49f | 2001-07-18 23:47:19 +0000 | [diff] [blame] | 170 | if(cmax <= 0.0) { |
Josh Coalson | 456db82 | 2001-03-01 19:14:05 +0000 | [diff] [blame] | 171 | /* => coefficients are all 0, which means our constant-detect didn't work */ |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 172 | return 2; |
| 173 | } |
| 174 | else { |
Josh Coalson | 8c6f90f | 2001-07-19 17:07:13 +0000 | [diff] [blame] | 175 | int log2cmax; |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 176 | |
Josh Coalson | 765ff50 | 2002-08-27 05:46:11 +0000 | [diff] [blame] | 177 | (void)frexp(cmax, &log2cmax); |
Josh Coalson | 8c6f90f | 2001-07-19 17:07:13 +0000 | [diff] [blame] | 178 | log2cmax--; |
| 179 | *shift = (int)precision - log2cmax - 1; |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 180 | |
| 181 | if(*shift < min_shiftlimit || *shift > max_shiftlimit) { |
Josh Coalson | eac1024 | 2002-10-04 05:25:54 +0000 | [diff] [blame] | 182 | #if 0 |
| 183 | /*@@@ this does not seem to help at all, but was not extensively tested either: */ |
| 184 | if(*shift > max_shiftlimit) |
| 185 | *shift = max_shiftlimit; |
| 186 | else |
| 187 | #endif |
| 188 | return 1; |
Josh Coalson | c625f90 | 2001-02-28 23:56:03 +0000 | [diff] [blame] | 189 | } |
| 190 | } |
| 191 | |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 192 | if(*shift >= 0) { |
| 193 | for(i = 0; i < order; i++) { |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 194 | qlp_coeff[i] = (FLAC__int32)floor((FLAC__double)lp_coeff[i] * (FLAC__double)(1 << *shift)); |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 195 | |
Josh Coalson | 8c6f90f | 2001-07-19 17:07:13 +0000 | [diff] [blame] | 196 | /* double-check the result */ |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 197 | if(qlp_coeff[i] > qmax || qlp_coeff[i] < qmin) { |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 198 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 199 | fprintf(stderr,"FLAC__lpc_quantize_coefficients: compensating for overflow, qlp_coeff[%u]=%d, lp_coeff[%u]=%f, cmax=%f, precision=%u, shift=%d, q=%f, f(q)=%f\n", i, qlp_coeff[i], i, lp_coeff[i], cmax, precision, *shift, (FLAC__double)lp_coeff[i] * (FLAC__double)(1 << *shift), floor((FLAC__double)lp_coeff[i] * (FLAC__double)(1 << *shift))); |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 200 | #endif |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 201 | cmax *= 2.0; |
| 202 | goto redo_it; |
Josh Coalson | 5975e8a | 2001-07-03 04:10:21 +0000 | [diff] [blame] | 203 | } |
| 204 | } |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 205 | } |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 206 | else { /* (*shift < 0) */ |
| 207 | const int nshift = -(*shift); |
Josh Coalson | 3dbbf94 | 2001-07-12 21:27:40 +0000 | [diff] [blame] | 208 | #ifdef DEBUG |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 209 | fprintf(stderr,"FLAC__lpc_quantize_coefficients: negative shift = %d\n", *shift); |
Josh Coalson | 3dbbf94 | 2001-07-12 21:27:40 +0000 | [diff] [blame] | 210 | #endif |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 211 | for(i = 0; i < order; i++) { |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 212 | qlp_coeff[i] = (FLAC__int32)floor((FLAC__double)lp_coeff[i] / (FLAC__double)(1 << nshift)); |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 213 | |
Josh Coalson | 8c6f90f | 2001-07-19 17:07:13 +0000 | [diff] [blame] | 214 | /* double-check the result */ |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 215 | if(qlp_coeff[i] > qmax || qlp_coeff[i] < qmin) { |
| 216 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 217 | fprintf(stderr,"FLAC__lpc_quantize_coefficients: compensating for overflow, qlp_coeff[%u]=%d, lp_coeff[%u]=%f, cmax=%f, precision=%u, shift=%d, q=%f, f(q)=%f\n", i, qlp_coeff[i], i, lp_coeff[i], cmax, precision, *shift, (FLAC__double)lp_coeff[i] / (FLAC__double)(1 << nshift), floor((FLAC__double)lp_coeff[i] / (FLAC__double)(1 << nshift))); |
Josh Coalson | 4e6b3ac | 2001-07-06 00:37:57 +0000 | [diff] [blame] | 218 | #endif |
| 219 | cmax *= 2.0; |
| 220 | goto redo_it; |
| 221 | } |
| 222 | } |
| 223 | } |
| 224 | |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 225 | return 0; |
| 226 | } |
| 227 | |
Josh Coalson | 7446e18 | 2005-01-26 04:04:38 +0000 | [diff] [blame] | 228 | void FLAC__lpc_compute_residual_from_qlp_coefficients(const FLAC__int32 *data, unsigned data_len, const FLAC__int32 qlp_coeff[], unsigned order, int lp_quantization, FLAC__int32 residual[]) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 229 | { |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 230 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 231 | FLAC__int64 sumo; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 232 | #endif |
| 233 | unsigned i, j; |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 234 | FLAC__int32 sum; |
| 235 | const FLAC__int32 *history; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 236 | |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 237 | #ifdef FLAC__OVERFLOW_DETECT_VERBOSE |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 238 | fprintf(stderr,"FLAC__lpc_compute_residual_from_qlp_coefficients: data_len=%d, order=%u, lpq=%d",data_len,order,lp_quantization); |
| 239 | for(i=0;i<order;i++) |
| 240 | fprintf(stderr,", q[%u]=%d",i,qlp_coeff[i]); |
| 241 | fprintf(stderr,"\n"); |
| 242 | #endif |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 243 | FLAC__ASSERT(order > 0); |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 244 | |
| 245 | for(i = 0; i < data_len; i++) { |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 246 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 247 | sumo = 0; |
| 248 | #endif |
| 249 | sum = 0; |
| 250 | history = data; |
| 251 | for(j = 0; j < order; j++) { |
| 252 | sum += qlp_coeff[j] * (*(--history)); |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 253 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 254 | sumo += (FLAC__int64)qlp_coeff[j] * (FLAC__int64)(*history); |
Josh Coalson | b3538c8 | 2003-01-12 08:42:23 +0000 | [diff] [blame] | 255 | #if defined _MSC_VER |
Josh Coalson | 0c671c8 | 2003-01-08 08:04:42 +0000 | [diff] [blame] | 256 | if(sumo > 2147483647I64 || sumo < -2147483648I64) |
Josh Coalson | fec4a77 | 2004-03-22 05:47:25 +0000 | [diff] [blame] | 257 | fprintf(stderr,"FLAC__lpc_compute_residual_from_qlp_coefficients: OVERFLOW, i=%u, j=%u, c=%d, d=%d, sumo=%I64d\n",i,j,qlp_coeff[j],*history,sumo); |
Josh Coalson | d37acf4 | 2001-07-09 18:22:46 +0000 | [diff] [blame] | 258 | #else |
| 259 | if(sumo > 2147483647ll || sumo < -2147483648ll) |
Josh Coalson | b35bebd | 2001-07-03 04:37:18 +0000 | [diff] [blame] | 260 | fprintf(stderr,"FLAC__lpc_compute_residual_from_qlp_coefficients: OVERFLOW, i=%u, j=%u, c=%d, d=%d, sumo=%lld\n",i,j,qlp_coeff[j],*history,sumo); |
Josh Coalson | fec4a77 | 2004-03-22 05:47:25 +0000 | [diff] [blame] | 261 | #endif |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 262 | #endif |
| 263 | } |
| 264 | *(residual++) = *(data++) - (sum >> lp_quantization); |
| 265 | } |
| 266 | |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 267 | /* Here's a slower but clearer version: |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 268 | for(i = 0; i < data_len; i++) { |
| 269 | sum = 0; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 270 | for(j = 0; j < order; j++) |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 271 | sum += qlp_coeff[j] * data[i-j-1]; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 272 | residual[i] = data[i] - (sum >> lp_quantization); |
| 273 | } |
| 274 | */ |
| 275 | } |
| 276 | |
Josh Coalson | 7446e18 | 2005-01-26 04:04:38 +0000 | [diff] [blame] | 277 | void FLAC__lpc_compute_residual_from_qlp_coefficients_wide(const FLAC__int32 *data, unsigned data_len, const FLAC__int32 qlp_coeff[], unsigned order, int lp_quantization, FLAC__int32 residual[]) |
Josh Coalson | eac1024 | 2002-10-04 05:25:54 +0000 | [diff] [blame] | 278 | { |
| 279 | unsigned i, j; |
| 280 | FLAC__int64 sum; |
| 281 | const FLAC__int32 *history; |
| 282 | |
| 283 | #ifdef FLAC__OVERFLOW_DETECT_VERBOSE |
| 284 | fprintf(stderr,"FLAC__lpc_compute_residual_from_qlp_coefficients_wide: data_len=%d, order=%u, lpq=%d",data_len,order,lp_quantization); |
| 285 | for(i=0;i<order;i++) |
| 286 | fprintf(stderr,", q[%u]=%d",i,qlp_coeff[i]); |
| 287 | fprintf(stderr,"\n"); |
| 288 | #endif |
| 289 | FLAC__ASSERT(order > 0); |
| 290 | |
| 291 | for(i = 0; i < data_len; i++) { |
| 292 | sum = 0; |
| 293 | history = data; |
| 294 | for(j = 0; j < order; j++) |
| 295 | sum += (FLAC__int64)qlp_coeff[j] * (FLAC__int64)(*(--history)); |
| 296 | #ifdef FLAC__OVERFLOW_DETECT |
| 297 | if(FLAC__bitmath_silog2_wide(sum >> lp_quantization) > 32) { |
| 298 | fprintf(stderr,"FLAC__lpc_compute_residual_from_qlp_coefficients_wide: OVERFLOW, i=%u, sum=%lld\n", i, sum >> lp_quantization); |
| 299 | break; |
| 300 | } |
| 301 | if(FLAC__bitmath_silog2_wide((FLAC__int64)(*data) - (sum >> lp_quantization)) > 32) { |
| 302 | fprintf(stderr,"FLAC__lpc_compute_residual_from_qlp_coefficients_wide: OVERFLOW, i=%u, data=%d, sum=%lld, residual=%lld\n", i, *data, sum >> lp_quantization, (FLAC__int64)(*data) - (sum >> lp_quantization)); |
| 303 | break; |
| 304 | } |
| 305 | #endif |
| 306 | *(residual++) = *(data++) - (FLAC__int32)(sum >> lp_quantization); |
| 307 | } |
| 308 | } |
| 309 | |
Josh Coalson | 5f2b46d | 2004-11-09 01:34:01 +0000 | [diff] [blame] | 310 | #endif /* !defined FLAC__INTEGER_ONLY_LIBRARY */ |
| 311 | |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 312 | void FLAC__lpc_restore_signal(const FLAC__int32 residual[], unsigned data_len, const FLAC__int32 qlp_coeff[], unsigned order, int lp_quantization, FLAC__int32 data[]) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 313 | { |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 314 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 315 | FLAC__int64 sumo; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 316 | #endif |
| 317 | unsigned i, j; |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 318 | FLAC__int32 sum; |
| 319 | const FLAC__int32 *history; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 320 | |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 321 | #ifdef FLAC__OVERFLOW_DETECT_VERBOSE |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 322 | fprintf(stderr,"FLAC__lpc_restore_signal: data_len=%d, order=%u, lpq=%d",data_len,order,lp_quantization); |
| 323 | for(i=0;i<order;i++) |
| 324 | fprintf(stderr,", q[%u]=%d",i,qlp_coeff[i]); |
| 325 | fprintf(stderr,"\n"); |
| 326 | #endif |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 327 | FLAC__ASSERT(order > 0); |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 328 | |
| 329 | for(i = 0; i < data_len; i++) { |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 330 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 331 | sumo = 0; |
| 332 | #endif |
| 333 | sum = 0; |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 334 | history = data; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 335 | for(j = 0; j < order; j++) { |
| 336 | sum += qlp_coeff[j] * (*(--history)); |
Josh Coalson | bb6712e | 2001-04-24 22:54:07 +0000 | [diff] [blame] | 337 | #ifdef FLAC__OVERFLOW_DETECT |
Josh Coalson | 77e3f31 | 2001-06-23 03:03:24 +0000 | [diff] [blame] | 338 | sumo += (FLAC__int64)qlp_coeff[j] * (FLAC__int64)(*history); |
Josh Coalson | b3538c8 | 2003-01-12 08:42:23 +0000 | [diff] [blame] | 339 | #if defined _MSC_VER |
Josh Coalson | 0c671c8 | 2003-01-08 08:04:42 +0000 | [diff] [blame] | 340 | if(sumo > 2147483647I64 || sumo < -2147483648I64) |
Josh Coalson | fec4a77 | 2004-03-22 05:47:25 +0000 | [diff] [blame] | 341 | fprintf(stderr,"FLAC__lpc_restore_signal: OVERFLOW, i=%u, j=%u, c=%d, d=%d, sumo=%I64d\n",i,j,qlp_coeff[j],*history,sumo); |
Josh Coalson | d37acf4 | 2001-07-09 18:22:46 +0000 | [diff] [blame] | 342 | #else |
| 343 | if(sumo > 2147483647ll || sumo < -2147483648ll) |
Josh Coalson | b35bebd | 2001-07-03 04:37:18 +0000 | [diff] [blame] | 344 | fprintf(stderr,"FLAC__lpc_restore_signal: OVERFLOW, i=%u, j=%u, c=%d, d=%d, sumo=%lld\n",i,j,qlp_coeff[j],*history,sumo); |
Josh Coalson | fec4a77 | 2004-03-22 05:47:25 +0000 | [diff] [blame] | 345 | #endif |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 346 | #endif |
| 347 | } |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 348 | *(data++) = *(residual++) + (sum >> lp_quantization); |
| 349 | } |
| 350 | |
| 351 | /* Here's a slower but clearer version: |
| 352 | for(i = 0; i < data_len; i++) { |
| 353 | sum = 0; |
| 354 | for(j = 0; j < order; j++) |
| 355 | sum += qlp_coeff[j] * data[i-j-1]; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 356 | data[i] = residual[i] + (sum >> lp_quantization); |
| 357 | } |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 358 | */ |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 359 | } |
| 360 | |
Josh Coalson | eac1024 | 2002-10-04 05:25:54 +0000 | [diff] [blame] | 361 | void FLAC__lpc_restore_signal_wide(const FLAC__int32 residual[], unsigned data_len, const FLAC__int32 qlp_coeff[], unsigned order, int lp_quantization, FLAC__int32 data[]) |
| 362 | { |
| 363 | unsigned i, j; |
| 364 | FLAC__int64 sum; |
| 365 | const FLAC__int32 *history; |
| 366 | |
| 367 | #ifdef FLAC__OVERFLOW_DETECT_VERBOSE |
| 368 | fprintf(stderr,"FLAC__lpc_restore_signal_wide: data_len=%d, order=%u, lpq=%d",data_len,order,lp_quantization); |
| 369 | for(i=0;i<order;i++) |
| 370 | fprintf(stderr,", q[%u]=%d",i,qlp_coeff[i]); |
| 371 | fprintf(stderr,"\n"); |
| 372 | #endif |
| 373 | FLAC__ASSERT(order > 0); |
| 374 | |
| 375 | for(i = 0; i < data_len; i++) { |
| 376 | sum = 0; |
| 377 | history = data; |
| 378 | for(j = 0; j < order; j++) |
| 379 | sum += (FLAC__int64)qlp_coeff[j] * (FLAC__int64)(*(--history)); |
| 380 | #ifdef FLAC__OVERFLOW_DETECT |
| 381 | if(FLAC__bitmath_silog2_wide(sum >> lp_quantization) > 32) { |
| 382 | fprintf(stderr,"FLAC__lpc_restore_signal_wide: OVERFLOW, i=%u, sum=%lld\n", i, sum >> lp_quantization); |
| 383 | break; |
| 384 | } |
| 385 | if(FLAC__bitmath_silog2_wide((FLAC__int64)(*residual) + (sum >> lp_quantization)) > 32) { |
| 386 | fprintf(stderr,"FLAC__lpc_restore_signal_wide: OVERFLOW, i=%u, residual=%d, sum=%lld, data=%lld\n", i, *residual, sum >> lp_quantization, (FLAC__int64)(*residual) + (sum >> lp_quantization)); |
| 387 | break; |
| 388 | } |
| 389 | #endif |
| 390 | *(data++) = *(residual++) + (FLAC__int32)(sum >> lp_quantization); |
| 391 | } |
| 392 | } |
| 393 | |
Josh Coalson | 5f2b46d | 2004-11-09 01:34:01 +0000 | [diff] [blame] | 394 | #ifndef FLAC__INTEGER_ONLY_LIBRARY |
| 395 | |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 396 | FLAC__double FLAC__lpc_compute_expected_bits_per_residual_sample(FLAC__double lpc_error, unsigned total_samples) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 397 | { |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 398 | FLAC__double error_scale; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 399 | |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 400 | FLAC__ASSERT(total_samples > 0); |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 401 | |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 402 | error_scale = 0.5 * M_LN2 * M_LN2 / (FLAC__double)total_samples; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 403 | |
Josh Coalson | ddc5bc7 | 2002-06-05 05:53:17 +0000 | [diff] [blame] | 404 | return FLAC__lpc_compute_expected_bits_per_residual_sample_with_error_scale(lpc_error, error_scale); |
Josh Coalson | a1b53c4 | 2001-05-24 19:27:08 +0000 | [diff] [blame] | 405 | } |
| 406 | |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 407 | FLAC__double FLAC__lpc_compute_expected_bits_per_residual_sample_with_error_scale(FLAC__double lpc_error, FLAC__double error_scale) |
Josh Coalson | a1b53c4 | 2001-05-24 19:27:08 +0000 | [diff] [blame] | 408 | { |
| 409 | if(lpc_error > 0.0) { |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 410 | FLAC__double bps = (FLAC__double)0.5 * log(error_scale * lpc_error) / M_LN2; |
Josh Coalson | a1b53c4 | 2001-05-24 19:27:08 +0000 | [diff] [blame] | 411 | if(bps >= 0.0) |
| 412 | return bps; |
| 413 | else |
| 414 | return 0.0; |
| 415 | } |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 416 | else if(lpc_error < 0.0) { /* error should not be negative but can happen due to inadequate floating-point resolution */ |
| 417 | return 1e32; |
Josh Coalson | a1b53c4 | 2001-05-24 19:27:08 +0000 | [diff] [blame] | 418 | } |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 419 | else { |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 420 | return 0.0; |
Josh Coalson | 9f77a19 | 2001-02-08 00:26:45 +0000 | [diff] [blame] | 421 | } |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 422 | } |
| 423 | |
Josh Coalson | 6e2b565 | 2006-04-28 00:11:31 +0000 | [diff] [blame] | 424 | unsigned FLAC__lpc_compute_best_order(const FLAC__double lpc_error[], unsigned max_order, unsigned total_samples, unsigned overhead_bits_per_order) |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 425 | { |
Josh Coalson | 6e2b565 | 2006-04-28 00:11:31 +0000 | [diff] [blame] | 426 | unsigned order, index, best_index; /* 'index' the index into lpc_error; index==order-1 since lpc_error[0] is for order==1, lpc_error[1] is for order==2, etc */ |
| 427 | FLAC__double bits, best_bits, error_scale; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 428 | |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 429 | FLAC__ASSERT(max_order > 0); |
| 430 | FLAC__ASSERT(total_samples > 0); |
Josh Coalson | a1b53c4 | 2001-05-24 19:27:08 +0000 | [diff] [blame] | 431 | |
Josh Coalson | 0975843 | 2004-10-20 00:21:50 +0000 | [diff] [blame] | 432 | error_scale = 0.5 * M_LN2 * M_LN2 / (FLAC__double)total_samples; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 433 | |
Josh Coalson | 6e2b565 | 2006-04-28 00:11:31 +0000 | [diff] [blame] | 434 | best_index = 0; |
| 435 | best_bits = (unsigned)(-1); |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 436 | |
Josh Coalson | 6e2b565 | 2006-04-28 00:11:31 +0000 | [diff] [blame] | 437 | for(index = 0, order = 1; index < max_order; index++, order++) { |
| 438 | bits = FLAC__lpc_compute_expected_bits_per_residual_sample_with_error_scale(lpc_error[index], error_scale) * (FLAC__double)(total_samples - order) + (FLAC__double)(order * overhead_bits_per_order); |
| 439 | if(bits < best_bits) { |
| 440 | best_index = index; |
| 441 | best_bits = bits; |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 442 | } |
| 443 | } |
| 444 | |
Josh Coalson | 6e2b565 | 2006-04-28 00:11:31 +0000 | [diff] [blame] | 445 | return best_index+1; /* +1 since index of lpc_error[] is order-1 */ |
Josh Coalson | bb7f6b9 | 2000-12-10 04:09:52 +0000 | [diff] [blame] | 446 | } |
Josh Coalson | 5f2b46d | 2004-11-09 01:34:01 +0000 | [diff] [blame] | 447 | |
| 448 | #endif /* !defined FLAC__INTEGER_ONLY_LIBRARY */ |