FFmpeg源码:av_gcd函数分析

一、引言

公约数,是一个能同时整除几个整数的数。如果一个整数同时是几个整数的约数,称这个整数为它们的“公约数”;公约数中最大的称为最大公约数。对任意的若干个正整数,1总是它们的公约数。
公约数与公倍数相反,就是既是A的约数同时也是B的约数的数,12和15的公约数有1,3,最大公约数就是3。再举个例子,30和40,它们的公约数有1,2,5,10,最大公约数是10。FFmpeg源码中使用av_gcd函数来计算两个整数的最大公约数。

二、av_gcd函数的声明

av_gcd函数声明在FFmpeg源码(本文演示用的FFmpeg源码版本为7.0.1)的头文件libavutil/mathematics.h中:

/*** Compute the greatest common divisor of two integer operands.** @param a Operand* @param b Operand* @return GCD of a and b up to sign; if a >= 0 and b >= 0, return value is >= 0;* if a == 0 and b == 0, returns 0.*/
int64_t av_const av_gcd(int64_t a, int64_t b);

该函数作用是:计算两个整数操作数的最大公约数。

形参a:输入型参数。第一个整数操作数。

形参b:输入型参数。第二个整数操作数。

返回值:两个整数操作数a和b的最大公约数。如果a和b都不小于0,返回值不小于0;如果a和b都等于0,返回值等于0(0既不是质数也不是合数 且它没有任何约数,最好避免形参值为0的情况)。

三、av_gcd函数的定义

av_gcd函数定义在FFmpeg源码的源文件libavutil/mathematics.c中:

/* Stein's binary GCD algorithm:* https://en.wikipedia.org/wiki/Binary_GCD_algorithm */
int64_t av_gcd(int64_t a, int64_t b) {int za, zb, k;int64_t u, v;if (a == 0)return b;if (b == 0)return a;za = ff_ctzll(a);zb = ff_ctzll(b);k  = FFMIN(za, zb);u = llabs(a >> za);v = llabs(b >> zb);while (u != v) {if (u > v)FFSWAP(int64_t, v, u);v -= u;v >>= ff_ctzll(v);}return (uint64_t)u << k;
}

该函数内部使用了二进制GCD算法寻找两个整数操作数的最大公约数。二进制GCD算法(binary GCD algorithm),也被称为Stein's算法或二进制欧氏算法(binary Euclidean algorithm),是一种计算两个非负整数的最大公约数(GCD)的算法。Stein's算法比传统的Euclidean算法使用更简单的算术运算,它用算术移位、比较和减法代替除法(用移位的方法得到代码比调用乘除法子程序生成的代码效率高。实际上,只要是乘以或除以一个整数,均可以想办法用移位的方法得到结果。整数除法是整数运算中最慢的,所以应该尽可能避免)。

虽然这种现代形式的算法是由物理学家和程序员Josef Stein在1967年首次发表的,但它在公元前2世纪,即古代中国被人们所知。

四、编写av_gcd函数的使用例子

编写测试例子main.c,在Ubuntu中使用9.4.0版本的gcc编译通过:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>
#include <features.h>#ifdef __GNUC__
#    define AV_GCC_VERSION_AT_LEAST(x,y) (__GNUC__ > (x) || __GNUC__ == (x) && __GNUC_MINOR__ >= (y))
#    define AV_GCC_VERSION_AT_MOST(x,y)  (__GNUC__ < (x) || __GNUC__ == (x) && __GNUC_MINOR__ <= (y))
#else
#    define AV_GCC_VERSION_AT_LEAST(x,y) 0
#    define AV_GCC_VERSION_AT_MOST(x,y)  0
#endif#ifndef av_always_inline
#if AV_GCC_VERSION_AT_LEAST(3,1)
#    define av_always_inline __attribute__((always_inline)) inline
#elif defined(_MSC_VER)
#    define av_always_inline __forceinline
#else
#    define av_always_inline inline
#endif
#endif#if AV_GCC_VERSION_AT_LEAST(2,6) || defined(__clang__)
#    define av_const __attribute__((const))
#else
#    define av_const
#endif#define FFMIN(a,b) ((a) > (b) ? (b) : (a))
#define FFSWAP(type,a,b) do{type SWAP_tmp= b; b= a; a= SWAP_tmp;}while(0)#ifdef __USE_ISOC99
__extension__ extern long long int llabs (long long int __x)__THROW __attribute__ ((__const__)) __wur;
#endif#ifndef ff_ctzll
#define ff_ctzll ff_ctzll_c
/* We use the De-Bruijn method outlined in:* http://supertech.csail.mit.edu/papers/debruijn.pdf. */
static av_always_inline av_const int ff_ctzll_c(long long v)
{static const uint8_t debruijn_ctz64[64] = {0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12};return debruijn_ctz64[(uint64_t)((v & -v) * 0x022FDD63CC95386DU) >> 58];
}
#endifint64_t av_gcd(int64_t a, int64_t b) {int za, zb, k;int64_t u, v;if (a == 0)return b;if (b == 0)return a;za = ff_ctzll(a);zb = ff_ctzll(b);k  = FFMIN(za, zb);u = llabs(a >> za);v = llabs(b >> zb);while (u != v) {if (u > v)FFSWAP(int64_t, v, u);v -= u;v >>= ff_ctzll(v);}return (uint64_t)u << k;
}int main()
{int64_t a = 12;int64_t b = 15;printf("av_gcd(%ld, %ld): %ld\n", a, b, av_gcd(a, b));int64_t c = 30;int64_t d = 40;printf("av_gcd(%ld, %ld): %ld\n", c, d, av_gcd(c, d));int64_t e = 0;int64_t f = 5;printf("av_gcd(%ld, %ld): %ld\n", e, f, av_gcd(e, f));int64_t g = 0;int64_t h = 0;printf("av_gcd(%ld, %ld): %ld\n", g, h, av_gcd(g, h));return 0;
}

