Lecture Computer organization and assembly language: Chapter 26 - Dr. Safdar Hussain Bouk

pptx
Số trang Lecture Computer organization and assembly language: Chapter 26 - Dr. Safdar Hussain Bouk 46 Cỡ tệp Lecture Computer organization and assembly language: Chapter 26 - Dr. Safdar Hussain Bouk 979 KB Lượt tải Lecture Computer organization and assembly language: Chapter 26 - Dr. Safdar Hussain Bouk 0 Lượt đọc Lecture Computer organization and assembly language: Chapter 26 - Dr. Safdar Hussain Bouk 4
Đánh giá Lecture Computer organization and assembly language: Chapter 26 - Dr. Safdar Hussain Bouk
4.3 ( 6 lượt)
Nhấn vào bên dưới để tải tài liệu
Để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

CSC 221 Computer Organization and Assembly Language Lecture 26: Recursion and String Operations Lecture 25: Review Assembly Implementation of: • Stack Parameters – INVOKE Directive – PROC Directive – PROTO Directive – Passing by Value or by Reference – Example: Exchanging Two Integers Lecture 25: Review Assembly Implementation of: • Stack Frames – Explicit Access to Stack Parameters – Passing Arguments by Reference (cont.) Lecture Outline • Advanced Procedures: • Recursion – What is recursion? – Recursively Calculating a Sum – Calculating a Factorial • String Primitive Instructions – MOVSB, MOVSW, and MOVSD – CMPSB, CMPSW, and CMPSD – SCASB, SCASW, and SCASD – STOSB, STOSW, and STOSD – LODSB, LODSW, and LODSD Lecture Outline • Selected String Procedures – Str_length Procedure – Str_copy Procedure – Str_trim Procedure – Str_ucase Procedure Recursion • What is recursion? • Recursively Calculating a Sum • Calculating a Factorial What is Recursion? • The process created when . . . – A procedure calls itself – Procedure A calls procedure B, which in turn calls procedure A • Using a graph in which each node is a procedure and each edge is a procedure call, recursion forms a cycle: A E B D C Recursively Calculating a Sum The CalcSum procedure recursively calculates the sum of an array of integers. Receives: ECX = count. Returns: EAX = sum CalcSum PROC cmp ecx,0 jz L2 add eax,ecx sum dec ecx call CalcSum L2: ret CalcSum ENDP Stack frame: ; check counter value ; quit if zero ; otherwise, add to ; decrement counter ; recursive call Recursively Calculating a Sum .code main PROC mov ecx,10 ; count = 10 mov eax,0 ; holds the sum call CalcSum ; calculate sum L1: invoke dwtoa, eax, addr disp1 ; display eax invoke StdOut, addr disp1 invoke ExitProcess,0 main ENDP ;-----------------------------------------CalcSum PROC ; Calculates the sum of a list of integers ; Receives: ECX = count | Returns: EAX = sum ;-----------------------------------------cmp ecx,0 ; check counter value jz L2 ; quit if zero add eax,ecx ; otherwise, add to sum dec ecx ; decrement counter call CalcSum ; recursive call L2: ret CalcSum ENDP END Main Calculating a Factorial This function calculates the factorial of integer n. A new value of n is saved in each stack frame: int function factorial(int n) { if(n == 0) return 1; else return n * factorial(n-1); } As each call instance returns, the product it returns is multiplied by the previous value of n. (1 of 3) recursive calls backing up 5! = 5 * 4! 5 * 24 = 120 4! = 4 * 3! 4 * 6 = 24 3! = 3 * 2! 3*2=6 2! = 2 * 1! 2*1=2 1! = 1 * 0! 1*1=1 0! = 1 1=1 (base case) Calculating a Factorial (2 of 3) Factorial PROC push ebp mov ebp,esp mov eax,[ebp+8] ; get n cmp eax,0 ; n < 0? ja L1 ; yes: continue mov eax,1 ; no: return 1 jmp L2 L1: dec eax push eax ; Factorial(n-1) call Factorial ; Instructions from this point on execute when each ; recursive call returns. ReturnFact: mov ebx,[ebp+8] ; get n mul ebx ; eax = eax * ebx L2:pop ebp ; return EAX ret 4 ; clean up stack Factorial ENDP Calculating a Factorial 12 (3 of 3) n ReturnMain • Suppose we want to calculate 12! • This diagram shows the first few stack frames created by recursive calls to Factorial • Each recursive call uses 12 bytes of stack space. ebp0 11 n-1 ReturnFact ebp1 10 n-2 ReturnFact ebp2 9 ReturnFact ebp3 (etc...) n-3 String Primitive Instructions • MOVSB, MOVSW, and MOVSD • CMPSB, CMPSW, and CMPSD • SCASB, SCASW, and SCASD • STOSB, STOSW, and STOSD • LODSB, LODSW, and LODSD MOVSB, MOVSW, and MOVSD (1 of 2) • The MOVSB, MOVSW, and MOVSD instructions copy data from the memory location pointed to by ESI to the memory location pointed to by EDI. .data source DWORD 0FFFFFFFFh target DWORD ? .code mov esi,OFFSET source mov edi,OFFSET target movsd MOVSB, MOVSW, and MOVSD (2 of 2) • ESI and EDI are automatically incremented or decremented: – MOVSB increments/decrements by 1 – MOVSW increments/decrements by 2 – MOVSD increments/decrements by 4 Direction Flag • The Direction flag controls the incrementing or decrementing of ESI and EDI. – DF = clear (0): increment ESI and EDI – DF = set (1): decrement ESI and EDI The Direction flag can be explicitly changed using the CLD and STD instructions: CLD STD ; clear Direction flag ; set Direction flag Using a Repeat Prefix • REP (a repeat prefix) can be inserted just before MOVSB, MOVSW, or MOVSD. • ECX controls the number of repetitions • Example: Copy 20 doublewords from source to target .data source DWORD 20 DUP(?) target DWORD 20 DUP(?) .code cld ; direction = forward mov ecx,LENGTHOF source ; set REP counter mov esi,OFFSET source mov edi,OFFSET target rep movsd Drill . . . • Use MOVSD to delete the first element of the following doubleword array. All subsequent array values must be moved one position forward toward the beginning of the array: array DWORD 1,1,2,3,4,5,6,7,8,9,10 .data array DWORD 1,1,2,3,4,5,6,7,8,9,10 .code cld mov ecx,(LENGTHOF array) - 1 mov esi,OFFSET array+4 mov edi,OFFSET array rep movsd CMPSB, CMPSW, and CMPSD • The CMPSB, CMPSW, and CMPSD instructions each compare a memory operand pointed to by ESI to a memory operand pointed to by EDI. – CMPSB compares bytes – CMPSW compares words – CMPSD compares doublewords • Repeat prefix often used – REPE (REPZ) – REPNE (REPNZ) Comparing a Pair of Doublewords If source > target, the code jumps to label L1; otherwise, it jumps to label L2 .data source DWORD 1234h target DWORD 5678h .code mov esi,OFFSET mov edi,OFFSET cmpsd ja L1 jmp L2 source target ; compare doublewords ; jump if source > target ; jump if source <= target Drill . . . • Modify the program in the previous slide by declaring both source and target as WORD variables. Make any other necessary changes. Comparing Arrays Use a REPE (repeat while equal) prefix to compare corresponding elements of two arrays. .data source DWORD COUNT DUP(?) target DWORD COUNT DUP(?) .code mov ecx,COUNT ; repetition count mov esi,OFFSET source mov edi,OFFSET target cld ; direction = forward repe cmpsd ; repeat while equal Example: Comparing Two Strings (1 of 3) This program compares two strings (source and destination). It displays a message indicating whether the lexical value of the source string is less than the destination string. .data source BYTE "MARTIN " dest BYTE "MARTINEZ" str1 BYTE "Source is smaller",0dh,0ah,0 str2 BYTE "Source is not smaller",0dh,0ah,0 Screen output: Source is smaller Example: Comparing Two Strings (2 of 3) .code main PROC cld ; direction = forward mov esi,OFFSET source mov edi,OFFSET dest mov ecx,LENGTHOF source repe cmpsb jb source_smaller mov edx,OFFSET str2 ; "source is not smaller" jmp done source_smaller: mov edx,OFFSET str1 ; "source is smaller" done: call WriteString exit main ENDP END main Example: Comparing Two Strings (3 of 3) • The following diagram shows the final values of ESI and EDI after comparing the strings: Before Source: M A R T I After N M A R T I N ESI ESI Before Dest: M EDI A R T I After N E Z M A R T I N E Z EDI Drill . . . • Modify the String Comparison program from the previous two slides. Prompt the user for both the source and destination strings. • Sample output: Input first string: ABCDEFG Input second string: ABCDDG The first string is not smaller. SCASB, SCASW, and SCASD • The SCASB, SCASW, and SCASD instructions compare a value in AL/AX/EAX to a byte, word, or doubleword, respectively, addressed by EDI. • Useful types of searches: – Search for a specific element in a long string or array. – Search for the first element that does not match a given value. SCASB Example Search for the letter 'F' in a string named alpha: .data alpha BYTE "ABCDEFGH",0 .code mov edi,OFFSET alpha mov al,'F’ ; search for 'F' mov ecx,LENGTHOF alpha cld repne scasb ; repeat while not equal jnz quit dec edi ; EDI points to 'F' What is the purpose of the JNZ instruction? STOSB, STOSW, and STOSD • The STOSB, STOSW, and STOSD instructions store the contents of AL/AX/EAX, respectively, in memory at the offset pointed to by EDI. • Example: fill an array with 0FFh .data Count = 100 string1 BYTE Count DUP(?) .code mov al,0FFh ; mov edi,OFFSET string1 ; mov ecx,Count ; cld ; rep stosb ; value to be stored ES:DI points to target character count direction = forward fill with contents of AL LODSB, LODSW, and LODSD • LODSB, LODSW, and LODSD load a byte or word from memory at ESI into AL/AX/EAX, respectively. • Example: .data array BYTE 1,2,3,4,5,6,7,8,9 .code mov esi,OFFSET array mov ecx,LENGTHOF array cld L1: lodsb ; load byte into AL or al,30h ; convert to ASCII call WriteChar ; display it loop L1 Array Multiplication Example Multiply each element of a doubleword array by a constant value. .data array DWORD 1,2,3,4,5,6,7,8,9,10 multiplier DWORD 10 .code cld ; direction = up mov esi,OFFSET array ; source index mov edi,esi ; destination index mov ecx,LENGTHOF array ; loop counter L1: lodsd mul multiplier stosd loop L1 ; copy [ESI] into EAX ; multiply by a value ; store EAX at [EDI] Drill . . . • Write a program that converts each unpacked binarycoded decimal byte belonging to an array into an ASCII decimal byte and copies it to a new array. .data 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 cld L1:lodsb ; load into AL or al,30h ; convert to ASCII stosb ; store into memory loop L1 Selected String Procedures The following string procedures may be found in the Irvine32 and Irvine16 libraries: • Str_length Procedure • Str_copy Procedure • Str_trim Procedure • Str_ucase Procedure Str_length Procedure • Calculates the length of a null-terminated string and returns the length in the EAX register. • Prototype: Str_length PROTO, pString:PTR BYTE ; pointer to string Example: .data myString BYTE "abcdefg",0 .code INVOKE Str_length, ADDR myString ; EAX = 7 Str_length Source Code Str_length PROC USES edi, pString:PTR BYTE ; pointer to string mov edi,pString mov eax,0 L1: cmp byte ptr [edi],0 je L2 inc edi inc eax jmp L1 L2: ret Str_length ENDP ; character count ; ; ; ; end of string? yes: quit no: point to next add 1 to count Str_copy Procedure • Copies a null-terminated string from a source location to a target location. • Prototype: Str_copy PROTO, source:PTR BYTE, target:PTR BYTE ; pointer to string ; pointer to string Str_copy Source Code Str_copy PROC USES eax ecx esi edi, source:PTR BYTE, ; source string target:PTR BYTE ; target string INVOKE Str_length,source ; EAX = length source mov ecx,eax ; REP count inc ecx ; add 1 for null byte mov esi,source mov edi,target cld ; direction = up rep movsb ; copy the string ret Str_copy ENDP Str_trim Procedure • The Str_trim procedure removes all occurrences of a selected trailing character from a null-terminated string. • Prototype: Str_trim PROTO, pString:PTR BYTE, ; points to string char:BYTE ; char to remove Example: .data myString BYTE "Hello###",0 .code INVOKE Str_trim, ADDR myString, '#’ myString = "Hello" Str_trim Procedure • Str_trim checks a number of possible cases (shown here with # as the trailing character): – The string is empty. – The string contains other characters followed by one or more trailing characters, as in "Hello##". – The string contains only one character, the trailing character, as in "#" – The string contains no trailing character, as in "Hello" or "H". – The string contains one or more trailing characters followed by one or more non-trailing characters, as in "#H" or "###Hello". Str_trim Source Code Str_trim PROC USES eax ecx edi, pString:PTR BYTE, ; points to string char:BYTE ; char to remove mov edi,pString INVOKE Str_length,edi; returns length in EAX cmp eax,0 ; zero-length string? je L2 ; yes: exit mov ecx,eax ; no: counter = string length dec eax add edi,eax ; EDI points to last char mov al,char ; char to trim std ; direction = reverse repe scasb ; skip past trim character jne L1 ; removed first character? dec edi ; adjust EDI: ZF=1 && ECX=0 L1:mov BYTE PTR [edi+2],0 ; insert null byte L2:ret Str_trim ENDP Str_ucase Procedure • The Str_ucase procedure converts a string to all uppercase characters. It returns no value. • Prototype: Str_ucase PROTO, pString:PTR BYTE ; pointer to string Example: .data myString BYTE "Hello",0 .code INVOKE Str_ucase, ADDR myString Str_ucase Source Code Str_ucase PROC USES eax esi, pString:PTR BYTE mov esi,pString L1:mov cmp je cmp jb cmp ja and al,[esi] ; get char al,0 ; end of string? L3 ; yes: quit al,'a’ ; below "a"? L2 al,'z’ ; above "z"? L2 BYTE PTR [esi],11011111b ;convert the char L2:inc esi jmp L1 L3: ret Str_ucase ENDP ; next char Summary • Advanced Procedures: • Recursion – What is recursion? – Recursively Calculating a Sum – Calculating a Factorial • String Primitive Instructions – MOVSB, MOVSW, and MOVSD – CMPSB, CMPSW, and CMPSD – SCASB, SCASW, and SCASD – STOSB, STOSW, and STOSD – LODSB, LODSW, and LODSD Summary • Selected String Procedures – Str_length Procedure – Str_copy Procedure – Str_trim Procedure – Str_ucase Procedure (cont.) Reference Most of the Slides are taken from Presentation: Chapter 8 & 9 Assembly Language for Intel-Based Computers, 4th Edition Kip R. Irvine (c) Pearson Education, 2002. All rights reserved. You may modify and copy this slide show for your personal use, or for use in the classroom, as long as this copyright statement, the author's name, and the title are not changed.
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.