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