715
|
1 /* libFLAC - Free Lossless Audio Codec library
|
|
2 * Copyright (C) 2001,2002,2003,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 "private/bitmath.h"
|
|
37 #include "FLAC/assert.h"
|
|
38
|
|
39 /* An example of what FLAC__bitmath_ilog2() computes:
|
|
40 *
|
|
41 * ilog2( 0) = assertion failure
|
|
42 * ilog2( 1) = 0
|
|
43 * ilog2( 2) = 1
|
|
44 * ilog2( 3) = 1
|
|
45 * ilog2( 4) = 2
|
|
46 * ilog2( 5) = 2
|
|
47 * ilog2( 6) = 2
|
|
48 * ilog2( 7) = 2
|
|
49 * ilog2( 8) = 3
|
|
50 * ilog2( 9) = 3
|
|
51 * ilog2(10) = 3
|
|
52 * ilog2(11) = 3
|
|
53 * ilog2(12) = 3
|
|
54 * ilog2(13) = 3
|
|
55 * ilog2(14) = 3
|
|
56 * ilog2(15) = 3
|
|
57 * ilog2(16) = 4
|
|
58 * ilog2(17) = 4
|
|
59 * ilog2(18) = 4
|
|
60 */
|
|
61 unsigned FLAC__bitmath_ilog2(FLAC__uint32 v)
|
|
62 {
|
|
63 unsigned l = 0;
|
|
64 FLAC__ASSERT(v > 0);
|
|
65 while(v >>= 1)
|
|
66 l++;
|
|
67 return l;
|
|
68 }
|
|
69
|
|
70 unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v)
|
|
71 {
|
|
72 unsigned l = 0;
|
|
73 FLAC__ASSERT(v > 0);
|
|
74 while(v >>= 1)
|
|
75 l++;
|
|
76 return l;
|
|
77 }
|
|
78
|
|
79 /* An example of what FLAC__bitmath_silog2() computes:
|
|
80 *
|
|
81 * silog2(-10) = 5
|
|
82 * silog2(- 9) = 5
|
|
83 * silog2(- 8) = 4
|
|
84 * silog2(- 7) = 4
|
|
85 * silog2(- 6) = 4
|
|
86 * silog2(- 5) = 4
|
|
87 * silog2(- 4) = 3
|
|
88 * silog2(- 3) = 3
|
|
89 * silog2(- 2) = 2
|
|
90 * silog2(- 1) = 2
|
|
91 * silog2( 0) = 0
|
|
92 * silog2( 1) = 2
|
|
93 * silog2( 2) = 3
|
|
94 * silog2( 3) = 3
|
|
95 * silog2( 4) = 4
|
|
96 * silog2( 5) = 4
|
|
97 * silog2( 6) = 4
|
|
98 * silog2( 7) = 4
|
|
99 * silog2( 8) = 5
|
|
100 * silog2( 9) = 5
|
|
101 * silog2( 10) = 5
|
|
102 */
|
|
103 unsigned FLAC__bitmath_silog2(int v)
|
|
104 {
|
|
105 while(1) {
|
|
106 if(v == 0) {
|
|
107 return 0;
|
|
108 }
|
|
109 else if(v > 0) {
|
|
110 unsigned l = 0;
|
|
111 while(v) {
|
|
112 l++;
|
|
113 v >>= 1;
|
|
114 }
|
|
115 return l+1;
|
|
116 }
|
|
117 else if(v == -1) {
|
|
118 return 2;
|
|
119 }
|
|
120 else {
|
|
121 v++;
|
|
122 v = -v;
|
|
123 }
|
|
124 }
|
|
125 }
|
|
126
|
|
127 unsigned FLAC__bitmath_silog2_wide(FLAC__int64 v)
|
|
128 {
|
|
129 while(1) {
|
|
130 if(v == 0) {
|
|
131 return 0;
|
|
132 }
|
|
133 else if(v > 0) {
|
|
134 unsigned l = 0;
|
|
135 while(v) {
|
|
136 l++;
|
|
137 v >>= 1;
|
|
138 }
|
|
139 return l+1;
|
|
140 }
|
|
141 else if(v == -1) {
|
|
142 return 2;
|
|
143 }
|
|
144 else {
|
|
145 v++;
|
|
146 v = -v;
|
|
147 }
|
|
148 }
|
|
149 }
|