FFmpeg: libavutil/mathematics.c Source File

FFmpeg

[フレーム]

libavutil

mathematics.c

Go to the documentation of this file.

1 /*

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 */

21 /**

22 * @file

23 * miscellaneous math routines and tables

24 */

26 #include <stdint.h>

27 #include <limits.h>

29 #include "avutil.h"

30 #include "mathematics.h"

31 #include "libavutil/intmath.h"

32 #include "libavutil/common.h"

33 #include "avassert.h"

35 /* Stein's binary GCD algorithm:

36 * https://en.wikipedia.org/wiki/Binary_GCD_algorithm */

37 int64_t av_gcd(int64_t a, int64_t b) {

38 int za, zb, k;

39 int64_t u, v;

40 if (a == 0)

41 return b;

42 if (b == 0)

43 return a;

44 za = ff_ctzll(a);

45 zb = ff_ctzll(b);

46 k = FFMIN(za, zb);

47 u = llabs(a >> za);

48 v = llabs(b >> zb);

49 while (u != v) {

50 if (u > v)

51 FFSWAP(int64_t, v, u);

52 v -= u;

53 v >>= ff_ctzll(v);

54 }

55 return (uint64_t)u << k;

56 }

58 int64_t av_rescale_rnd(int64_t a, int64_t b, int64_t c, enum AVRounding rnd)

59 {

60 int64_t r = 0;

61 av_assert2(c > 0);

62 av_assert2(b >=0);

63 av_assert2((unsigned)(rnd&~AV_ROUND_PASS_MINMAX)<=5 && (rnd&~AV_ROUND_PASS_MINMAX)!=4);

65 if (c <= 0 || b < 0 || !((unsigned)(rnd&~AV_ROUND_PASS_MINMAX)<=5 && (rnd&~AV_ROUND_PASS_MINMAX)!=4))

66 return INT64_MIN;

68 if (rnd & AV_ROUND_PASS_MINMAX) {

69 if (a == INT64_MIN || a == INT64_MAX)

70 return a;

71 rnd -= AV_ROUND_PASS_MINMAX;

72 }

74 if (a < 0)

75 return -(uint64_t)av_rescale_rnd(-FFMAX(a, -INT64_MAX), b, c, rnd ^ ((rnd >> 1) & 1));

77 if (rnd == AV_ROUND_NEAR_INF)

78 r = c / 2;

79 else if (rnd & 1)

80 r = c - 1;

82 if (b <= INT_MAX && c <= INT_MAX) {

83 if (a <= INT_MAX)

84 return (a * b + r) / c;

85 else {

86 int64_t ad = a / c;

87 int64_t a2 = (a % c * b + r) / c;

88 if (ad >= INT32_MAX && b && ad > (INT64_MAX - a2) / b)

89 return INT64_MIN;

90 return ad * b + a2;

91 }

92 } else {

93 #if 1

94 uint64_t a0 = a & 0xFFFFFFFF;

95 uint64_t a1 = a >> 32;

96 uint64_t b0 = b & 0xFFFFFFFF;

97 uint64_t b1 = b >> 32;

98 uint64_t t1 = a0 * b1 + a1 * b0;

99 uint64_t t1a = t1 << 32;

100 int i;

101

102 a0 = a0 * b0 + t1a;

103 a1 = a1 * b1 + (t1 >> 32) + (a0 < t1a);

104 a0 += r;

105 a1 += a0 < r;

106

107 for (i = 63; i >= 0; i--) {

108 a1 += a1 + ((a0 >> i) & 1);

109 t1 += t1;

110 if (c <= a1) {

111 a1 -= c;

112 t1++;

113 }

114 }

115 if (t1 > INT64_MAX)

116 return INT64_MIN;

117 return t1;

118 #else

119 /* reference code doing (a*b + r) / c, requires libavutil/integer.h */

120 AVInteger ai;

121 ai = av_mul_i(av_int2i(a), av_int2i(b));

122 ai = av_add_i(ai, av_int2i(r));

123

124 return av_i2int(av_div_i(ai, av_int2i(c)));

125 #endif

126 }

127 }

128

129 int64_t av_rescale(int64_t a, int64_t b, int64_t c)

130 {

131 return av_rescale_rnd(a, b, c, AV_ROUND_NEAR_INF);

132 }

133

134 int64_t av_rescale_q_rnd(int64_t a, AVRational bq, AVRational cq,

135 enum AVRounding rnd)

136 {

137 int64_t b = bq.num * (int64_t)cq.den;

138 int64_t c = cq.num * (int64_t)bq.den;

139 return av_rescale_rnd(a, b, c, rnd);

140 }

141

