Difference between revisions of "CSC231 Homework 8 Fall 2017"
(→Problem #1: Programming in C) |
(→Problem 2) |
||
(14 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 13:57, 27 November 2017 (EST) | --[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 13:57, 27 November 2017 (EST) | ||
---- | ---- | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<br /> | <br /> | ||
+ | <bluebox> | ||
+ | This homework assignment is due Monday Dec. 4th, at 11:55 p.m. | ||
+ | </bluebox> | ||
<br /> | <br /> | ||
<br /> | <br /> | ||
− | + | __TOC__ | |
<br /> | <br /> | ||
− | Write an assembly program called ''' | + | =Problem #1= |
+ | <br /> | ||
+ | Write an assembly program called '''hw8a.asm''' that contains several functions, but no main program. In other words, your program '''should not contain a "_start" label'''. The main program will be in a separate file that will be assembled separately, and linked to your program to create an executable file. | ||
The functions should behave as follows: | The functions should behave as follows: | ||
Line 49: | Line 47: | ||
call f2 | call f2 | ||
− | ; upon return from f2, eax | + | ; upon return from f2, eax will contain 2a + 3b - c = 2*3 + 3*5 - 7 = 14 |
</source> | </source> | ||
Line 72: | Line 70: | ||
==Making Your Functions Known to Other Programs== | ==Making Your Functions Known to Other Programs== | ||
<br /> | <br /> | ||
− | Your ''' | + | Your '''hw8a.asm''' program should contain only the 3 functions described above. <font color="magenta">You may add other helper functions if it makes your programming task easier. For example, you may want to have a function that tests an integer and returns 1 or 0 depending on whether the integer is even or not.</font> No need for a data segment or for a _Start label. However, you need to make your functions known to the main program that is in a different file, and that will be linked with your program. So you need to add these 3 lines at the top of your program: |
<br /> | <br /> | ||
<br /> | <br /> | ||
Line 84: | Line 82: | ||
==Testing Your Code== | ==Testing Your Code== | ||
<br /> | <br /> | ||
− | Create the following program and call it test.asm. It will be the test program for your | + | Create the following program and call it test.asm. It will be the test program for your hw8b.asm program: |
<br /> | <br /> | ||
::<source lang="asm"> | ::<source lang="asm"> | ||
Line 153: | Line 151: | ||
231b@aurora ~ '''nasm -f elf test.asm''' | 231b@aurora ~ '''nasm -f elf test.asm''' | ||
− | 231b@aurora ~ '''nasm -f elf | + | 231b@aurora ~ '''nasm -f elf hw8a.asm''' |
231b@aurora ~ '''nasm -f elf 231Lib.asm''' | 231b@aurora ~ '''nasm -f elf 231Lib.asm''' | ||
− | 231b@aurora ~ '''ld -melf_i386 -o test test.o | + | 231b@aurora ~ '''ld -melf_i386 -o test test.o hw8a.o 231Lib.o''' |
231b@aurora ~ '''./test''' | 231b@aurora ~ '''./test''' | ||
HELLO THERE! 12345 | HELLO THERE! 12345 | ||
Line 162: | Line 160: | ||
;Note: | ;Note: | ||
− | : The test program above does not check | + | : The test program above does not check whether ''f3'' modifies the ebx, ecx, edx, esi, or edi registers. You can verify this yourself (maybe by printing the registers before and after the call to ''f3'')! |
+ | <br /> | ||
+ | <br /> | ||
+ | |||
+ | =Problem 2= | ||
+ | <br /> | ||
+ | ==Java Program== | ||
+ | <br /> | ||
+ | ::<source lang="java"> | ||
+ | /* | ||
+ | Series.java | ||
+ | Homework program with a recursive function. | ||
+ | */ | ||
+ | |||
+ | class Series { | ||
+ | |||
+ | /** | ||
+ | sumNSquared: returns the sum 1 + 2*2 + 3*3 + 4*4 +... + n*n | ||
+ | The computation is done recursively. | ||
+ | */ | ||
+ | private static int sumNSquared( int n ) { | ||
+ | |||
+ | if ( n <= 1 ) return 1; | ||
+ | return n*n + sumNSquared( n-1 ); | ||
+ | } | ||
+ | |||
+ | public static void main( String args[] ) { | ||
+ | int n = Integer.parseInt ( args[0] ); | ||
+ | System.out.print( "sumNSquared(" + n + ")=" + sumNSquared(n) +"\n\n" ); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </source> | ||
+ | <br /> | ||
+ | ==Example== | ||
+ | <br /> | ||
+ | ::<source lang="text"> | ||
+ | cs231a@aurora ~ $ javac Series.java | ||
+ | cs231a@aurora ~ $ java Series 1 | ||
+ | sumNSquared(1)=1 | ||
+ | |||
+ | cs231a@aurora ~ $ java Series 2 | ||
+ | sumNSquared(2)=5 | ||
+ | |||
+ | cs231a@aurora ~ $ java Series 10 | ||
+ | sumNSquared(10)=385 | ||
+ | |||
+ | cs231a@aurora ~ $ java Series 100 | ||
+ | sumNSquared(100)=338350 | ||
+ | |||
+ | |||
+ | </source> | ||
+ | <br /> | ||
+ | ==Questions== | ||
+ | <br /> | ||
+ | Please answer the following questions on Moodle: | ||
+ | <br /> | ||
+ | ;Question 1 | ||
+ | :What is the smallest integer number provided on the command line that will generate an arithmetic overflow of the result? | ||
+ | |||
+ | ;Question 2 | ||
+ | :Will the Java Virtual Machine crash when an airthmetic overflow of the result occurs in the program? | ||
+ | |||
+ | ;Question 3 | ||
+ | : How many recursive calls will take place before a stack overflow error occurs? | ||
+ | |||
+ | <br /> | ||
+ | |||
+ | =Problem 3= | ||
+ | <br /> | ||
+ | Create an assembly program called '''hw8c.asm''' that implements the program of Problem 2, with a slight modification: your program will prompt the user for a number, and will output the series corresponding to that number. | ||
+ | <br /> | ||
+ | ==Examples== | ||
+ | <br /> | ||
+ | cs231a@aurora ~ $ ./hw8c | ||
+ | > 5 | ||
+ | 55 | ||
+ | cs231a@aurora ~ $ ./hw8c | ||
+ | > 1 | ||
+ | 1 | ||
+ | cs231a@aurora ~ $ ./hw8c | ||
+ | > 10 | ||
+ | 385 | ||
+ | |||
+ | <br /> | ||
+ | ==Submission== | ||
<br /> | <br /> | ||
+ | Submit your program in the Homework 8 Problem 3 section on Moodle. | ||
<br /> | <br /> | ||
<!-- ==================================================================== --> | <!-- ==================================================================== --> | ||
− | + | ||
<br /> | <br /> | ||
<br /><br /> | <br /><br /> | ||
Line 188: | Line 272: | ||
<br /> | <br /> | ||
=Solution Program= | =Solution Program= | ||
+ | |||
==Problem 1== | ==Problem 1== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<br /> | <br /> | ||
::<source lang="asm"> | ::<source lang="asm"> | ||
Line 317: | Line 348: | ||
</source> | </source> | ||
− | </ | + | ==Problem 2== |
+ | <br /> | ||
+ | ::<source lang="text"> | ||
+ | Question 1: what value of n creates an overflow? | ||
+ | Answer: 1861 | ||
+ | |||
+ | 1860 | ||
+ | sumNSquared(1860)=2146682110 | ||
+ | |||
+ | 1861 | ||
+ | sumNSquared(1861)=-2144821865 | ||
+ | |||
+ | |||
+ | Question 2: The Java VM does not crash when the number provided on the command line generates an overflow | ||
+ | |||
+ | Question 3: We use bash: | ||
+ | |||
+ | for i in `seq 9000 10000` ; do java Series $i ; done &> output.txt | ||
+ | |||
+ | The bash loop above runs the Series program for all values of i ranging in 9000 to 10000, | ||
+ | and outputs both stdout and stderr to the file output.txt | ||
+ | |||
+ | grep -B 5 -i stackOverflow output.txt | head -n 10 | ||
+ | |||
+ | The command above looks for the lines containing "stackoverflow", and ask to see | ||
+ | 5 lines BEFORE the matching line (-B 5). The "head -n 10" pipe keeps only the | ||
+ | first 10 lines of the output of grep: | ||
+ | |||
+ | Here's the output of the bash command: | ||
+ | |||
+ | sumNSquared(9923)=-675808722 | ||
+ | |||
+ | sumNSquared(9924)=-577322946 | ||
+ | |||
+ | Exception in thread "main" java.lang.StackOverflowError | ||
+ | -- | ||
+ | at Series.sumNSquared(Series.java:15) | ||
+ | at Series.sumNSquared(Series.java:15) | ||
+ | at Series.sumNSquared(Series.java:15) | ||
+ | |||
+ | |||
+ | So the answer is that the stack overflow occurs for n = 9925. | ||
+ | |||
+ | |||
+ | </source> | ||
+ | <br /> | ||
+ | |||
+ | ==Problem 3== | ||
+ | <br /> | ||
+ | ::<source lang="asm"> | ||
+ | ;;; -------------------------------------------------- | ||
+ | ;;; hw8c.asm | ||
+ | ;;; D. Thiebaut | ||
+ | ;;; Uses a recursive function to compute | ||
+ | ;;; n*n + (n-1)*(n-1) + ... + 3*3 + 2*2 + 1*1 | ||
+ | ;;; | ||
+ | ;;; -------------------------------------------------- | ||
+ | |||
+ | section .data | ||
+ | n dd 0 | ||
+ | prompt db "> " | ||
+ | |||
+ | section .text | ||
+ | global _start | ||
+ | extern _printInt | ||
+ | extern _println | ||
+ | extern _getInput | ||
+ | extern _printString | ||
+ | |||
+ | ;;; -------------------------------------------------- | ||
+ | ;;; def series( n ): | ||
+ | ;;; if n==1: | ||
+ | ;;; return 1 | ||
+ | ;;; res = series( n-1 ) | ||
+ | ;;; return n*n + res | ||
+ | ;;; -------------------------------------------------- | ||
+ | ;;; passes n in stack, returns result in eax | ||
+ | series: push ebp | ||
+ | mov ebp, esp | ||
+ | |||
+ | push ebx ;save regs used by function | ||
+ | push edx | ||
+ | |||
+ | .if: cmp dword[ebp+8], 1 | ||
+ | jg .recurse | ||
+ | mov eax, 1 | ||
+ | jmp .endSeries | ||
+ | |||
+ | .recurse: | ||
+ | mov eax,dword[ebp+8] | ||
+ | mul dword[ebp+8] | ||
+ | push eax ;save n*n in stack, temporarily | ||
+ | |||
+ | mov eax,dword[ebp+8] ;eax <- n | ||
+ | dec eax ;eax <- n-1 | ||
+ | push eax ;pass n-1 to fact | ||
+ | call series ;eax <- series(n-1) | ||
+ | pop ebx ;get n*n | ||
+ | add eax,ebx ;eax <- n*n + series(n-1) | ||
+ | |||
+ | .endSeries: | ||
+ | pop edx | ||
+ | pop ebx | ||
+ | |||
+ | pop ebp | ||
+ | ret 4 | ||
+ | |||
+ | ;;; def main(): | ||
+ | ;;; n = 5 | ||
+ | ;;; print( series( n ) ) | ||
+ | ;;; main() | ||
+ | |||
+ | _start: | ||
+ | ;; get n from user | ||
+ | mov ecx, prompt | ||
+ | mov edx, 2 | ||
+ | call _printString | ||
+ | call _getInput | ||
+ | mov dword[n], eax | ||
+ | |||
+ | ;; call series | ||
+ | push dword[n] | ||
+ | call series | ||
+ | |||
+ | ;; print result passed in eax | ||
+ | call _printInt | ||
+ | call _println | ||
+ | |||
+ | exit: | ||
+ | mov eax, 1 | ||
+ | mov ebx, 0 | ||
+ | int 0x80 | ||
+ | |||
+ | </source> | ||
+ | |||
<br /> | <br /> | ||
<br /> | <br /> |
Latest revision as of 12:33, 5 December 2017
--D. Thiebaut (talk) 13:57, 27 November 2017 (EST)
This homework assignment is due Monday Dec. 4th, at 11:55 p.m.
Contents
Problem #1
Write an assembly program called hw8a.asm that contains several functions, but no main program. In other words, your program should not contain a "_start" label. The main program will be in a separate file that will be assembled separately, and linked to your program to create an executable file.
The functions should behave as follows:
- f1( s ). Receives the address of a string s in the stack, and converts the string to uppercase, replacing all the alphabetic characters in the string to uppercase. We assume that the string, as in C, is terminated by a '\0' char. Here is an example of how to call the function:
s1 db "Hello world!", 0 s1Len equ $-s1 ... mov eax, s1 push eax call f1 mov ecx, s1 mov edx, s1Len-1 ; figure out why the -1! mov eax, 4 mov ebx, 1 int 0x80
- The code above will print "HELLO WORLD!"
- f2(a, b, c): f2 receives 3 integer parameters in the stack and computes 2a + 3b -c and returns this value in eax.
- Here is an example of how to call the function:
a dd 3 b dd 5 c dd 7 ... push dword[a] push dword[b] push dword[c] call f2 ; upon return from f2, eax will contain 2a + 3b - c = 2*3 + 3*5 - 7 = 14
- f3( table, n ): this function receives in the stack the address of an array of ints, and the number of ints in the array. It returns in eax the number of even ints in the array. f3 should not modify any of the other registers, besides eax, of course!
- Here is an example of how to call the function f3:
array dd 3, 5, 0, 1, 2, 10, 100, 4, 1 arrayLen equ ($-array)/4 ; figure out the /4 part. ... mov eax, array push eax mov eax, arrayLen push eax call f3 ; upon return from f3, eax contains 5, because there are 5 even numbers in array.
Making Your Functions Known to Other Programs
Your hw8a.asm program should contain only the 3 functions described above. You may add other helper functions if it makes your programming task easier. For example, you may want to have a function that tests an integer and returns 1 or 0 depending on whether the integer is even or not. No need for a data segment or for a _Start label. However, you need to make your functions known to the main program that is in a different file, and that will be linked with your program. So you need to add these 3 lines at the top of your program:
global f1 global f2 global f3
Testing Your Code
Create the following program and call it test.asm. It will be the test program for your hw8b.asm program:
;;;------------------------------------------------------------ ;;; test.asm ;;; tests the functions in hw8_2.asm by calling each one ;;; and printing its result. ;;;------------------------------------------------------------ extern _printString extern _println extern _printDec extern f1 ; f1, f2, and f3 are declared somewhere else extern f2 extern f3 ;;;------------------------------------------------------------ ;;; some variables to pass to the functions ;;;------------------------------------------------------------ section .data s1 db "Hello there! 12345", 0 s1Len equ $-s1 Table dd 1, 2, 3, 30, 100, 200 TableLen equ ($-Table)/4 x1 dd 10 x2 dd 20 x3 dd -1 ;;;------------------------------------------------------------ ;;; main program ;;;------------------------------------------------------------ section .text global _start _start: ;;; test f1 mov eax, s1 ; pass s1 to f1 push eax call f1 mov ecx, s1 mov edx, s1Len call _printString call _println ;;; test f2 push dword[x1] ; pass x1, x2, x3 to f2 push dword[x2] push dword[x3] call f2 call _printDec call _println ;;; test f3 mov eax, Table ; pass Table and length to f3 push eax mov eax, TableLen push eax call f3 call _printDec call _println ;;; ; exit mov ebx, 0 mov eax, 1 int 0x80
- Assemble, link, and run as follows:
231b@aurora ~ nasm -f elf test.asm 231b@aurora ~ nasm -f elf hw8a.asm 231b@aurora ~ nasm -f elf 231Lib.asm 231b@aurora ~ ld -melf_i386 -o test test.o hw8a.o 231Lib.o 231b@aurora ~ ./test HELLO THERE! 12345 81 4
- Note
- The test program above does not check whether f3 modifies the ebx, ecx, edx, esi, or edi registers. You can verify this yourself (maybe by printing the registers before and after the call to f3)!
Problem 2
Java Program
/* Series.java Homework program with a recursive function. */ class Series { /** sumNSquared: returns the sum 1 + 2*2 + 3*3 + 4*4 +... + n*n The computation is done recursively. */ private static int sumNSquared( int n ) { if ( n <= 1 ) return 1; return n*n + sumNSquared( n-1 ); } public static void main( String args[] ) { int n = Integer.parseInt ( args[0] ); System.out.print( "sumNSquared(" + n + ")=" + sumNSquared(n) +"\n\n" ); } }
Example
cs231a@aurora ~ $ javac Series.java cs231a@aurora ~ $ java Series 1 sumNSquared(1)=1 cs231a@aurora ~ $ java Series 2 sumNSquared(2)=5 cs231a@aurora ~ $ java Series 10 sumNSquared(10)=385 cs231a@aurora ~ $ java Series 100 sumNSquared(100)=338350
Questions
Please answer the following questions on Moodle:
- Question 1
- What is the smallest integer number provided on the command line that will generate an arithmetic overflow of the result?
- Question 2
- Will the Java Virtual Machine crash when an airthmetic overflow of the result occurs in the program?
- Question 3
- How many recursive calls will take place before a stack overflow error occurs?
Problem 3
Create an assembly program called hw8c.asm that implements the program of Problem 2, with a slight modification: your program will prompt the user for a number, and will output the series corresponding to that number.
Examples
cs231a@aurora ~ $ ./hw8c > 5 55 cs231a@aurora ~ $ ./hw8c > 1 1 cs231a@aurora ~ $ ./hw8c > 10 385
Submission
Submit your program in the Homework 8 Problem 3 section on Moodle.
Solution Program
Problem 1
;;; ------------------------------------------------------ ;;; hw8_2.asm ;;; D. Thiebaut ;;; ------------------------------------------------------ global f1 global f2 global f3 ;;; ------------------------------------------------------ ;;; f1( s ): modifies s in place and make it uppercase. f1: push ebp mov ebp, esp push ebx mov ebx, dword[ebp+8] .for: cmp byte[ebx], 0 je .done cmp byte[ebx],'a' jl .endfor cmp byte[ebx],'z' jg .endfor add byte[ebx],'A'-'a' .endfor: inc ebx jmp .for .done: pop ebx pop ebp ret 4 ;;; ------------------------------------------------------ ;;; f2( a, b, c ) ;;; returns 2a + 3b -c in eax ;;; computes it as 2(a+b) + b - c (fewer operations) f2: push ebp mov ebp, esp mov eax, dword[ebp+8+4+4] ; get first param add eax, dword[ebp+8+4] ; eax <- a+b add eax, eax ; eax <- 2(a+b) add eax, dword[ebp+8+4] ; eax <- 2(a+b) + b sub eax, dword[ebp+8] ; eax <- 2a + 3b -c pop ebp ; ret 4*3 ; return and get rid of 3 ints ;;; ------------------------------------------------------ ;;; f3( array, n ) ;;; computes the number of even ints in array, of length n. ;;; returns this number in eax. f3: push ebp mov ebp, esp push ebx push ecx mov ebx, dword[ebp+8+4] ; ebx <- array mov ecx, dword[ebp+8] ; ecx <- n mov eax, 0 ; number of even ints .for: and dword[ebx], 1 ; and array[i] with 1 jnz .notEven ; if result is 1, then odd number .even: inc eax ; otherwise, add 1 to counter. .notEven: add ebx, 4 loop .for pop ecx pop ebx pop ebp ret 2*4
Problem 2
Question 1: what value of n creates an overflow? Answer: 1861 1860 sumNSquared(1860)=2146682110 1861 sumNSquared(1861)=-2144821865 Question 2: The Java VM does not crash when the number provided on the command line generates an overflow Question 3: We use bash: for i in `seq 9000 10000` ; do java Series $i ; done &> output.txt The bash loop above runs the Series program for all values of i ranging in 9000 to 10000, and outputs both stdout and stderr to the file output.txt grep -B 5 -i stackOverflow output.txt | head -n 10 The command above looks for the lines containing "stackoverflow", and ask to see 5 lines BEFORE the matching line (-B 5). The "head -n 10" pipe keeps only the first 10 lines of the output of grep: Here's the output of the bash command: sumNSquared(9923)=-675808722 sumNSquared(9924)=-577322946 Exception in thread "main" java.lang.StackOverflowError -- at Series.sumNSquared(Series.java:15) at Series.sumNSquared(Series.java:15) at Series.sumNSquared(Series.java:15) So the answer is that the stack overflow occurs for n = 9925.
Problem 3
;;; -------------------------------------------------- ;;; hw8c.asm ;;; D. Thiebaut ;;; Uses a recursive function to compute ;;; n*n + (n-1)*(n-1) + ... + 3*3 + 2*2 + 1*1 ;;; ;;; -------------------------------------------------- section .data n dd 0 prompt db "> " section .text global _start extern _printInt extern _println extern _getInput extern _printString ;;; -------------------------------------------------- ;;; def series( n ): ;;; if n==1: ;;; return 1 ;;; res = series( n-1 ) ;;; return n*n + res ;;; -------------------------------------------------- ;;; passes n in stack, returns result in eax series: push ebp mov ebp, esp push ebx ;save regs used by function push edx .if: cmp dword[ebp+8], 1 jg .recurse mov eax, 1 jmp .endSeries .recurse: mov eax,dword[ebp+8] mul dword[ebp+8] push eax ;save n*n in stack, temporarily mov eax,dword[ebp+8] ;eax <- n dec eax ;eax <- n-1 push eax ;pass n-1 to fact call series ;eax <- series(n-1) pop ebx ;get n*n add eax,ebx ;eax <- n*n + series(n-1) .endSeries: pop edx pop ebx pop ebp ret 4 ;;; def main(): ;;; n = 5 ;;; print( series( n ) ) ;;; main() _start: ;; get n from user mov ecx, prompt mov edx, 2 call _printString call _getInput mov dword[n], eax ;; call series push dword[n] call series ;; print result passed in eax call _printInt call _println exit: mov eax, 1 mov ebx, 0 int 0x80