输出如下:

五、参考

维基百科:《Binary GCD algorithm》

百度百科:《公约数》

《C语言如何用移位来解决乘除法问题》

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/389989.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DB-Engines Ranking 2024年8月数据库排行

DB-Engines Ranking 2024年8月数据库排行 DB-Engines排名根据数据库管理系统的受欢迎程度进行排名。排名每月更新一次。 2024年8月&#xff0c;共有423个数据库进入排行。 排行榜 前15名趋势图 关系型数据库前 10 名 键值数据库前 10 名 文档数据库前 10 名 时序数据库前 10 …

Google引领LLM竞赛:Gemini 1.5 Pro的创新与突破

在科技领域&#xff0c;语言模型&#xff08;LLM, Large Language Model&#xff09;的发展总是备受瞩目。多年来&#xff0c;Google在这场竞赛中一直处于追赶的状态&#xff0c;但这一次&#xff0c;他们终于站在了领先的位置。Google近日发布了Gemini 1.5 Pro实验版本&#x…

Nginx进阶-常见配置

一、nginx Proxy 反向代理 1、代理原理 反向代理产生的背景&#xff1a; 在计算机世界里&#xff0c;由于单个服务器的处理客户端&#xff08;用户&#xff09;请求能力有一个极限&#xff0c;当用户的接入请求蜂拥而入时&#xff0c;会造成服务器忙不过来的局面&#xff0c…

Unity后处理(Post-processing)

Unity post-processing 就像是对图片采用滤镜一样&#xff08;如下图对比&#xff09;对当前场景显示做一定的显示处理&#xff0c;使得场景更漂亮、有趣或者有型。 视觉风格与视觉保真 游戏场景后处理能够达到所需的视觉风格&#xff08;visual style&#xff09;同时也保证视…

文件解析漏洞

IIS解析漏洞 在windows Server 2003安装iis 1.IIS6.X 1.1 目录解析 在网站下建立文件夹的名字为 .asp/.asa 的文件夹&#xff0c;其目录内的任何扩展名的文件都被IIS当作asp文件来解析并执行。 先创建一个1.asp文件夹 再创建一个1.txt 里面写 <%now()%> 2.1 畸形文件…

DTU、RTU和边缘计算网关的联系与区别

在工业4.0发展浪潮中&#xff0c;物联网助力工业逐渐向智能化发展&#xff0c;各种工业设备相互连接起来形成物联网。而传输层作为物联网体系中十分重要的一环&#xff0c;它是连接物理世界与数字世界的桥梁&#xff0c;是数据的第一入口。 其中&#xff0c;我们经常会使用到三…

jQuery入门(五)Ajax和json

一、Ajax 简介 AJAX(Asynchronous JavaScript And XML)&#xff1a;异步的 JavaScript 和 XML。 本身不是一种新技术&#xff0c;而是多个技术综合。用于快速创建动态网页的技术。 一般的网页如果需要更新内容&#xff0c;必需重新加载个页面。 而 AJAX 通过浏览器与服务器进行…

windows内存泄漏检查汇总

