Mercurial > libavcodec.hg
comparison integer.c @ 2001:7523553ca85f libavcodec
arbitrary precision integer support
+ - * / % << >> log2 compare are supported
and dont fear, no bloated lib, just 130 lines of c code
author | michael |
---|---|
date | Tue, 04 May 2004 02:51:18 +0000 |
parents | |
children | 2c2f738772b7 |
comparison
equal
deleted
inserted
replaced
2000:86220e37a31e | 2001:7523553ca85f |
---|---|
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 int av_log2_i(AVInteger a){ | |
51 int i; | |
52 | |
53 for(i=AV_INTEGER_SIZE-1; i>=0; i--){ | |
54 if(a.v[i]) | |
55 return av_log2_16bit(a.v[i]) + 16*i; | |
56 } | |
57 return -1; | |
58 } | |
59 | |
60 AVInteger av_mul_i(AVInteger a, AVInteger b){ | |
61 AVInteger out; | |
62 int i, j; | |
63 int na= (av_log2_i(a)+16) >> 4; | |
64 int nb= (av_log2_i(b)+16) >> 4; | |
65 | |
66 memset(&out, 0, sizeof(out)); | |
67 | |
68 for(i=0; i<na; i++){ | |
69 unsigned int carry=0; | |
70 | |
71 if(a.v[i]) | |
72 for(j=i; j<AV_INTEGER_SIZE && j-i<=nb; j++){ | |
73 carry= (carry>>16) + out.v[j] + a.v[i]*b.v[j-i]; | |
74 out.v[j]= carry; | |
75 } | |
76 } | |
77 | |
78 return out; | |
79 } | |
80 | |
81 int av_cmp_i(AVInteger a, AVInteger b){ | |
82 int i; | |
83 int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1]; | |
84 if(v) return (v>>16)|1; | |
85 | |
86 for(i=AV_INTEGER_SIZE-2; i>=0; i--){ | |
87 int v= a.v[i] - b.v[i]; | |
88 if(v) return (v>>16)|1; | |
89 } | |
90 return 0; | |
91 } | |
92 | |
93 AVInteger av_shr_i(AVInteger a, int s){ | |
94 AVInteger out; | |
95 int i; | |
96 | |
97 for(i=0; i<AV_INTEGER_SIZE; i++){ | |
98 int index= i + (s>>4); | |
99 unsigned int v=0; | |
100 if(index+1<AV_INTEGER_SIZE && index+1>=0) v = a.v[index+1]<<16; | |
101 if(index <AV_INTEGER_SIZE && index >=0) v+= a.v[index ]; | |
102 out.v[i]= v >> (s&15); | |
103 } | |
104 return out; | |
105 } | |
106 | |
107 AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ | |
108 int i= av_log2_i(a) - av_log2_i(b); | |
109 AVInteger quot_temp; | |
110 if(!quot) quot = "_temp; | |
111 | |
112 assert((int16_t)a[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b[AV_INTEGER_SIZE-1] >= 0); | |
113 assert(av_log2(b)>=0); | |
114 | |
115 if(i > 0) | |
116 b= av_shr_i(b, -i); | |
117 | |
118 memset(quot, 0, sizeof(AVInteger)); | |
119 | |
120 while(i-- >= 0){ | |
121 *quot= av_shr_i(*quot, -1); | |
122 if(av_cmp_i(a, b) >= 0){ | |
123 a= av_sub_i(a, b); | |
124 quot->v[0] += 1; | |
125 } | |
126 b= av_shr_i(b, 1); | |
127 } | |
128 return a; | |
129 } | |
130 | |
131 AVInteger av_div_i(AVInteger a, AVInteger b){ | |
132 AVInteger quot; | |
133 av_mod_i(", a, b); | |
134 return quot; | |
135 } | |
136 | |
137 AVInteger av_int2i(int64_t a){ | |
138 AVInteger out; | |
139 int i; | |
140 | |
141 for(i=0; i<AV_INTEGER_SIZE; i++){ | |
142 out.v[i]= a; | |
143 a>>=16; | |
144 } | |
145 return out; | |
146 } | |
147 | |
148 int64_t av_i2int(AVInteger a){ | |
149 int i; | |
150 int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1]; | |
151 | |
152 for(i= AV_INTEGER_SIZE-2; i>=0; i--){ | |
153 out = (out<<16) + a.v[i]; | |
154 } | |
155 return out; | |
156 } | |
157 | |
158 #if 0 | |
159 #undef NDEBUG | |
160 #include <assert.h> | |
161 | |
162 const uint8_t ff_log2_tab[256]={ | |
163 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, | |
164 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, | |
165 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, | |
166 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, | |
167 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, | |
168 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, | |
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 }; | |
172 | |
173 main(){ | |
174 int64_t a,b; | |
175 | |
176 for(a=7; a<256*256*256; a+=13215){ | |
177 for(b=3; b<256*256*256; b+=27118){ | |
178 AVInteger ai= av_int2i(a); | |
179 AVInteger bi= av_int2i(b); | |
180 | |
181 assert(av_i2int(ai) == a); | |
182 assert(av_i2int(bi) == b); | |
183 assert(av_i2int(av_add_i(ai,bi)) == a+b); | |
184 assert(av_i2int(av_sub_i(ai,bi)) == a-b); | |
185 assert(av_i2int(av_mul_i(ai,bi)) == a*b); | |
186 assert(av_i2int(av_shr_i(ai, 9)) == a>>9); | |
187 assert(av_i2int(av_shr_i(ai,-9)) == a<<9); | |
188 assert(av_i2int(av_shr_i(ai, 17)) == a>>17); | |
189 assert(av_i2int(av_shr_i(ai,-17)) == a<<17); | |
190 assert(av_log2_i(ai) == av_log2(a)); | |
191 assert(av_i2int(av_div_i(ai,bi)) == a/b); | |
192 } | |
193 } | |
194 } | |
195 #endif |