00001 /* 00002 * Copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at> 00003 * 00004 * This file is part of FFmpeg. 00005 * 00006 * FFmpeg is free software; you can redistribute it and/or 00007 * modify it under the terms of the GNU Lesser General Public 00008 * License as published by the Free Software Foundation; either 00009 * version 2.1 of the License, or (at your option) any later version. 00010 * 00011 * FFmpeg is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 * Lesser General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU Lesser General Public 00017 * License along with FFmpeg; if not, write to the Free Software 00018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 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 // int o= a1 & 0x8000000000000000ULL; 00097 a1+= a1 + ((a0>>i)&1); 00098 t1+=t1; 00099 if(/*o || */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