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