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