10장 - 비트 단위 연산 - AND/OR/XOR/NOT
이 연산을 불리언 연산 (boolean operation)이라고도 하고 논리 연산 (logical operation)이라고도 한다. 작동 방식이 비트 단위로 이루어져 비트단위
연산 (bitwise, bit-by-bit operation)이라고도 한다. 여기서는 비트 단위 (bitwise) 연산이라고 하기로하겠다. AND/OR/XOR은 두 비트를 취해서 그
결과를 갱신한다. NOT은 한 비트를 취해 그 결과를 갱신한다. 즉, A op B 또는 NOT A/NOT B 형태가 될 수 있다.
AND: 0 op 0 = 0, 0 op 1 = 0, 1 op 0 = 0, 1 op 1 = 1
OR: 0 op 0 = 0, 0 op 1 = 1, 1 op 0 = 1, 1 op 1 = 1
XOR: 0 op 0 = 0, 0 op 1 = 1, 1 op 0 = 1, 1 op 0 = 0
NOT: not 0 = 1, not 1 = 0
수학적으로 해석하면, and는 교집합, or은 합집합, xor은 합집합 - 교집합, not은 여집합 쯤에 해당한다.
<그림>
하지만 창피하게도 이땅은 수학 문맹국이므로 이런 수학적 논리 따위는 통하지 않는다. 논리 회로를 공부한 사람이라면 여러 불 연산중 단지 4개뿐임을 눈치챌 것이다. 이유는 이들 4개만 있어도 불 연산을 모두 흉내낼수 있어 (예로, NAND = AND -> NOT, NOR = OR -> NOT), 원자적인 불 대수 역할을 하기 때문이라고 할 수 있다.
똑똑한 사람들은 이를 외우지만, 더 중요한 것은 이를 이해하는 것이다. 이 진리표는 언제라도 필요하면 찾아볼 수 있지 않은가 ? 비트 단위 명령을
어셈블리 코딩시 주의해야 할 한가지를 꼽자면, "결과를 갱신한다"는 것이다. 즉, NOT 을 제외하고 두개의 입력 (input) 값으로 하나의 출력 (output)
값을 산출한다. 지금도 외워쓰는 수준에 불과하지만, 이것을 이해 못해 처음 어셈블리를 배울 때 무진장 고생했던 기억이 있다. 또한, 추가로 중요한
것은 같은 연산자 끼리도 연산이 가능한 것이다.
mov ax, 1
and ax, 0 ; ax = 1 and 0의 결과를 반영한다.
mov bx, 1
or bx, bx ; bx = 1 or 1의 결과를 반영한다.
mov cx, 1
xor cx, myflag ; cx = 1 xor myflag의 결과를 반영한다.
mov dx, 0FFh ; dx = 1111 1111 1111 1111
not dx ; dx = 0000 0000 0000 0000
여기서 and/or/xor 을 잘 살펴보면, 모두 op A, B의 형태를 취하며, A는 A op B가 되고 B는 그대로 유지된다 (소스 불변의 법칙). 반면, or의 경우,
뒤의 bx는 원래 변하지 않기로 했지만, or을 해줌과 동시에 갱신된다. 즉 같은 연산자일 경우 소스 불변의 법칙은 깨진다. not의 경우는 어려울게
없지만 문제는 1비트만 not 하는 경우가 별로 없다보니 어렵기는 마찬가지다. 플랙표는 다음과 같다:
똑똑한 사람은 이 플랙표를 외우지만, 메모리가 약간 부족한 사람은 이를 다음처럼 이해한다:
비트 연산 명령은 비트 단위 (bit-by-bit)로 연산하므로 자리 올림에 관여하는 OF/CF를 건드려서는 안된다. 비트 연산을 할 때 최소 8비트 이상의
데이터 (가장 작은 레지스터가 8비트 레지스터)를 가지고 연산하므로 1니블 캐리를 의미하는 AF은 무시해도 된다. 비트 연산을 하다보면 MSb가
토글될수 있으며, 모든 비트가 0이 될 수 있고, 최하위 8비트 (MSB)가 토글될 수 있다.
이 플랙표는 jo/jc 명령을 쓰다가 버그에 이를 수 있음을 경고한다고 할 수 있다.
or ax, ax
jc Location ; 이렇게 하면 뒷일은 책임 못진다.
또한, 다음처럼 무책임한 분기처리를 하지도 않을 것이다.
not ax
jz Location ; 무슨 근거로 분기를 ?
하지만 우리는 다음처럼 cmp 명령 없이도 비트 단위 명령으로 분기 조건을 테스트할 수 있다는 것을 알 수 있다.
and ax, 1 or ax, ax xor bx, bx
jnz L1 jz L1 js L1
논리 연산 명령으로 분기 처리할 때 xor은 강제 분기 (unconditional jump) 역할을 할 수 있으므로 거의 사용하지 않는다. 테스트되는 플랙중 0 이냐
1 이냐를 결정하는 ZF 플랙이 가장 중요하다고 할 수 있다.
and, or, xor 3 명령은 "op r/m8/16/32, r/m/i8/16/32" 형태로 같다. 특이한 점은 레지스터 없이 "and mem, imm" 형태는 허용되어도, 메모리 간의
연산인 "and mem, mem" 형태는 없다. MOV 명령과 마찬가지로 메모리 간의 직접 연산은 대부분의 인텔 명령에서 통하지 않는다. not은 "not r/m8/16/32"의 단항 (unary)
명령이며, 플랙을 완전히 무시하고, "not mem"은 허용되어도, "not imm" 형태는 없다.
and 명령은 "and d, s" 일반적인 형태로 s 연산자에서 소스를 취해 d 연산자에 bitwise AND 연산을 수행하여 결과를 d에 반영한다. 두 연산자의
같은 자리에 있는 각 비트가 1로 일치하면 d에 1로 세팅하고, 그렇지 않으면 0으로 세팅한다. (0으로 세팅 = 클리어) 연산 수행후 OF/CF가 클리어
(0)되고, SF/ZF/PF는 결과에 따라 세팅되고 AF는 정의되지 않는다.
or 명령은 and와 포맷과 플랙 세팅이 같으며 bitwise OR 연산을 수행하는 점이 다르다. 두 연산자의 같은 자리에 있는 각 비트가 0으로 일치하면
d에 0으로 세팅하고, 그렇지 않으면 1로 세팅한다. xor 명령도 포맷 플랙 세팅은 같지만, bitwise XOR 연산을 수행하며, 같은 자리에 있는 각 비트가
서로 다르면 1로 세팅하고, 그렇지 않으면 0으로 세팅한다. not은 아무런 플랙에 영향주지 않으며, "not d" 포맷으로 하나의 연산자인 d를 취해 모든
비트를 뒤집어 (이를 1의 보수라 한다) 그 결과를 d에 되돌린다.
그런 이유로 "and X, 1" 형태로 마스킹에 주로 사용되며, "or X, 0/1" 형태로 비트 세팅에 사용되며, "xor X, X" 형태로 비트 소거에 자주 사용된다.
고급 언어인 C와 표현 방식을 비교해보면 이렇다. (앞으로 어셈블리(어) 등의 약어를 "ASM, 어셈" 등으로 칭하기로 한다)
ASM C
-------------------
AND X, Y X & Y
OR X, Y X | Y
XOR X, Y X ^ Y
NOT X ~ X
고급 언어는 직접적으로 CPU 명령을 쓸 수 없으니 특별한 기호라도 써서 표현해야 하니 이 얼마나 불편한가 ? 만약 비트 연산을 중복해서 한다면
C 코드는 외계인의 언어처럼 변해버린다. C 프로그래머에게 어셈블러는 "가난한 사람들의 컴파일러" 쯤에 해당하지만, ASM 프로그래머에게 C는
"게으른 사람들을 위한 어셈블러" 쯤에 해당한다. 물론 한물간 논쟁거리가 되버렸지만...
여기까지가 교과서적인 내용이고 잘 읽었다면, 다음 문제는 쉽게 풀어야 정상이다.
xor ax, ax ; 0 xor 0 = 0, 1 xor 1 = 0
xor bx, bx
mov ax, 01010000b
mov bx, 01110000b
xor ax, bx ; ax, bx = ?
답을 제시하고 싶은 맘은 없었으나 그래도 간략히 설명하면 이렇다. 같은 연산자를 "xor X, X"하면, X와 X의 합집합 - X와 X의 교집합 = 0 이 되듯이,
"xor ax, ax"는 0으로 ax 레지스터를 소거한다. "xor bx, bx"도 마찬가지다. mov 명령은 고급 언어에서 대입 (assignment) 정도에 해당한다. 16비트
레지스터 ax, bx에 8비트 값을 주면 하위 8비트만 채우고 상위 8비트는 손대지 않는다. 이를 xor하여 ax에만 저장하므로,
ax = 0000 0000 0101 0000
bx = 0000 0000 0111 0000
---------------------------
ax = 0000 0000 0010 0000
이 되고, bx는 소스 연산자로 사용되므로 그대로 값을 유지한다.
쉽게 풀리지 않았다면, 학교에서 "연산"만 배워서 일 것이다. "연산후 취하자"는 개념이 있을 줄을 그때는 몰랐던가, 아니면 비트가 많아질 것을
고려하지 않았기 때문일 것이다. 단순히 8비트 논리 연산에서 틀리면 32비트/64비트 프로그래밍을 어찌하겠는가 ? 어셈블리 프로그래밍에서 논리
연산은 가장 중요하다고 할 수 있다. 그만큼 숙달되어야 한다는 뜻이다. 앞으로 중간 중간 물음표를 던져줄테니 직접 풀어서 마침표로 리턴해주기
바란다. 내가 풀이한 것은 나만의 우물속에서 해석한 세상일 뿐이다. 나라는 인간이 갇혀사는 우물 속에 그대마저 가두어두고 싶지는 않다. 나를
밟고 뛰어 세상으로 나가라. 그리고 세상 밖이 어떻게 생겼는지 얘기라도 해주라.
xor은 희안하게 작동하면서도 쓸모가 굉장히 많으며, 이전에도 특정 레지스터 두개를 스와핑할 때 사용해봤다.
ASM C
----------------------------
xor x, y X = X ^ Y
xor y, x Y = Y ^ X
xor x, y X = X ^ Y
이는 말로 설명하기 힘드니 위의 밴 다이어그램을 떠올려서라도 이해하라. 이 코드는 temp라는 제3자를 사용하지 않고, 둘을 직접 스와핑하는 매직
코드 정도에 해당한다고 외우자.
불 대수 (boolean algebra) 연산에서 어떤 비트 x에 0을 더하면 x가 되고, 어떤 비트 y에 1을 더하면 1이된다. 이러한 비트 단위의 덧셈을 or로
표현한다. 즉,
x + 0 = x, y + 1 = 1
0 + x = x, 1 + y = 1
라는 수학적 공식 (axiom)이 성립한다. 예로,
or x, 0 ; x = 0
or x, 1 ; x = 1
하지만 이 또한 수학적인 정의로만 남는다. 돼지털 세상에서는 재정의해야 한다. 예로,
xor ax, ax
xor bx, bx
xor cx, cx ; ax = bx = cx = 0
mov al, 0Fh ; al = 0000 1111
mov bl, 0 ; bl = 0000 0000
mov cl, 1 ; cl = 0000 0001
or al, 0 ; al = 0000 1111
or al, 1 ; al = 0000 1111
or al, 2 ; al = 0000 1111
or al, 0FFh ; al = 1111 1111
or bl, 0 ; bl = 0000 0000
or bl, 1 ; bl = 0000 0001
or bl, 2 ; bl = 0000 0011
or bl, 0FFh ; bl = 1111 1111
or cl, 0 ; cl = 0000 0001
or cl, 1 ; cl = 0000 0001
or cl, 2 ; cl = 0000 0011
or cl, 0FFh ; cl = 1111 1111
특정한 패턴이 감지되는가 ? 아마도 감지하지 못했다면, 다소 도배적인 코드여서이거나 아니면 자릿수가 늘어나서 소홀해졌기 때문일 것이다.
or은 특정 비트를 and나 xor처럼 세팅하는 것은 마찬가지이지만, 0을 1로 만드는 것을 주목할 필요가 있다. or을 "논리합"이라고 표현하는데
우리는 "비트합"으로 해석하면 문제가 쉽게 해결될 것이다. 위의 예에서, "1111"로 이미 세팅된 비트는 아무 비트나 더해도 1을 유지하므로,
0, 1, 2로 or해도 무의미한 효과가 된다. 반면, 0Fh는 하위 4비트가 1로 켜진 것에 해당하는데, 여기에 0FFh를 or하면 상위 비트마저 켜서,
0F -> FF 가 된다. 여기에 아무리 큰 수를 더해도 CF/OF를 0으로 만들기 때문에 (즉, 캐리/오버플로 무시) 자리 올림이 일어나지 않는 비트합
이라고 할 수 있다. "or bl, 2"는 현재 01인데 여기에 2 (10)을 or하므로 결국 11 (3)이 된다고 이게 십진수로 2를 더했다고 생각해서는 안된다.
그런 이유로 or은 1로 마스킹할 때 유용하게 사용된다. 예로,
mov al, 0010 0101
or al, 1000 0000
-------------------
1010 0101
이렇게 하면 (물론 공백은 코딩할땐 붙여써야하고, 이진수는 -b를 붙여줘야한다), 최상위 비트 (즉, 사인비트)만 켜주는 역할을 한다. 만약 이
비트가 1로 켜져있는 상태라면 1로 or하므로 그대로 유지된다. 물론 오버플로와는 관련없다. or로 마스킹할 때 몇가지 중요한 매직 넘버는 이렇다:
00h : 비트를 유지 (jz 명령과 혼합하여 무조건 분기하는 역할)
80h : 8비트 최상위 비트만 세팅,
FFh ; 8비트 모든 비트 세팅
0Fh ; 하위 니블만 세팅
7Fh ; 사인비트만 무시하고 세팅 (0111 1111b)
물론 이 매직 넘버를 16비트나 32비트로 사용하려면 뒤에 F나 0을 붙여준다. 예로, or EAX, 80000000h / or AX, 0FFFFh.
반면, 이 코드의 or을 전부 and로 바꾸면 모두 0000 0000이 되며, and를 테스트하기엔 마땅치않다. and는 논리곱이라고 하는데 여기서는 "비트곱"
이라고 하자. 예로,
mov ax, 1234h ; ax = 1001000110100
and ax, 0FFFFh ; ax = 1001000110100 = or ax, 0
보다시피 모든 비트를 켠채로 (FFFF = 1111 1111 1111 1111) and 해주면 그 값을 그대로 유지한다. 이는 0으로 or 해준 것과 같은 효과다.
반면 "and ax, 0" 하면 ax는 모든 비트가 0으로 된다. 이는 xor ax, ax 또는 mov ax, 0과 같은 효과다. and로 마스킹 할때도 위의 or에서와
비슷한 매직 넘버를 사용할 수 있다.
00h : 모든 비트 off
FFh : 모든 비트 on
80h : 사인 비트만 on 나머지는 off
0Fh : 하위 니블만 on 상위 니블은 off
7Fh : 사인 비트만 off 나머지는 on (복수 바이트 일 경우 even-parity를 생성한다)
and는 비트단위의 곱셈에 해당하는 값만 취하기때문에 or보다 마스킹에 더욱 유용하게 사용된다. 물론 마스킹 비트를 확장하려면 or에서 처럼
0 이나 F를 추가해주고 0은 지워지고 F는 남겨진다고 생각하면 된다.
아스키 테이블을 보면, 30h~39h는 아스키 십진 숫자 (0~9)로 할당되어있다. 이를 unpacked BCD (4비트 숫자)로 표현하려면 상위 니블을 꺼주면 된다.
mov al, '0' ; al = 0011 0000 ('0', 30h)
and al, 0Fh ; al = 0000 0000
mov al, '9' ; al = 0011 1001 ('9', 39h)
and al, 0Fh ; al = 0000 1001
꺼진 비트를 다시 켜려면 "or al, 30h"로 해주면 된다. 즉, 4비트 BCD를 십진수로 변환하는 원리이다. 또한, 홀수와 짝수도 and 명령으로 테스트해볼
수 있다.
mov al, 0Fh ; 테스트 값
mov bl, al ; 복사
and bl, 1 ; 끝 비트만 격리시켜 (isolate)
jz L1 ; ZF가 세트되면 짝수이므로 여기에 홀수 처리 루틴을 위치시킨다
jmp next
L1: ; 여기에 짝수 루틴이 위치한다
next: ; 홀수/짝수 루틴 모두 여기에 이른다
물론 암시적 and 명령인 "test al, 1"도 같은 역할이다. 모든 홀수는 끝 비트가 1이므로, 만약 al이 홀수이면, ZF 플랙이 세트되지 않으며, 만약
짝수이면 ZF 플랙이 세트된다.
and와 or은 혼합해서 쓸 수 있고, 쉬프트와도 혼합해서 쓰기도 한다. 돼지털 세상에서 만능 키워드인 "copy & paste" 테크닉을 살짝 수정한 것이
"cut & paste"이고, 이는 비트 세상에도 적용할 수 있다.
mov al, X ; X 중에 불필요한 것이 있다
mov bl, Y ; Y 중에 불필요한 것이 있다
and al, 0F0h ; = 1111 0000 (X - 상위 니블)
and bl, 0Fh ; = 0000 1111 (Y - 하위 니블)
or al, bl ; = 1111 1111 (재구성)
물론 바이트에서 특정 비트를 0000 0101 또는 1010 1111 등으로 짤라내거나 LSb 또는 MSb만 짤라낼 수도 있을 것이다. 예로,
and al, 80h ; = 1000 0000
and bl, 01h ; = 0000 0001
or al, bl ; = 1000 0001
sar al, 1 ; = 1100 0000
xor은 비트를 뒤집는다. 예로,
mov al, 0AAh ; = 1010 1010
xor al, 0FFh ; = 0101 0101
이를 1의 보수라하고 여기에 "add al, 1"하면 2의 보수로 변신한다. not과 같은 역할이다. 하지만 이를 다시 뒤집으면,
mov al, 0AAh ; = 1010 1010
xor al, 0FFh ; = 0101 0101 = not al
xor al, 0FFh ; = 1010 1010 = not al
같은 값으로 xor을 두번 해주면 원래의 값을 되찾는다. 이런 원리로 인해 대부분의 암호화 프로그램에서는 xor을 꼭 쓴다. 암호화 프로그램은 먼저
평문 (plain text)를 특정 키 (위에서는 0FFh가 키이다)를 사용하여 암호화된 문장 (encrypted text)로 만들고, 이를 해독할 때 다시 그 키를 xor로
재사용하여 평문으로 되돌린다. 그래픽 프로그램에서 xor은 특정 컬러 비트를 지웠다가 다시 복원하는 용도로 사용되기도 하며, 특정 포트나 하드웨어
리소스를 임시로 토글할 때도 사용된다.
간혹 우리는 어떤 수를 xor 했을 때 어떤 값인지 알아야 할 때가 있다. 예로, 3 xor 5 = ? 값을 구한다고 하자. 위의 밴 다이어그램을 비트 레벨로
해석하자. 3 = 011, 5 = 101 이므로 둘 간의 비트 합집합은 111이고, 둘 간의 비트 교집합은 001 이므로 111 - 001 = 110 = 6이다.
mov ax, 3
mov bx, 5
mov cx, ax ; 복사
or ax, bx
and cx, bx
sub ax, cx
not은 특정 비트를 뒤집는다. 하지만 뒤집어진 비트가 논리적으로 반대의 뜻을 가진 수라고 가정해서는 안된다. 예로, 0000을 not하면 1111이 된다.
이는 특정 함수의 리턴 값으로 인정할 수 있지만, 0 의 반댓말이 F 라는 뜻은 아니다. 비트 세상에서 0의 논리적인 반댓값은 1이다. 하지만, 1의
반댓값은 0FE이다.
- N = - |NOT (N) + 1|
-3 = NOT (2)
-128 = NOT (127)
80h = NOT (7Fh)
mov al, 0FFh
not al ; al = 0
mov bl, 0FEh
not bl ; bl = 1
그러므로 0 과 1을 번갈아 토글하려면, xor을 사용해야한다.
mov al, 01
xor al, 01 ; al = 00
xor al, 01 ; al = 01
test 명령은 암시적인 and라고 할 수 있다. 즉, and 연산은 하되 결과에 따라 SF/ZF/PF를 세트하고, 그 결과 값을 버린다. 반영되는 플랙은 위의
and와 같으며 작동 유사 코드는 이렇다:
temp <- Src1 AND Src2;
SF <- MSB (temp);
if temp = 0
then ZF <- 1;
else ZE <- 0;
fi;
PF <- BitwiseXNOR (temp[0:7]);
CF <- 0;
OF <- 0; ; AF는 정의되지 않음
neg 명령은 "0 - X"를 수행하여 2의 보수를 구하며, 작동 코드는 이렇다:
if dest = 0
then CF <- 0;
else CF <- 1;
fi;
dest <- [0 - (dest)]
이 명령은 만약 소스 연산자가 0이면 CF를 0으로 세팅하고 그렇지 않으면 1로 세팅한다. CF를 제외한 5개 플랙은 결과에 따라 세팅한다.
복정밀 논리 연산은 다소 쉽다. 로드 - 연산 - 저장 3과정만 해주면된다. 여기서는 AoA 코드를 인용한다.
32비트 복정밀 and:
mov ax, word ptr [var]
and ax, wor ptr [mask]
mov word ptr [result], ax
mov ax, word ptr [var+2]
and ax, word ptr [mask+2]
mov word ptr [result+2], ax
48비트 복정밀 or:
mov ax, word ptr [var]
or ax, word ptr [mask]
mov wor ptr [result], ax
mov ax, word ptr [var+2]
or ax, word ptr [mask+2]
mov word ptr [result+2], ax
mov ax, word ptr [var+4]
or ax, word ptr [mask+4]
mov word ptr [result+4], ax
64비트 소스를 32비트 레지스터로 복정밀 xor:
mov eax, dword ptr [var]
xor eax, dword ptr [mask]
mov dword ptr [result], eax
mov eax, dword ptr [var+4]
xor eax, dword ptr [mask+4]
mov dword ptr [result+4], eax
32비트 (dx: 상위 16비트, ax: 하위 16비트) 복정밀 not:
not ax
not dx
또는,
not dx
not ax
복정밀 neg는 직접 AoA를 참조하라.
