00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00026 #include "common.h"
00027 #include "mathematics.h"
00028
00029 const uint8_t ff_sqrt_tab[256]={
00030 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,
00031 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,
00032 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,
00033 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,
00034 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,
00035 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,
00036 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,
00037 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
00038 };
00039
00040 const uint8_t ff_log2_tab[256]={
00041 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,
00042 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,
00043 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,
00044 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,
00045 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,
00046 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,
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 };
00050
00051 int64_t ff_gcd(int64_t a, int64_t b){
00052 if(b) return ff_gcd(b, a%b);
00053 else return a;
00054 }
00055
00056 int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd){
00057 int64_t r=0;
00058 assert(c > 0);
00059 assert(b >=0);
00060 assert(rnd >=0 && rnd<=5 && rnd!=4);
00061
00062 if(a<0 && a != INT64_MIN) return -av_rescale_rnd(-a, b, c, rnd ^ ((rnd>>1)&1));
00063
00064 if(rnd==AV_ROUND_NEAR_INF) r= c/2;
00065 else if(rnd&1) r= c-1;
00066
00067 if(b<=INT_MAX && c<=INT_MAX){
00068 if(a<=INT_MAX)
00069 return (a * b + r)/c;
00070 else
00071 return a/c*b + (a%c*b + r)/c;
00072 }else{
00073 #if 1
00074 uint64_t a0= a&0xFFFFFFFF;
00075 uint64_t a1= a>>32;
00076 uint64_t b0= b&0xFFFFFFFF;
00077 uint64_t b1= b>>32;
00078 uint64_t t1= a0*b1 + a1*b0;
00079 uint64_t t1a= t1<<32;
00080 int i;
00081
00082 a0 = a0*b0 + t1a;
00083 a1 = a1*b1 + (t1>>32) + (a0<t1a);
00084 a0 += r;
00085 a1 += a0<r;
00086
00087 for(i=63; i>=0; i--){
00088
00089 a1+= a1 + ((a0>>i)&1);
00090 t1+=t1;
00091 if(c <= a1){
00092 a1 -= c;
00093 t1++;
00094 }
00095 }
00096 return t1;
00097 }
00098 #else
00099 AVInteger ai;
00100 ai= av_mul_i(av_int2i(a), av_int2i(b));
00101 ai= av_add_i(ai, av_int2i(r));
00102
00103 return av_i2int(av_div_i(ai, av_int2i(c)));
00104 }
00105 #endif
00106 }
00107
00108 int64_t av_rescale(int64_t a, int64_t b, int64_t c){
00109 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
00110 }
00111
00112 int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq){
00113 int64_t b= bq.num * (int64_t)cq.den;
00114 int64_t c= cq.num * (int64_t)bq.den;
00115 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
00116 }
00117
00118 #ifdef TEST
00119 #include "integer.h"
00120 #undef printf
00121 int main(void){
00122 int64_t a,b,c,d,e;
00123
00124 for(a=7; a<(1LL<<62); a+=a/3+1){
00125 for(b=3; b<(1LL<<62); b+=b/4+1){
00126 for(c=9; c<(1LL<<62); c+=(c*2)/5+3){
00127 int64_t r= c/2;
00128 AVInteger ai;
00129 ai= av_mul_i(av_int2i(a), av_int2i(b));
00130 ai= av_add_i(ai, av_int2i(r));
00131
00132 d= av_i2int(av_div_i(ai, av_int2i(c)));
00133
00134 e= av_rescale(a,b,c);
00135
00136 if((double)a * (double)b / (double)c > (1LL<<63))
00137 continue;
00138
00139 if(d!=e) printf("%"PRId64"*%"PRId64"/%"PRId64"= %"PRId64"=%"PRId64"\n", a, b, c, d, e);
00140 }
00141 }
00142 }
00143 return 0;
00144 }
00145 #endif