Bit Operations

Bitmap Operations에서 사용하는 함수와 많은 부분 중복된다.

fls()

arch/arm/include/asm/bitops.h

/*
 * fls() returns zero if the input is zero, otherwise returns the bit
 * position of the last set bit, where the LSB is 1 and MSB is 32.
 */
static inline int fls(int x)
{
        if (__builtin_constant_p(x))
               return constant_fls(x);

        return 32 - __clz(x);
}
  • 셋 되어 있는 마지막 비트의 위치(1~32)를 리턴한다. x 값이 0 즉, 설정된 비트가 없으면 0을 리턴한다.
  • 인수 x 값이 상수이면 constant_fls() 함수를 사용하고 상수가 아니면 __clz() 함수를 사용한다.

bitops-1

 

__fls()

arch/arm/include/asm/bitops.h

/*
 * __fls() returns the bit position of the last bit set, where the
 * LSB is 0 and MSB is 31.  Zero input is undefined.
 */
static inline unsigned long __fls(unsigned long x)
{       
        return fls(x) - 1;
}
  • lsb -> msb 방향으로 가장 마지막 bit가 1인 bit 번호를 리턴한다. (based 0)
    • 예) 0x0000_0011 -> 0
    • 예) 0x8800_0000 -> 31

 

constant_fls()

arch/arm/include/asm/bitops.h

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~32)를 리턴한다. x 값이 0 즉, 설정된 비트가 없으면 0을 리턴한다.
  • 컴파일러가 optimization 설정이 높으면 게산된 상수로 대치될 것으로 예측된다.
  • 0) x가 0인 경우 1로 설정된 비트가 없으므로 0을 리턴한다.
  • 그 이후 이분 법으로 최장 5번의 조건을 진행한다.
    • 1) x가 0xffff_0000가 0인 경우, 즉 msb 16비트를 조사하여 설정된 비트가 없으면 x를 16비트 쉬프트하고 r을 16감소
    • 2) x가 0xff00_0000가 0인 경우, 즉 msb 8비트를 조사하여 설정된 비트가 없으면 x를 8비트 쉬프트하고 r을 8감소
    • 3) x가 0xf000_0000가 0인 경우, 즉 msb 4비트를 조사하여 설정된 비트가 없으면 x를 4비트 쉬프트하고 r을 4감소
    • 4) x가 0xc000_0000가 0인 경우, 즉 msb 2비트를 조사하여 설정된 비트가 없으면 x를 2비트 쉬프트하고 r을 2감소
    • 5) x가 0x8000_0000가 0인 경우, 즉 msb 1비트를 조사하여 설정된 비트가 없으면 x를 1비트 쉬프트하고 r을 1감소
    • 리턴되는 r 값이 1이 설정된 마지막 장소이다.
  • 예)
    • 0x8000_0000 -> 5번의 조건을 모두 실패하고 32가 리턴된다.
    • 0x0000_8000 -> 처음 1번의 조건을 실패하고 16이 리턴된다. (32-16=16)
    • 0x0000_0001 -> 5번의 조건을 모두 만족하고 1이 리턴된다. (32-16-8-4-2-1=1)

 

__clz()

arch/arm/include/asm/bitops.h

/*
 * On ARMv5 and above those functions can be implemented around the
 * clz instruction for much better code efficiency.  __clz returns
 * the number of leading zeros, zero input will return 32, and
 * 0x80000000 will return 0.
 */
static inline unsigned int __clz(unsigned int x)
{
        unsigned int ret;

        asm("clz\t%0, %1" : "=r" (ret) : "r" (x));

        return ret;
}
  • msb 부터 시작하여 비트가 0으로 시작하는 갯 수를 리턴한다.
  • 이 명령은 ARMv5 아키텍트 이상에서 하나의 전용 명령으로 동작하여 빠르게 수행한다.

bitops-2

ffs()

arch/arm/include/asm/bitops.h

/*
 * ffs() returns zero if the input was zero, otherwise returns the bit
 * position of the first set bit, where the LSB is 1 and MSB is 32.
 */
static inline int ffs(int x)
{
        return fls(x & -x);
}
  • 셋 되어 있는 첫 비트의 위치(1~32)를 리턴한다. x 값이 0 즉, 설정된 비트가 없으면 0을 리턴한다.

bitops-3

 

ffz()

arch/arm/include/asm/bitops.h”

#define ffz(x) __ffs( ~(x) )
  • clear(0) 되어 있는 첫 비트의 위치(0~31)를 리턴한다.  x 값이 0xffff_ffff 즉,  zero bit가 없으면 -1을 리턴한다.

 

__ffs()

arch/arm/include/asm/bitops.h

/*
 * __ffs() returns the bit position of the first bit set, where the
 * LSB is 0 and MSB is 31.  Zero input is undefined.
 */
static inline unsigned long __ffs(unsigned long x)
{
        return ffs(x) - 1;
}
  • 셋 되어 있는 첫 비트의 위치(0~31)를 리턴한다. x 값이 0 즉, 설정된 비트가 없으면 -1을 리턴한다.

 

fls_long()

include/linux/bitops.h

static inline unsigned fls_long(unsigned long l) 
{
        if (sizeof(l) == 4)
                return fls(l);
        return fls64(l);
}

long형 타입 인수 l에 대해 lsb 부터 msb 로의 비트 검색을 하여 마지막 set bit를 알아오고 못 찾은 경우 0을 리턴한다. (based=1)

 

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.