FLAC/src/fixed.c

   1 /* libFLAC - Free Lossless Audio Codec library
   2  * Copyright (C) 2000-2009  Josh Coalson
   3  * Copyright (C) 2011-2022  Xiph.Org Foundation
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *
  12  * - Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  *
  16  * - Neither the name of the Xiph.org Foundation nor the names of its
  17  * contributors may be used to endorse or promote products derived from
  18  * this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
  24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 #ifdef HAVE_CONFIG_H
  34 #  include <config.h>
  35 #endif
  36
  37 #include <math.h>
  38 #include <string.h>
  39 #include "share/compat.h"
  40 #include "private/bitmath.h"
  41 #include "private/fixed.h"
  42 #include "private/macros.h"
  43 #include "FLAC/assert.h"
  44
  45 #ifdef local_abs
  46 #undef local_abs
  47 #endif
  48 #define local_abs(x) ((uint32_t)((x)<0? -(x) : (x)))
  49
  50 #ifdef local_abs64
  51 #undef local_abs64
  52 #endif
  53 #define local_abs64(x) ((uint64_t)((x)<0? -(x) : (x)))
  54
  55 #ifdef FLAC__INTEGER_ONLY_LIBRARY
  56 /* rbps stands for residual bits per sample
  57  *
  58  *             (ln(2) * err)
  59  * rbps = log  (-----------)
  60  *           2 (     n     )
  61  */
  62 static FLAC__fixedpoint local__compute_rbps_integerized(FLAC__uint32 err, FLAC__uint32 n)
  63 {
  64         FLAC__uint32 rbps;
  65         uint32_t bits; /* the number of bits required to represent a number */
  66         int fracbits; /* the number of bits of rbps that comprise the fractional part */
  67
  68         FLAC__ASSERT(sizeof(rbps) == sizeof(FLAC__fixedpoint));
  69         FLAC__ASSERT(err > 0);
  70         FLAC__ASSERT(n > 0);
  71
  72         FLAC__ASSERT(n <= FLAC__MAX_BLOCK_SIZE);
  73         if(err <= n)
  74                 return 0;
  75         /*
  76          * The above two things tell us 1) n fits in 16 bits; 2) err/n > 1.
  77          * These allow us later to know we won't lose too much precision in the
  78          * fixed-point division (err<<fracbits)/n.
  79          */
  80
  81         fracbits = (8*sizeof(err)) - (FLAC__bitmath_ilog2(err)+1);
  82
  83         err <<= fracbits;
  84         err /= n;
  85         /* err now holds err/n with fracbits fractional bits */
  86
  87         /*
  88          * Whittle err down to 16 bits max.  16 significant bits is enough for
  89          * our purposes.
  90          */
  91         FLAC__ASSERT(err > 0);
  92         bits = FLAC__bitmath_ilog2(err)+1;
  93         if(bits > 16) {
  94                 err >>= (bits-16);
  95                 fracbits -= (bits-16);
  96         }
  97         rbps = (FLAC__uint32)err;
  98
  99         /* Multiply by fixed-point version of ln(2), with 16 fractional bits */
 100         rbps *= FLAC__FP_LN2;
 101         fracbits += 16;
 102         FLAC__ASSERT(fracbits >= 0);
 103
 104         /* FLAC__fixedpoint_log2 requires fracbits%4 to be 0 */
 105         {
 106                 const int f = fracbits & 3;
 107                 if(f) {
 108                         rbps >>= f;
 109                         fracbits -= f;
 110                 }
 111         }
 112
 113         rbps = FLAC__fixedpoint_log2(rbps, fracbits, (uint32_t)(-1));
 114
 115         if(rbps == 0)
 116                 return 0;
 117
 118         /*
 119          * The return value must have 16 fractional bits.  Since the whole part
 120          * of the base-2 log of a 32 bit number must fit in 5 bits, and fracbits
 121          * must be >= -3, these assertion allows us to be able to shift rbps
 122          * left if necessary to get 16 fracbits without losing any bits of the
 123          * whole part of rbps.
 124          *
 125          * There is a slight chance due to accumulated error that the whole part
 126          * will require 6 bits, so we use 6 in the assertion.  Really though as
 127          * long as it fits in 13 bits (32 - (16 - (-3))) we are fine.
 128          */
 129         FLAC__ASSERT((int)FLAC__bitmath_ilog2(rbps)+1 <= fracbits + 6);
 130         FLAC__ASSERT(fracbits >= -3);
 131
 132         /* now shift the decimal point into place */
 133         if(fracbits < 16)
 134                 return rbps << (16-fracbits);
 135         else if(fracbits > 16)
 136                 return rbps >> (fracbits-16);
 137         else
 138                 return rbps;
 139 }
 140
 141 static FLAC__fixedpoint local__compute_rbps_wide_integerized(FLAC__uint64 err, FLAC__uint32 n)
 142 {
 143         FLAC__uint32 rbps;
 144         uint32_t bits; /* the number of bits required to represent a number */
 145         int fracbits; /* the number of bits of rbps that comprise the fractional part */
 146
 147         FLAC__ASSERT(sizeof(rbps) == sizeof(FLAC__fixedpoint));
 148         FLAC__ASSERT(err > 0);
 149         FLAC__ASSERT(n > 0);
 150
 151         FLAC__ASSERT(n <= FLAC__MAX_BLOCK_SIZE);
 152         if(err <= n)
 153                 return 0;
 154         /*
 155          * The above two things tell us 1) n fits in 16 bits; 2) err/n > 1.
 156          * These allow us later to know we won't lose too much precision in the
 157          * fixed-point division (err<<fracbits)/n.
 158          */
 159
 160         fracbits = (8*sizeof(err)) - (FLAC__bitmath_ilog2_wide(err)+1);
 161
 162         err <<= fracbits;
 163         err /= n;
 164         /* err now holds err/n with fracbits fractional bits */
 165
 166         /*
 167          * Whittle err down to 16 bits max.  16 significant bits is enough for
 168          * our purposes.
 169          */
 170         FLAC__ASSERT(err > 0);
 171         bits = FLAC__bitmath_ilog2_wide(err)+1;
 172         if(bits > 16) {
 173                 err >>= (bits-16);
 174                 fracbits -= (bits-16);
 175         }
 176         rbps = (FLAC__uint32)err;
 177
 178         /* Multiply by fixed-point version of ln(2), with 16 fractional bits */
 179         rbps *= FLAC__FP_LN2;
 180         fracbits += 16;
 181         FLAC__ASSERT(fracbits >= 0);
 182
 183         /* FLAC__fixedpoint_log2 requires fracbits%4 to be 0 */
 184         {
 185                 const int f = fracbits & 3;
 186                 if(f) {
 187                         rbps >>= f;
 188                         fracbits -= f;
 189                 }
 190         }
 191
 192         rbps = FLAC__fixedpoint_log2(rbps, fracbits, (uint32_t)(-1));
 193
 194         if(rbps == 0)
 195                 return 0;
 196
 197         /*
 198          * The return value must have 16 fractional bits.  Since the whole part
 199          * of the base-2 log of a 32 bit number must fit in 5 bits, and fracbits
 200          * must be >= -3, these assertion allows us to be able to shift rbps
 201          * left if necessary to get 16 fracbits without losing any bits of the
 202          * whole part of rbps.
 203          *
 204          * There is a slight chance due to accumulated error that the whole part
 205          * will require 6 bits, so we use 6 in the assertion.  Really though as
 206          * long as it fits in 13 bits (32 - (16 - (-3))) we are fine.
 207          */
 208         FLAC__ASSERT((int)FLAC__bitmath_ilog2(rbps)+1 <= fracbits + 6);
 209         FLAC__ASSERT(fracbits >= -3);
 210
 211         /* now shift the decimal point into place */
 212         if(fracbits < 16)
 213                 return rbps << (16-fracbits);
 214         else if(fracbits > 16)
 215                 return rbps >> (fracbits-16);
 216         else
 217                 return rbps;
 218 }
 219 #endif
 220
 221 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 222 uint32_t FLAC__fixed_compute_best_predictor(const FLAC__int32 data[], uint32_t data_len, float residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 223 #else
 224 uint32_t FLAC__fixed_compute_best_predictor(const FLAC__int32 data[], uint32_t data_len, FLAC__fixedpoint residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 225 #endif
 226 {
 227         FLAC__uint32 total_error_0 = 0, total_error_1 = 0, total_error_2 = 0, total_error_3 = 0, total_error_4 = 0;
 228         uint32_t order;
 229 #if 0
 230         /* This code has been around a long time, and was written when compilers weren't able
 231          * to vectorize code. These days, compilers are better in optimizing the next block
 232          * which is also much more readable
 233          */
 234         FLAC__int32 last_error_0 = data[-1];
 235         FLAC__int32 last_error_1 = data[-1] - data[-2];
 236         FLAC__int32 last_error_2 = last_error_1 - (data[-2] - data[-3]);
 237         FLAC__int32 last_error_3 = last_error_2 - (data[-2] - 2*data[-3] + data[-4]);
 238         FLAC__int32 error, save;
 239         /* total_error_* are 64-bits to avoid overflow when encoding
 240          * erratic signals when the bits-per-sample and blocksize are
 241          * large.
 242          */
 243         for(uint32_t i = 0; i < data_len; i++) {
 244                 error  = data[i]     ; total_error_0 += local_abs(error);                      save = error;
 245                 error -= last_error_0; total_error_1 += local_abs(error); last_error_0 = save; save = error;
 246                 error -= last_error_1; total_error_2 += local_abs(error); last_error_1 = save; save = error;
 247                 error -= last_error_2; total_error_3 += local_abs(error); last_error_2 = save; save = error;
 248                 error -= last_error_3; total_error_4 += local_abs(error); last_error_3 = save;
 249         }
 250 #else
 251         for(int i = 0; i < (int)data_len; i++) {
 252                 total_error_0 += local_abs(data[i]);
 253                 total_error_1 += local_abs(data[i] - data[i-1]);
 254                 total_error_2 += local_abs(data[i] - 2 * data[i-1] + data[i-2]);
 255                 total_error_3 += local_abs(data[i] - 3 * data[i-1] + 3 * data[i-2] - data[i-3]);
 256                 total_error_4 += local_abs(data[i] - 4 * data[i-1] + 6 * data[i-2] - 4 * data[i-3] + data[i-4]);
 257         }
 258 #endif
 259
 260
 261         /* prefer lower order */
 262         if(total_error_0 <= flac_min(flac_min(flac_min(total_error_1, total_error_2), total_error_3), total_error_4))
 263                 order = 0;
 264         else if(total_error_1 <= flac_min(flac_min(total_error_2, total_error_3), total_error_4))
 265                 order = 1;
 266         else if(total_error_2 <= flac_min(total_error_3, total_error_4))
 267                 order = 2;
 268         else if(total_error_3 <= total_error_4)
 269                 order = 3;
 270         else
 271                 order = 4;
 272
 273         /* Estimate the expected number of bits per residual signal sample. */
 274         /* 'total_error*' is linearly related to the variance of the residual */
 275         /* signal, so we use it directly to compute E(|x|) */
 276         FLAC__ASSERT(data_len > 0 || total_error_0 == 0);
 277         FLAC__ASSERT(data_len > 0 || total_error_1 == 0);
 278         FLAC__ASSERT(data_len > 0 || total_error_2 == 0);
 279         FLAC__ASSERT(data_len > 0 || total_error_3 == 0);
 280         FLAC__ASSERT(data_len > 0 || total_error_4 == 0);
 281 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 282         residual_bits_per_sample[0] = (float)((total_error_0 > 0) ? log(M_LN2 * (double)total_error_0 / (double)data_len) / M_LN2 : 0.0);
 283         residual_bits_per_sample[1] = (float)((total_error_1 > 0) ? log(M_LN2 * (double)total_error_1 / (double)data_len) / M_LN2 : 0.0);
 284         residual_bits_per_sample[2] = (float)((total_error_2 > 0) ? log(M_LN2 * (double)total_error_2 / (double)data_len) / M_LN2 : 0.0);
 285         residual_bits_per_sample[3] = (float)((total_error_3 > 0) ? log(M_LN2 * (double)total_error_3 / (double)data_len) / M_LN2 : 0.0);
 286         residual_bits_per_sample[4] = (float)((total_error_4 > 0) ? log(M_LN2 * (double)total_error_4 / (double)data_len) / M_LN2 : 0.0);
 287 #else
 288         residual_bits_per_sample[0] = (total_error_0 > 0) ? local__compute_rbps_integerized(total_error_0, data_len) : 0;
 289         residual_bits_per_sample[1] = (total_error_1 > 0) ? local__compute_rbps_integerized(total_error_1, data_len) : 0;
 290         residual_bits_per_sample[2] = (total_error_2 > 0) ? local__compute_rbps_integerized(total_error_2, data_len) : 0;
 291         residual_bits_per_sample[3] = (total_error_3 > 0) ? local__compute_rbps_integerized(total_error_3, data_len) : 0;
 292         residual_bits_per_sample[4] = (total_error_4 > 0) ? local__compute_rbps_integerized(total_error_4, data_len) : 0;
 293 #endif
 294
 295         return order;
 296 }
 297
 298 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 299 uint32_t FLAC__fixed_compute_best_predictor_wide(const FLAC__int32 data[], uint32_t data_len, float residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 300 #else
 301 uint32_t FLAC__fixed_compute_best_predictor_wide(const FLAC__int32 data[], uint32_t data_len, FLAC__fixedpoint residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 302 #endif
 303 {
 304         FLAC__uint64 total_error_0 = 0, total_error_1 = 0, total_error_2 = 0, total_error_3 = 0, total_error_4 = 0;
 305         uint32_t order;
 306
 307         for(int i = 0; i < (int)data_len; i++) {
 308                 total_error_0 += local_abs(data[i]);
 309                 total_error_1 += local_abs(data[i] - data[i-1]);
 310                 total_error_2 += local_abs(data[i] - 2 * data[i-1] + data[i-2]);
 311                 total_error_3 += local_abs(data[i] - 3 * data[i-1] + 3 * data[i-2] - data[i-3]);
 312                 total_error_4 += local_abs(data[i] - 4 * data[i-1] + 6 * data[i-2] - 4 * data[i-3] + data[i-4]);
 313         }
 314
 315         /* prefer lower order */
 316         if(total_error_0 <= flac_min(flac_min(flac_min(total_error_1, total_error_2), total_error_3), total_error_4))
 317                 order = 0;
 318         else if(total_error_1 <= flac_min(flac_min(total_error_2, total_error_3), total_error_4))
 319                 order = 1;
 320         else if(total_error_2 <= flac_min(total_error_3, total_error_4))
 321                 order = 2;
 322         else if(total_error_3 <= total_error_4)
 323                 order = 3;
 324         else
 325                 order = 4;
 326
 327         /* Estimate the expected number of bits per residual signal sample. */
 328         /* 'total_error*' is linearly related to the variance of the residual */
 329         /* signal, so we use it directly to compute E(|x|) */
 330         FLAC__ASSERT(data_len > 0 || total_error_0 == 0);
 331         FLAC__ASSERT(data_len > 0 || total_error_1 == 0);
 332         FLAC__ASSERT(data_len > 0 || total_error_2 == 0);
 333         FLAC__ASSERT(data_len > 0 || total_error_3 == 0);
 334         FLAC__ASSERT(data_len > 0 || total_error_4 == 0);
 335 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 336         residual_bits_per_sample[0] = (float)((total_error_0 > 0) ? log(M_LN2 * (double)total_error_0 / (double)data_len) / M_LN2 : 0.0);
 337         residual_bits_per_sample[1] = (float)((total_error_1 > 0) ? log(M_LN2 * (double)total_error_1 / (double)data_len) / M_LN2 : 0.0);
 338         residual_bits_per_sample[2] = (float)((total_error_2 > 0) ? log(M_LN2 * (double)total_error_2 / (double)data_len) / M_LN2 : 0.0);
 339         residual_bits_per_sample[3] = (float)((total_error_3 > 0) ? log(M_LN2 * (double)total_error_3 / (double)data_len) / M_LN2 : 0.0);
 340         residual_bits_per_sample[4] = (float)((total_error_4 > 0) ? log(M_LN2 * (double)total_error_4 / (double)data_len) / M_LN2 : 0.0);
 341 #else
 342         residual_bits_per_sample[0] = (total_error_0 > 0) ? local__compute_rbps_wide_integerized(total_error_0, data_len) : 0;
 343         residual_bits_per_sample[1] = (total_error_1 > 0) ? local__compute_rbps_wide_integerized(total_error_1, data_len) : 0;
 344         residual_bits_per_sample[2] = (total_error_2 > 0) ? local__compute_rbps_wide_integerized(total_error_2, data_len) : 0;
 345         residual_bits_per_sample[3] = (total_error_3 > 0) ? local__compute_rbps_wide_integerized(total_error_3, data_len) : 0;
 346         residual_bits_per_sample[4] = (total_error_4 > 0) ? local__compute_rbps_wide_integerized(total_error_4, data_len) : 0;
 347 #endif
 348
 349         return order;
 350 }
 351
 352 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 353 #define CHECK_ORDER_IS_VALID(macro_order)               \
 354 if(order_##macro_order##_is_valid && total_error_##macro_order < smallest_error) { \
 355         order = macro_order;                            \
 356         smallest_error = total_error_##macro_order ;    \
 357         residual_bits_per_sample[ macro_order ] = (float)((total_error_0 > 0) ? log(M_LN2 * (double)total_error_0 / (double)data_len) / M_LN2 : 0.0); \
 358 }                                                       \
 359 else                                                    \
 360         residual_bits_per_sample[ macro_order ] = 34.0f;
 361 #else
 362 #define CHECK_ORDER_IS_VALID(macro_order)               \
 363 if(order_##macro_order##_is_valid && total_error_##macro_order < smallest_error) { \
 364         order = macro_order;                            \
 365         smallest_error = total_error_##macro_order ;    \
 366         residual_bits_per_sample[ macro_order ] = (total_error_##macro_order > 0) ? local__compute_rbps_wide_integerized(total_error_##macro_order, data_len) : 0; \
 367 }                                                       \
 368 else                                                    \
 369         residual_bits_per_sample[ macro_order ] = 34 * FLAC__FP_ONE;
 370 #endif
 371
 372
 373 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 374 uint32_t FLAC__fixed_compute_best_predictor_limit_residual(const FLAC__int32 data[], uint32_t data_len, float residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 375 #else
 376 uint32_t FLAC__fixed_compute_best_predictor_limit_residual(const FLAC__int32 data[], uint32_t data_len, FLAC__fixedpoint residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 377 #endif
 378 {
 379         FLAC__uint64 total_error_0 = 0, total_error_1 = 0, total_error_2 = 0, total_error_3 = 0, total_error_4 = 0, smallest_error = UINT64_MAX;
 380         FLAC__uint64 error_0, error_1, error_2, error_3, error_4;
 381         FLAC__bool order_0_is_valid = true, order_1_is_valid = true, order_2_is_valid = true, order_3_is_valid = true, order_4_is_valid = true;
 382         uint32_t order = 0;
 383
 384         for(int i = 0; i < (int)data_len; i++) {
 385                 error_0 = local_abs64((FLAC__int64)data[i]);
 386                 error_1 = (i > 0) ? local_abs64((FLAC__int64)data[i] - data[i-1]) : 0 ;
 387                 error_2 = (i > 1) ? local_abs64((FLAC__int64)data[i] - 2 * (FLAC__int64)data[i-1] + data[i-2]) : 0;
 388                 error_3 = (i > 2) ? local_abs64((FLAC__int64)data[i] - 3 * (FLAC__int64)data[i-1] + 3 * (FLAC__int64)data[i-2] - data[i-3]) : 0;
 389                 error_4 = (i > 3) ? local_abs64((FLAC__int64)data[i] - 4 * (FLAC__int64)data[i-1] + 6 * (FLAC__int64)data[i-2] - 4 * (FLAC__int64)data[i-3] + data[i-4]) : 0;
 390
 391                 total_error_0 += error_0;
 392                 total_error_1 += error_1;
 393                 total_error_2 += error_2;
 394                 total_error_3 += error_3;
 395                 total_error_4 += error_4;
 396
 397                 /* residual must not be INT32_MIN because abs(INT32_MIN) is undefined */
 398                 if(error_0 > INT32_MAX)
 399                         order_0_is_valid = false;
 400                 if(error_1 > INT32_MAX)
 401                         order_1_is_valid = false;
 402                 if(error_2 > INT32_MAX)
 403                         order_2_is_valid = false;
 404                 if(error_3 > INT32_MAX)
 405                         order_3_is_valid = false;
 406                 if(error_4 > INT32_MAX)
 407                         order_4_is_valid = false;
 408         }
 409
 410         CHECK_ORDER_IS_VALID(0);
 411         CHECK_ORDER_IS_VALID(1);
 412         CHECK_ORDER_IS_VALID(2);
 413         CHECK_ORDER_IS_VALID(3);
 414         CHECK_ORDER_IS_VALID(4);
 415
 416         return order;
 417 }
 418
 419 #ifndef FLAC__INTEGER_ONLY_LIBRARY
 420 uint32_t FLAC__fixed_compute_best_predictor_limit_residual_33bit(const FLAC__int64 data[], uint32_t data_len, float residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 421 #else
 422 uint32_t FLAC__fixed_compute_best_predictor_limit_residual_33bit(const FLAC__int64 data[], uint32_t data_len, FLAC__fixedpoint residual_bits_per_sample[FLAC__MAX_FIXED_ORDER+1])
 423 #endif
 424 {
 425         FLAC__uint64 total_error_0 = 0, total_error_1 = 0, total_error_2 = 0, total_error_3 = 0, total_error_4 = 0, smallest_error = UINT64_MAX;
 426         FLAC__uint64 error_0, error_1, error_2, error_3, error_4;
 427         FLAC__bool order_0_is_valid = true, order_1_is_valid = true, order_2_is_valid = true, order_3_is_valid = true, order_4_is_valid = true;
 428         uint32_t order = 0;
 429
 430         for(int i = 0; i < (int)data_len; i++) {
 431                 error_0 = local_abs64(data[i]);
 432                 error_1 = (i > 0) ? local_abs64(data[i] - data[i-1]) : 0 ;
 433                 error_2 = (i > 1) ? local_abs64(data[i] - 2 * data[i-1] + data[i-2]) : 0;
 434                 error_3 = (i > 2) ? local_abs64(data[i] - 3 * data[i-1] + 3 * data[i-2] - data[i-3]) : 0;
 435                 error_4 = (i > 3) ? local_abs64(data[i] - 4 * data[i-1] + 6 * data[i-2] - 4 * data[i-3] + data[i-4]) : 0;
 436
 437                 total_error_0 += error_0;
 438                 total_error_1 += error_1;
 439                 total_error_2 += error_2;
 440                 total_error_3 += error_3;
 441                 total_error_4 += error_4;
 442
 443                 /* residual must not be INT32_MIN because abs(INT32_MIN) is undefined */
 444                 if(error_0 > INT32_MAX)
 445                         order_0_is_valid = false;
 446                 if(error_1 > INT32_MAX)
 447                         order_1_is_valid = false;
 448                 if(error_2 > INT32_MAX)
 449                         order_2_is_valid = false;
 450                 if(error_3 > INT32_MAX)
 451                         order_3_is_valid = false;
 452                 if(error_4 > INT32_MAX)
 453                         order_4_is_valid = false;
 454         }
 455
 456         CHECK_ORDER_IS_VALID(0);
 457         CHECK_ORDER_IS_VALID(1);
 458         CHECK_ORDER_IS_VALID(2);
 459         CHECK_ORDER_IS_VALID(3);
 460         CHECK_ORDER_IS_VALID(4);
 461
 462         return order;
 463 }
 464
 465 void FLAC__fixed_compute_residual(const FLAC__int32 data[], uint32_t data_len, uint32_t order, FLAC__int32 residual[])
 466 {
 467         const int idata_len = (int)data_len;
 468         int i;
 469
 470         switch(order) {
 471                 case 0:
 472                         FLAC__ASSERT(sizeof(residual[0]) == sizeof(data[0]));
 473                         memcpy(residual, data, sizeof(residual[0])*data_len);
 474                         break;
 475                 case 1:
 476                         for(i = 0; i < idata_len; i++)
 477                                 residual[i] = data[i] - data[i-1];
 478                         break;
 479                 case 2:
 480                         for(i = 0; i < idata_len; i++)
 481                                 residual[i] = data[i] - 2*data[i-1] + data[i-2];
 482                         break;
 483                 case 3:
 484                         for(i = 0; i < idata_len; i++)
 485                                 residual[i] = data[i] - 3*data[i-1] + 3*data[i-2] - data[i-3];
 486                         break;
 487                 case 4:
 488                         for(i = 0; i < idata_len; i++)
 489                                 residual[i] = data[i] - 4*data[i-1] + 6*data[i-2] - 4*data[i-3] + data[i-4];
 490                         break;
 491                 default:
 492                         FLAC__ASSERT(0);
 493         }
 494 }
 495
 496 void FLAC__fixed_compute_residual_wide(const FLAC__int32 data[], uint32_t data_len, uint32_t order, FLAC__int32 residual[])
 497 {
 498         const int idata_len = (int)data_len;
 499         int i;
 500
 501         switch(order) {
 502                 case 0:
 503                         FLAC__ASSERT(sizeof(residual[0]) == sizeof(data[0]));
 504                         memcpy(residual, data, sizeof(residual[0])*data_len);
 505                         break;
 506                 case 1:
 507                         for(i = 0; i < idata_len; i++)
 508                                 residual[i] = (FLAC__int64)data[i] - data[i-1];
 509                         break;
 510                 case 2:
 511                         for(i = 0; i < idata_len; i++)
 512                                 residual[i] = (FLAC__int64)data[i] - 2*(FLAC__int64)data[i-1] + data[i-2];
 513                         break;
 514                 case 3:
 515                         for(i = 0; i < idata_len; i++)
 516                                 residual[i] = (FLAC__int64)data[i] - 3*(FLAC__int64)data[i-1] + 3*(FLAC__int64)data[i-2] - data[i-3];
 517                         break;
 518                 case 4:
 519                         for(i = 0; i < idata_len; i++)
 520                                 residual[i] = (FLAC__int64)data[i] - 4*(FLAC__int64)data[i-1] + 6*(FLAC__int64)data[i-2] - 4*(FLAC__int64)data[i-3] + data[i-4];
 521                         break;
 522                 default:
 523                         FLAC__ASSERT(0);
 524         }
 525 }
 526
 527 void FLAC__fixed_compute_residual_wide_33bit(const FLAC__int64 data[], uint32_t data_len, uint32_t order, FLAC__int32 residual[])
 528 {
 529         const int idata_len = (int)data_len;
 530         int i;
 531
 532         switch(order) {
 533                 case 0:
 534                         for(i = 0; i < idata_len; i++)
 535                                 residual[i] = data[i];
 536                         break;
 537                 case 1:
 538                         for(i = 0; i < idata_len; i++)
 539                                 residual[i] = data[i] - data[i-1];
 540                         break;
 541                 case 2:
 542                         for(i = 0; i < idata_len; i++)
 543                                 residual[i] = data[i] - 2*data[i-1] + data[i-2];
 544                         break;
 545                 case 3:
 546                         for(i = 0; i < idata_len; i++)
 547                                 residual[i] = data[i] - 3*data[i-1] + 3*data[i-2] - data[i-3];
 548                         break;
 549                 case 4:
 550                         for(i = 0; i < idata_len; i++)
 551                                 residual[i] = data[i] - 4*data[i-1] + 6*data[i-2] - 4*data[i-3] + data[i-4];
 552                         break;
 553                 default:
 554                         FLAC__ASSERT(0);
 555         }
 556 }
 557
 558 #ifdef FUZZING_BUILD_MODE_NO_SANITIZE_SIGNED_INTEGER_OVERFLOW
 559 /* The attribute below is to silence the undefined sanitizer of oss-fuzz.
 560  * Because fuzzing feeds bogus predictors and residual samples to the
 561  * decoder, having overflows in this section is unavoidable. Also,
 562  * because the calculated values are audio path only, there is no
 563  * potential for security problems */
 564 __attribute__((no_sanitize("signed-integer-overflow")))
 565 #endif
 566 void FLAC__fixed_restore_signal(const FLAC__int32 residual[], uint32_t data_len, uint32_t order, FLAC__int32 data[])
 567 {
 568         int i, idata_len = (int)data_len;
 569
 570         switch(order) {
 571                 case 0:
 572                         FLAC__ASSERT(sizeof(residual[0]) == sizeof(data[0]));
 573                         memcpy(data, residual, sizeof(residual[0])*data_len);
 574                         break;
 575                 case 1:
 576                         for(i = 0; i < idata_len; i++)
 577                                 data[i] = residual[i] + data[i-1];
 578                         break;
 579                 case 2:
 580                         for(i = 0; i < idata_len; i++)
 581                                 data[i] = residual[i] + 2*data[i-1] - data[i-2];
 582                         break;
 583                 case 3:
 584                         for(i = 0; i < idata_len; i++)
 585                                 data[i] = residual[i] + 3*data[i-1] - 3*data[i-2] + data[i-3];
 586                         break;
 587                 case 4:
 588                         for(i = 0; i < idata_len; i++)
 589                                 data[i] = residual[i] + 4*data[i-1] - 6*data[i-2] + 4*data[i-3] - data[i-4];
 590                         break;
 591                 default:
 592                         FLAC__ASSERT(0);
 593         }
 594 }
 595
 596 void FLAC__fixed_restore_signal_wide(const FLAC__int32 residual[], uint32_t data_len, uint32_t order, FLAC__int32 data[])
 597 {
 598         int i, idata_len = (int)data_len;
 599
 600         switch(order) {
 601                 case 0:
 602                         FLAC__ASSERT(sizeof(residual[0]) == sizeof(data[0]));
 603                         memcpy(data, residual, sizeof(residual[0])*data_len);
 604                         break;
 605                 case 1:
 606                         for(i = 0; i < idata_len; i++)
 607                                 data[i] = (FLAC__int64)residual[i] + (FLAC__int64)data[i-1];
 608                         break;
 609                 case 2:
 610                         for(i = 0; i < idata_len; i++)
 611                                 data[i] = (FLAC__int64)residual[i] + 2*(FLAC__int64)data[i-1] - (FLAC__int64)data[i-2];
 612                         break;
 613                 case 3:
 614                         for(i = 0; i < idata_len; i++)
 615                                 data[i] = (FLAC__int64)residual[i] + 3*(FLAC__int64)data[i-1] - 3*(FLAC__int64)data[i-2] + (FLAC__int64)data[i-3];
 616                         break;
 617                 case 4:
 618                         for(i = 0; i < idata_len; i++)
 619                                 data[i] = (FLAC__int64)residual[i] + 4*(FLAC__int64)data[i-1] - 6*(FLAC__int64)data[i-2] + 4*(FLAC__int64)data[i-3] - (FLAC__int64)data[i-4];
 620                         break;
 621                 default:
 622                         FLAC__ASSERT(0);
 623         }
 624 }
 625
 626 #ifdef FUZZING_BUILD_MODE_NO_SANITIZE_SIGNED_INTEGER_OVERFLOW
 627 /* The attribute below is to silence the undefined sanitizer of oss-fuzz.
 628  * Because fuzzing feeds bogus predictors and residual samples to the
 629  * decoder, having overflows in this section is unavoidable. Also,
 630  * because the calculated values are audio path only, there is no
 631  * potential for security problems */
 632 __attribute__((no_sanitize("signed-integer-overflow")))
 633 #endif
 634 void FLAC__fixed_restore_signal_wide_33bit(const FLAC__int32 residual[], uint32_t data_len, uint32_t order, FLAC__int64 data[])
 635 {
 636         int i, idata_len = (int)data_len;
 637
 638         switch(order) {
 639                 case 0:
 640                         for(i = 0; i < idata_len; i++)
 641                                 data[i] = residual[i];
 642                         break;
 643                 case 1:
 644                         for(i = 0; i < idata_len; i++)
 645                                 data[i] = (FLAC__int64)residual[i] + data[i-1];
 646                         break;
 647                 case 2:
 648                         for(i = 0; i < idata_len; i++)
 649                                 data[i] = (FLAC__int64)residual[i] + 2*data[i-1] - data[i-2];
 650                         break;
 651                 case 3:
 652                         for(i = 0; i < idata_len; i++)
 653                                 data[i] = (FLAC__int64)residual[i] + 3*data[i-1] - 3*data[i-2] + data[i-3];
 654                         break;
 655                 case 4:
 656                         for(i = 0; i < idata_len; i++)
 657                                 data[i] = (FLAC__int64)residual[i] + 4*data[i-1] - 6*data[i-2] + 4*data[i-3] - data[i-4];
 658                         break;
 659                 default:
 660                         FLAC__ASSERT(0);
 661         }
 662 }