annotate rational.c @ 812:f849545df4e5 libavutil

Mark all intreadwrite functions av_always_inline
author mru
date Mon, 18 Jan 2010 01:35:19 +0000
parents 70bdd5501662
children 0795a743bda1
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 /*
633
8c48a1b999a3 spelling/grammar/consistency review part I
diego
parents: 618
diff changeset
2 * rational numbers
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
3 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
4 *
116
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 87
diff changeset
5 * This file is part of FFmpeg.
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 87
diff changeset
6 *
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 87
diff changeset
7 * 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
8 * 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
9 * 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: 87
diff changeset
10 * 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
11 *
116
d76a36742464 Change license headers to say 'FFmpeg' instead of 'this program/this library'
diego
parents: 87
diff changeset
12 * 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
13 * 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
14 * 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
15 * Lesser General Public License for more details.
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
16 *
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
17 * 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: 87
diff changeset
18 * 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
19 * 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
20 */
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
21
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
22 /**
642
70bdd5501662 Use full internal pathname in doxygen @file directives.
diego
parents: 641
diff changeset
23 * @file libavutil/rational.c
633
8c48a1b999a3 spelling/grammar/consistency review part I
diego
parents: 618
diff changeset
24 * rational numbers
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
25 * @author Michael Niedermayer <michaelni@gmx.at>
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
26 */
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
27
618
e0bf946f7d23 Directly #include a bunch of indirectly #included headers.
diego
parents: 607
diff changeset
28 #include <assert.h>
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
29 //#include <math.h>
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
30 #include <limits.h>
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
31
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
32 #include "common.h"
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
33 #include "mathematics.h"
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
34 #include "rational.h"
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
35
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
36 int av_reduce(int *dst_num, int *dst_den, int64_t num, int64_t den, int64_t max){
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
37 AVRational a0={0,1}, a1={1,0};
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
38 int sign= (num<0) ^ (den<0);
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
39 int64_t gcd= av_gcd(FFABS(num), FFABS(den));
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
40
161
3c1966537d5e fix av_reduce() with things like 1/0 and 0/0
michael
parents: 149
diff changeset
41 if(gcd){
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
42 num = FFABS(num)/gcd;
161
3c1966537d5e fix av_reduce() with things like 1/0 and 0/0
michael
parents: 149
diff changeset
43 den = FFABS(den)/gcd;
3c1966537d5e fix av_reduce() with things like 1/0 and 0/0
michael
parents: 149
diff changeset
44 }
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
45 if(num<=max && den<=max){
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
46 a1= (AVRational){num, den};
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
47 den=0;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
48 }
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
49
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
50 while(den){
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
51 uint64_t x = num / den;
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
52 int64_t next_den= num - den*x;
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
53 int64_t a2n= x*a1.num + a0.num;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
54 int64_t a2d= x*a1.den + a0.den;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
55
148
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
56 if(a2n > max || a2d > max){
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
57 if(a1.num) x= (max - a0.num) / a1.num;
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
58 if(a1.den) x= FFMIN(x, (max - a0.den) / a1.den);
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
59
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
60 if (den*(2*x*a1.den + a0.den) > num*a1.den)
148
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
61 a1 = (AVRational){x*a1.num + a0.num, x*a1.den + a0.den};
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
62 break;
e299e867a485 return optimal fraction
michael
parents: 120
diff changeset
63 }
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
64
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
65 a0= a1;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
66 a1= (AVRational){a2n, a2d};
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
67 num= den;
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
68 den= next_den;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
69 }
607
819752f80c64 export gcd function as av_gcd()
aurel
parents: 573
diff changeset
70 assert(av_gcd(a1.num, a1.den) <= 1U);
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
71
641
41e4544b228b cosmetics: Use 'num' instead of 'nom' as abbreviation for numerator.
diego
parents: 633
diff changeset
72 *dst_num = sign ? -a1.num : a1.num;
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
73 *dst_den = a1.den;
12
ce8f9f4390c3 COSMETICS: Remove all trailing whitespace.
diego
parents: 0
diff changeset
74
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
75 return den==0;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
76 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
77
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
78 AVRational av_mul_q(AVRational b, AVRational c){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
79 av_reduce(&b.num, &b.den, b.num * (int64_t)c.num, b.den * (int64_t)c.den, INT_MAX);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
80 return b;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
81 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
82
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
83 AVRational av_div_q(AVRational b, AVRational c){
87
891a0f0580cd simplify
michael
parents: 86
diff changeset
84 return av_mul_q(b, (AVRational){c.den, c.num});
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
85 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
86
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
87 AVRational av_add_q(AVRational b, AVRational c){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
88 av_reduce(&b.num, &b.den, b.num * (int64_t)c.den + c.num * (int64_t)b.den, b.den * (int64_t)c.den, INT_MAX);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
89 return b;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
90 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
91
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
92 AVRational av_sub_q(AVRational b, AVRational c){
87
891a0f0580cd simplify
michael
parents: 86
diff changeset
93 return av_add_q(b, (AVRational){-c.num, c.den});
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
94 }
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
95
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
96 AVRational av_d2q(double d, int max){
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
97 AVRational a;
87
891a0f0580cd simplify
michael
parents: 86
diff changeset
98 #define LOG2 0.69314718055994530941723212145817656807550013436025
891a0f0580cd simplify
michael
parents: 86
diff changeset
99 int exponent= FFMAX( (int)(log(fabs(d) + 1e-20)/LOG2), 0);
0
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
100 int64_t den= 1LL << (61 - exponent);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
101 av_reduce(&a.num, &a.den, (int64_t)(d * den + 0.5), den, max);
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
102
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
103 return a;
ee8f44bb7c4d libavutil: Utility code from libavcodec moved to a separate library.
al
parents:
diff changeset
104 }
573
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
105
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
106 int av_nearer_q(AVRational q, AVRational q1, AVRational q2)
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
107 {
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
108 /* n/d is q, a/b is the median between q1 and q2 */
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
109 int64_t a = q1.num * (int64_t)q2.den + q2.num * (int64_t)q1.den;
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
110 int64_t b = 2 * (int64_t)q1.den * q2.den;
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
111
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
112 /* rnd_up(a*d/b) > n => a*d/b > n */
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
113 int64_t x_up = av_rescale_rnd(a, q.den, b, AV_ROUND_UP);
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
114
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
115 /* rnd_down(a*d/b) < n => a*d/b < n */
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
116 int64_t x_down = av_rescale_rnd(a, q.den, b, AV_ROUND_DOWN);
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
117
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
118 return ((x_up > q.num) - (x_down < q.num)) * av_cmp_q(q2, q1);
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
119 }
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
120
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
121 int av_find_nearest_q_idx(AVRational q, const AVRational* q_list)
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
122 {
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
123 int i, nearest_q_idx = 0;
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
124 for(i=0; q_list[i].den; i++)
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
125 if (av_nearer_q(q, q_list[i], q_list[nearest_q_idx]) > 0)
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
126 nearest_q_idx = i;
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
127
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
128 return nearest_q_idx;
1f4b70bcd610 Implement av_nearer_q() and av_find_nearest_q_idx() functions.
stefano
parents: 358
diff changeset
129 }