src/libFLAC/float.c

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