FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libswscale/rational64.c
Date: 2026-10-20 22:17:59
Exec Total Coverage
Lines: 126 130 96.9%
Functions: 12 12 100.0%
Branches: 88 96 91.7%
Line Branch Exec Source
1 /*
2 * 64-bit rational numbers
3 * Copyright (c) 2025 Niklas Haas
4 * Copyright (c) 2003 Michael Niedermayer <michaelni@gmx.at>
5 *
6 * This file is part of FFmpeg.
7 *
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 */
22
23 /**
24 * @file
25 * 64-bit rational numbers
26 * @author Niklas Haas
27 */
28
29 #include <limits.h>
30
31 #include "libavutil/attributes.h"
32 #include "libavutil/common.h"
33 #include "libavutil/int128.h"
34 #include "libavutil/intmath.h"
35 #include "rational64.h"
36
37 129475996 static av_always_inline uint64_t high64(av_int128 a)
38 {
39 129475996 return av_from128u(av_shr128(a, 64));
40 }
41
42 /* unsigned version of av_gcd(); see libavutil/mathematics.c */
43 1915203674 static av_always_inline uint64_t gcd_u64(uint64_t a, uint64_t b)
44 {
45
2/2
✓ Branch 0 taken 1134727298 times.
✓ Branch 1 taken 780476376 times.
 1915203674 if (!a)
46 1134727298 return b;
47
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 780475928 times.
 780476376 if (!b)
48 448 return a;
49
50 780475928 const int k = ff_ctzll(a | b);
51 780475928 a >>= ff_ctzll(a);
52 do {
53 6221441854 b >>= ff_ctzll(b);
54
2/2
✓ Branch 0 taken 1573540015 times.
✓ Branch 1 taken 4647901839 times.
 6221441854 if (a > b)
55 1573540015 FFSWAP(uint64_t, a, b);
56 6221441854 b -= a;
57
2/2
✓ Branch 0 taken 5440965926 times.
✓ Branch 1 taken 780475928 times.
 6221441854 } while (b);
58 780475928 return a << k;
59 }
60
61 9928197 static av_int128 gcd128(av_int128 a, av_int128 b)
62 {
63
2/2
✓ Branch 0 taken 278588556 times.
✓ Branch 1 taken 9928197 times.
 288516753 while (av_test128(b)) {
64 278588556 av_int128 tmp = b;
65 278588556 b = av_mod128(a, b);
66 278588556 a = tmp;
67 }
68 9928197 return a;
69 }
70
71 69619780 static AVRational64 reduce64(av_int128 num, av_int128 den)
72 {
73 69619780 const av_int128 zero = av_to128i(0);
74 69619780 const av_int128 max = av_to128i(INT64_MAX);
75 69619780 const int num_sign = av_cmp128(num, zero) < 0;
76 69619780 const int den_sign = av_cmp128(den, zero) < 0;
77
2/2
✓ Branch 0 taken 24351343 times.
✓ Branch 1 taken 45268437 times.
 69619780 if (num_sign)
78 24351343 num = av_sub128(zero, num);
79
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 69619780 times.
 69619780 if (den_sign)
80 ✗ den = av_sub128(zero, den);
81
82
4/4
✓ Branch 1 taken 59856216 times.
✓ Branch 2 taken 9763564 times.
✓ Branch 4 taken 59714666 times.
✓ Branch 5 taken 141550 times.
 69619780 if (!high64(num) && !high64(den)) {
83 /* Fast path: both values already fit into 64 bits */
84 59714666 uint64_t n = av_from128u(num), d = av_from128u(den);
85 59714666 const uint64_t gcd = gcd_u64(n, d);
86
2/2
✓ Branch 0 taken 59649836 times.
✓ Branch 1 taken 64830 times.
 59714666 if (gcd) {
87 59649836 n /= gcd;
88 59649836 d /= gcd;
89 }
90
91
2/2
✓ Branch 0 taken 59691583 times.
✓ Branch 1 taken 23083 times.
 59714666 if (!((n | d) >> 63)) {
92 59691583 AVRational64 res = { n, d };
93
2/2
✓ Branch 0 taken 19375206 times.
✓ Branch 1 taken 40316377 times.
 59691583 if (num_sign ^ den_sign)
94 19375206 res.num = -res.num;
95 59691583 return res;
96 }
97
98 /* Fall back to 128-bit arithmetic for values > INT64_MAX */
99 23083 num = av_to128u(n);
100 23083 den = av_to128u(d);
101 }
102
103 9928197 const av_int128 gcd = gcd128(num, den);
104
1/2
✓ Branch 0 taken 9928197 times.
✗ Branch 1 not taken.
 9928197 if (av_test128(gcd)) {
105 9928197 num = av_div128(num, gcd);
106 9928197 den = av_div128(den, gcd);
107 }
108
109 9928197 av_uint128 a0n = av_to128u(0), a0d = av_to128u(1);
110 9928197 av_uint128 a1n = av_to128u(1), a1d = av_to128u(0);
111
7/8
✓ Branch 0 taken 1173549 times.
✓ Branch 1 taken 8754648 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1173549 times.
✓ Branch 4 taken 40948 times.
✓ Branch 5 taken 8713700 times.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 40946 times.
 9928197 if (av_cmp128(num, max) <= 0 && av_cmp128(den, max) <= 0) {
112 8713702 a1n = num;
113 8713702 a1d = den;
114 8713702 goto done;
115 }
116
117
1/2
✓ Branch 0 taken 43086804 times.
✗ Branch 1 not taken.
 43086804 while (av_test128(den)) {
118 43086804 av_int128 x = av_div128(num, den);
119 43086804 av_int128 next_den = av_sub128(num, av_mul128(den, x));
120 43086804 av_uint128 a2n = av_add128(av_mul128(x, a1n), a0n);
121 43086804 av_uint128 a2d = av_add128(av_mul128(x, a1d), a0d);
122
123
6/8
✓ Branch 0 taken 1072863 times.
✓ Branch 1 taken 42013941 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1072863 times.
✓ Branch 4 taken 141632 times.
✓ Branch 5 taken 41872309 times.
✓ Branch 6 taken 141632 times.
✗ Branch 7 not taken.
 43086804 if (av_cmp128(a2n, max) > 0 || av_cmp128(a2d, max) > 0) {
124
2/2
✓ Branch 0 taken 1214493 times.
✓ Branch 1 taken 2 times.
 1214495 if (av_test128(a1n))
125 1214493 x = av_div128(av_sub128(max, a0n), a1n);
126
2/2
✓ Branch 0 taken 1214481 times.
✓ Branch 1 taken 14 times.
 1214495 if (av_test128(a1d)) {
127 1214481 av_uint128 tmp = av_div128(av_sub128(max, a0d), a1d);
128 1214481 x = av_min128(x, tmp);
129 }
130
131 1214495 av_uint128 x1d = av_mul128(x, a1d);
132 1214495 av_uint128 a = av_mul128(den, av_add128(av_add128(x1d, x1d), a0d));
133 1214495 av_uint128 b = av_mul128(num, a1d);
134
3/4
✓ Branch 0 taken 285512 times.
✓ Branch 1 taken 928983 times.
✓ Branch 2 taken 285512 times.
✗ Branch 3 not taken.
 1214495 if (av_cmp128(a, b) > 0) {
135 285512 a1n = av_add128(av_mul128(x, a1n), a0n);
136 285512 a1d = av_add128(x1d, a0d);
137 }
138 1214495 break;
139 }
140
141 41872309 a0n = a1n;
142 41872309 a0d = a1d;
143 41872309 a1n = a2n;
144 41872309 a1d = a2d;
145 41872309 num = den;
146 41872309 den = next_den;
147 }
148
149 ✗ done:;
150 9928197 AVRational64 res = { av_from128i(a1n), av_from128i(a1d) };
151
2/2
✓ Branch 0 taken 4976137 times.
✓ Branch 1 taken 4952060 times.
 9928197 if (num_sign ^ den_sign)
152 4976137 res.num = -res.num;
153 9928197 return res;
154 }
155
156 10745882492 static av_always_inline int fits31(int64_t x)
157 {
158
4/4
✓ Branch 0 taken 10705202867 times.
✓ Branch 1 taken 40679625 times.
✓ Branch 2 taken 10652072124 times.
✓ Branch 3 taken 53130743 times.
 10745882492 return x >= -INT32_MAX && x <= INT32_MAX;
159 }
160
161 2747047294 static av_always_inline int fits31_q(AVRational64 b, AVRational64 c)
162 {
163
8/8
✓ Branch 1 taken 2672660362 times.
✓ Branch 2 taken 74386932 times.
✓ Branch 4 taken 2671661774 times.
✓ Branch 5 taken 998588 times.
✓ Branch 7 taken 2654513062 times.
✓ Branch 8 taken 17148712 times.
✓ Branch 10 taken 2653236926 times.
✓ Branch 11 taken 1276136 times.
 2747047294 return fits31(b.num) && fits31(b.den) && fits31(c.num) && fits31(c.den);
164 }
165
166 /* Simplified version of reduce64() for small values */
167 1855489008 static AVRational64 reduce64_fast(int64_t num, int64_t den)
168 {
169 1855489008 const int sign = (num < 0) ^ (den < 0);
170
2/2
✓ Branch 0 taken 121978693 times.
✓ Branch 1 taken 1733510315 times.
 1855489008 uint64_t n = num < 0 ? -(uint64_t) num : num;
171
2/2
✓ Branch 0 taken 76871 times.
✓ Branch 1 taken 1855412137 times.
 1855489008 uint64_t d = den < 0 ? -(uint64_t) den : den;
172 1855489008 const uint64_t gcd = gcd_u64(n, d);
173
2/2
✓ Branch 0 taken 1609908420 times.
✓ Branch 1 taken 245580588 times.
 1855489008 if (gcd) {
174 1609908420 n /= gcd;
175 1609908420 d /= gcd;
176 }
177
178 1855489008 AVRational64 res = { n, d };
179
2/2
✓ Branch 0 taken 122037054 times.
✓ Branch 1 taken 1733451954 times.
 1855489008 if (sign)
180 122037054 res.num = -res.num;
181 1855489008 return res;
182 }
183
184
185 821938506 int ff_cmp_q64(AVRational64 a, AVRational64 b)
186 {
187 int test;
188
2/2
✓ Branch 1 taken 797747918 times.
✓ Branch 2 taken 24190588 times.
 821938506 if (fits31_q(a, b)) {
189 797747918 const int64_t p = a.num * b.den;
190 797747918 const int64_t q = b.num * a.den;
191 797747918 test = (p > q) - (p < q);
192 } else {
193 24190588 const av_int128 p = av_mul128(av_to128i(a.num), av_to128i(b.den));
194 24190588 const av_int128 q = av_mul128(av_to128i(b.num), av_to128i(a.den));
195
2/2
✓ Branch 0 taken 14938250 times.
✓ Branch 1 taken 9252338 times.
 24190588 test = av_cmp128(p, q);
196 }
197
198
2/2
✓ Branch 0 taken 524958578 times.
✓ Branch 1 taken 296979928 times.
 821938506 if (test)
199
2/2
✓ Branch 0 taken 29906 times.
✓ Branch 1 taken 524928672 times.
 524958578 return (a.den < 0) ^ (b.den < 0) ? -test : test;
200
4/4
✓ Branch 0 taken 262190156 times.
✓ Branch 1 taken 34789772 times.
✓ Branch 2 taken 240276382 times.
✓ Branch 3 taken 21913774 times.
 296979928 else if (b.den && a.den)
201 240276382 return 0;
202
4/4
✓ Branch 0 taken 13469970 times.
✓ Branch 1 taken 43233576 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 13469954 times.
 56703546 else if (a.num && b.num)
203 16 return (a.num >> 63) - (b.num >> 63);
204 else
205 56703530 return INT_MIN;
206 }
207
208 1093085214 AVRational64 ff_mul_q64(AVRational64 b, AVRational64 c)
209 {
210
2/2
✓ Branch 1 taken 1059877343 times.
✓ Branch 2 taken 33207871 times.
 1093085214 if (fits31_q(b, c))
211 1059877343 return reduce64_fast(b.num * c.num, b.den * c.den);
212
213 33207871 return reduce64(av_mul128(av_to128i(b.num), av_to128i(c.num)),
214 33207871 av_mul128(av_to128i(b.den), av_to128i(c.den)));
215 }
216
217 500 AVRational64 ff_div_q64(AVRational64 b, AVRational64 c)
218 {
219 500 return ff_mul_q64(b, ff_inv_q64(c));
220 }
221
222 832022949 AVRational64 ff_add_q64(AVRational64 b, AVRational64 c)
223 {
224
2/2
✓ Branch 1 taken 795611040 times.
✓ Branch 2 taken 36411909 times.
 832022949 if (fits31_q(b, c))
225 795611040 return reduce64_fast(b.num * c.den + c.num * b.den, b.den * c.den);
226
227 36411909 return reduce64(av_add128(av_mul128(av_to128i(b.num), av_to128i(c.den)),
228 av_mul128(av_to128i(c.num), av_to128i(b.den))),
229 36411909 av_mul128(av_to128i(b.den), av_to128i(c.den)));
230 }
231
232 625 AVRational64 ff_sub_q64(AVRational64 b, AVRational64 c)
233 {
234
1/2
✓ Branch 1 taken 625 times.
✗ Branch 2 not taken.
 625 if (fits31_q(b, c))
235 625 return reduce64_fast(b.num * c.den - c.num * b.den, b.den * c.den);
236
237 ✗ return reduce64(av_sub128(av_mul128(av_to128i(b.num), av_to128i(c.den)),
238 av_mul128(av_to128i(c.num), av_to128i(b.den))),
239 ✗ av_mul128(av_to128i(b.den), av_to128i(c.den)));
240 }
241