9.1 이장의내용 9 장. 스트링과배열 스트링프리미티브명령어 2 차원배열 정수배열검색및정렬 컴퓨터정보통신 어셈블리언어 2 9.2 스트링프리미티브명령어 String Primitive Instructions 의동작 String Primitive Instructions Instructions 설명 동작 MOVS(B,W,D) Move string data M[EDI] M[ESI] CMPS(B,W,D) Compare strings M[EDI] 와 M[ESI] 를비교 SCAS(B,W,D) Scan string M[EDI] 와 AL/AX/EAX와비교 STOS(B,W,D), Store string M[EDI] AL/AX/EAX / LODS(B,W,D) Load string AL/AX/EAX M[ESI] LODS AL/AX/EAX STOS SCAS MOVS CMPS MOVS, LODS, STOS: 이동 ( 복사 ) memory ESI (SI) EDI (DI) CMPS, SCAS: 비교 MOVSB, MOVSW, MOVSD 와같이명령어의끝에오퍼런드의크기를나타내는 B(byte), W(word), D(double word) 를사용함 Operand를명시하지않음 Implicit Operand ESI와 EDI는 Direction Flag(DF) 의값에따라서자동적으로증가또는감소됨 String( 배열 ) 처리에유용 DF=0: 증가 (1,2,4), DF=1: 감소 (1,2,4) 16-bit 모드에서는 ESI와 EDI 대신에 SI와 DI가사용됨 컴퓨터정보통신 어셈블리언어 3 컴퓨터정보통신 어셈블리언어 4
MOVSB, MOVSW, MOVSD 명령어 MOVSB, MOVSW, MOVSD 동작 : M[ES:EDI] M[DS:ESI] EDI와 ESI 증가또는감소 (B: 1, W: 2, D: 4) Direction Flag 와 CLD, STD 명령어 Direction Flags (DF) ESI와 EDI의증가, 감소방향을제어 DF = 0: 증가 DF = 1: 감소 source DWORD 0FFFFFFFFh target DWORD? mov esi,offset source mov edi,offset target movsd ; [edi] [esi] ; target source CLD 와 STD Instruction CLD ; clear DF (0) STD ;setdf(1) DF 를명시적으로지정하여증가 / 감소방향을정할때에사용 컴퓨터정보통신 어셈블리언어 5 컴퓨터정보통신 어셈블리언어 6 REP prefix REP (repeat prefix) MOVSB, MOVSW, MOVSD 명령어앞에사용하여명령어의반복수행을지시함 ECX에반복횟수지정 rep movsb L1: movsb Example: 20 doubleword 를 source 배열에서 target 배열로복사 source DWORD 20 DUP(?) target DWORD 20 DUP(?) mov esi,offset source mov edi,offset target mov ecx,lengthof source rep movsd ; DF=0 (forward) ; set REP counter(20) ; 20번반복수행 CMPSB, CMPSW, CMPSD 명령어 CMPSB, CMPSW, CMPSD 동작 : M[ES:ESI] M[DS:EDI] (compare) EDI 와 ESI 증가또는감소 Example: if (source > target) goto L1 else goto L2 source DWORD 1234h target DWORD 5678h mov esi,offset source mov edi,offset target cmpsd ; compare [esi] with [edi] ja L1 ; if source > target, t jump L1 jmp L2 ; else jump L2 컴퓨터정보통신 어셈블리언어 7 컴퓨터정보통신 어셈블리언어 8
REPE, REPNE prefix conditional REP prefix REPE (REPZ) ; ECX>0, ZF=1 인동안 string instruction 반복수행 REPNE (REPNZ) ; ECX>0, ZF=0인동안string instruction 반복수행 반복할때마다 ECX 가 1 씩감소 CMPS 와 SCAS 와같은 string 비교명령어와함께사용 repe cmpsb L1: cmpsb loope L1 repne scasb L1: scasb loopne L1 Example: 여러개의더블워드비교 예 : 더블워드배열비교 source DWORD 1234h, 2345h, 4567h target DWORD 5678h, 789ah, 9abch mov esi,offset source mov edi,offset targett mov ecx, LENGTHOF source repe cmpsd ; repeat while equal ; Now, if equal, then ZF=1, else ZF=0 je Equal jmp NotEqual 컴퓨터정보통신 어셈블리언어 9 컴퓨터정보통신 어셈블리언어 10 SCASB, SCASW, SCASD 명령어 SCASB, SCASW, SCASD 동작 : AL/AX/EAX M[DS:EDI] (compare) 용도 EDI 증가또는감소 배열에서특정한값을검색 배열에서특정한값이아닌원소를검색 Example: 문자열에서특정문자검색 alpha BYTE "ABCDEFGH",0 mov al,'f' ; search for 'F' mov edi,offset alpha mov ecx,lengthof alpha repne scasb ; repeat while not equal jnz quit dec edi ; EDI points to 'F' repeat 가종료되는경우 ZF=1 : 검색성공 (EDI 를감소시켜서검색문자위치저장 ) ZF=0, ECX=0 : 검색실패 컴퓨터정보통신 어셈블리언어 11 컴퓨터정보통신 어셈블리언어 12
STOSB, STOSW, STOSD 명령어 STOSB, STOSW, STOSD 동작 : M[DS:EDI] AL/AX/EAX (store) EDI 증가또는감소 Example: 배열을 0FFh 로채움 str BYTE 100 DUP(?) mov al,0ffh mov edi,offset str mov ecx,lengthof str rep stosb ; value to be stored ; ES:DI points to target ; character count ; direction = forward ; fill with contents of AL LODSB, LODSW, LODSD 명령어 LODSB, LODSW, LODSD 동작 : AL/AX/EAX M[DS:EDI] (load) ESI 증가또는감소 Example: 숫자를 ASCII 코드로변환하여출력 array BYTE 1,2,3,4,5,6,7,8,9 mov esi,offset array mov ecx,lengthof array L1: lodsb ; load byte into AL or al,30h ; convert to ASCII call WriteChar ; display it LODS 를 REP 와같이사용하는것은의미가없음 컴퓨터정보통신 어셈블리언어 13 컴퓨터정보통신 어셈블리언어 14 Example: 배열곱셈 doubleword 배열의각원소에특정한값을곱하여저장 array DWORD 1,2,3,4,5,6,7,8,9,10 multiplier DWORD 10 ; direction = up mov esi,offset array ; source index mov edi,esi ; destination index mov ecx,lengthof array ; loop counter L1: lodsd ; copy [ESI] into EAX mul multiplier li ; multiply l by a value stosd ; store EAX at [EDI] Exercise unpacked BCD가저장된 byte 배열원소를 ASCII로변환하여새로운 byte 배열에저장하는프로그램작성 array BYTE 1,2,3,4,5,6,7,8,9,,,,,,, dest BYTE (LENGTHOF array) DUP(?) mov esi,offset array mov edi,offset dest mov ecx,lengthof array L1: lodsb ; load into AL or al,30h ; convert to ASCII stosb ; store into memory 컴퓨터정보통신 어셈블리언어 15 컴퓨터정보통신 어셈블리언어 16
9.4 2 차원배열 Base-Index Addressing operand 주소 = reg + reg 형식 : [reg + reg] ( 예 ) mov al, [ebx+esi] ; al M[ds:ebx+esi] Base-Index Displacement Addressing operand 주소 = reg + reg + constant 형식 : [reg + reg + constant] 또는 constant[reg + reg] ( 예 ) mov al, table[ebx+esi] ; al M[ds:ebx+esi+table] Base-Index Operand Base-Index Operand: 형식 : [reg + reg] operand 주소 = reg + reg protected mode 에서는 general purpose register 사용가능 real mode 에서는 bx, bp ( 베이스레지스터 ) 와 si, di ( 인덱스레지스터 ) 의결합으로사용함 bp 가포함되면 stack segment 를사용 base reg1 index reg2 constant 를 displacement 라고부름 컴퓨터정보통신 어셈블리언어 17 컴퓨터정보통신 어셈블리언어 18 Base-Index-Displacement Operand Base-Index-Displacement Operand 형식 : [reg + reg + disp] disp[reg + reg] operand 주소 = reg + reg + disp 사용가능한 register 는 base-index operand 와같음 base reg1 index reg2 Scaling Factor 사용 scaling factor 를사용한 base-index operand 형식 : [reg + reg*scale] scaling factor를사용한 base-index-displacement operand 형식 : [reg + reg*scale + disp] disp[reg + reg*scale] word, double word 배열에대한코드작성에주로사용 displacement 컴퓨터정보통신 어셈블리언어 19 컴퓨터정보통신 어셈블리언어 20
Array 1-dimension 1-dimensional array: int tab[10]; tab[2] tab [tab+8] mov eax, [tab+8] Array 2-dimension 2-dimensional array: int tab[4][5]; j logical l organization tab[k] mov eax, tab[esi] k tab[j][k]? tab tab[esi] (esi 4*k), 또는 tab[esi*4] (esi k), physical organization tab[k] mov eax, [ebx+esi] (ebx tab) [ebx] base [ebx+esi] (esi 4*k) k), 또는 [ebx+esi*4] (esi k) index tab tab[ebx] tab[ebx+esi] 단, ebx 4*j*5 ( 행시작offset) esi 4*k ( 열의위치 ) 컴퓨터정보통신 어셈블리언어 21 컴퓨터정보통신 어셈블리언어 22 Structure Array of Structure structure struct misc { int a; short b; char c; } sdata; sdata [sdata+4] [sdata+6] array of structure: struct misc sarray[4]; sdata.b = ax mov [sdata+4], ax p=&sdata; p->b = ax mov ebx, offsetsdatasdata mov [ebx+4], ax 또는 mov ebx, offset sdata mov esi, 4 mov [ebx+esi], ax sarray[k].b = ax mov [esi+sarray+4], ax mov sarray[esi+4], ax mov [ebx + esi + 4], ax 단, ebx sarray 시작주소 esi k* 구조체크기 ( 행시작 offset) 컴퓨터정보통신 어셈블리언어 23 컴퓨터정보통신 어셈블리언어 24
Example: 2-Dimensional Table Table with 3 x 5 array data table BYTE 10h, 20h, 30h, 40h, 50h BYTE 60h, 70h, 80h, 90h, 0A0h BYTE 0B0h, 0C0h, 0D0h, 0E0h, 0F0h NumCols = 5 Row = 1 Col = 2 mov ebx,numcols * Row mov esi,col mov al,table[ebx + esi] Example: 2 차원배열의한행의합계산 mov eax, 2 ; row index mov ecx, 5 ; row size mul ecx ; row index * row size add ebx,eax ; ebx = row offset mov eax,0 ; sum = 0 mov esi,0 ; column index L1: movzx edx,byte PTR[ebx + esi] ; get a byte add eax,edx ; add to sum inc esi ; next byte in row L1: movzx edx,word PTR[ebx + esi*2] ; get a word add eax, edx L1: add eax,[ebx + esi*4] 컴퓨터정보통신 어셈블리언어 25 컴퓨터정보통신 어셈블리언어 26 9.5 정수배열의검색과정렬 Bubble Sort 인접원소와비교후정렬순서가아니면서로교환하면서정렬함 총 n-1 번반복 pass 1: n-1번비교 pass 2: n-2번비교... pass n-2: 2번비교 pass n-1: 1번비교 비교 정렬된원소 Bubble Sort Pseudocode N: 배열원소수 CX1 = N - 1 while (CX1 > 0) { esi = array의시작주소 CX2 = CX1 while (CX2 > 0) { } { if( [esi+4] < [esi] ) // 인접원소비교 exchange [esi] with [esi+4] add esi,4 dec CX2 } dec CX1 컴퓨터정보통신 어셈블리언어 27 컴퓨터정보통신 어셈블리언어 28
Bubble Sort Implementation Bubble Sort Implementation ( 계속 ) ; sort 결과출력 컴퓨터정보통신 어셈블리언어 29 컴퓨터정보통신 어셈블리언어 30 Binary Search Binary Search 순서대로정렬된배열원소들을검색하는알고리즘 Divide and conquer 방법사용 검색범위를반으로줄이면서검색수행 O(log n) 알고리즘 최대비교횟수 (2 16 ) (2 20 ) (2 32 ) 2 3 1 Binary Search Pseudocode values: 배열, N: 배열원소수, sval: 검색값 first = 0; 검색범위시작 last = count - 1; 검색범위끝 while( first <= last ){ 시작 > 끝이면종료 mid = (last + first) / 2; if(values[mid] < sval) first = mid + 1; 중간값 <sval이면검색범위 위쪽 else if(values[mid] > sval) last = mid - 1; 중간값 <sval이면검색범위 아래쪽 else "success" 검색성공 } "fail" 컴퓨터정보통신 어셈블리언어 31 컴퓨터정보통신 어셈블리언어 32
Binary Search Implementation Binary Search Implementation ( 계속 ) 검색할숫자입력 컴퓨터정보통신 어셈블리언어 33 컴퓨터정보통신 어셈블리언어 34 Binary Search Implementation ( 계속 ) Binary Search Implementation ( 계속 ) 컴퓨터정보통신 어셈블리언어 35 컴퓨터정보통신 어셈블리언어 36