• 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 <stdint.h>
00028 #include <limits.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 const uint8_t av_reverse[256]={
00054 0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
00055 0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
00056 0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
00057 0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
00058 0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
00059 0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
00060 0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
00061 0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
00062 0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
00063 0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
00064 0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
00065 0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
00066 0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
00067 0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
00068 0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
00069 0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF,
00070 };
00071 
00072 int64_t av_gcd(int64_t a, int64_t b){
00073     if(b) return av_gcd(b, a%b);
00074     else  return a;
00075 }
00076 
00077 int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd){
00078     int64_t r=0;
00079     assert(c > 0);
00080     assert(b >=0);
00081     assert(rnd >=0 && rnd<=5 && rnd!=4);
00082 
00083     if(a<0 && a != INT64_MIN) return -av_rescale_rnd(-a, b, c, rnd ^ ((rnd>>1)&1));
00084 
00085     if(rnd==AV_ROUND_NEAR_INF) r= c/2;
00086     else if(rnd&1)             r= c-1;
00087 
00088     if(b<=INT_MAX && c<=INT_MAX){
00089         if(a<=INT_MAX)
00090             return (a * b + r)/c;
00091         else
00092             return a/c*b + (a%c*b + r)/c;
00093     }else{
00094 #if 1
00095         uint64_t a0= a&0xFFFFFFFF;
00096         uint64_t a1= a>>32;
00097         uint64_t b0= b&0xFFFFFFFF;
00098         uint64_t b1= b>>32;
00099         uint64_t t1= a0*b1 + a1*b0;
00100         uint64_t t1a= t1<<32;
00101         int i;
00102 
00103         a0 = a0*b0 + t1a;
00104         a1 = a1*b1 + (t1>>32) + (a0<t1a);
00105         a0 += r;
00106         a1 += a0<r;
00107 
00108         for(i=63; i>=0; i--){
00109 //            int o= a1 & 0x8000000000000000ULL;
00110             a1+= a1 + ((a0>>i)&1);
00111             t1+=t1;
00112             if(/*o || */c <= a1){
00113                 a1 -= c;
00114                 t1++;
00115             }
00116         }
00117         return t1;
00118     }
00119 #else
00120         AVInteger ai;
00121         ai= av_mul_i(av_int2i(a), av_int2i(b));
00122         ai= av_add_i(ai, av_int2i(r));
00123 
00124         return av_i2int(av_div_i(ai, av_int2i(c)));
00125     }
00126 #endif
00127 }
00128 
00129 int64_t av_rescale(int64_t a, int64_t b, int64_t c){
00130     return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
00131 }
00132 
00133 int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq){
00134     int64_t b= bq.num * (int64_t)cq.den;
00135     int64_t c= cq.num * (int64_t)bq.den;
00136     return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
00137 }
00138 
00139 int av_compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b){
00140     int64_t a= tb_a.num * (int64_t)tb_b.den;
00141     int64_t b= tb_b.num * (int64_t)tb_a.den;
00142     if (av_rescale_rnd(ts_a, a, b, AV_ROUND_DOWN) < ts_b) return -1;
00143     if (av_rescale_rnd(ts_b, b, a, AV_ROUND_DOWN) < ts_a) return  1;
00144     return 0;
00145 }
00146 
00147 #ifdef TEST
00148 #include "integer.h"
00149 #undef printf
00150 int main(void){
00151     int64_t a,b,c,d,e;
00152 
00153     for(a=7; a<(1LL<<62); a+=a/3+1){
00154         for(b=3; b<(1LL<<62); b+=b/4+1){
00155             for(c=9; c<(1LL<<62); c+=(c*2)/5+3){
00156                 int64_t r= c/2;
00157                 AVInteger ai;
00158                 ai= av_mul_i(av_int2i(a), av_int2i(b));
00159                 ai= av_add_i(ai, av_int2i(r));
00160 
00161                 d= av_i2int(av_div_i(ai, av_int2i(c)));
00162 
00163                 e= av_rescale(a,b,c);
00164 
00165                 if((double)a * (double)b / (double)c > (1LL<<63))
00166                     continue;
00167 
00168                 if(d!=e) printf("%"PRId64"*%"PRId64"/%"PRId64"= %"PRId64"=%"PRId64"\n", a, b, c, d, e);
00169             }
00170         }
00171     }
00172     return 0;
00173 }
00174 #endif

Generated on Fri Sep 16 2011 17:17:51 for FFmpeg by  doxygen 1.7.1