FFmpeg
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
integer.c
Go to the documentation of this file.
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 
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 
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 
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 
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 
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 
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 
112  int i= av_log2_i(a) - av_log2_i(b);
113  AVInteger quot_temp;
114  if(!quot) 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 
142  AVInteger quot;
143  av_mod_i(&quot, a, b);
144  return quot;
145 }
146 
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 
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
const char * s
Definition: avisynth_c.h:631
const char * b
Definition: vf_curves.c:109
int av_log2(unsigned v)
Definition: intmath.c:26
int av_log2_16bit(unsigned v)
Definition: intmath.c:31
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:63
uint16_t v[AV_INTEGER_SIZE]
Definition: integer.h:37
int64_t av_i2int(AVInteger a)
Convert the given AVInteger to an int64_t.
Definition: integer.c:158
AVInteger av_int2i(int64_t a)
Convert the given int64_t to an AVInteger.
Definition: integer.c:147
int av_log2_i(AVInteger a)
Return the rounded-down value of the base 2 logarithm of the given AVInteger.
Definition: integer.c:54
AVInteger av_mul_i(AVInteger a, AVInteger b)
Definition: integer.c:64
simple assert() macros that are a bit more flexible than ISO C assert().
int av_cmp_i(AVInteger a, AVInteger b)
Return 0 if a==b, 1 if a>b and -1 if a<b.
Definition: integer.c:85
AVInteger av_add_i(AVInteger a, AVInteger b)
Definition: integer.c:34
const uint8_t ff_log2_tab[256]
Definition: log2_tab.c:23
FILE * out
Definition: movenc-test.c:54
int index
Definition: gxfenc.c:89
static const AVInteger zero_i
Definition: integer.c:32
AVInteger av_sub_i(AVInteger a, AVInteger b)
Definition: integer.c:44
AVInteger av_shr_i(AVInteger a, int s)
bitwise shift
Definition: integer.c:97
arbitrary precision integers
AVInteger av_mod_i(AVInteger *quot, AVInteger a, AVInteger b)
Return a % b.
Definition: integer.c:111
common internal and external API header
#define AV_INTEGER_SIZE
Definition: integer.h:34
AVInteger av_div_i(AVInteger a, AVInteger b)
Return a/b.
Definition: integer.c:141
int main(int argc, char **argv)
Definition: main.c:22