[시스템 프로그래밍 10강] Shift and Rotate 명령 및 활용

덧셈 나눗셈을 하려 하는데 그 전에 쉬프트 연산자를 먼저 알아보자.

Shift and Rotate Instructions

• x86 프로세스는 쉬프트 연산에 많은 명령어 세트를 제공한다.

  

• 모두 OVERFLOW와 캐리플래그에 영향을 준다.

• 2가지 형태의 쉬프트 연산을 제공한다.

1. Logical Shifts and Arithmetic Shifts

1. Logical shift

• 우리가 익히 알고 있는 쉬프트 연산이다.

• 8비트의 데이터가 있다고 할 때

• 한칸씩 우리가 원하는 방향으로 이동 시키고 새로 생성된 비트를 0으로 채우는 것이 특징이다.

  

• 빠져나온 비트가 캐리 플래그로 이동한다.

• LSB가 빠져나왔고 MSB는 비어있어서 0으로 채워진다.

• 예시 11001111에 대한 단일 논리적 오른쪽 이동으로 01100111이 생성된다.

  

2. Arithmetic shift(산술이동)

• 새로 생성된 비트 위치는 원래 숫자의 부호비트의 복사본으로 채워진다.

  

• 이것의 의미는 부호를 지키는 것이다.

• 만약 이렇게 하지 않으면 UNSIGNED만 처리가 가능하다.

• 예시 :부호 비트에 1이 있는 11001111이 이동하면 11100111이 된다.

  

2. SHL (shift left) Instruction

• x86프로세서에서 제공하는 쉬프트 연산을 살펴보자!

• 이건 왼쪽으로 shift를 하는 명령어이다.

• destination operand를 logical left shift를 해서 아래 비트를 0으로 채워준다.

• 가장 높은 비트는 캐리 플래그로 이동하고 캐리 플래그에 있던 비트는 버려진다.

• 예시 : 11001111을 1비트만큼 왼쪽으로 밀면 1001110이 된다.

  

명령 형식(Instruction format)

• SHL destiantion,count
  • SHL reg,imm8
  • SHL mem,imm8
  • SHL reg, CL
  • SHL mem,CL
  • 여기서 imm8이 무엇이냐고 한다면 그냥 상수라고 보면 0~255까지의 값을 가진다고 생각하면 된다.
  • CL은 8비트 레지스터이다.

• 모든 종류의 메모리와 레지스터가 올 수가 있다.

• 인자로 몇 비트를 쉬프트 할지 정할수도 있고, CL에 들어있는 값으로 인자를 사용할 수 있다.

예제

• BL이 왼쪽으로 한 번 이동합니다.

• 가장 높은 비트는 Carry 플래그에 복사되고 가장 낮은 비트 위치는 0으로 할당됩니다.

  

• 여러비트를 shift한다는 건 shift연산이 여러번 이뤄진다는 것을 의미한다.

• 몇번 shift했는지에 따라서 마지막으로 빠져나온 비트가 CF에 세팅이 된다.

Bitwise Multiplication

• 비트를 왼쪽으로 이동하면 2를 곱했다는 것을 의미한다.

  

• 2번 shift하면 2^2을 곱한 것과 같은 결과가 나온다.

  

3. SHR (shift right) Instruction

• 오른쪽으로 비트를 shift하는 명령

• 빈칸은 0으로 나가는 비트는 Carryflag로 변경

  

• SHL과 동일한 모양이다.

예제

Bitwise Division

• 왼쪽으로 쉬프트 해주면 곱이고 오른쪽은 나눗셈을 의미한다. (당연)

• 다만 이 나누기는 Unsigned라고 생각했기 떄문에 의미가 있는 것이고, signed 나누기를 하고 싶다면 SAR를 해줘야 한다.

4. SAL (shift arithmetic left) and SAR (shift arithmetic right) Instructions

SAL (shift arithmetic left)

• The SAL instruction works the same as the SHL instruction

• 즉 SAL명령은 SHL과 완전 동일하다. 따라서 딱히 고민할 필요는 없다.

