00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00026 #include <assert.h>
00027 #include "avutil.h"
00028 #include "common.h"
00029 #include "mathematics.h"
00030
00031 const uint8_t ff_sqrt_tab[256]={
00032 0, 16, 23, 28, 32, 36, 40, 43, 46, 48, 51, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90,
00033 91, 92, 94, 95, 96, 98, 99,100,102,103,104,105,107,108,109,110,111,112,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
00034 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,144,145,146,147,148,149,150,151,151,152,153,154,155,156,156,
00035 157,158,159,160,160,161,162,163,164,164,165,166,167,168,168,169,170,171,171,172,173,174,174,175,176,176,177,178,179,179,180,181,
00036 182,182,183,184,184,185,186,186,187,188,188,189,190,190,191,192,192,193,194,194,195,196,196,197,198,198,199,200,200,201,202,202,
00037 203,204,204,205,205,206,207,207,208,208,209,210,210,211,212,212,213,213,214,215,215,216,216,217,218,218,219,219,220,220,221,222,
00038 222,223,223,224,224,225,226,226,227,227,228,228,229,230,230,231,231,232,232,233,233,234,235,235,236,236,237,237,238,238,239,239,
00039 240,240,241,242,242,243,243,244,244,245,245,246,246,247,247,248,248,249,249,250,250,251,251,252,252,253,253,254,254,255,255,255
00040 };
00041
00042 const uint8_t ff_log2_tab[256]={
00043 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,
00044 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,
00045 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,
00046 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,
00047 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,
00048 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,
00049 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,
00050 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
00051 };
00052
00053 int64_t av_gcd(int64_t a, int64_t b){
00054 if(b) return av_gcd(b, a%b);
00055 else return a;
00056 }
00057
00058 #if LIBAVUTIL_VERSION_MAJOR < 50
00059 int64_t ff_gcd(int64_t a, int64_t b){
00060 return av_gcd(a, b);
00061 }
00062 #endif
00063
00064 int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd){
00065 int64_t r=0;
00066 assert(c > 0);
00067 assert(b >=0);
00068 assert(rnd >=0 && rnd<=5 && rnd!=4);
00069
00070 if(a<0 && a != INT64_MIN) return -av_rescale_rnd(-a, b, c, rnd ^ ((rnd>>1)&1));
00071
00072 if(rnd==AV_ROUND_NEAR_INF) r= c/2;
00073 else if(rnd&1) r= c-1;
00074
00075 if(b<=INT_MAX && c<=INT_MAX){
00076 if(a<=INT_MAX)
00077 return (a * b + r)/c;
00078 else
00079 return a/c*b + (a%c*b + r)/c;
00080 }else{
00081 #if 1
00082 uint64_t a0= a&0xFFFFFFFF;
00083 uint64_t a1= a>>32;
00084 uint64_t b0= b&0xFFFFFFFF;
00085 uint64_t b1= b>>32;
00086 uint64_t t1= a0*b1 + a1*b0;
00087 uint64_t t1a= t1<<32;
00088 int i;
00089
00090 a0 = a0*b0 + t1a;
00091 a1 = a1*b1 + (t1>>32) + (a0<t1a);
00092 a0 += r;
00093 a1 += a0<r;
00094
00095 for(i=63; i>=0; i--){
00096
00097 a1+= a1 + ((a0>>i)&1);
00098 t1+=t1;
00099 if(c <= a1){
00100 a1 -= c;
00101 t1++;
00102 }
00103 }
00104 return t1;
00105 }
00106 #else
00107 AVInteger ai;
00108 ai= av_mul_i(av_int2i(a), av_int2i(b));
00109 ai= av_add_i(ai, av_int2i(r));
00110
00111 return av_i2int(av_div_i(ai, av_int2i(c)));
00112 }
00113 #endif
00114 }
00115
00116 int64_t av_rescale(int64_t a, int64_t b, int64_t c){
00117 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
00118 }
00119
00120 int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq){
00121 int64_t b= bq.num * (int64_t)cq.den;
00122 int64_t c= cq.num * (int64_t)bq.den;
00123 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
00124 }
00125
00126 #ifdef TEST
00127 #include "integer.h"
00128 #undef printf
00129 int main(void){
00130 int64_t a,b,c,d,e;
00131
00132 for(a=7; a<(1LL<<62); a+=a/3+1){
00133 for(b=3; b<(1LL<<62); b+=b/4+1){
00134 for(c=9; c<(1LL<<62); c+=(c*2)/5+3){
00135 int64_t r= c/2;
00136 AVInteger ai;
00137 ai= av_mul_i(av_int2i(a), av_int2i(b));
00138 ai= av_add_i(ai, av_int2i(r));
00139
00140 d= av_i2int(av_div_i(ai, av_int2i(c)));
00141
00142 e= av_rescale(a,b,c);
00143
00144 if((double)a * (double)b / (double)c > (1LL<<63))
00145 continue;
00146
00147 if(d!=e) printf("%"PRId64"*%"PRId64"/%"PRId64"= %"PRId64"=%"PRId64"\n", a, b, c, d, e);
00148 }
00149 }
00150 }
00151 return 0;
00152 }
00153 #endif