ffmpeg / libavutil / integer.c @ 5509bffa
History  View  Annotate  Download (5.69 KB)
1 
/*


2 
* arbitrary precision integers

3 
* Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>

4 
*

5 
* This library is free software; you can redistribute it and/or

6 
* modify it under the terms of the GNU Lesser General Public

7 
* License as published by the Free Software Foundation; either

8 
* version 2 of the License, or (at your option) any later version.

9 
*

10 
* This library is distributed in the hope that it will be useful,

11 
* but WITHOUT ANY WARRANTY; without even the implied warranty of

12 
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

13 
* Lesser General Public License for more details.

14 
*

15 
* You should have received a copy of the GNU Lesser General Public

16 
* License along with this library; if not, write to the Free Software

17 
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301 USA

18 
*

19 
*/

20  
21 
/**

22 
* @file integer.c

23 
* arbitrary precision integers.

24 
* @author Michael Niedermayer <michaelni@gmx.at>

25 
*/

26  
27 
#include "common.h" 
28 
#include "integer.h" 
29  
30 
AVInteger av_add_i(AVInteger a, AVInteger b){ 
31 
int i, carry=0; 
32  
33 
for(i=0; i<AV_INTEGER_SIZE; i++){ 
34 
carry= (carry>>16) + a.v[i] + b.v[i];

35 
a.v[i]= carry; 
36 
} 
37 
return a;

38 
} 
39  
40 
AVInteger av_sub_i(AVInteger a, AVInteger b){ 
41 
int i, carry=0; 
42  
43 
for(i=0; i<AV_INTEGER_SIZE; i++){ 
44 
carry= (carry>>16) + a.v[i]  b.v[i];

45 
a.v[i]= carry; 
46 
} 
47 
return a;

48 
} 
49  
50 
/**

51 
* returns the rounded down value of the logarithm of base 2 of the given AVInteger.

52 
* this is simply the index of the most significant bit which is 1. Or 0 of all bits are 0

53 
*/

54 
int av_log2_i(AVInteger a){

55 
int i;

56  
57 
for(i=AV_INTEGER_SIZE1; i>=0; i){ 
58 
if(a.v[i])

59 
return av_log2_16bit(a.v[i]) + 16*i; 
60 
} 
61 
return 1; 
62 
} 
63  
64 
AVInteger av_mul_i(AVInteger a, AVInteger b){ 
65 
AVInteger out; 
66 
int i, j;

67 
int na= (av_log2_i(a)+16) >> 4; 
68 
int nb= (av_log2_i(b)+16) >> 4; 
69  
70 
memset(&out, 0, sizeof(out)); 
71  
72 
for(i=0; i<na; i++){ 
73 
unsigned int carry=0; 
74  
75 
if(a.v[i])

76 
for(j=i; j<AV_INTEGER_SIZE && ji<=nb; j++){

77 
carry= (carry>>16) + out.v[j] + a.v[i]*b.v[ji];

78 
out.v[j]= carry; 
79 
} 
80 
} 
81  
82 
return out;

83 
} 
84  
85 
/**

86 
* returns 0 if a==b, 1 if a>b and 1 if a<b.

87 
*/

88 
int av_cmp_i(AVInteger a, AVInteger b){

89 
int i;

90 
int v= (int16_t)a.v[AV_INTEGER_SIZE1]  (int16_t)b.v[AV_INTEGER_SIZE1]; 
91 
if(v) return (v>>16)1; 
92  
93 
for(i=AV_INTEGER_SIZE2; i>=0; i){ 
94 
int v= a.v[i]  b.v[i];

95 
if(v) return (v>>16)1; 
96 
} 
97 
return 0; 
98 
} 
99  
100 
/**

101 
* bitwise shift.

102 
* @param s the number of bits by which the value should be shifted right, may be negative for shifting left

103 
*/

