FFmpeg
mathematics.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2005-2012 Michael Niedermayer <michaelni@gmx.at>
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20 
21 /**
22  * @file
23  * miscellaneous math routines and tables
24  */
25 
26 #include <stdint.h>
27 #include <limits.h>
28 
29 #include "mathematics.h"
30 #include "libavutil/intmath.h"
31 #include "libavutil/common.h"
32 #include "avassert.h"
33 
34 /* Stein's binary GCD algorithm:
35  * https://en.wikipedia.org/wiki/Binary_GCD_algorithm */
36 int64_t av_gcd(int64_t a, int64_t b) {
37  int za, zb, k;
38  int64_t u, v;
39  if (a == 0)
40  return b;
41  if (b == 0)
42  return a;
43  za = ff_ctzll(a);
44  zb = ff_ctzll(b);
45  k = FFMIN(za, zb);
46  u = llabs(a >> za);
47  v = llabs(b >> zb);
48  while (u != v) {
49  if (u > v)
50  FFSWAP(int64_t, v, u);
51  v -= u;
52  v >>= ff_ctzll(v);
53  }
54  return (uint64_t)u << k;
55 }
56 
57 int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd)
58 {
59  int64_t r = 0;
60  av_assert2(c > 0);
61  av_assert2(b >=0);
62  av_assert2((unsigned)(rnd&~AV_ROUND_PASS_MINMAX)<=5 && (rnd&~AV_ROUND_PASS_MINMAX)!=4);
63 
64  if (c <= 0 || b < 0 || !((unsigned)(rnd&~AV_ROUND_PASS_MINMAX)<=5 && (rnd&~AV_ROUND_PASS_MINMAX)!=4))
65  return INT64_MIN;
66 
67  if (rnd & AV_ROUND_PASS_MINMAX) {
68  if (a == INT64_MIN || a == INT64_MAX)
69  return a;
70  rnd -= AV_ROUND_PASS_MINMAX;
71  }
72 
73  if (a < 0)
74  return -(uint64_t)av_rescale_rnd(-FFMAX(a, -INT64_MAX), b, c, rnd ^ ((rnd >> 1) & 1));
75 
76  if (rnd == AV_ROUND_NEAR_INF)
77  r = c / 2;
78  else if (rnd & 1)
79  r = c - 1;
80 
81  if (b <= INT_MAX && c <= INT_MAX) {
82  if (a <= INT_MAX)
83  return (a * b + r) / c;
84  else {
85  int64_t ad = a / c;
86  int64_t a2 = (a % c * b + r) / c;
87  if (ad >= INT32_MAX && b && ad > (INT64_MAX - a2) / b)
88  return INT64_MIN;
89  return ad * b + a2;
90  }
91  } else {
92 #if 1
93  uint64_t a0 = a & 0xFFFFFFFF;
94  uint64_t a1 = a >> 32;
95  uint64_t b0 = b & 0xFFFFFFFF;
96  uint64_t b1 = b >> 32;
97  uint64_t t1 = a0 * b1 + a1 * b0;
98  uint64_t t1a = t1 << 32;
99  int i;
100 
101  a0 = a0 * b0 + t1a;
102  a1 = a1 * b1 + (t1 >> 32) + (a0 < t1a);
103  a0 += r;
104  a1 += a0 < r;
105 
106  for (i = 63; i >= 0; i--) {
107  a1 += a1 + ((a0 >> i) & 1);
108  t1 += t1;
109  if (c <= a1) {
110  a1 -= c;
111  t1++;
112  }
113  }
114  if (t1 > INT64_MAX)
115  return INT64_MIN;
116  return t1;
117 #else
118  /* reference code doing (a*b + r) / c, requires libavutil/integer.h */
119  AVInteger ai;
120  ai = av_mul_i(av_int2i(a), av_int2i(b));
121  ai = av_add_i(ai, av_int2i(r));
122 
123  return av_i2int(av_div_i(ai, av_int2i(c)));
124 #endif
125  }
126 }
127 
128 int64_t av_rescale(int64_t a, int64_t b, int64_t c)
129 {
130  return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);
131 }
132 
133 int64_t av_rescale_q_rnd(int64_t a, AVRational bq, AVRational cq,
134  enum AVRounding rnd)
135 {
136  int64_t b = bq.num * (int64_t)cq.den;
137  int64_t c = cq.num * (int64_t)bq.den;
138  return av_rescale_rnd(a, b, c, rnd);
139 }
140 
141 int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq)
142 {
143  return av_rescale_q_rnd(a, bq, cq, AV_ROUND_NEAR_INF);
144 }
145 
146 int av_compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b)
147 {
148  int64_t a = tb_a.num * (int64_t)tb_b.den;
149  int64_t b = tb_b.num * (int64_t)tb_a.den;
150  if ((FFABS64U(ts_a)|a|FFABS64U(ts_b)|b) <= INT_MAX)
151  return (ts_a*a > ts_b*b) - (ts_a*a < ts_b*b);
152  if (av_rescale_rnd(ts_a, a, b, AV_ROUND_DOWN) < ts_b)
153  return -1;
154  if (av_rescale_rnd(ts_b, b, a, AV_ROUND_DOWN) < ts_a)
155  return 1;
156  return 0;
157 }
158 
159 int64_t av_compare_mod(uint64_t a, uint64_t b, uint64_t mod)
160 {
161  int64_t c = (a - b) & (mod - 1);
162  if (c > (mod >> 1))
163  c -= mod;
164  return c;
165 }
166 
167 int64_t av_rescale_delta(AVRational in_tb, int64_t in_ts, AVRational fs_tb, int duration, int64_t *last, AVRational out_tb){
168  int64_t a, b, this;
169 
170  av_assert0(in_ts != AV_NOPTS_VALUE);
171  av_assert0(duration >= 0);
172 
173  if (*last == AV_NOPTS_VALUE || !duration || in_tb.num*(int64_t)out_tb.den <= out_tb.num*(int64_t)in_tb.den) {
174 simple_round:
175  *last = av_rescale_q(in_ts, in_tb, fs_tb) + duration;
176  return av_rescale_q(in_ts, in_tb, out_tb);
177  }
178 
179  a = av_rescale_q_rnd(2*in_ts-1, in_tb, fs_tb, AV_ROUND_DOWN) >>1;
180  b = (av_rescale_q_rnd(2*in_ts+1, in_tb, fs_tb, AV_ROUND_UP )+1)>>1;
181  if (*last < 2*a - b || *last > 2*b - a)
182  goto simple_round;
183 
184  this = av_clip64(*last, a, b);
185  *last = this + duration;
186 
187  return av_rescale_q(this, fs_tb, out_tb);
188 }
189 
190 int64_t av_add_stable(AVRational ts_tb, int64_t ts, AVRational inc_tb, int64_t inc)
191 {
192  int64_t m, d;
193 
194  if (inc != 1)
195  inc_tb = av_mul_q(inc_tb, (AVRational) {inc, 1});
196 
197  m = inc_tb.num * (int64_t)ts_tb.den;
198  d = inc_tb.den * (int64_t)ts_tb.num;
199 
200  if (m % d == 0 && ts <= INT64_MAX - m / d)
201  return ts + m / d;
202  if (m < d)
203  return ts;
204 
205  {
206  int64_t old = av_rescale_q(ts, ts_tb, inc_tb);
207  int64_t old_ts = av_rescale_q(old, inc_tb, ts_tb);
208 
209  if (old == INT64_MAX || old == AV_NOPTS_VALUE || old_ts == AV_NOPTS_VALUE)
210  return ts;
211 
212  return av_sat_add64(av_rescale_q(old + 1, inc_tb, ts_tb), ts - old_ts);
213  }
214 }
r
const char * r
Definition: vf_curves.c:116
av_compare_ts
int av_compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b)
Compare two timestamps each in its own time base.
Definition: mathematics.c:146
av_add_stable
int64_t av_add_stable(AVRational ts_tb, int64_t ts, AVRational inc_tb, int64_t inc)
Add a value to a timestamp.
Definition: mathematics.c:190
u
#define u(width, name, range_min, range_max)
Definition: cbs_h2645.c:264
b
#define b
Definition: input.c:40
AVRounding
AVRounding
Rounding methods.
Definition: mathematics.h:79
t1
#define t1
Definition: regdef.h:29
mathematics.h
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
av_i2int
int64_t av_i2int(AVInteger a)
Convert the given AVInteger to an int64_t.
Definition: integer.c:158
av_gcd
int64_t av_gcd(int64_t a, int64_t b)
Compute the greatest common divisor of two integer operands.
Definition: mathematics.c:36
b1
static double b1(void *priv, double x, double y)
Definition: vf_xfade.c:1703
AV_ROUND_UP
@ AV_ROUND_UP
Round toward +infinity.
Definition: mathematics.h:83
AVRational::num
int num
Numerator.
Definition: rational.h:59
av_clip64
#define av_clip64
Definition: common.h:99
a1
#define a1
Definition: regdef.h:47
avassert.h
rnd
#define rnd()
Definition: checkasm.h:111
duration
int64_t duration
Definition: movenc.c:64
av_int2i
AVInteger av_int2i(int64_t a)
Convert the given int64_t to an AVInteger.
Definition: integer.c:147
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
limits.h
av_rescale_q
int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq)
Rescale a 64-bit integer by 2 rational numbers.
Definition: mathematics.c:141
av_rescale_delta
int64_t av_rescale_delta(AVRational in_tb, int64_t in_ts, AVRational fs_tb, int duration, int64_t *last, AVRational out_tb)
Rescale a timestamp while preserving known durations.
Definition: mathematics.c:167
av_add_i
AVInteger av_add_i(AVInteger a, AVInteger b)
Definition: integer.c:34
AVRational
Rational number (pair of numerator and denominator).
Definition: rational.h:58
ff_ctzll
#define ff_ctzll
Definition: intmath.h:126
AV_ROUND_NEAR_INF
@ AV_ROUND_NEAR_INF
Round to nearest and halfway cases away from zero.
Definition: mathematics.h:84
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
av_rescale_rnd
int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd)
Rescale a 64-bit integer with specified rounding.
Definition: mathematics.c:57
AV_NOPTS_VALUE
#define AV_NOPTS_VALUE
Undefined timestamp value.
Definition: avutil.h:248
av_mul_i
AVInteger av_mul_i(AVInteger a, AVInteger b)
Definition: integer.c:64
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
a0
#define a0
Definition: regdef.h:46
av_assert2
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:64
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:271
AVInteger
Definition: integer.h:36
a2
#define a2
Definition: regdef.h:48
common.h
AV_ROUND_DOWN
@ AV_ROUND_DOWN
Round toward -infinity.
Definition: mathematics.h:82
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
av_rescale
int64_t av_rescale(int64_t a, int64_t b, int64_t c)
Rescale a 64-bit integer with rounding to nearest.
Definition: mathematics.c:128
mod
static int mod(int a, int b)
Modulo operation with only positive remainders.
Definition: vf_v360.c:749
av_compare_mod
int64_t av_compare_mod(uint64_t a, uint64_t b, uint64_t mod)
Compare the remainders of two integer operands divided by a common divisor.
Definition: mathematics.c:159
FFSWAP
#define FFSWAP(type, a, b)
Definition: macros.h:52
av_div_i
AVInteger av_div_i(AVInteger a, AVInteger b)
Return a/b.
Definition: integer.c:141
av_sat_add64
#define av_sat_add64
Definition: common.h:138
AVRational::den
int den
Denominator.
Definition: rational.h:60
av_mul_q
AVRational av_mul_q(AVRational b, AVRational c)
Multiply two rationals.
Definition: rational.c:80
AV_ROUND_PASS_MINMAX
@ AV_ROUND_PASS_MINMAX
Flag telling rescaling functions to pass INT64_MIN/MAX through unchanged, avoiding special cases for ...
Definition: mathematics.h:108
d
d
Definition: ffmpeg_filter.c:153
b0
static double b0(void *priv, double x, double y)
Definition: vf_xfade.c:1702
FFABS64U
#define FFABS64U(a)
Definition: common.h:83
av_rescale_q_rnd
int64_t av_rescale_q_rnd(int64_t a, AVRational bq, AVRational cq, enum AVRounding rnd)
Rescale a 64-bit integer by 2 rational numbers with specified rounding.
Definition: mathematics.c:133
intmath.h
Generated on Wed Aug 24 2022 21:38:30 for FFmpeg by   doxygen 1.8.17