src/libFLAC/float.c

   1 /* libFLAC - Free Lossless Audio Codec library
   2  * Copyright (C) 2004,2005  Josh Coalson
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  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.
  30  */
  31
  32 #include "FLAC/assert.h"
  33
  34 #include "private/float.h"
  35
  36 #ifdef FLAC__INTEGER_ONLY_LIBRARY
  37
  38 /* adjust for compilers that can't understand using LLU suffix for uint64_t literals */
  39 #ifdef _MSC_VER
  40 #define FLAC__U64L(x) x
  41 #else
  42 #define FLAC__U64L(x) x##LLU
  43 #endif
  44
  45 const FLAC__fixedpoint FLAC__FP_ZERO = 0;
  46 const FLAC__fixedpoint FLAC__FP_ONE_HALF = 0x00008000;
  47 const FLAC__fixedpoint FLAC__FP_ONE = 0x00010000;
  48 const FLAC__fixedpoint FLAC__FP_LN2 = 45426;
  49 const FLAC__fixedpoint FLAC__FP_E = 178145;
  50
  51 /* Lookup tables for Knuth's logarithm algorithm */
  52 #define LOG2_LOOKUP_PRECISION 16
  53 static const FLAC__uint32 log2_lookup[][LOG2_LOOKUP_PRECISION] = {
  54         {
  55                 /*
  56                  * 0 fraction bits
  57                  */
  58                 /* undefined */ 0x00000000,
  59                 /* lg(2/1) = */ 0x00000001,
  60                 /* lg(4/3) = */ 0x00000000,
  61                 /* lg(8/7) = */ 0x00000000,
  62                 /* lg(16/15) = */ 0x00000000,
  63                 /* lg(32/31) = */ 0x00000000,
  64                 /* lg(64/63) = */ 0x00000000,
  65                 /* lg(128/127) = */ 0x00000000,
  66                 /* lg(256/255) = */ 0x00000000,
  67                 /* lg(512/511) = */ 0x00000000,
  68                 /* lg(1024/1023) = */ 0x00000000,
  69                 /* lg(2048/2047) = */ 0x00000000,
  70                 /* lg(4096/4095) = */ 0x00000000,
  71                 /* lg(8192/8191) = */ 0x00000000,
  72                 /* lg(16384/16383) = */ 0x00000000,
  73                 /* lg(32768/32767) = */ 0x00000000
  74         },
  75         {
  76                 /*
  77                  * 4 fraction bits
  78                  */
  79                 /* undefined */ 0x00000000,
  80                 /* lg(2/1) = */ 0x00000010,
  81                 /* lg(4/3) = */ 0x00000007,
  82                 /* lg(8/7) = */ 0x00000003,
  83                 /* lg(16/15) = */ 0x00000001,
  84                 /* lg(32/31) = */ 0x00000001,
  85                 /* lg(64/63) = */ 0x00000000,
  86                 /* lg(128/127) = */ 0x00000000,
  87                 /* lg(256/255) = */ 0x00000000,
  88                 /* lg(512/511) = */ 0x00000000,
  89                 /* lg(1024/1023) = */ 0x00000000,
  90                 /* lg(2048/2047) = */ 0x00000000,
  91                 /* lg(4096/4095) = */ 0x00000000,
  92                 /* lg(8192/8191) = */ 0x00000000,
  93                 /* lg(16384/16383) = */ 0x00000000,
  94                 /* lg(32768/32767) = */ 0x00000000
  95         },
  96         {
  97                 /*
  98                  * 8 fraction bits
  99                  */
 100                 /* undefined */ 0x00000000,
 101                 /* lg(2/1) = */ 0x00000100,
 102                 /* lg(4/3) = */ 0x0000006a,
 103                 /* lg(8/7) = */ 0x00000031,
 104                 /* lg(16/15) = */ 0x00000018,
 105                 /* lg(32/31) = */ 0x0000000c,
 106                 /* lg(64/63) = */ 0x00000006,
 107                 /* lg(128/127) = */ 0x00000003,
 108                 /* lg(256/255) = */ 0x00000001,
 109                 /* lg(512/511) = */ 0x00000001,
 110                 /* lg(1024/1023) = */ 0x00000000,
 111                 /* lg(2048/2047) = */ 0x00000000,
 112                 /* lg(4096/4095) = */ 0x00000000,
 113                 /* lg(8192/8191) = */ 0x00000000,
 114                 /* lg(16384/16383) = */ 0x00000000,
 115                 /* lg(32768/32767) = */ 0x00000000
 116         },
 117         {
 118                 /*
 119                  * 12 fraction bits
 120                  */
 121                 /* undefined */ 0x00000000,
 122                 /* lg(2/1) = */ 0x00001000,
 123                 /* lg(4/3) = */ 0x000006a4,
 124                 /* lg(8/7) = */ 0x00000315,
 125                 /* lg(16/15) = */ 0x0000017d,
 126                 /* lg(32/31) = */ 0x000000bc,
 127                 /* lg(64/63) = */ 0x0000005d,
 128                 /* lg(128/127) = */ 0x0000002e,
 129                 /* lg(256/255) = */ 0x00000017,
 130                 /* lg(512/511) = */ 0x0000000c,
 131                 /* lg(1024/1023) = */ 0x00000006,
 132                 /* lg(2048/2047) = */ 0x00000003,
 133                 /* lg(4096/4095) = */ 0x00000001,
 134                 /* lg(8192/8191) = */ 0x00000001,
 135                 /* lg(16384/16383) = */ 0x00000000,
 136                 /* lg(32768/32767) = */ 0x00000000
 137         },
 138         {
 139                 /*
 140                  * 16 fraction bits
 141                  */
 142                 /* undefined */ 0x00000000,
 143                 /* lg(2/1) = */ 0x00010000,
 144                 /* lg(4/3) = */ 0x00006a40,
 145                 /* lg(8/7) = */ 0x00003151,
 146                 /* lg(16/15) = */ 0x000017d6,
 147                 /* lg(32/31) = */ 0x00000bba,
 148                 /* lg(64/63) = */ 0x000005d1,
 149                 /* lg(128/127) = */ 0x000002e6,
 150                 /* lg(256/255) = */ 0x00000172,
 151                 /* lg(512/511) = */ 0x000000b9,
 152                 /* lg(1024/1023) = */ 0x0000005c,
 153                 /* lg(2048/2047) = */ 0x0000002e,
 154                 /* lg(4096/4095) = */ 0x00000017,
 155                 /* lg(8192/8191) = */ 0x0000000c,
 156                 /* lg(16384/16383) = */ 0x00000006,
 157                 /* lg(32768/32767) = */ 0x00000003
 158         },
 159         {
 160                 /*
 161                  * 20 fraction bits
 162                  */
 163                 /* undefined */ 0x00000000,
 164                 /* lg(2/1) = */ 0x00100000,
 165                 /* lg(4/3) = */ 0x0006a3fe,
 166                 /* lg(8/7) = */ 0x00031513,
 167                 /* lg(16/15) = */ 0x00017d60,
 168                 /* lg(32/31) = */ 0x0000bb9d,
 169                 /* lg(64/63) = */ 0x00005d10,
 170                 /* lg(128/127) = */ 0x00002e59,
 171                 /* lg(256/255) = */ 0x00001721,
 172                 /* lg(512/511) = */ 0x00000b8e,
 173                 /* lg(1024/1023) = */ 0x000005c6,
 174                 /* lg(2048/2047) = */ 0x000002e3,
 175                 /* lg(4096/4095) = */ 0x00000171,
 176                 /* lg(8192/8191) = */ 0x000000b9,
 177                 /* lg(16384/16383) = */ 0x0000005c,
 178                 /* lg(32768/32767) = */ 0x0000002e
 179         },
 180         {
 181                 /*
 182                  * 24 fraction bits
 183                  */
 184                 /* undefined */ 0x00000000,
 185                 /* lg(2/1) = */ 0x01000000,
 186                 /* lg(4/3) = */ 0x006a3fe6,
 187                 /* lg(8/7) = */ 0x00315130,
 188                 /* lg(16/15) = */ 0x0017d605,
 189                 /* lg(32/31) = */ 0x000bb9ca,
 190                 /* lg(64/63) = */ 0x0005d0fc,
 191                 /* lg(128/127) = */ 0x0002e58f,
 192                 /* lg(256/255) = */ 0x0001720e,
 193                 /* lg(512/511) = */ 0x0000b8d8,
 194                 /* lg(1024/1023) = */ 0x00005c61,
 195                 /* lg(2048/2047) = */ 0x00002e2d,
 196                 /* lg(4096/4095) = */ 0x00001716,
 197                 /* lg(8192/8191) = */ 0x00000b8b,
 198                 /* lg(16384/16383) = */ 0x000005c5,
 199                 /* lg(32768/32767) = */ 0x000002e3
 200         },
 201         {
 202                 /*
 203                  * 28 fraction bits
 204                  */
 205                 /* undefined */ 0x00000000,
 206                 /* lg(2/1) = */ 0x10000000,
 207                 /* lg(4/3) = */ 0x06a3fe5c,
 208                 /* lg(8/7) = */ 0x03151301,
 209                 /* lg(16/15) = */ 0x017d6049,
 210                 /* lg(32/31) = */ 0x00bb9ca6,
 211                 /* lg(64/63) = */ 0x005d0fba,
 212                 /* lg(128/127) = */ 0x002e58f7,
 213                 /* lg(256/255) = */ 0x001720da,
 214                 /* lg(512/511) = */ 0x000b8d87,
 215                 /* lg(1024/1023) = */ 0x0005c60b,
 216                 /* lg(2048/2047) = */ 0x0002e2d7,
 217                 /* lg(4096/4095) = */ 0x00017160,
 218                 /* lg(8192/8191) = */ 0x0000b8ad,
 219                 /* lg(16384/16383) = */ 0x00005c56,
 220                 /* lg(32768/32767) = */ 0x00002e2b
 221         }
 222 };
 223
 224 #if 0
 225 static const FLAC__uint64 log2_lookup_wide[] = {
 226         {
 227                 /*
 228                  * 32 fraction bits
 229                  */
 230                 /* undefined */ 0x00000000,
 231                 /* lg(2/1) = */ FLAC__U64L(0x100000000),
 232                 /* lg(4/3) = */ FLAC__U64L(0x6a3fe5c6),
 233                 /* lg(8/7) = */ FLAC__U64L(0x31513015),
 234                 /* lg(16/15) = */ FLAC__U64L(0x17d60497),
 235                 /* lg(32/31) = */ FLAC__U64L(0x0bb9ca65),
 236                 /* lg(64/63) = */ FLAC__U64L(0x05d0fba2),
 237                 /* lg(128/127) = */ FLAC__U64L(0x02e58f74),
 238                 /* lg(256/255) = */ FLAC__U64L(0x01720d9c),
 239                 /* lg(512/511) = */ FLAC__U64L(0x00b8d875),
 240                 /* lg(1024/1023) = */ FLAC__U64L(0x005c60aa),
 241                 /* lg(2048/2047) = */ FLAC__U64L(0x002e2d72),
 242                 /* lg(4096/4095) = */ FLAC__U64L(0x00171600),
 243                 /* lg(8192/8191) = */ FLAC__U64L(0x000b8ad2),
 244                 /* lg(16384/16383) = */ FLAC__U64L(0x0005c55d),
 245                 /* lg(32768/32767) = */ FLAC__U64L(0x0002e2ac)
 246         },
 247         {
 248                 /*
 249                  * 48 fraction bits
 250                  */
 251                 /* undefined */ 0x00000000,
 252                 /* lg(2/1) = */ FLAC__U64L(0x1000000000000),
 253                 /* lg(4/3) = */ FLAC__U64L(0x6a3fe5c60429),
 254                 /* lg(8/7) = */ FLAC__U64L(0x315130157f7a),
 255                 /* lg(16/15) = */ FLAC__U64L(0x17d60496cfbb),
 256                 /* lg(32/31) = */ FLAC__U64L(0xbb9ca64ecac),
 257                 /* lg(64/63) = */ FLAC__U64L(0x5d0fba187cd),
 258                 /* lg(128/127) = */ FLAC__U64L(0x2e58f7441ee),
 259                 /* lg(256/255) = */ FLAC__U64L(0x1720d9c06a8),
 260                 /* lg(512/511) = */ FLAC__U64L(0xb8d8752173),
 261                 /* lg(1024/1023) = */ FLAC__U64L(0x5c60aa252e),
 262                 /* lg(2048/2047) = */ FLAC__U64L(0x2e2d71b0d8),
 263                 /* lg(4096/4095) = */ FLAC__U64L(0x1716001719),
 264                 /* lg(8192/8191) = */ FLAC__U64L(0xb8ad1de1b),
 265                 /* lg(16384/16383) = */ FLAC__U64L(0x5c55d640d),
 266                 /* lg(32768/32767) = */ FLAC__U64L(0x2e2abcf52)
 267         }
 268 };
 269 #endif
 270
 271 FLAC__uint32 FLAC__fixedpoint_log2(FLAC__uint32 x, unsigned fracbits, unsigned precision)
 272 {
 273         const FLAC__uint32 ONE = (1u << fracbits);
 274         const FLAC__uint32 *table = log2_lookup[fracbits >> 2];
 275
 276         FLAC__ASSERT(fracbits < 32);
 277         FLAC__ASSERT((fracbits & 0x3) == 0);
 278
 279         if(x < ONE)
 280                 return 0;
 281
 282         if(precision > LOG2_LOOKUP_PRECISION)
 283                 precision = LOG2_LOOKUP_PRECISION;
 284
 285         /* Knuth's algorithm for computing logarithms, optimized for base-2 with lookup tables */
 286         {
 287                 FLAC__uint32 y = 0;
 288                 FLAC__uint32 z = x >> 1, k = 1;
 289                 while (x > ONE && k < precision) {
 290                         if (x - z >= ONE) {
 291                                 x -= z;
 292                                 z = x >> k;
 293                                 y += table[k];
 294                         }
 295                         else {
 296                                 z >>= 1;
 297                                 k++;
 298                         }
 299                 }
 300                 return y;
 301         }
 302 }
 303
 304 #endif /* defined FLAC__INTEGER_ONLY_LIBRARY */