Mercurial > libavutil.hg
comparison integer.c @ 0:ee8f44bb7c4d libavutil
libavutil: Utility code from libavcodec moved to a separate library.
author | al |
---|---|
date | Mon, 01 Aug 2005 20:07:05 +0000 |
parents | |
children | ce8f9f4390c3 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:ee8f44bb7c4d |
---|---|
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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_SIZE-1; 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 && j-i<=nb; j++){ | |
77 carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i]; | |
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_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1]; | |
91 if(v) return (v>>16)|1; | |
92 | |
93 for(i=AV_INTEGER_SIZE-2; 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_SIZE-1] >= 0 && (int16_t)b[AV_INTEGER_SIZE-1] >= 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_SIZE-1]; | |
177 | |
178 for(i= AV_INTEGER_SIZE-2; 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)) == a-b); | |
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 |