src/libFLAC/float.c

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