• SAL과 SHL은 완전 같은 기계어 코드를 공유한다.

• 다만 SAR은 조금 다르다.

SAR (shift arithmetic right)

• SAR 명령은 대상 피연산자에 대해 오른쪽 산술 시프트를 수행합니다.

  

• 사용법은 SHR과 같지만 동작은 살짝 다르다. (사인비트 때문에)

  

• 음수에 대해서도 제대로 동작한다.

• signed로 나누기 예시

  

AX레지스터에 있는 걸 EAX로 Sign을 확장

• AX에 부호있는 정수가 포함되어 있고, 그 부호를 EAX로 확장하려고 한다고 가정해 보겠습니다.

• 먼저 EAX를 16비트 왼쪽으로 이동한 다음 산술적으로 16비트를 오른쪽으로 이동한다.

• 왼쪽으로 16칸 이동 후 오른쪽으로 16칸 밀기

• 다음으로 오른쪽으로 16칸을 밀게 되면 전부 같은 1로 채울 수 있게 된다.

• 사실 movsigned extention(MOVSX)쓰면 되는데 어떻게 쓰는지를 보여주는 것이다.

5. ROL (rotate left) Instruction

• 비트를 원형으로 회전시킨다.

• 비트가 사라지는 비트가 다시 생기는 비트로 들어간다.

• ROL 명령은 각 비트를 왼쪽으로 이동합니다.

• 가장 높은 비트는 캐리 플래그와 가장 낮은 비트 위치에 복사됩니다.

  

• 높은 비트가 캐리 플래그와 비트위치 0 모두에 복사되는 걸 볼 수 있다.

  

• 다중 회전

  

• 비트 교환

  

4비트를 회전 시키면 앞쪽 비트와 아래 비트를 변경 할 수 있다.

• 16진수 기준으로 보기(회전 잘보이게)(4비트)

  

6. ROR (rotate right) Instruction

• 방향만 다르고 ROL과 같다.

  

• 왼쪽 회전이다.

• 예시

  

7. RCL (rotate carry left) and RCR (rotate carry right) Instructions

RCL

• RCL은 각 비트를 왼쪽으로 이동하고, CF를 LSB에 복사하고, MSB를 CF에 복사한다.

  

• 이 녀석은 Carry flag를 포함해서 Rotate를 돌리고 있다.

CLC 명령으로 carry flag를 지운다.

• 예시코드

  

• 예시코드 해설

  

RCR

가장 뒤에 있는 LSB를 기준으로 CF를 설정한다. (분기에 사용)

• RCR 명령은 각 비트를 오른쪽으로 이동하고, CF를 MSB로 복사하고 LSB를 CF로 복사한다.

  

• 다음 코드 예제는 STC를 사용해서 캐리 플래그를 설정하고 AH레지스터에서 RCR연산을 수행하는 것이다.

  

8. Signed Overflow

• 일반적으로 signed에서 overflow가 중요하고, unsigned 에서 carry flag가 중요했다.

• ROTATE연산의 결과로 부호가 바끼면 OVERFLOW가 세팅이 된다.

• 한가지 주의할점!!

• 1비트 단위에 대해서만 overflow플래그가 설정이 되지만…! 그 이상의 shift나 rotate를 하려고 하면 안된다.!!!!!!!!

9. SHLD (shift left double) / SHRD (shift right double) Instructions

The SHLD instruction

• 이 녀석은 피연산자가 3개이다는 점이 특히 좀 다르다.!

• SHLD dest, source, count

• SHLD는 dest 피연산자를 지정된 비트 수만큼 왼쪽으로 이동합니다.

• shift에 의해 비워진 비트는 source 피연산자의 MSB로 채워진다.

• 소스 피연산자는 영향을 받지 않지만 부호,0,보조, 패리티, 캐리 플래그는 영향을 받는다.

dest만 업데이트 되고 source는 변화하지 않는다.

• 그림은 시프트 카운터가 1인 SHLD의 실행을 보여준다.

