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