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 */ 309