• 소스 피연산자의 가장 높은 비트가 대상 피연산자의 가장 낮은 비트에 복사된다.

• 모든 대상 피연산자비트가 왼쪽으로 이동한다.

The SHRD instruction

• SHRD dest, source, count

• SHRD는 dest 피연산자를 주어진 비트 수만큼 오른쪽으로 이동한다.

• shift에 의해 비워진 비트는 source의 LSB에 의해 채워진다.

• 그림은 count가 1인 SHRD를 보여준다.

  

• 명령의 dest와 source를 잘 보고 하세요!!

명령 포맷

• dest 는 레지스터 또는 피연산자 일 수 있다.

• source는 레지스터여야만 한다.

• count는 cl레지스터이거나 8비트 상수(imm)연산자 일 수도 있다.

  

예제 1

• wval을 왼쪽 4비트 이동하고 AX의 상위 4비트를 wval의 하위 4비트 위치에 넣는 예시

  

.data
wval WORD 9BA6h
.code
mov ax,0AC36h
shld wval,ax,4 ;wval = BA6Ah

예제 2

• AX를 오른쪽으로 4비트 이동하고, DX의 낮은 4비트는 AX의 높은 4비트 위치로 이동하는 예시

  

mov ax,234Bh
mov dx,7654h
shrd ax,dx,4

SHLD와 SHRD 조작하는 예제

• 어플리케이션 응용 가능 분야
  • 화면에서 이미지 위치를 변경하기 위해서 비트그룹을 좌우로 이동해야 하는 경우 SHLD, SHRD를 이용해서 비트 매핑된 이미지를 조작할 수 있다.
  • 또 다른 잠재적 응용 분야는 암호화 알고리즘에 비트이동이 포함되는 데이터 암호화이다.
  • 마지막으로 매우 긴 정수로 빠른 곱셈과 나눗셈을 수행할 때 2가지 명령이 사용 될 수 있다.

예제 doubleWord array를 오른쪽으로 4비트 이동하기

.data
array DWORD 648B2165h,8c943A29h,6DFA4B86h,91F76c04h, 
.code
		mov bl,4 ; shift count
		mov esi,OFFSET array ; offset of the array
		mov ecx,(LENGTHOF array) - 1 ; number of array elements

L1: push ecx ; save loop counter
		mov eax,[esi + TYPE DWORD] 
		mov cl,bl  ; shift count
		shrd [esi],eax,cl ; shift EAX into high bits of [ESI]
		add esi,TYPE DWORD ; point to next doubleword pair
		pop ecx ; restore loop counter
		loop L1
		shr DWORD PTR [esi],COUNT ;shift the last doubleword 

• push ecx 하는 이유 : cl레지스터 쓰므로

• 저자의 의도대로 하면 루프에서는 4번원소까지 수정완료되서 루프가 끝나면 쉬프트 한번 해준다.

• shr를 보면 PTR이라고 적혀있는데 DWORD PTR은 8비트를 가져오겠다는 것을 의미한다.

• 교수님이 보시기엔 right가 아니라 left일 거라는 생각을 하신다.

1. Shifting Multiple Doublewords

• byte, word, doubleword배열로 분할 된 확장된 정밀도 정수를 사용할 수 있다.

• 일반적인 정수 저장 방법은 리틀앤디안 방식이다.
  • 배열의 시작 주소에서 하위 바이트를 배치한다.
  • 그 후 해당 바이트에서 위쪽으로 올라가면서 다음 순차 메모리 위치에 각각을 저장한다.
  • 배열을 일련의 바이트로 저장하는 대신에 일련의 word 또는 double word로 저장할 수 있다.
  • 이렇게 해도 x86컴퓨터는 word와 doubleword를 리틀앤디안 순서로 저장하기 때문에 각각 바이트는 여전히 리틀앤디안 순서대로 저장된다.

멀티 바이트 배열을 오른쪽 1비트 이동하는 방법(여기부터)

