## ffmpeg / libavutil / integer.c @ 0b006599

History | View | Annotate | Download (5.71 KB)

1 | 29adde83 | Michael Niedermayer | ```
/*
``` |
---|---|---|---|

2 | ```
* arbitrary precision integers
``` |
||

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

4 | ```
*
``` |
||

5 | b78e7197 | Diego Biurrun | ```
* This file is part of FFmpeg.
``` |

6 | ```
*
``` |
||

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

8 | 29adde83 | Michael Niedermayer | ```
* modify it under the terms of the GNU Lesser General Public
``` |

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

10 | b78e7197 | Diego Biurrun | ```
* version 2.1 of the License, or (at your option) any later version.
``` |

11 | 29adde83 | Michael Niedermayer | ```
*
``` |

12 | b78e7197 | Diego Biurrun | ```
* FFmpeg is distributed in the hope that it will be useful,
``` |

13 | 29adde83 | Michael Niedermayer | ```
* 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 | b78e7197 | Diego Biurrun | ```
* License along with FFmpeg; if not, write to the Free Software
``` |

19 | 5509bffa | Diego Biurrun | ```
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
``` |

20 | 29adde83 | Michael Niedermayer | ```
*
``` |

21 | ```
*/
``` |
||

22 | 115329f1 | Diego Biurrun | |

23 | 29adde83 | Michael Niedermayer | ```
/**
``` |

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 | 115329f1 | Diego Biurrun | |

35 | 29adde83 | Michael Niedermayer | 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 | 115329f1 | Diego Biurrun | |

45 | 29adde83 | Michael Niedermayer | 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 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

53 | ```
* returns the rounded down value of the logarithm of base 2 of the given AVInteger.
``` |
||

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

55 | ```
*/
``` |
||

56 | 29adde83 | Michael Niedermayer | ```
int av_log2_i(AVInteger a){
``` |

57 | ```
int i;
``` |
||

58 | |||

59 | for(i=AV_INTEGER_SIZE-1; i>=0; i--){ |
||

60 | ```
if(a.v[i])
``` |
||

61 | return av_log2_16bit(a.v[i]) + 16*i; |
||

62 | } |
||

63 | return -1; |
||

64 | } |
||

65 | |||

66 | AVInteger av_mul_i(AVInteger a, AVInteger b){ |
||

67 | AVInteger out; |
||

68 | ```
int i, j;
``` |
||

69 | int na= (av_log2_i(a)+16) >> 4; |
||

70 | int nb= (av_log2_i(b)+16) >> 4; |
||

71 | 115329f1 | Diego Biurrun | |

72 | 29adde83 | Michael Niedermayer | memset(&out, 0, sizeof(out)); |

73 | 115329f1 | Diego Biurrun | |

74 | 29adde83 | Michael Niedermayer | for(i=0; i<na; i++){ |

75 | unsigned int carry=0; |
||

76 | 115329f1 | Diego Biurrun | |

77 | 29adde83 | Michael Niedermayer | ```
if(a.v[i])
``` |

78 | ```
for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){
``` |
||

79 | ```
carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i];
``` |
||

80 | out.v[j]= carry; |
||

81 | } |
||

82 | } |
||

83 | |||

84 | ```
return out;
``` |
||

85 | } |
||

86 | |||

87 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

88 | ```
* returns 0 if a==b, 1 if a>b and -1 if a<b.
``` |
||

89 | ```
*/
``` |
||

90 | 29adde83 | Michael Niedermayer | ```
int av_cmp_i(AVInteger a, AVInteger b){
``` |

91 | 115329f1 | Diego Biurrun | ```
int i;
``` |

92 | 29adde83 | Michael Niedermayer | int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1]; |

93 | if(v) return (v>>16)|1; |
||

94 | 115329f1 | Diego Biurrun | |

95 | 29adde83 | Michael Niedermayer | for(i=AV_INTEGER_SIZE-2; i>=0; i--){ |

96 | ```
int v= a.v[i] - b.v[i];
``` |
||

97 | if(v) return (v>>16)|1; |
||

98 | } |
||

99 | return 0; |
||

100 | } |
||

101 | |||

102 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

103 | ```
* bitwise shift.
``` |
||

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

105 | ```
*/
``` |
||

106 | 29adde83 | Michael Niedermayer | ```
AVInteger av_shr_i(AVInteger a, int s){
``` |

107 | AVInteger out; |
||

108 | ```
int i;
``` |
||

109 | |||

110 | for(i=0; i<AV_INTEGER_SIZE; i++){ |
||

111 | int index= i + (s>>4); |
||

112 | unsigned int v=0; |
||

113 | if(index+1<AV_INTEGER_SIZE && index+1>=0) v = a.v[index+1]<<16; |
||

114 | if(index <AV_INTEGER_SIZE && index >=0) v+= a.v[index ]; |
||

115 | ```
out.v[i]= v >> (s&15);
``` |
||

116 | } |
||

117 | ```
return out;
``` |
||

118 | } |
||

119 | |||

120 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

121 | ```
* returns a % b.
``` |
||

122 | ```
* @param quot a/b will be stored here
``` |
||

123 | ```
*/
``` |
||

124 | 29adde83 | Michael Niedermayer | AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ |

125 | ```
int i= av_log2_i(a) - av_log2_i(b);
``` |
||

126 | AVInteger quot_temp; |
||

127 | ```
if(!quot) quot = "_temp;
``` |
||

128 | 115329f1 | Diego Biurrun | |

129 | 29adde83 | Michael Niedermayer | assert((int16_t)a[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b[AV_INTEGER_SIZE-1] >= 0); |

130 | ```
assert(av_log2(b)>=0);
``` |
||

131 | 115329f1 | Diego Biurrun | |

132 | 29adde83 | Michael Niedermayer | if(i > 0) |

133 | b= av_shr_i(b, -i); |
||

134 | 115329f1 | Diego Biurrun | |

135 | 29adde83 | Michael Niedermayer | memset(quot, 0, sizeof(AVInteger)); |

136 | |||

137 | while(i-- >= 0){ |
||

138 | ```
*quot= av_shr_i(*quot, -1);
``` |
||

139 | if(av_cmp_i(a, b) >= 0){ |
||

140 | a= av_sub_i(a, b); |
||

141 | quot->v[0] += 1; |
||

142 | } |
||

143 | ```
b= av_shr_i(b, 1);
``` |
||

144 | } |
||

145 | ```
return a;
``` |
||

146 | } |
||

147 | |||

148 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

149 | ```
* returns a/b.
``` |
||

150 | ```
*/
``` |
||

151 | 29adde83 | Michael Niedermayer | AVInteger av_div_i(AVInteger a, AVInteger b){ |

152 | AVInteger quot; |
||

153 | av_mod_i(", a, b); |
||

154 | ```
return quot;
``` |
||

155 | } |
||

156 | |||

157 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

158 | ```
* converts the given int64_t to an AVInteger.
``` |
||

159 | ```
*/
``` |
||

160 | 29adde83 | Michael Niedermayer | AVInteger av_int2i(int64_t a){ |

161 | AVInteger out; |
||

162 | ```
int i;
``` |
||

163 | 115329f1 | Diego Biurrun | |

164 | 29adde83 | Michael Niedermayer | for(i=0; i<AV_INTEGER_SIZE; i++){ |

165 | out.v[i]= a; |
||

166 | ```
a>>=16;
``` |
||

167 | } |
||

168 | ```
return out;
``` |
||

169 | } |
||

170 | |||

171 | 5c07b9e9 | Michael Niedermayer | ```
/**
``` |

172 | ```
* converts the given AVInteger to an int64_t.
``` |
||

173 | 115329f1 | Diego Biurrun | ```
* if the AVInteger is too large to fit into an int64_t,
``` |

174 | 5c07b9e9 | Michael Niedermayer | ```
* then only the least significant 64bit will be used
``` |

175 | ```
*/
``` |
||

176 | 29adde83 | Michael Niedermayer | int64_t av_i2int(AVInteger a){ |

177 | ```
int i;
``` |
||

178 | ```
int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1];
``` |
||

179 | 115329f1 | Diego Biurrun | |

180 | 29adde83 | Michael Niedermayer | for(i= AV_INTEGER_SIZE-2; i>=0; i--){ |

181 | ```
out = (out<<16) + a.v[i];
``` |
||

182 | } |
||

183 | ```
return out;
``` |
||

184 | } |
||

185 | |||

186 | ```
#if 0
``` |
||

187 | ```
#undef NDEBUG
``` |
||

188 | ```
#include <assert.h>
``` |
||

189 | |||

190 | ```
const uint8_t ff_log2_tab[256]={
``` |
||

191 | ```
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,
``` |
||

192 | ```
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,
``` |
||

193 | ```
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,
``` |
||

194 | ```
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,
``` |
||

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

198 | ```
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
``` |
||

199 | ```
};
``` |
||

200 | |||

201 | ```
main(){
``` |
||

202 | ```
int64_t a,b;
``` |
||

203 | |||

204 | ```
for(a=7; a<256*256*256; a+=13215){
``` |
||

205 | ```
for(b=3; b<256*256*256; b+=27118){
``` |
||

206 | ```
AVInteger ai= av_int2i(a);
``` |
||

207 | ```
AVInteger bi= av_int2i(b);
``` |
||

208 | 115329f1 | Diego Biurrun | |

209 | 29adde83 | Michael Niedermayer | ```
assert(av_i2int(ai) == a);
``` |

210 | ```
assert(av_i2int(bi) == b);
``` |
||

211 | ```
assert(av_i2int(av_add_i(ai,bi)) == a+b);
``` |
||

212 | ```
assert(av_i2int(av_sub_i(ai,bi)) == a-b);
``` |
||

213 | ```
assert(av_i2int(av_mul_i(ai,bi)) == a*b);
``` |
||

214 | ```
assert(av_i2int(av_shr_i(ai, 9)) == a>>9);
``` |
||

215 | ```
assert(av_i2int(av_shr_i(ai,-9)) == a<<9);
``` |
||

216 | ```
assert(av_i2int(av_shr_i(ai, 17)) == a>>17);
``` |
||

217 | ```
assert(av_i2int(av_shr_i(ai,-17)) == a<<17);
``` |
||

218 | ```
assert(av_log2_i(ai) == av_log2(a));
``` |
||

219 | ```
assert(av_i2int(av_div_i(ai,bi)) == a/b);
``` |
||

220 | ```
}
``` |
||

221 | ```
}
``` |
||

222 | ```
}
``` |
||

223 | `#endif` |