Libav 0.7.1
|
00001 /* 00002 * Copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at> 00003 * 00004 * This file is part of Libav. 00005 * 00006 * Libav 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 * Libav 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 Libav; 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((unsigned)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 int64_t av_compare_mod(uint64_t a, uint64_t b, uint64_t mod){ 00148 int64_t c= (a-b) & (mod-1); 00149 if(c > (mod>>1)) 00150 c-= mod; 00151 return c; 00152 } 00153 00154 #ifdef TEST 00155 #include "integer.h" 00156 #undef printf 00157 int main(void){ 00158 int64_t a,b,c,d,e; 00159 00160 for(a=7; a<(1LL<<62); a+=a/3+1){ 00161 for(b=3; b<(1LL<<62); b+=b/4+1){ 00162 for(c=9; c<(1LL<<62); c+=(c*2)/5+3){ 00163 int64_t r= c/2; 00164 AVInteger ai; 00165 ai= av_mul_i(av_int2i(a), av_int2i(b)); 00166 ai= av_add_i(ai, av_int2i(r)); 00167 00168 d= av_i2int(av_div_i(ai, av_int2i(c))); 00169 00170 e= av_rescale(a,b,c); 00171 00172 if((double)a * (double)b / (double)c > (1LL<<63)) 00173 continue; 00174 00175 if(d!=e) printf("%"PRId64"*%"PRId64"/%"PRId64"= %"PRId64"=%"PRId64"\n", a, b, c, d, e); 00176 } 00177 } 00178 } 00179 return 0; 00180 } 00181 #endif