• 리틀앤디안 형식이여서 그냥 밀면 원하는대로 밀 수가 없다.

• 그래서 시작부분이 esi + 2가 되는 것이다.

멀티바이트 배열을 오른쪽으로 1비트 이동하는 방법

• step1 : [ESI + 2] 에서 가장 높은 바이트를 오른쪽으로 이동하여 가장 낮은 비트를 CF에 자동으로 복사한다.

  

• step 2 : [ESI + 1]의 값을 오른쪽으로 회전해서 가장 높은 비트를 CF의 값으로 채우고 가장 낮은 비트를 CF로 이동한다.

  

• step3 : [ESI]의 값을 오른쪽으로 회전하여 가장 높은 비트를 CF의 값으로 채우고 가장 낮은 비트를 CF로 이동한다.

  

• 3단계가 완료되면 모든 비트가 오른쪽으로 1단계 이동한다.

  

• 전체를 3바이트라고 보고 그림에서는 이렇게 해서 shift를 안 것처럼 보이게 할 수 있다.

• 즉 더 큰 크기의 데이터들에 대해서 곱셈 나눗셈을 할 수 있다는 점에서 의의가 있다.

어셈블리 코드

.data
ArraySize = 3
array BYTE ArraySize DUP(99h) ;1001 pattern in each nybble
.code 
main PROC
	mov esi,0
	shr array[esi+2],1 ;high byte
	rcr array[esi+1],1 ;middle byte, include Carry flag
	rcr array[esi],1 ;low byte, include Carry flag

• 이 예제는 3바이트만 이동하지만 단어배열이나 다른 것을 사용해서도 다 적용할 수 있다.

2. Binary Multiplication

• 때떄로 프로그래머는 MUL명령어 보다는 비트 연산이 더 낫다.

• 다만 꼭 2의 N승만 가능하냐? 그건 아니다.

• 실제로 2의 제곱만 곱하는게 아니라 unsigned 36을 eax에 곱하는 예시를 보면

  

예시) 23 * 36 곱은 4428

• 2번비트와 5번 비트는 36으로 설정되고 위에서 보이듯 shift 2를 한것과 shift5를 한것을 더해서 결과값을 구할 수 있다.

mov eax,12
mov ebx,eax
shl eax,5 ;multiply by 2^5
shl ebx,2 ;multiply by 2^2
add eax,ebx ;add the product

3. Displaying Binary Bits

• binary integer를 ASCII binary string로 변환해서 표시할 수 있도록 한다.
  • SHL명령은 피연산자가 왼쪽으로 이동할 때마다 피연산자의 가장 높은 비트를 CF에 복사하기 때문에 이점에서 유용하다.

    

  BinToAsc PROC
  push ecx
  	push esi
  	mov ecx,32 ;number of bits in EAX
  L1: sh1 eax ,1 ;shift high bit into Carry flag
  		mov BYTE PTR [esi], '0' ;choose 0 as default digit
  		jnc L2 ;if no Carry, jump to L2
  		mov BYTE PTR [esi],'1' ;else move 1 to buffer
  L2: inc esi ;next buffer position
  		loop L1 ;shift another bit to left
  		pop esi
  		pop ecx
  		ret
  BinToAsc ENDP

  • 이 코드를 보면 1비트씩 밀면서 crray flag가 없으면 다음 버퍼로 넘어가고 캐리가 있으면 문자 1이 esi로 들어간다. 그리고 esi는 주소값이니까 1증가 시키면 다음 버퍼 포지션으로 가게 되고 다시 루프를 돌린다. 그렇게 바이너리 값을 아스키로 바꿔서 화면에 바이너리를 출력하게 해준다.

4. Extracting File Date Fields

• 과거 도스 시절 16비트에 날짜를 저장했다.

• ms는 1980년을 기준으로 숫자를 늘려갔다. (중요하지 않아요 이 내용!!! 그냥 알려주는거~~)

따라서 비트마스킹을 해서 요일필드 월 필드 연도 필드를 추출 할 수 있었다.

Uploaded by N2T