blob: 6d6855fa1b9e3ff68d8e3788615700315bb303f4
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 02110-1301 USA |
20 | */ |
21 | |
22 | /** |
23 | * @file |
24 | * arbitrary precision integers |
25 | * @author Michael Niedermayer <michaelni@gmx.at> |
26 | */ |
27 | |
28 | #include "common.h" |
29 | #include "integer.h" |
30 | #include "avassert.h" |
31 | |
32 | static const AVInteger zero_i; |
33 | |
34 | AVInteger av_add_i(AVInteger a, AVInteger b){ |
35 | int i, carry=0; |
36 | |
37 | for(i=0; i<AV_INTEGER_SIZE; i++){ |
38 | carry= (carry>>16) + a.v[i] + b.v[i]; |
39 | a.v[i]= carry; |
40 | } |
41 | return a; |
42 | } |
43 | |
44 | AVInteger av_sub_i(AVInteger a, AVInteger b){ |
45 | int i, carry=0; |
46 | |
47 | for(i=0; i<AV_INTEGER_SIZE; i++){ |
48 | carry= (carry>>16) + a.v[i] - b.v[i]; |
49 | a.v[i]= carry; |
50 | } |
51 | return a; |
52 | } |
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 | int av_cmp_i(AVInteger a, AVInteger b){ |
86 | int i; |
87 | int v= (int16_t)a.v[AV_INTEGER_SIZE-1] - (int16_t)b.v[AV_INTEGER_SIZE-1]; |
88 | if(v) return (v>>16)|1; |
89 | |
90 | for(i=AV_INTEGER_SIZE-2; i>=0; i--){ |
91 | int v= a.v[i] - b.v[i]; |
92 | if(v) return (v>>16)|1; |
93 | } |
94 | return 0; |
95 | } |
96 | |
97 | AVInteger av_shr_i(AVInteger a, int s){ |
98 | AVInteger out; |
99 | int i; |
100 | |
101 | for(i=0; i<AV_INTEGER_SIZE; i++){ |
102 | unsigned int index= i + (s>>4); |
103 | unsigned int v=0; |
104 | if(index+1<AV_INTEGER_SIZE) v = a.v[index+1]<<16; |
105 | if(index <AV_INTEGER_SIZE) v+= a.v[index ]; |
106 | out.v[i]= v >> (s&15); |
107 | } |
108 | return out; |
109 | } |
110 | |
111 | AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b){ |
112 | int i= av_log2_i(a) - av_log2_i(b); |
113 | AVInteger quot_temp; |
114 | if(!quot) quot = "_temp; |
115 | |
116 | if ((int16_t)a.v[AV_INTEGER_SIZE-1] < 0) { |
117 | a = av_mod_i(quot, av_sub_i(zero_i, a), b); |
118 | *quot = av_sub_i(zero_i, *quot); |
119 | return av_sub_i(zero_i, a); |
120 | } |
121 | |
122 | av_assert2((int16_t)a.v[AV_INTEGER_SIZE-1] >= 0 && (int16_t)b.v[AV_INTEGER_SIZE-1] >= 0); |
123 | av_assert2(av_log2_i(b)>=0); |
124 | |
125 | if(i > 0) |
126 | b= av_shr_i(b, -i); |
127 | |
128 | memset(quot, 0, sizeof(AVInteger)); |
129 | |
130 | while(i-- >= 0){ |
131 | *quot= av_shr_i(*quot, -1); |
132 | if(av_cmp_i(a, b) >= 0){ |
133 | a= av_sub_i(a, b); |
134 | quot->v[0] += 1; |
135 | } |
136 | b= av_shr_i(b, 1); |
137 | } |
138 | return a; |
139 | } |
140 | |
141 | AVInteger av_div_i(AVInteger a, AVInteger b){ |
142 | AVInteger quot; |
143 | av_mod_i(", a, b); |
144 | return quot; |
145 | } |
146 | |
147 | AVInteger av_int2i(int64_t a){ |
148 | AVInteger out; |
149 | int i; |
150 | |
151 | for(i=0; i<AV_INTEGER_SIZE; i++){ |
152 | out.v[i]= a; |
153 | a>>=16; |
154 | } |
155 | return out; |
156 | } |
157 | |
158 | int64_t av_i2int(AVInteger a){ |
159 | int i; |
160 | int64_t out=(int8_t)a.v[AV_INTEGER_SIZE-1]; |
161 | |
162 | for(i= AV_INTEGER_SIZE-2; i>=0; i--){ |
163 | out = (out<<16) + a.v[i]; |
164 | } |
165 | return out; |
166 | } |
167 | |
168 | #ifdef TEST |
169 | |
170 | const uint8_t ff_log2_tab[256]={ |
171 | 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, |
172 | 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, |
173 | 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, |
174 | 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, |
175 | 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, |
176 | 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, |
177 | 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, |
178 | 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 |
179 | }; |
180 | |
181 | int main(void){ |
182 | int64_t a,b; |
183 | |
184 | for(a=7; a<256*256*256; a+=13215){ |
185 | for(b=3; b<256*256*256; b+=27118){ |
186 | AVInteger ai= av_int2i(a); |
187 | AVInteger bi= av_int2i(b); |
188 | |
189 | av_assert0(av_i2int(ai) == a); |
190 | av_assert0(av_i2int(bi) == b); |
191 | av_assert0(av_i2int(av_add_i(ai,bi)) == a+b); |
192 | av_assert0(av_i2int(av_sub_i(ai,bi)) == a-b); |
193 | av_assert0(av_i2int(av_mul_i(ai,bi)) == a*b); |
194 | av_assert0(av_i2int(av_shr_i(ai, 9)) == a>>9); |
195 | av_assert0(av_i2int(av_shr_i(ai,-9)) == a<<9); |
196 | av_assert0(av_i2int(av_shr_i(ai, 17)) == a>>17); |
197 | av_assert0(av_i2int(av_shr_i(ai,-17)) == a<<17); |
198 | av_assert0(av_log2_i(ai) == av_log2(a)); |
199 | av_assert0(av_i2int(av_div_i(ai,bi)) == a/b); |
200 | } |
201 | } |
202 | return 0; |
203 | } |
204 | #endif |
205 |