[Solidity] 비트 수 세기 SWAR (SIMD Within A Register) 알고리즘 || Algorithm | BitMask

안녕하세요. 스마트 컨트렉트 개발자 개발이 체질의 최원혁입니다.

이번 게시글에서 Solidity에서 활용할 수 있는 SWAR (SIMD Within A Register) 알고리즘에 대해 알아보겠습니다.

SWAR 알고리즘 이란?

SWAR 알고리즘은 2진수 데이터에서 활성화된 1의 개수를 세는 것입니다. 비트 연산은 프로그래밍에서 시간 복잡도를 상당히 낮춰주기 때문에, 매우 우수한 성능을 발휘할 수 있습니다. SWAR 알고리즘은 비트 연산을 활용한 알고리즘입니다. Solidity에 적용할 경우, Smart Contract의 특성 상 발생하는 가스비(수수료)에 최적화된 로직을 만들 수 있습니다.

SWAR 알고리즘은 다양한 종류가 있습니다. 그 중에서도 0x3F 모듈러스 연산을 활용한 방법에 대해 알아보겠습니다. 이 방법은 반복문(for)을 사용하지 않고도 1의 개수를 알아낼 수 있기 때문입니다. Smart Contract에서 반복문은 높은 가스비를 측정하기 때문에, 저는 모듈러스 연산을 활용한 SWAR 알고리즘을 Smart Contract 개발할 때 자주 사용합니다.

📌 전체코드는 게시글 하단에 Github 링크를 통해 확인할 수 있습니다.

변수 설정

uint constant public POPCNT_MULT = 0x0000000000002000000000100000000008000000000400000000020000000001;
uint constant public POPCNT_MASK = 0x0001041041041041041041041041041041041041041041041041041041041041;
uint constant public POPCNT_MODULO = 0x3F;

SWAR 알고리즘을 활용하기 위해 2가지 상수(POPCNT_MULT,POPCNT_MASK)와 모듈러스 연산에 필요한 변수 1개(POPCNT_MODULO)가 필요합니다. 각 변수가 알고리즘에 적용되는 부분은 전체 코드를 보면서 설명해보겠습니다.

Code Review

C언어 또는 다양한 언어에서 2진수의 활성화된 비트의 개수를 알려주는 API나 함수의 이름은 주로 POPCOUNT이기에, 저도 함수명을 똑같이 지어봤습니다. 파라미터 uint num을 넣어 num의 2진수에서 1이 몇개인지 확인을 해보겠습니다.

Example : num = 5

10진수 5 => 2진수 0101
POPCOUNT(5) = 2;

실제로 함수를 실행 시켜보면 숫자 2가 잘 나옵니다. 10진수와 2진수의 관계를 잘 모르신다면 아래 링크를 통해 먼저 학습을 해주세요.

[Solidity] 비트마스크(BitMask) 연산 || Solidity 0.8 | Operators ||

안녕하세요. 스마트 컨트렉트 개발자 개발이 체질의 최원혁입니다. 이번 게시글에서 Solidity에서 활용할 수 있는 비트마스크(BitMask) 연산에 대해 알아보겠습니다. 비트마스크(BitMask) 란? 10진수를

borntodevelop.tistory.com

이제 단계 별로 차근차근 알아보겠습니다

STAP 1 .(num * POPCNT_MULT)

16진수 :

POPCNT_MULT = 0x0000000000002000000000100000000008000000000400000000020000000001

2진수 :

POPCNT_MULT =

000000000000

00000000000000000000000000000000000000001

16진수로 되어있는 POPCNT_MULT를 2진수로 변환하면 40개의 Padding(0으로 가득 채우는 행동)과 1이 6개 이어져 있습니다. 각각은 10진수 숫자 1이 41비트 메모리에 저장되있음을 의미합니다.

그리고 POPCNT_MULT을 uint로 정의했기 때문에 64바이트를 맞추기 위해 12개의 0을 추가로 넣어 위와 같은 형태가 됩니다.

5(num) * POPCNT_MULT =

000000000000

00000000000000000000000000000000000000101

POPCNT_MULT에 우리가 예시로 넣었던 숫자 5를 넣으면, 각 위치의 비트가 00000000000000000000000000000000000000101 = 5가 됩니다.

이는 POPCNT_MULT의 41비트 단위의 숫자가 모두 1이기 때문에 1 x 5를 하여 5가 되고, 그 결과를 2진수로 표현한 것입니다. 이후 2진수의 곱하기 연산에 따라 6개 모두가 같은 결과를 갖게 됩니다. 2진수의 4칙연산에 대한 내용은 아래를 참고해주세요.

[IT Series] 2진수 4칙연산(더하기,빼기,곱하기,나누기) 원리 || Bit | Binary Arithmetix ||

안녕하세요. 스마트컨트렉트 개발자 개발이 체질의 최원혁입니다. 이번 게시글에서 소개해드릴 내용은 2진수의 4칙연산입니다. 2진수(binary digit)는 비트를 뜻하는 말로 컴퓨터에서 사용되는 데

borntodevelop.tistory.com

STAP 2. ((num * POPCNT_MULT) & POPCNT_MASK)

16진수 :

POPCNT_MASK = 0x0001041041041041041041041041041041041041041041041041041041041041;

2진수 :

POPCNT_MASK =

00000000000000001(0x0001)

000001000001(0x041)

