Bit Operations

Bit 관련 매크로

BITS_PER_LONG

include/asm-generic/bitsperlong.h”

1#ifdef CONFIG_64BIT
2#define BITS_PER_LONG 64
3#else
4#define BITS_PER_LONG 32
5#endif /* CONFIG_64BIT */

long 타입에서 사용될 수 있는 비트 수

BITS_PER_LONG_LONG

include/asm-generic/bitsperlong.h”

1#ifndef BITS_PER_LONG_LONG
2#define BITS_PER_LONG_LONG 64
3#endif

long long 타입에서 사용될 수 있는 비트 수

BIT_ULL()

include/linux/bits.h

`1`	`#define BIT_ULL(nr) (ULL(1) << (nr))`

nr 비트에 해당하는 unsigned long long 값을 반환한다.

nr=0~63 비트까지 지정할 수 있다.
예)
- nr=0 -> 1
- nr=1 -> 2
- ..
- nr=63 -> 0x8000_0000_0000_0000

BIT_MASK()

include/linux/bits.h

`1`	`#define BIT_MASK(nr) (UL(1) << ((nr) % BITS_PER_LONG))`

unsigned long 값(또는 배열)에서 nr 비트에 해당하는 비트를 추출할 목적의 비트 마스크를 만든다.

nr=0~
예)
- nr=0 -> 1
- nr=1 -> 2
- ..
- nr=63 -> 0x8000_0000 (32 bit 기준), 0x8000_0000_0000_0000 (64 bit 기준)
- nr=64 -> 1

BIT_WORD()

include/linux/bits.h

`1`	`#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)`

@nr 비트가 속한 unsigned long 비트맵 배열의 인덱스 번호 (0부터 시작)

nr=0~
예)
- nr=0 -> 0
- nr=31 -> 0
- nr=32 -> 1 (32bit 기준), 0 (64bit 기준)
- nr=63 -> 1 (32bit 기준), 0 (64bit 기준)
- nr=64 -> 2 (32bit 기준), 1 (64bit 기준)
- nr=95 -> 2 (32bit 기준), 1 (64bit 기준)
- nr=96 -> 3 (32bit 기준), 1 (64bit 기준)
- nr=127 -> 3 (32bit 기준), 1 (64bit 기준)
- nr=128 -> 4 (32bit 기준), 2 (64bit 기준)
- nr=159 -> 4 (32bit 기준), 2 (64bit 기준)
- nr=160 -> 5 (32bit 기준), 2 (64bit 기준)
- nr=191 -> 5 (32bit 기준), 2 (64bit 기준)

BIT_ULL_MASK()

include/linux/bits.h

`1`	`#define BIT_ULL_MASK(nr) (ULL(1) << ((nr) % BITS_PER_LONG_LONG))`

unsigned long long 값(또는 배열)에서 nr 비트에 해당하는 비트를 추출할 목적의 비트 마스크를 만든다.

nr=0~
예)
- nr=0 -> 1
- nr=1 -> 2
- ..
- nr=63 -> 0x8000_0000_0000_0000 (32 bit 및 64 bit 동일)
- nr=64 -> 1

BIT_ULL_WORD()

include/linux/bits.h

`1`	`#define BIT_ULL_WORD(nr) ((nr) / BITS_PER_LONG_LONG)`

@nr 비트가 속한 unsigned long long 비트맵 배열에 대한 인덱스 번호 (0부터 시작)

nr=0~
예)
- nr=0 -> 0
- nr=63 -> 0
- nr=64 -> 1
- nr=127 -> 1
- nr=128 -> 2
- nr=191 -> 2

BITS_PER_BYTE

include/linux/bits.h

`1`	`#define BITS_PER_BYTE 8`

byte 타입에서 사용될 수 있는 비트 수

Bit Operations

API들

Search

fls()
__fls()
ffs()
__ffs()
ffz()
fls_long()

Iteration

for_each_set_bit(bit, addr, size)
- size 비트 한도의 addr 값에서 셋(1) 비트 수 만큼 루프를 돈다.
- 예) addr=0x3f0, size=8
  - 4번의 루프(bit=4, 5, 6, 7)
for_each_set_bit_from(bit, addr, size)
- for_each_set_bit()와 유사하지만 시작 비트를 지정한 곳에서 출발한다.
- 예) addr=0x3f0, size=8, bit=5
  - 3번의 루프(bit=5, 6, 7)
for_each_clear_bit(bit, addr, size)
- size 비트 한도의 addr 값에서 클리어(0) 비트 수 만큼 루프를 돈다.
- 예) addr=0xfff0, size=8
  - 4번의 루프(bit=0, 1, 2, 3)
for_each_clear_bit_from(bit, addr, size)
- for_each_set_bit()와 유사하지만 시작 비트를 지정한 곳에서 출발한다.
- 예) addr=0x3f0, size=8, bit=1
  - 3번의 루프(bit=1, 2, 3)

rotate

rol64()
ror64()
rol32()
ror32()
rol16()
ror16()
rol8()
ror8()

atomic

set_bit()
test_bit()
clear_bit()
change_bit()
test_and_set_bit()
test_and_clear_bit()
test_and_change_bit()
find_first_zero_bit()
find_next_zero_bit()
find_last_zero_bit()
find_first_bit()
find_next_bit()
find_last_bit()

lock

test_and_set_bit_lock()
clear_bit_unlock()
- __clear_bit_unlock()
clear_bit_unlock_is_negative_byte()

