Difference between revisions of "CSC231 Homework 8 Fall 2017"

From dftwiki3
Jump to: navigation, search
(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)
 
----
 
----
<!--center>
 
<font size="+2">Page under construction!</font>
 
</center>
 
<P>
 
<center>
 
[[File:UnderConstruction.jpg|300px]]
 
</center-->
 
 
<br />
 
<br />
 +
<bluebox>
 +
This homework assignment is due Monday Dec. 4th, at 11:55 p.m. 
 +
</bluebox>
 
<br />
 
<br />
 
<br />
 
<br />
=Problem #2=
+
__TOC__
 
<br />
 
<br />
Write an assembly program called '''hw8_2.asm''' that contains several functions, but no main program.  The main program will be in a separate file, that will be assembled separately, and linked to your program to create a fully executable file.
+
=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 contains 2a + 3b - c = 2*3 + 3*5 - 7 = 14
+
; 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 '''hw8_2.asm''' program should contain only the 3 functions described above.  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:
+
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 hw8_2.asm program:
+
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 hw8_2.asm'''
+
  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 hw8_2.o 231Lib.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 that f3 does not modify the ebx, ecx, edx, esi, or edi registers.  You can add additional  testing yourself!   
+
: 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 />
  
 
<!-- ==================================================================== -->
 
<!-- ==================================================================== -->
  
<onlydft>
+
 
 
<br />
 
<br />
 
<br /><br />
 
<br /><br />
Line 188: Line 272:
 
<br />
 
<br />
 
=Solution Program=
 
=Solution Program=
 +
 
==Problem 1==
 
==Problem 1==
 
<br />
 
::<source lang="C">
 
#include <stdio.h>
 
#include <stdlib.h>
 
#include <string.h>
 
 
 
void main( int argc, char *argv[] ) {
 
  char *marker1, *marker2, *DNA;
 
  char *fileName;
 
 
  if (argc < 4 ) {
 
    printf( "syntax: %s marker1 marker2 DNA\n", argv[0] );
 
    return;
 
  }
 
 
  marker1 = argv[1];
 
  marker2 = argv[2];
 
  DNA    = argv[3];
 
 
 
  //--- print the markers and DNA ---
 
  /* (for debugging purposes)
 
  printf( "Marker1 = %s\n", marker1 );
 
  printf( "Marker2 = %s\n", marker2 );
 
  if ( strlen( DNA ) > 80 )
 
    printf( "DNA    = %.*s...%s (%d bases)\n\n",
 
          10, DNA, DNA+((int)strlen(DNA)-10),
 
  (int) strlen( DNA) );
 
  else
 
    printf( "DNA    = %s\n\n", DNA );
 
  */
 
 
  //--- add your code below this point ---
 
  char *first, *second;
 
  first = strstr( DNA, marker1 );
 
  if ( first == NULL ) {
 
    printf( "%s\n", DNA );
 
    return;
 
  }
 
  second = strstr( first+1, marker2 );
 
  if ( second == NULL ) {
 
    printf( "%s\n", DNA );
 
    return;
 
  }
 
 
 
  char *p;
 
  for ( p= first; p < second+strlen(marker2); p++ )
 
    *p = '-';
 
 
  printf( "%s\n", DNA );
 
}
 
</source>
 
==Problem 2==
 
 
<br />
 
<br />
 
::<source lang="asm">
 
::<source lang="asm">
Line 317: Line 348:
  
 
</source>
 
</source>
</onlydft>
+
==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 11: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.




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