专栏首页科技分享linux内核中的宏ffs(x)

linux内核中的宏ffs(x)

linux内核中ffs(x)宏是平台相关的宏,在arm平台,该宏定义在

arch/arm/include/asm/bitops.h

#define ffs(x) ({ unsigned long __t = (x); fls(__t & -__t); })
static inline int fls(int x)
{
    int ret;

    if (__builtin_constant_p(x))
           return constant_fls(x);

    asm("clz\t%0, %1" : "=r" (ret) : "r" (x) : "cc");
           ret = 32 - ret;
    return ret;
}

__t & -__t 等于找到__t 第一个为1的位(从低位开始),并把该位保留为1其余位清0.

例如 一32位整形数 6,用二进制表示它的低8位:00000110, 都知道负数为最高为1其余位取反加1.-6即 11111010

相与得 00000010,即6&-6. 把该值传递给函数fls().

再看fls函数.

if (__builtin_constant_p(x)) return constant_fls(x);

__builtin_constant_p 是Gcc的内建函数 ,用于判断一个值是否为编译时常数,如果参数的值是常数,函数返回 1,否则返回 0。

如果是常数就用下面函数计算00000010中1的位置

static inline int constant_fls(int x)
{
    int r = 32;

    if (!x)
        return 0;
    if (!(x & 0xffff0000u)) {
        x <<= 16;
        r -= 16;
    }
    if (!(x & 0xff000000u)) {
        x <<= 8;
        r -= 8;
    }
    if (!(x & 0xf0000000u)) {
        x <<= 4;
        r -= 4;
    }
    if (!(x & 0xc0000000u)) {
        x <<= 2;
        r -= 2;
    }
    if (!(x & 0x80000000u)) {
        x <<= 1;
        r -= 1;
    }
    return r;
}

算法就是折半法,这个函数计算的是从高位起第一个1位的位置.00000010, r=2. 由于__t&-__t只有一个1,所以就是找到该1的位置.

如果输入参数是00001010 那么 r=4.

如果参数是变量,直接使用arm指令运算.

执行 asm("clz\t%0, %1" : "=r" (ret) : "r" (x) : "cc"); ret = 32 - ret; CLZ(Count Leading Zeros)指令对Rm中值的高位(leading zeros)个数进行计数,结果放到Rd中。若源寄存器全为0,则结果为32。若[31]为1,则结果为0。

clz指令计算高位0的个数, 然后拿32-ret 算出1的位置.

所以,ffs(x)这个宏的值就是x的第一个1的位置(从低位开始,数值从1开始,0代表x全0).

另外,该文件中还有很多linux关于位操作的函数,可以作为自己写应用程序时的有用参考.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux下对input设备调用ioctl时指定EVIOCGBIT选项时的缓冲区该多大【转】

    转自:https://blog.csdn.net/imred/article/details/82669990

    用户3033338
  • 用户态与内核态 & 文件流与文件描述符 简介

    区分用户态和内核态主要是由于系统资源的有限性,不能无限制的随意分配给用户使用,必须由系统进行统一管理

    用户3033338
  • 用户态与内核态 & 文件流与文件描述符 简介【转】

    转自:https://www.cnblogs.com/Jimmy1988/p/7479856.html

    用户3033338
  • HashMap的实现原理浅析

    查看HashMap源代码,可以发现其继承自AbstractMap, 并实现了Map, Cloneable, Serializable接口

    孟君
  • 【USACO 1.3】Ski Course Design

    n个点(n<=1000)大小范围[0,100],改变一些点的值,使得极差不超过17,代价为改变值的平方。

    饶文津
  • CodeForces 919B Perfect Number(水题)

    Ch_Zaqdt
  • 死磕 java集合之HashMap源码分析

    HashMap采用key/value存储结构,每个key对应唯一的value,查询和修改的速度都很快,能达到O(1)的平均时间复杂度。它是非线程安全的,且不保证...

    彤哥
  • 一文解读JDK8中HashMap的源码

    HashMap是平时开发中非常常用的一个集合框架类,了解其内部构造及运行原理可以说是每一个Java程序员必不可少的,接下来就从源码一探究竟HashMap到底是什...

    beifengtz
  • 面试官:HashMap 源码你都不知道还来面试?

    HashMap采用key/value存储结构,每个key对应唯一的value,查询和修改的速度都很快,能达到O(1)的平均时间复杂度。它是非线程安全的,且不保证...

    zhisheng
  • HashMap源码分析(II)

    上一节主要讲述了HashMap的一些基础属性和构造方法,本节将会讲述HashMap的核心方法。

    shysh95

扫码关注云+社区

领取腾讯云代金券