• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

libavutil/mathematics.c

Go to the documentation of this file.
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

Generated on Sat Feb 16 2013 09:23:15 for ffmpeg by  doxygen 1.7.1