le(little endian)

find_next_zero_bit_le()
find_next_bit_le()
find_first_zero_bit_le()
test_bit_le()
set_bit_le()
- __set_bit_le()
clear_bit_le()
- __clear_bit_le()
test_and_set_bit_le()
- __test_and_set_bit_le()
test_and_clear_bit_le()
- __test_and_clear_bit_le()

etc

get_bitmask_order()
hweight_long()
sign_extend32()
sign_extend64()
get_count_order()
get_count_order_long()
__ffs64()
assign_bit()
- __assign_bit()
set_mask_bits()
bit_clear_unless()

bitops 아키텍처별 헤더 파일

Bit operation은 기본 구현 헤더, Generic 라이브러리, asm-generic 헤더 및 아키텍처별 헤더에 구현되어 있다.

기본 구현 헤더
- include/linux/bitops.h
- include/asm-generic/bitops.h
- include/asm-generic/bitops/*.h
Generic 라이브러리
- lib/find_bit.c
- lib/hweight.c
- …
아키텍처별 헤더
- arch/arm/include/asm/bitops.h
- arch/arm64/include/asm/bitops.h

비트 검색 operations

fls()

include/asm-generic/bitops/builtin-fls.h

1/**
2 * fls - find last (most-significant) bit set
3 * @x: the word to search
4 *
5 * This is defined the same way as ffs.
6 * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
7 */

1static __always_inline int fls(unsigned int x)
2{
3        return x ? sizeof(x) * 8 - __builtin_clz(x) : 0;
4}

unsigned int 타입 @x 값에서 셋 되어 있는 마지막(가장 좌측) 비트의 위치(1~32)를 리턴한다. 설정된 비트가 없으면 0을 리턴한다.

예)
- 0 -> 0
- 0x0000_0001 -> 1
- 0x0000_0011 -> 2
- 0x8000_0000 -> 32
- 0x8800_0000 -> 32

__fls()

include/asm-generic/bitops/builtin-_ffs.h

1/**
2 * __fls - find last (most-significant) set bit in a long word
3 * @word: the word to search
4 *
5 * Undefined if no set bit exists, so code should check against 0 first.
6 */

1static __always_inline unsigned long __fls(unsigned long word)
2{
3        return (sizeof(word) * 8) - 1 - __builtin_clzl(word);
4}

unsigned long 타입 @word에서 가장 마지막(가장 좌측) bit가 1인 bit 번호를 리턴한다. (based 0)

예)
- 0 -> 오류 (0 값이 입력으로 전달되면 안된다)
- 0x0000_0001 -> 0
- 0x0000_0011 -> 1
- 0x8000_0000 -> 31
- 0x8800_0000 -> 31
- 0x8800_0000_0000_0000 -> 63 (64bits only)

ffs()

include/asm-generic/bitops/builtin-ffs.h

1/**
2 * ffs - find first bit set
3 * @x: the word to search
4 *
5 * This is defined the same way as
6 * the libc and compiler builtin ffs routines, therefore
7 * differs in spirit from the above ffz (man ffs).
8 */

1static __always_inline int ffs(int x)
2{
3        return __builtin_ffs(x);
4}

int 타입 @x에서 셋 되어 있는 첫(가장 우측) 비트의 위치(1~32)를 리턴한다. x 값이 0 즉, 설정된 비트가 없으면 0을 리턴한다.

예)
- 0 -> 0
- 1 -> 1
- 0x0000_0011 -> 1
- 0x8000_0000 -> 32
- 0x8800_0000 -> 31

__ffs()

include/asm-generic/bitops/builtin-_ffs.h

1/**
2 * __ffs - find first bit in word.
3 * @word: The word to search
4 *
5 * Undefined if no bit exists, so code should check against 0 first.
6 */

1static __always_inline unsigned long __ffs(unsigned long word)
2{
3        return __builtin_ctzl(word);
4}

unsigned long 타입 @word에서 셋 되어 있는 첫(가장 우측) 비트의 위치(0~31)를 리턴한다. x 값이 0 즉, 설정된 비트가 없으면 -1을 리턴한다.

예)
- 0 -> -1
- 0x0000_0001 -> 0
- 0x0000_0011 -> 1
- 0x8000_0000 -> 31
- 0x8800_0000 -> 30
- 0x8800_0000_0000_0000 -> 62 (64bits only)

ffz()

include/asm-generic/bitops/ffz.h

1/*
2 * ffz - find first zero in word.
3 * @word: The word to search
4 *
5 * Undefined if no zero exists, so code should check against ~0UL first.
6 */

`1`	`#define ffz(x) __ffs(~(x))`

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

예)
- 0 -> 0
- 0x0000_0001 -> 1
- 0x0000_000f -> 4
- 0x7fff_ffff -> 31
- 0xffff_ffff -> -1

fls_long()

include/linux/bitops.h

1static inline unsigned fls_long(unsigned long l) 
2{
3        if (sizeof(l) == 4)
4                return fls(l);
5        return fls64(l);
6}

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

예)
- 0 -> 0
- 1 -> 1
- 0x8000_0000 -> 32
- 0x8000_0000_0000_0000 -> 64 (64bits only)

Atomic 비트 조작 operations

다음 API들을 알아본다.

set_bit()
clear_bit()
change_bit()
test_and_set_bit()
test_and_clear_bit()
test_and_change_bit()