annotate mathematics.c @ 603:880c6441f56a libavutil

Change semantic of CONFIG_*, HAVE_* and ARCH_*. They are now always defined to either 0 or 1.
author aurel
date Tue, 13 Jan 2009 23:44:16 +0000
parents dcb08e8f3b2e
children 819752f80c64
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
1 /*
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
2 * Copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at>
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
3 *
116
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 41
diff changeset
4 * This file is part of FFmpeg.
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 41
diff changeset
5 *
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 41
diff changeset
6 * FFmpeg is free software; you can redistribute it and/or
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
7 * modify it under the terms of the GNU Lesser General Public
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
8 * License as published by the Free Software Foundation; either
116
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 41
diff changeset
9 * version 2.1 of the License, or (at your option) any later version.
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
10 *
116
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 41
diff changeset
11 * FFmpeg is distributed in the hope that it will be useful,
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
14 * Lesser General Public License for more details.
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
15 *
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
16 * You should have received a copy of the GNU Lesser General Public
116
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 41
diff changeset
17 * License along with FFmpeg; if not, write to the Free Software
15
af59e84e283d Update licensing information: The FSF changed postal address.
diego
parents: 12
diff changeset
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
19 */
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
20
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
21 /**
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
22 * @file mathematics.c
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
23 * Miscellaneous math routines and tables.
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
24 */
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
25
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
26 #include "common.h"
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
27 #include "mathematics.h"
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
28
432
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
29 const uint8_t ff_sqrt_tab[256]={
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
30 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
31 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
32 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
33 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
34 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
35 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
36 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,
dcb08e8f3b2e Faster ff_sqrt()
michael
parents: 427
diff changeset
37 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
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
38 };
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
39
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
40 const uint8_t ff_log2_tab[256]={
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
41 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
42 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
43 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
44 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
45 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
46 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
47 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,
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
48 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
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
49 };
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
50
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
51 int64_t ff_gcd(int64_t a, int64_t b){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
52 if(b) return ff_gcd(b, a%b);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
53 else return a;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
54 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
55
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
56 int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
57 int64_t r=0;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
58 assert(c > 0);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
59 assert(b >=0);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
60 assert(rnd >=0 && rnd<=5 && rnd!=4);
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
61
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
62 if(a<0 && a != INT64_MIN) return -av_rescale_rnd(-a, b, c, rnd ^ ((rnd>>1)&1));
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
63
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
64 if(rnd==AV_ROUND_NEAR_INF) r= c/2;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
65 else if(rnd&1) r= c-1;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
66
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
67 if(b<=INT_MAX && c<=INT_MAX){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
68 if(a<=INT_MAX)
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
69 return (a * b + r)/c;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
70 else
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
71 return a/c*b + (a%c*b + r)/c;
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
72 }else{
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
73 #if 1
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
74 uint64_t a0= a&0xFFFFFFFF;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
75 uint64_t a1= a>>32;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
76 uint64_t b0= b&0xFFFFFFFF;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
77 uint64_t b1= b>>32;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
78 uint64_t t1= a0*b1 + a1*b0;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
79 uint64_t t1a= t1<<32;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
80 int i;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
81
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
82 a0 = a0*b0 + t1a;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
83 a1 = a1*b1 + (t1>>32) + (a0<t1a);
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
84 a0 += r;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
85 a1 += a0<r;
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
86
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
87 for(i=63; i>=0; i--){
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
88 // int o= a1 & 0x8000000000000000ULL;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
89 a1+= a1 + ((a0>>i)&1);
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
90 t1+=t1;
36
8795371b6c88 <= vs. >= 10l bug
michael
parents: 35
diff changeset
91 if(/*o || */c <= a1){
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
92 a1 -= c;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
93 t1++;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
94 }
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
95 }
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
96 return t1;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
97 }
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
98 #else
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
99 AVInteger ai;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
100 ai= av_mul_i(av_int2i(a), av_int2i(b));
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
101 ai= av_add_i(ai, av_int2i(r));
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
102
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
103 return av_i2int(av_div_i(ai, av_int2i(c)));
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
104 }
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
105 #endif
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
106 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
107
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
108 int64_t av_rescale(int64_t a, int64_t b, int64_t c){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
109 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
110 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
111
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
112 int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
113 int64_t b= bq.num * (int64_t)cq.den;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
114 int64_t c= cq.num * (int64_t)bq.den;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
115 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
116 }
426
d9390a931aef Allow compilation of test programs when TEST is defined.
diego
parents: 404
diff changeset
117
d9390a931aef Allow compilation of test programs when TEST is defined.
diego
parents: 404
diff changeset
118 #ifdef TEST
41
e2d207b1cb8e improve selftest
michael
parents: 37
diff changeset
119 #include "integer.h"
36
8795371b6c88 <= vs. >= 10l bug
michael
parents: 35
diff changeset
120 #undef printf
427
e7192ff1857d Fix a couple of 'return type defaults to int' and 'control reaches end of
diego
parents: 426
diff changeset
121 int main(void){
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
122 int64_t a,b,c,d,e;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
123
41
e2d207b1cb8e improve selftest
michael
parents: 37
diff changeset
124 for(a=7; a<(1LL<<62); a+=a/3+1){
e2d207b1cb8e improve selftest
michael
parents: 37
diff changeset
125 for(b=3; b<(1LL<<62); b+=b/4+1){
e2d207b1cb8e improve selftest
michael
parents: 37
diff changeset
126 for(c=9; c<(1LL<<62); c+=(c*2)/5+3){
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
127 int64_t r= c/2;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
128 AVInteger ai;
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
129 ai= av_mul_i(av_int2i(a), av_int2i(b));
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
130 ai= av_add_i(ai, av_int2i(r));
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
131
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
132 d= av_i2int(av_div_i(ai, av_int2i(c)));
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
133
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
134 e= av_rescale(a,b,c);
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
135
36
8795371b6c88 <= vs. >= 10l bug
michael
parents: 35
diff changeset
136 if((double)a * (double)b / (double)c > (1LL<<63))
8795371b6c88 <= vs. >= 10l bug
michael
parents: 35
diff changeset
137 continue;
8795371b6c88 <= vs. >= 10l bug
michael
parents: 35
diff changeset
138
128
d94fb7e6cb53 Replace most of the %lld and %llx by their (cleaner) PRI*64 counterparts.
diego
parents: 116
diff changeset
139 if(d!=e) printf("%"PRId64"*%"PRId64"/%"PRId64"= %"PRId64"=%"PRId64"\n", a, b, c, d, e);
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
140 }
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
141 }
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
142 }
427
e7192ff1857d Fix a couple of 'return type defaults to int' and 'control reaches end of
diego
parents: 426
diff changeset
143 return 0;
34
dedc1568e2cf avoid AVInteger usage in av_rescale
michael
parents: 15
diff changeset
144 }
35
b734d9f69ff4 add newline at end of file
mru
parents: 34
diff changeset
145 #endif