142 int64_t av_rescale_q(int64_t a, AVRational bq, AVRational cq)

143 {

144 return av_rescale_q_rnd(a, bq, cq, AV_ROUND_NEAR_INF);

145 }

146

147 int av_compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b, AVRational tb_b)

148 {

149 int64_t a = tb_a.num * (int64_t)tb_b.den;

150 int64_t b = tb_b.num * (int64_t)tb_a.den;

151 if ((FFABS64U(ts_a)|a|FFABS64U(ts_b)|b) <= INT_MAX)

152 return (ts_a*a > ts_b*b) - (ts_a*a < ts_b*b);

153 if (av_rescale_rnd(ts_a, a, b, AV_ROUND_DOWN) < ts_b)

154 return -1;

155 if (av_rescale_rnd(ts_b, b, a, AV_ROUND_DOWN) < ts_a)

156 return 1;

157 return 0;

158 }

159

160 int64_t av_compare_mod(uint64_t a, uint64_t b, uint64_t mod)

161 {

162 int64_t c = (a - b) & (mod - 1);

163 if (c > (mod >> 1))

164 c -= mod;

165 return c;

166 }

167

168 int64_t av_rescale_delta(AVRational in_tb, int64_t in_ts, AVRational fs_tb, int duration, int64_t *last, AVRational out_tb){

169 int64_t a, b, this;

170

171 av_assert0(in_ts != AV_NOPTS_VALUE);

172 av_assert0(duration >= 0);

173

174 if (*last == AV_NOPTS_VALUE || !duration || in_tb.num*(int64_t)out_tb.den <= out_tb.num*(int64_t)in_tb.den) {

175 simple_round:

176 *last = av_rescale_q(in_ts, in_tb, fs_tb) + duration;

177 return av_rescale_q(in_ts, in_tb, out_tb);

178 }

179

180 a = av_rescale_q_rnd(2*in_ts-1, in_tb, fs_tb, AV_ROUND_DOWN) >>1;

181 b = (av_rescale_q_rnd(2*in_ts+1, in_tb, fs_tb, AV_ROUND_UP )+1)>>1;

182 if (*last < 2*a - b || *last > 2*b - a)

183 goto simple_round;

184

185 this = av_clip64(*last, a, b);

186 *last = this + duration;

187

188 return av_rescale_q(this, fs_tb, out_tb);

189 }

190

191 int64_t av_add_stable(AVRational ts_tb, int64_t ts, AVRational inc_tb, int64_t inc)

192 {

193 int64_t m, d;

194

195 if (inc != 1)

196 inc_tb = av_mul_q(inc_tb, (AVRational) {inc, 1});

197

198 m = inc_tb.num * (int64_t)ts_tb.den;

199 d = inc_tb.den * (int64_t)ts_tb.num;

200

201 if (m % d == 0 && ts <= INT64_MAX - m / d)

202 return ts + m / d;

203 if (m < d)

204 return ts;

205

206 {

207 int64_t old = av_rescale_q(ts, ts_tb, inc_tb);

208 int64_t old_ts = av_rescale_q(old, inc_tb, ts_tb);

209

210 if (old == INT64_MAX || old == AV_NOPTS_VALUE || old_ts == AV_NOPTS_VALUE)

211 return ts;

212

213 return av_sat_add64(av_rescale_q(old + 1, inc_tb, ts_tb), ts - old_ts);

214 }

215 }

const char * r

Definition: vf_curves.c:126

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:147

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:191

#define u(width, name, range_min, range_max)

Definition: cbs_h2645.c:262

#define b

Definition: input.c:41

AVRounding

Rounding methods.

Definition: mathematics.h:79

#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:160

av_gcd

int64_t av_gcd(int64_t a, int64_t b)

Compute the greatest common divisor of two integer operands.

Definition: mathematics.c:37

static double b1(void *priv, double x, double y)

Definition: vf_xfade.c:1771

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:98

#define a1

Definition: regdef.h:47

avassert.h

rnd

#define rnd()

Definition: checkasm.h:118

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:149

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:142

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:168

av_add_i

AVInteger av_add_i(AVInteger a, AVInteger b)

Definition: integer.c:36

AVRational

Rational number (pair of numerator and denominator).

Definition: rational.h:58

ff_ctzll

#define ff_ctzll

Definition: intmath.h:127

AV_ROUND_NEAR_INF

@ AV_ROUND_NEAR_INF

Round to nearest and halfway cases away from zero.

Definition: mathematics.h:84

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:58

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:66

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

#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

#define i(width, name, range_min, range_max)

Definition: cbs_h2645.c:269

AVInteger

Definition: integer.h:36

#define a2