VLD(Visual Leak Detector) 下载 官方下载地址2.5 另一分支2.7 安装 点击运行安装

苹果手机升级iOS18测试版本后使用体验不好?怎么降级?

近期苹果发布了诸多的iOS18版本给用户提前尝鲜测试&#xff0c;许多果粉们都迫不及待的选择了升级&#xff0c;但是有不少的果粉升级时没有考虑到设备适配性问题&#xff0c;导致升级之后手机变得有些卡顿&#xff0c;使用体验不好时&#xff0c;想要降级回到正式的版本&#x…

ubuntu安装nginx以及php的部署

1.安装依赖包 apt-get install gcc apt-get install libpcre3 libpcre3-dev apt-get install zlib1g zlib1g-dev sudo apt-get install openssl sudo apt-get install libssl-dev 2.安装nginx cd /usr/local mkdir nginx cd nginx tar -xvf nginx-1.21.6.tar.gz 3.编译…

【考研高数】反函数的那些事

在这里给同学们推荐来自「荒原之梦考研数学」网的三篇文章&#xff0c;分别是反函数的性质汇总&#xff0c;以及两道相关习题&#xff0c;有需要加强这部分练习的同学&#xff0c;可以点击下方链接&#xff0c;在「荒原之梦考研数学」官网中打开对应的文章&#xff1a; 《反函…

【算法】双指针-OJ题详解1

双指针-OJ题 移动零&#xff08;点击跳转&#xff09;原理讲解代码实现 复写零&#xff08;点击跳转&#xff09;原理讲解代码实现 快乐数&#xff08;点击跳转&#xff09;原理讲解代码实现 盛最多水的容器&#xff08;点击跳转&#xff09;原理讲解代码实现 有效三角形的个数…

C语言自定义类型结构体与位段超详解

文章目录 1. 结构体类型的声明1. 1 结构体声明1. 2 结构体变量的创建和初始化1. 3 结构体的特殊声明1. 3 结构体的自引用 2. 结构体内存对齐2. 1 对齐规则2. 2 为什么存在内存对齐2. 3 修改默认对齐数 3. 结构体传参4. 结构体实现位段4. 1 什么是位段4. 2 位段成员的内存分配4.…

吴恩达老师机器学习作业-ex7

导入库&#xff0c;读取数据&#xff0c;查看数据类型等进行分析&#xff0c;可视化数据 import matplotlib.pyplot as plt import numpy as np import scipy.io as sio#读取数据 path "./ex7data2.mat" data sio.loadmat(path) # print(type(data)) # print(data…

Java | Leetcode Java题解之第316题去除重复字母

题目&#xff1a; 题解&#xff1a; class Solution {public String removeDuplicateLetters(String s) {boolean[] vis new boolean[26];int[] num new int[26];for (int i 0; i < s.length(); i) {num[s.charAt(i) - a];}StringBuffer sb new StringBuffer();for (in…

nginx续1:

八、虚拟主机配置 基于域名的虚拟主机 [rootserver2 ~]# ps -au|grep nginx //查看进程 修改Nginx服务配置&#xff0c;添加相关虚拟主机配置如下 1. [rootproxy ~]# vim /usr/local/nginx/conf/nginx.conf 2. .. .. 3. server { 4. listen …

第15课 Scratch少儿编程 入门篇:师生问候

师生问候 故事背景&#xff1a; 魔法学院的期末考核刚刚考完&#xff0c;魔法老师在教室里碰到小明&#xff0c;老师问小明考的怎么样&#xff1f; 程序原理&#xff1a; 找一个教室的背景&#xff0c;小精灵角色和魔法师的角色&#xff0c;将魔法师的角色造型左右反转&…

MyBatis 源码学习 | Day 1 | 了解 MyBatis

什么是 MyBatis 在对一项技术进行深入学习前&#xff0c;我们应该先对它有个初步的认识。MyBatis 是一个 Java 持久层框架&#xff0c;用于简化数据库的操作。它通过 XML 或注解的方式配置和映射原始类型、接口和 Java POJO&#xff08;Plain Old Java Objects&#xff0c;普通…

如何理解复信号z的傅里叶变换在频率v<0的时候恒为0,是解析信号

考虑例子2.12.1的说法。 首先我尝试解释第二个说法。需要注意一个事实是 实函数f的傅里叶变换F的实部是偶函数&#xff0c;虚部是奇函数。如图所示&#xff1a; 注意的是这个图中虽然是离散傅里叶变换的性质&#xff0c;但是对于一般的傅里叶变换的性质是适用的。 推导过程如下…