이 포스팅에서는 2의 제곱수로 수로 어떤 수를 나누었을때 빠르게 나머지를 구하는 방법을 알아보겠습니다.
6502 어셈블리어로 코딩을 하면서 비교문, 반복문, 연산의 최적화 고민을 많이하게 되었습니다.
특히 6502 cpu에서는 나누기를 위한 명령어 파이프라인이 없기 때문에 나누기를 하려면 빼기를 여러번 반복해서 몫과 나머지를 구해야했습니다(곱하기도 마찬가지).
6502 cpu에서 나누기하는 코드를 확인해보면,
lda 11 ; [1] a 레지스터에 11을 로드
ldy 0 ; [2] y 레지스터(인덱스 레지스터)에 0을 로드
subtract_loop:
cmp 4 ; [3] 2와 a레지스터를 비교
bcc exit ; [4] cmp결과 캐리비트가 꺼져있으면(a < 2 일때) 종료
sbc 4 ; [5] 캐리비트가 켜져있으면 a레지스터에서 2를 뺌
iny ; [6] y 레지스터를 1증가
bne subtract_loop ; [7] 반복
exit:
brc ; [8] 프로그램 종료이 코드를 실행하면 y레지스터에 몫, a레지스터에 나머지가 남아있습니다.
6502 cpu의 경우 데이터크기는 8비트, 주소는 16비트로 이루어지고, cpu성능 또한 일반적인 cpu보다 성능이 좋지않습니다.
이런 제한된 환경에서 컴퓨터 자원을 최대한 적게 활용할 필요가 있습니다.
위의 나머지 연산의 경우는 나누는 대상이 커질수록 성능에 큰 영향을 미칩니다. 하지만 2의 제곱수로 어떤 수를 나누게 되면 논리연산 만으로 나머지를 쉽게 구할수 있습니다.
나머지의 성질
예를들어 203102301230120 이라는 수를 12로 나누면 나머지는 0~11이 나올것입니다.
마찬가지로 숫자 11을 4로 나누면 나머지는 반드시 0~3이 나오게됩니다.
11은 2진수로 0000 1011 입니다.
숫자 4에 해당하는 비트는 언제나 세번째 비트입니다.
즉, 위에서 봤던 반복문을 돌면서 4를 지속적으로 빼 나가도 첫번째 비트(1)와 두번째 비트(1)는 절대로 건들수 없음을 의미합니다.
그래서 여기서 나머지는 0000 0011 에 해당하는 3입니다.
이제 비트패턴 0000 1011 에서 0000 0011 부분만 비트마스크 통해서 빼내면 됩니다.
lda 11
and %0000 0011이렇게하면 a레지스터에 3이 담겨져 있습니다.
이 방법은 2진수 비트패턴에서 하나의 비트가 2단위로 구분되기 때문에 2의 제곱수로 나눌때만 가능하고, 2의 제곱수가 아닌경우에는 반복문을 돌면서 뺄셈을 할수밖에 없습니다..
현대 6502와 같이 간단한 초소형(?) 어셈블리어에서는 이런식으로 나누기 반복문을 직접 구현해주어야 하지만, 현대의 어셈블리어(x86, arm64 등) 에서는 명령어에서 나누기(혹은 곱하기) 파이프라인을 만들어놔서 명령어 하나로 나누기 곱하기 연산이 가능해집니다. 그래서 적어도 명령어를 fetch 하는 시간은 줄어든다는것을 알수 있습니다.
하지만 여전히 cpu 내부에서는 반복문을 돌면서 빼기를 할것으로 예상되기 때문에 2의 제곱으로 나눌 경우에는 비트마스크와 and연산을 통해서 나머지를 구하는게 더 빠를 것 같다고 생각합니다
