ffmpeg / libavutil / integer.c @ 10e26bc7
History  View  Annotate  Download (5.04 KB)
1 
/*


2 
* arbitrary precision integers

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

4 
*

5 
* This file is part of FFmpeg.

6 
*

7 
* FFmpeg is free software; you can redistribute it and/or

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

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

10 
* version 2.1 of the License, or (at your option) any later version.

11 
*

12 
* FFmpeg is distributed in the hope that it will be useful,

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

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

15 
* Lesser General Public License for more details.

16 
*

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

18 
* License along with FFmpeg; if not, write to the Free Software

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

20 
*

21 
*/

22  
23 
/**

24 
* @file integer.c

25 
* arbitrary precision integers.

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

27 
*/

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

37 
a.v[i]= carry; 
38 
} 
39 
return a;

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

47 
a.v[i]= carry; 
48 
} 
49 
return a;

50 
} 
51  
52 
int av_log2_i(AVInteger a){

53 
int i;

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

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

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

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

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

76 
out.v[j]= carry; 
77 
} 
78 
} 
79  
80 
return out;

81 
} 
82  
83 
int av_cmp_i(AVInteger a, AVInteger b){

84 
int i;

85 
int v= (int16_t)a.v[AV_INTEGER_SIZE1]  (int16_t)b.v[AV_INTEGER_SIZE1]; 
86 
if(v) return (v>>16)1; 
87  
88 
for(i=AV_INTEGER_SIZE2; i>=0; i){ 
89 
int v= a.v[i]  b.v[i];

90 
if(v) return (v>>16)1; 
91 
} 
92 
return 0; 
93 
} 
94  
95 
AVInteger av_shr_i(AVInteger a, int s){

96 
AVInteger out; 
97 
int i;

98  
99 
for(i=0; i<AV_INTEGER_SIZE; i++){ 
100 
int index= i + (s>>4); 
101 
unsigned int v=0; 
102 
if(index+1<AV_INTEGER_SIZE && index+1>=0) v = a.v[index+1]<<16; 
103 
if(index <AV_INTEGER_SIZE && index >=0) v+= a.v[index ]; 
104 
out.v[i]= v >> (s&15);

105 
} 
106 
return out;

107 
} 
108  
109 
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ 
110 
int i= av_log2_i(a)  av_log2_i(b);

111 
AVInteger quot_temp; 
112 
if(!quot) quot = "_temp;

113  
114 
assert((int16_t)a[AV_INTEGER_SIZE1] >= 0 && (int16_t)b[AV_INTEGER_SIZE1] >= 0); 
115 
assert(av_log2(b)>=0);

116  
117 
if(i > 0) 
118 
b= av_shr_i(b, i); 
119  
120 
memset(quot, 0, sizeof(AVInteger)); 
121  
122 
while(i >= 0){ 
123 
*quot= av_shr_i(*quot, 1);

124 
if(av_cmp_i(a, b) >= 0){ 
125 
a= av_sub_i(a, b); 
126 
quot>v[0] += 1; 
127 
} 
128 
b= av_shr_i(b, 1);

129 
} 
130 
return a;

131 
} 
132  
133 
AVInteger av_div_i(AVInteger a, AVInteger b){ 
134 
AVInteger quot; 
135 
av_mod_i(", a, b); 
136 
return quot;

137 
} 
138  
139 
AVInteger av_int2i(int64_t a){ 
140 
AVInteger out; 
141 
int i;

142  
143 
for(i=0; i<AV_INTEGER_SIZE; i++){ 
144 
out.v[i]= a; 
145 
a>>=16;

146 
} 
147 
return out;

148 
} 
149  
150 
int64_t av_i2int(AVInteger a){ 
151 
int i;

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

153  
154 
for(i= AV_INTEGER_SIZE2; i>=0; i){ 
155 
out = (out<<16) + a.v[i];

156 
} 
157 
return out;

158 
} 
159  
160 
#if 0

161 
#undef NDEBUG

162 
#include <assert.h>

163 

164 
const uint8_t ff_log2_tab[256]={

165 
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,

166 
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,

167 
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,

168 
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,

169 
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,

170 
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,

171 
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,

172 
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

173 
};

174 

175 
main(){

176 
int64_t a,b;

177 

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

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

180 
AVInteger ai= av_int2i(a);

181 
AVInteger bi= av_int2i(b);

182 

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

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

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

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

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

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

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

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

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

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

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

194 
}

195 
}

196 
}

197 
#endif