104 
AVInteger av_shr_i(AVInteger a, int s){

105 
AVInteger out; 
106 
int i;

107  
108 
for(i=0; i<AV_INTEGER_SIZE; i++){ 
109 
int index= i + (s>>4); 
110 
unsigned int v=0; 
111 
if(index+1<AV_INTEGER_SIZE && index+1>=0) v = a.v[index+1]<<16; 
112 
if(index <AV_INTEGER_SIZE && index >=0) v+= a.v[index ]; 
113 
out.v[i]= v >> (s&15);

114 
} 
115 
return out;

116 
} 
117  
118 
/**

119 
* returns a % b.

120 
* @param quot a/b will be stored here

121 
*/

122 
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ 
123 
int i= av_log2_i(a)  av_log2_i(b);

124 
AVInteger quot_temp; 
125 
if(!quot) quot = "_temp;

126  
127 
assert((int16_t)a[AV_INTEGER_SIZE1] >= 0 && (int16_t)b[AV_INTEGER_SIZE1] >= 0); 
128 
assert(av_log2(b)>=0);

129  
130 
if(i > 0) 
131 
b= av_shr_i(b, i); 
132  
133 
memset(quot, 0, sizeof(AVInteger)); 
134  
135 
while(i >= 0){ 
136 
*quot= av_shr_i(*quot, 1);

137 
if(av_cmp_i(a, b) >= 0){ 
138 
a= av_sub_i(a, b); 
139 
quot>v[0] += 1; 
140 
} 
141 
b= av_shr_i(b, 1);

142 
} 
143 
return a;

144 
} 
145  
146 
/**

147 
* returns a/b.

148 
*/

149 
AVInteger av_div_i(AVInteger a, AVInteger b){ 
150 
AVInteger quot; 
151 
av_mod_i(", a, b); 
152 
return quot;

153 
} 
154  
155 
/**

156 
* converts the given int64_t to an AVInteger.

157 
*/

158 
AVInteger av_int2i(int64_t a){ 
159 
AVInteger out; 
160 
int i;

161  
162 
for(i=0; i<AV_INTEGER_SIZE; i++){ 
163 
out.v[i]= a; 
164 
a>>=16;

165 
} 
166 
return out;

167 
} 
168  
169 
/**

170 
* converts the given AVInteger to an int64_t.

171 
* if the AVInteger is too large to fit into an int64_t,

172 
* then only the least significant 64bit will be used

173 
*/

174 
int64_t av_i2int(AVInteger a){ 
175 
int i;

176 
int64_t out=(int8_t)a.v[AV_INTEGER_SIZE1];

177  
178 
for(i= AV_INTEGER_SIZE2; i>=0; i){ 
179 
out = (out<<16) + a.v[i];

180 
} 
181 
return out;

182 
} 
183  
184 
#if 0

185 
#undef NDEBUG

186 
#include <assert.h>

187 

188 
const uint8_t ff_log2_tab[256]={

189 
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,

190 
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,

191 
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,

192 
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,

193 
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,

194 
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,

195 
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,

196 
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7

197 
};

198 

199 
main(){

200 
int64_t a,b;

201 

202 
for(a=7; a<256*256*256; a+=13215){

203 
for(b=3; b<256*256*256; b+=27118){

204 
AVInteger ai= av_int2i(a);

205 
AVInteger bi= av_int2i(b);

206 

207 
assert(av_i2int(ai) == a);

208 
assert(av_i2int(bi) == b);

209 
assert(av_i2int(av_add_i(ai,bi)) == a+b);

210 
assert(av_i2int(av_sub_i(ai,bi)) == ab);

211 
assert(av_i2int(av_mul_i(ai,bi)) == a*b);

212 
assert(av_i2int(av_shr_i(ai, 9)) == a>>9);

213 
assert(av_i2int(av_shr_i(ai,9)) == a<<9);

214 
assert(av_i2int(av_shr_i(ai, 17)) == a>>17);

215 
assert(av_i2int(av_shr_i(ai,17)) == a<<17);

216 
assert(av_log2_i(ai) == av_log2(a));

217 
assert(av_i2int(av_div_i(ai,bi)) == a/b);

218 
}

219 
}

220 
}

221 
#endif