16진수로 된 POPCNT_MASK를 2진수로 변환하면 위와 같은 형태가 됩니다. 반복되는 0x041은 2진수로 1000001이며, 5개를 Padding을 주어 000001000001가 20개 반복됩니다. 마지막에 0x0001을 주어 [0 5개 + 1]의 규칙성을 만들어 냈습니다. 그리고 POPCNT_MASK을 uint로 정의했기 때문에 64바이트를 맞추기 위해 나머지에 0을 추가로 넣어 위와 같은 형태가 됩니다.

(5(num) * POPCNT_MULT) & POPCNT_MASK =

1000000000000000000000000000000000000000000000000000000000000000000000000000000000001

비트연산자 AND(&)를 사용하여 겹치는 부분을 찾으면 위와 같은 결과가 나타납니다. 이때 1의 개수를 세면 2되고, 5의 2진수는 0101이니, 1의 개수는 2가 됩니다. 이런 결과의 이유는 각각 차지하는 비트의 개수의 차이 때문입니다.

5(num) * POPCNT_MULT) = 00000000000000000000000000000000000000000

POPCNT_MASK = 000001000001000001000001000001000001000001

5(num) * POPCNT_MULT)의 첫번째 줄과 POPCNT_MASK을 비교해 보면 반복되는 0x041로 인해 6개 마다 비교하여 활성화된 1을 찾습니다. 41개로 구성되어 있는 POPCNT_MULT는 6개씩 비교하게 되면 위와 같이 한줄당 7개를 비교할 수 있습니다.

00000000000000000000000000000000000000000

이 과정을 반복하면 POPCNT_MASK의 264(41 * 6)개의 비트를 전부 확인 할 수 있습니다. 개수의 차이를 AND(&)연산을 통해 1을 찾는것이 SWAR 알고리즘의 원리입니다.

STAP 3. ((num * POPCNT_MULT) & POPCNT_MASK) % POPCNT_MODULO(0x3F)

(5(num) * POPCNT_MULT) & POPCNT_MASK =

1000000000000000000000000000000000000000000000000000000000000000000000000000000000001

우리는 위와 같은 2진수형태의 결과에 도달했습니다. 이제 1의 개수를 알려주는 형태로 변환하면 끝납니다. 이를 위해 모듈러스 (0x3F)에 나머지 연산을 활용하여 1의 개수를 10진수로 구해보겠습니다.

우리는 POPCNT_MASK의 형태를 통해 6개의 비트마다 1을 찾는걸 배웠습니다.

Exampe :

00000000000000000000000000000000001000000= > 2^6 = 64 = 64

만약 6개마다 1이 활성화가된걸 10진수로 표현하면 2^6(64)마다 활성화가 되는걸 뜻합니다.

이때 64 % 63(0x3F)을 하게되면 나머지가 1이 나오면서 활성화된 개수를 알려줍니다. 2^6에 64를 나누면 나머지 없이 딱 떨어지기에, 63(0x3F)을 활용하여 나머지를 구하는것이 모듈러스 연산의 특징입니다.

((5(num) * POPCNT_MULT) & POPCNT_MASK ) % 0x3F

1000000000000000000000000000000000000000000000000000000000000000000000000000000000001

= ( 2^42 + 2^0 ) % 63 = (1 % 63) + (2^42 % 63 ) = 2

이를 num = 5에 적용하면 위와 같은 계산이 되며, 최종적으로 숫자 5에 활성화된 1의 비트 개수를 구할 수 있습니다.

지금까지 Solidity에서 활용할 수 있는 SWAR (SIMD Within A Register) 알고리즘에 대해 알아봤습니다.

감사합니다.

📌 Github Solidity Code :

GitHub - imelon2/My-Solidity-Playground

Contribute to imelon2/My-Solidity-Playground development by creating an account on GitHub.

github.com

🔎 Reference :

https://www.playingwithpointers.com/blog/swar.html

https://stackoverflow.com/questions/75586792/question-about-bit-population-count-algorithm/75587612#75587612

https://namocom.tistory.com/377

저작자표시 비영리 변경금지 (새창열림)

'Block Chain > Solidity' 카테고리의 다른 글

[Solidity] 배열 오름차순 정렬 삽입 정렬(Insertion Sort) 알고리즘 (0)	2025.01.29
[Solidity] 스마트컨트렉트 함수 호출 Call() \|\| Solidity 0.8 \| ethers.js \| payload \|\| (0)	2023.05.07
[Solidity] Payable, Fallback and Receive \|\| Solidity 0.8 \|\| (0)	2023.02.16
[Solidity] 머클트리 Merkle Tree Root & Proof \|\| Solidity 0.8 \| Openzeppelin \|\| (2)	2023.01.29
[Solidity] 지갑주소(EOA)와 컨트렉트 주소(CA) 구분하기 \|\| Solidity 0.8 \| isContract \|\| (0)	2023.01.13

개발이 체질인 나그네

[Solidity] 비트 수 세기 SWAR (SIMD Within A Register) 알고리즘 || Algorithm | BitMask | Binary ||

SWAR 알고리즘 이란?

변수 설정

Code Review

📌 Github Solidity Code :

'Block Chain > Solidity' 카테고리의 다른 글

댓글

티스토리툴바

[Solidity] 비트 수 세기 SWAR (SIMD Within A Register) 알고리즘 || Algorithm | BitMask | Binary ||

SWAR 알고리즘 이란?

변수 설정

Code Review

📌 Github Solidity Code :

'Block Chain > Solidity' 카테고리의 다른 글

관련글

댓글

티스토리툴바